决策树的优化-剪枝优化

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

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

后剪枝（post-pruning）：后剪枝就是先把整颗决策树构造完毕，然后⾃底向上的对⾮叶结点进⾏考察，若将该结点对应的⼦树换为叶结点能够带来泛化性能的提升，则把该⼦树替换为叶结点。

⼀、预剪枝（pre-pruning）

关于预剪枝（pre-pruning）的基本概念，在前⾯已经介绍过了，下⾯就直接举个例⼦来看看预剪枝（pre-pruning）是怎样操作的。数据集为（图⽚来⾃西⽠书）：

这个数据集根据信息增益可以构造出⼀颗未剪枝的决策树（图⽚来⾃西⽠书）：

下⾯来看下具体的构造过程：

前⾯博客（ ）讲过⽤信息增益怎么构造决策树，这边还是⽤信息增益构造决策树，先来计算出所有特征的信息增益值：

因为 ⾊泽和 脐部的信息增益值最⼤，所以从这两个中随机挑选⼀个，这⾥选择 脐部来对数据集进⾏划分，这会产⽣三个分⽀，如下图所⽰：

但是因为是预剪枝，所以要判断是否应该进⾏这个划分，判断的标准 就是看划分前后的泛华性能是否有提升，也就是如果划分后泛化性能有提升，则划分；否则，不划分。 下⾯来看看是否要⽤ 脐部进⾏划分， 划分前：所有样本都在根节点，把该结点标记为叶结点，其类别标记为训练集中样本数量最多的类别，因此标记为 好⽠，然后⽤验证集对其性能评估，可以看出样本{4，5，8}被正确分类，其他被错误分类，因此精度为43.9%。 划分后： 划分后的的决策树为：

则验证集在这颗决策树上的精度为：5/7 = 71.4% > 42.9%。因此，⽤ 脐部 进⾏划分。

接下来，决策树算法对结点 (2) 进⾏划分，再次使⽤信息增益挑选出值最⼤的那个特征，这⾥我就不算了，计算⽅法和上⾯类似，信息增益值最⼤的那个特征是“⾊泽”，则使⽤“⾊泽”划分后决策树为：

但到底该不该划分这个结点，还是要⽤验证集进⾏计算，可以看到划分后，精度为：5/7=0.571<0.714，因此，预剪枝策略将禁⽌划分结点(2) 。对于结点 (3) 最优的属性为“根蒂”，划分后验证集精度仍为71.4%，因此这个划分不能提升验证集精度，所以预剪枝将禁⽌结点 (3) 划分。对于结点 (4) ，其所含训练样本已属于同⼀类，所以不再进⾏划分。 所以基于预剪枝策略⽣成的最终的决策树为：

总结： 对⽐未剪枝的决策树和经过预剪枝的决策树可以看出：预剪枝使得决策树的很多分⽀都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但是，另⼀⽅⾯，因为预剪枝是基于“贪⼼”的，所以，虽然当前划分不能提升泛华性能，但是基于该划分的后续划分却有可能导致性能提升，因此预剪枝决策树有可能带来⽋拟合的风险。

⼆、后剪枝（post-pruning）

后剪枝就是先构造⼀颗完整的决策树，然后⾃底向上的对⾮叶结点进⾏考察，若将该结点对应的⼦树换为叶结点能够带来泛华性能的提升，则把该⼦树替换为叶结点。前⾯已经说过了，使⽤前⾯给出的训练集会⽣成⼀颗（未剪枝）决策树：

后剪枝算法⾸先考察上图中的结点 (6)，若将以其为根节点的⼦树删除，即相当于把结点 (6) 替换为叶结点，替换后的叶结点包括编号为{7,15}的训练样本，因此把该叶结点标记为“好⽠”（因为这⾥正负样本数量相等，所以随便标记⼀个类别），因此此时的决策树在验证集上的精度为57.1%（为剪枝的决策树为42.9%），所以后剪枝策略决定剪枝，剪枝后的决策树如下图所⽰：

接着考察结点 5，同样的操作，把以其为根节点的⼦树替换为叶结点，替换后的叶结点包含编号为{6,7,15}的训练样本，根据“多数原则”把该叶结点标记为“好⽠”，测试的决策树精度认仍为57.1%，所以不进⾏剪枝。

考察结点 2 ，和上述操作⼀样，不多说了，叶结点包含编号为{1,2,3,14}的训练样本，标记为“好⽠”，此时决策树在验证集上的精度为71.4%，因此，后剪枝策略决定剪枝。剪枝后的决策树为：

接着考察结点 3 ，同样的操作，剪枝后的决策树在验证集上的精度为71.4%，没有提升，因此不剪枝；对于结点 1 ，剪枝后的决策树的精度为42.9%，精度下降，因此也不剪枝。

因此，基于后剪枝策略⽣成的最终的决策树如上图所⽰，其在验证集上的精度为71.4%。

总结：对⽐预剪枝和后剪枝，能够发现，后剪枝决策树通常⽐预剪枝决策树保留了更多的分⽀，⼀般情形下，后剪枝决策树的⽋拟合风险⼩，泛化性能往往也要优于预剪枝决策树。但后剪枝过程是在构建完全决策树之后进⾏的，并且要⾃底向上的对树中的所有⾮叶结点进⾏逐⼀考察，因此其训练时间开销要⽐未剪枝决策树和预剪枝决策树都⼤得多。