machine-learning - CART 算法 - 为什么对分类变量进行 2^m-1 -1 分割？

Question

我试图了解有关 CART 算法的更多信息，特别是分类变量考虑了多少个分割。

我正在阅读 ftp://ftp.boulder.ibm.com/software/analytics/spss/support/Stats/Docs/Statistics/Algorithms/14.0/TREE-CART.pdf

和

http://www.stat.wisc.edu/~loh/treeprogs/guide/wires11.pdf

他们都指出，对于分类变量，CART 将考虑 2^m-1 -1 分割。

特别是在第二篇论文中，Loh 教授强调，对于包含 31 个离散值的分类变量，“仅在根节点上”就需要 2^30 -1 次分割。总共有近 20 亿次 split 。

我真的很难清楚地理解这一点，我误解了过程的一部分。如果我计算 31 个值的排列数，结果是 8.22...e+33，这显然远远超过 20 亿。然而，组合数为 31^2 = 961。

在这种情况下，我们如何得出 2^30 次分割的需要？我似乎无法确定这里的规则或逻辑。它似乎不是基于组合学，如果我们只有 31 个值可供分割，我不明白我们如何需要 20 亿次分割。

任何指导将不胜感激。

谢谢

大卫

Answer 1

2^31 来自算法考虑每个可能的分割的想法。因此，左子节点有一组值，右子节点有其余值。

例如，如果前两个值向左移动，则分割将为 11000000000000。 . 。左侧为“1”，右侧为“0”。每个二进制数都是不同的分割(实际上是一半，因为左右是对称的)。

这是一个理论想法。实际情况是确定每个值的纯度测量值(31 次)。然后，根据估计的目标值对它们进行排序。 “较高”的值位于左侧子级，较低的值位于右侧(取决于其他条件，并允许多个拆分和数字目标)。该算法不会对 2^31 种不同的组合进行强力比较。

2^30 来自简单对称。您可以翻转 0 和 1 并获得相同的分割，即 111000000 。 。 。与 000111111 的分割相同。 。 。 child 交换了，但纯度是一样的。 - 1 是因为全 1 或 0 的分割根本不是分割；该算法需要两个子级用于递归分区部分。