Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

What are theoretical reasons to not handle missing values? Gradient boosting machines, regression trees handle missing values. Why doesn't Random Forest do that?

share|improve this question
    
They are handled in the party R package. One blog article here: exegetic.biz/blog/2013/05/… –  Stéphane Laurent Dec 12 at 12:01

4 Answers 4

up vote 6 down vote accepted

Gradient Boosting Trees uses CART trees (in a standard setup, as it was proposed by its authors). CART trees are also used in Random Forests. What @user777 said is true, that RF trees handles missing values either by imputation with average, either by rough average/mode, either by an averaging/mode based on proximities. These methods were proposed by Breiman and Cutler and are used for RF. This is a reference from authors Missing values in training set.

However, one can build a GBM or RF with other type of decision trees. The usual replacement for CART is C4.5 proposed by Quinlan. In C4.5 the missing values are not replaced on data set. Instead, the impurity function computed takes into account the missing values by penalizing the impurity score with the ration of missing values. On test set the evaluation in a node which has a test with missing value, the prediction is built for each child node and aggregated later (by weighting).

Now, in many implementations C4.5 is used instead of CART. The main reason is to avoid expensive computation (CART has more rigorous statistical approaches, which require more computation), the results seems to be similar, the resulted trees are often smaller (since CART is binary and C4.5 not). I know that Weka uses this approach. I do not know other libraries, but I expect it to not be a singular situation. If that is the case with your GBM implementation, than this would be an answer.

share|improve this answer
    
@user777 is referring to RF and NOT to CART. –  Prophet60091 Dec 11 at 20:50
    
Let us continue this discussion in chat. –  Prophet60091 Dec 11 at 21:29

Recursive partitioning uses surrogate splits based on non-missing predictors that are correlated with the predictor possessing the missing value for an observation. It would seem possible in theory for random forests to be implemented that use the same idea. I don't know if any random forest software has done so.

share|improve this answer

"What are [the] theoretical reasons [for RF] to not handle missing values? Gradient boosting machines, regression trees handle missing values. Why doesn't Random Forest do that?"

RF does handle missing values, just not in the same way that CART and other similar decision tree algorithms do. User777 correctly describes the two methods used by RF to handle missing data (median imputation and/or proximity based measure), whereas Frank Harrell correctly describes how missing values are handled in CART (surrogate splits). For more info, see links on missing data handling for CART (or it's FOSS cousin: RPART) and RF.

An answer to your actual question is covered clearly, IMHO, in Ishwaran et al's 2008 paper entitled Random Survival Forests. They provide the following plausible explanation for why RF does not handle missing data in the same way as CART or similar single decision tree classifiers:

"Although surrogate splitting works well for trees, the method may not be well suited for forests. Speed is one issue. Finding a surrogate split is computationally intensive and may become infeasible when growing a large number of trees, especially for fully saturated trees used by forests. Further, surrogate splits may not even be meaningful in a forest paradigm. RF randomly selects variables when splitting a node and, as such, variables within a node may be uncorrelated, and a reasonable surrogate split may not exist. Another concern is that surrogate splitting alters the interpretation of a variable, which affects measures such as [Variable Importance].

For these reasons, a different strategy is required for RF."

This is an aside, but for me, this calls into question those who claim that RF uses an ensemble of CART models. I've seen this claim made in many articles, but I've never seen such statements sourced to any authoritative text on RF. For one, the trees in a RF are grown without pruning, which is usually not the standard approach when building a CART model. Another reason would be the one you allude to in your question: CART and other ensembles of decision trees handle missing values, whereas [the original] RF does not, at least not internally like CART does.

With those caveats in mind, I think you could say that RF uses an ensemble of CART-like decision trees (i.e., a bunch of unpruned trees, grown to their maximum extent, without the ability to handle missing data through surrogate splitting). Perhaps this is one of those punctilious semantic differences, but it's one I think worth noting.


EDIT: On my side note, which is unrelated to the actual question asked, I stated that "I've never seen such statements sourced to any authoritative text on RF". Turns out Breiman DID specifically state that CART decision trees are used in the original RF algorithm:

"The simplest random forest with random features is formed by selecting at random, at each node, a small group of input variables to split on. Grow the tree using CART methodology to maximum size and do not prune." [My emphasis]

Source: p.9 of Random Forests. Breiman (2001)

However, I still stand (albeit more precariously) on the notion that these are CART-like decision trees in that they are grown without pruning, whereas a CART is normally never run in this configuration as it will almost certainly over-fit your data (hence the pruning in the first place).

share|improve this answer

Random Forest has two methods for handling missing values, according to Leo Breiman and Adele Cutler, who invented it.

The first is quick and dirty: it just fills in the median value for continuous variables, or the most common non-missing value by class.

The second method fills in missing values, then runs RF, then for missing continuous values, RF computes the proximity-weighted average of the missing values. Then this process is repeated several times. Then the model is trained a final time using the RF-imputed data set.

share|improve this answer
    
Thank you for your answer! But, both this methods are replacing missing values. But in GBM or regression trees missing values don't replace for anything. What is theoretical difference between, for example GBM and RF in this sense? –  Kristina May 16 at 13:22
    
I'm not an expert on GBM, but the RF handling of missing values appears to be rooted in the idea of imputation, en.wikipedia.org/wiki/Imputation_(statistics) In cases where missing values are not missing at random, your results can be biased due to missingness. Imputation attempts to recover this missing values and reduce bias. –  user777 May 16 at 14:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.