简介
决策树是与有监督学习中的常用方法。决策树的算法多见于分类问题中，即我们常说的分类树（Classification Tree）；少数情况下，决策树也可以用于连续问题，即回归树（Regression Tree）。若构建决策树的自变量过多，会产生高维度、过拟合等问题，因此，需要在全树的基础上进行剪枝，保留最有效的自变量，删除不那么重要的自变量。这一过程，就叫剪枝。
一句话解释版本：
剪枝分为前剪枝与后剪枝，通过留出法在测试集上比对剪枝前后的效果来判定是否剪枝。
数据分析与挖掘体系位置
决策树是有监督学习中的一种模型。所以在数据分析与数据挖掘中的位置如下图所示。
剪枝的目的
对决策树进行剪枝的目的是为了防止过拟合（Overfitting）问题。
过拟合就是值学习器把样本学的太好了，把一些只属于训练集的特性也当作了一般性规律处理。在决策树中，过多的分支会使模型将一些个性化特征视为一般性特征，降低了泛化能力。因此就需要我们通过剪枝减少分支（自变量）个数。
剪枝的方法
剪枝的方法分为：预剪枝（pre-pruning）与后剪枝（post-pruning）。
预剪枝是在决策树生成的过程中剪枝。即，对每个结点在划分前估计，若当前结点的划分不能使决策树泛化性能提升，则停止划分，并将当前结点标记为叶结点。
后剪枝是在决策树生成完整后剪枝。即，先生成一个完整的决策树，然后从枝叶的最末端往树干方向逐一考察非叶结点，若将非叶结点对应的子树替换为叶结点能提升模型泛化能力，则在此剪枝，将子树替换为叶结点。
剪枝的步骤
一、留出法：划分样本
模型的泛化能力可以通过留出法验证，即将样本划分为互斥的样本训练集与样本测试集。在训练集上建立模型，在测试集上应用模型并评估预测结果的好坏。若通过剪枝，能够让决策树在测试集上的表现得到提升，就代表通过剪枝模型的泛化能力得以增强。
同样用4.3.1有监督学习（二） - 决策树（Decision Tree） - 构建树的核心指标 中的样本数据，我们总共17条数据中的10条作为训练集（Training Sample），7条作为测试集（Testing Sample）。
10条训练集数据中，分别有5条最终决策是“去玩”，5条是“不出去玩”。样本划分结果如下图所示：
二、构建树：信息增益/增益率/基尼系数
第二步，我们需要基于训练集的数据构建一棵完整的决策树。构建树的方法，可以是4.3.1有监督学习（二） - 决策树（Decision Tree） - 构建树的核心指标 中的任何一种。
这里，我们使用相对较为简单的信息增益计算出未剪枝的完整的树。
三、预剪枝
首先，我们来分析预剪枝。基于第二步计算出的信息增益，我们最先选取属性“双休日”划分训练集。预剪枝首先要评判这个划分是否需要。具体的评判标准如下：
划分之前，所有样本集中在根节点，证明我们没有做任何划分。那么，我们把所有类别标记为训练样例数最多的类别，把所有的决策都定义为：“去”。所以不论是否双休、是否加班、女友是否同意、天气如何，我们都会选择“去玩”。那么，把这种评定标准带入到测试集中，我们会发现，分对了3个，分错了4个。在测试集上的精度为：3/7 * 100% = 42.9%。
划分之后，也就是我们通过属性“双休日”对样本进行划分后，双休日为“是”的中有“去”占4/5，双休日为“否”的中有“去”占1/5，所以我们可以得到下面的划分图：
其中，双休日为“是”这条分支在测试集中全部预测正确，双休日为“否”这条分支在测试集中也全部预测正确。
所以，在划分后，精度由原先的42.9%上升为100%，那么代表这个分支是很有效的。我们肯定要保留此分支。
之后，我们要对下一级的分支重复此操作，其结果就是下图
所以，将在属性“双休日”后就对决策树进行剪枝。最终，剪枝后的树精度为100%。
但是，预剪枝存在的风险在于，由于剪枝是一层一层向下推进的，有些属性在一些属性的基础上才会有性能的提高，但是预剪枝不能考虑这些问题，有时候在开始就把整个枝都给剪掉了，这也可能会导致“欠拟合”问题。
四、后剪枝
后剪枝是从树的最末端开始往上判断。
首先，我们判断，一颗完整的树，其在测试集上的精度为多少？将测试样本带入模型后，我们发现7个测试样本中，5个预测对了，2个预测错了（BH：8与13）。所以，模型的精度为5/7 = 71.4%。
之后，后剪枝先考察最末端的分支，即“女朋友”属性，将这个分支删除后，“天气”属性为多云的结果判定为“去”（当样本两种结果几率一样时，任意选择一个）。此时，模型的精度下降为57.1%。因此后剪枝判定不剪枝。
但是，这里有个有趣的事实，因为样本量太少，在删除了“女朋友”属性后，“天气”=“多云”且“双休日”=“否”的样本只剩下两个，一个是去玩，一个是不去玩。这时，我们只能任意选其一作为叶结点的结果。如果，我们将“天气”属性为多云的结果判定为“不去”，那么，模型的精度反而会提升到85.7%，后剪枝会判定剪枝。
所以，这就反映出了样本足够大，以及样本抽取合理的重要性。
总体而言，后剪枝比前剪枝保留的分支可能更多一些，产生欠拟合的几率相对小一些，泛化能力也好于决策树。
剪枝的在Python与R中的实现
代码好长，不想放这里占地方，请去Github下载吧。
https://github.com/starsfell/decision_tree
参考资料：
【1】周志华：《机器学习》