How to use Random Forest for categorical variables with missing value

Question

I have a labelled dataset of 1M rows and 600 features. I am trying to build a supervised learning model for prediction. I am particularly working with Random forests in R. The data I have has following properties.

1. Most of the features are categorical in nature.
2. Each categorical variable has multiple levels ( some of them having 20 levels)
3. Some of the features have data missing

Can random forests work without imputation of these missing values? If no, then what is the best way to impute these missing categorical values? Any literature or R functionality which addresses this issue will be really helpful.

Answer 1

Off the top of my head, I would say that this shouldn't be an issue. The rf package in R implements random forests using CARTs. One of the nicest thing about trees is how they are "natively" capable of dealing with categorical and missing variables. Here is the package documentation; you can download the package itself from CRAN.

Chapter 8 in James, Witten, Hastie, & Tibshirani's Introduction to Statistical Learning with Applications in R offers a good introduction to tree methods and also covers random forests on page 328.

Imputing missing variables is a whole thing in and of itself and, depending on your needs and data, you might be able to get away with not having to do it. If you do have to perform imputation you might want to check here and here for some quick pointers, but you're probably just going to have to read up on imputation methods and make a judgement call on what to go with.

Answer 2

The R randomForest package includes functions for doing a rough imputation of missing values and then iterativelly improving this imputation based on case proximity in RF runs.

There are a bunch of other methods that have been proposed as ways rf's and decision trees can handle missing values:

1) Leave them out when split and do a bias correction for the reduction in impurity.

2) Split them onto a a third branch at each node.

3) Label them as a separate category as chf suggests. For numerical features impute and create a separate x_is_missing feature.

4) Identify "surrogate splitter" relationships between features by analyzing which features work well in the same place and then use a surrogate to split when a feature is missing.

5) Do a local imputation within the branch of the tree.

I'm not aware of R code for most of these though it may exist.

I implemented a stand alone utility that can do the first two methods: https://github.com/ryanbressler/CloudForest

It is easy enough to use write.arff to dump you're data out and call it and load the predictions (which are stored in a tsv) back in. (The arff file format is nice for categorical data with missing values).

I chose those two methods as they don't increase the computation required on large data sets. I've found the first works well when there are few missing values and they aren't meaningfully distributed...imputation often also works well here.

The second, three way splitting, works well when the fact a value is missing may be significant. This is quite common in poorly designed survey's that don't include a "don't know" or "not applicable" category. Method 3 can also work well here.

Answer 3

You can simply introduce a new level for each categorical variable which represents missing data. Then you would simply replace the missing fields with this new category.