文档介绍：决策树的剪枝理论 (2013-11-1916:39:21)转载▼标签: 数据挖掘 决策树 剪枝 it分类: 数据挖掘剪枝理论,决策树的剪枝在上一节中没有仔细讲,趁这个机会学****了剪枝的基础理论,这里会详细学****决策树为什么(WHY)要剪枝?原因是避免决策树过拟合(Overfitting)样本。前面的算法生成的决策树非常详细并且庞大,每个属性都被详细地加以考虑,决策树的树叶节点所覆盖的训练样本都是“纯”的。因此用这个决策树来对训练样本进行分类的话,你会发现对于训练样本而言,这个树表现完好,误差率极低且能够正确得对训练样本集中的样本进行分类。训练样本中的错误数据也会被决策树学****成为决策树的部分,但是对于测试数据的表现就没有想象的那么好,或者极差,这就是所谓的过拟合(Overfitting)问题。Quinlan教授试验,在数据集中,过拟合的决策树的错误率比经过简化的决策树的错误率要高。 现在问题就在于,如何(HOW)在原生的过拟合决策树的基础上,生成简化版的决策树?可以通过剪枝的方法来简化过拟合的决策树。剪枝可以分为两种:预剪枝(Pre-Pruning)和后剪枝(Post-Pruning),下面我们来详细学****下这两种方法:PrePrune:预剪枝,及早的停止树增长,方法可以参考见上面树停止增长的方法。PostPrune:后剪枝,在已生成过拟合决策树上进行剪枝,可以得到简化版的剪枝决策树。其实剪枝的准则是如何确定决策树的规模,可以参考的剪枝思路有以下几个:1:使用训练集合(TrainingSet)和验证集合(ValidationSet),来评估剪枝方法在修剪结点上的效用2:使用所有的训练集合进行训练,但是用统计测试来估计修剪特定结点是否会改善训练集合外的数据的评估性能,如使用Chi-Square(Quinlan,1986)测试来进一步扩展结点是否能改善整个分类数据的性能,还是仅仅改善了当前训练集合数据上的性能。3:使用明确的标准来衡量训练样例和决策树的复杂度,当编码长度最小时,停止树增长,如MDL(MinimumDescriptionLength)准则。 我们先看下使用思路一来解决问题的集中后剪枝方法:Reduced-ErrorPruning(REP,错误率降低剪枝)该剪枝方法考虑将书上的每个节点作为修剪的候选对象,决定是否修剪这个结点有如下步骤组成:1:删除以此结点为根的子树2:使其成为叶子结点3:赋予该结点关联的训练数据的最常见分类4:当修剪后的树对于验证集合的性能不会比原来的树差时,才真正删除该结点因为训练集合的过拟合,使得验证集合数据能够对其进行修正,反复进行上面的操作,从底向上的处理结点,删除那些能够最大限度的提高验证集合的精度的结点,直到进一步修剪有害为止(有害是指修剪会减低验证集合的精度)REP是最简单的后剪枝方法之一,不过在数据量比较少的情况下,REP方法趋于过拟合而较少使用。这是因为训练数据集合中的特性在剪枝过程中被忽略,所以在验证数据集合比训练数据集合小的多时,要注意这个问题。尽管REP有这个缺点,不过REP仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学****方法的优点和缺点提供了了一个很好的学****思路。由于验证集合没有参与决策树的创建,所以用REP剪枝后的决策树对于测试样例的偏差要好很多,能够解决一定程度的过拟合问题。 PessimisticErrorPruning(PEP,悲观剪枝)先计算规则在它应用的训练样例上的精度,然后假定此估计精度为二项式分布,并计算它的标准差。对于给定的置信区间,采用下界估计作为规则性能的度量。这样做的结果,是对于大的数据集合,该剪枝策略能够非常接近观察精度,随着数据集合的减小,离观察精度越来越远。该剪枝方法尽管不是统计有效的,但是在实践中有效。PEP为了提高对测试集合的预测可靠性,PEP对误差估计增加了连续性校正(ContinuityCorrection)。PEP方法认为,如果: 成立,则Tt应该被剪枝,上式中: 其中,e(t)为结点t出的误差;i为覆盖Tt的叶子结点;Nt为子树Tt的叶子树;n(t)为在结点t处的训练集合数量。PEP采用自顶向下的方式,如果某个非叶子结点符合上面的不等式