剪枝的目的：

剪枝的目的是为了避免决策树模型的过拟合。因为决策树算法在学习的过程中为了尽可能的正确的分类训练样本，不停地对结点进行划分，因此这会导致整棵树的分支过多，也就导致了过拟合。决策树的剪枝策略最基本的有两种：预剪枝（pre-pruning）和后剪枝（post-pruning）：

• 预剪枝（pre-pruning）：预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛化性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。
• 后剪枝（post-pruning）：后剪枝就是先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛化性能的提升，则把该子树替换为叶结点。

一、数据集：

其中{1,2,3,6,7,10,14,15,16,17}为测试集，{4,5,8,9,11,12,13}为训练集。

二、预剪枝

再回顾一下预剪枝：预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛化性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。

使用以上数据集，根据信息增益可以构造出一颗未剪枝的决策树（图片来自西瓜书）：

具体构造过程如下：
（1）分别计算所有特征的信息增益，据此选出决策树的根节点

由上述计算结果可知：信息增益值：脐部（0.276）=色泽（0.276）>纹理（0.174）=敲声（0.174）>根蒂（0.115）>触感（0）

（2）因为色泽和脐部的信息增益值最大，所以从这两个中随机挑选一个，这里选择脐部来对数据集进行划分，即为决策树的第①个节点；这会产生三个分支，分别是凹陷、稍凹、平坦，对应节点②，节点③，节点④；

而此时是预剪枝。需要判断是否按照“脐部”进行划分，判断标准：看划分前后的泛化性能是否有提升，如果划分后泛化性能有提升，则划分；否则，不划分，具体计算如下：

• 划分前：根据训练集，类别标记为训练样例数最多的类别，由于训练集中的好瓜与坏瓜是相同多的类别，均为5，因此任选其中一类，此处选择了好瓜作为标记类别（也就是说10个瓜，管他好的坏的，全标记是好瓜了）。此时验证集（3个好瓜，7个坏瓜）在这棵决策树上的精度为3/7=42.9%
• 划分后：（9，13）这两个编号的瓜原本都是坏瓜，结果都被分成好瓜了，其他瓜（4，5，8，11，12）都被分对了。所以验证集在这棵决策树上的精度为5/7=71.4%
• 比较： 42.9% < 71.4%，所以划分后的泛化能力有提升，应该对“脐部”进行划分
• 此时划分后的决策树为：
  
  （3）在对“脐部”进行划分的基础上，再对节点②进行划分，再次使用信息增益挑选出训练集{1，2，3，14}中值最大的那个特征为“色泽”、“根蒂”与“纹理”（三个的增益值同样最大），随便选一个，选的是色泽，再对“色泽”进行划分，即下图所示，此时与(1)步骤相同，分别计算划分前后，对验证集的泛化性能是否有提升，有，划分；否则，越划越差就别划了
  
  看圈出来的部分，可见按照“色泽”进行划分后，验证集精度反而下降，所以别划分“色泽”这个特征了（禁止划分）；

（4）在对“脐部”进行划分的基础上，再对节点③进行划分，再次使用信息增益挑选出训练集{6，7，5，17}值最大的那个特征为“根蒂”、“敲声”、“触感”（三个的增益值同样最大），随便选一个，选的是根蒂，再对“根蒂”进行划分，即下图所示，此时与(1)步骤相同，分别计算划分前后，对验证集的泛化性能是否有提升，有，划分；否则，越划越差就别划了

看圈出来的部分，可见按照“根蒂”进行划分后，验证集精度不变，所以别划分“根蒂”这个特征了（禁止划分）；

（5）对于结点 ④ ，其所含训练样本已属于同一类，所以不再进行划分。

所以基于预剪枝策略生成的最终的决策树为：

预剪枝总结：

预剪枝的优点：

降低过拟合风险和显著减少了训练的时间和测试时间

预剪枝的缺点：

带来了欠拟合风险。因为有些分支的当前划分虽然不能提升泛化性能，但在其基础上进行的后续划分却有可能导致性能显著提高

三、后剪枝

再回顾一下后剪枝：后剪枝就是先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛化性能的提升，则把该子树替换为叶结点。
之前提到，使用（一、数据集）中的数据集，根据信息增益可以构造出一颗未剪枝的决策树（图片来自西瓜书）：

后剪枝步骤：
（1）首先考察上图中的结点 ⑥，若将以其为根节点的子树删除（即剪枝），即相当于把结点⑥ 替换为叶结点，替换后的叶结点包括编号为{7,15}的训练样本，把该叶结点标记为“好瓜”（因为这里正负样本数量相等，都为1，所以随便标记一个类别），此时的决策树在验证集上的精度为4/7=57.1%（而未剪枝的决策树为3/7=42.9%），所以对节点⑥决定剪枝

（2）然后考察上图中的节点⑤, 此时：未剪枝前在验证集上的精度为4/7=57.1%（即（1）中剪枝结果的精度），而剪枝之后在验证集上的精度也为4/7=57.1%，所以对节点⑤决定不剪枝

（3）同上，对节点②进行考察，发现剪枝前：4/7=57.1% ，剪枝后：5/7=71.4%，所以对节点②决定剪枝
（4）同上，对节点③进行考察，发现剪枝前：5/7=71.4% ，剪枝后：5/7=71.4%，所以对节点③决定不剪枝
（5）最后，对节点①进行考察，发现剪枝前：5/7=71.4% ，剪枝后（此时和预剪枝中要不要对节点①“脐部”进行划分时的不划分状态的精度一致）：3/7=42.9%，所以对节点①决定不剪枝

所以基于后剪枝策略生成的最终的决策树为：

后剪枝总结

后剪枝优点：

后剪枝比预剪枝保留了更多的分支，欠拟合风险小，泛化性能往往优于预剪枝决策树

后剪枝缺点：

后剪枝训练时间开销大，后剪枝过程是在生成完全决策树之后进行的，需要自底向上对所有非叶结点逐一考察

四、总结（两种剪枝策略对比）

参考文献
[1]: 周志华 《机器学习》
[2]:决策树（decision tree）(二)——剪枝
[3]:决策树的预剪枝与后剪枝