高级人工智能---机器学习课件

1、高级人工智能第6章 机器学习1机器学习机器学习就是计算机自动获取知识，它是知识工程的三个分支(知识获取、知识表示和知识推理)之一，是AI中一个重要的研究领域，一直受到人工智能和认知心理学家们的普遍关注。机器学习涉及计算机科学、数学、心理学、生理学等多个交叉学科，涉及的面比较宽，许多理论和技术的问题尚处于研究阶段。 从IJCAI，当前AI中三个研究热点：机器学习、知识表示和推理、多Agent系统2本章内容 参考文献 6.1 概述 6.2 机器学习系统的基本模型 6.3 机械学习(Rote Learning) 6.4 归纳学习(Inductive Learning) 6.5 强化学习(Reinfo

2、rcement Learning) 6.6 统计学习(Statistical Learning) 6.7 多示例学习( Learning) 本章小结第6章机器学习3参考文献(1)蔡自兴，徐光佑.人工智能及其应用. 清华大学出版社. 2004:第6章 Tom M. Mitchell, 机器学习，曾华军等译，机械工业出版社，2003年1月第一版史忠植. 高级人工智能. 科学出版社, 1998年：第6章 / 第7章 / 第8章 陆汝钤 编著: 人工智能(下册) 第20章 / 第21章T. Mitchell, The discipline of machine learning, July 2006

3、R. E. Schapire (2001), The Boosting Approach to Machine LearningAn Overview, 见网页http:/www.cs. /schapire /boost.htmlLawrence R. Rabiner (1989), A tutorial on Hidden Markov Models & selected applications in speech recognitionthe Proc. of IEEE (Vol. 77, No. 2)第6章 机器学习方法4参考文献(2)关于支持向量机学习，一本值得推荐的参考书是：邓乃扬

4、、田英杰著：数据挖掘中的新方法支持向量机，科学出版社，2004年6月 / 特点：从基础开始讲起、详细、透彻第6章 机器学习方法5机器学习顶级期刊Machine LearningJournal of Machine learning researchACM Transactions on Knowledge Discovery from Data Data Mining and Knowledge Discovery 第6章机器学习6机器学习顶级会议ICML(International Conference on Machine Learning) ECML(European Conferenc

5、e on Machine Learning )76.1 概述6.1.1 什么是机器学习 6.1.2 研究机器学习的意义 6.1.3 机器学习的发展史 6.1.4 机器学习的主要策略第6章机器学习86.1.1 什么是机器学习：学习的概念学习的概念：学习是系统改善其性能的过程(西蒙)。即，学习就是系统在不断重复的工作中对本身的一种改变，使其能力得到增强或改进，使得系统在下一次执行同样任务或类似任务时，会比现在做的更好或效率更高/影响较大。学习就是知识获取。由从事专家系统的人提出，因为在专家系统的建造中，知识的自动获取是非常困难的。所以知识获取似乎就成了学习的本质，但是获取的知识有时不会使系统的性能

6、有所改善。技巧的获取往往是通过大量时间或反复的训练进行，在获取技巧时，知识获取只起到了很小的作用。第6章机器学习9学习的概念(2)学习是对客观经验表示的构造或修改。客观经验包括对外界事物的感受，以及内部的思考过程，学习系统就是通过这种感受和思考过程来获取对客观世界的认识的。其核心问题就是对这种客观经验的形式进行构造和修改学习是客观规律的发现过程。这种观点将学习看作是从感性认识到理性认识的认识过程，从表层知识到深层知识的特化过程，也就是说学习就是发现事物规律，上升形成理论的过程。学习是一个有特定目的的知识获取过程，其内在行为是获取知识、积累经验、发现规律，其外在表现是使系统性能得到改进、系统实现

7、自我完善、自适应环境。第6章机器学习10机器学习机器学习是研究如何使用计算机来模拟人类学习活动的一门科学。更严格的讲，是研究计算机获取新知识和新技能、识别现有知识、不断改善性能、实现自我完善的方法。机器学习研究的目标人类学习过程的认知模型：对人类学习机制的研究，希望能从中受到启发。通用学习算法：对人类学习过程的研究，探索各种可能的学习方法，建立起独立于具体应用领域的通用学习算法。构造面向任务的专业学习系统：要解决专门的实际问题，并开发完成这些专门任务的学习系统。第6章机器学习11研究机器学习的意义(1)机器学习是研究怎样使用计算机模拟人类学习活动的科学，是AI中最具有智能特征、最前沿的研究领域

8、之一，机器学习的一个重大进步就标志着AI甚至整个计算机科学向前迈进了一步。意义：学习速度：人类的学习是一个相当缓慢而又艰苦的过程，受到身体生长发育和生理规律的限制。人类学习从幼年开始，大约需要20年的时间才能掌握人类生活中的基本技能，而且还必须“活到老，学到老”。而机器学习却能以惊人的速度进行，而且机器可以不用休息，其学习速度是人类无法比拟的：第6章 机器学习12研究机器学习的意义(2)知识积累：人类的知识不具有继承性，而机器的知识具有继承性。一个人一生可能积累了很多知识，但是一旦生命结束，这些知识也就随之消失了，不能把知识遗传给后代子孙。如，任何人都必须从小学开始。如果机器具有学习能力，就可

9、以把知识不断延续下去，避免大量的重复学习，使知识积累达到新的高度。知识传播：一个人拥有了很多知识，但是很难让别人像他一样拥有这些知识，其他人必须从头学起。对于机器而言，只要一台机器学会了，其他机器只要简单复制就学会了。利用机器学习有利于知识传播综上所述，机器学习学习速度快、便于知识积累、利于知识传播，因此在机器学习领域的一点进步，就会使得计算机能力显著增强，从而对人类产生影响。第6章机器学习13机器学习的应用无处不在网络入侵检测天气预报地震预警 互联网搜索引擎。14机器学习的发展史(1)从20世纪50年代中期到60年代中期，属于热烈时期研究目标是应用决策理论的方法，研制各类自组织系统、自适应的

10、学习系统；基本思想是：系统是一个由互连的元件组成的网络，网络结构可能是任意的，那么这些元件类似于神经原；如果给系统一组刺激、一个反馈源和一个修改自身组织的自由度，则系统就可以自适应地趋向最优化指导本阶段的理论基础是早在20世纪40年代开始的神经网络模型；典型代表：1957年F.Rosenbatt提出的感知器算法，第一个具有重要学术意义的机器学习算法。第6章机器学习15机器学习的发展史(2)从20世纪60年代中期到70年代中叶，属于冷时期研究目标：模拟人类的概念学习过程，并采用逻辑结构或图结构作为机器的内部描述。研究者们力图在高层知识符号表示的基础上建立人类的学习模型，使机器能够采用符号来描述概

11、念，并提出关于概念的各种假设。代表性工作：温斯顿(Winston)的结构学习系统和海斯罗斯(Hayes Roth)等的基于逻辑的归纳学习系统虽然这里学习系统取得了较大成功，但只能学习单一概念，并且未能投入实际应用。第6章机器学习16机器学习的发展史(3)从20世纪70年代中期到80年代中叶，属于复兴时期研究从学习单个概念扩展到学习多个概念，探索不同的学习策略和各种学习方法。知识学习的过程一般都建立在大规模知识库上，实现知识强化学习把学习系统与具体应用相结合，取得了很大成功，促进了机器学习的发展1980年，在美国的卡内基梅隆大学召开了第一届机器学习国际研讨会，标志着机器学习已在全世界兴起，从此人

12、工智能进入应用阶段1986年，Machine Learning创刊，迎来了机器学习蓬勃发展的新时期第6章机器学习17机器学习的发展史(4)从1986年开始，机器学习进入新阶段从事神经元模型研究的学者们，经过10多年的潜心研究，克服了神经元模型的局限性，使得神经网络的研究重新兴起。实验研究和应用研究得到前所未有的重视。第6章机器学习18机器学习的主要策略(1)学习过程与推理过程是紧密相连的，学习中使用的推理方法称为学习策略学习过程中推理过程实际上就是一种变换过程，它将系统外部提供的信息变换为符号系统内部表达的新的形式，以便对信息进行存储和使用。这种变换的性质就决定了学习策略的类型。几种基本的学习

13、策略：机械学习：又称记忆学习。不需要任何推理过程，外面输入知识的表示方式与系统内部表示方式完全一致，不需要任何处理和变换。利用计算机的存储容量大，检索速度快，记忆精确。如下棋程序，将棋局及得分放入电脑，走棋时尽量选使自己分数高的棋局第6章机器学习19机器学习的主要策略(2)传授学习：又称指导式、示教学习。外界输入知识的表示方式与系统内部表达方式不完全一致，系统在接受外部知识时，需要一点推理、翻译和转化工作。演绎学习：系统由给定的知识进行演绎的保真推理，并存储有用的结论。最近几年才成为一种独立的学习策略。演绎学习包括知识改造、知识演绎、产生宏操作、保持等价的操作和其他保真变换。归纳学习：应用归纳

14、推理进行学习。按其有无教师指导，可以分为实例学习及观察与发现学习：实例学习：概念获取，通过向学习者提供某一概念的一组正例和反例，使学习者从这些正反例中归纳推理出概念的一般描述/这个描述应能理解所有给定的正第6章机器学习20机器学习的主要策略(3)例并排除所有给定的反例。这些正反例是由信息源提供的，信息源可能是已知概念的教师，也可以是学习者本身，还可以是学习者以外的环境观察和发现学习：描述的一般化。没有教师指导，它要产生对所有或大多数观察到的规律和规则。这类学习包括概念聚类、构造分类、曲线拟合、发现并解释观察到的定律并形成理论。类比学习：在遇到新问题时，可以学习以前解决过的类似问题的解决方法，来

15、解决当前问题。寻找与当前问题相似的已知问题很重要，并且必须能够发现当前任务与已知任务的相似之处，由此制定完成当前任务的方案。第6章机器学习21基于解释的学习(Explanation-based learning, EBL)。 学生根据教师提供的目标概念、该概念的一个例子、领域理论及可操作准则，首先构造一个解释来说明为什该例子满足目标概念，然后将解释推广为目标概念的一个满足可操作准则的充分条件。EBL已被广泛应用于知识库求精和改善系统的性能。著名的EBL系统有迪乔恩（G.DeJong）的GENESIS, 米切尔（T.Mitchell）的LEXII和LEAP, 以及明斯顿（S.Minton）等的P

16、RODIGY。基于解释的学习从本质上说属于演绎学习，它是根据给定的领域知识，进行保真的演绎推理,存储有用结论，经过知识的求精和编辑，产生适于以后求解类似问题的控制知识。 22机器学习方法的分类从训练样本的歧义性（ambiguity），分为监督学习：它通过对具有概念标记（concept label）的训练样例进行学习，以尽可能正确地对训练集之外的示例的概念标记进行预测。/所有训练例的概念标记都是已知的，因此训练样本的歧义性最低。 无监督学习：它通过对没有概念标记的训练例进行学习，以发现训练例中隐藏的结构性知识 /这里的训练例的概念标记是不知道的，因此训练样本的歧义性最高。强化学习：它通过对没有概

17、念标记、但与一个延迟奖赏或效用（可视为延迟的概念标记）相关联的训练例进行学习，以获得某种从状态到行动的映射。这里本来没有概念标记的概念，但延迟奖赏可被视为一种延迟概念标记，因此其训练样本的歧义性介于监督学习和非监督学习之间。 23半监督学习（semi-supervised learning）：部分标记。用户期望用未标记的样本来辅助对已标记样本的学习。 246.3 机械学习(Rote Learning)6.3.1 机械学习的过程 6.3.2 机械学习系统要考虑的问题第6章机器学习25机械学习(Rote Learning)机械学习：记忆学习、死记硬背式学习：直接记忆或存储环境提供的新知识，并在以后

18、通过对知识库的检验来直接使用这些知识，而不再需要进行任何的计算和推导。机械学习是一个基本的学习过程，虽然它没有独立处理事物的能力，但存储对于任何智能型的程序来说，都是必要和基本的。记忆学习是任何学习系统的一部分，任何学习系统都要将它所获取的知识存储在知识库中，以便利用这些知识。第6章机器学习26机械学习过程(1)机械学习的学习过程是这样的：执行机构每解决一个问题，系统就记住这个问题和它的解。把执行机构抽象地看成是某一函数F，该函数得到输入是(x1,x2,xn)，经推导计算后得到输出为(y1,y2,yn)，如果经过评价得知该计算是正确的，则就把联想对(x1,x2,xn)， (y1,y2,yn)存

19、入知识库中，在以后需要计算F(x1,x2,xn)时，系统的执行机构就直接从知识库中把(y1,y2,yn)检索出来，而不需要再重复计算。第6章机器学习27学习过程应用过程(x1,x2,xn)计算(y1,y2,yn)存储(x1,x2,xn), (y1,y2,yn)(x1,x2,xn)检索(y1,y2,yn)输出(x1,x2,xn), (y1,y2,yn)28应用举例(1)例：要设计一个汽车修理成本估算系统。该系统的输入信息是关于待修理汽车的描述，包括制造厂商、出厂日期、车型、汽车损坏部件以及损坏程度；输出则是该汽车的修理成本。为了进行估算，系统必须在知识库中找同一厂商、同一出厂日期、同一车型、同样

20、损坏情况的汽车，然后把知识库中对应的数据作为修理成本的估算数据输出给用户/如果在知识库中没有找到这样的汽车，则系统将请求用户给出大概的费用并进行确认，系统则将该车的描述和经过确认的费用存储到知识库中，以便下次查找使用。虽然机械学习在方法上看来很简单，但是由于计算机的存储量大、检索速度快、记忆准确，因此也能产生意想不到的结果。第6章机器学习29举例(2)应用记忆学习的一个典型例子是塞缪尔的CHECKERS跳棋程序。该程序采用极大极小方法搜索博奔树在约定的搜索深度用估价函数F对格局进行评分，然后通过倒推计算求出上层节点的例推值，以决定当前的最佳走步。 CHECKERS的学习环节把每个格局的倒推值都

21、记录下来，当下次遇到相同的情况时，就直接利用“记住”的例推值决定最位走步，而不必重新计算。例如，设在某一格局A时轮到CHECKERS走步它向前搜索三步，得到如图所示的搜索树。30 在上图中，根据对端节点的静态伯值，可求得A的例推值为6，最佳走步是走向c。这时CHECKERS就记住A及其倒推值6。假若在以后的博弈中又出现了格局A且轮到它走步，则它就可以通过检索直接得到A的倒推值，而不必再做倒推计算，这就提高了效率。31机械学习系统要考虑的问题(1)机械学习系统不具备推理能力，只是将所有的信息存入计算机来增加知识，其实质上是以存储空间换取计算时间。虽然节省了计算时间，但却多用了存储空间。因此，机械

22、学习系统设计时需要考虑三个问题知识库的存储结构; 只有当对知识的检索所需时间少于重新计算的时间时，机械学习才有效。为了快速检索知识库的内容，要合理组织。因此，采用适当的存储方式，使检索速度尽可能的快，是机械式学习中的重要问题。环境的稳定性与存储信息的适用性：在急剧变化的情况下，机械学习不适用。机械学习的一个重要假设是认为保存的知识或信息以后仍然有效。如果环境变化快，这个假设就破坏了。因此，机械学习必须保证所保存的信息适应于外界环境变化的需要，即所谓的信息适用性问题。第6章机器学习32机械学习系统要考虑的问题(2)随时监控环境的变化，不断更新知识库中保存的信息或知识。例如当发现某种汽车被淘汰了，

23、则把与这种汽车相关的知识删除。存储与计算之间的衡量在解决一个新问题时，是利用知识库的知识还是重新计算，需要权衡比较二者的代价。在权衡到底是存储还是利用计算时，考虑两方面：在首次得到一条信息时，确定是否要保存它，这时要考虑该信息以后的使用概率、存储空间和计算代价为了保证足够的检索速度，需要尽量精简知识库的内容 (存储的越多检索速度越慢)。因此，对保存的内容在读取时加上时间标志，表示最后使用的时间，当保存一项新内容时，要删除一项未使用时间最长的旧内容。第6章机器学习336.4 归纳学习(Inductive Learning)实例学习/观察与发现学习第6章机器学习34归纳学习归纳是人类拓展认识能力的

24、重要方法，是一种从个别到一般、从部分到整体的推理行为归纳推理利用归纳方法，从足够多的具体实例中归纳出一般性知识，提取事物的一般性规律，它是一种从个别到一般的推理归纳推理的特点：能够产生新知识，但不保真，保假归纳学习是应用归纳推理进行学习的一种方法；归纳学习旨在根据给定关于某个概念的一系列已知的正例和反例，归纳出一个一般的概念描述。它是机器学习最核心、最成熟的分支。根据有无教师指导，归纳学习分为实例学习和观察与发现学习。前者有导师，后者没有导师第6章机器学习356.6.1 实例学习(Learning from examples)通过从环境中取得若干与某概念相关的例子，经归纳得出一般性概念的一种方

25、法。在这种学习中，外部环境(教师)提供给系统一些特殊的例子，这些实例事先由教师将其分为正例和反例两类实例学习系统根据这些实例进行归纳推理，得到一般性的规则或知识，这些一般性的知识应能解释所有的正例，排除所有给定的反例 早在20世纪50年代，实例学习就引起了AI学者的注意，是机器学习领域中研究最充分、成果最丰富的一个分支实例学习在某些系统中的应用已经成为机器学习走向实用的先导第6章机器学习36实例学习实例学习的任务：给定由N个“输入-输出”对样例组成的训练集(x1, y1),.(xN,yN)，其中每个yi由未知函数y=f(x)生成发现一个函数h，它逼近真实函数fx和y不限于数值，可以是任何形式的

26、值(属性值向量表示法)函数h是一个假说学习是一个搜索过程，它在可能假说空间寻找一个不仅在训练集上，而且在新样例上具有高精度的假说为了测量假说h的精确度，一般给学习系统一个由样例组成的测试集，它不同于训练集所谓一个假说泛化地好是指他能正确预测新样例的y值拟合：指假设能够很好地在训练集上模拟f有的时候，函数f是随机的，而不是x的严格函数，其实要学的是一个条件概率分布P(Y|x)37当输出y的值为有限集合时，学习问题称为是分类若值集只包括两个元素，称为布尔或二元分类若y值是数值型的，则学习问题称为回归一个例子：在某些数据点上拟合一个单变量函数样例是(x,y)平面上的点，在真实函数f未知的情况下，用假

27、设空间H的一个函数h逼近它假说空间是诸如x5+3x2+2形式的多项式集合38图(a)表示能用直线确切拟合某些数据/该假设称为一致假说，因为它与所有的数据相符图(b)为一个与同样数据一致的高阶多项式。图(a)图(b)39这说明了归纳学习中的一个基本问题：如何从多个假设中进行抉择？答案是选择与数据一致的最简单假说这个原理基于奥卡姆剃刀原理一般来说，在较好的拟合训练数据的复杂假说和更好泛化的简单假说之间存在着折中40例如，给出肺炎与肺结核两种病的一些病例(实例)。每个病例都含有五种症状：发烧(无、低、高)，咳嗽(轻度、中废、剧烈)，x光所见阴影(点状、索条状、片状、空洞)，皿沉(正常、快)听诊(正常

28、、干鸣音、水泡音)。4142实例学习算法的一般步骤预处理训练实例集对新事物分类预处理训练实例集，包括6个部分：离散化连续值型属性，将连续型属性的值划分为有穷多个小区间；过滤无关属性，过滤掉与目标概念无关的属性，一般可采用统计属性重要性，最小充分属性等办法来实现；处理“未知”属性值，有3种途径：赋一个特殊值；赋一个最可能的值；按条件概率赋所有可能的值。第6章机器学习43处理不重要的属性值，不重要的属性值只会使实例集增大，导致学习复杂性增加，预测精度下降。清理无意义的属性值，将训练实例和将来要分类的实例中无意义的属性值去掉；数据清理，从训练集中选择一个好的实例集，以便减少噪音和不一致性，同时使得到

29、的实例集更具有代表性。对新事物分类构造分类器的目的就是要检查新事例是否与目标概念的分类规则匹配。44按最后得到规则的表示形式，分为覆盖算法(covering algorithms)：归纳生成规则，一般用析取范式表示。知名的覆盖算法：AQ11 (Michabki Chilausky, 1980)及其扩充EQll(Michabki，Hong等，l986)，AEl(Hong，1985)及其改进AE9(赵美德、洪家荣，1995)、HCV(wM，1992)，HCV(陈格、洪家荣，1996)，GS(洪家荣，1987)，扩张TU45分治算法(divide and conquer)：归纳生成树状结构。知名的分

30、治算法有CLS(Hunt等，1966)及其改进ID3(QuinLan, 1983)、 C4.5(QuinLan, 1984) 。第6章机器学习洪家荣.归纳学习算法、理论和应用。科学出版社,199746覆盖算法假定有两组人，其中每个人具有如下三个特征：身材：高或矮发色：金色、黑色或红色眼睛(颜色)：黑色、蓝色或灰色每个人一个向量来表征，即下表给出了这两组人向量特征的集合(例子的集合)实例学习的目的就是从两类或多类例子的集合中找出描述其中一类而排出其余类的一般规则如，对于上例运行某种覆盖算法，得到两个规则4748为了讨论方便，通常把一个离散符号集映射到非负整数集上，并且把正、反例集PE与NE列成矩

31、阵的形式并仍记为PE与NE 49基本概念设E是一个n维离散符号的有穷向量空间，E=D1D2Dn，其中Dj是有穷离散符号集，jN，N=1，2,n为变元下标集。E中的元素e称为一个例子，记作e=，其中vj Dj 。选择子是形为xj#Aj的关系语句，其中xj是第j个变元， Aj Dj ，关系# =, , ,。公式或复合为选择子的合取式，记为已知例子e=，选择子S= xj#Aj及公式 当e满足选择子所定义的条件时，称e满足选择子；当e满足L所定义的条件时，称e满足公式L，也称为L覆盖e。给定一个正例集PE=e1+, e2+, ek+，反例集NE=e1-, e2-, em-，其中ei*=50正例集PE在

32、反例集NE背景下满足公式L当且仅当每个正例都满足L，而每个反例不满足L。已知正例集PE、反例集NE，以及学习算法A。算法A归纳产生覆盖PE但排除NE的规则记为Cover(PE, NE, A)或Cover(PE, NE)51星算法与AQ11最早的覆盖算法是Michalski的Aq，其意为准优算法(quasi-optimal algorithm)， Aq算法的核心是星算法，其定义如下。已知正例集PE=e1+, e2+, ek+，反例集NE=e1-, e2-, em-，其中ei*=。一个正例ei+在反例ej-背景下的星记为G(ei+ | ej-)，是所有覆盖ei+而排除ej-的极大复合的集合。这里一

33、个极大复合是除覆盖ei+排除ej-之外覆盖最多数目的其他正例的复合。正例ei+在反例集NE背景下的星记为G(ei+ | NE)，是所有覆盖ei+而排除NE中所有反例的极大复合的集合。引理： ei+=在反例ej-=背景下的星G(ei+ | ej-)是一个逻辑公式，为ei+ej-52 即( x1=vi1+x2= vi2+ xn =vin+ ) ( x1=vj1-x2= vj2- xn =vjn- )，即，( x1=vi1+x2= vi2+ xn =vin+ ) ( x1vj1-x2 vj2- xn =vjn+ )展开式中那些极大复合的集合。正例ei+在反例集NE背景下的星G(ei+ | NE)是逻

34、辑公式ei+NE 展开式中那些极大复合的集合。易见G(ei+ | NE)的展开式中共有nm个复合，其中n是变元数，m是反例数，从中寻找极大复合的问题是NP完全的，因此直接构造星是不实际的，而Aq中使用缩小的星。531980 ，AQ11 (Michabki Chilausky, 1980)扩充AQll(Michabki，Hong等，l986)AEl(Hong，1985)AE9(赵美德、洪家荣，1995)HCV(Xindong Wu，1992)HCV(陈格、洪家荣，1996)GS(洪家荣，1987)1991年洪家荣提出扩张矩阵EM1997郭茂祖扩张图54分治算法分治算法是用属性对例子集逐级划分，直

35、到一个结点仅含有同一类的例子为止。分治算法的结果是一棵决策树(decision tree)最早的分治算法是Hunt等的CLS(Concept Learning System)，后来又出现了Quinlan的ID3、C4.5等。决策树每一个节点表示对样本实例的某个属性值进行测试，该节点后相连接的各条路径上的值表示该属性的可能取值（二叉，三叉，）叶子节点即为实例所属的分类。每一个叶子产生一条规则，规则由根到该叶子的路径上所有节点的55决策树的说明 条件，规则的结论是叶子上标注的结论（决策，分类，判断）决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这

36、些合取的析取决策树以事物的属性描述集合作为输入，输出通常是一个分类(离散的输出)一般是二值分类(真或假)56决策树例子 第6章 机器学习方法OutlookWindHumiditySunnyOvercastRainHigh Normal Strong WeakYesNoYesNoYes(Outlook=Sunny) (Humidity=Normal) (Outlook=Overcast)(Outlook=Rain) (Wind=Weak)57决策树适用问题决策树学习的适用问题：实例是由“属性-值”对表示的固定的属性+离散或连续的取值目标函数具有离散的输出值析取表达式训练数据可以包含错误决策树学习

37、的鲁棒性好训练数据可以包含缺少属性值的实例第6章 机器学习方法58基本的决策树学习算法大多数决策树学习算法是一种核心算法CLS的变体采用自顶向下的贪婪搜索遍历可能的决策树空间ID3是这种算法的代表决策树学习包括2个步骤：从实例中归纳出决策树(建立决策树)利用决策树对新实例进行分类判断ID3的构建决策树的过程分类能力最好的属性被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复以上过程，用每个分支关联的训练样例来选取该节点被测试的最佳属性。59表3-1 用于学习布尔函数的ID3算法概要ID3(Examples, Target_attribute, Attributes)创建

38、树的root节点如果Examples都为正,返回label=+的单节点树root如果Examples都为反,返回label=-的单节点树root如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值否则开始AAttributes中分类examples能力最好的属性root的决策属性A对于A的每个可能值vi在root下加一个新的分支对应测试A=vi令Examplesvi为Examples中满足A属性值为vi的子集如果Examplesvi为空在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target

39、_attribute值否则在新分支下加一个子树ID3（ Examplesvi,Target_attribute,Attributes-A）返回root60属性选择ID3算法的核心问题是选取在树的每个结点要测试的属性。希望选择最有助于分类实例的属性。/目标是为了最小化最终树的深度，从而使用尽可能少的判断步骤来分类某个实例ID3衡量分类属性区分训练样例能力的标准是“信息增益”。即，ID3在构建树的每一步使用这个信息增益标准从候选属性中选择属性。为了定义信息增益，现定义信息论中广泛使用的一个度量标准熵，它刻画了样例集的纯度。61熵一个信息的大小是通过它的不确定性来衡量的。p(x)表示随机变量x的概率

40、，那么用s(x)表示X的信息量。 如果p(x)=1或0，则s(x)=0;一个随机变量x(假设x有n个可能取值)的平均信息量，即熵是这样计算的：对于包含关于某个目标概念的正反样例集S，那么S相对于这个布尔型分类的熵为，其中p1和p2分别表示S中正例的比例和反例的比例62熵的物理意义熵用于衡量样本集的纯度；如果样例集S中所有成员均属于一类，则S的熵为0；如果S中正反例数目相当，其熵为1。熵值越大，表示样例越不纯，同时信息量越多；反之则样例越纯，信息量越小6364信息增益有了用熵度量训练样例集纯度的标准，现在可以定义属性分类训练数据能力的度量标准。一个属性的信息增益就是由于使用这个属性分割样例而导致

41、的期望熵降低。即，一个属性A相对于样例集合S的信息增益Gain(S,A)被定义为：其中，values(A)表示属性A所有可能值的集合，Sv是S中属性A的值为v的子集，Entropy(S)表示原集合S的熵， Entropy(Sv)表示用A分类S后的熵。65例：假定S是一套有关天气的训练样例，描述它的属性为可具有weak和Strong两个值的Wind。假定S中有14个样例，其中正例9个，反例5个。在这14个样例中，假定正例中的6个和反例中的2个有Wind=weak，其他的是Wind= Strong。由于按照属性Wind分类14个样例得到的信息增益计算如下：6667在ID3中，每次要选择增益最大的属

42、性如何理解选信息增益最大的属性？第6章 机器学习方法开始，决策树的树根对应于最大的不确定状态，表示在分类之前对被分类的对象一无所知随着每个属性的不断判断，向树的叶子方向前进，即相当于选择了其中的一棵子树，其不确定状态就减小了到达叶子节点，分类完成，此时不确定性为零综上所述，构建决策树的过程是熵不断下降的过程。要提高决策树的分类效率，就要求熵值下降的更快 / 这样，ID3算法的实质就是构造一棵熵值下降平均最快的决策树每次选择信息增益最大的属性，就相当于是选择平均熵下降最快的属性；68决策树算法的要点是在构造决策树的每一层次(从根向下)时，从尚未检测的属性中挑选一个信息增益最高的属性进行分解69例

43、子著名的隐形眼镜例子对于是否可配戴隐形眼镜，可把人们分为3类：类1：适于配戴硬性隐形眼镜；类2：适于配戴软性隐形眼镜；类3：不适于配戴隐形眼镜为了判断一个人是否适合配戴隐形眼镜，需要检查以下4种属性：属性a：配戴者年龄，取值a=属性b：配戴者的视力缺陷，取值b=属性c：配戴者是否有散光，取值c=属性d：配戴者泪腺分泌情况，取值d=第6章 机器学习方法70隐形眼镜例子(1)上述属性和人群分类一律按顺序用数字1, 2表示，可以假设根据属性a、b、c、d有如下表的分类(纯属虚拟)计算S初始熵值和各属性分解熵值如下：初始熵值为Entropy(S)=-p1log p1 -p2log p2-p3log p

44、3属于第1类4个 / 第2类5个 / 第3类15个Entropy(S)=- =-(4/24)log(4/24)-(5/24)log(5/24)-(15/24)log(15/24)=0.4308+0.4715+0.4238=1.3261第6章 机器学习方法71隐形眼镜例子(2)第6章 机器学习方法72隐形眼镜例子(3)为了方便地计算各个属性的信息增益，给出下表从表中可得，X中属性a=2/3的w1元素只有1个，a=1的w1元素是2个 / 而属性d=1的w3元素共有12个，而此时没有w1/w2分类 / 如此等等第6章 机器学习方法73隐形眼镜例子(4)利用上表，可以得到如下计算：Entospy(a=

45、1) =-(2/8)log(2/8)-(2/8)log(2/8)-(4/8)log(4/8)=0.5+0.5+0.5=1.5Entospy(a=2) =-(1/8)log(1/8)-(2/8)log(2/8)-(5/8)log(5/8)=0.375+0.5+0.4238=1.2988Entospy(a=3) =-(1/8)log(1/8)-(1/8)log(1/8)-(6/8)log(6/8)=0.375+0.375+0.3113=1.0613由此得Gain(S,a)=E(S)-p(a1) Entospy(a=1) -p(a2) Entospy(a=2) -p(a3) Entospy(a=3)

46、 = 1.3261-(8/24)*1.5+(8/24)*1.2988+(8/24)*1.0613= 1.3261-0.5-0.4329-0.3538=0.0394第6章 机器学习方法74隐形眼镜例子(5)同样可得：Gain(S,b)=1.3261-(12/24)*(0.5+0.4308+0.4536)+12/24)*(0.2987+0.5+0.3900) =1.3261-0.6922-0.5944=0.0395Gain(S,c)=1.3261- (12/24)*(0+0.5263+0.4536)+ (12/24)*(0.5283+0+0.3900)= 1.3261- 0.4900-0.4592

47、=0.3769Gain(S,d)=1.3261-(12/24)*(0.5283+0.5263+0.5)=0.5488第6章 机器学习方法75隐形眼镜例子(6)根据以上计算数据，选择信息增益最大的Gain(S,d)，即以属性d作为第一次划分 / 此时d=1分支中的元素全部为w=3类别，只需对d=2分支继续进行熵值计算 / d=2分支为(X,a, b, c)，X是去掉d=1的元素之后剩下的集合(12个元素)第6章 机器学习方法X,dd=1d=2w3X76隐形眼镜例子(7)缩小以后集合S的属性取值表如下第6章 机器学习方法77隐形眼镜例子(8)接着进行计算，注意在集合S下Entropy(S)Gain

48、(S,a)=.Gain(S,b)=Gain(S,c)=Gain(S,d)=经过反复计算，可得如图示的决策树第6章 机器学习方法78隐形眼镜例子(9)第6章 机器学习方法该例子给出的数据完整情况(请考虑实例不完整情况下如何建立决策树？)79算法的评价 一个学习算法产生的假设(或者分类)应该对未知的实例进行很好的预测如何评价预测的质量也就是学习算法的性能？有2种方式预先估计预测的质量计算学习理论，回答为什么学习是可行的事后考察预测的质量实验验证(训练集/测试集)第6章 机器学习方法80实验验证策略预留法（holdout cross validation）随机将数据分为训练集和测试集，训练集用于学习

49、算法产生h，测试集用于评估h的精度缺点：不能利用所有可用数据，得到的低劣假说或低劣估计K-折交叉验证（k-fold cross validation）能从数据中获取更多东西，并仍然获得精确估计每个样例既作为训练数据又做为测试数据81基本思想：将数据划分为k个规模相等的子集执行k轮次学习在每次学习中，选择1个子集作测试集，然后k-1个作为训练集；k轮测试中得到的平均分数应该好于单一分数但是需要多花费K倍的计算时间82模型选择和相对良好性拟合多项式的阶数越高，就越能更好地模拟训练数据，但阶数太高会出现过度拟合，从而在验证数据上表现低劣定义过拟合(overfit)给定假设空间H和一个假设hH, 如果

50、存在其他假设hH使得在训练样例上h的错误率比h小，但在整个实例分布上h错误率比h小，则称h过拟合训练样例如何寻找一个训练充分又具有最好的泛化能力的决策树呢？当验证集误差开始下降时停止(下页图)。83随着决策树节点的增加，在训练样例上的精度是单调上升的，然而，在独立于训练样例的测试样例上，精度先上升后下降。84决策树算法的性能产生过拟合的原因：训练样例数量太少，很可能出现一些巧合的规律性数据中含有噪声第6章 机器学习方法85观察与发现学习一种无教师指导的归纳学习。分为观察学习和发现学习两种。观察学习用于对事例进行概念聚类，形成概念描述；发现学习用于发现规律，产生定律或规则。概念聚类：观察学习研究

51、中的一个重要技术,基本思想是把事例按一定的方式和准则进行分组,如划分为不同的类、不同的层次等,使不同的组代表不同的概念,并且对每一个分组进行特征概括,得到一个概念的语义符号描述。/聚类就是对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个类别，使类别内的数据相似度较大而类别间的数据相似度较小;第6章机器学习86概念聚类算法列举现在的聚类算法，举例说明与实例学习的区别;训练集87聚类的基本要素定义数据之间的相似度;聚类有效性函数（停止判别条件）; 1. 在聚类算法的不同阶段会得到不同的类别划分结果，可以通过聚类有效性函数来判断多个划分结果中哪个是有效的; 2. 使用有效性函数作为算法停

52、止的判别条件，当类别划分结果达到聚类有效性函数时即可停止算法运行;类别划分策略（算法）; 通过何种类别划分方式使类别划分结果达到有效性函数;88流行聚类算法基于划分: K-means, K-medoids基于层次: HFC基于密度: DBSCAN基于网格: CLIQUE , STING参考文献：孙吉贵. 聚类算法研究. 软件学报, 2008, 19(1)：48-6189发现学习：由系统的初始知识、观察事例或经验数据中归纳出规律或规则；是最困难且最富有创造性的一种学习。分为经验发现和知识发现，经验发现指从经验数据中发现规律和定律,如，物理、化学定理，Bacon；知识发现是从已观察的事例中发现新的

53、知识90集成学习(Ensemble Learning)归纳学习通常从假设空间中选出一个假设对新实例进行分类预测集体学习的思路是在对新的实例进行分类的时候，把若干个单个分类器集成起来，通过对多个分类器的分类结果进行某种组合来决定最终的分类，以取得比单个分类器更好的性能。三个臭皮匠，胜过诸葛亮91为什么集成学习有效？ 统计上的原因：对于一般的学习任务，往往要搜索的空间十分庞大，但是用于训练分类器的训练集中实例个数不足够用来精确地学习到目标假设，这时学习的结果可能是一系列满足训练集的假设，而学习算法只能够选择这些假设的其中之一作为学习到的分类器进行输出。把多个假设集成起来能够降低这种风险。 92计算

54、上的原因 ：证明了在人工神经网络学习和决策树学习中，学习到最好的人工神经网络或者是决策树是一个NP-hard问题，其他的分类器模型也面临着类似的计算复杂度的问题。这使得我们只能用某些启发式的方法来降低寻找目标假设的复杂度，但这样的结果是找到的假设不一定是最优的。通过把多个假设集成起来能够使得最终的结果更加接近实际的目标函数值。 93表示上的原因：由于假设空间是人为规定的，在大多数机器学习的应用场合中实际目标假设并不在假设空间之中，如果假设空间在某种集成运算下不封闭，那么我们通过把假设空间中的一系列假设集成起来就有可能表示出不在假设空间中的目标假设。94集成学习有效的条件虽然以上几点原因使得集成

55、学习可能取得更好的学习效果，但是并不是所有的集成方式都有效的，集成学习有效的条件是每个单一的学习器错误率都应当低于0.5，否则集成的结果反而会提高错误率进行集成学习的每个分类器还应当各不相同/如果每个基本分类器分类结果差不多，则集成后的分类器整体和单个分类器做出的决策实际上没有什么差异，这样集成后的分类器就难以保证比单个分类器有更好的性能了。 95考察一个集成学习方法时应该考虑以下几方面的问题： a) 基本分类器之间是什么关系？ b) 怎么样生成多个不同的基本分类器？ c) 如何把多个基本分类器的分类结果整合起来？ 96基本分类器之间的关系按照基本分类器之间的种类关系可以把集成学习方法划分为异

56、态集成学习和同态集成学习两种异态集成学习指的是使用各种不同的分类器进行集成，异态集成学习的两个主要代表是叠加法（Stack Generalization）和元学习法（Meta Learning）。 同态集成学习：集成的基本分类器都是同一种分类器，只是这些基本分类器之间的参数有所不同。97不同的基本分类器的获得方式基本分类器的多样性是评价集成学习算法的重要标准，因此如何获取不同的基本分类器对集成学习的效果有着重要影响。对于异态集成学习方法，基本分类器的不同来源于他们本身种类的不同；对于同态集成学习方法，基本分类器的不同来自于多种可能，以下把不同基本分类器的获取方式划分为4类，并分别予以说明： 9

57、8不同的基本分类器的获得方式对训练样例进行处理对数据特征进行处理引入随机扰动99不同的基本分类器的获得方式对训练样例进行处理对数据特征进行处理引入随机扰动100对训练数据进行处理BaggingBagging由Breiman提出：对训练集有效地抽取训练样例，从而为每一个基本分类器都构造出一个跟训练集同样大小但各不相同集， 从而训练出不同的分类器。Bagging是基于对训练集进行处理的集成方法中最简单、最直观的一种。要使Bagging有效，基本分类器的学习算法必须是不稳定的，即对训练数据敏感。基本分类器的算法对训练数据越敏感，Bagging的效果越好，因此，对于决策树和人工神经网络这样的学习算法B

58、agging相当有效。Bagging的分类器数应该随着分类种数的增多而增加。101Boosting最先由Robert T. Schapire提出：对那些容易分错的训练实例加强学习首先给每一个训练样例赋予相同的权重，然后训练第一个基本分类器并用它来对训练集进行测试；对于那些分类错误的测试样例提高其权重，然后用调整后的带权训练集训练第二个基本分类器，然后重复这个过程直到得到一个较好的分类器为止。典型算法：AdaBoost102不同的基本分类器的获得方式对训练样例进行处理对数据特征进行处理引入随机扰动103对输入特征进行处理对于具有多种特征的实例，通过抽取不同的特征子集分别进行训练，从而获得不同的分

59、类器。特征子集的选取又叫做集成特征选取（Ensemble Feature Selection），根据特征子集的选取方式不同，又有随机子空间法（随机抽取特征子集）和少量余留法（Input Decimation，只抽取和问题最相关的那些特征）104不同的基本分类器的获得方式对训练样例进行处理对数据特征进行处理引入随机扰动105随机扰动法（Injecting Randomness）在每个基本分类器的学习过程之中引入随机扰动，使得学习出来的每个基本分类器都不同，这是用于进行人工神经网络集成学习的最常见方法。只要基本学习器对随机扰动敏感，则随机扰动法能够有效地产生多个不同的基本分类器。对于人工神经网络，

60、使用后向传递算法来进行学习的时候对于每个神经网络的初始权值都随机分配，则产生的基本分类器会有很明显的不同，对于决策树，则可以在每个决策结点的特征选取的时候从某个特征子集（例如前20个导致熵增益最大的特征构成的集合）里面随机选取一个作为该结点的分类特征。 106基本分类器分类结果的整合方式 简单投票 贝叶斯投票 基于D-S证据理论的整合方式 107简单投票多个基本分类器都进行分类预测，然后根据分类结果用某种投票的原则进行投票表决，按照投票原则的不同投票法可以有一票否决：当且仅当所有的分类器都把实例x划分到类Ci时才把x划分到Ci，否则拒绝这个实例;一致表决:没有分类器否定把实例x划分到类Ci时把