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