剪枝理论

剪枝理论，决策树的剪枝在上一节中没有仔细讲，趁这个机会学习了剪枝的基础理论，这里会详细学习。

决策树为什么(WHY)要剪枝？原因是避免决策树过拟合(Overfitting)样本。前面的算法生成的决策树非常详细并且庞大，每个属性都被详细地加以考虑，决策树的树叶节点所覆盖的训练样本都是“纯”的。因此用这个决策树来对训练样本进行分类的话，你会发现对于训练样本而言，这个树表现完好，误差率极低且能够正确得对训练样本集中的样本进行分类。训练样本中的错误数据也会被决策树学习，成为决策树的部分，但是对于测试数据的表现就没有想象的那么好，或者极差，这就是所谓的过拟合(Overfitting)问题。Quinlan教授试验，在数据集中，过拟合的决策树的错误率比经过简化的决策树的错误率要高。

现在问题就在于，如何(HOW)在原生的过拟合决策树的基础上，生成简化版的决策树？可以通过剪枝的方法来简化过拟合的决策树。剪枝可以分为两种：预剪枝(Pre-Pruning)和后剪枝(Post-Pruning),下面我们来详细学习下这两种方法：

PrePrune：预剪枝，及早的停止树增长，方法可以参考见上面树停止增长的方法。

PostPrune：后剪枝，在已生成过拟合决策树上进行剪枝，可以得到简化版的剪枝决策树。

其实剪枝的准则是如何确定决策树的规模，可以参考的剪枝思路有以下几个：

1：使用训练集合(Training Set）和验证集合(Validation Set)，来评估剪枝方法在修剪结点上的效用

2：使用所有的训练集合进行训练，但是用统计测试来估计修剪特定结点是否会改善训练集合外的数据的评估性能，如使用Chi-Square（Quinlan，1986）测试来进一步扩展结点是否能改善整个分类数据的性能，还是仅仅改善了当前训练集合数据上的性能。

3：使用明确的标准来衡量训练样例和决策树的复杂度，当编码长度最小时，停止树增长，如MDL(Minimum Description Length)准则。

我们先看下使用思路一来解决问题的集中后剪枝方法：

Reduced-Error Pruning(REP,错误率降低剪枝）

该剪枝方法考虑将书上的每个节点作为修剪的候选对象，决定是否修剪这个结点有如下步骤组成：

1：删除以此结点为根的子树

2：使其成为叶子结点

3：赋予该结点关联的训练数据的最常见分类

4：当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点

因为训练集合的过拟合，使得验证集合数据能够对其进行修正，反复进行上面的操作，从底向上的处理结点，删除那些能够最大限度的提高验证集合的精度的结点，直到进一步修剪有害为止(有害是指修剪会减低验证集合的精度)

REP是最简单的后剪枝方法之一，不过在数据量比较少的情况下，REP方法趋于过拟合而较少使用。这是因为训练数据集合中的特性在剪枝过程中被忽略，所以在验证数据集合比训练数据集合小的多时，要注意这个问题。

尽管REP有这个缺点，不过REP仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学习方法的优点和缺点提供了了一个很好的学习思路。由于验证集合没有参与决策树的创建，所以用REP剪枝后的决策树对于测试样例的偏差要好很多，能够解决一定程度的过拟合问题。

Pessimistic Error Pruning(PEP，悲观剪枝）

先计算规则在它应用的训练样例上的精度，然后假定此估计精度为二项式分布，并计算它的标准差。对于给定的置信区间，采用下界估计作为规则性能的度量。这样做的结果，是对于大的数据集合，该剪枝策略能够非常接近观察精度，随着数据集合的减小，离观察精度越来越远。该剪枝方法尽管不是统计有效的，但是在实践中有效。

PEP为了提高对测试集合的预测可靠性，PEP对误差估计增加了连续性校正(Continuity Correction)。PEP方法认为，如果：

成立，则Tt应该被剪枝，上式中：

其中，e(t)为结点t出的误差；i为覆盖Tt的叶子结点；Nt为子树Tt的叶子树；n(t)为在结点t处的训练集合数量。PEP采用自顶向下的方式，如果某个非叶子结点符合上面的不等式，就裁剪掉该叶子结点。该算法被认为是当前决策树后剪枝算法中经度比较高的算法之一，但是饿存在有缺陷。首先，PEP算法是唯一使用Top-Down剪枝策略，这种策略会导致与先剪枝出现同样的问题，将该结点的某子节点不需要被剪枝时被剪掉；另外PEP方法会有剪枝失败的情况出现。

虽然PEP方法存在一些局限性，但是在实际应用中表现出了较高的精度,。两外PEP方法不需要分离训练集合和验证机和，对于数据量比较少的情况比较有利。再者其剪枝策略比其它方法相比效率更高，速度更快。因为在剪枝过程中，树中的每颗子树最多需要访问一次，在最坏的情况下，它的计算时间复杂度也只和非剪枝树的非叶子节点数目成线性关系。

可能有同学会对上面的那个不等式有疑问，可以参考这篇文章http://blog.sina.com.cn/s/blog_68ffc7a40100urn3.html 中关于PEP剪枝部分内容。PEP方法实际上是将结点误差数目看做二项式分布，根据期望和方差得到的结果。

Cost-Complexity Pruning(CCP、代价复杂度)

CCP方法包含两个步骤：

1：从原始决策树T0开始生成一个子树序列{T0、T1、T2、…、Tn},其中Ti+1是从Ti总产生，Tn为根节点

2：从子树序列中，根据树的真实误差估计选择最佳决策树。

在步骤一中，生成子树序列{T0、T1、T2、…、Tn}的基本思想是从T0开始，裁剪Ti中关于训练数据集合误差增加最小的分支来得到Ti+1。实际上当一棵树T在结点t出剪枝时，它的误差增加直观上认为是:

其中R(t)为在结点t的子树被裁剪后结点t的误差，R(Tt)为在结点t的子树没被裁剪时子树T的误差。不过剪枝后T的叶子树减少了|L(Ti)|-1，其中|L(Ti)|为子树Ti的叶子树，也就是说T的复杂性降低。因此考虑到树的复杂性因素，树分支被裁剪后误差增加率可以由下式决定：

Ti+1就是选择Ti中具有最小\alpha值所对应的剪枝树

如何从第一步骤产生的子树序列{T0、T1、T2、…、Tn}中选择出最佳决策树是CCP方法的第二步骤的关键。通常可以采用V-交叉验证(V-fold Cross-Validation)和基于独立剪枝数据集两种方法，这两种方法可以参考(Classification And Regression Trees,Breiman et.al)。当使用基于独立数据集剪枝时，和REP方法相比，CCP选择出来的最有决策树，不是从原始决策树T的所有可能子树中得到，所以有可能会找到到最有决策树。

其它如Minimum Error Pruning(MEP)，Critical Value Pruning(CVP)，Optimal Pruning(OPP)，Cost-Sensitive Decision Tree Pruning(CSDTP)等方法，这些剪枝方法各有利弊，关注不同的优化点，感兴趣的同学可以学习下。

剪枝过程特别重要，所以在最优决策树生成过程中占有重要地位。有研究表明，剪枝过程的重要性要比树生成过程更为重要，对于不同的划分标准生成的最大树(Maximum Tree)，在剪枝之后都能够保留最重要的属性划分，差别不大。反而是剪枝方法对于最优树的生成更为关键。重点理解这些剪枝方法的理论，对于最终最优树的生成是有好处的，其中上篇文章http://isilic.iteye.com/blog/1844097中C4.5使用了PEP剪枝方法，本文的CART使用了CCP的剪枝方法，实际上，不应该对于算法使用的剪枝方法过于追根究底，而是应该对于剪枝过程理解透彻，对于在何种场景下对于不同的数据类型使用何种的剪枝方法能够获得最优树的选择，才是真正理解了剪枝的理论和重要性。