决策树——（二）决策树的生成与剪枝ID3,C4.5

1.基本概念

在正式介绍决策树的生成算法前，我们先将之前的几个概念梳理一下：

1.1 信息熵

设X是一个取有限个值的离散型随机变量，其分布概率为

则随机变量X的熵定义为

其中，若pi=0，则定义0log0=0；且通常log取2为底和e为底时，其熵的单位分别称为比特(bit)或纳特(nat).如无特殊说明，默认2为底。

1.2 条件熵

设有随机变量(X,Y)，其联合概率分布分

条件熵H(Y|X)表示在已知随机变量X的条件下，随机变量Y的不确定性。其定义为

其中，pi=P(X=xi),i=1,2,...,n
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称之为经验熵(empirical entropy)和经验条件熵(empirical coditional entropy)。事实上我们在实际处理的时候确实时用的经验熵和经验条件熵，这一点同朴素贝叶斯中的处理一样。

1.3 信息增益

特征A对训练数据集D的信息增益d(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即

设训练集为D，|D|表示其样本容量，即样本个数。设有K个类Ck,k=1,2,...,K;|Ck|为属于类Ck的样本的个数，即∑Kk=1|Ck|=|D|.设特征A有n个不同的取值a1,a2,...,an，根据特征A的取值将D划分为n个子集D1,D2,...,Dn,|Di|为Di的样本个数，即∑ni=1|Di|=|D|.记子集Di中，属于类Ck的样本集合为Dik，即Dik=Di⋂Ck，|Dik|为Dik的样本个数. 则有：
（1）数据集D的经验熵H(D)为

（2）特征值A对数据集D的经验条件熵H(D|A)为

（3）信息增益

仅看上面的公式肯定会很模糊，还是举个例子来说明一下(将公式同下面的计算式子对比着看会更容易理解).下表是一个由15个样本组成的贷款申请训练数据集。数据包括4个特征，最后一列表示是否通过申请。

(1)计算H(D)

(2)计算条件熵
由上表我们可以知道，数据集有4个特征A1,A2,A3,A4；则接下来我们就计算D分别在4个特征条件下的熵H(D|Ai)

这里的D1,D2,D3分别是A1取值为青年，中年，老年的样本子集

---

这里的D1,D2分别是A2取值为是，否的样本子集

---

这里的D1,D2分别是A3取值为是，否的样本子集

---

这里的D1,D2,D3分别是A4取值为一般，好，非常好的样本子集

（3）计算信息增益

2.决策树的生成

决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树（即能对训练数据进行正确分类的决策树）可能有多个，也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。

决策树学习的算法（生成决策树）通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这样一来，对于每一次递归选择特征时就显得格外重要。

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。那么此时通常特征选择的准则就是我们前面谈到的信息增益。

2.1 ID3算法

ID3(Interactive Dichotomizer-3)算法的核心时在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有可以选择为止。

步骤如下：
输入：训练数据集D，特征集A，阈值ε;
输出：决策树

（1）若D中所有实例属于同一类Ck，则T为单结点树，并将Ck作为该结点的类标记，返回T;
（2）若A=∅，则T为单结点树，并将D中实例数最大的类Ck作为该 几点的类标记，返回T；
（3）否则，计算A中各特征对D的信息增益，选择信息增益最大的特征Ag；
（4）如果Ag的信息增益小于阈值ε，则置T为单结点树，并将D中实例数最大的类Ck最为该结点的类标记，返回T；
（5）否者，对Ag的每一个可能值ai，依Ag=ai将D分割为若干非空子集建立为子结点；
（6）对于第i个子结点，以Di为训练集，以A−{Ag}为特征集，递归地调用(1)-(5)，得到子树Ti，返回Ti

下面用ID3算法对上表中的数据集进行学习

易知该数据集不满足步骤(1)(2)，所有执行步骤(3)。
在1.3的最后，我们算出对于特征A1,A2,A3,A4来说，在A3的条件下，信息增益最大，所以选择特征A3作为根节点

本例中未设置阈值，所以执行步骤（5）
将训练集D划分为两个子集D1,D2，如下表

开始执行步骤(6)，由于D1满足步骤(1)中的条件，所以它成为一个叶结点，结点的类标记为“是”。则此时的决策树如下：

易知D2不满足步骤(1)(2)中的条件，所有对D2执行步骤(3)，此时D2需要从特征A−{Ag}即A1,A2,A4中选择新的特征，并计算信息增益：

计算后发现信息增益最大的特征是A2，所以执行步骤(5)，将D2划分为两个子集D21,D22，如下表

由划分后的结果可知，D21,D22均满足步骤(1)中的条件，所以它成为叶结点，结点的类标记分别为“是”和“否”，到此递归结束；最终的决策树如下：

如上就是整个决策树的生成过程，但同时我们也可以清楚的看到，ID3算法极易导致过拟合。原因就在于，如果单纯以g(D,A)作为标准的话，会存在偏向于选择取值较多的特征（比如上面的A1,A4）虽然这个例子不存在。但是我们仍可以从直观上理解为什么会偏向于选取特征值取值较多的特征。

由于g(D,A)的直观意义是D被A划分后不确定性的减少量，可想而知，当A的取值很多时，D会被划分成很多分，于是其不确定性自然会减少很多，从而ID3算法会倾向于选择取值较多的特征作为划分依据。但如果这样的话可以想象，我们最终得到的决策树将会是一颗很胖很矮的树，从而导致过拟合。

2.2 C4.5算法

为了解决ID3算法的弊端，从而产生了C4.5算法。C4.5算法与ID3算法相似，不同之处仅在于C4.5算法在选择特征的时候采用了信息增益比作为标准。信息增益比定义如下：

特征A对训练即D的信息增益比gR(D,A)定义为其信息增益g(D,A)与其训练集D关于特征A的值的熵HA(D)之比，即

其中，HA(D)=−∑i=1n|Di||D|log2|Di||D|，n是特征A取值的个数。

如前面例子中，对于选取根节点时，其增益比计算如下：

所以有：

训练步骤如下：
输入：训练数据集D，特征集A，阈值ε;
输出：决策树

（1）若D中所有实例属于同一类Ck，则T为单结点树，并将Ck作为该结点的类标记，返回T;
（2）若A=∅，则T为单结点树，并将D中实例数最大的类Ck作为该 几点的类标记，返回T；
（3）否则，计算A中各特征对D的信息增益比，选择信息增益比最大的特征Ag；
（4）如果Ag的信息增益比小于阈值ε，则置T为单结点树，并将D中实例数最大的类Ck最为该结点的类标记，返回T；
（5）否者，对Ag的每一个可能值ai，依Ag=ai将D分割为若干非空子集建立为子结点；
（6）对于第i个子结点，以Di为训练集，以A−{Ag}为特征集，递归地调用(1)-(5)，得到子树Ti，返回Ti

3. 决策树的剪枝

决策树生成算法递归地产生决策树，知道不能继续下去为止。这样产生的树往往对训练集的分类很准确，但对于未知的测试数据的分类却没那么准确，即出现了过拟合现象。过拟合的原因在于学习的时候过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法就是考虑决策树的复杂度，对已经生成的决策树进行简化，也就是剪枝。

决策树的剪枝往是通过极小化决策树整体的损失函数或者代价函数来实现。设树T的叶结点个数为T，t是树T的叶结点，该叶结点有Nt个样本点，其中k类的样本点有Ntk个，k=1,2,...,K,Ht(T)为叶结点t上的经验熵，α≥0为参数，则决策树的损失函数可以定义为

C(T)表示模型对训练数据的预测误差，即模型与训练集的拟合程度，|T|表示模型复杂度，参数α≥0控制两者之间的影响。较大的α促使选择较简单的模型（树），较小的α促使选择较复杂的模型（树）。α=0意味着只考虑模型与训练集的拟合程度，不考虑模型的复杂度。

剪枝步骤：
输入：生成算法产生的整个树T，参数α；
输出：修剪后的子树Tα
（1）计算每个叶结点的经验熵；
（2）递归地从树的叶结点往上回缩
设一组叶结点回缩到其父结点之前与之后的整体树分别为TB,TA，其对应的损失函数值分别是Cα(TB),Cα(TA)，如果

则进行剪枝，即将父结点变为新的叶结点。
（3）返回（2），直到不能继续为止，得到损失函数最小的子树Tα

之所以用这么一个判别式是因为：按常理来说，应该是剪枝后的损失值大于剪枝前的损失值；但如果剪枝后的损失值比不剪枝的损失值还有小，那这减去的部分就真是多余的了，有了这部分非但没能使得损失降低，反而增大了，所以得减掉。

举例：
下面我们根据之前建立好的决策树来进行剪枝计算

如上图所示，考虑是否要减掉“有工作”这个结点，首先需要计算的就是剪枝前的损失函数数值。由于剪枝时，每次只考虑一个结点，所以在计算剪枝前和剪枝后的损失函数值时，仅考虑该结点即可。因为其他叶结点的经验熵对于剪枝前和剪枝后都没有变化。

易知“有工作”这个结点的训练数据如下

则

由此可以，当设定的α≥8时，就会剪枝。

参考：

• 统计学习方法
• Python与机器学习实战