1700534618
1700534619
■ 后剪枝
1700534620
1700534621
后剪枝的核心思想是让算法生成一棵完全生长的决策树，然后从最底层向上计算是否剪枝。剪枝过程将子树删除，用一个叶子结点替代，该结点的类别同样按照多数投票的原则进行判断。同样地，后剪枝也可以通过在测试集上的准确率进行判断，如果剪枝过后准确率有所提升，则进行剪枝。相比于预剪枝，后剪枝方法通常可以得到泛化能力更强的决策树，但时间开销会更大。
1700534622
1700534623
常见的后剪枝方法包括错误率降低剪枝（Reduced Error Pruning，REP）、悲观剪枝（Pessimistic Error Pruning，PEP）、代价复杂度剪枝（Cost Complexity Pruning，CCP）、最小误差剪枝（Minimum Error Pruning，MEP）、CVP（Critical Value Pruning）、OPP（Optimal Pruning）等方法，这些剪枝方法各有利弊，关注不同的优化角度，本文选取著名的CART剪枝方法CCP进行介绍。
1700534624
1700534625
代价复杂剪枝主要包含以下两个步骤。
1700534626
1700534627
（1）从完整决策树T0开始，生成一个子树序列{T0,T1,T2,…,Tn}，其中Ti+1由Ti生成，Tn为树的根结点。
1700534628
1700534629
（2）在子树序列中，根据真实误差选择最佳的决策树。
1700534630
1700534631
步骤（1）从T0开始，裁剪Ti中关于训练数据集合误差增加最小的分支以得到Ti+1。具体地，当一棵树T在结点t处剪枝时，它的误差增加可以用R(t)−R(Tt)表示，其中R(t)表示进行剪枝之后的该结点误差，R(Tt)表示未进行剪枝时子树Tt的误差。考虑到树的复杂性因素，我们用|L(Tt)|表示子树Tt的叶子结点个数，则树在结点t处剪枝后的误差增加率为
1700534632
1700534633
1700534634
．
1700534635
1700534636
（3.25）
1700534637
1700534638
在得到Ti后，我们每步选择α最小的结点进行相应剪枝。
1700534639
1700534640
用一个例子简单地介绍生成子树序列的方法。假设把场景中的问题进行一定扩展，女孩需要对80个人进行见或不见的分类。假设根据某种规则，已经得到了一棵CART决策树T0，如图3.15所示。
1700534641
1700534642
此时共5个内部结点可供考虑，其中
1700534643
1700534644
1700534645
，
1700534646
1700534647
1700534648
，
1700534649
1700534650
1700534651
，
1700534652
1700534653
1700534654
，
1700534655
1700534656
1700534657
．
1700534658
1700534659
可见α（t3）最小，因此对t3进行剪枝，得到新的子树T1，如图3.16所示。
1700534660
1700534661
1700534662
1700534663
1700534664
图3.15 初始决策树T0
1700534665
1700534666
1700534667