机器学习算法之决策树（二）

标题：

剪枝的基本概念

留出法

预剪枝

后剪枝

我们知道，单纯的不做处理的决策树容易产生过拟合的现象，毕竟决策树的算法决定了它对每一个特征都要进行处理，为了减少这种现象的发生，新的决策树算法便引入了“剪枝”操作。

1.剪枝的基本概念

剪枝(pruning)是决策树算法对付“过拟合”的主要手段。

剪枝的基本策略有两个，一个是预剪枝(prepruning)，一个是后剪枝(postpruning)。

预剪枝是指在决策树生成过程中，在每个节点划分前先对这个节点做一个估计，判断这个节点的划分是否能够带来决策树泛化性能的提升，然后根据结果判断是否要划分节点。

后剪枝则是先从训练集生成一棵完整的树，然后自下而上地对非叶节点进行考察，判断若将该节点替换为叶节点能否带来决策树泛化性能的提升。

2.留出法

那么在学习剪枝之前，我们就还需要先知道如何判断决策树的泛化性能。这里我们介绍一个方法，留出法：即预留一部分数据作为“验证集”以进行性能评估，实际上，我们在实际任务中进行机器学习的时候，往往都需要将数据集分为三个部分而不是我们最开始介绍的两个部分，因为事实上除了训练集和测试集外，我们还会有一个验证集供我们测试模型的性能并在上面进行调参，部分读者可能会感到奇怪，就是为什么不通过测试集来进行调参，这是因为如果我们根据测试集调参，那么本质上也是将模型“为了测试集”而调整，测试集对模型而言就不单纯只是一个用来测试性能的数据集，而是有目的指向性的，这不符合我们对泛化性能的期望，但另一方面，如果我们不在验证集上将模型参数调至最优，似乎又不会期望它在测试集上的表现（在验证集都表现不佳，那自然就又不会觉得模型在测试集反而能“超水平发挥”），这确实是一个相较而言充满矛盾的点，但我们并没有堪称“完美”的行为方案，因此在现实任务中，我们或许也仅能是不断进行尝试了。

现在让我们回到留出法的介绍，对于我们之前所举的西瓜例子，我们用留出法可以将它化为下面两个部分（上部分为训练集，下部分为验证集）：

假定我们采用信息增益准则来划分属性，生成了下面这样的一棵决策树（为了便于讨论，图中的部分加了编号）：

这是一棵基于上表生成的未剪枝决策树，接下来我们将讨论如何在这棵决策树上利用泛化性能评估来进行剪枝。

3. 预剪枝

前面说过，预剪枝是指在决策树生成过程中，在每个节点划分前先对这个节点做一个估计，判断这个节点的划分是否能够带来决策树泛化性能的提升，然后根据结果判断是否要划分节点。那么基于信息增益准则，我将们优先选取“脐部”来对训练集进行划分，划分完成后，它会产生3个分支，如图：

为了判断我们是否有必要进行这个划分，我们就需要来对它划分前后的泛化性能进行估计：

首先我们假设我们没有进行划分，然后将该节点标记为叶节点，这个叶节点的类别为父节点中训练样本数最多的类别（在本例中即为根节点中样本最多的类别，若两者相同则随机取其一，这里我们假设是“好瓜”）

接着我们用验证集来对这个单节点决策树进行评估（在本例中，我们得到，编号的样本分类正确，另外4个样本分类错误，因此验证集精度为3/7*100%=42.9%）

然后我们再用选定的属性对节点进行划分，并将划分出来的节点按照其包含最多的类别划分为叶节点（这里就是用“脐部属性”对训练样本进行划分，得到图中节点编号2，3，4分别包含训练样本，，并且这三个节点还被分别标记为叶节点“好瓜”，“好瓜”，“坏瓜”）

代入验证集，检查划分后的验证精度。（在例子中得到验证集中编号为的样本被分类正确，验证集精度5/7∗100%=71.4%>42.9%）

得出结果，判断是否划分（决定用脐部对节点进行划分

重复这个过程，我们再对图中编号为2的节点进行划分，先基于信息增益准则挑出属性“色泽”。然而，在使用“色泽”划分后，编号为{5}的验证集样本分类结果会由正确转为错误，导致验证集精度下降为57.1%，于是，我们不对图中编号为2的节点进行划分。

对图中编号为4的节点，由于其所含样例已属于同一类，不再进行划分。

于是，我们可以生成如图所示的决策树：

（没错，和上面那幅就是一样的）

该决策树的验证精度为71.4%，这种仅有一层划分的决策树我们成为决策树桩(decision stump)

对比仅根据信息准则划分和加入了预剪枝划分的决策树示意图，我们可以看出，预剪枝让决策树的很多分支没有展开。这不仅降低了过拟合的风险，而且还能显著减少决策树的训练时间开销和测试时间开销。

但另一方面，有些分支的当前划分或许不能提升甚至降低泛化性能，但在其基础上进行的后续划分却也有可能提高泛化性能。预剪枝基于贪心本质将这些分支禁止展开，会给决策树带来欠拟合的风险。为了解决这个问题，我们就需要引入后剪枝。

4.后剪枝

后剪枝先从训练集中生成一棵完整的决策树，例如下面基于训练集表根据信息增益准则生成的决策树表，并且，我们还可以知道，该决策树的验证集精度为42.9%。

对这个已经生成的决策树应用后剪枝，我们会先考察图中的节点6：

首先我们将其替换为叶节点，然后根据给节点中的集合所包含的训练样本决定该叶节点的类别（本例中替换后的叶节点包含编号，因此类别为“好瓜”）

计算替换叶节点后的验证精度（本例中为57.1%），与未替换前（42.9%）做对比，决定是否剪枝。（本例中我们发现精度提高，于是进行剪枝）

然后我们再用同样的流程考察节点5，我们发现，替换前与替换后的精度都是57.1%，于是我们决定不剪枝。（这是书中例子的做法，但事实上，根据奥卡姆剃刀准则（“如无必要，勿增实体”），剪枝后的模型会更好，书中例子这样做仅是为了绘图方便，因而采取不剪枝的保守做法）

接着，我们再考察节点2，发现剪枝后精度提升到71.4%，遂进行剪枝。

对节点3和节点1，计算求得的精度分别为71.4%和42.9%，均未提高，于是将其保留。

最后，我们得到剪枝后的决策树：

该决策树的验证精度为71.4%。

将该图与预剪枝后的决策树示意图进行对比（然而实际上我们若应用奥卡姆剃刀准则，两幅图应该是一样的），后剪枝决策树通常比预剪枝保留了更多的分支。并且，一般情况下，后剪枝决策树欠拟合的风险很小，泛化性能也往往优于预剪枝的决策树。然而，后剪枝过程是在完全生成决策树之后才进行的，并且还要自底向上地对树中的所有非节点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大的多。

资料参考来源：

清华大学出版社-周志华《机器学习》

AI遇见机器学习

mltoai