决策树剪枝

作者: Max_7 | 来源:发表于2018-11-29 15:51 被阅读0次

一概述

决策树剪枝的目的：防止构建的决策树出现过拟合。
理由：随着决策树的深度的增加，模型的准确度肯定会越来越好。但是对于新的未知数据，模型的表现会很差，泛化能力不够。
在数据集没有足够多的情况下，数据集本身存在噪声，同时数据的特征属性不能完全作为分类的标准。以上三点会使决策树出现过拟合现象。

剪枝

构建如下的损失函数：
$C_{\alpha}T=\sum_{t=1}^{|T|}N_{t}H_{t}(T)+\alpha|T|$
其实各个参数的含义：
$|T|$ ：树中叶子的个数
$N_{t}$ :第t个叶子中的样本数量
$H_{t}$ :第t个叶子的熵
$\alpha$ :惩罚因子
可见，模型的复杂度越高，损失越大。

剪枝方法

剪枝分为预剪枝和后剪枝两种方法。

预剪枝

在构建完全正确分类训练集的决策树之前，停止树的构建。
常见有3种方法来决定何时停止树的构建：
1 预设树的高度。当决策树的高度达到预设值之后，停止继续构建。
2 设定阈值。当叶子结点里的实例数量小于阈值时，停止。
3 设定阈值。计算每一次增加深度后模型的增益，增益小于阈值，则停止。

优点：速度快，计算量少。
缺点：视线短浅。比如一颗完整的决策树有5层，A-> B->C->D->E。
从B->C的过程中模型几乎没有什么提升，但是从C->D的过程中模型的准确度提升显著。这种情况使用预剪枝，会使模型提前终止。

后剪枝

后剪枝的整体思路是先构建完整的决策树，然后再对决策树进行剪枝操作。

1 错误率降低剪枝

错误率降低剪枝（REP,Reduce-Error Pruning）
使用一个测试集。
对于非叶子节点的子树，尝试把它替换成叶子节点。用子树中样本数量最多的类来表示这个节点的结果。比较替换前后，两个决策树在测试集上的表现。
从下至上，遍历所有的可能的子树，直到在测试集上没有提升时，停止。

缺点：当数据量较少时，会过度剪枝，产生过拟合现象（只着眼于当前少量数据的特征，对于未知数据表现差）。
一些少量的，只出现在训练集中的有效的特征，会被剪掉（因为该特征不出现在测试集中）。

2 悲观剪枝

悲观剪枝（PEP，Pessimistic Error Pruning）
特点：从上至下，不用专门使用测试集。
对于决策树中的子树，尝试把它直接替换成一个叶子节点（具体用哪个节点来替代不太确定，有些资料表示直接用子树的根来替换）。
比较被替换子树的错误数-标准差（由二项分布计算）和新叶子节点错误数
如果前者大，那么执行剪枝操作。反之保留。
这里会计算这个叶子经验错误率E。这个E会在标准差的计算中用到。
公式为：
$\frac{\sum E +0.5*L}{\sum N}$
其中L表示的是子树的叶子个数，0.5为系数，可以调整。

优点：精确度较高。不用分出数据集做测试集。速度快（O（n））
缺点：因为是自顶而下，会出现和预剪枝类似的情况，出现提前终止的情况。

3 代价复杂度剪枝

代价复杂度剪枝（CCP， Cost-Complexity Pruning)
决策树的损失函数：
$C_{\alpha}=C（T）+\alpha|T|$
将 $\alpha$ 视为变量，当 $\alpha$ 极小时，最初的决策树就是最优解，当其极大时，只能使用最简单的决策树，也就是根节点作为最优解。所以，当 $\alpha$ 固定时，可以找到一个最优的决策树结构 $T(\alpha)$ 。
对于一颗子树而言：
剪枝前：
$C_{\alpha}(T_{t})=C（T_{t}）+\alpha|T_{t}|$
剪枝后：
$C_{\alpha}(t)=C（t）+\alpha$
这里剪枝后，子树就只有一个节点了。
令剪枝前后的损失相等，可以求得
$\alpha^{'}=\frac {C(t)-C_{\alpha}(t)}{|T_{t}|-1}$
如果 $\alpha > \alpha^{'}$ 说明 $C_{\alpha}(T_{t}) > C_{\alpha}(t)$ 。执行剪枝操作。
下一步就是对这个子树中每个节点都计算一次
$g(t)=\frac {C(t)-C_{\alpha}(t)}{|T_{t}|-1}$
这里g(t)表示剪枝后，整体损失函数的减少程度。
找到最小的g(t)，剪去。
选最小值剪去的原因是，当前节点直至叶子节点的误差差距很小，那说明这几层的构建是没有意义的或者说意义非常少。例如从B子树到叶子节点，整个子树有8层深。这棵8层深树与直接把B节点当整棵子树相比，误差只小了0.0001，那么就没有什么必要构建这8层子树，直接剪掉就好。
整个算法的复杂度为 $O(N^{2})$