Why doesn't Random Forest handle missing values in predictors?

Question

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

Answer 1

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.

Answer 2

"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).

Answer 3

Random forest does handle missing data and there are two distinct ways it does so:

1) Without imputation of missing data, but providing inference. 2) Imputing the data. Imputed data is then used for inference.

Both methods are implemented in my R-package randomForestSRC (co-written with Udaya Kogalur). First, it is important to remember that because random forests employs random feature selection, traditional missing data methods used by single trees (CART and the like) do not apply. This point was made in Ishwaran et al. (2008), "Random Survival Forests", Annals of Applied Statistics, 2, 3, and nicely articulated by one of the commenters.

Method (1) is an "on the fly imputation" (OTFI) method. Prior to splitting a node, missing data for a variable is imputed by randomly drawing values from non-missing in-bag data. The purpose of this imputed data is to make it possible to assign cases to daughter nodes in the event the node is split on a variable with missing data. Imputed data is however not used to calculate the split-statistic which uses non-missing data only. Following a node split, imputed data are reset to missing and the process is repeated until terminal nodes are reached. OTFI preserves the integrity of out-of-bag data and therefore performance values such as variable importance (VIMP) remain unbiased. The OTFI algorithm was described in Ishwaran et al (2008) and implemented in the retired randomSurvivalForest package, and has now been extended to randomForestSRC to apply to all families (i.e. not just survival).

Method (2) is implemented using the "impute" function in randomForestSRC. Unsupervised, randomized, and multivariate splitting methods for imputing data are available. For example, multivariate splitting generalizes the highly successful missForest imputation method (Stekhoven & Bühlmann (2012), "MissForest—non-parametric missing value imputation for mixed-type data", Bioinformatics, 28, 1). Calling the impute function with missing data will return an imputed data frame which can be fit using the primary forest function "rfsrc".

A detailed comparison of the different forest missing data algorithms implemented using "impute" was described in a recent paper with Fei Tang "Random forest missing data algorithms", 2017. I recommend consulting the help files of "rfsrc" and "impute" from randomForestSRC for more details about imputation and OTFI.

Answer 4

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.

Answer 5

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.

Answer 6

For CART, you can apply the missing-in-attributes (MIA) approach. That is, for categorical predictors, you code missing as a separate category. For numerical predictors, you create two new variables for every variable with missings: one where you code missings as -Inf and one where you code missings as +Inf. Then you apply a random forest function as usual to your data.

Advantages of MIA:

1. Computationally cheap
2. Does not yield multiple datasets and thereby models, as multiple imputation does (the imputation-of-missing-data literature generally agrees that one imputed dataset is not enough)
3. Does not require you to choose a statistical method and/or model for imputing the data.
4. If values are MNAR, and missingness is in fact predictive of the outcome, MIA may outperform multiple imputation

Functions ctree() and cforest() from package partykit allow for applying MIA by passing ctree_control(MIA = TRUE) to their control arguments.

Jerome Friedman's RuleFit program appears to use MIA for dealing with missings, see https://statweb.stanford.edu/~jhf/r-rulefit/rulefit3/RuleFit_help.html#xmiss.

A description of the MIA approach can be found in Twala et al. (2008):

Twala, B.E.T.H., Jones, M.C., and Hand, D.J. (2008). Good methods for coping with missing data in decision trees. Pattern Recognition Letters, 29(7), 950-956.

Answer 7

Instead of using median values, etc., I would highly recommend looking at the missRanger package (currently in development on Github) or the R package missForest). Both of these packages use random forests to first impute your data using a method similar to multiple imputation via chained equations (MICE). This would be the appropriate imputation method to use as it corresponds closely to your actual analysis model. You can then use all your data without having to worry about dropping individual rows due to missing observations. In addition, the imputed values will be far more realistic than simply selecting medians or modes.

You can use just one filled-in imputed data set for your analyses, but the best way to incorporate uncertainty over missing values is to run multiple runs of these imputation methods, and then estimate your model on each of the resulting datasets (i.e., multiple imputation) and then combine the estimates using Rubin's rules (see R package mitools).