决策树详解——精选推荐

决策树详解

⼀、背景

⽹上有很多排序算法的总结，整理的⼀⽬了然，惹⼈喜爱，但关于决策树的相关博⽂，普遍存在以下问题1）归纳程度不⾜，深度不够

2）总结点不⾜，有些疑问找不到答案

3）照抄现有书籍上的公式和推导过程

于是想到⾃⼰整理⼀篇关于决策树的⽂章，同时也加深⾃⼰的理解

⼆、正⽂⾸先，不说话，直接上图

在解释上图之前，⾸先声明，本⽂尽可能避免公式的罗列（想看的可以翻书或者搜相关博⽂），尽量⽤⾃然语⾔（⼈话）去解释相关的概念。

要理解决策树之前，要理解如下⼏个概念：1、概率，符号表⽰为p, p(x)代表随机事件x发⽣的概率，⽐如x代表天⽓情况，就有天⽓晴朗的概率和下⾬的概率

2、信息量， 符号表⽰为h，h(x)代表随机事件x发⽣这件事包含多少信息量，h(x) = -logp(x)，我们看到概率越⼩，信息量越⼤；举个例⼦，我们经常调侃某句话或者某张图的信息量有点⼤，在看这段话或这张图的时候你脑海中肯定闪过的是各种污污的⼩概率事件3、熵，物理和化学中的概念，代表⼀个系统的混乱程度，熵越⼤，混乱程度越⼤，⽐如⽔蒸⽓的熵>⽔的熵>冰的熵

4、信息熵，符号表⽰为H, H(x)代表各种x所有可能取值的信息量的期望（可以粗糙地理解为信息量的平均值，实际为加权平均），

，衡量事件x的确定程度，信息熵越⼤代表事件的可能性越多，越不确定，⽐如明天下⾬和晴天的概率均为0.5，也就是不确定性最⼤的情况，这时信息熵为log2；当明天下⾬的概率为1时，确定性最⼤，信息熵为0。

5、条件熵，即为随机事件x发⽣的条件下y

事件的信息熵的期望，，也即表⽰在已知随机变量X的条件下随机变量Y的不确定性的期望，强调的是随机事件x对随机事件y的不确定性的影响。⽐如随机事件y包括今天下⾬或者晴天两种情况，随机事件x包括昨天晚上下⾬或者晴天的两天情况；如果昨天晚上下⾬，今天下⾬的概率会增⼤，确定性会增加；如果昨晚晴天，今天晴天的概率会增加，确定性也会增加；所以考虑昨晚的天⽓情况x时，y的不确定性（条件熵）会减少。6、信息增益（互信息）。随机变量y的信息熵减去考虑随机变量x的y的条件熵，即为信息增益；衡量在考虑随机变量x的情况下y的不确定性减少的程度。

7、信息增益率。信息增益率的存在意义在于弥补信息增益的应⽤缺陷。信息增益主要⽤于帮助选择某个能够最⼤程度减少⽬标变量不确定性的特征（随机变量），考虑极端情况，当选择唯⼀id这种随机变量时，会导致条件熵为0，信息增益最⼤，但这种情况没有任何泛化意义，所以需要对类似的情况进⾏惩罚，从⽽帮助我们做出更合理的选择。所以 信息增益率=信息增益/惩罚项，正好考虑到上述极端情况下我们选择的随机变量x的信息熵最⼤，所以惩罚项选择随机变

量x

的信息熵，最后公式为

8、Gini（基尼）指数。从另⼀个⾓度衡量随机变量的不确定性。可以这样理解，随机事件x发⽣的概率为p，然后根据该概率对随机事件x进⾏预测，猜错的可能性为1-p,⽽对随机事件x的所有可能的猜错期望即为基尼指数。即系统越混乱越不确定，猜错的可能性的期望越⾼，基尼指数越⾼。

。（也可以理解为随机抽取两个样本，它们属于不同类别的概率）

在详细说明每种决策树之前，我觉得有必要去理解⼀下决策树是什么：

1、编码⾓度，决策树是⼀系列if-else规则，他能通过⼀系列决策对样本进⾏处理并输出结果；它和硬编码⼀样可以做到对集合中样本的不重不漏地处理，⽽且通过学习算法得到决策树，相⽐⼈为硬编码不易出错，所以我觉得以后开发⼯程师的基本技术栈⾥不仅要包括数据结构与算法，还要包括机器学习。2、概率论⾓度，决策树展⽰了⽬标变量y在给定特征条件下的条件概率分布。

在构造决策树的过程中，主要有三⼤步骤：1、特征选择

2、决策树的⽣成（包含预剪枝）

3、决策树的剪枝（后剪枝）

下⾯我们分别针对三种常⽤的决策树进⾏介绍，他们分别为1、ID3

2、C4.5

3、CART

2.1 ID3决策树

2.1.1 特征选择

应⽤场景：分类

依赖指标：信息熵、条件熵、信息增益1、计算待分类样本的信息熵

2、计算某个特征条件下的条件熵

3、计算信息增益，选择最⼤信息增益对应的特征作为当前划分依据

4、对⼦节点，递归进⾏特征选择，待选择特征集去除了上⼀步已选择过的特征，即某个特征在从根到某个叶⼦结点的路径上不会重复出现

2.1.2 决策树的⽣成

输⼊：训练数据集D, 特征集A，阈值e，决策树的最⼤深度n,作为叶⼦结点要⼩于的样本数量m

输出：决策树T1）若D中所有实例属于同⼀类，则T为单结点树，并将该类作为该结点的类标记，返回T

2）若A为空集，则T为单结点树，并将D中实例树最⼤的类作为该结点的类标记，返回T

3）否则，计算A中各特征对D的信息增益，选择信息增益最⼤的特征Ag4）（预剪枝）如果Ag的信息增益⼩于阈值e,则置T为单结点树，并将D中实例树最⼤的类作为该结点的类标记，返回T5）否则，对Ag的每⼀可能取值ai, 依Ag=ai将D分割为若⼲⾮空⼦集Di，将Di中实例树最⼤的类作为标记，构建⼦结点，由结点及其⼦结点构成树T, 返回T

6）对第i个⼦结点，以Di为训练集，以A-{Ag}为特征集，递归地调⽤（1）~（5）步，如果⼦结点的深度等于n或者⼦结点的样本数量⼩于m，则将该⼦结点作为叶⼦结点，停⽌递归调⽤，得到⼦树Ti,返回Ti

2.1.3 决策树的剪枝

决策树的⽣成是采⽤启发式算法（类似贪婪算法），每⼀步做出最优选择，实现的是局部最优，结果就是容易过拟合，因为模型记住了很多训练数据集特有的细节，这些细节会降低模型泛化的能⼒

决策树的剪枝采⽤的是最优化算法，明确整棵决策树（全局）的损失函数或代价函数（损失函数+结构风险正则化）进⾏迭代优化 代价函数如下：

其中t代表某个叶⼦结点，Nt表⽰该叶⼦结点对应的样本数量，Ht表⽰该结点的经验熵（信息熵）,|T|表⽰模型的复杂度，α控制正则化的强度

这⾥的Nt可以理解为权重，毕竟如果两个叶⼦结点的经验熵相同，包含⼦结点数量更多的那个结点对总体混乱程度的贡献更⼤。

输⼊：⽣成算法产⽣的决策树T,正则化参数α

输出：修剪后的⼦树Tα1）计算每个结点的经验熵

2）递归地从树的叶节点向上回缩

3）如果回缩后的损失函数⼩于等于回缩前的，则进⾏剪枝

4）返回第⼆步调⽤，知道不能继续为⽌，得到剪枝后的决策树

2.2 C4.5决策树

C4.5树是基于ID3树的改进，具体表现为两点

1）特征选择不仅使⽤信息增益，⽽且还考虑信息增益率，具体原因请看⽂章开头关于信息增益和信息增益率的介绍（很多资料单纯地说⽤信息增益率替代了信息增益，这是不准确的）2）增加了对连续变量（特征）的⽀持（这⼀点很多资料没有讲，尤其是没有讲如何处理连续变量）

下⾯我们就讲⼀下C4.5决策树对特征的处理。

1）对于离散特征（分类或者顺序特征），该决策树采⽤N叉树的⽅式，对于每⼀个特征取值分出⼀个⼦结点，和ID3处理⽅式相同

2）对于连续型特征，采⽤⼆分法，

1、⾸先将样本按照该特征⼤⼩进⾏排序

2、每两个相邻特征值取平均值，将该平均值作为分裂点进⾏样本划分

3、计算每种划分所对应的信息增益，选取信息增益最⼤的分裂点作为最终⼆分的分裂点

4、计算所有特征的信息增益率和信息增益，先选取信息增益⾼于平均值的特征，再选取信息增益率最⼤的特征作为当前划分依据3）划分后的样本不再保留其原有值，⽽⽤布尔值代替。

这⾥有两个问题需要解释：

Q1:为什么连续特征的最佳分裂点选取使⽤信息增益⽽⾮信息增益率？

因为同⼀个特征下，最终的结果确定是⼆分，这种相对的⽐较，也就不存在信息增益⾃⾝的缺陷（倾向于选择情况更多的特征，现在情况只有两种）Q2:为什么最佳特征的选择先考虑信息增益再考虑信息增益率？

⾸先，信息增益倾向于选择可取值数量较多的变量，信息增益率倾向于选择可取值数较少的变量（有点⼉矫枉过正），所以采⽤启发式算法，先选取信息增益⾼于平均值的特征，再选取信息增益率最⼤的特征作为当前划分依据 2.3 CART树（分类树）

2.3.1 特征选择使⽤最⼩化基尼指数，具体来讲，1）对所有特征的所有可能切分点进⾏基尼指数计算

2）选择基尼指数最⼩的特征+切分点组合

2.3.2 决策树的⽣成

输⼊：训练数据集D,停⽌计算的条件（预剪枝条件，参考ID3决策树）

输出：CART决策树

根据训练数据集，从根节点开始，递归地对每个结点进⾏以下操作：1）设结点的训练数据集为D,计算现有特征对该数据集的基尼指数。此时，对每⼀个特征A,对其可能取的每个值a（对于⼤量连续变量计算代价过⾼，可以选择

分类发⽣变化的点）,根据样本点对A=a的测试为‘是’或‘否’，将D分割成D1和D2两部分，根据

计算A=a时的基尼指数。

2）在所有可能的特征A以及他们所有可能的切分点a中，选择基尼指数最⼩的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点⽣成两个⼦结点，将训练数据集依特征分配到两个⼦结点中去。3）对两个⼦结点递归地调⽤（1）（2），直⾄满⾜停⽌条件

4）⽣成决策树

2.3.3 决策树的剪枝

CART的剪枝这⾥不详细讲解了，总体⽽⾔就两个过程

1）根据⽣成的完整决策树，计算每个内部结点对应的损失函数增加量，然后砍去损失函数增加最多的结点，⽣成新树

2）对新树递归调⽤第⼀步，⽣成更多的新树，构成树集合

3）通过验证集选择最佳的决策树上图

注意第六步中应该返回步骤3，这是⼀个错误。该图⽚摘⾃李航的《统计学习⽅法》 2.4 CART树（回归树）

2.4.1 特征选择根据平⽅误差最⼩化准则1）对每个特征进⾏排序，依次选择不同的切分点对样本进⾏切分

2）计算切分后⼦结点中样本的值与与样本均值的平⽅误差和，选择平⽅误差和最⼩的切分点和左右⼦结点平⽅误差和最⼩的特征

3）对⼦结点递归进⾏1、2步

2.4.2 决策树⽣成

2.4.3 决策树的剪枝

和CART(分类树)的剪枝⼏乎相同，不同点在于损失函数由基尼指数变为了最⼩⼆乘。 3、补充

1、关于决策树的具体输出结果问题A:拿sklearn关于决策树的API来讲，对于分类树，既可以⽤predict()⽅法直接获得分类的结果，也可以⽤predict_prob()获得样本属于某个类别的概率2、关于整个预测流程是怎样的？A：⾸先通过训练数据集训练出了决策树，包括决策树的结构和结点，且根据训练样本分配到每个叶⼦结点的数量计算出了每个叶⼦结点对应的所属类别的概率（好多资料只提到了叶⼦结点对应了该节点所属类别最多的样本对应的类别）。然后待预测样本只需要根据所训练出的决策树⾛到决策树的某个叶⼦结点，输出该结点早就计算好的分类类别或者某个类别的概率即可（回归树则输出该结点对应训练样本的平均值）。3、关于特征值复⽤的问题

周志华的《机器学习》⼀书中讲到连续特征可以复⽤，但没有对此作出解释，我的推测为，因为连续特征的可选择切分点会有n个（⼤于1）情况，所以⼀个连续特征被使⽤⼀次之后（选择了某个切分点），他所包含的信息并没有被完全利⽤，仍有潜在的价值（其他切分点的信息可能对接下来的训练你有所贡献），据此，我也推测CART不仅对连续特征可以复⽤，针对离散特征（可能的切分情况⼤于1时），特征也可以复⽤。4、关于样本缺失值处理的问题

具体来讲是两个⼦问题4.1：对于某个特征a,如何选择a的切分点？

A：计算时只考虑a不为空的样本

4.2：在特征a处，如果某个样本的特征a为空，如何对样本进⾏划分？

A：将样本同时划⼊所有⼦结点，但要包含权重，权重值为所划⼊结点的样本所占⽗结点样本的⽐例*样本的权重（⼀般情况下所有样本的权重初始化相等）

Finished!

感觉还是没有做到通俗易懂啊。。。little sad

参考资料：