剪枝
将复杂的决策树进行简化的过程称为剪枝，它的目的是去掉一些节点，包括叶节点和中间节点。
剪枝常用方法：预剪枝与后剪枝两种。
预剪枝：在构建决策树的过程中，提前终止决策树生长，从而避免过多的节点产生。该方法不实用，我们无法判断何时终止树的生长。
后剪枝：在决策树构建完成后，再去掉一些节点。
常见的后剪枝方法有四种：
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.****.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个样本的响应值。