决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但是对未知的测试数据的分类却不准确，这就叫过拟合，我们需要对决策树进行简化。这个过程叫做剪枝。
剪枝
剪枝从已生成的树上裁掉一些子树或者叶节点，并将其根节点或父节点作为新的叶节点，从而简化分类树模型。
过程
决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。设树T的叶子结点个数为|T|，t是树T的某个叶子节点，该叶子结点有$Nt$个样本,该叶子结点中k类的样本点有$N{tk} 个， k = 1,2,3,…K$，$Ht(T)为叶节点t上的经验熵，$ a>=0为参数，则决策树学习的损失函数可以定义为
$C_a(T)=\sum{t=1}^{|T|} N_tH_t(T)+a|T|$ 这个T代表了树，不一定非得是跟，也可能是某个节点组成的小树，思维不要僵化。
这其实是一种添加正则化项的思想。
其中，经验熵为$Ht(T)=-\sum{k}\frac{N{tk}}{N_t}log\frac{N_tk}{N_t}$ 叶节点t所有样本中k类的个数/叶节点t的总样本数
在损失函数中，将上式的第一项记作：
$$C(T)=\sum{t=1}^{|T|}NtH_t(T)=-\sum{t=1}^{|T|}\sum{k=1}^{K}N{tk}log\frac{N_{tk}}{N_t}C_a(T)=C(T)+a|T|$$
$C(T)$表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，参数控制两者之间的影响，较大的a促使选择简单的树，较小的a选择复杂的树。a=0意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。
剪枝就是当a确定时，选择损失函数最小的模型，即损失函数最小的子树。当a确定时，子树越大，往往拟合越好，但是模型复杂度就越高；子树越小则反之，损失函数正好表示了对两者的平衡。
输入：树T，参数a
输出：剪枝后的T
（1）计算每个结点的经验熵
（2）递归的从树的叶子结点向上回缩。
设一组叶节点回缩到其父节点之前与之后整体树分别为$T_B和T_A$，其对应的损失函数值分别为$C_a(T_B)$和$C_a(T_A)$，如果$C_a(T_A)$<=$C_a(T_B)$,说明这个非叶子节点没必要划分，则进行剪枝，因为划分反而会影响结果，就把该非叶子节点换成叶子节点，把它之前的儿子们中的样本全部放在现在这个节点中，取最多的类当做分类结果。
（3）返回（2），直到不能继续为止，得到损失函数最小的子树$T_a$
光说不练假把式，我们来一个例子试试。
例子
下图是我们已经生成的一颗决策树，
由于算法顺序是从下往上、所以我们先考察最右下方的 Node（该 Node 的划分标准是“测试人员”），该 Node 所包含的数据集如下表所示：
| 颜色 | 测试人员 | 结果 |
|---|---|---|
| 黄色 | 成人 | 爆炸 |
| 黄色 | 小孩 | 不爆炸 |
我们现在开始第一次尝试剪枝：
剪枝前：
剪枝前该结点（测试人员的那个节点），有2个叶子结点，我们来计算他的损失为$C_a(T)=C(T)+a|T|$
我们经过带入后得到
注意这时候的T不是整个树，而是右下角那个测试人员的那棵小树。所以为$C_a(T) = |T|a= 2a$
剪枝后：
剪枝之后，之前这个节点是非叶子结点，现在变成了叶子结点，我们来计算一下损失
所以
回忆生成算法的实现，我们彼时将α定义为了α=特征个数/2（注意：这只是α的一种朴素的定义方法，很难说它有什么合理性、只能说它从直观上有一定道理；如果想让模型表现更好、需要结合具体的问题来分析α应该取何值）。由于气球数据集 1.0 一共有四个特征、所以此时α=2；结合各个公式、我们发现：
所以我们已经进行局部剪枝，局部剪枝后的决策树如下图所示：
注意：进行局部剪枝后，由于该 Node 中样本只有两个、且一个样本类别为“不爆炸”一个为“爆炸”，所以给该 Node 标注为“不爆炸”、“爆炸”甚至以 50%的概率标注为“不爆炸”等做法都是合理的。为简洁，我们如上图中所做的一般、将其标注为“爆炸”
现在我们开始尝试第二次剪枝：
然后我们需要考察最左下方的 Node（该 Node 的划分标准也是“测试人员”），易知计算过程和上述的没有区别。对其进行局部剪枝后的决策树如下图所示：
现在我们开始尝试第三次剪枝：
然后我们需要考察右下方的 Node（该 Node 的划分标准是“动作”），该 Node 所包含的数据集如下表所示：
| 颜色 | 测试人员 | 测试动作 | 结果 |
|---|---|---|---|
| 黄色 | 成人 | 用手打 | 爆炸 |
| 黄色 | 成人 | 用脚踩 | 爆炸 |
| 黄色 | 小孩 | 用手打 | 不爆炸 |
| 黄色 | 小孩 | 用脚踩 | 爆炸 |
| 紫色 | 成人 | 用脚踩 | 爆炸 |
| 紫色 | 小孩 | 用脚踩 | 爆炸 |
剪枝前：
剪枝之前这个节点（动作）有2个叶子结点，一个叶子结点中有2个样本，一个叶子结点中有4个样本，让我们来计算一下这个结点的损失：
这个T代表动作这个小树
后面一项等于0，所以
剪枝后：
剪枝后改结点变成了叶子结点，有6个样本，我们来计算一下损失
将a=2带入后得剪枝后的损失<剪枝前的损失，所以应该进行剪枝。
后面的计算类似 我就不说了。 记住是对每棵树的每个叶子结点计算经验熵。
写到这里的时候我才知道剪枝还分为预剪枝和后剪枝，我刚才说的是后剪枝的一种方法，其实后剪枝还有很多方法。我再介绍一种方法。
这种方法需要一个验证集来进行验证。
你把这棵树的每个非叶子结点用验证集来对比剪枝前和剪枝后的结果，如果剪后的结果好于或者等于剪枝前，就可以进行剪枝，否则不进行剪枝，就是这样。不过这种方法不好的地方在于需要一个验证集。
我们再来介绍一下预剪枝，预剪枝的话方法比较少，这里我只介绍一种方法。
预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛华性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。不过也需要一个验证集
过程
（1）先计算所有特征的信息增益比，找到一个最合适的特征来划分决策树。
（2）但是因为是预剪枝，所以要判断是否应该进行这个划分，判断的标准就是看划分前后的泛华性能是否有提升，也就是如果划分后泛华性能有提升，则划分；否则，不划分。
（3）如果遇到了某个叶子结点划分后不如不划分，则这个叶子节点就不划分了，改去划分别的结点。
给个例子：
决策树用验证集来验证是否剪枝的例子
预剪枝总结：对比未剪枝的决策树和经过预剪枝的决策树可以看出：预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但是，另一方面，因为预剪枝是基于“贪心”的，所以，虽然当前划分不能提升泛华性能，但是基于该划分的后续划分却有可能导致性能提升，因此预剪枝决策树有可能带来欠拟合的风险。
后剪枝总结：对比预剪枝和后剪枝，能够发现，后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情形下，后剪枝决策树的欠拟合风险小，泛华性能往往也要优于预剪枝决策树。但后剪枝过程是在构建完全决策树之后进行的，并且要自底向上的对树中的所有非叶结点进行逐一考察，因此其训练时间开销要比未剪枝决策树和预剪枝决策树都大得多。
