rpart中分类变量的处理方法

Question

我想知道rpart如何处理分类变量。有几个参考资料表明，对于无序因子，它会查看所有组合。实际上，即使在vignette的第6.2节中也指出：

对于具有m个级别的分类预测变量，将测试所有2^m−1种不同的可能分割。

然而，根据我的经验，我发现很难相信这一点。vignette展示了一个支持证据，运行

rpart(Reliability ~ ., data=car90) 

通常情况下，处理这样的任务需要花费很长很长的时间。然而在我的情况下，它只需要几秒钟就能完成。尽管存在一个具有30个级别的无序因子变量。

为了更好地说明问题，我创建了几个具有52个级别的变量，这意味着如果探索了所有可能性，则需要检查2^51 - 1 ~ 2.2 10^15个分裂。但是这段代码只需约一分钟即可运行，这证明了并没有检查所有组合。

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

rpart 实际上检查了哪些分类变量的组合？

- Love-R

Answer 1

我知道这是一个老问题，但我找到了this link，可能会解答其中的一些问题。

底线是rpart似乎应用了一个简单的算法：

• 首先，对条件均值p_i = E(Y|X = x_i)进行排序
• 然后根据从该排序获得的组计算基尼指数。
• 选择给出这些基尼指数最大值的两个组。

因此，它不应该是计算上昂贵的。

然而，我个人有一个案例，其中我有一个单一的分类变量，其类别是美国各州，当尝试使用它来生成分类树时，rpart会超时。使用51个变量（每个州一个）创建虚拟变量并运行rpart可以正常工作。

- wohlrajh