决策树中有哪些剪枝算法

问题引入

大家可能都知道决策树在构建完成之后要做剪，但是大家知道有哪些常见的剪枝算法吗？大家可能接触到最多的就说CCP算法吧，在李航那本书上也有讲过这么一种算法，还有其他的几种算法，现在共同总结下，面试的时候大家不要说错了哦，最起码还是要说出来这些剪枝算法的，当然，还是要对一些基本的算法有详细的了解比如CCP。

问题回答

决策树中常见的剪枝算法有：
Reduced-Error Pruning（REP,错误率降低剪枝）
Pesimistic-Error Pruning（PEP,悲观错误剪枝）
Cost-Complexity Pruning（CCP，代价复杂度剪枝）
Minimum Error Pruning （MEP, 最小误差剪枝）

REP：通过一个新的验证集来纠正树的过拟合问题。对于决策树中的每一个非叶子节点的子树，我们将它替换成一个叶子节点，该叶子节点的类别用大多数原则来确定，这样就产生了一个新的相对简化决策树，然后比较这两个决策树在验证集中的表现。如果新的决策树在验证集中的正确率较高，那么该子树就可以替换成叶子节点，从而达到决策树剪枝的目的。

PEP：这个算法和REP差不多，和REP不同之处在于：PEP不需要新的验证集，并且PEP是自上而下剪枝的。由于我们还是用生成决策树时相同的训练样本，那么对于每个节点剪枝后的错分率一定是会上升的，因此在计算错分率时需要加一个惩罚因子0.5。

CPC：CCP算法为子树定义了代价和复杂度，以及一个衡量代价与复杂度之间关系的参数。代价指的是在剪枝过程中因子树被叶节点替代而增加的错分样本;复杂度表示剪枝后子树减少的叶结点数; 从下到上计算每一个非叶节点的α值，然后每一次都剪掉具有最小值的子树，最后得到,其中是完整的数，表示根节点，然后根据真实的错误率在中选择一个最好的。

MEP方法的基本思路是采用自底向上的方式，对于树中每个非叶节点。首先计算该节点的误差,然后，计算该节点每个分支的误差,并且加权相加，权为每个分支拥有的训练样本比例。如果大于,则保留该子树；否则就剪裁。

详细的对比如下：

大家对于复杂度、剪枝的方式还是需要掌握的，具体的大家可以看下参考文献中的链接，去深入了解详细的剪枝算法，这里就不再进行详细的介绍了。

参考：

https://www.cnblogs.com/starfire86/p/5749334.html
https://link.zhihu.com/?target=http%3A//blog.csdn.net/yujianmin1990/article/details/49864813
https://zhuanlan.zhihu.com/p/30296061
https://blog.csdn.net/weixin_43216017/article/details/87534496
https://blog.csdn.net/sheepy123/article/details/89850764