R's randomForest can not handle more than 32 levels. What is workaround?

Question

R's randomForest package can not handle factor with more than 32 levels. When it is given more than 32 levels, it emits an error message:

Can not handle categorical predictors with more than 32 categories.

But the data I have has several factors. Some of them have 1000+ levels and some of them have 100+. It even has 'state' of united states which is 52.

So, here's my question.

1. Why is there such limitation? randomForest refuse to run even for the simple case.

   > d <- data.frame(x=factor(1:50), y=1:50)
   > randomForest(y ~ x, data=d)
     Error in randomForest.default(m, y, ...) : 
     Can not handle categorical predictors with more than 32 categories.
   

   If it is simply due to memory limitation, how can scikit learn's randomForeestRegressor run with more than 32 levels?

2. What is the best way to handle this problem? Suppose that I have X1, X2, ..., X50 independent variables and Y is dependent variable. And suppose that X1, X2 and X3 has more than 32 levels. What should I do?

   What I'm thinking of is running clustering algorithm for each of X1, X2 and X3 where distance is defined as difference in Y. I'll run three clusterings as there are three problematic variables. And in each clustering, I wish I can find similar levels. And I'll merge them.

   How does this sound?

Answer 1

It is actually a pretty reasonable constrain because a split on a factor with $N$ levels is actually a selection of one of the $2^N-2$ possible combinations. So even with $N$ like 25 the space of combinations is so huge that such inference makes minor sense.

Most other implementations simply treat factor as an ordinal one (i.e. integers from 1 to $N$), and this is one option how you can solve this problem. Actually RF is often wise enough to slice this into arbitrary groups with several splits.

The other option is to change representation -- maybe your outcome does not directly depend on state entity but, for instance, area, population, number of pine trees per capita or other attribute(s) you can plug into your information system instead.

It may be also that each state is such an isolated and uncorrelated entity that it requires a separate model for itself.

Clustering based on a decision is probably a bad idea because this way you are smuggling information from the decision into attributes, which often ends in overfitting.

Answer 2

The main reason is how randomForest is implemented. Implementation from R follows a lot from the original Breiman's specifications. What is important here to note is that for factor/categorical variables, the split criteria is binary with some label values on the left and the rest label values on the right.

That means it searches for all combinations of grouping label values in two groups. If you denote with $0$ the left group and with $1$ the right group and you enumerate for each label one digit, you will get a number in range $[0;2^M-1]$ combinations, which is prohibitive from a computational point of view.

Why the implementations from Weka and Python works?

The weka implementation does not use CART trees by default. It uses C45 trees which does not have this computational problem, since for categorical inputs it splits in multiple node, one for each level value.

The python random forest implementation can't use categorical/factor variables. You have to encode those variables into dummy or numerical variables.

Another implementations might allow multiple levels (including weka here) because even if they use CART, they does not necessarily implements twoing. Which means they allow finding best split for a factor variable only by grouping one label against all the other values. This is requires by far less computation since it needs to check only $M$ split points.

Answer 3

You might try representing that one column differently. You could represent the same data as a sparse dataframe.

Minimum viable code;

example <- as.data.frame(c("A", "A", "B", "F", "C", "G", "C", "D", "E", "F"))
names(example) <- "strcol"

for(level in unique(example$strcol)){
      example[paste("dummy", level, sep = "_")] <- ifelse(example$strcol == level,     1, 0)
}

Notice how each value in the original column now becomes a separate dummy column.

More extensive example code;

set.seed(0)
combs1 = sample.int(33, size= 10000, replace=TRUE)
combs2 = sample.int(33, size= 10000, replace=TRUE)
combs3 = combs1 * combs2 + rnorm(10000,mean=0,100)
df_hard = data.frame(y=combs3, first=factor(combs1), second=factor(combs2))

for(level in unique(df_hard$first)){
    df_hard[paste("first", level, sep = "_")] <- ifelse(df_hard$first == level, 1, 0)
}

for(level in unique(df_hard$second)){
    df_hard[paste("second", level, sep = "_")] <- ifelse(df_hard$second == level, 1, 0)
}

example$first <- NULL
example$second <- NULL

rf_mod = randomForest( y ~ ., data=example )

Even though this piece of code shows that you indeed will no longer get the error, you will notice that the randomForest algorithm now needs a long time before it finishes. This is due to a CPU constraint, you could map reduce this task via sampling now as well.

For more information please check out this blogpost:

https://blog.cloudera.com/blog/2013/02/how-to-resample-from-a-large-data-set-in-parallel-with-r-on-hadoop/

Answer 4

Another option: depending on the number of levels and number of observations in your data, you could merge some levels. Beyond getting under the limit, it may reduce variance if you have many levels with just a few observations. Hadley's forcats:fct_lump does this.

Answer 5

You may use package extraTrees instead. Extremely randomized forests algorithm do not try any breakpoint/split, but only a limited random subset of splits.