机器学习算法(三) 决策树 (二) 决策树的剪枝

　　决策树生成算法递归的产生决策树，知道不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但是对为止的数据不太友好，容易产生过拟合 问题，所以引入了剪枝这个话题。
　　首先剪枝（pruning）的目的是为了避免决策树模型的过拟合。决策树的剪枝策略最基本的有两种：预剪枝（pre-pruning）和后剪枝（post-pruning）：

• 预剪枝（pre-pruning）：预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛华性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。
• 后剪枝（post-pruning）：后剪枝就是先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛华性能的提升，则把该子树替换为叶结点。

预剪枝

　　关于预剪枝（pre-pruning）的基本概念，在前面已经介绍过了，下面就直接举个例子来看看预剪枝（pre-pruning）是怎样操作的。数据集为（图片来自西瓜书）：
，
通过ID3算法可以构建一个如下的决策树：

计算出所有特征的信息增益值：

因为色泽和脐部的信息增益值最大，所以从这两个中随机挑选一个，这里选择脐部来对数据集进行划分，这会产生三个分支，如下图所示：

但是因为是预剪枝，所以要判断是否应该进行这个划分，判断的标准就是看划分前后的泛华性能是否有提升，也就是如果划分后泛华性能有提升，则划分；否则，不划分。

在测试集中：在没有分类的时候，首先将测试集的所有数据都认为是好瓜，发现只有4、5、8分类正确，那么,正确率为 3/7 = 0.428
在训练集中：可以看到凹陷和稍凹的都是好瓜，平坦的不是好瓜
在测试集中：在进行分类的时候发现，4 5 8 11 12分类正确，那么正确率提升，所以可以使用这个特征进行分类
在凹陷中判断色泽是否起到促进作用
在测试集中： 在没有分类的时候，首先认为凹陷的西瓜都是好瓜，那么4 5分类正确，那么准确率为 2/3 = 0.666
在训练集中 青绿 乌黑是好瓜，而浅白是坏瓜，
在测试集中：在进行分类的时候发现，4 5 8 11 12分类正确，那么正确率提升，所以可以使用这个特征进行分类，只分类对1个，所以说分类没有促进作用，不可以这样分。 （自己理解的结果和西瓜书里面差别比较大，期待指正）

总结： 对比未剪枝的决策树和经过预剪枝的决策树可以看出：预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但是，另一方面，因为预剪枝是基于“贪心”的，所以，虽然当前划分不能提升泛华性能，但是基于该划分的后续划分却有可能导致性能提升，因此预剪枝决策树有可能带来欠拟合的风险。

后剪枝

总结：对比预剪枝和后剪枝，能够发现，后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情形下，后剪枝决策树的欠拟合风险小，泛华性能往往也要优于预剪枝决策树。但后剪枝过程是在构建完全决策树之后进行的，并且要自底向上的对树中的所有非叶结点进行逐一考察，因此其训练时间开销要比未剪枝决策树和预剪枝决策树都大得多。

参考：周志华 《机器学习》