1、第七章 机器学习,7.1 概述7.2 归纳学习7.3 决策树学习7.4 基于实例的学习本章小结课后练习题,普通高等院校“十二五”规划教材,第七章 机器学习,机器能否像人类一样具有学习能力呢？1959年美国的塞缪尔设计了一个下棋程序，这个程序具有学习能力，它可以在不断的对弈中改善自己的棋艺。4年后，这个程序战胜了设计者本人。又过了3年，这个程序战胜了美国一个保持8年之久的常胜不败的冠军。它向人们展示了机器学习的能力。本章主要介绍机器学习的基本概念和归纳学习、决策树学习、基于实例的学习等具体的机器学习方法，希望读者能对这一领域有一个初步的了解和认识。,普通高等院校“十二五”规划教材,7.1 概述,
2、机器学习的研究是根据生理学、认知科学等对人类学习机理的了解，建立人类学习过程的计算模型或认识模型，发展各种学习理论和学习方法，研究通用的学习算法并进行理论上的分析，建立面向任务的具有特定应用的学习系统。这些研究目标相互影响相互促进。自从1980年在卡内基-梅隆大学召开第一届机器学术研讨会以来，机器学习的研究工作发展很快，已成为中心课题之一。,普通高等院校“十二五”规划教材,7.1.1 什么是机器学习,1关于机器学习的定义Langley(1996)定义的“机器学习是一门人工智能的科学，该领域的主要研究对象是人工智能，特别是如何在经验学习中改善具体算法的性能。”TomMitchell的机器学习(1
3、997)对信息论中的一些概念有详细的解释,其中定义机器学习时提到，“机器学习是对能通过经验自动改进的计算机算法的研究”Alpaydin(2004)也提出自己对机器学习的定义，“机器学习是用数据或以往的经验，以此优化计算机程序的性能标准。”顾名思义，机器学习是研究如何使用机器来模拟人类学习活动的一门学科。,普通高等院校“十二五”规划教材,7.1.1 什么是机器学习,稍为严格的提法是：机器学习是一门研究机器获取新知识和新技能，并识别现有知识的学问。这里所说的“机器”，指的就是计算机，现在是电子计算机，以后还可能是中子计算机、光子计算机或神经计算机等等。,普通高等院校“十二五”规划教材,7.1.1
4、什么是机器学习,2机器学习的发展简史最早的具有学习能力的程序是 年美国的 设计的跳棋程序。第一阶段是20世纪50到60年代的探索阶段。主要成果有：感知机(Perceptron)；Friedberg等模拟随机突变和自然选择过程的程序；Hunt等的决策树归纳程序CLS。第二阶段是20世纪70年代的发展阶段。主要系统和算法包括：Winston的积木世界学习系统；Michalski基于逻辑的归纳学习系统AQVAL；Michalski和Chilausky的AQII；Quinlan的ID3程序；Mitchell的版本空间方法。,普通高等院校“十二五”规划教材,7.1.1 什么是机器学习,第三阶段是20世纪
5、80年代至今的鼎盛阶段。主要成果有：一方面传统的符号学习的各种方法已日臻完善。另一方面，机器学习的基础理论的研究越来越引起人们的重视。3机器学习的一般步骤图7.1.1机器学习的基本系统结构模型,普通高等院校“十二五”规划教材,7.1.1 什么是机器学习,“环境”是指外部信息的来源，它为系统的学习提供有关信息；“学习”是系统的学习结构，从环境中取得外部信息，然后经分析、综合、类比和归纳等思维过程获得知识，并存入知识库中更新知识库；“知识库”用于存放由学习得到的知识，在存储时要适当的组织，便于应用和维护；“执行”环节是基于学习得到的新的知识库，它执行一系列的任务。此外还需将执行结果信息反馈给学习环
6、节，以完成对新“知识库”的评价，指导进一步的学习工作。,普通高等院校“十二五”规划教材,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）归纳推理所
7、谓归纳推理，就是从个别性知识推出一般性结论的推理。归纳推理的前提是其结论的必要条件。（3）类比推理类比推理是根据两个或两类对象有部分属性相同，从而推出它们的其他属性也相同的推理。简称类推、类比。它是以关于两个事物某些属性相同的判断为前提，推出两个事物的其他属性相同的结论的推理。,普通高等院校“十二五”规划教材,7.2 归纳学习,归纳学习是人工智能中发展较为成熟，并得到广泛的研究和应用的学习方法。它是是由一些实例或反例，通过归纳推理得出该概念的一般描述。实现实例到规则的归纳推理过程就是归纳学习过程。它的一般操作是泛化和特化，泛化用来扩展假设的语义信息，以使其能够包含更多的正例，应用于更多的情况。
8、特化是泛化的相反的操作，用于限制概念描述的应用范围。,普通高等院校“十二五”规划教材,7.2.1 归纳学习的基本概念,归纳是指从个别到一般，从部分到整体的推论行为。归纳推理是应用归纳方法所进行的推理，即从足够多的实例中归纳出一般性的知识，它是一种从个别到一般的推理。归纳学习是应用归纳推理进行学习的一种学习方法。归纳学习旨在从大量的经验数据中归纳抽取出一般的判定规则和模式，是从特殊情况推导出一般规则的学习方法。它的目标是形成合理的能解释已知事实和预见新事实的一般性结论。归纳学习由于依赖于经验数据，因此又被称为经验学习；由于依赖于数据间的相似性，因此也被称为基于相似性的学习。,普通高等院校“十二五
9、”规划教材,7.2.1 归纳学习的基本概念,1归纳学习的双空间模型图7.2.1 双空间模型,普通高等院校“十二五”规划教材,7.2.1 归纳学习的基本概念,2归纳学习的分类归纳学习按其有无教师指导可分为示例学习和观察与发现学习。示例学习，又叫做概念获取它的任务是确定概念的一般描述，这个描述应能解释所有给定的正例，并排除所有给定的反例，由于学习是根据教师分好类的正反例进行学习，因此是有教师学习。观察与发现学习又称为描述的泛化这类学习没有教师的帮助，它要产生解释所有或大多数观察的规律和规则，这些都是未经分类的观察学习或是由系统自身的功能去发现。,普通高等院校“十二五”规划教材,7.2.1 归纳学习
10、的基本概念,归纳学习还可以划分为单概念学习和多概念学习两类。典型的单概念学习系统包括米切尔的基于数据驱动的变型空间法，昆兰的ID3方法，狄特利希和米哈尔斯基提出的基于模型驱动的Induce算法。典型的多概念学习方法和系统有米哈尔斯基的、元 和 程序等。多概念学习任务可以划分成多个单概念学习的任务来完成。多概念学习与单概念学习的差别在于多概念学习必须处理概念之间的冲突问题。,普通高等院校“十二五”规划教材,7.2.2 变型空间学习,1变型空间的结构7.2.2 变型空间排序的关系,普通高等院校“十二五”规划教材,7.2.2 变型空间学习,2.候选项删除算法算法过程：（1）初始化H为整个概念空间（规
11、则空间）。（2）接受一个新的示教例子。（3）重复步骤（2），直到G=S，且使这两个集合都只含有一个元素为止。（4）输出H中的概念，即输出G或S。,普通高等院校“十二五”规划教材,7.3 决策树学习,决策树学习是应用最广泛的归纳学习，特别是在专家系统、工业控制过程、金融保险预测以及医疗诊断等领域。如果学习的任务是对一个大的实例集合做概念分类的归纳定义，而这些例子都是用一些无结构的属性值对来表示，那么可以采用决策树学习算法。亨特(Hunt)的概念学习系统CLS是一种早期的基于决策树的归纳学习系统。1979年，昆兰对此进行了发展，提出了ID3算法，该算法不仅能方便地表示概念属性值信息的结构，而且能从
12、大量实例数据中有效地生成相应的决策树模型。,普通高等院校“十二五”规划教材,7.3.1 决策树及构造算法,所谓决策树是一个类似流程图的树结构，其中树的每个结点对应一个特征（属性）变量值的检验，每个分枝表示检验结果，树枝上的叶结点代表所关心的因变量的取值，最顶端的结点称为根结点，内结点用矩形框表示，叶结点用椭圆框表示。从根结点到每个叶结点都有唯一的一条路径，这条路径就是一条决策“规则”。如果每个内结点都恰好有两个分枝，则称为二叉树，类似可定义多叉树，在所有的决策树中，二叉树最为常用。,普通高等院校“十二五”规划教材,7.3.1 决策树及构造算法,普通高等院校“十二五”规划教材,7.3.2 基本的
13、决策树学习算法,普通高等院校“十二五”规划教材,7.3.2 基本的决策树学习算法,普通高等院校“十二五”规划教材,7.4 基于实例的学习,基于实例的学习采用保存实例本身的方法来表达从实例集提取出的知识，并将未知的新实例与现有的类已知的实例联系起来进行操作。这种方法直接在样本上工作，不需要建立规则。基于实例的学习方法包括最近邻法、局部加权回归法、基于范例的推理法等等。基于实例的学习只是简单地把训练样例存储起来，对这些实例进行泛化的工作被推迟到必须分类新的实例时，所以也被称为消极学习法。,普通高等院校“十二五”规划教材,7.4.1 k-近邻算法,最近邻法通过距离函数来判断训练集中的某个实例与哪个位
14、置的测试实例最靠近，一旦找到最靠近的训练实例，那么最靠近实例所属的类就被预测为测试实例的类。实质性的工作在对新的实例进行分类时进行，通过距离函数将每个新实例与现有的实例进行比较，利用最接近的现有实例赋予新实例类别，这就是最近邻分类方法。有时使用多个最近邻实例，并且用最近的K个邻居所属的多数类（如果类是数值型，就是经距离加权的平均值）赋予新的实例类别值，这就是K-近邻法。,普通高等院校“十二五”规划教材,7.4.2 距离加权最近邻法,对K-近邻算法的一个改进是对K个近邻的贡献进行加权，越近的距离赋予越大的权值，这就是所谓的距离加权最近邻法。K-近邻算法的所有变体都只考虑K个近邻用以分类查询点，如
15、果按距离加权，那么可以允许所有的训练样例都影响实例Xq的分类，因为距离非常远的实例影响很小。考虑所有样例的唯一不足是会使分类进行得更慢。如果分类一个新实例时，考虑所有的训练样例，可以称其为全局法；如果仅考虑靠近的训练样例，则称为局部法。,普通高等院校“十二五”规划教材,7.4.3 基于范例的学习,1基于范例推理的一般过程（1）联想记忆（2）类比映射（3）获得求解方案（4）评价2范例的表示(1)SUM_NAME slots：简记为SMU槽。(2)Constraint slots：简记为CON槽。(3)Taxonomy slots：简记为TAX槽。(4)Causality slots：简记为CAU
16、槽。(5)Similarity slots：简记为SIM槽。,普通高等院校“十二五”规划教材,7.4.3 基于范例的学习,(6)Partonomy slots：简记为PAR槽。(7)Csae slots：简记为CAS槽。(8)Theory slots：简记为THY槽。3范例组织（1）范例内容（2）范例索引4范例的检索（1）特征辨识（2）初步匹配（3）最佳选定,普通高等院校“十二五”规划教材,7.4.3 基于范例的学习,5范例的复用（1）替换法（2）转换法（3）特定目标驱动法（4）派生重演,普通高等院校“十二五”规划教材,7.4.1 k-近邻算法,普通高等院校“十二五”规划教材,7.1 概述,普通高等院校“十二五”规划教材,7.1 概述,普通高等院校“十二五”规划教材,本章小结,普通高等院校“十二五”规划教材,课后练习题,普通高等院校“十二五”规划教材,报告结束！,谢谢！,
