通常,在决策树的每个节点处,我们考虑每个特征的所有特征和所有分裂点 . 我们计算整个节点的熵与潜在左右分支的熵的加权平均值之间的差异,并且选择给出我们最大熵降的特征分裂feature_value作为该特定节点的分裂标准 .
有人可以解释为什么上述过程需要(2 ^ m -2)/ 2在每个节点尝试 for each feature ,其中m是节点上不同feature_values的数量,与 trying ONLY m-1 splits 相同:
-
将m个不同的feature_values按节点内采样该功能的feature_value的1个样本的百分比进行排序 .
-
仅尝试分割排序列表的m-1方式 .
这个“仅尝试m-1分裂”的方法在下面的文章中被称为“快捷方式”,其中(根据“快捷方式”的定义)意味着两种方法在运行时大不相同的结果完全相同 .
引用:“对于回归和二元分类问题,K = 2响应类,有一个计算捷径[1] . 树可以通过平均响应(用于回归)或类别概率对其中一个类别进行排序(对于然后,最优分裂是有序列表的L-1分裂之一 . “
请注意,我只谈论分类变量 .
1 回答
答案很简单:两个程序都不一样 . 正如你所注意到的那样,以精确的方式分裂是一个NP难问题,因此在实践中几乎不可能解决任何问题 . 此外,由于过度拟合通常不是发电方面的最佳结果 .
相反,详尽的搜索被某种贪婪的过程取代,如下所示:先排序,然后尝试所有有序的拆分 . 通常,这导致与精确分裂不同的结果 .
为了改善贪婪的结果,还经常应用修剪(可以看作是另一种贪婪和启发式方法) . 从来没有像随机森林或BART这样的方法通过对几棵树进行平均来有效地处理这个问题 - 因此单个树的偏差变得不那么重要了 .