文档介绍：决策树归纳
关键词:分类,归纳,决策树,信息理论,知识获取,专家系统
摘要: 通过实例的归纳推理构建基于知识的系统的技术已经在若干实际应用中成功地证明。本文总结了合成在各种系统中使用的决策树的方法,并且详细描述了一个这样的系统ID3。最近研究的结果显示可以修改该方法以处理嘈杂和/或不完整的信息的方式。讨论了报告的基本算法的缺点,并且比较了克服它的两种手段。本文结束了当前研究方向的插图。
由于人工智能首先在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)确定了机器学****系统可以分类的三个主要方面:
•使用的基础学****策略;
•由系统获得的知识的表示;
•和系统的应用程序域。
本文涉及一系列在这些维度上具有强共同联系的学****系统。
以相反的顺序取得这些特征,这些系统的应用领域不限于智力活动的任何特定领域,例如化学或象棋; 它们可以应用于任何这样的区域。虽然它们是通用系统,但它们所涉及的应用程序都涉及分类。学****的产物是一种程序性知识,其可以将迄今未看见的对象分配给指定数量的不相交类别中的一个。分类任务的示例有:
,其中类别可以是各种疾病状态或可能的治疗;
,分类用白色赢得,白色输和平局; 和
,可能的或很可能的。
可能看起来分类任务只是程序性任务的一个微小的子集,但即使是诸如机器人规划的活动也可以重新分类为分类问题(Dechter和Michie,1985)。
这个家庭的成员的特点是他们代表知识作为决策树。这是相对简单的知识形式主义,缺乏语义网络或其他一阶表示的表达能力。作为这种简单性的结果,在TDIDT系列中使用的学****方法比在能够以更强大的语言表达其学****的结果的系统中使用的学****方法复杂得多。然而,仍然可能以决策树的形式生成能够解决具有实际意义的困难问题的知识。
基本策略是从例子的非增量学****向系统呈现与分类任务相关的一组案例,并且由示例中的频率信息指导而不是由给出示例的特定顺序从上而下开发判定树。这与诸如在MARVIN(Sammut,1985)中采用的增量方法形成对比,其中用指导员进行对话以“调试”部分正确的概念,并且由Winston(1975)使用,其中示例是每次分析一个,每个产生发展概念的小变化;在这两个系统中,呈现示例的顺序是最重要的。这里描述的系统搜索给定示例中的模式,因此必须能够在学****期间的许多阶段检查和重新检查所有模式。共享这种数据驱动方法的其他知名程序包括BACON(Langley,Bradshaw和Simon,1983)和INDUCE(Michalski,1980)。
因此,总之,这