22
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Searching the web with the package name and the error message provides some answers. $\endgroup$ – Roland Feb 4 '13 at 17:08
  • 5
    $\begingroup$ @Roland Actually it lead me here… $\endgroup$ – isomorphismes Oct 9 '14 at 6:42
  • 1
    $\begingroup$ you might try the data science se as several statistical minds there have experience programming for data with many dimensions. $\endgroup$ – aeroNotAuto Apr 30 '15 at 23:57
  • 2
    $\begingroup$ UPDATE: Since version 4.6-9, randomForest can handle categorical predictors with up to 53 levels. News $\endgroup$ – Ben Jun 1 '16 at 23:51
  • $\begingroup$ How does R's random forest determine the number of levels? I guess level means categories. $\endgroup$ – ajp May 26 '17 at 18:20
25
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ It can be easily moved around, though in a slightly tedious manner. For example, if you have between 33 and 1024 levels, create two factors each of <=32 levels. $\endgroup$ – KalEl May 23 '13 at 17:38
15
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Thanks a lot! Does it follow from your answer that R's implementation for treating categorical values is superior to that of Python's (I remember Max Kuhn mentioned grouping categorical variables for RF provides slightly better results than dummifying them), or at the very least running Random Forest in R vs Python I have a very good chance of getting different results (accuracies etc...)? From your experience, when modelling, does it make sense trying both grouping vars (in R) and dummifying them and then comparing two approaches? $\endgroup$ – Sergey Bushmanov Oct 20 '15 at 17:03
  • 2
    $\begingroup$ Dummy encoding works but it can produce only one category vs all. After encoding variables are tested once at a time. So, it's impossible to implement twoing. If this feature can help, I think that practically there are no big differences. However there are other things which might require attention when working with variable importance: some implementations are biased towards categorical with multiple levels. See Carolin Strobl papers for details: statistik.uni-dortmund.de/useR-2008/slides/Strobl+Zeileis.pdf . In R there are some implementations which does not have this bias. $\endgroup$ – rapaio Oct 21 '15 at 6:45
2
$\begingroup$

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/

$\endgroup$
  • $\begingroup$ The second code block looks confusing, Although you use df_hard throughout the body, at the last lines, you set "first" and "second" to NULL, and also use "example" as the data for randomForest this doesn't make sense to me, since there is no connection between example and df_hard. $\endgroup$ – Özgür May 3 '15 at 10:51
  • $\begingroup$ Vincent, don't you feel I will end up with such great trouble if I have levels of the order 100+, do you suggest to add each column as input to random? $\endgroup$ – Hardik Gupta Jan 6 '17 at 8:49
  • $\begingroup$ Another alternative is to use the randomforest implementation in h2o; this has better support for large datasets. I don't understand the "add each column as input to random" bit. $\endgroup$ – Vincent Warmerdam Jan 6 '17 at 14:22
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ extraTrees has limitation, in the sense your input has to be a numeric data matrix right? $\endgroup$ – Hardik Gupta Jan 6 '17 at 9:49
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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