决策树归纳(共24页).docx

《决策树归纳(共24页).docx》由会员分享，可在线阅读，更多相关《决策树归纳(共24页).docx（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上决策树归纳关键词：分类，归纳，决策树，信息理论，知识获取，专家系统摘要： 通过实例的归纳推理构建基于知识的系统的技术已经在若干实际应用中成功地证明。 本文总结了合成在各种系统中使用的决策树的方法，并且详细描述了一个这样的系统ID3。 最近研究的结果显示可以修改该方法以处理嘈杂和/或不完整的信息的方式。 讨论了报告的基本算法的缺点，并且比较了克服它的两种手段。 本文结束了当前研究方向的插图。1.介绍由于人工智能首先在1950年代中期被认可为一门学科，机器学习已成为一个中心研究领域。可以给出这个突出的两个原因。学习的能力是智能行为的标志，所以任何将智力理解为现象的尝试都必

2、须包括对学习的理解。更具体地，学习提供了构建高性能系统的潜在方法。学习研究由不同的子领域组成。在一个极端，有自适应系统监视自己的性能，并尝试通过调整内部参数来改善它。这种方法，大部分早期学习工作的特点，产生了自我完善的游戏程序（Samuel，1967），平衡杆（Michie，1982），解决问题（Quinlan，1969）和许多其他领域。一个完全不同的方法认为学习是以概念形式获取结构化知识（Hunt，1962; Winston，1975），歧视网（Feigenbaum和Simon，1963）或生产规则（Buchanan，1978）。后一种机器学习的实际重要性已经被低估了，由基于知识的专家系统的

3、出现。正如他们的名字所暗示的，这些系统由显式地表示而不是在算法中隐含的知识提供动力。驱动开拓性专家系统所需的知识通过领域专家和知识工程师之间的长期互动来编写。虽然通过该方法的典型的知识解释速率是每人每天的几个规则，但是用于复杂任务的专家系统可能需要数百或甚至数千个这样的规则。很明显，知识获取的面试方法不能跟上对专家系统的迅速增长的需求; Feigen-baum（1981）认为这是“瓶颈问题”。这种观点刺激了机器学习方法作为一种解释知识的手段的研究（Michie，1983）。本文集中在一个微观的机器学习和一系列的学习系统，已被用来建立一个简单的类型的知识为基础的系统。第2节概述了这个家庭的特点，

4、并介绍其成员。所有这些系统解决了从示例中引入决策树的同一任务。在更完整地说明这个任务之后，在第4节中详细描述了一个系统（ID3）。第5和6节给出了ID3的扩展，使其能够处理噪声和不完整的信息。对感应算法的中心方面的回顾揭示了第7节中阐述的可能的改进。本文结束时提出了两个新的举措，提出了家庭可能成长的方向的一些想法。2. TDIDT系列学习系统Carbonell，Michalski和Mitchell（1983）确定了机器学习系统可以分类的三个主要方面：使用的基础学习策略;由系统获得的知识的表示; 和系统的应用程序域。本文涉及一系列在这些维度上具有强共同联系的学习系统。以相反的顺序取得这些特征，这

5、些系统的应用领域不限于智力活动的任何特定领域，例如化学或象棋; 它们可以应用于任何这样的区域。 虽然它们是通用系统，但它们所涉及的应用程序都涉及分类。 学习的产物是一种程序性知识，其可以将迄今未看见的对象分配给指定数量的不相交类别中的一个。 分类任务的示例有：1.从症状诊断医学状况，其中类别可以是各种疾病状态或可能的治疗;2.确定棋位的游戏理论价值，分类用白色赢得，白色输和平局; 和3.从大气层观察来判断严重的雷暴是不可能的，可能的或很可能的。可能看起来分类任务只是程序性任务的一个微小的子集，但即使是诸如机器人规划的活动也可以重新分类为分类问题（Dechter和Michie，1985）。这个家

6、庭的成员的特点是他们代表知识作为决策树。 这是相对简单的知识形式主义，缺乏语义网络或其他一阶表示的表达能力。 作为这种简单性的结果，在TDIDT系列中使用的学习方法比在能够以更强大的语言表达其学习的结果的系统中使用的学习方法复杂得多。 然而，仍然可能以决策树的形式生成能够解决具有实际意义的困难问题的知识。基本策略是从例子的非增量学习。向系统呈现与分类任务相关的一组案例，并且由示例中的频率信息指导而不是由给出示例的特定顺序从上而下开发判定树。这与诸如在MARVIN（Sammut，1985）中采用的增量方法形成对比，其中用指导员进行对话以“调试”部分正确的概念，并且由Winston（1975）使用

7、，其中示例是每次分析一个，每个产生发展概念的小变化;在这两个系统中，呈现示例的顺序是最重要的。这里描述的系统搜索给定示例中的模式，因此必须能够在学习期间的许多阶段检查和重新检查所有模式。共享这种数据驱动方法的其他知名程序包括BACON（Langley，Bradshaw和Simon，1983）和INDUCE（Michalski，1980）。因此，总之，这里描述的系统开发用于分类任务的决策树。 这些树从树的根开始构造并且向下到其叶。 家庭的回文名称强调，其成员执行决策树的7bp-e）/ nduction。开发分类规则的示例对象仅仅通过它们的一组属性或属性的值是已知的，并且决策树依次以这些相同的属性

8、表示。示例本身可以以两种方式组装。它们可能来自形成观察历史的现有数据库，例如在诊断中心积累的某些医学领域的患者记录。这种对象给出可靠的统计图像，但是，由于它们不以任何方式组织，它们可以是在记录期间没有遇到的冗余或省略的情况。另一方面，对象可以是域专家准备的精心挑选的教程示例集合，每个对与完整和正确的分类规则具有某些特定相关性。专家可能会为了避免冗员，并包括罕见病例的例子。虽然系统系统将以令人满意的方式处理任一类型的收集，但应当提及的是，较早的TDIDT系统被设计为具有历史记录，方法，但是这里描述的所有系统现在经常与教程一起使用（Michie，1985）。CLS (1963)IID3 (1979

9、)(|IACLS (1981)ASSISTANT (1984)Expert- Ease (1983) EX-TRAN (1984)RuleMaster (1984)图L TDIDT系列树。图1显示了TDIDT系统的系列树。 这个家族的族长是Hunfs概念学习系统框架（Hunt，Marin and Stone，1966）。 CLS构造了一个尝试最小化对对象进行分类的成本的决策树。 该成本具有两种类型的分量：确定对象所展现的属性A的值的测量成本，以及当其实际类别为K时，确定对象属于类别J的错误分类成本。CLS使用类似于 最小值。 在每个阶段，CLS将可能的决策树的空间探索到固定深度，选择动作以使该

10、有限空间中的成本最小化，然后在树中向下移动一个级别。 根据所选择的预期深度，CLS可能需要大量的计算，但是能够在显示的对象中发现细微的模式。ID3（Quinlan，1979，1983a）是一系列从CLS开发的程序之一，响应由唐纳德Michie提出的具有挑战性的诱导任务，从单独的基于模式的特征来决定在King-Rook中的特定棋位置 vs国王骑士的游戏失去了骑士侧在固定数量的层。 ID3的完整描述出现在第4节中，因此在这里要注意的是，它在迭代外壳中嵌入了树构建方法，并且使用信息驱动的评估函数放弃了CLS的成本驱动的前瞻。ACLS（Paterson和Niblett，1983）是ID3的概括。 CL

11、S和ID3都要求用于描述对象的每个属性只具有来自指定集合的值。 除了此类型的属性，ACLS允许具有不受限制的整数值的属性。 处理这种属性的能力允许ACLS应用于困难的任务，如图像识别（Shepherd，1983）。ASSISTANT（Kononenko，Bratko和Roskar，1984）也承认ID3是其直接祖先。 它在许多方面与ID3不同，其中一些将在后面的章节中详细讨论。 ASSISTANT通过允许具有连续（实数）值的属性进一步推广ACLS的整数值属性。 ASSISTANT不是坚持类是不相交的，而是允许它们形成层次结构，使得一个类可以是另一个的更细分割。 ASSISTANT不以ID3的方

12、式迭代地形成决策树，而是包括用于从可用对象中选择训练集的算法。 ASSISTANT已经用于具有有希望结果的多个医学领域。图中最底部的三个系统是ACLS的商业衍生品。 虽然它们没有显着提高基础理论，但它们包含了许多用户友好的创新和实用程序，加快了生成和使用决策树的任务。 他们都有工业成功的信用。 例如，西屋电气的水反应堆部门指出了一个燃料富集应用，其中该公司能够通过使用其中一个，每年增加1000多万美元的收入。3.感应任务我们现在给出一个更精确的感应任务的说明。 基础是以属性集合的形式描述的对象的宇宙。 每个属性测量对象的一些重要特征，并且在这里将限制为采用一组离散的，互斥的值（通常是小的）。

13、例如，如果对象是星期六早上，分类任务涉及天气，属性可能是天气，值为晴，阴，雨）温度，值（酷，温和，湿），湿度，值（高，正常），风，值（真，假）总之，属性提供了用于表征宇宙中的对象的零阶语言。 特定的星期六早上可能被描述为天气：阴温度：冷湿度：正常大风：假的Universe中的每个对象都属于一组互斥类中的一个。 为了简化以下处理，我们将假定只有两个这样的类表示为P和N，但是扩展到任何数量的类不是困难的。 在两类诱导任务中，类P和N的对象有时分别被称为被学习的概念的肯定实例和否定实例。另一个主要成分是其类别已知的对象的训练集合。 归纳任务是开发一个分类规则，可以从属性的值确定任何对象的类。 直接的

14、问题是属性是否提供足够的信息来做到这一点。 特别地，如果训练集包含对于每个属性具有相同值但仍属于不同类的两个对象，则显然不可能仅参考给定属性来区分这些对象。 在这种情况下，属性将被称为训练集的因而用于诱导任务。如上所述，分类规则将被表示为决策树。表1显示了一个使用“星期六上午，属性”的小训练集。每个对象的每个属性的值与对象的类一起显示（这里，类P的早晨适用于一些未指定的活动）。在图2中给出了对训练集中的每个对象进行正确分类的决策树。决策树的叶子是类名，其他节点表示基于属性的测试，每个可能结果都有一个分支。为了对对象进行分类，我们从树的根开始，评估测试，并采取适当的分支结果。该过程继续直到遇到叶

15、，在该时间对象被断言为属于由叶命名的类。采用图2的决策树，该过程包括在该部分的开始处作为示例出现并且不是训练集的成员的对象应当属于类别P.注意，只有子集的属性可能在从决策树的根到叶的特定路径上遇到;在这种情况下，在确定类之前只测试outlook属性表1.一个小的训练集No.AttributesClassOutlookTemperatureHumidityWindy1sunnyhothighfalseN2sunnyhothightrueN3overcasthothighfalseP4rainmildhighfalseP5raincoolnormalfalseP6raincoolnormaltru

16、eN7overcastcoolnormaltrueP8sunnymildhighfalseN9sunnycoolnormalfalseP10rainmildnormalfalseP11sunnymildnormaltrueP12overcastmildhightrueP13overcasthotnormalfalseP14rainmildhightrueN Outlook图2.一个简单的决策树如果属性足够，则总是可以构造正确地分类训练集中的每个对象的决策树，并且通常存在许多这样的正确决策树。归纳的本质是移动超出训练集，即构造决策树，其不仅正确地分类来自训练集的对象，而且还正确地分类其他（未见的

17、）对象。为了做到这一点，决策树必须捕获一个对象类和它的属性值之间的一些有意义的关系。给定在两个决策树之间的选择，其中每个决策树在训练集合上是正确的，似乎更倾向于更简单的决策树，因为它更可能捕获问题中固有的结构。因此，更简单的树将被期望在训练集之外正确地分类更多的对象。例如，图3的决策树对于表1的训练集合也是正确的，但是其更大的复杂性使其被怀疑为训练集合的“解释”。(对于更简单的树的偏好，这里作为Occam的剃刀的常识应用程序呈现，也通过分析支持。 Pearl（1978b）和Quinlan（1983a）使用不同的形式从一组已知的情况推导出了预期误差的上界。 对于预定尺寸的训练集，这些边界随着诱导

18、归纳的复杂性而增加。)4.ID3上述诱导任务的一种方法是生成正确分类训练集并选择其中最简单的所有可能的决策树。 这样的树的数量是有限的但是非常大，因此这种方法仅对于小的感应任务是可行的。 ID3被设计用于频谱的另一端，其中存在许多属性，并且训练集包含许多对象，但是其中需要相当好的决策树而没有太多的计算。 通常已经发现构造简单的决策树，但是它使用的方法不能保证更好的树没有被忽视图3是复杂的决策树ID3的基本结构是迭代的。随机选择被称为window的训练集合的子集，并从其中形成决策树;这个树正确地分类窗口中的所有对象。然后使用树对训练集中的所有其他对象进行分类。如果树给出所有这些对象的正确答案，则

19、对于整个训练集是正确的，并且过程终止。如果不是，则将未正确分类的对象的选择添加到窗口，并且处理继续。以这种方式，在针对高达50个属性描述的多达三万个对象的训练集合的仅仅几次迭代之后，已经找到正确的决策树。经验证据表明，通过该迭代方法，通常比通过从整个训练集直接形成树更快地发现正确的决策树。然而，0 * Keefe（1983）已经注意到，不能保证迭代框架收敛在最终树上，除非窗口可以增长以包括内容训练集。这种潜在的限制在实践中还没有出现。问题的关键是如何形成一个对象的任意集合C的决策树。如果C是空的或只包含一个类的对象，最简单的决策树只是一个用类标记的叶子。否则，让T是对具有可能结果i，2，. O

20、w的对象的任何测试。 C中的每个对象将为T提供这些结果之一，因此T产生C的分区Ci，C2，. Cwj，其中Ci包含具有结果i的那些对象。这由图4的树形式图形地表示。如果该图中的每个子集C i可以由针对C 1的决策树替换，则结果将是针对所有C的决策树。此外，只要两个或更多个C i，是非空的，每个Ci小于C.在最坏的情况下，这种分割和征服策略将产生满足叶的一类需求的单对象子集。因此，假设总是可以找到给出任何对象集合的非平凡分区的测试，则该过程将总是产生正确地分类C中的每个对象的决策树。图4. C中对象的树结构T/ / l 1 2 3 wC3Cw如果决策树是简单的，测试的选择是至关重要的。 目前，测

21、试将被限制为对属性的值进行分支，因此选择测试是为了选择树根的属性。 ID系列中的第一个诱导程序使用了工作得相当好的座位评价函数。 根据Peter Gacs的建议，ID3采用了一种基于信息的方法，该方法取决于两个假设。 令C包含P类的p个对象和N类的n个。假设是：（1） 对于C的任何正确的决策树将以与它们在C中的表示相同的比例来分类对象。任意对象将被确定为以概率p /（p + n）属于类P，并且具有概率n / （p + n）。（2） 当决策树用于对对象进行分类时，它返回一个类。 因此，决策树可以被认为是消息的源，或者具有生成该消息所需的预期信息p + nI (P，n)=I (P，n)=np +

22、nlg2np + npp + nlg2Pp + nI (P，n)=np + nlg2np + npp + nlg2Pp + nI (P，n)=np + nlg2np + npp + nlg2Pp + nI (P，n)=公式见原稿如果将具有值Ai，A2，. Av）的属性A用于决策树的根，则将C分割为Ci，C2，. Cv，其中Ci包含C中具有值的那些对象 Ai。令Ci包含P类的pi对象和N类的rii。对于C的子树所需的预期信息是I（pi，ni）。 然后获得对于以A作为根的树所需要的预期信息作为加权平均lg2np + npp + nlgI (P，n)=np + nlg2np + npp + nlg2

23、Pp + I (P，n)=np + nlg2np + npp + nlg2Pp + nI (P，n)=式见原稿np +其中第i个分支的权重是C中属于Ci的对象的比例。 因此，通过在A上分支获得的信息gain(A) = I(p, n) - E(A)一个好的经验法则似乎是选择那个属性来分支，获得最多的信息。 ID3检查所有候选属性并选择A以最大化增益（A），如上形成树，然后递归地使用相同的过程以形成用于残余子集Ci，C2，. Cv的决策树。为了说明这个想法，让C是表1中的对象集。在14个对象中，9个是P类，5个是N类，因此分类所需的信息是I(p，n) = - log2 log2 = 0.940 b

24、its14 141414现在考虑outlook属性与值sunny，overcast，rain）。 C中14个对象中的5个具有第一个值（晴天），其中两个来自P类，三个来自N类pi = 2 ni = 3 I(Pl) m) = 0.971和类似p2 = 4 n2 = 0 I(p2j n2) = p3 = 3 n3 2 I(p3, n3) = 0.971因此，测试此属性后的预期信息要求545E (outlook) - I(pi, m) + -1 (p2, n2) + I(P3, n3)141414=0.694 bits然后，该属性的增益gain(outlook) = 0.940 - E(outlook

25、) = 0.246 bits类似的分析给出gain(temperature) = 0.029 bits gain(humidity) = 0.151 bits gain(windy) = 0.048 bits因此ID3中使用的树形成方法将选择outlook作为决策树根的属性。 然后根据它们的outlook属性的值将对象分成子集，并且以类似的方式引发每个子集的决策树。 实际上，图2示出了来自该训练集合的ID3生成的实际决策树。如果C不包含具有某个特定值A的对象，则给出空的Cj，则出现特殊情况。 ID3标记了一个叶子（nuir，因此它不能分类任何到达那个叶子的对象，一个更好的解决方案会从Q来的集合

26、C中推广出来，并赋予这个叶子在C中更频繁的类。ID3 属性选择启发式的价值可以通过所得到的决策树的简单性来评估，或者更准确地说，这些树表示类和属性之间的真实关系的程度，这通过它们将对象分类的精确度 而不是训练集中的那些（它们的预测精度）。 评估该预测准确度的直接方法是仅使用给定对象集合中的Tpart作为训练集，并且在剩余部分上检查所得到的决策树。已经进行了这种类型的几个实验。在一个领域中，在49个二进制值属性中描述的140万个象棋位置产生715个不同对象，分成65：类之间为35。该域是相对复杂的，因为用于所有715个对象的正确决策树包含大约150个节点。当随机选择包含这些715个对象的20的训

27、练集时，它们产生正确分类超过84的未见对象的决策树。在同一域的另一个版本中，39个属性给出了551个具有类似大小的正确决策树的不同对象;这些551个对象的20的训练集给出了具有几乎相同精度的决策树。在一个更简单的域（具有48个节点的正确决策树的1,987个对象）中，包含20的对象的随机选择的训练集给出了正确分类98的未见对象的决策树。在所有三种情况下，清楚的是，决策树反映数据中存在的有用（而不是范围）关系。通过查看过程的计算要求，对ID3的这种讨论进行四舍五入。 在决策树的每个非叶节点处，必须确定每个未测试的属性A的增益。 该增益又依赖于A的每个值Ai的值pi和ni，因此必须检查C中的每个对象

28、以确定其类别和其值A.因此，每个这样的节点处的过程的计算复杂度 是O（ICI-IAI），其中IAI是上面的属性的数量。 因此，每次迭代的1D3的总计算需求与训练集的大小，属性的数量和决策树中的非叶节点的数量的乘积成比例。 相同的关系似乎延伸到整个感应过程，即使执行几次迭代。 当感应任务的尺寸增加时，没有观察到时间或空间的指数增长，因此该技术可以应用于大任务。5.噪音到目前为止，训练集中提供的信息被假定为完全准确。遗憾的是，基于现实世界数据的感应任务不可能发现这个假设是可以成立的。对象的描述可以包括基于测量或主观判断的属性，这两者都可能引起属性值中的错误。训练集中的一些对象甚至可能被错误分类。为

29、了说明这个想法，考虑从患者病史的集合开发用于医学诊断的分类规则的任务。属性可以测试血液中某些物质的存在，并且几乎不可避免地在某些时候给出假阳性或阴性读数。另一个属性可以将构建评估为轻微，中等或重，并且不同的评估者可以应用不同的标准。最后，病例历史的收集可能包括对其进行了不正确诊断的一些患者，由此在训练集中提供的类信息中具有随后的错误。这些类型的错误会对前面描述的树构建过程产生什么问题？再次考虑表1中的小训练集，并且现在假设对象1的属性外观被错误地记录为阴影。对象1和3将具有相同的描述，但属于不同的类，因此对于该训练集合属性变得不足。如果对象4的属性风被破坏为真，则属性也将变得不足，因为该对象然

30、后将与对象14相冲突。最后，初始训练集可以由图2的简单决策树来解释，其包含8个节点。假设对象3的类被破坏为N.这个被破坏的训练集合的正确的决策树现在必须解释对象3的明显的特殊情况。最小的这样的树包含十二个节点，一半又如“后”树。这些图示突出了两个问题：训练集中的错误可能导致属性变得不足，或者可能导致伪复杂度的决策树。这种在系统属性值或类信息中的非系统误差通常被称为噪声。 如果树构造算法将能够用受噪声影响的训练集合来操作，则需要两个修改。（1）算法必须能够使用不适当的属性，因为噪声可以导致甚至最全面的属性集合看起来不足。（2）算法必须能够决定测试另外的属性将不会改进决策树的预测准确性。 在上面的

31、最后一个例子中，它应该避免增加决策树的复杂性以适应单个噪声生成的特殊情况。我们从决定属性何时真正与分类相关的第二个要求开始。 令C是包含两个类的代表的对象的集合，并且使A是具有产生子集Ci，C2，. Cv的随机值的属性。 除非每个Ci中的P类对象的比例与C本身中的P类对象的比例完全相同，否则属性A上的分支将给出明显的信息增益。 因此，看起来测试属性A是一个明智的步骤，即使A的值是随机的，因此不能帮助对C中的对象进行分类。这种困境的一个解决方案可能是要求任何被测试的属性的信息增益超过一些绝对或百分比阈值。 使用该方法的实验表明，大到足以筛选出不相关属性的阈值也排除了相关的属性，并且在无噪声的情况

32、下降低了树构建过程的性能。已经发现基于随机独立性的卡方检验的替代方法更有用。 在先前的符号中，假设属性A产生C的子集（Ci，C2，. Cv），其中Q分别包含类P和N的pi和m个对象。 如果A的值与C中的对象的类无关，则pi的期望值pi应为Pi = PPi + mp + n如果n i是ni的对应期望值，则是统计量 (Pi-P、)2 + (ni-n、)2 i=l Pini是具有v-1自由度的近似卡方。 假设值pi或n i非常小，该统计量可以用于确定可以拒绝A与C中的对象类无关的假设的置信度（Hogg和Craig，1970）。 然后可以修改树构建过程以防止测试任何不相关性不能以非常高（例如99）的置

33、信水平拒绝的属性。 已经发现这在防止过度复杂的树中是有效的，其试图在没有噪声的情况下适应噪声而不影响过程的性能。现在转到第一个要求，我们看到可能出现以下情况：C对象的集合可以包含两个类的代表，但是可以排除C的进一步测试，或者因为属性不足并且不能在 C中的对象，或者因为每个属性被判断为与C中的对象类无关。在这种情况下，有必要产生一个用类信息标记的叶子，但C中的对象不是全部相同的类。有两种可能性。 类的概念可以被概括为允许在区间（0,1）中的值p /（p + n），0.8的类（说）被解释为属于具有概率0.8s的类P. 另一种方法是选择更多的类，即如果p n则将叶分配给类P，如果p n则将叶分配给类

34、N，如果p = n，则将叶分配给类N. 第一种方法使C中的对象上的误差的平方和最小化，而第二种方法使C中的对象上的绝对误差的和最小化。如果目的是最小化预期误差，则可以预期第二种方法 是优越的，实际上已经发现是这种情况。已经进行了几项研究，以了解这种修改过程在不同噪声水平下如何保持（Quinlan 1983b，1985a）。 一个这样的研究在这里基于前面提到的任务与551个对象和39二进制值属性。 在每个实验中，整个对象集合被人为破坏，如下所述，并用作训练集以产生决策树。 然后每个对象被重新损坏，由该树分类并且确定错误率。 将该过程重复20次以得到更可靠的平均值。在这项研究中，值被破坏如下。应用

35、于值的n的噪声水平意味着以概率n，真实值被从可能出现的值中随机选择的值代替。表2示出了当噪声水平从5 至100被应用于最噪声敏感属性的值，所有属性的值同时应用于类信息。该表显示观察到的相当不同的降解形式。破坏类信息产生误差的线性增加，使得当所有类信息都是噪声时，所得到的解决树完全随机地对对象进行分类。单个属性中的噪声没有显着的效果。然而，所有属性中的噪声一起导致到达峰值和下降的误差相对快速增加。峰值有些令人担忧，可以解释如下。令C是分别包含来自类P的p和来自类N的n的对象的集合。在大约507o的噪声水平，用于构造决策树的算法仍然可以找到相关的属性来分支，即使该树对未看见但同样有噪声的对象的性能

36、将是基本上随机的。假设用于C的树将对象分类为具有可能性p /（n + p）的类P.如果具有与C中的那些相似的类分布的对象被该树分类，则期望的错误由下式给出丄.（1 _ 丄）+ 丄（1 丄）= p + np + n p + np + n (p + n)2然而，在非常高的噪声水平，算法将找到所有属性无关，并将一切都分类为更频繁的类; 假定不失一般性，这个类是P.在这种情况下的预期误差是p + np + np + n其小于上述表达式，因为我们假设p大于n。 因此，当噪声变得更强烈时，误差的下降是卡方截止发挥作用的结果。该表提出了低水平的噪声不会导致树木建造机器落在悬崖上的点。对于这个任务，单个属性中

37、的5噪声水平产生小于2的性能下降， ; 在所有属性中的5V0噪声水平一起产生分类性能的1270劣化; 而类信息中的类似噪声电平导致3的降级。 对于其他感应任务已经获得了类似的数字。一个有趣的点来自其他实验，其中使用从未破坏的训练集形成的正确的决策树来对其描述被破坏的对象进行分类。 这种情况对应于在受控和消毒的实验室条件下形成分类规则，然后使用它来对现场中的对象进行分类。 对于更高的噪声水平，发现正确的决策树对损坏的数据的性能劣于从损坏到相似水平的数据形成的不完全决策树的性能！ （该现象具有与上面针对表2中的峰值给出的解释类似的解释。）道德似乎在于，如果这些相同的属性将是主题，则从训练集中的属性

38、信息中消除噪声是相反的 当诱导决策树投入使用时到高噪声水平。6.未知的属性值上一节检查了对树构建过程的修改，使其能够处理嘈杂或损坏的值。这部分涉及在实践中也出现的联合问题：未知的属性值。为了继续以前的医疗诊断示例，当形成训练集的患者病例历史不完整时应该做什么？围绕该问题的一种方式试图通过利用由上下文提供的信息来填充未知值。使用前面的符号，让我们假设对象的集合C包含属性A的值为未知的对象的集合C. ASSIS TANT（Kononenko等人，1984）使用贝叶斯形式来确定对象具有A的值A的可能性，通过检查C中的A的值的分布作为其类的函数。假设所讨论的对象属于类P.对象具有属性A的值Ai的概率可

39、以表示为其中pi和p的计算限于其值A已知的C的那些成员。已经确定了未知值在A的可能值上的概率分布，该方法可以选择最可能的值，或者将对象划分为分数对象，每个具有根据上述概率加权的A的可能值。Alen Shapiro（私人通信）建议使用决策树方法来确定属性的未知值。让C是由属性A的值被定义的那些对象组成的C的子集。在Cr，原来第九十七页 类（P或N）被认为是另一个属性，而属性A的值变为要确定的类5。 也就是说，用于构造用于从其他属性和类中确定属性A的值的决策树。 当被配置时，该决策树可以用于对C-Cr中的每个对象进行“分类”，并且结果被指定为A的未知值。虽然这些用于确定未知属性值的方法在纸上看起来

40、不错，但即使当一个属性的单个值未知时，它们也给出不可信的结果; 正如可能预期的，当几个属性的几个值未知时，它们的性能更差。 再次考虑551对象39属性任务。 我们可能会问，当被要求填写单个未知属性值时，方法执行得如何。 表3示出了对于三个最重要的属性中的每一个，每个方法不能用未知值替换其正确值的次数的比例。 为了比较，该表还显示了简单策略的相同图：始终用其最常见的值替换属性的未知值。 贝叶斯方法给出的结果几乎不如简单策略给出的结果，而决策树方法使用更多的上下文，因此更准确，但仍然给出令人失望的结果。而不是试图猜测未知的属性值，我们可以将未知，作为每个属性的新的可能值，并以与其他值相同的方式处理

41、它。 这可能导致异常情况，如以下示例所示。 假设A是具有值（Ai，A2）的属性，并且让C是对象的集合Pi = 2 P2 = 2ni = 2 ri2 = 2给出E（A）的1位的值。 现在让A是相同的属性，除了A的值为A的对象中的一个具有未知的A值。 A具有值AS，A; 2，A3 =未知），因此相应的值可能是 Pi = 1P; 2 = 2 p3 = 1 ni = 2 n2 = 2 n3 = 0第九十八页 导致E（A / f）的值为0.84位。根据先前开发的选择标准，A; 现在似乎给出了比A更高的信息增益。因此，获取未知值可能显然增加属性的期望性，结果完全反对常识。 结论是，处理*未知，作为一个单独

42、的值不是解决问题的解决方案。已经发现工作良好的一种策略如下。 令A是具有值Ai，A2，. AVj的属性。 对于对象的一些集合C，使具有A的值Ai的对象的数量是pi和ni，并且令pu和nu分别表示具有未知值A的类别P和N的对象的数量。当信息 评估属性A的增益，具有未知值的这些对象与这些值在C中的相对频率成比例地分布在A的值上。因此，增益被评估为如同pi的真实值由Pi + pu ratii whereratiiPi + njI； (Pi + n和类似地对于m。 （该表达式具有以下属性：未知值只能减小属性的信息增益。）当通过选择标准选择了属性时，在形成用于子集的决策树之前丢弃具有该属性的未知值的对象

43、Q 。故事的另一半是在分类期间如何处理未知属性值。 假设使用希望在属性A上分支但是属性A的对象值未知的决策树来对对象进行分类。 正确的过程将采用对应于真实值A i的分支，但是，由于该值是未知的，唯一的选择是探索所有分支而不忘记一些比其他分支更可能。在概念上，假设与被分类的对象一起，我们已经传递了具有某个值T的令牌。在上面的情况中，Ai的每个分支然后使用值的令牌T ratii即给定令牌值与所有比例成比例地分布在所有可能的值上。 传递给分支的值可以通过对该对象具有未知值的其他属性的后续测试来进一步分布。 代替到叶的单个路径，现在可以有许多，每个由其令牌值限定。 在叶子处的这些令牌值对于每个类求和，

44、分类的结果是第九十九页该类具有较高的值。 在可能的类上的值的分布也可以用于计算分类的置信水平。尽管可能是直接的，但是已经发现这个过程给出了非常优雅的退化，因为未知值的发生率增加。图5将对现在熟悉的任务的实验结果与551个对象和-39属性进行求和。各种无知的水平，类似于早先的噪音水平，有20个repititions在每个级别。对于无效级别为fn的每个运行，创建551个对象的副本，将每个属性的每个值替换为具有m百分比概率的“未知*”。如上所述形成了这些（不完全）对象的决策树，然后用于对以相同方式损坏的每个对象的新副本进行分类。该图表明，无知级别的性能的退化是逐渐的。在实践中，当然，无知级别甚至高达

45、10是不可能的 - 这将对应于每十个目标描述中的一个值的未知的平均值。即使如此，从这样的补丁训练集产生的决策树正确地分类了近似百分之九十的具有未知值的对象。当具有未知值的对象使用正确的决策树分类时，观察到低得多的退化水平。这种处理假定没有关于未知属性的信息可用。 Catlett（1985）通过允许对Shafer符号中的属性值的部分了解（Garvey，Lowrance和Fischler，1981），使这种方法更进一步。 这种符号允许对对象可能具有的属性的可能值的任何子集或子集进行概率性确定。7.选择标准最近注意力集中在用于选择最佳基于属性的测试以形成决策树的根的评估函数。 回想前面描述的标准选择

46、获得大多数信息的属性。 在他们的实验过程中，第一百页 Bratko5s组遇到一个医学归纳问题，其中通过增益标准（患者的年龄，具有九个值范围）选择的属性被专家判断为与其他属性相关性较低），这种情况在其他任务中也被记录，提示 Kononenko等人（1984）建议，增益标准往往有利于具有许多价值的属性。分析支持这一发现。 令A是具有值A2，.的属性。 . Av，并且A是由A通过将值之一分成两个而形成的属性。 如果A的值对于手头的诱导任务足够精细，我们不会期望这种细化增加A的有用性。相反，可以预期过度的细度将倾向于模糊训练集中的结构，使得A， 实际上比A更不有用。然而，可以证明增益（A 1）大于或等

47、于增益（A），当它们的类别的比例对于 原值。 一般来说，增益（A ）将超过增益（A），结果是第4节的评估函数将优选于A.通过类比，具有更多值的属性将倾向于优先于具有较少值的属性。作为另一种查看问题的方式，让A是具有随机值的属性，并假设A的可能值的集合大到足以使得不可能，训练集中的两个对象具有相同的值A. 属性将具有最大信息增益，因此增益准则将其选择为决策树的根。 这将是一个非常差的选择，因为A的值是随机的，不包含与训练集中的对象类相关的信息。ASSISTANT（Kononenko等人，1984）通过要求所有测试仅具有两个结果来解决这个问题。 如果我们如前所述具有v值Ai，A2的属性A，. Av，决策树不再具有每个可能值的分支。 相反，选择值的子集S，并且树具有两个分支，一个用于集合中的所有