决策树二进制分类器快捷方式(排序)

Question

通常，在决策树的每个节点，我们考虑每个特征的所有特征和所有分裂点。计算了整个节点的熵与势左、右分支熵的加权avg之差，并选择给出最大熵降的特征+分裂feature_value作为该节点的分裂判据。

有人能解释为什么上面的进程(要求(2^m -2)/2 )在每个节点上为每个特性尝试(其中m是节点上不同的feature_values数)与只尝试m-1拆分的相同。

1. 按照接受该特性的feature_values的节点中的样本的1的百分比对m个不同的feature_value进行排序。
2. 只尝试使用m-1方式拆分排序列表。

在下面的文章中，这种“只尝试m-1拆分”的方法被称为“快捷方式”，这意味着这两种方法在运行时的结果完全相同。

引用：“对于回归和二进制分类问题，对于K=2个响应类，有一个计算捷径1。树可以按平均响应(用于回归)或对其中一个类的类概率排序(用于分类)。然后，最优分割是有序列表的L1分裂之一。”

文章：drop&requestedDomain=uk.mathworks.com

请注意，我只讨论范畴变量。

Answer 1

是否有人能解释一下，上述进程(要求(2^m -2)/2 )在每个节点上尝试每个特性(其中m是节点上不同的feature_values数)与只尝试m-1拆分相同：

答案很简单:这两种程序并不相同。正如您注意到的，分裂的确切方式是一个NP难问题，因此几乎不可能在实践中的任何问题。此外，由于过度拟合，这通常不会是最优的结果，就泛化。

相反，穷尽搜索被某种贪婪的过程所取代，它是这样的:先排序，然后尝试所有有序的拆分。通常情况下，这会导致与精确分裂不同的结果。

为了改善贪婪的结果，人们经常采用剪枝(这可以看作是另一种贪婪的启发式方法)。从来没有像随机森林或BART这样的方法通过对几棵树的平均来有效地处理这个问题--这样一棵树的偏差就变得不那么重要了。