决策树

作者: 胜利主义章北海 | 来源:发表于2019-07-03 18:00 被阅读0次

1.前言

决策树是一种基本的分类和回归方法。决策树呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。采用的是自顶而下的递归方法，从根节点开始一步步走到叶子节点，所有的数据最终都会落在叶子节点。它可以认为是if-then规则的集合，也可以认为是定义在特征空间和类空间上的条件概率分布。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。决策树学习通常包括三个步骤：特征选择、决策树的生成和决策树的剪枝。决策树算法的发展从ID3到C4.5再到CART。

1.1 树的组成

根节点：第一个选择点
非叶子节点与分支：中间过程
叶子节点：最终的决策结果

1.2 决策树的训练与测试

训练阶段：从给定的训练集构造出来一棵树（从跟节点开始选择特征，如何进行特征切分）
测试阶段：根据构造出来的树模型从上到下去走一遍就好了
一旦构造好了决策树，那么分类或者预测任务就很简单了，只需要走一遍就可以了，那么难点就在于如何构造出来一颗树，这就没那么容易了，需要考虑的问题还有很多的

2. 特征选择

问题：根节点的选择该用哪个特征呢？接下来呢？如何切分呢？
想象一下：我们的目标应该是根节点就像一个老大似的能更好的切分数据（分类的效果更好），根节点下面的节点自然就是二当家了。
目标：通过一种衡量标准，来计算通过不同特征进行分支选择后的分类情况，找出来最好的那个当成根节点，以此类推。

特征选择在于选取对训练数据具有分类能力的特征。特征选择的基本方法有三种：ID3的信息增益、C4.5的信息增益比、CART的基尼系数。

2.1 信息增益

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

$g(D,A)=H(D)−H(D|A)$

2.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)=-\displaystyle \sum^{n}_{i=1} {\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|}}$

其中 $n$ 为特征 $A$ 的类别数， $D_i$ 为特征 $A$ 的第 $i$ 个取值对应的样本个数。 $D$ 为样本个数。

2.3 基尼系数

CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。
具体的，在分类问题中，假设有 $K$ 个类别，第 $k$ 个类别的概率为 $p_k$ , 则基尼系数的表达式为：

$Gini(p)=\displaystyle\sum^{K}_{k=1}{p_k(1−p_k)} = 1-\displaystyle\sum^{K}_{k=1}{p_k}^2$

3.决策树的生成

3.1 ID3算法

ID3算法的核心是再决策树各个节点上应用信息增益选择特征，递归的构建决策树。
输入：训练集 $D$ ，特征集 $A$ ，阈值 $ε$
输出：决策树 $T$

初始化信息增益的阈值 $ε$
判断样本是否为同一类输出 $D_i$ ，如果是则返回单节点树 $T$ 。标记类别为 $D_i$ 。
判断特征是否为空，如果是则返回单节点树&T&，标记类别为样本中输出类别 $D$ 实例数最多的类别。
计算 $A$ 中的各个特征（一共n个）对输出 $D$ 的信息增益，选择信息增益最大的特征 $A_g$ 。
如果 $A_g$ 的信息增益小于阈值 $ε$ ，则返回单节点树 $T$ ，标记类别为样本中输出类别 $D$ 实例数最多的类别。
否则，按特征 $A_g$ 的不同取值 $A_{gi}$ 将对应的样本输出 $D$ 分成不同的类别 $D_i$ 。每个类别产生一个子节点。对应特征值为 $A_{gi}$ 。返回增加了节点的数 $T$ 。
对于所有的子节点，令 $D=Di,A=A−A_g$ 递归调用2-6步，得到子树 $T_i$ 并返回。

3.2 C4.5算法

C4.5算法整体结构和ID3基本一样，只有在特征选择的时候换成了信息增益比。

3.3 CART算法

输入是训练集 $D$ ，基尼系数的阈值 $ε_1$ ，样本个数阈值 $ε_2$ 。
输出是决策树 $T$ 。
我们的算法从根节点开始，用训练集递归的建立CART树。

对于当前节点的数据集为 $D$ ，如果样本个数小于阈值 $ε_2$ 或者没有特征，则返回决策子树，当前节点停止递归。
计算样本集 $D$ 的基尼系数，如果基尼系数小于阈值 $ε_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$ 上的经验熵， $α≥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)=\displaystyle\sum^{|T_{leaf}|}_{t=1}N_tH_t(T)$

损失函数其实是求叶结点的经验熵期望。用 $N_t$ 给经验熵加权的依据是叶子节点含有的样本个数越多，其分类效果或混乱程度越占主导，相当于求了期望，可以更好的描述分支前后的关系。例如设一个结点 $r$ 有 $n$ 个样本，其组成是第 $i$ 类有 $n_i$ 个样本，在分了几个孩子结点后各个叶结点的成分仍保持原比例，记新的子树为 $R$ ，可以计算得出评价函数 $C(r)=C(R)$ ，即在随机分组后不会有任何分类效果的改进。损失函数越小越好。熵的期望和熵一样，越小越好。所以，损失函数越大，说明模型的分类效果越差。

损失函数的正则化:

$C_α(T)=\displaystyle\sum^{|T_{leaf}|}_{t=1}N_tH_t(T)+\alpha|T_{leaf}|$

修正项 $α|T_{leaf}|$ 是基于复杂度的考虑。如上面提到的情况， $r$ 与 $R$ 其实是一样的，没有进行任何分类的处理，但是我们仍然觉得 $r$ 更好，原因在于 $R$ 的复杂度更高。加了此修正项后具有现实的意义：如果 $α=0$ 表示未剪枝的完全树损失更小（熵更小的占主导地位），如果 $\alpha\to \infty$ 表示剪枝到只剩根结点更好（叶结点个数占主导地位）。修正项 $α|T_{leaf}|$ 可以避免过拟合。修正项 $α|T_{leaf}|$ 考虑到了复杂度， $α$ 值设置得好可以避免出现完全树和根结点这类的极端情况，因此可以避免过拟合。

损失函数简化形式：

$C_α(T)=C(T)+α|T_{leaf}|$

计算剪枝系数 $α$ :

假定当前对以 $t$ 为根的子树 $T_t$ 剪枝，剪枝后只保留 $t$ 本身而删掉所有的子结点。
剪枝后的损失函数： $C_α(t)=C(t)+α$

剪枝前的损失函数： $C_α(T_t)=C(T_t)+α|T_{leaf}|$ ( $C(T_t)$ 应该是小于 $C(t)$ )

令二者相等，求得： $α=\frac{C(t)−C(T)}{|T_{leaf}|−1}，$ 因为损失相同，那就取复杂度小的，所以就可以剪枝。 $α$ 称为结点 $t$ 的剪枝系数。

剪枝算法流程：

对于给定的决策树 $T_0$ 。
计算所有内部结点的剪枝系数。
查找最小剪枝系数的结点，剪枝得决策树 $T_k$ 。
重复以上步骤，直到决策树 $T_k$ 只有一个结点。
得到决策树序列 $T_0,T_1,T_2...T_k$ 。
使用验证样本集选择最优子树。

5. ID3、C4.5、CART比较

5.1 ID3算法

5.1.1 ID3原理

ID3算法就是用信息增益大小来判断当前节点应该用什么特征来构建决策树，用计算出的信息增益最大的特征来建立决策树的当前节点。算法具体过程看上文。

5.1.2 ID3的不足

ID3算法虽然提出了新思路，但是还是有很多值得改进的地方。

ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。如果校正这个问题呢？
ID3算法对于缺失值的情况没有做考虑
没有考虑过拟合的问题
ID3 算法的作者昆兰基于上述不足，对ID3算法做了改进，这就是C4.5算法，也许你会问，为什么不叫ID4，ID5之类的名字呢?那是因为决策树太火爆，他的ID3一出来，别人二次创新，很快就占了ID4，ID5，所以他另辟蹊径，取名C4.0算法，后来的进化版为C4.5算法。

5.2 C4.5算法

5.2.1 C4.5对ID3的改进

C4.5改进了上面ID3的4个问题：

对于ID3不能处理连续特征，C4.5的思路是将连续的特征离散化。比如 $m$ 个样本的连续特征 $A$ 有 $m$ 个，从小到大排列为 $a_1,a_2,...,a_m$ , 则C4.5取相邻两样本值的平均数，一共取得 $m−1$ 个划分点，其中第 $i$ 个划分点 $T_i$ 表示为： $Ti=\frac{a_i+a_i+1}{2}$ 。对于这 $m−1$ 个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为 $a_t$ , 则小于 $a_t$ 的值为类别1，大于 $a_t$ 的值为类别2，这样我们就做到了连续特征的离散化。要注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。
对于ID3的第2个问题，信息增益作为标准容易偏向于取值较多的特征的问题。我们引入一个信息增益比的变量 $I_R(X,Y)$ ，它是信息增益和特征熵的比值。

$I_R(D,A)=\frac{I(A,D)}{H_A(D)}$
对于ID3的第3个缺失值处理的问题，主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。
1. 对于第一个子问题，对于某一个有缺失特征值的特征 $A$ 。C4.5的思路是将数据分成两部分，对每个样本设置一个权重（初始可以都为1），然后划分数据，一部分是有特征值 $A$ 的数据 $D_1$ ，另一部分是没有特征 $A$ 的数据 $D_2$ 。然后对于没有缺失特征 $A$ 的数据集 $D_1$ 来和对应的 $A$ 特征的各个特征值一起计算加权重后的信息增益比，最后乘上一个系数，这个系数是无特征 $A$ 缺失的样本加权后所占加权总样本的比例。
2. 对于第二个子问题，可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征 $A$ 的样本 $a$ 之前权重1，特征 $A$ 有3个特征值 $A_1,A_2,A_3$ 。3个特征值对应的无缺失 $A$ 特征的样本个数为2,3,4。a同时划分入 $A_1,A_2,A_3$ 。对应权重调节为2/9, 3/9, 4/9。
对于ID3的第4个问题，C4.5引入了正则化系数进行剪枝。

5.2.2 C4.5的不足

C4.5虽然改进或者改善了ID3算法的几个主要的问题，仍然有优化的空间。

由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。C4.5的剪枝方法是PEP。PEP的准确度比较高，但是依旧会存在以下的问题：
1. PEP算法实用的从从上而下的剪枝策略，这种剪枝会导致和预剪枝同样的问题，造成剪枝过度。
2.PEP剪枝会出现剪枝失败的情况。
C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。

5.3 CART算法

5.3.1 CART对C4.5的改进

CART算法在C4.5的基础上，对于C4.5中的出现的问题进行了改进。针对上面提到的C4.5中出现的4点问题，进行如下改进：

CART使用了CCP代价复杂度剪枝算法，对C4.5的剪枝方法进行了优化。
针对C4.5的多叉树的问题，CART改成了二叉树。CART采用的是不停的二分，举个例子，CART分类树会考虑把 $A$ 分成{ $A_1$ }和{ $A_2,A_3$ },{ $A_2$ }和{ $A_1,A_3$ },{ $A_3$ }和{ $A_1,A_2$ }三种情况，找到基尼系数最小的组合，比如{ $A_2$ }和{ $A_1,A_3$ }, 然后建立二叉树节点，一个节点是{ $A_2$ }对应的样本，另一个节点是{ $A_1,A_3$ }对应的节点。同时，由于这次没有把特征 $A$ 的取值完全分开，后面我们还有机会在子节点继续选择到特征 $A$ 来划分{ $A_1$ }和{ $A_3$ }。这和ID3或者C4.5不同，在ID3或者C4.5的一棵子树中，离散特征只会参与一次节点的建立，而CART中的离散特征会参与多次节点建立。
CART可以分为CART分类树和CART回归树。CART分类树和CART回归树的算法大致相同，主要区别有下面两点：
1. 连续值的处理方法不同。
  1. CART分类树采用的是用基尼系数的大小来度量特征的各个划分点的优劣情况
  2. CART回归树的度量目标是，对于任意划分特征 $A$ ，对应的任意划分点 $s$ 两边划分成的数据集 $D_1$ 和 $D_2$ ，求出使 $D_1$ 和 $D_2$ 各自集合的均方差最小，同时 $D_1$ 和 $D_2$ 的均方差之和最小所对应的特征和特征值划分点。表达式为：
$\underbrace{min}_{A,s}\left[ \underbrace{min}_{c_1} \sum^{}_{x_i\in{D_1}(A,s)}{(y_i-c_1)^2} + \underbrace{min}_{c_2} \sum^{}_{x_i\in{D_2}(A,s)}{(y_i-c_2)^2} \right]$
1. 决策树建立后做预测的方式不同。
  1. CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。
  2. CART回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

4.CART分类树使用了使用的是基尼系数的度量方式

CART算法相比C4.5算法的分类方法，采用了简化的二叉树模型，同时特征选择采用了近似的基尼系数来简化计算。当然CART树最大的好处是还可以做回归模型，这个C4.5没有。

5.3.2 CART的不足

无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1，这里不多介绍。
如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。

6. 总结

决策树算法的优点：

简单直观，生成的决策树很直观。
基本不需要预处理，不需要提前归一化，处理缺失值。
使用决策树预测的代价是 $O({\log_2^m})$ 。 $m$ 为样本数。
既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
可以处理多维度输出的分类问题。
相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释
可以交叉验证的剪枝来选择模型，从而提高泛化能力。
对于异常点的容错能力好，健壮性高。

决策树算法的缺点:

决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

决策树