决策树归纳

决策树归纳关键词：分类，归纳，决策树，信息理论，知识获取，专家系统摘要：通过实例的归纳推理构建基于知识的系统的技术已经在若干实际应用中成功地证明。本文总结了合成在各种系统中使用的决策树的方法，并且详细描述了一个这样的系统ID3。最近研究的结果显示可以修改该方法以处理嘈杂和/或不完整的信息的方式。讨论了报告的基本算法的缺点，并且比较了克服它的两种手段。本文结束了当前研究方向的插图。1.介绍由于人工智能首先在1950年代中期被认可为一门学科，机器学习已成为一个中心研究领域。可以给出这个突出的两个原因。学习的能力是智能行为的标志，所以任何将智力理解为现象的尝试都必须包括对学习的理解。更具体地，学习提供了构建高性能系统的潜在方法。学习研究由不同的子领域组成。在一个极端，有自适应系统监视自己的性能，并尝试通过调整内部参数来改善它。这种方法，大部分早期学习工作的特点，产生了自我完善的游戏程序（Samuel，1967），平衡杆（Michie，1982），解决问题（Quinlan，1969）和许多其他领域。一个完全不同的方法认为学习是以概念形式获取结构化知识（Hunt，1962;Winston，1975），•歧视网（Feigenbaum和Simon，1963）或生产规则（Buchanan，1978）。后一种机器学习的实际重要性已经被低估了，由基于知识的专家系统的出现。正如他们的名字所暗示的，这些系统由显式地表示而不是在算法中隐含的知识提供动力。驱动开拓性专家系统所需的知识通过领域专家和知识工程师之间的长期互动来编写。虽然通过该方法的典型的知识解释速率是每人每天的几个规则，但是用于复杂任务的专家系统可能需要数百或甚至数千个这样的规则。很明显，知识获取的面试方法不能跟上对专家系统的迅速增长的需求;Feigen-baum（1981）认为这是“瓶颈问题”。这种观点刺激了机器学习方法作为一种解释知识的手段的研究（Michie，1983）。本文集中在一个微观的机器学习和一系列的学习系统，已被用来建立一个简单的类型的知识为基础的系统。第2节概述了这个家庭的特点，并介绍其成员。所有这些系统解决了从示例中引入决策树的同一任务。在更完整地说明这个任务之后，在第4节中详细描述了一个系统（ID3）。第5和6节给出了ID3的扩展，使其能够处理噪声和不完整的信息。对感应算法的中心方面的回顾揭示了第7节中阐述的可能的改进。本文结束时提出了两个新的举措，提出了家庭可能成长的方向的一些想法。2.TDIDT系列学习系统Carbonell，Michalski和Mitchell（1983）确定了机器学习系统可以分类的三个主要方面：•使用的基础学习策略;•由系统获得的知识的表示;•和系统的应用程序域。本文涉及一系列在这些维度上具有强共同联系的学习系统。以相反的顺序取得这些特征，这些系统的应用领域不限于智力活动的任何特定领域，例如化学或象棋;它们可以应用于任何这样的区域。虽然它们是通用系统，但它们所涉及的应用程序都涉及分类。学习的产物是一种程序性知识，其可以将迄今未看见的对象分配给指定数量的不相交类别中的一个。分类任务的示例有：1.从症状诊断医学状况，其中类别可以是各种疾病状态或可能的治疗;2.确定棋位的游戏理论价值，分类用白色赢得，白色输和平局;和3.从大气层观察来判断严重的雷暴是不可能的，可能的或很可能的。可能看起来分类任务只是程序性任务的一个微小的子集，但即使是诸如机器人规划的活动也可以重新分类为分类问题（Dechter和Michie，1985）。这个家庭的成员的特点是他们代表知识作为决策树。这是相对简单的知识形式主义，缺乏语义网络或其他一阶表示的表达能力。作为这种简单性的结果，在TDIDT系列中使用的学习方法比在能够以更强大的语言表达其学习的结果的系统中使用的学习方法复杂得多。然而，仍然可能以决策树的形式生成能够解决具有实际意义的困难问题的知识。基本策略是从例子的非增量学习。向系统呈现与分类任务相关的一组案例，并且由示例中的频率信息指导而不是由给出示例的特定顺序从上而下开发判定树。这与诸如在MARVIN（Sammut，1985）中采用的增量方法形成对比，其中用指导员进行对话以“调试”部分正确的概念，并且由Winston（1975）使用，其中示例是每次分析一个，每个产生发展概念的小变化;在这两个系统中，呈现示例的顺序是最重要的。这里描述的系统搜索给定示例中的模式，因此必须能够在学习期间的许多阶段检查和重新检查所有模式。共享这种数据驱动方法的其他知名程序包括BACON（Langley，Bradshaw和Simon，1983）和INDUCE（Michalski，1980）。因此，总之，这里描述的系统开发用于分类任务的决策树。这些树从树的根开始构造并且向下到其叶。家庭的回文名称强调，其成员执行决策树的7bp-e）/nduction。开发分类规则的示例对象仅仅通过它们的一组属性或属性的值是已知的，并且决策树依次以这些相同的属性表示。示例本身可以以两种方式组装。它们可能来自形成观察历史的现有数据库，例如在诊断中心积累的某些医学领域的患者记录。这种对象给出可靠的统计图像，但是，由于它们不以任何方式组织，它们可以是在记录期间没有遇到的冗余或省略的情况。另一方面，对象可以是域专家准备的精心挑选的教程示例集合，每个对与完整和正确的分类规则具有某些特定相关性。专家可能会为了避免冗员，并包括罕见病例的例子。虽然系统系统将以令人满意的方式处理任一类型的收集，但应当提及的是，较早的TDIDT系统被设计为具有历史记录，方法，但是这里描述的所有系统现在经常与教程一起使用（Michie，1985）。CLS(1963)IID3(1979)(_____|__IACLS(1981)ASSISTANT(1984)Expert-Ease(1983)EX-TRAN(1984)RuleMaster(1984)图LTDIDT系列树。图1显示了TDIDT系统的系列树。这个家族的族长是Hunfs概念学习系统框架（Hunt，MarinandStone，1966）。CLS构造了一个尝试最小化对对象进行分类的成本的决策树。该成本具有两种类型的分量：确定对象所展现的属性A的值的测量成本，以及当其实际类别为K时，确定对象属于类别J的错误分类成本。CLS使用类似于最小值。在每个阶段，CLS将可能的决策树的空间探索到固定深度，选择动作以使该有限空间中的成本最小化，然后在树中向下移动一个级别。根据所选择的预期深度，CLS可能需要大量的计算，但是能够在显示的对象中发现细微的模式。ID3（Quinlan，1979，1983a）是一系列从CLS开发的程序之一，响应由唐纳德·Michie提出的具有挑战性的诱导任务，从单独的基于模式的特征来决定在King-Rook中的特定棋位置vs国王骑士的游戏失去了骑士^侧在固定数量的层。ID3的完整描述出现在第4节中，因此在这里要注意的是，它在迭代外壳中嵌入了树构建方法，并且使用信息驱动的评估函数放弃了CLS的成本驱动的前瞻。ACLS（Paterson和Niblett，1983）是ID3的概括。CLS和ID3都要求用于描述对象的每个属性只具有来自指定集合的值。除了此类型的属性，ACLS允许具有不受限制的整数值的属性。处理这种属性的能力允许ACLS应用于困难的任务，如图像识别（Shepherd，1983）。ASSISTANT（Kononenko，Bratko和Roskar，1984）也承认ID3是其直接祖先。它在许多方面与ID3不同，其中一些将在后面的章节中详细讨论。ASSISTANT通过允许具有连续（实数）值的属性进一步推广ACLS的整数值属性。ASSISTANT不是坚持类是不相交的，而是允许它们形成层次结构，使得一个类可以是另一个的更细分割。ASSISTANT不以ID3的方式迭代地形成决策树，而是包括用于从可用对象中选择训练集的算法。ASSISTANT已经用于具有有希望结果的多个医学领域。图中最底部的三个系统是ACLS的商业衍生品。虽然它们没有显着提高基础理论，但它们包含了许多用户友好的创新和实用程序，加快了生成和使用决策树的任务。他们都有工业成功的信用。例如，西屋电气的水反应堆部门指出了一个燃料富集应用，其中该公司能够通过使用其中一个，每年增加1000多万美元的收入。3.感应任务我们现在给出一个更精确的感应任务的说明。基础是以属性集合的形式描述的对象的宇宙。每个属性测量对象的一些重要特征，并且在这里将限制为采用一组离散的，互斥的值（通常是小的）。例如，如果对象是星期六早上，分类任务涉及天气，属性可能是天气，值为{晴，阴，雨）温度，值（酷，温和，湿），湿度，值（高，正常），风，值（真，假）总之，属性提供了用于表征宇宙中的对象的零阶语言。特定的星期六早上可能被描述为天气：阴温度：冷湿度：正常大风：假的Universe中的每个对象都属于一组互斥类中的一个。为了简化以下处理，我们将假定只有两个这样的类表示为P和N，但是扩展到任何数量的类不是困难的。在两类诱导任务中，类P和N的对象有时分别被称为被学习的概念的肯定实例和否定实例。另一个主要成分是其类别已知的对象的训练集合。归纳任务是开发一个分类规则，可以从属性的值确定任何对象的类。直接的问题是属性是否提供足够的信息来做到这一点。特别地，如果训练集包含对于每个属性具有相同值但仍属于不同类的两个对象，则显然不可能仅参考给定属性来区分这些对象。在这种情况下，属性将被称为训练集的因而用于诱导任务。如上所述，分类规则将被表示为决策树。表1显示了一个使用“星期六上午，属性”的小训练集。每个对象的每个属性的值与对象的类一起显示（这里，类P的早晨适用于一些未指定的活动）。在图2中给出了对训练集中的每个对象进行正确分类的决策树。决策树的叶子是类名，其他节点表示基于属性的测试，每个可能结果都有一个分支。为了对对象进行分类，我们从树的根开始，评估测试，并采取适当的分支结果。该过程继续直到遇到叶，在该时间对象被断言为属于由叶命名的类。采用图2的决策树，该过程包括在该部分的开始处作为示例出现并且不是训练集的成员的对象应当属于类别P.注意，只有子集的属性可能在从决策树的根到叶的特定路径上遇到;在这种情况下，在确定类之前只测试outlook属性表1.一个小的训练集No.AttributesClassOutlookTemperatureHumidityWindy1sunnyhothighfalseN2sunnyhothightrueN3overcasthothighfalseP4rainmildhighfalseP5raincoolnormalfalseP6raincoolnormaltrueN7overcastcoolnormaltrueP8sunnymildhighfalseN9sunnycoolnormalfalseP10rainmildnormalfalseP11sunnymildnormaltrueP12overcastmildhightrueP13overcasthotnormalfalseP14rainmildhightrueNOutlook图2.一个简单的决策树如果属性足够，则总是可以构造正确地分类训练集中的每个对象的决策树，并且通常存在许多这样的正确决策树。归纳的本质是移动超出训练集，即构造决策树，其不仅正确地分类来自训练集的对象，而且还正确地分类其他（未见的）对象。为了做到这一点，决策树必须捕获一个对象类和它的属性值之间的一些有意义的关系。给定在两个决策树之间的选择，其中每个决策树在训练集合上是正确的，似乎更倾向于更简单的决策树，因为它更可能捕获问题中固有的结构。因此，更简单的树将被期望在训练集之外正确地分类更多的对象。例如，图3的决策树对于表1的训练集合也是正确的，但是其更大的复杂性使其被怀疑为训练集合的“解释”。(对于更简单的树的偏好，这里作为Occam的剃刀的常识应用程序呈现，也通过分析支持。Pearl（1978b）和Quinlan（1983a）使用不同的形式从一