目录
- 1. 简介
- 2. 预剪枝
- 3. 后剪枝
1. 简介
剪枝 (pruning)：决策树学习算法对付"过拟合"的主要手段
过拟合原因：为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得"太好"了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。
基本策略:
- 预剪枝：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
- 后剪枝：先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
以下表为例进行预剪枝和后剪枝：
图4.5是基于信息增益准则（见ML经典算法：决策树（1））生成的未剪枝决策树：
2. 预剪枝
基于信息增益准则（见ML经典算法：决策树（1）），选取属性"脐部"来对训练集进行划分，并产生 3 个分支
类别标记为训练样例数最多的类别，
若不以脐部进行划分：则脐部标记为"好瓜”，用表 4.2 的验证集对这个单结点决策树进行评估，编号为 {4 ， 5 ， 8} 的样例被分类正确，准确率为42.9%
以脐部进行划分：用属性"脐部"划分之后，图 4.6 中的结点②、③、④分别被标记为叶结点"好瓜"、 “好瓜”、 “坏瓜”。验证集中编号为{4 ， 5 ， 8 ，1l， 12} 的样例被分类正确，验证集精度为71.4%
于是，用"脐部"进行划分得以确定。以此类推进行构建决策树。
对比图 4.6 和图 4.5可看出，预剪枝使得决策树的很多分支都没有"展开”。不仅降低了过拟合的风险还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降?但在其基础上进行的后续划分却有可能导致性能显著提高；预剪枝基于"贪心"本质禁止这些分支展开给预剪枝决策树带来欠拟含的风险。
3. 后剪枝
后剪枝先从训练集生成一棵完整决策树，例如基于表 4.2 的数据我们得到如图 4.5 所示的决策树，该决策树的验证集精度为 42.9%。
后剪枝首先考察图 4.5 中的结点⑥.若将其领衔的分支剪除，则相当于把⑤替换为叶结点.替换后的叶结点包含编号为 {7 ， 15} 的训练样本，于是该叶结点的类别标记为"好瓜"，此时决策树的验证集精度提高至 57.1%. 于是，后剪枝策略决定剪枝，若未提高，则不进行剪枝。以此类推进行后剪枝操作。
预剪枝与后剪枝比较：
后剪枝决策树通常比预剪枝决策树保留 了更多的分支 。后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的并且要白底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。