1. 前言
决策树是一种
基本的分类和回归方法
。决策树呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间和类空间上的条件概率分布。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。决策树学习通常包括三个步骤：
特征选择、决策树的生成和决策树的剪枝
。决策树算法的发展从ID3到C4.5再到CART，下面会分别介绍。
2. 特征选择
特征选择在于选取对训练数据具有分类能力的特征。特征选择的基本方法有三种，
（ID3的信息增益、C4.5的信息增益比、CART的基尼系数）
特征
\(A\)
对训练数据集
\(D\)
的信息增益
\(g(D,A)\)
，定义为集合
\(D\)
的经验熵
\(H(D)\)
与特征
\(A\)
给定条件下D的经验条件熵
\(H(D|A)\)
之差，即
\[g(D,A)=H(D)-H(D|A)
\]
2.2 信息增益比
ID3采用信息增益的方式很快就被人发现有问题，在相同条件下，取值比较多的特征比取值少的特征信息增益大，即
信息增益作为标准容易偏向于取值较多的特征
。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。
所以在C4.5中，引入了信息增益比
\(I_R(X,Y)\)
，它是信息增益和特征熵的比值。表达式如下：
\[I_R(D,A)=\frac{I(A,D)}{H_A(D)}
\]
其中
\(D\)
为样本特征输出的集合，
\(A\)
为样本特征，对于特征熵
\(H_A(D)\)
, 表达式如下：
\[H_A(D) = -\sum\limits_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}
\]
其中
\(n\)
为特征
\(A\)
的类别数，
\(D_i\)
为特征
\(A\)
的第
\(i\)
个取值对应的样本个数。
\(D\)
为样本个数。
2.3 基尼系数
在ID3算法中我们使用了
信息增益
来选择特征，信息增益大的优先选择。在C4.5算法中，采用了
信息增益比
来选择特征，以减少信息增益容易选择特征值多的特征的问题。但是无论是ID3还是C4.5,都是基于
信息论的熵模型
的，这里面会涉及大量的对数运算，比较耗时。CART分类树算法使用
基尼系数
来代替信息增益比，
基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的
。
具体的，在分类问题中，假设有
\(K\)
个类别，第
\(k\)
个类别的概率为
\(p_k\)
, 则基尼系数的表达式为：
\[Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k) = 1- \sum\limits_{k=1}^{K}p_k^2
\]
3. 决策树的生成
3.1 ID3算法
ID3算法的核心是再决策树各个节点上应用信息增益选择特征，递归的构建决策树。
输入：训练集
\(D\)
，特征集
\(A\)
，阈值
\(\varepsilon\)
输出：决策树
\(T\)
初始化信息增益的阈值
\(\varepsilon\)
判断样本是否为同一类输出
\(D_i\)
，如果是则返回单节点树
\(T\)
。标记类别为
\(D_i\)
。
判断特征是否为空，如果是则返回单节点树
\(T\)
，标记类别为样本中输出类别
\(D\)
实例数最多的类别。
计算
\(A\)
中的各个特征（一共n个）对输出
\(D\)
的信息增益，选择信息增益最大的特征
\(A_g\)
。
如果
\(A_g\)
的信息增益小于阈值
\(\varepsilon\)
，则返回单节点树
\(T\)
，标记类别为样本中输出类别
\(D\)
实例数最多的类别。
否则，按特征
\(A_g\)
的不同取值
\(A_{gi}\)
将对应的样本输出D分成不同的类别
\(D_i\)
。每个类别产生一个子节点。对应特征值为
\(A_{gi}\)
。返回增加了节点的数
\(T\)
。
对于所有的子节点，令
\(D=D_i,A=A-{A_g}\)
递归调用2-6步，得到子树
\(T_i\)
并返回。
3.2 C4.5算法
C4.5算法整体结构和ID3基本一样，只有在特征选择的时候换成了
信息增益比
。
3.3 CART算法
输入是训练集
\(D\)
，基尼系数的阈值
\(\varepsilon_1\)
，样本个数阈值
\(\varepsilon_2\)
。
输出是决策树
\(T\)
。
我们的算法从根节点开始，用训练集递归的建立CART树。
对于当前节点的数据集为
\(D\)
，如果样本个数小于阈值
\(\varepsilon_2\)
或者没有特征，则返回决策子树，当前节点停止递归。
计算样本集
\(D\)
的基尼系数，如果基尼系数小于阈值
\(\varepsilon_1\)
，则返回决策树子树，当前节点停止递归。
计算当前节点现有的各个特征的各个特征值对数据集
\(D\)
的基尼系数。
在计算出来的各个特征的各个特征值对数据集
\(D\)
的基尼系数中，选择基尼系数最小的特征
\(A\)
和对应的特征值
\(a\)
。根据这个最优特征和最优特征值，把数据集划分成两部分
\(D1\)
和
\(D2\)
，同时建立当前节点的左右节点，做节点的数据集
\(D\)
为
\(D1\)
，右节点的数据集
\(D\)
为
\(D2\)
。
对左右的子节点递归的调用1-4步，生成决策树。
4. 决策树的剪枝
决策树生成算法递归地产生决策树，直到不能继续下去为止。
这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没那么准确，即出现过拟合现象
。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。
可以通过剪枝的方式降低决策树的复杂度，剪枝类型分为预剪枝、后剪枝。
预剪枝
：是在构建决策树的过程中，提前终止决策树的生长，从而避免过多的节点产生。预剪枝方法虽然简单但实用性不强，因为很难精确的判断何时终止树的生长。
后剪枝
：是在决策树构建完成之后，对那些置信度不达标的节点子树用叶子结点代替，该叶子结点的类标号用该节点子树中频率最高的类标记。后剪枝方法又分为两种:
把训练数据集分成树的生长集和剪枝集（参考周志华老师的西瓜书上介绍的剪枝方法）。
使用同一数据集进行决策树生长和剪枝。常见的后剪枝方法有CCP(Cost Complexity Pruning)、REP(Reduced Error Pruning)、PEP(Pessimistic Error Pruning)、MEP(Minimum Error Pruning)。
C4.5算法采用PEP
(Pessimistic Error Pruning)剪枝法。PEP剪枝法由Quinlan提出，是一种自上而下的剪枝法，根据剪枝前后的错误率来判定是否进行子树的修剪。
CART采用的是CCP
(Cost Complexity Pruning)的剪枝法策略。
本文介绍CART决策树的后剪枝算法CCP(Cost Complexity Pruning)。
4.1 CART的CCP剪枝算法
总体思路
：由完全树
\(T_0\)
开始，剪枝部分结点得到
\(T_1\)
，再次剪枝部分结点得到
\(T_2\)
...直到剩下树根的树
\(T_k\)
；在验证数据集上对这
\(k\)
个树分别评价，选择损失函数最小的树
\(T_a\)
。
变量预定义
：
\(|T_{leaf}|\)
表示树
\(T\)
的叶结点个数，
\(t\)
表示树
\(T\)
的叶结点，同时，
\(N_t\)
表示该叶结点含有的样本点个数，其中属于
\(k\)
类的样本点有
\(N_{tk}\)
个，
\(K\)
表示类别的个数，
\(H_t(T)\)
为叶结点
\(t\)
上的经验熵，
\(\alpha≥0\)
为参数。
一个节点的样本数，是这个样本所有类的数量的和，公式如下：
\[N_t=\displaystyle\sum^{K}_{k=1}{N_{tk}}
经验熵
：
\[H_t(T)=-\displaystyle \sum_k^K \frac {N_{tk}} {N_t} \log \frac {N_{tk}}{N_t}
\]
经验熵反映了一个叶结点中的分类结果的混乱程度。经验熵越大，说明该叶结点所对应的分类结果越混乱，也就是说分类结果中包含了较多的类别，表明该分支的分类效果较差。
损失函数
：
\[C(T)=\sum^{|T_{leaf}|}_{t=1} {N_tH_t(T)}
\]
损失函数其实是求叶结点的经验熵期望。用
\(N_t\)
给经验熵加权的依据是叶子节点含有的样本个数越多，其分类效果或混乱程度越占主导，相当于求了期望，可以更好的描述分支前后的关系。例如设一个结点
\(r\)
有
\(n\)
个样本，其组成是第
\(i\)
类有
\(n_i\)
个样本，在分了几个孩子结点后各个叶结点的成分仍保持原比例，记新的子树为
\(R\)
，可以计算得出评价函数
\(C(r)=C(R)\)
，即在随机分组后不会有任何分类效果的改进。损失函数越小越好。熵的期望和熵一样，越小越好。所以，损失函数越大，说明模型的分类效果越差。
损失函数的正则化
：
\[C_\alpha(T)=\sum^{|T_{leaf}|}_{t=1} {N_tH_t(T)+\alpha|T_{leaf}|}
\]
修正项
\(\alpha|T_{leaf}|\)
是基于复杂度的考虑。如上面提到的情况，
\(r\)
与
\(R\)
其实是一样的，没有进行任何分类的处理，但是我们仍然觉得
\(r\)
更好，原因在于
\(R\)
的复杂度更高。加了此修正项后具有现实的意义：如果
\(\alpha=0\)
表示未剪枝的完全树损失更小（熵更小的占主导地位），如果
\(\alpha->\infty\)
表示剪枝到只剩根结点更好（叶结点个数占主导地位）。修正项
\(\alpha|T_{leaf}|\)
可以避免过拟合。修正项
\(\alpha|T_{leaf}|\)
考虑到了复杂度，
\(\alpha\)
值设置得好可以避免出现完全树和根结点这类的极端情况，因此可以避免过拟合。
损失函数简化形式
：
\[C_{\alpha}(T)=C(T)+\alpha|T_{leaf}|
计算剪枝系数
\(\alpha\)
：
假定当前对以
\(t\)
为根的子树
\(T_t\)
剪枝，剪枝后只保留
\(t\)
本身而删掉所有的子结点。
剪枝后的损失函数：
\(C_\alpha(t)=C(t)+\alpha\)
剪枝前的损失函数：
\(C_\alpha(T_t)=C(T_t)+\alpha|T_{leaf}|\)
(
\(C(T_t)\)
应该是小于
\(C(t)\)
)
令二者相等，求得：
\(\alpha=\frac{C(t)-C(T)}{|T_{leaf}|-1}\)
，因为损失相同，那就取复杂度小的，所以就可以剪枝。
\(\alpha\)
称为结点
\(t\)
的剪枝系数。
剪枝算法流程
：
对于给定的决策树
\(T_0\)
。
计算所有内部结点的剪枝系数。
查找最小剪枝系数的结点，剪枝得决策树
\(T_k\)
。
重复以上步骤，直到决策树
\(T_k\)
只有一个结点。
得到决策树序列
\(T_0,T_1,T_2...T_k\)
。
使用验证样本集选择最优子树。
5. 总结
本文从：
特征选择、决策树的生成和决策树的剪枝
三个方面介绍了决策树的原理。并且也介绍了三种决策树的算法ID3、C4.5、CART。下文将比较ID3、C4.5、CART的异同点。
最后对决策树这个一类算法做总结：
首先我们看看决策树算法的优点：
简单直观，生成的决策树很直观。
基本不需要预处理，不需要提前归一化，处理缺失值。
使用决策树预测的代价是O(log2m)。 m为样本数。
既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
可以处理多维度输出的分类问题。
相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释
可以交叉验证的剪枝来选择模型，从而提高泛化能力。
对于异常点的容错能力好，健壮性高。
我们再看看决策树算法的缺点:
决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。
