文档介绍：决策树剪枝算法目录CONTENTS1234先剪枝错误率降低剪枝悲观剪枝代价复杂度剪枝在有些时候,一棵经过训练的决策树过于“繁茂”,知识过多,或者说得到的规则集合过大。经过剪枝,可以得到一棵相对简洁的决策树,较少的规则使得在进行分类预测时,决策树效率更高。同时,剪枝也可以减少过拟合现象的发生。??先剪枝通过提前停止树的构建而对树剪枝,一旦停止,节点就是树叶,该树叶持有子集元祖最频繁的类。停止决策树生长最简单的方法有:,,即使这些实例不属于同一类,也可以停止决策树的生长。,当达到某个节点的实例个数小于阈值时就可以停止决策树的生长。或定义一个阈值,通过计算每次扩张对系统性能的增益,并比较增益值与该阈值大小来决定是否停止决策树的生长。不足:阈值不好设置,过大决策树过于简单;过小,有多余树枝,过于茂盛。后剪枝方法后剪枝(postpruning):它首先构造完整的决策树,允许树过度拟合训练数据,然后对那些置信度不够的节点子树用叶子节点来代替,该叶子的类标号用该节点子树中最频繁的类标记。相比于先剪枝,这种方法更常用,正是因为在先剪枝方法中精确地估计何时停止树增长很困难。后剪枝方法主要有以下几个方法:Reduced-ErrorPruning(REP,错误率降低剪枝)Pesimistic-ErrorPruning(PEP,悲观错误剪枝)P,代价复杂度剪枝)REP错误率降低剪枝REP方法是一种比较简单的后剪枝的方法,在该方法中,可用的数据被分成两个样例集合:一个训练集用来生成决策树,一个分离的验证集用来评估这个决策树在后续数据上的精度,确切地说是用来评估修剪这个决策树的影响。这个方法的动机是:即使学****器可能会被训练集中的随机错误和巧合规律所误导,但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验。该剪枝方法考虑将树上的每个节点作为修剪的候选对象,决定是否修剪这个结点,步骤如下。REP错误率降低剪枝1)删除以此结点为根的子树2)使其成为叶子节点3)赋予该节点关联的训练数据的最常见分类4)当修剪后的树对于验证集合的性能不会比原来的树差时,才真正删除该结点5)算法终止的条件:以bootom-up方式遍历所有的子树,直到没有任何子树可以替换使得测试数据集的表现得以改进。因为训练集合的过拟合,使得验证集合数据能够对其进行修正,反复进行上面的操作,从底向上的处理节点,删除那些能够最大限度的提高验证集合精度的节点,直到进一步修剪有害为止(有害是指修剪会减低验证集合的精度)。REP错误率降低剪枝REP是最简单的后剪枝方法之一,不过由于使用独立的测试集,原始决策树相比,修改后的决策树可能偏向于过度修剪。尽管REP有这个缺点,不过REP仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学****方法的优点和缺点提供了一个很好的学****思路。由于验证集合没有参与决策树的创建,所以用REP剪枝后的决策树对于测试样例的偏差要好很多,能够解决一定程度的过拟合问题。PEP悲观错误剪枝悲观错误剪枝法是根据剪枝前后的错误率来判定子树的修剪。该方法引入了统计学上连续修正的概念弥补REP中的缺陷,在评价子树的训练错误公式中添加了一个常数,假定每个叶子结点都自动对实例的某个部分进行错误的分类。把一棵子树(具有多个叶子节点)的分类用一个叶子节点来替代的话,在训练集上的误判率肯定是上升的,但是在新数据上不一定。于是我们需要把子树的误判计算加上一个经验性的惩罚因子。