将复杂的决策树进行简化的过程称为剪枝，它的目的是去掉一些节点，包括叶节点和中间节点。

剪枝常用方法：预剪枝与后剪枝两种。

 

预剪枝：在构建决策树的过程中，提前终止决策树生长，从而避免过多的节点产生。该方法不实用，我们无法判断何时终止树的生长。

 

后剪枝：在决策树构建完成后，再去掉一些节点。

常见的后剪枝方法有四种：

1.悲观错误剪枝（PEP）

2.最小错误剪枝（MEP）

3.代价复杂度剪枝（CCP）

4.基于错误的剪枝（EBP）

 

CCP可以用于CART算法中，它的本质是度量每减少一个叶节点所得到的平均错误。

 

每一个叶节点的减少，平均错误都会下降，CCP的本质就是通过计算度量其平均错误来进行的。

CCP算法会产生一系列树的序列，{T1,T2,T3,......Tm},其中T0是由训练得到的决策树，而Tm只含有一个根节点，序列中的树是嵌套的，也就是序列中的T(i+1)是由Ti通过剪枝得到的，即实现用T(i+1)中一个叶节点来替代Ti中医该节点为跟的子树。（此图可能有问题，后期我再改一下）

这种被替代的原则就是使误差的增加率α最小，即：

式中，R(n)表示Ti中节点n的预测误差，R(nt)表示Ti中以节点n为根节点的子树的所有叶节点的预测误差之和，|nt|为该子树叶节点的数量，|nt|也被称为复杂度，因为叶节点越多，复杂性当然就越强。

因此α的含义就是用一个节点n来替代以n为根节点的所有|nt|个节点的误差增加的规范化程度。

在Ti中，我们选择最小的α值的节点进行替代，最终得到Ti+1。

以此类推，每需要得到一棵决策树，都需要计算其前一棵决策树的α值，根据α值来对前一棵决策树进行剪枝，直到最终剪枝到只剩下含有一个根节点的Tm为止。

 

根据决策树是分类树还是回归树，节点的预测误差的计算也分为两种情况。

分类树：

分类误差公式：可以采用1,2,3三个公式，详情请见：https://blog.csdn.net/LEE18254290736/article/details/81842816

熵：        

基尼指数（Gini Index）：

分类误差：

 

假如用（3）来表示节点n的预测误差（这里R（n）就是直接等于分类误差的式子），则：

 

 

Nj表示节点n下第j个分类的样本数，N为该节点的所有样本数，max{Nj}表示在m个分类中，拥有样本数最多的那个分类的样本数量。

 

 

回归树：

我们用以下式子表示节点n的预测误差：

（熵计算用均方误差代替，把样本的预测值用样本数处置的平均来代替）

得到的式子为：

 

yi表示第i个样本的响应值，N为该节点的样本数量。

我们把分类树与回归树的这两个式子中，分子不分称为节点的风险值。

我们用全部样本得到的决策树序列为{T0,T1,…,Tm}，其所对应的α值为α0<α1<…<αm。

 

下一步就是如何从这个序列中最优的选择一颗决策树Ti。而与其说找到最优的Ti，不如说找到其所对应的αi。

这一步骤通常采用的方法是交叉验证（Cross-Validation，定义请见：https://baike.baidu.com/item/%E4%BA%A4%E5%8F%89%E9%AA%8C%E8%AF%81/8543100）。

 

我们把L个样本随机划分为数量相等的V个子集Lv，v=1,…,V。

第v个训练样本集为：

Lv被用来做的测试样本集。

对每个训练样本集按照CCP算法得到决策树的序列

其对应的α值为α0(v)<α1(v)<…<αm(v)。

α值的计算仍然采用

 

对分类树来说，第v个子集的节点n的预测误差为：

Nj(v)表示训练样本集L(v)中节点n的第j个分类的样本数，N(v)为L(v)中节点n的所有样本数，max{Nj(v)}表示在m个分类中，L(v)中节点n拥有样本数最多的那个分类的样本数量。

对于回归树来说，第v个子集的节点n的预测误差为：

yj(v)表示训练样本集L(v)中节点n的第i个样本的响应值。