人工智能与专家系统第七章

第七章机器学习7.1概述7.2归纳学习7.3决策树学习7.4基于实例的学习本章小结课后练习题普通高等院校“十二五〞规划教材第七章机器学习机器能否像人类一样具有学习才干呢？1959年美国的塞缪尔设计了一个下棋程序，这个程序具有学习才干，它可以在不断的对弈中改善本人的棋艺。4年后，这个程序战胜了设计者本人。又过了3年，这个程序战胜了美国一个坚持8年之久的常胜不败的冠军。它向人们展现了机器学习的才干。本章主要引见机器学习的根本概念和归纳学习、决策树学习、基于实例的学习等详细的机器学习方法，希望读者能对这一领域有一个初步的了解和认识。普通高等院校“十二五〞规划教材7.1概述机器学习的研讨是根据生理学、认知科学等对人类学习机理的了解，建立人类学习过程的计算模型或认识模型，开展各种学习实际和学习方法，研讨通用的学习算法并进展实际上的分析，建立面向义务的具有特定运用的学习系统。这些研讨目的相互影响相互促进。自从1980年在卡内基-梅隆大学召开第一届机器学术研讨会以来，机器学习的研讨任务开展很快，已成为中心课题之一。普通高等院校“十二五〞规划教材7.1.1什么是机器学习1．关于机器学习的定义Langley(1996)定义的“机器学习是一门人工智能的科学，该领域的主要研讨对象是人工智能，特别是如何在阅历学习中改善详细算法的性能。〞TomMitchell的机器学习(1997)对信息论中的一些概念有详细的解释,其中定义机器学习时提到，“机器学习是对能经过阅历自动改良的计算机算法的研讨〞Alpaydin(2004)也提出本人对机器学习的定义，“机器学习是用数据或以往的阅历，以此优化计算机程序的性能规范。〞顾名思义，机器学习是研讨如何运用机器来模拟人类学习活动的一门学科。普通高等院校“十二五〞规划教材7.1.1什么是机器学习稍为严厉的提法是：机器学习是一门研讨机器获取新知识和新技艺，并识别现有知识的学问。这里所说的“机器〞，指的就是计算机，如今是电子计算机，以后还能够是中子计算机、光子计算机或神经计算机等等。普通高等院校“十二五〞规划教材7.1.1什么是机器学习2．机器学习的开展简史最早的具有学习才干的程序是年美国的设计的跳棋程序。第一阶段是20世纪50到60年代的探求阶段。主要成果有：感知机(Perceptron)；Friedberg等模拟随机突变和自然选择过程的程序；Hunt等的决策树归纳程序CLS。第二阶段是20世纪70年代的开展阶段。主要系统和算法包括：Winston的积木世界学习系统；Michalski基于逻辑的归纳学习系统AQVAL；Michalski和Chilausky的AQII；Quinlan的ID3程序；Mitchell的版本空间方法。普通高等院校“十二五〞规划教材7.1.1什么是机器学习第三阶段是20世纪80年代至今的鼎盛阶段。主要成果有：一方面传统的符号学习的各种方法已日臻完善。另一方面，机器学习的根底实际的研讨越来越引起人们的注重。3．机器学习的普通步骤图7.1.1机器学习的根本系统构造模型普通高等院校“十二五〞规划教材7.1.1什么是机器学习“环境〞是指外部信息的来源，它为系统的学习提供有关信息；“学习〞是系统的学习构造，从环境中获得外部信息，然后经分析、综合、类比和归纳等思想过程获得知识，并存入知识库中更新知识库；“知识库〞用于存放由学习得到的知识，在存储时要适当的组织，便于运用和维护；“执行〞环节是基于学习得到的新的知识库，它执行一系列的义务。此外还需将执行结果信息反响给学习环节，以完成对新“知识库〞的评价，指点进一步的学习任务。普通高等院校“十二五〞规划教材7.1.1什么是机器学习图7.1.2机器系统学习环节的普经过程普通高等院校“十二五〞规划教材7.1.2机器学习方法的分类1．按学习时所用的分类方法进展分类：〔1〕机械式学习〔2〕示教学习〔3〕类比学习〔4〕解释学习2．按推理的战略分类〔1〕演绎学习〔2〕归纳学习3．按综合要素分类〔1〕衔接学习〔2〕分析学习〔3〕分类器系统普通高等院校“十二五〞规划教材7.1.3机器学习中的推理方法〔1〕演绎推理演绎推理是结论可从叫做前提的知现实必然的得出的推理。假设前提为真，那么结论必然为真。〔2〕归纳推理所谓归纳推理，就是从个别性知识推出普通性结论的推理。归纳推理的前提是其结论的必要条件。〔3〕类比推理类比推理是根据两个或两类对象有部分属性一样，从而推出它们的其他属性也一样的推理。简称类推、类比。它是以关于两个事物某些属性一样的判别为前提，推出两个事物的其他属性一样的结论的推理。普通高等院校“十二五〞规划教材7.2归纳学习归纳学习是人工智能中开展较为成熟，并得到广泛的研讨和运用的学习方法。它是是由一些实例或反例，经过归纳推理得出该概念的普通描画。实现实例到规那么的归纳推理过程就是归纳学习过程。它的普通操作是泛化和特化，泛化用来扩展假设的语义信息，以使其可以包含更多的正例，运用于更多的情况。特化是泛化的相反的操作，用于限制概念描画的运用范围。普通高等院校“十二五〞规划教材7.2.1归纳学习的根本概念归纳是指从个别到普通，从部分到整体的推论行为。归纳推理是运用归纳方法所进展的推理，即从足够多的实例中归纳出普通性的知识，它是一种从个别到普通的推理。归纳学习是运用归纳推理进展学习的一种学习方法。归纳学习旨在从大量的阅历数据中归纳抽取出普通的断定规那么和方式，是从特殊情况推导出普通规那么的学习方法。它的目的是构成合理的能解释知现实和预见新现实的普通性结论。归纳学习由于依赖于阅历数据，因此又被称为阅历学习；由于依赖于数据间的类似性，因此也被称为基于类似性的学习。普通高等院校“十二五〞规划教材7.2.1归纳学习的根本概念1．归纳学习的双空间模型图7.2.1双空间模型普通高等院校“十二五〞规划教材7.2.1归纳学习的根本概念2．归纳学习的分类归纳学习按其有无教师指点可分为例如学习和察看与发现学习。例如学习，又叫做概念获取——它的义务是确定概念的普通描画，这个描画应能解释一切给定的正例，并排除一切给定的反例，由于学习是根据教师分好类的正反例进展学习，因此是有教师学习。察看与发现学习又称为描画的泛化——这类学习没有教师的协助，它要产生解释一切或大多数察看的规律和规那么，这些都是未经分类的察看学习或是由系统本身的功能去发现。普通高等院校“十二五〞规划教材7.2.1归纳学习的根本概念归纳学习还可以划分为单概念学习和多概念学习两类。典型的单概念学习系统包括米切尔的基于数据驱动的变型空间法，昆兰的ID3方法，狄特利希和米哈尔斯基提出的基于模型驱动的Induce算法。典型的多概念学习方法和系统有米哈尔斯基的、元和程序等。多概念学习义务可以划分成多个单概念学习的义务来完成。多概念学习与单概念学习的差别在于多概念学习必需处置概念之间的冲突问题。普通高等院校“十二五〞规划教材7.2.2变型空间学习1．变型空间的构造7.2.2变型空间排序的关系普通高等院校“十二五〞规划教材7.2.2变型空间学习2.候选项删除算法算法过程：〔1〕初始化H为整个概念空间〔规那么空间〕。〔2〕接受一个新的示教例子。〔3〕反复步骤〔2〕，直到G=S，且使这两个集合都只含有一个元素为止。〔4〕输出H中的概念，即输出G或S。普通高等院校“十二五〞规划教材7.3决策树学习决策树学习是运用最广泛的归纳学习，特别是在专家系统、工业控制过程、金融保险预测以及医疗诊断等领域。假设学习的义务是对一个大的实例集合做概念分类的归纳定义，而这些例子都是用一些无构造的属性值对来表示，那么可以采用决策树学习算法。亨特(Hunt)的概念学习系统CLS是一种早期的基于决策树的归纳学习系统。1979年，昆兰对此进展了开展，提出了ID3算法，该算法不仅能方便地表示概念属性值信息的构造，而且能从大量实例数据中有效地生成相应的决策树模型。普通高等院校“十二五〞规划教材7.3.1决策树及构造算法所谓决策树是一个类似流程图的树构造，其中树的每个结点对应一个特征〔属性〕变量值的检验，每个分枝表示检验结果，树枝上的叶结点代表所关怀的因变量的取值，最顶端的结点称为根结点，内结点用矩形框表示，叶结点用椭圆框表示。从根结点到每个叶结点都有独一的一条途径，这条途径就是一条决策“规那么〞。假设每个内结点都恰好有两个分枝，那么称为二叉树，类似可定义多叉树，在一切的决策树中，二叉树最为常用。普通高等院校“十二五〞规划教材7.3.1决策树及构造算法

普通高等院校“十二五〞规划教材7.3.2根本的决策树学习算法

普通高等院校“十二五〞规划教材7.3.2根本的决策树学习算法

普通高等院校“十二五〞规划教材7.4基于实例的学习基于实例的学习采用保管实例本身的方法来表达从实例集提取出的知识，并将未知的新实例与现有的类知的实例联络起来进展操作。这种方法直接在样本上任务，不需求建立规那么。基于实例的学习方法包括最近邻法、部分加权回归法、基于范例的推理法等等。基于实例的学习只是简单地把训练样例存储起来，对这些实例进展泛化的任务被推迟到必需分类新的实例时，所以也被称为消极学习法。普通高等院校“十二五〞规划教材7.4.1k-近邻算法最近邻法经过间隔函数来判别训练集中的某个实例与哪个位置的测试实例最接近，一旦找到最接近的训练实例，那么最接近实例所属的类就被预测为测试实例的类。本质性的任务在对新的实例进展分类时进展，经过间隔函数将每个新实例与现有的实例进展比较，利用最接近的现有实例赋予新实例类别，这就是最近邻分类方法。有时运用多个最近邻实例，并且用最近的K个邻居所属的多数类〔假设类是数值型，就是经间隔加权的平均值〕赋予新的实例类别值，这就是K-近邻法。普通高等院校“十二五〞规划教材7.4.2间隔加权最近邻法对K-近邻算法的一个改良是对K个近邻的奉献进展加权，越近的间隔赋予越大的权值，这就是所谓的间隔加权最近邻法。K-近邻算法的一切变体都只思索K个近邻用以分类查询点，假设按间隔加权，那么可以允许一切的训练样例都影响实例Xq的分类，由于间隔非常远的实例影响很小。思索一切样例的独一缺乏是会使分类进展得更慢。假设分类一个新实例时，思索一切的训练样例，可以称其为全局法；假设仅思索接近的训练样例，那么称为部分法。普通高等院校“十二五〞规划教材7.4.3基于范例的学习1．基于范例推理的普经过程〔1〕联想记忆〔2〕类比映射〔3〕获得求解方案〔4〕评价2．范例的表示(1)SUM_NAMEslots：简记为SMU槽。(2)Constraintslots：简记为CON槽。(3)Taxonomyslots：简记为TAX槽。(4)Causalityslots：简记为CAU槽。(5)Similarityslots：简记为SIM槽。普通高等院校“十二五〞规划教材7.4.3基于范例的学习(6)Partonomyslots：简记为PAR槽。(7)Csaeslots：简记为CAS槽。(8)Theoryslots：简记为THY槽。3．范例组织〔1〕范例内容〔2〕范例索引4．范例的检