【十分钟 机器学习 系列课程】 讲义（二十四）：决策树的后剪枝MEP

欢迎回来。上篇讲义我们开启了「决策树」中的「后剪枝」的篇章。

后剪枝的概念是指对已经生成的决策树进行剪枝，常见的方法有：

❝

• 降低错误剪枝 Reduce Error Pruning
• 悲观错误剪枝 Pessimistic Error Pruning
• 最小误差剪枝 Minimum Error Pruning
• 基于错误的剪枝 Error Based Pruning
• 代价复杂度剪枝 Cost-Complexity Pruning

❞

上篇我们讲了前两种方法【十分钟 机器学习 系列课程】 讲义（二十三）：决策树的后剪枝-REP和PEP，今天继续讲解第三种方法-「最小误差剪枝MEP的方法」。

壹 最小误差剪枝MEP-算法说明

「原理」：根据剪枝前后的最小分类错误来决定是否剪枝。

「特点」：自下而上剪枝，只需要训练集即可。

在结点 处，计算出属于类别 的概率

那么这个概率怎么计算呢？常规的计算就是在结点 处将属于类别 的个数比上总样本个数 ，也就是 ，但是现在我们要将先验概率考虑进来，也就是贝叶斯思维，需要复习这个知识点的小伙伴可以点击链接回顾一下哦。【十分钟  机器学习  系列课程】讲义（十六）：朴素贝叶斯法 【十分钟 机器学习 系列课程】 讲义（十八）：贝叶斯估计

先验的单词是prior，那么这里的 「 就是在结点 出类别 的先验概率」，那么 又是什么呢？「 是指先验概率对后验概率的影响」。

❝

• 如果 ， 意味着以后验概率为准。
• 如果 ， 意味着以先验概率为准。

❞

在结点 处，计算出预测错误率

如果我们将结点 记为类别 ，那么预测错误率自然就是不属于类 的啦，今天我们讲的这个方法叫做「最小误差剪枝」，顾名思义，就是求最小的预测错误率啦。

接着把上面的概率式子 代入到预测错误率中， 也就是要求出：

如果先验概率是确定的，那么就是以 作为变量，得到对应的预测错误率的最小值。

❝

• 注意：这里的 是需要计算选择出来的哦，而不是给定的。我们可以通过

  选出合适的 。

❞

在这里,为了演示MEP的算法，我们假设 ， 是指类别的总个数，

一般，在无任何假设的情况下，我们通常假设各类别是等概率出现的，因此，先验概率为 。

这样，我们的预测错误率就可以写作

贰 最小误差剪枝MEP-步骤讲解

首先咱们先用两步走计算剪枝前的预测错误率。

Step 1 计算剪枝前目标子树每个叶子结点的预测错误率

代表在叶子结点处样本的个数， 代表在叶子结点 处属于第 类的样本个数。

Step2 计算剪枝前目标子树的预测错误率

假如目标子树中一共有 个叶子结点

这里的 就是指每个叶子结点对应目标子树的权重。

接着咱们就来计算剪枝后的错误率，并且来比较剪枝前后的预测错误率，「如果剪枝后错误率降低了，那么就意味着可以剪枝」，反之就不可以哦。

Step3 计算剪枝后目标子树的预测错误率

这里就是将整个子树 判定为类 ，计算出对应的预测错误率。

Step4 比较剪枝前后的预测错误率，如果满足以下不等式，则剪枝；否则，不剪枝

叁 最小误差剪枝MEP-例题计算

咱们还是用上篇悲观错误剪枝中的例子来看看。

这里T4~T8分别代表了叶子结点。+号代表「正类样本」，-号代表「负类样本」，个数就是对应的数字哦。接着可以看到3个矩形叶子结点，分别是T6、T7、T8。

绿色表示正类，红色表示负类。

现在我们就要「用最小误差剪枝方法判断在T5这棵子树处是否需要剪枝」，那么就开始吧！

1、计算剪枝前目标子树每个叶子结点的预测错误率

我们看到T5这棵子树有T7和T8两个叶子结点，那么咱们就分别计算一下预测误差率吧！

T7这个叶子结点的样本总是为 ，一共分为了正类和负类，意味着 ,那么就可以知道 啦。这里由于T7属于正类，其中2个不属于正类。那么分子就等于负类的个数加上1。

同理可以求出T8的预测错误率，这里注意哦，由于这个叶子属性是负类，这里分子就以正类的个数来计算。

2、计算剪枝前目标子树的预测错误率

接着我们计算出T7和T8的权重，分别「就是它们在子树T5中的个数占比」，然后乘以各自结点的预测错误率后求和，就算出T5这棵目标子树的预测错误率啦。

3、计算剪枝后目标子树的预测错误率

可以看出T5这个叶子结点中，有10个正类，10个负类，那咱们不妨就把它认为是正类。接着就可以来计算预测错误率啦。

4 比较剪枝前后的预测错误率

咱们可以看出剪枝前的误差率 明显小于剪枝后的 ，说明剪枝后的误差率反而提高了，那就得出了「不能剪枝」的结论。

好啦，今天的分享就到此，下篇我们将继续分享剩余2种后剪枝方法，咱们下期不见不散，感兴趣的朋友可以点击视频链接继续学习哦~