Treatment of categorical variables in rpart

user_3241151 0
Viewed 863

I wonder how rpart treats categorical variables. There are several references suggesting that for unordered factors it looks through all combinations. Actually, even the vignette at the end section 6.2 states

(F)or a categorical predictor with m levels, all 2^m−1 different possible splits are tested.

However, given my experience with the code, I find it difficult to believe. The vignette shows a supporting evidence that running

rpart(Reliability ~ ., data=car90)

takes a really long, long time. However, in my case, it runs in seconds. Despite having an unordered factor variable with 30 levels. To demonstrate the issue further, I have created several variables with 52 levels, meaning that 2^51 - 1 ~ 2.2 10^15 splits would need to be checked if all possibilities were explored. This code runs in about a minute, IMHO proving that all combinations are not checked. 

NROW = 50000
NVAR = 20

rand_letters = data.frame(replicate(NVAR, as.factor(c(
  letters[sample.int(26, floor(NROW/2), replace = TRUE)],
  LETTERS[sample.int(26, ceiling(NROW/2), replace = TRUE)]))))
rand_letters$target = rbinom(n = NROW, size = 1, prob = 0.1)

system.time({
  tree_letter = rpart(target ~., data = rand_letters, cp = 0.0003)
})
tree_letter

What combinations of categorical variables are ACTUALLY checked in rpart?

decision-tree r
1 Answers

I know it is an old question but I found this link that might answer some of it.

Bottom line is that rpart seems to be applying a simple algorithm:

  • First, sort the conditional means, p_i = E(Y|X = x_i)
  • Then compute Gini indices based on groups obtained from that ordering.
  • Pick the two groups giving the maximum of these Gini indices.

So it should not be nearly as computationally expensive.

However, I personally have a case where I have a single categorical variable, whose categories are US states, and rpart overtimes when trying to use it to produce a classification tree. Creating dummy variables and running rpart with the 51 variables (1 for each state) works fine.

user_46950110
Related