决策树剪枝

一 概述

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

剪枝

构建如下的损失函数：

其实各个参数的含义：
：树中叶子的个数
:第t个叶子中的样本数量
:第t个叶子的熵
:惩罚因子
可见，模型的复杂度越高，损失越大。

剪枝方法

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

预剪枝

在构建 完全正确分类训练集 的决策树之前，停止树的构建。
常见有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会在标准差的计算中用到。
公式为：

其中L表示的是子树的叶子个数，0.5为系数，可以调整。

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

3 代价复杂度剪枝

代价复杂度剪枝 （CCP， Cost-Complexity Pruning)
决策树的损失函数：

将视为变量，当极小时，最初的决策树就是最优解，当其极大时，只能使用最简单的决策树，也就是根节点作为最优解。所以，当固定时，可以找到一个最优的决策树结构。
对于一颗子树而言：
剪枝前：

剪枝后：

这里剪枝后，子树就只有一个节点了。
令剪枝前后的损失相等，可以求得

如果说明。执行剪枝操作。
下一步就是对这个子树中每个节点都计算一次

这里g(t)表示剪枝后，整体损失函数的减少程度。
找到最小的g(t)，剪去。
选最小值剪去的原因是，当前节点直至叶子节点的误差差距很小，那说明这几层的构建是没有意义的或者说意义非常少。例如从B子树到叶子节点，整个子树有8层深。这棵8层深树与直接把B节点当整棵子树相比，误差只小了0.0001，那么就没有什么必要构建这8层子树，直接剪掉就好。
整个算法的复杂度为

以上就是决策树剪枝的基本流程，具体选用哪个还是要在实际情况中分析。