Python实现决策树的预剪枝与后剪枝（下）

　　决策树构造完成后进行剪枝。剪枝的过程是对拥有同样父节点的一组节点进行检查，判断如果将其合并，熵的增加量是否小于某一阈值。如果确实小，则这一组节点可以合并一个节点，其中包含了所有可能的结果。后剪枝是目前最普遍的做法。

　　后剪枝的剪枝过程是删除一些子树，然后用其叶子节点代替，这个叶子节点所标识的类别通过大多数原则(majority class criterion)确定。所谓大多数原则，是指剪枝过程中, 将一些子树删除而用叶节点代替,这个叶节点所标识的类别用这棵子树中大多数训练样本所属的类别来标识,所标识的类 称为majority class ，（majority class 在很多英文文献中也多次出现）。

　　后剪枝算法有很多种，这里简要总结如下：

　　·Reduced-Error Pruning(REP)

　　· Pesimistic-Error Pruning(PEP)

　　· Cost-Complexity Pruning(CCP)

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

　　这个思路很直接，完全的决策树不是过度拟合么，我再搞一个测试数据集来纠正它。对于完全决策树中的每一个非叶子节点的子树，我们尝试着把它替换成一个叶子节点，该叶子节点的类别我们用子树所覆盖训练样本中存在最多的那个类来代替，这样就产生了一个简化决策树，然后比较这两个决策树在测试数据集中的表现，如果简化决策树在测试数据集中的错误比较少，那么该子树就可以替换成叶子节点。该算法以bottom-up的方式遍历所有的子树，直至没有任何子树可以替换使得测试数据集的表现得以改进时，算法就可以终止。

　　Pessimistic Error Pruning (PEP，悲观剪枝）

　　PEP剪枝算法是在C4.5决策树算法中提出的， 把一颗子树（具有多个叶子节点）用一个叶子节点来替代（我研究了很多文章貌似就是用子树的根来代替）的话，比起REP剪枝法，它不需要一个单独的测试数据集。

　　PEP算法首先确定这个叶子的经验错误率（empirical）为（E+0.5）/N，0.5为一个调整系数。对于一颗拥有L个叶子的子树，则子树的错误数和实例数都是就应该是叶子的错误数和实例数求和的结果，则子树的错误率为e

　　然后用一个叶子节点替代子树，该新叶子节点的类别为原来子树节点的最优叶子节点所决定，J为这个替代的叶子节点的错判个数，但是也要加上0.5，即KJ+0.5。最终是否应该替换的标准为

　　被替换子树的错误数-标准差 > 新叶子错误数

　　出现标准差，是因为子树的错误个数是一个随机变量，经过验证可以近似看成是二项分布，就可以根据二项分布的标准差公式算出标准差，就可以确定是否应该剪掉这个树枝了。子树中有N的实例，就是进行N次试验，每次实验的错误的概率为e，符合 B(N,e) 的二项分布，根据公式，均值为Ne，方差为Ne(1-e)，标准差为方差开平方。

　　Cost-Complexity Pruning(CCP，代价复杂度剪枝)

　　在决策树中，这种剪枝技术是由代价复杂性参数ccp_alpha来参数化的。ccp_alpha值越大，剪枝的节点数就越多。简单地说，代价复杂性是一个阈值。只有当模型的整体不纯度改善了一个大于该阈值的值时，该模型才会将一个节点进一步拆分为其子节点，否则将停止。

　　当CCP值较低时，即使不纯度减少不多，该模型也会将一个节点分割成子节点。随着树的深度增加，这一点很明显，也就是说，当我们沿着决策树往下走时，我们会发现分割对模型整体不纯度的变化没有太大贡献。然而，更高的分割保证了类的正确分类，即准确度更高。

　　当CCP值较低时，会创建更多的节点。节点越高，树的深度也越高。

　　下面的代码(Scikit Learn)说明了如何对alpha进行调整，以获得更高精度分数的模型。

　　从结果可知如果alpha设置为0.04得到的测试集精度最好，我们将从新训练模型。

后剪枝后决策树

　　可以看到，模型深度非常浅，也能达到很好的效果。模型在训练集上有140个错误样本，但在测试集上只存在54个错误样本。

训练数据集混淆矩阵

测试数据集混淆矩阵