CART 算法 - 为什么 2^m-1 -1 拆分分类变量？
CART Algorithm - why 2^m-1 -1 splits for categorical variables?
我正在尝试了解有关 CART 算法的更多信息，尤其是分类变量考虑了多少拆分。
和
http://www.stat.wisc.edu/~loh/treeprogs/guide/wires11.pdf
他们都声明对于分类变量，CART 将考虑 2^m-1 -1 拆分。
特别是在第二篇论文中，Loh 教授强调，对于包含 31 个离散值的分类变量，需要进行 2^30 -1 次拆分 "on the root node alone"。所以将近20亿次分裂。
我真的很难清楚地理解这一点，我误解了过程的一部分。如果我计算 31 个值的排列数，它会给出 8.22...e+33，这显然超过了 20 亿。然而组合的数量是 31^2 = 961.
在这种情况下，我们如何得出 2^30 次分割的需要？我似乎无法确定这里的规则或逻辑。它似乎不是基于组合学，如果我们只有 31 个值可以拆分，我不明白我们如何需要 20 亿次拆分。
任何指导将不胜感激。
谢谢
大卫
2^31 源于算法正在考虑每个可能的拆分的想法。因此，左侧有一组值 child，右侧有一组值 child。
例如，如果前两个值向左，则拆分为 11000000000000。. .右边是“1"s on the left and the "0”。每个二进制数都是不同的拆分（好吧，实际上是一半，因为左右是对称的）。
这是理论上的想法。在实践中发生的情况是确定每个值的纯度度量（31 次）。然后，这些按估计的目标值排序。 "higher" 值向左 child 和向右下方（取决于其他条件，并允许多个拆分和数字目标）。该算法没有对 2^31 种不同组合进行蛮力比较。
第2^30来自简单对称。您可以翻转 0 和 1 并获得相同的拆分，因此 111000000 。 . .与 000111111 相同。 . . child仁互换，但纯度相同。 - 1 是因为全 1 或全 0 的拆分根本不是拆分；该算法需要两个 children 用于递归分区部分。
你好戈登谢谢你的解释。根据你的回答，如果我有以下数量的离散值，我会有效地得到像这样的二进制序列......
对于 3 个值
Val 1 | Val 2 | Val 3
----- | ----- | -----
0 | 0 | 0 * Not considered
0 | 0 | 1
0 | 1 | 1
0 | 1 | 0
1 | 1 | 0
1 | 0 | 1
1 | 0 | 0
1 | 1 | 1
这是否涵盖了组合部分的大部分内容？
我可以看到基于纯度测量的优化可以减少大量重复，但我需要花一些时间消化那部分才能更好地理解。
谢谢你们的帮助。
大卫
我正在尝试了解有关 CART 算法的更多信息，尤其是分类变量考虑了多少拆分。
和
http://www.stat.wisc.edu/~loh/treeprogs/guide/wires11.pdf
他们都声明对于分类变量，CART 将考虑 2^m-1 -1 拆分。
特别是在第二篇论文中，Loh 教授强调，对于包含 31 个离散值的分类变量，需要进行 2^30 -1 次拆分 "on the root node alone"。所以将近20亿次分裂。
我真的很难清楚地理解这一点，我误解了过程的一部分。如果我计算 31 个值的排列数，它会给出 8.22...e+33，这显然超过了 20 亿。然而组合的数量是 31^2 = 961.
在这种情况下，我们如何得出 2^30 次分割的需要？我似乎无法确定这里的规则或逻辑。它似乎不是基于组合学，如果我们只有 31 个值可以拆分，我不明白我们如何需要 20 亿次拆分。
任何指导将不胜感激。
谢谢
大卫
2^31 源于算法正在考虑每个可能的拆分的想法。因此，左侧有一组值 child，右侧有一组值 child。
例如，如果前两个值向左，则拆分为 11000000000000。. .右边是“1"s on the left and the "0”。每个二进制数都是不同的拆分（好吧，实际上是一半，因为左右是对称的）。
这是理论上的想法。在实践中发生的情况是确定每个值的纯度度量（31 次）。然后，这些按估计的目标值排序。 "higher" 值向左 child 和向右下方（取决于其他条件，并允许多个拆分和数字目标）。该算法没有对 2^31 种不同组合进行蛮力比较。
第2^30来自简单对称。您可以翻转 0 和 1 并获得相同的拆分，因此 111000000 。 . .与 000111111 相同。 . . child仁互换，但纯度相同。 - 1 是因为全 1 或全 0 的拆分根本不是拆分；该算法需要两个 children 用于递归分区部分。
你好戈登谢谢你的解释。根据你的回答，如果我有以下数量的离散值，我会有效地得到像这样的二进制序列...... 对于 3 个值
Val 1 | Val 2 | Val 3
----- | ----- | -----
0 | 0 | 0 * Not considered
0 | 0 | 1
0 | 1 | 1
0 | 1 | 0
1 | 1 | 0
1 | 0 | 1
1 | 0 | 0
1 | 1 | 1
这是否涵盖了组合部分的大部分内容？
我可以看到基于纯度测量的优化可以减少大量重复，但我需要花一些时间消化那部分才能更好地理解。
谢谢你们的帮助。
大卫