决策树剪枝

决策树的剪枝

完整的决策树并不是一棵分类预测新数据对象的最佳树。其原因是完整的决策树对Training Data描述过于“精确”。我们知道，随着决策树的生长，决策树分枝时所处理的样本数量在不断减少，决策树对数据总体珠代表程度在不断下降。在对根节点进行分枝时，处理的是全部样本，再往下分枝，则是处理的不同分组下的分组下的样本。可见随着决策树的生长和样本数量的不断减少，越深层处的节点所体现的数据特征就越个性化，可能出现如上推理规则：“年收入大于50000元且年龄大于50岁且姓名叫张三的人购买了此产品”。这种过度学习从而精确反映Training Data特征，失去一般代表性而无法应用于新数据分类预测的现象，叫过度拟合（Overfitting）或过度学习。那我们应该怎么办呢？修剪！

剪枝方法

常用的修剪技术有预修剪（Pre-Pruning）和后修剪（Post-Pruning）。
Pre-Pruning可以事先指定决策树的最大深度，或最小样本量，以防止决策树过度生长。前提是用户对变量聚会有较为清晰的把握，且要反复尝试调整，否则无法给出一个合理值。注意，决策树生长过深无法预测新数据，生长过浅亦无法预测新数据。
Post-pruning是一个边修剪边检验的过程，即在决策树充分生长的基础上，设定一个允许的最大错误率，然后一边修剪子树，一边计算输出结果的精度或误差。当错误率高于最大值后，立即停止剪枝。

剪枝思路

使用训练集合(Training Set）和验证集合(Validation Set)，来评估剪枝方法在修剪结点上的效用
使用所有的训练集合进行训练，但是用统计测试来估计修剪特定结点是否会改善训练集合外的数据的评估性能，如使用Chi-Square（Quinlan，1986）测试来进一步扩展结点是否能改善整个分类数据的性能，还是仅仅改善了当前训练集合数据上的性能。
使用明确的标准来衡量训练样例和决策树的复杂度，当编码长度最小时，停止树增长，如MDL(Minimum Description Length)准则。

Reduced-Error Pruning(REP,错误率降低剪枝）

该剪枝方法考虑将书上的每个节点作为修剪的候选对象，决定是否修剪这个结点有如下步骤组成：

删除以此结点为根的子树
使其成为叶子结点
赋予该结点关联的训练数据的最常见分类
当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点。

因为训练集合的过拟合，使得验证集合数据能够对其进行修正，反复进行上面的操作，从底向上的处理结点，删除那些能够最大限度的提高验证集合的精度的结点，直到进一步修剪有害为止(有害是指修剪会减低验证集合的精度)

REP是最简单的后剪枝方法之一，不过在数据量比较少的情况下，REP方法趋于过拟合而较少使用。这是因为训练数据集合中的特性在剪枝过程中被忽略，所以在验证数据集合比训练数据集合小的多时，要注意这个问题。

尽管REP有这个缺点，不过REP仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学习方法的优点和缺点提供了了一个很好的学习思路。由于验证集合没有参与决策树的创建，所以用REP剪枝后的决策树对于测试样例的偏差要好很多，能够解决一定程度的过拟合问题。

Pessimistic Error Pruning(PEP，悲观剪枝）

先计算规则在它应用的训练样例上的精度，然后假定此估计精度为二项式分布，并计算它的标准差。对于给定的置信区间，采用下界估计作为规则性能的度量。这样做的结果，是对于大的数据集合，该剪枝策略能够非常接近观察精度，随着数据集合的减小，离观察精度越来越远。该剪枝方法尽管不是统计有效的，但是在实践中有效。
PEP为了提高对测试集合的预测可靠性，PEP对误差估计增加了连续性校正(Continuity Correction)。PEP方法认为，如果： $e^{'}(t)\le e^{'}(T_t)+S_e(e^{'}(T_t))$ 成立，则 $T_t$ 应该被剪枝。
上式中： $e^{'}=[e(t)+\frac{1}{2}];e^{'}(T_t)=\sum e(i)+\frac{N_t}{2}$ .
其中， $e(t)$ 为结点t的误差，i为覆盖 $T_t$ 的结点， $N_t$ 为子树 $T_t$ 的叶子树， $n(t)$ 为在结点t处的训练集合数量。用自顶向下的方式，如果某个非叶子结点符合上面的不等式，就裁剪掉该叶子结点。该算法被认为是当前决策树后剪枝算法中经度比较高的算法之一，但是饿存在有缺陷。首先，PEP算法是唯一使用Top-Down剪枝策略，这种策略会导致与先剪枝出现同样的问题，将该结点的某子节点不需要被剪枝时被剪掉；另外PEP方法会有剪枝失败的情况出现。

虽然PEP方法存在一些局限性，但是在实际应用中表现出了较高的精度,。两外PEP方法不需要分离训练集合和验证机和，对于数据量比较少的情况比较有利。再者其剪枝策略比其它方法相比效率更高，速度更快。因为在剪枝过程中，树中的每颗子树最多需要访问一次，在最坏的情况下，它的计算时间复杂度也只和非剪枝树的非叶子节点数目成线性关系。

Cost-Complexity Pruning(CCP、代价复杂度)

CCP方法包含两个步骤：

从原始决策树T0开始生成一个子树序列{T0、T1、T2、…、Tn},其中Ti+1是从Ti总产生，Tn为根节点
从子树序列中，根据树的真实误差估计选择最佳决策树。
在步骤一中，生成子树序列 $T_0,T_1,T_2,...,T_n$ 的基本思想是从 $T_0$ 开始，裁剪 $T_i$ 中关于训练数据集合误差增加最小的分支来得到 $T_{i+1}$ 。实际上当一棵树T在结点t出剪枝时，它的误差增加直观上认为是: $R(t)-R(T_t)$ ,其中 $R(t)$ 为在结点t的子树被裁剪后结点t的误差， $R(T_t)$ 为在结点t的子树没被裁剪时子树T的误差。不过剪枝后T的叶子树减少了 $|L(T_i)|-1$ ，其中 $|L(T_i)|$ 为子树Ti的叶子树，也就是说T的复杂性降低。因此考虑到树的复杂性因素，树分支被裁剪后误差增加率可以由下式决定：

$\alpha=\frac{R(t)-R(T_t)}{|L(T_i)|-1}$

$T_{i+1}$ 就是选择 $T_i$ 中具有最小 $\alpha$ 值所对应的剪枝树.

如何从第一步骤产生的子树序列 $T_0,T_1,T_2,...,T_n$ 中选择出最佳决策树是CCP方法的第二步骤的关键。通常可以采用V-交叉验证(V-fold Cross-Validation)和基于独立剪枝数据集两种方法，这两种方法可以参考(Classification And Regression Trees,Breiman et.al)。当使用基于独立数据集剪枝时，和REP方法相比，CCP选择出来的最有决策树，不是从原始决策树T的所有可能子树中得到，所以有可能会找到到最有决策树。

参考资料

决策树：C5.0（一）

数据挖掘十大经典算法–CART: 分类与回归树

Decision Tree：CART、剪枝

大放悲声

展开全文

阅读 1+

评论 0+