决策树的后期修剪技术.doc

决策树的后期修剪技术北方交通大学 姜海摘要：决策树是对分类任务进行深入研究的一种解决方案，决策树面临的一个重要问题是，在确保决策精确的同时，又要使树简单和易于理解，这就需要借助于树的修剪技术。本文总结和评价了一些常用的后期修剪技术，目的在于提供一个清晰、详细的后期修剪技术视图。关键词：决策树、 后期修剪、 状态空间搜索Abstract: Decision tree is a widely-used solution to classification problems. A problem that decision tree faces is to realize both accuracy and simplification, so it must turn to tree-pruning technology. The article summarizes and discusses some post-pruning technology, which aims to provide a concise view of post-pruning technology. Keywords: DecisionTree、 Post-Pruning、State-Space Search 引言总结树修剪技术的关键问题在于解决方法的多样性。要驾御这种多样性，可以将这些方法分为五类。类的建立是将树归纳看作是对预想树空间的即席状态搜索。第一类中的方法直接控制树的大小，如前期修剪或后期修剪等，这些方法是通过对树的二次搜索完成的。第二类中技术侧重于状态（即树）的搜索空间。第三类中主要是调整搜索规则本身。第四类通过在搜索进程中不考虑某些事例或事例特征来限制数据库。最后一类通过转换数据结构来简化树，如转换成决策表或决策图。在决策树的分类框架中，最常用的是直接控制树的大小，包括前期修剪和后期修剪等，下面将详细介绍这类修剪技术中的后期修剪。一、后期修剪技术概述由于前期修剪会引起树在不完全成熟之前停止，即树可能在不应停止时停止扩展（horizon效应），为避免horizon效应，许多研究人员将目光转向后期修剪技术。后期修剪算法输入一个未修剪的树T，输出修剪了T中一个或多个子树后获得的树T。算法并非搜索每个可能的T，而是借助于启发式搜索减少搜索量。修剪将子树转化为叶，进而用叶节点替代内部节点。与前期修剪不同的是，后期修剪没有使用一个消除细节的函数，而是直接采用默认的同质暂停规则。如果决策树采用同质暂停规则，将不会产生替代错误，因而，修剪仅仅会削弱训练集中替代精确度。然而，当树相对培训集冗余时（即噪声参与了建模时），修剪将非常有效地提高精确度。例如，给定培训集m，假设包含培训集n的叶节点类标签为多数满足n= n，则替代错误率为（n-n）/ m，低层叶节点对替代精确度的影响最小，因而被最先修剪。后期修剪方法借助于多种评价函数，用以确定修剪一个节点是削弱还是增强了事例集的精确度。修剪是是可以提高分类的精确度的，尤其是当培训集噪声级别比较高时，修剪相当有效。有些后期修剪方法将培训集分为两个子集。一个用于生成树，另一个用于后期修剪，不妨成之为生成集和修剪集。生成集常用于生成一个树，然后，按修剪变量生成树集S，修剪集将从S中选择一个最佳的树。例外情况是排错修剪（REP）技术，即修剪集对树进行修剪，而不单单是选择。修剪集方法的优势在于生成树集，而非一个树。尤其是当领域专家算法对选择的树不满意时，可以从树集中进行人为挑选，树集归纳可以提高预测的精确度。将培训集分为两个子集的不足之处在于，设计决策受人为的影响较大，小的培训集可能产生一个很小的树，因为低层部分被剪掉，但这恰恰是应该选择一个尽可能大的培训集的很好的理由，减小培训集的大小相当于增加了修剪预测精确度的不确定性。将修剪集分离出来会带来不少好处的，但也有人认为将修剪集分离出来相当于给于了分离培训集较其他方法更多的培训事例，当将同样多的培训事例用于其他方法时，结果将毫无差别。但有一点可以肯定，将修剪集分离出来确实提供了一种新的修剪思路，而且，在研究这种方法时，还发现了修剪方法和测试方法之间并无太大关系，这样就可以独立地研究这两个问题了。后期修剪算法的搜索策略是由下向上的，即搜索开始于树最底层的内部节点（子类都是叶的节点），将符合修剪规则的剪掉。此过程可能从新生成的最底层节点重新开始，直到没有节点满足修剪规则时停止。如果节点的子树不应按某种规则被修剪，则由下向上的评价规则将使该节点避免被按同一规则修剪。与此相对的是自上向下的策略，即从根开始依次修剪节点，直到无法修剪为止。这样作的风险在于，按某种规则剪掉了某个节点，但其子类是不应按这一规则被剪掉的。二、主要后期修剪技术修剪技术专家Esposito等人将按各种修剪技术生成的树与按基于修剪集的REP技术生成的“理想大小”的树进行了比较，比较的假设前提是REP能生成基于修剪集的优化的修剪树。生成的树比这个标准大的修剪称为“不彻底修剪”，生成的树比这个标准小的修剪称为“过量修剪”。生成的树与标准树进行大小的比较，而不是树结构的比较。因而，理想树的大小与分类精度不够相关。现在总结以下这些后期修剪算法的主要特征及优缺点：1、 最小成本复杂度修剪（MCCP）第一种后期修剪方法是MCCP，是BreImen等人开发的著名CART系统的一部分。他们为树T定义了成本（cost） 和复杂度（complexity），以及一个可由用户设置的成本与复杂度之间的权衡参数，其中，成本指T的替代错误总数，复杂度表示叶的总数。该方法包括两步，首先，从衍生树开始一直到根树，不断修剪子树将产生一系列逐渐变小的树，直至获得最小成本复杂度。修剪策略由下向上，这样树就会向根树聚集。但不同与其它自下而上的策略，即在修剪的同时，每次往复将遍及每一个节点。第二步，选择一个“最好”的树，主要考虑其大小和MCCP的参数，即修剪集精确度或交叉验证（CV）准确度。MCCP将输出一个错误不多于标准错误（1-SE）的最小的树。0-SE参数是近期引入MCCP中的，它不需要1-SE参数的支持（即选择仅仅基于精确度）。这样就有四个可选参数了：修剪集、CV集、0-SE和1-SE。在大小和精确度方面，选择0-SE和CV的组合决不逊色于其它方法，而0-SE和修剪集的组合则要强于其它方法。CV可生成精确度很高的树，尤其是对小样本的培训集。2、 排错修剪（REP）REP，作为ID3系统的一部分，也使用修剪集。MCCP在树归纳和修剪过程中均应用生长集，而RPE则仅在归纳时应用，在生成和评价修剪树时应用修剪集。RPE自下而上修剪树，不降低修剪集的精确度。REP可以在修剪集的基础上，生成最小的树，而且错误率最低。RPE方法不但在精确度方面与其它方法不相上下，而且比大多数方法生成的树要小。3、 最小错误修剪（MEP）MEP方法基于生长集计算内部节点的错误概率，参数m确定一个类对错误计算的影响，MEP自下而上检查内部节点，如果子树产生的错误大于用叶来替代它产生的错误，就剪掉子树。当m取不同的值时，MEP可以生成一个修剪树集，再由领域专家确定其中最好的树。目前设计的自选树的方案是选择最小的和错误率最低的树。MEP属于不彻底修剪，但精确度不比其它方法逊色。4、 关键值修剪（CVP）CVP方法可以选择地使用修剪集，包括两步：首先，针对测试集选择参数cv（关键值）。在自下而上的修剪过程中，若评价函数取值小于或等于关键值，则包含事例集和测试集的节点将被修剪掉。选择不同的关键值重复进行这一过程，则会得到一个修剪树集。其次，从树集中选择一个最好的树，主要考虑决策精度和重要程度，通常借助于统计表完成，但统计表难以用于比较不同树之间的“相关重要性”。也有人认为概率测度是不合理的，应借助于修剪集测试CVP。CVP属于不彻底修剪，精确度不高。5、保守错误修剪（PEP）PEP算法的出现与ID3相关，像MCCP的CV变量一样不用修剪集。PEP强加了一个纠正机制，以尽量减少错误，而且，子树都建立在应该被修剪的假设前提下，除非其错误估计至少比根节点错误估计少一个标准错误。尽管PEP算法在测试中最精确，但仍有其局限性。PEP是唯一一种采取自顶向下修剪策略的算法，它面临着与前期修剪同样的问题：树在某节点被剪掉，而其子树不应按同一规则被剪掉。其次，PEP有时不会作修剪工作，即使是对随机数据。第三，将创建树的数据样本看作是随机样本是不合适的，尽管这些局限性，PEP仍保持了高的精确度，自顶向下的修剪策略也要比其它方法高效。6、基于错误的修剪（EBP）EBP用于ID3的子类C4.5，是PEP的一个子类。EBP算法事先定义节点的培训数据集、占优势的类、以及不属于此类的事例集，EBP将培训数据集作为一个分布样本，在适当的约束下，估计节点的错误率，并将之作为子类概率分布的上限。另外，EBP新增一个修剪操作，该操作允许用节点的子树替代此节点。保留好的节点，而将其父节点修剪，这就减少了EBP受horizon效应的影响，扩展了搜索空间。虽然EBP比PEP侧重于修剪，但EBP仍属于不彻底修剪，不过，精确度高于其它方法。在测试过的各种方法中，PEP和BEP的精确度最高，而且它们不需要修剪集和进行代价昂贵的交叉验证，但它们属于不彻底修剪。相比而言，REP和MCCP的0-SE组合生成的树更接近“合适”的大小（即不彻底修剪和过量修剪的程度最低），而且精确度不错。后期修剪在这些方面的差异已经过测试验证了，但要确切的定义和量化它们，还需要更深入的研究。另外，还有其它一些后期修剪方法，但不如上述方法优良，故在此不予以详述。结论决策树提供了数据库的一个抽象定义，即在不需要存储数据库的情况下，作出迅速、准确的数据预测。当然，如果用户愿意接受存储培训集和测试集的成本，那么他们就可以选择适合专业领域的一种或多种修剪技术，对决策树进行深层次的精练和优化。参考资料：1. Gilbreath, R. E. Health care data repositories: components and a model. The Journal of the Healthcare Information and Management Systems Society, Vol. 9, No. 1, pp63-73.2. Kimball, R. (1996). The Data Warehouse Toolkit. New York: John Wiley & Sons Inc.3. Meyer, D. and Cannon, C. (1998). Building a Better Data Warehou