模型算法基础——决策树剪枝算法（三）

在经过前两篇模型算法基础——决策树剪枝算法（一）和模型算法基础——决策树剪枝算法（二）之后，相信同学们对误差降低剪枝(REP)和悲观错误剪枝(PEP)已经有了一定的了解了，那么今天我们再来介绍一种剪枝算法——代价复杂度剪枝(Cost Complexity Pruning/CCP)。

代价复杂度剪枝分为两步：

第一步：在所有非叶子节点中寻找代价复杂度参数最小的节点，其中代价复杂度参数为：

其中e(T)为错分率，p(T)为该节点所覆盖的样本量占总样本量的比例，L(T)为T节点下叶子节点的个数。

还是前两篇的那个栗子，假设总样本量为60，计算节点T4的代价复杂度参数：

第二步：循环对代价复杂度参数最小的节点进行剪枝（有多个节点同时取到最小值时取叶子节点最多的节点），直到只剩下根节点，可得到一系列的剪枝数，其中T0为原始的决策树，Tm为根节点，Ti+1为Ti剪枝后的结果。在这一系列的剪枝树中，根据实际的误差估计决定最优的决策树。

代价复杂度参数α可以理解为代价和复杂度之间的关系，剪枝后叶子节点的个数（复杂度）减少，但是错分样本个数（代价）增多了。CCP是在一系列子树中选择最优树，因此结果也较为准确。

除此之外，还有Minimum Error Pruning(MEP), CriticalValue Pruning(CVP), Optimal Pruning(OPP), Error Based Pruning(EBP)等等剪枝方法，这些方法各有优缺点和针对性，感兴趣的同学可以学习一下。