决策树剪枝，常用这2种方法

前面我们了解了决策树的概念，现在来了解一下决策树剪枝。可能会有人问：为什么要剪枝?答案是：如果一棵决策树完全生长，那么这棵决策树所对应的每一个叶节点中只会包含一个样本，就很有可能面临过拟合问题，因此就需要我们对这棵决策树进行剪枝，以此来提高此决策树模型的泛化能力。

一般情况下，可以使用以下两类方法对决策树进行剪枝，缩小决策树的规模:

一、预剪枝：

预剪枝的核心思想是在树中节点进行扩展之前，先计算当前的划分是否能提升模型泛化能力，如果不能，则不再继续生长子树。此时可能出现不同类别的样本同时存于节点中的情况，可以通过使用多数投票的原则对该节点所属类别进行判断。关于预剪枝何时停止决策树的生长，可以采用以下几种方法：

(1) 当树达到一定深度的时候，停止树的生长;

(2) 当到达当前节点的样本数量比某个阈值小的时候，停止树的生长;

(3) 计算决策树的每一次分裂能否提升测试集的准确度，当提升程度小于某个阈值的时候，不再继续生树的长。

预剪枝具有思想直接、算法简单、效率高等一系列特点，适合解决大规模数据的问题。但是，对于上述阈值，需要一定的经验来进行判断。另外，预剪枝存在欠拟合风险。这是因为，虽然当前的划分会导致测试集准确率降低或提升不高，但在之后的划分中，准确率会有显著提升也不无可能。

二、后剪枝：

后剪枝的核心思想是先让算法生成一颗完全生长的决策树，然后自底层向上计算是否进行剪枝操作。后剪枝也需要通过在测试集上的准确率来进行判断，如果剪枝之后，能够提升准确率，则进行剪枝。

具体操作：

1.如果存在任一子集是一棵树，则在该子集递归剪枝过程

2.计算不合并的误差

3.如果合并会降低误差的话，就将叶节点合并

在回归树一般用总方差计算误差(即用叶子节点的值减去所有叶子节点的均值)。

相比于预剪枝，后剪枝的泛化能力更强，但是计算开销会更大。

后剪枝方法： 错误率降低剪枝(Reduced Error Pruning,REP)、悲观剪枝(Pessimistic Error Pruning,PEP)、代价复杂度剪枝(Cost Complexity Pruning,CCP)、最小误差剪枝(Minimum Error Pruning,MEP)、CVP(Critical Value Pruning)、OPP(Optimal Pruning)等。