Which regression tree to use for large data?

Question

I have a dataframe with 2 million rows and approximately 200 columns / features. Approximately 30-40% of the entries are blank. I am trying to find important features for a binary response variable. The predictors may be categorical or continuous.

I started with applying logistic regression, but having so much missing entries I feel that this is not a good approach as glm discard all records which have any item blank. So I am now looking to apply tree based algorithms (rpart or gbm) which are capable to handle missing data in a better way.

Since my data is too big for rpart or gbm, I decided to randomly fetch 10,000 records from original data, apply rpart on that, and keep building a pool of important variables. However, even this 10,000 records seem to be too much for the rpart algorithm.

What can I do in this situation? Is there any switch that I can use to make it fast? Or it is impossible to apply rpart on my data.

I am using the following rpart command:

varimp = rpart(fmla,  dat=tmpData, method = "class")$variable.importance

Answer 1

Simple answer:

Why don't you just simply drop the features which have a large amount of missing data from your analysis? They give you little information and are unlikely to be useful predictors. However if you start dropping the rows with missing data that might start introducing bias in your results. This highlights the more fundamental problem of dealing with missing data.

More involved answer:

Missing data is a well established problem in statistics and there are techniques which deal with this issue. One way you could go about addressing the missing data problem is to attempt to impute i.e guess the missing data. Once you've done that you would then be able to run a logistic regression. To factor in the uncertainty you introduce when guessing the missing data you could generate multiple imputed data sets and use the R package mitools when doing the logistic regression. I have used this approach in my data. However how you go about doing the actual imputation/guessing depends on the properties of your dataset. Are certain features correlated for example?

Regarding your question about the performance of the classification regression tree method, I have not used this technique extensively but I imagine it is going to struggle with a large number of features since from my understanding it would construct a classification tree of at least 200 nodes. No idea how it deals with missing data either. It is a bit alarming if it doesn't complain!

I think logistic regression is your best bet but you need to figure out how to deal with the missing data.

Take home message: be wary about missing data don't run methods without knowing how they deal with missing data and what assumptions they make.

Answer 2

It may be helpful to randomly fetch fewer records (try 2000 or 5000). From here what I would do is try making multiple classification trees and average your results across trees. Here's a great video by Wallace Campbell showing how to average multiple trees to decide on one tree (http://vimeo.com/71992876). I'd also recommend taking a look over your 200 columns. To save on computing power you may come across columns little to no variability. These predictors may not be useful to you or others. You may save some computer power by seeing if this exclusion improves your ability to run your analyses.

Allowing surrogates in your decision tree would greatly influence your prediction and allow you to avoid imputation. You may want to experiment the number of surrogates you allow in your model.

Answer 3

I can't comment on the relative performance with respect to rpart, but you might want to try imputing using Gradient Boosted Models (gbm package in R; a.k.a. gradient-boosted machines).

Here is a link describing how it's used : http://s3l.stanford.edu/blog/?p=73

Here is a link to Jeff Wong's GitHub repo with the R code for the function : https://github.com/jeffwong/imputation/blob/master/R/gbmImpute.R

As another poster suggested, it's probably worth trying gbm again with a smaller random sample of your original data set. In this case, running a few different times with different randomly sample (with replacement) subsets might help you avoid over-training.

Note that the gbm package deals with missing values implicitly, i.e. the method is internal or black-box. I'm fairly sure it uses surrogate splitting to deal with missing values but have yet to find a definitive answer and/or dig through the C++ and FORTRAN code to figure it out.

Answer 4

If you want to do logistic regression, a simple approach is:

• for each continuous feature with missing data, replace all missing values by the average or median value for this feature, and create one more boolean feature which indicates whether the data is missing or not
• for each unordered categorical feature with missing data, put all missing values into a new category