模型算法基础——决策树剪枝算法（二）

在上一篇模型算法基础——决策树剪枝算法（一）中，我们介绍了误差降低剪枝(REP)，今天我们继续介绍另一种后剪枝算法—— 悲观错误剪枝(PessimisticError Pruning/PEP) 。

悲观错误剪枝也是根据剪枝前后的错误率来决定是否剪枝，和REP不同的是，PEP不需要使用验证样本，并且PEP是 自上而下 剪枝的。由于还是用生成决策树时相同的训练样本，那么对于每个节点，剪枝后错分率一定是会上升的，因此在计算错分率时需要加上一个经验性的惩罚因子1/2。假设T表示考虑是否剪枝的某节点，t表示该节点下的叶子节点，N(t)表示节点t覆盖的样本个数，e(t)表示节点t的错分样本个数，那么节点T的错分率：

也就是说，每一个样本有E(Tt)的概率分类正确，1- E(Tt)的概率分类错误。可以认为错分次数服从Bernoulli分布，其期望为：

标准差为：

如果对T进行剪枝，当T节点成为叶子节点后的错分率：

如果有

则认为该节点需要剪枝。

还是用REP中训练样本的栗子，我们考虑T4节点（假设母节点们都不需要剪枝）：

由于6+2.05>7，因此根据PEP判断节点T4需要剪枝。

悲观错误剪枝的准确度较高，且不需要分离训练样本和验证样本，对样本量较少的情况比较有利。同时，每棵子树最多只需要访问一次，效率较高。但是由于方向是自上而下，可能会造成某些不必要的剪枝。