决策树的英剪枝理论.docxVIP

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