决策树是对分类问题进行深入分析的一种方法，在实际问题中，按算法生成的决策树往往复杂而庞大，令用户难以理解。这就告诉我们在重分类精确性的同时，也要加强对树修剪的研究。 引言机器学习领域研究对数据的归纳分类，主要集中在预测精确度方面。然而，在许多实际业务中，只有"数据的预测结构更易于理解"的分类规则才易让人接受，就象这个分类规则所解决的决策问题一样让人清楚明白。在机器学习和统计领域，决策树归纳作为一种分类问题的解决方法正在被广泛的研究。由于许多树简化规则正在生成越来越简单和越来越小的决策树，树简化规则已经成为继预测精度之后的第二个研究焦点。总结树简化技术的关键问题在于解决方法的多样性。要驾御这种多样性，可以将这些方法分为五类。类的建立是将树归纳看作是对预想树空间的即席状态搜索。 一、决策树算法的程序实现决策树归纳算法在机器学习、统计和其它解决分类问题的领域有着广泛的应用。决策树可以按如下方式分类一个查询事例，给定要分类的查询Q，树将沿一条路径从根遍历到叶节点，直到将类标签分配给Q。测试通常能够评价描述事例的特征或（如布尔或线形）组合特征集。笔者开发的决策树算法包括四个输入：
算法输出的决策树T的每一叶代表一个类，通常有唯一的类标签。决策树由根部向下运用递归分割算法。Make-T函数生成决策树，并完成后期修剪工作，这可能有三种结果：维持原状、修剪或转换成另一种数据结构。Induce-T函数输出树T，它输入C中的子集C'、 测试集R、评价函数E()，以及暂停函数Stop()。 二、对树进行修剪优化时应考虑的问题1、决策树的大小决策树变的异常庞大有多种原因。其中之一是特征描述不当，有些树特征描述方式不能精确的建立目标概念模型，当用这种描述方式时，目标模型非常复杂。相反，运用的当的描述将大大降低模型的复杂程度。因此，这个问题很好地提醒我们，树修剪过程中要考虑相应的描述；另一个导致树庞大的原因是噪声。当事例包含大量的特征噪声（即错误标签的特征值）或类噪声（即错误标签的类值）时，归纳运算会因为不相关的事例特征而将树扩展的漫无边际。噪声导致无关的事例掺杂在选定的测试集中，这将引起"无谓建模"的现象，即树将目标概念和内部噪声都作为建模的对象。这是个普遍的问题，因为给定事例中都不同程度地包含噪声。虽然有多种降低噪声的剪树方法，但记住没有一个剪树方法对任何噪声都有效。 超大的树通常是破碎的--过多的叶，且每叶仅有少数的事例。这样的叶比拥有许多事例的叶更易出现分类错误，更易受噪声影响。这些叶节点（或更准确地说，其相应的树路径）是分散的，发生的可能性都很低。因而，另一种树简化方法是通过剪掉只有少数事例的叶子来消除这种分散性。不管什么原因，复杂树不仅难以理解，而且分类模糊，因为小散点比大散点更易出错。然而，毕竟在培训集中辨别特征的真伪决非易事，在不考虑对树在未知测试事例中运行性能的影响下，修剪树往往会降低对培训集分类的精确度。 2、权衡精确度与简易性修剪方法在于确保精确程度的同时，提高可理解性。这两个目标不一定是矛盾的，可能有种方法能同时提高精确度和可理解性。实际上，最初引入树简化方法的目的是控制培训集中的噪声，而后发现它可以提高许多含噪声的数据集的精确度。 对简化（或修剪）程度的控制一直是人们争论不朽的问题。通过牺牲精确度修剪的决策树常常灵巧的出奇，然而，保守一点的修剪可能带来精确度的大大提高，这在实际应用中至关重要。故此，许多学者在研究决策树的精确度与简易性的最佳比例，但在随机选择的培训集中很难作做到这一点，因为单凭培训集中的事例，难以区分树的哪部分复杂是由噪声引起的和哪部分是由树本身属性引起的。而且，专门领域的知识不属于培训集之内，就需要在培训集中评价专门领域知识的噪声级别、自身属性的复杂度、以及选择需要简化的程度。对知识稀疏的归纳算法不会涉及这些，因而每个树就假定了模型的复杂程度和培训噪声的级别，这将影响树简化的整个过程。这些算法与描述偏差还有所不同。例如，许多算法假定模型是正规分散的形式，测试对事例特征是单变量的函数，而其它算法假定特征值可以进行线形组合。自然，针对特定的任务，会有一些算法比另一些算法要好。如果无法决断哪个算法对给定的数据库最好，就它们放在一起运行，然后比较结果。 三、决策树的修剪算法修剪树有多种算法，一般人们将其分为五大类方法。最常用的是直接控制树大小的一类方法，通过前期修剪（即在树扩展过程中强行增加一个停止规则），或后期修剪（在树生成后剪掉子树）完成，或逐渐调整树的大小。再一类方法主要是扩展测试集，首先按特征构成是数据驱动还是假设驱动（即借助于以前建立的树预测构件特征）的差别，将建立的特征组合或分割，然后在此基础上引进多变量测试集。这些方法在调整树表达时有效地扩展了树集。第三类，包括选择不同的测试集评价函数，通过改善连续特征的描述，或修改搜索算法本身实现。第四类，数据库约束，即通过削减数据库或事例描述特征集来简化树。第五类，将树转换成另一种数据结构（如决策表或决策图）。这些方法通常可以在同一种算法中相互结合，进而增强各自的功能。例如，经常在搜索测试或搜索空间测试中引入控制树大小的方法。简化决策树的最常用方法是在树建立过程中控制其大小，包括前期修建和后期修剪。 前期修剪阻止决策树按默认的同质暂停规则生成一个"完全"的树，要作到着一点，需在树生成进程中加入另一个暂停规则。自由限制树的简易修剪形式非常适用，然而，通常暂停规则将评价树继续扩展的效应，如果效用为零（或很小），则停止扩展。或者说此后的处理对树的输出形态影响不大。前期修剪较后期修剪有效，因为它尽可能早的结束了树的生成阶段。约束暂停规则往往同时过滤掉相关和无关测试集，而且，当选择测试集和修剪时使用对某个节点是局部的同一个测试约束时会出现问题，因为约束的绝对值往往因样本的大小不同而变化。前期修剪会引起树在不完全成熟之前停止，即树可能在不应停止的时候而停止扩展，，或称之为horizon效应。即使这样，前期修剪对大规模的实际应用还是值得研究的，因为它相当高效。人们有望在未来的算法中解决horizon效应。 后期修剪是人们普遍关注的树简化方法，后期修剪算法输入一个未修剪的树T，输出修剪了T中一个或多个子树后获得的树T'。算法并非搜索每个可能的T'，而是借助于启发式搜索。修剪将子树转化为叶，进而用叶节点替代内部节点。与前期修剪不同的是，后期修剪没有使用一个消除细节的函数，而是直接采用默认的同质暂停规则。当树相对训练集冗余时（即噪声参与了建模），修剪将非常有效地提高精确度。例如，给定培训集m，假设包含培训集n的叶节点类标签为多数满足n'〈= n，则替代错误率为（n-n'）/ m，低层叶节点对替代精确度的影响最小，因而被最先修剪。后期修剪方法借助于多种评价函数，用以确定修剪一个节点是削弱还是增强了事例集的精确度。恰当的修剪可以提高分类的精确度。尤其是当训练集噪声级别比较高时，修剪相当有效。 结束语在精确度与简易性之间选择权衡值可能是决策树永远逃避不了的主题，但不管怎样，记住这一点是重要的，即即使我们专注的问题是修剪树，但决不能将精确度置之不理。修剪树如果导致精确度的大大降低，那修剪将是毫无意义的。
|