决策树剪枝ppt课件.pptx

《决策树剪枝ppt课件.pptx》由会员分享，可在线阅读，更多相关《决策树剪枝ppt课件.pptx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、决策树剪枝算法目 录CONTENTS1234先剪枝错误率降低剪枝悲观剪枝代价复杂度剪枝在有些时候，一棵经过训练的决策树过于“繁茂”，知识过多，或者说得到的规则集合过大。经过剪枝，可以得到一棵相对简洁的决策树，较少的规则使得在进行分类预测时，决策树效率更高。同时，剪枝也可以减少过拟合过拟合现象的发生。为什么需要剪枝为什么需要剪枝1.怎么剪？2.剪枝后效果如何？先剪枝先剪枝通过提前停止树的构建而对树剪枝，一旦停止，节点就是树叶，该树叶持有子集元祖最频繁的类。停止决策树生长最简单的方法有：1.定义一个高度，当决策树达到该高度时就停止决策树的生长2.达到某个节点的实例具有相同的特征向量，即使这些实例不

2、属于同一类，也可以停止决策树的生长。3.定义一个阈值，当达到某个节点的实例个数小于阈值时就可以停止决策树的生长。或定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值或定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值大小来决定是否停止决策树的生长。与该阈值大小来决定是否停止决策树的生长。不足：阈值不好设置，过大决策树过于简单；过小，有多余树枝，过于茂盛。后剪枝方法后剪枝方法后剪枝（postpruning）：它首先构造完整的决策树，允许树过度拟合训练数据，然后对那些置信度不够的节点子树用叶子节点来代替，该叶子的类标号用该节点子树中最频繁的类标记。相比于先剪枝，这种方法

3、更常用，正是因为在先剪枝方法中精确地估计何时停止树增长很困难。后剪枝方法主要有以下几个方法：Reduced-Error Pruning (REP,错误率降低剪枝)Pesimistic-Error Pruning (PEP,悲观错误剪枝)Cost-Complexity Pruning (CCP,代价复杂度剪枝)REP 错误率降低剪枝错误率降低剪枝REP方法是一种比较简单的后剪枝的方法，在该方法中，可用的数据被分成两个样例集合：一个训练集训练集用来生成决策树，一个分离的验证集验证集用来评估这个决策树在后续数据上的精度，确切地说是用来评估修剪这个决策树的影响。这个方法的动机是：即使学习器可能会被训练

4、集中的随机错误和巧合规律所误导，但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验。该剪枝方法考虑将树上的每个节点作为修剪的候选对象，决定是否修剪这个结点，步骤如下。REP 错误率降低剪枝错误率降低剪枝1）删除以此结点为根的子树2）使其成为叶子节点3）赋予该节点关联的训练数据的最常见分类4）当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点5)算法终止的条件：以bootom-up方式遍历所有的子树，直到没有任何子树可以替换使得测试数据集的表现得以改进。因为训练集合的过拟合，使得验证集合数据能够对其进行修正，反复进行上面的操作，从底

5、向上的处理节点，删除那些能够最大限度的提高验证集合精度的节点，直到进一步修剪有害为止(有害是指修剪会减低验证集合的精度)。REP 错误率降低剪枝错误率降低剪枝REP是最简单的后剪枝方法之一，不过由于使用独立的测试集，原始决策树相比，修改后的决策树可能偏向于过度修剪。尽管REP有这个缺点，不过REP仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学习方法的优点和缺点提供了一个很好的学习思路。由于验证集合没有参与决策树的创建，所以用REP剪枝后的决策树对于测试样例的偏差要好很多，能够解决一定程度的过拟合问题。PEP 悲观错误剪枝悲观错误剪枝悲观错误剪枝法是根据剪枝前后的错误率来判定子树

6、的修剪。该方法引入了统计学上连续修正的概念弥补REP中的缺陷，在评价子树的训练错误公式中添加了一个常数，假定每个叶子结点都自动对实例的某个部分进行错误的分类。把一棵子树（具有多个叶子节点）的分类用一个叶子节点来替代的话，在训练集上的误判率肯定是上升的，但是在新数据上不一定。于是我们需要把子树的误判计算加上一个经验性的惩罚因子。PEP 悲观错误剪枝悲观错误剪枝PEP 悲观错误剪枝悲观错误剪枝PEP 悲观错误剪枝悲观错误剪枝PEP 悲观错误剪枝悲观错误剪枝那么，如果子树可以被叶子节点替代，它必须满足下面的条件：这个条件就是剪枝的标准。根据置信区间，我们设定一定的显著性因子，我们可以估算出误判次数的

7、上下界。PEP 悲观错误剪枝悲观错误剪枝PEP 悲观错误剪枝悲观错误剪枝PEP采用自顶向下的方式，如果某个非叶子结点符合上面的不等式，就裁剪掉该叶子结点。该算法被认为是当前决策树后剪枝算法中精度比较高的算法之一，但是也存在缺陷。首先，PEP算法是唯一使用Top-Down剪枝策略，这种策略会导致与先剪枝出现同样的问题，将该结点的某子节点不需要被剪枝时被剪掉；另外PEP方法会有剪枝失败的情况出现。PEP 悲观错误剪枝悲观错误剪枝虽然PEP方法存在一些局限性，但是在实际应用中表现出了较高的精度。另外PEP方法不需要分离训练集合和验证集，对于数据量比较少的情况比较有利。其剪枝策略比其它方法相比效率更高

8、，速度更快。因为在剪枝过程中，树中的每棵子树最多需要访问一次，在最坏的情况下，它的计算时间复杂度也只和非剪枝树的非叶子节点数目成线性关系。CCP 代价复杂度剪枝代价复杂度剪枝CCP 代价复杂度剪枝代价复杂度剪枝CCP 剪枝时，选择“表面误差率增益值表面误差率增益值“最小最小的非叶子节点，删除该非叶子节点的左右子节点。若有多个非叶子节点的表面误差率增益值相同小，则选择子节点数最多的非叶子节点进行剪枝。CCP 代价复杂度剪枝代价复杂度剪枝CCP 代价复杂度剪枝代价复杂度剪枝该算法为子树Tt定义了代价（cost）和复杂度（complexity），以及一个可由用户设置的衡量代价与复杂度之间关系的参数参

9、数，其中，代价指在剪枝过程中因子树Tt被叶节点替代而增加的错分样本，复杂度表示剪枝后子树Tt减少的叶结点数，则表示剪枝后树的复杂度降低程度与代价间的关系，定义为:CCP 代价复杂度剪枝代价复杂度剪枝例如找到值最小的非叶子节点，令其左右孩子为NULL。当多个非叶子节点值同时达到最小时，取 较大的进行剪枝剪枝算法比较REPPEPCCP剪枝方式自底向上自顶向下自底向上独立剪枝集需要-计算复杂度O(n)O(n)O(n)误差估计剪枝集上误差估计使用连续纠正标准误差PPT模板下载： 行业PPT模板： 节日PPT模板： PPT素材下载： PPT图表下载： 优秀PPT下载： PPT教程： Word教程： Excel教程： 资料下载： PPT课件下载： 范文下载： 试卷下载： 教案下载： PPT论坛： 谢谢