决策树剪枝

决策树剪枝算法目录CONTENTS1234先剪枝错误率降低剪枝悲观剪枝代价复杂度剪枝在有些时候，一棵经过训练的决策树过于“繁茂”，知识过多，或者说得到的规则集合过大。经过剪枝，可以得到一棵相对简洁的决策树，较少的规则使得在进行分类预测时，决策树效率更高。同时，剪枝也可以减少过拟合现象的发生。为什么需要剪枝1.怎么剪？2.剪枝后效果如何？先剪枝通过提前停止树的构建而对树剪枝，一旦停止，节点就是树叶，该树叶持有子集元祖最频繁的类。停止决策树生长最简单的方法有：1.定义一个高度，当决策树达到该高度时就停止决策树的生长2.达到某个节点的实例具有相同的特征向量，即使这些实例不属于同一类，也可以停止决策树的生长。3.定义一个阈值，当达到某个节点的实例个数小于阈值时就可以停止决策树的生长。或定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值大小来决定是否停止决策树的生长。不足：阈值不好设置，过大决策树过于简单；过小，有多余树枝，过于茂盛。后剪枝方法后剪枝（postpruning）：它首先构造完整的决策树，允许树过度拟合训练数据，然后对那些置信度不够的节点子树用叶子节点来代替，该叶子的类标号用该节点子树中最频繁的类标记。相比于先剪枝，这种方法更常用，正是因为在先剪枝方法中精确地估计何时停止树增长很困难。后剪枝方法主要有以下几个方法：Reduced-ErrorPruning(REP,错误率降低剪枝)Pesimistic-ErrorPruning(PEP,悲观错误剪枝)Cost-ComplexityPruning(CCP,代价复杂度剪枝)REP错误率降低剪枝REP方法是一种比较简单的后剪枝的方法，在该方法中，可用的数据被分成两个样例集合：一个训练集用来生成决策树，一个分离的验证集用来评估这个决策树在后续数据上的精度，确切地说是用来评估修剪这个决策树的影响。这个方法的动机是：即使学习器可能会被训练集中的随机错误和巧合规律所误导，但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验。该剪枝方法考虑将树上的每个节点作为修剪的候选对象，决定是否修剪这个结点，步骤如下。REP错误率降低剪枝1）删除以此结点为根的子树2）使其成为叶子节点3）赋予该节点关联的训练数据的最常见分类4）当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点5)算法终止的条件：以bootom-up方式遍历所有的子树，直到没有任何子树可以替换使得测试数据集的表现得以改进。因为训练集合的过拟合，使得验证集合数据能够对其进行修正，反复进行上面的操作，从底向上的处理节点，删除那些能够最大限度的提高验证集合精度的节点，直到进一步修剪有害为止(有害是指修剪会减低验证集合的精度)。REP错误率降低剪枝REP是最简单的后剪枝方法之一，不过由于使用独立的测试集，原始决策树相比，修改后的决策树可能偏向于过度修剪。尽管REP有这个缺点，不过REP仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学习方法的优点和缺点提供了一个很好的学习思路。由于验证集合没有参与决策树的创建，所以用REP剪枝后的决策树对于测试样例的偏差要好很多，能够解决一定程度的过拟合问题。PEP悲观错误剪枝悲观错误剪枝法是根据剪枝前后的错误率来判定子树的修剪。该方法引入了统计学上连续修正的概念弥补REP中的缺陷，在评价子树的训练错误公式中添加了一个常数，假定每个叶子结点都自动对实例的某个部分进行错误的分类。把一棵子树（具有多个叶子节点）的分类用一个叶子节点来替代的话，在训练集上的误判率肯定是上升的，但是在新数据上不一定。于是我们需要把子树的误判计算加上一个经验性的惩罚因子。PEP悲观错误剪枝PEP悲观错误剪枝对于一叶子节点，它覆盖了N个样本，其中有E个错误，那么该叶子节点的错误率为（E+0.5）/N。这个0.5就是惩罚因子，那么一棵子树，它有L个叶子节点，那么该子树的误判率估计为：𝛴𝐸𝑖+0.5∗𝐿𝛴𝑁𝑖剪枝后内部节点变成了叶子节点，其误判个数J也需要加上一个惩罚因子，变成J+0.5。那么子树是否可以被剪枝就取决于剪枝后的错误J+0.5在𝛴𝐸+0.5∗𝐿的标准误差内。那么一棵树错误分类一个样本值为1，正确分类一个样本值为0，该树错误分类的概率（误判率）为e（e为分布的固有属性,可以通过𝛴𝐸+0.5∗𝐿𝛴𝑁统计出来），那么树的误判次数就是伯努利分布，我们可以估计出该树的误判次数均值和方差：E(subtree_err_count)=evar(subtree_err_count)=ⅇ1−ⅇPEP悲观错误剪枝PEP悲观错误剪枝那么，如果子树可以被叶子节点替代，它必须满足下面的条件：这个条件就是剪枝的标准。根据置信区间，我们设定一定的显著性因子，我们可以估算出误判次数的上下界。PEP悲观错误剪枝PEP为了提高对测试集合的预测可靠性，PEP对误差估计增加了连续性校正(ContinuityCorrection)。PEP方法认为，如果：ⅇ′𝑡≤ⅇ′𝑇𝑡+𝑆𝑒ⅇ′𝑇𝑡成立，则Tt应该被剪枝上式中：ⅇ′𝑡=ⅇ𝑡+12;𝑆𝑒ⅇ′𝑇𝑡=ⅇ′𝑇𝑡⋅𝑛𝑡−ⅇ′𝑇𝑡𝑛𝑡12ⅇ′𝑇𝑡=𝛴ⅇⅈ+𝑁𝑡2其中，e(t)为结点t出的误差；i为覆盖𝑇𝑡的叶子结点；𝑁𝑡为子树𝑇𝑡的叶子树；n(t)为在结点t处的训练集合数量。PEP悲观错误剪枝PEP采用自顶向下的方式，如果某个非叶子结点符合上面的不等式，就裁剪掉该叶子结点。该算法被认为是当前决策树后剪枝算法中精度比较高的算法之一，但是也存在缺陷。首先，PEP算法是唯一使用Top-Down剪枝策略，这种策略会导致与先剪枝出现同样的问题，将该结点的某子节点不需要被剪枝时被剪掉；另外PEP方法会有剪枝失败的情况出现。PEP悲观错误剪枝虽然PEP方法存在一些局限性，但是在实际应用中表现出了较高的精度。另外PEP方法不需要分离训练集合和验证集，对于数据量比较少的情况比较有利。其剪枝策略比其它方法相比效率更高，速度更快。因为在剪枝过程中，树中的每棵子树最多需要访问一次，在最坏的情况下，它的计算时间复杂度也只和非剪枝树的非叶子节点数目成线性关系。CCP代价复杂度剪枝CCP代价复杂度剪枝CCP剪枝时，选择“表面误差率增益值“最小的非叶子节点，删除该非叶子节点的左右子节点。若有多个非叶子节点的表面误差率增益值相同小，则选择子节点数最多的非叶子节点进行剪枝。CCP代价复杂度剪枝CCP剪枝算法分为两个步骤：1.对于完全决策树T的每个非叶结点计算α值，循环剪掉具有最小α值的子树，直到剩下根节点。在该步可得到一系列的剪枝树𝑇0,𝑇1,𝑇2⋯𝑇𝑚,其中𝑇0为原有的完全决策树，𝑇𝑚为根结点，𝑇𝑖+1为对𝑇𝑖进行剪枝的结果；2.从子树序列中，根据真实的误差估计选择最佳决策树。如何从步骤1产生的子树序列𝑇0,𝑇1,𝑇2⋯𝑇𝑚中选择出最佳决策树是CCP方法的第二步骤的关键。通常可以采用V-交叉验证(V-foldCross-Validation)和基于独立剪枝数据集两种方法。CCP代价复杂度剪枝该算法为子树Tt定义了代价（cost）和复杂度（complexity），以及一个可由用户设置的衡量代价与复杂度之间关系的参数α，其中，代价指在剪枝过程中因子树Tt被叶节点替代而增加的错分样本，复杂度表示剪枝后子树Tt减少的叶结点数，α则表示剪枝后树的复杂度降低程度与代价间的关系，定义为:其中，𝑁1：子树Tt中的叶节点数；R（t）：节点t的错误代价，计算公式为R（t）=r（t）∗p（t），r（t）为节点t的错分样本率，p（t）为落入结点t的样本占所有样本的比例；R（Tt）：子树Tt错误代价，计算公式为R（Tt）=∑R(i)，i为子树Tt的叶节点。CCP代价复杂度剪枝例如我们以非叶子结点T4为例，假设已有60条数据，那么:R(t)=r(t)∗p(t)=(7/16)∗(16/60)=7/60𝑅𝑇𝑡=𝛴𝑅ⅈ=(2/5)∗(5/60)+(0/2)∗(2/60)+(3/9)∗(9/60)=5/60𝑎=𝑅𝑡−𝑅𝑇𝑡/𝑁1−1=1/60找到α值最小的非叶子节点，令其左右孩子为NULL。当多个非叶子节点α值同时达到最小时，取较大的进行剪枝𝑁1剪枝算法比较REPPEPCCP剪枝方式自底向上自顶向下自底向上独立剪枝集需要----------计算复杂度O(n)O(n)O(n²)误差估计剪枝集上误差估计使用连续纠正标准误差PPT模板下载：行业PPT模板：节日PPT模板：素材下载：背景图片：图表下载：优秀PPT下载：教程：教程：教程：资料下载：课件下载：范文下载：试卷下载：教案下载：论坛：谢谢