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

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

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

3、ine LearningAn Overview,见网页http:/www.cs.princeton.edu/schapire/boost.html Lawrence R.Rabiner(1989),A tutorial on Hidden Markov Models&selected applications in speech recognitionthe Proc.of IEEE(Vol.77,No.2)第6章 机器学习方法5 关于支持向量机学习，一本值得推荐的参考书是：邓乃扬、田英杰著：数据挖掘中的新方法支持向量机，科学出版社，2004年6月/特点：从基础开始讲起、详细、透彻第6章 机器

4、学习方法6机器学习顶级期刊 Machine Learning Journal of Machine learning research ACM Transactions on Knowledge Discovery from Data Data Mining and Knowledge Discovery 第6章机器学习7机器学习顶级会议 ICML(International Conference on Machine Learning)ECML(European Conference on Machine Learning)86.1 概述6.1.1 什么是机器学习 6.1.2 研究机器学习的

5、意义 6.1.3 机器学习的发展史 6.1.4 机器学习的主要策略第6章机器学习9学习的概念：学习是系统改善其性能的过程(西蒙)。即，学习就是系统在不断重复的工作中对本身的一种改变，使其能力得到增强或改进，使得系统在下一次执行同样任务或类似任务时，会比现在做的更好或效率更高/影响较大。学习就是知识获取。由从事专家系统的人提出，因为在专家系统的建造中，知识的自动获取是非常困难的。所以知识获取似乎就成了学习的本质，但是获取的知识有时不会使系统的性能有所改善。技巧的获取往往是通过大量时间或反复的训练进行，在获取技巧时，知识获取只起到了很小的作用。第6章机器学习10 学习是对客观经验表示的构造或修改。

6、客观经验包括对外界事物的感受，以及内部的思考过程，学习系统就是通过这种感受和思考过程来获取对客观世界的认识的。其核心问题就是对这种客观经验的形式进行构造和修改 学习是客观规律的发现过程。这种观点将学习看作是从感性认识到理性认识的认识过程，从表层知识到深层知识的特化过程，也就是说学习就是发现事物规律，上升形成理论的过程。学习是一个有特定目的的知识获取过程，其内在行为是获取知识、积累经验、发现规律，其外在表现是使系统性能得到改进、系统实现自我完善、自适应环境。第6章机器学习11 机器学习是研究如何使用计算机来模拟人类学习活动的一门科学。更严格的讲，是研究计算机获取新知识和新技能、识别现有知识、不断

7、改善性能、实现自我完善的方法。机器学习研究的目标人类学习过程的认知模型：对人类学习机制的研究，希望能从中受到启发。通用学习算法：对人类学习过程的研究，探索各种可能的学习方法，建立起独立于具体应用领域的通用学习算法。构造面向任务的专业学习系统：要解决专门的实际问题，并开发完成这些专门任务的学习系统。第6章机器学习12研究机器学习的意义(1)机器学习是研究怎样使用计算机模拟人类学习活动的机器学习是研究怎样使用计算机模拟人类学习活动的科学，是科学，是AIAI中最具有智能特征、最前沿的研究领域之中最具有智能特征、最前沿的研究领域之一，机器学习的一个重大进步就标志着一，机器学习的一个重大进步就标志着AI

8、AI甚至整个计甚至整个计算机科学向前迈进了一步。意义：算机科学向前迈进了一步。意义：学习速度学习速度：人类的学习是一个相当缓慢而又艰苦的过：人类的学习是一个相当缓慢而又艰苦的过程，受到身体生长发育和生理规律的限制。人类学习程，受到身体生长发育和生理规律的限制。人类学习从幼年开始，大约需要从幼年开始，大约需要2020年的时间才能掌握人类生活年的时间才能掌握人类生活中的基本技能，而且还必须中的基本技能，而且还必须“活到老，学到老活到老，学到老”。而。而机器学习却能以惊人的速度进行，而且机器可以不用机器学习却能以惊人的速度进行，而且机器可以不用休息，其学习速度是人类无法比拟的：休息，其学习速度是人类

9、无法比拟的：第6章 机器学习13研究机器学习的意义(2)知识积累知识积累：人类的知识不具有继承性，而机器的知识：人类的知识不具有继承性，而机器的知识具有继承性。一个人一生可能积累了很多知识，但是具有继承性。一个人一生可能积累了很多知识，但是一旦生命结束，这些知识也就随之消失了，不能把知一旦生命结束，这些知识也就随之消失了，不能把知识遗传给后代子孙。如，任何人都必须从小学开始。识遗传给后代子孙。如，任何人都必须从小学开始。如果机器具有学习能力，就可以把知识不断延续下去，如果机器具有学习能力，就可以把知识不断延续下去，避免大量的重复学习，使知识积累达到新的高度。避免大量的重复学习，使知识积累达到新

10、的高度。知识传播知识传播：一个人拥有了很多知识，但是很难让别人：一个人拥有了很多知识，但是很难让别人像他一样拥有这些知识，其他人必须从头学起。对于像他一样拥有这些知识，其他人必须从头学起。对于机器而言，只要一台机器学会了，其他机器只要简单机器而言，只要一台机器学会了，其他机器只要简单复制就学会了。利用机器学习有利于知识传播复制就学会了。利用机器学习有利于知识传播综上所述，机器学习学习速度快、便于知识积累、利综上所述，机器学习学习速度快、便于知识积累、利于知识传播，因此在机器学习领域的一点进步，就会于知识传播，因此在机器学习领域的一点进步，就会使得计算机能力显著增强，从而对人类产生影响。使得计算

11、机能力显著增强，从而对人类产生影响。第6章机器学习14机器学习的应用无处不在 网络入侵检测 天气预报 地震预警 互联网搜索引擎。15机器学习的发展史(1)1.从20世纪50年代中期到60年代中期，属于热烈时期 研究目标是应用决策理论的方法，研制各类自组织系统、自适应的学习系统；基本思想是：系统是一个由互连的元件组成的网络，网络结构可能是任意的，那么这些元件类似于神经原；如果给系统一组刺激、一个反馈源和一个修改自身组织的自由度，则系统就可以自适应地趋向最优化 指导本阶段的理论基础是早在20世纪40年代开始的神经网络模型；典型代表：1957年F.Rosenbatt提出的感知器算法，第一个具有重要学

12、术意义的机器学习算法。第6章机器学习16机器学习的发展史(2)2.从20世纪60年代中期到70年代中叶，属于冷时期 研究目标：模拟人类的概念学习过程，并采用逻辑结构或图结构作为机器的内部描述。研究者们力图在高层知识符号表示的基础上建立人类的学习模型，使机器能够采用符号来描述概念，并提出关于概念的各种假设。代表性工作：温斯顿(Winston)的结构学习系统和海斯罗斯(Hayes Roth)等的基于逻辑的归纳学习系统 虽然这里学习系统取得了较大成功，但只能学习单一概念，并且未能投入实际应用。第6章机器学习17机器学习的发展史(3)3.从20世纪70年代中期到80年代中叶，属于复兴时期 研究从学习单

13、个概念扩展到学习多个概念，探索不同的学习策略和各种学习方法。知识学习的过程一般都建立在大规模知识库上，实现知识强化学习 把学习系统与具体应用相结合，取得了很大成功，促进了机器学习的发展 1980年，在美国的卡内基梅隆大学召开了第一届机器学习国际研讨会，标志着机器学习已在全世界兴起，从此人工智能进入应用阶段 1986年，Machine Learning创刊，迎来了机器学习蓬勃发展的新时期第6章机器学习18机器学习的发展史(4)4.从1986年开始，机器学习进入新阶段 从事神经元模型研究的学者们，经过10多年的潜心研究，克服了神经元模型的局限性，使得神经网络的研究重新兴起。实验研究和应用研究得到前

14、所未有的重视。第6章机器学习19机器学习的主要策略(1)学习过程与推理过程是紧密相连的，学习中使用的推理方法称为学习策略学习过程中推理过程实际上就是一种变换过程，它将系统外部提供的信息变换为符号系统内部表达的新的形式，以便对信息进行存储和使用。这种变换的性质就决定了学习策略的类型。几种基本的学习策略：机械学习：又称记忆学习。不需要任何推理过程，外面输入知识的表示方式与系统内部表示方式完全一致，不需要任何处理和变换。利用计算机的存储容量大，检索速度快，记忆精确。如下棋程序，将棋局及得分放入电脑，走棋时尽量选使自己分数高的棋局第6章机器学习20机器学习的主要策略(2)传授学习：又称指导式、示教学习

15、。外界输入知识的表示方式与系统内部表达方式不完全一致，系统在接受外部知识时，需要一点推理、翻译和转化工作。演绎学习：系统由给定的知识进行演绎的保真推理，并存储有用的结论。最近几年才成为一种独立的学习策略。演绎学习包括知识改造、知识演绎、产生宏操作、保持等价的操作和其他保真变换。归纳学习：应用归纳推理进行学习。按其有无教师指导，可以分为实例学习及观察与发现学习：实例学习：概念获取，通过向学习者提供某一概念的一组正例和反例，使学习者从这些正反例中归纳推理出概念的一般描述/这个描述应能理解所有给定的正第6章机器学习21机器学习的主要策略(3)例并排除所有给定的反例。这些正反例是由信息源提供的，信息源

16、可能是已知概念的教师，也可以是学习者本身，还可以是学习者以外的环境观察和发现学习：描述的一般化。没有教师指导，它要产生对所有或大多数观察到的规律和规则。这类学习包括概念聚类、构造分类、曲线拟合、发现并解释观察到的定律并形成理论。类比学习：在遇到新问题时，可以学习以前解决过的类似问题的解决方法，来解决当前问题。寻找与当前问题相似的已知问题很重要，并且必须能够发现当前任务与已知任务的相似之处，由此制定完成当前任务的方案。第6章机器学习22 基于解释的学习(Explanation-based learning,EBL)。学生根据教师提供的目标概念、该概念的一个例子、领域理论及可操作准则，首先构造一个

17、解释来说明为什该例子满足目标概念，然后将解释推广为目标概念的一个满足可操作准则的充分条件。EBL已被广泛应用于知识库求精和改善系统的性能。著名的EBL系统有迪乔恩（G.DeJong）的GENESIS,米切尔（T.Mitchell）的LEXII和LEAP,以及明斯顿（S.Minton）等的PRODIGY。基于解释的学习从本质上说属于演绎学习，它是根据给定的领域知识，进行保真的演绎推理,存储有用结论，经过知识的求精和编辑，产生适于以后求解类似问题的控制知识。23机器学习方法的分类从训练样本的歧义性（ambiguity），分为 监督学习：它通过对具有概念标记（concept label）的训练样例进

18、行学习，以尽可能正确地对训练集之外的示例的概念标记进行预测。/所有训练例的概念标记都是已知的，因此训练样本的歧义性最低。无监督学习：它通过对没有概念标记的训练例进行学习，以发现训练例中隐藏的结构性知识/这里的训练例的概念标记是不知道的，因此训练样本的歧义性最高。强化学习：它通过对没有概念标记、但与一个延迟奖赏或效用（可视为延迟的概念标记）相关联的训练例进行学习，以获得某种从状态到行动的映射。这里本来没有概念标记的概念，但延迟奖赏可被视为一种延迟概念标记，因此其训练样本的歧义性介于监督学习和非监督学习之间。24 半监督学习（semi-supervised learning）：部分标记。用户期望用

19、未标记的样本来辅助对已标记样本的学习。256.3 机械学习(Rote Learning)6.3.1 机械学习的过程 6.3.2 机械学习系统要考虑的问题第6章机器学习26 机械学习：记忆学习、死记硬背式学习：直接记忆或存储环境提供的新知识，并在以后通过对知识库的检验来直接使用这些知识，而不再需要进行任何的计算和推导。机械学习是一个基本的学习过程，虽然它没有独立处理事物的能力，但存储对于任何智能型的程序来说，都是必要和基本的。记忆学习是任何学习系统的一部分，任何学习系统都要将它所获取的知识存储在知识库中，以便利用这些知识。第6章机器学习27机械学习过程(1)机械学习的学习过程是这样的：执行机构每

20、解决一个问题，系统就记住这个问题和它的解。把执行机构抽象地看成是某一函数F，该函数得到输入是(x1,x2,xn)，经推导计算后得到输出为(y1,y2,yn)，如果经过评价得知该计算是正确的，则就把联想对(x1,x2,xn)，(y1,y2,yn)存入知识库中，在以后需要计算F(x1,x2,xn)时，系统的执行机构就直接从知识库中把(y1,y2,yn)检索出来，而不需要再重复计算。第6章机器学习28 学习过程 应用过程(x1,x2,xn)计算(y1,y2,yn)存储(x1,x2,xn),(y1,y2,yn)(x1,x2,xn)检索(y1,y2,yn)输出(x1,x2,xn),(y1,y2,yn)2

21、9应用举例(1)例：要设计一个汽车修理成本估算系统。该系统的输入信息是关于待修理汽车的描述，包括制造厂商、出厂日期、车型、汽车损坏部件以及损坏程度；输出则是该汽车的修理成本。为了进行估算，系统必须在知识库中找同一厂商、同一出厂日期、同一车型、同样损坏情况的汽车，然后把知识库中对应的数据作为修理成本的估算数据输出给用户/如果在知识库中没有找到这样的汽车，则系统将请求用户给出大概的费用并进行确认，系统则将该车的描述和经过确认的费用存储到知识库中，以便下次查找使用。虽然机械学习在方法上看来很简单，但是由于计算机的存储量大、检索速度快、记忆准确，因此也能产生意想不到的结果。第6章机器学习30举例(2)

22、应用记忆学习的一个典型例子是塞缪尔的CHECKERS跳棋程序。该程序采用极大极小方法搜索博奔树在约定的搜索深度用估价函数F对格局进行评分，然后通过倒推计算求出上层节点的例推值，以决定当前的最佳走步。CHECKERS的学习环节把每个格局的倒推值都记录下来，当下次遇到相同的情况时，就直接利用“记住”的例推值决定最位走步，而不必重新计算。例如，设在某一格局A时轮到CHECKERS走步它向前搜索三步，得到如图所示的搜索树。31 在上图中，根据对端节点的静态伯值，可求得A的例推值为6，最佳走步是走向c。这时CHECKERS就记住A及其倒推值6。假若在以后的博弈中又出现了格局A且轮到它走步，则它就可以通过

23、检索直接得到A的倒推值，而不必再做倒推计算，这就提高了效率。32机械学习系统要考虑的问题机械学习系统要考虑的问题(1)机械学习系统不具备推理能力，只是将所有的信息存入计算机来增加知识，其实质上是以存储空间换取计算时间。虽然节省了计算时间，但却多用了存储空间。因此，机械学习系统设计时需要考虑三个问题 知识库的存储结构;只有当对知识的检索所需时间少于重新计算的时间时，机械学习才有效。为了快速检索知识库的内容，要合理组织。因此，采用适当的存储方式，使检索速度尽可能的快，是机械式学习中的重要问题。环境的稳定性与存储信息的适用性：在急剧变化的情况下，机械学习不适用。机械学习的一个重要假设是认为保存的知识

24、或信息以后仍然有效。如果环境变化快，这个假设就破坏了。因此，机械学习必须保证所保存的信息适应于外界环境变化的需要，即所谓的信息适用性问题。第6章机器学习33机械学习系统要考虑的问题机械学习系统要考虑的问题(2)随时监控环境的变化，不断更新知识库中保存的信息或知识。例如当发现某种汽车被淘汰了，则把与这种汽车相关的知识删除。存储与计算之间的衡量 在解决一个新问题时，是利用知识库的知识还是重新计算，需要权衡比较二者的代价。在权衡到底是存储还是利用计算时，考虑两方面：在首次得到一条信息时，确定是否要保存它，这时要考虑该信息以后的使用概率、存储空间和计算代价 为了保证足够的检索速度，需要尽量精简知识库的

25、内容(存储的越多检索速度越慢)。因此，对保存的内容在读取时加上时间标志，表示最后使用的时间，当保存一项新内容时，要删除一项未使用时间最长的旧内容。第6章机器学习346.4 归纳学习(Inductive Learning)实例学习/观察与发现学习第6章机器学习35归纳学习归纳是人类拓展认识能力的重要方法，是一种从个别到一般、从部分到整体的推理行为归纳推理利用归纳方法，从足够多的具体实例中归纳出一般性知识，提取事物的一般性规律，它是一种从个别到一般的推理归纳推理的特点：能够产生新知识，但不保真，保假归纳学习是应用归纳推理进行学习的一种方法；归纳学习旨在根据给定关于某个概念的一系列已知的正例和反例，

26、归纳出一个一般的概念描述。它是机器学习最核心、最成熟的分支。根据有无教师指导，归纳学习分为实例学习和观察与发现学习。前者有导师，后者没有导师第6章机器学习366.6.1 实例学习(Learning from examples)通过从环境中取得若干与某概念相关的例子，经归纳得出一般性概念的一种方法。在这种学习中，外部环境(教师)提供给系统一些特殊的例子，这些实例事先由教师将其分为正例和反例两类实例学习系统根据这些实例进行归纳推理，得到一般性的规则或知识，这些一般性的知识应能解释所有的正例，排除所有给定的反例 早在20世纪50年代，实例学习就引起了AI学者的注意，是机器学习领域中研究最充分、成果最

27、丰富的一个分支实例学习在某些系统中的应用已经成为机器学习走向实用的先导第6章机器学习37实例学习 实例学习的任务：给定由N个“输入-输出”对样例组成的训练集(x1,y1),.(xN,yN)，其中每个yi由未知函数y=f(x)生成 发现一个函数h，它逼近真实函数f x和y不限于数值，可以是任何形式的值(属性值向量表示法)函数h是一个假说 学习是一个搜索过程，它在可能假说空间寻找一个不仅在训练集上，而且在新样例上具有高精度的假说 为了测量假说h的精确度，一般给学习系统一个由样例组成的测试集，它不同于训练集 所谓一个假说泛化地好是指他能正确预测新样例的y值 拟合：指假设能够很好地在训练集上模拟f 有

28、的时候，函数f是随机的，而不是x的严格函数，其实要学的是一个条件概率分布P(Y|x)38 当输出y的值为有限集合时，学习问题称为是分类 若值集只包括两个元素，称为布尔或二元分类 若y值是数值型的，则学习问题称为回归 一个例子：在某些数据点上拟合一个单变量函数 样例是(x,y)平面上的点，在真实函数f未知的情况下，用假设空间H的一个函数h逼近它 假说空间是诸如x5+3x2+2形式的多项式集合39图(a)表示能用直线确切拟合某些数据/该假设称为一致假说，因为它与所有的数据相符图(b)为一个与同样数据一致的高阶多项式。图(a)图(b)40这说明了归纳学习中的一个基本问题：如何从多个假设中进行抉择？答

29、案是选择与数据一致的最简单假说这个原理基于奥卡姆剃刀原理一般来说，在较好的拟合训练数据的复杂假说和更好泛化的简单假说之间存在着折中41例如，给出肺炎与肺结核两种病的一些病例(实例)。每个病例都含有五种症状：发烧(无、低、高)，咳嗽(轻度、中废、剧烈)，x光所见阴影(点状、索条状、片状、空洞)，皿沉(正常、快)听诊(正常、干鸣音、水泡音)。4243实例学习算法的一般步骤1.预处理训练实例集2.对新事物分类预处理训练实例集，包括6个部分：离散化连续值型属性，将连续型属性的值划分为有穷多个小区间；过滤无关属性，过滤掉与目标概念无关的属性，一般可采用统计属性重要性，最小充分属性等办法来实现；处理“未知

30、”属性值，有3种途径：赋一个特殊值；赋一个最可能的值；按条件概率赋所有可能的值。第6章机器学习44 处理不重要的属性值，不重要的属性值只会使实例集增大，导致学习复杂性增加，预测精度下降。清理无意义的属性值，将训练实例和将来要分类的实例中无意义的属性值去掉；数据清理，从训练集中选择一个好的实例集，以便减少噪音和不一致性，同时使得到的实例集更具有代表性。对新事物分类 构造分类器的目的就是要检查新事例是否与目标概念的分类规则匹配。45按最后得到规则的表示形式，分为 覆盖算法(covering algorithms)：归纳生成规则，一般用析取范式表示。知名的覆盖算法：AQ11(Michabki Chi

31、lausky,1980)及其扩充EQll(Michabki，Hong等，l986)，AEl(Hong，1985)及其改进AE9(赵美德、洪家荣，1995)、HCV(wM，1992)，HCV(陈格、洪家荣，1996)，GS(洪家荣，1987)，扩张TU46 分治算法(divide and conquer)：归纳生成树状结构。知名的分治算法有CLS(Hunt等，1966)及其改进ID3(QuinLan,1983)、C4.5(QuinLan,1984)。第6章机器学习洪家荣.归纳学习算法、理论和应用。科学出版社,199747覆盖算法 假定有两组人，其中每个人具有如下三个特征：身材：高或矮 发色：金色

32、、黑色或红色 眼睛(颜色)：黑色、蓝色或灰色 每个人一个向量来表征，即 下表给出了这两组人向量特征的集合(例子的集合)实例学习的目的就是从两类或多类例子的集合中找出描述其中一类而排出其余类的一般规则 如，对于上例运行某种覆盖算法，得到两个规则4849 为了讨论方便，通常把一个离散符号集映射到非负整数集上，并且把正、反例集PE与NE列成矩阵的形式并仍记为PE与NE 50基本概念 设E是一个n维离散符号的有穷向量空间，E=D1D2Dn，其中Dj是有穷离散符号集，jN，N=1，2,n为变元下标集。E中的元素e称为一个例子，记作e=，其中vj Dj。选择子是形为xj#Aj的关系语句，其中xj是第j个变

33、元，Aj Dj，关系#=,。公式或复合为选择子的合取式，记为 已知例子e=，选择子S=xj#Aj及公式 当e满足选择子所定义的条件时，称e满足选择子；当e满足L所定义的条件时，称e满足公式L，也称为L覆盖e。给定一个正例集PE=e1+,e2+,ek+，反例集NE=e1-,e2-,em-，其中ei*=#jjj JxA#jjj JLxA51正例集PE在反例集NE背景下满足公式L当且仅当每个正例都满足L，而每个反例不满足L。已知正例集PE、反例集NE，以及学习算法A。算法A归纳产生覆盖PE但排除NE的规则记为Cover(PE,NE,A)或Cover(PE,NE)52星算法与AQ11 最早的覆盖算法是

34、Michalski的Aq，其意为准优算法(quasi-optimal algorithm)，Aq算法的核心是星算法，其定义如下。已知正例集PE=e1+,e2+,ek+，反例集NE=e1-,e2-,em-，其中ei*=。一个正例ei+在反例ej-背景下的星记为G(ei+|ej-)，是所有覆盖ei+而排除ej-的极大复合的集合。这里一个极大复合是除覆盖ei+排除ej-之外覆盖最多数目的其他正例的复合。正例ei+在反例集NE背景下的星记为G(ei+|NE)，是所有覆盖ei+而排除NE中所有反例的极大复合的集合。引理：ei+=在反例ej-=背景下的星G(ei+|ej-)是一个逻辑公式，为ei+ej-5

35、3 即(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)是逻辑公式ei+NE 展开式中那些极大复合的集合。易见G(ei+|NE)的展开式中共有nm个复合，其中n是变元数，m是反例数，从中寻找极大复合的问题是NP完全的，因此直接构造星是不实际的，而Aq中使用缩小的星。54 1980，AQ11(Michabki Chilausky,1980)扩充AQll(Michabki，Hong等，

36、l986)AEl(Hong，1985)AE9(赵美德、洪家荣，1995)HCV(Xindong Wu，1992)HCV(陈格、洪家荣，1996)GS(洪家荣，1987)1991年洪家荣提出扩张矩阵EM 1997郭茂祖扩张图55分治算法 分治算法是用属性对例子集逐级划分，直到一个结点仅含有同一类的例子为止。分治算法的结果是一棵决策树(decision tree)最早的分治算法是Hunt等的CLS(Concept Learning System)，后来又出现了Quinlan的ID3、C4.5等。决策树 每一个节点表示对样本实例的某个属性值进行测试，该节点后相连接的各条路径上的值表示该属性的可能取值

37、（二叉，三叉，）叶子节点即为实例所属的分类。每一个叶子产生一条规则，规则由根到该叶子的路径上所有节点的56决策树的说明 条件，规则的结论是叶子上标注的结论（决策，分类，判断）决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取决策树以事物的属性描述集合作为输入，输出通常是一个分类(离散的输出)一般是二值分类(真或假)57第6章 机器学习方法OutlookWindHumiditySunnyOvercastRainHigh Normal Strong WeakYesNoYesNoYes(Outlook=Sunny)(Humidity=No

38、rmal)(Outlook=Overcast)(Outlook=Rain)(Wind=Weak)58 决策树学习的适用问题：实例是由“属性-值”对表示的固定的属性+离散或连续的取值 目标函数具有离散的输出值 析取表达式 训练数据可以包含错误决策树学习的鲁棒性好 训练数据可以包含缺少属性值的实例第6章 机器学习方法59基本的决策树学习算法大多数决策树学习算法是一种核心算法CLS的变体采用自顶向下的贪婪搜索遍历可能的决策树空间ID3是这种算法的代表决策树学习包括2个步骤：从实例中归纳出决策树(建立决策树)利用决策树对新实例进行分类判断ID3的构建决策树的过程 分类能力最好的属性被选作树的根节点 根

39、节点的每个可能值产生一个分支 训练样例排列到适当的分支 重复以上过程，用每个分支关联的训练样例来选取该节点被测试的最佳属性。60表3-1 用于学习布尔函数的ID3算法概要ID3(Examples,Target_attribute,Attributes)创建树的root节点如果Examples都为正,返回label=+的单节点树root如果Examples都为反,返回label=-的单节点树root如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值否则开始AAttributes中分类examples能力最好的属性root

40、的决策属性A对于A的每个可能值vi 在root下加一个新的分支对应测试A=vi 令Examplesvi为Examples中满足A属性值为vi的子集 如果Examplesvi为空 在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值 否则在新分支下加一个子树ID3（Examplesvi,Target_attribute,Attributes-A）返回root61属性选择ID3算法的核心问题是选取在树的每个结点要测试的属性。希望选择最有助于分类实例的属性。/目标是为了最小化最终树的深度，从而使用尽可能少的判断步骤来分类某个实例ID3衡量分类属

41、性区分训练样例能力的标准是“信息增益”。即，ID3在构建树的每一步使用这个信息增益标准从候选属性中选择属性。为了定义信息增益，现定义信息论中广泛使用的一个度量标准熵，它刻画了样例集的纯度。62熵 一个信息的大小是通过它的不确定性来衡量的。p(x)表示随机变量x的概率，那么用s(x)表示X的信息量。如果p(x)=1或0，则s(x)=0;一个随机变量x(假设x有n个可能取值)的平均信息量，即熵是这样计算的：对于包含关于某个目标概念的正反样例集S，那么S相对于这个布尔型分类的熵为，其中p1和p2分别表示S中正例的比例和反例的比例63熵的物理意义 熵用于衡量样本集的纯度；如果样例集S中所有成员均属于一

42、类，则S的熵为0；如果S中正反例数目相当，其熵为1。熵值越大，表示样例越不纯，同时信息量越多；反之则样例越纯，信息量越小6465信息增益 有了用熵度量训练样例集纯度的标准，现在可以定义属性分类训练数据能力的度量标准。一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低。即，一个属性A相对于样例集合S的信息增益Gain(S,A)被定义为：其中，values(A)表示属性A所有可能值的集合，Sv是S中属性A的值为v的子集，Entropy(S)表示原集合S的熵，Entropy(Sv)表示用A分类S后的熵。()(,)()()vvv Values AGain S AEntropy SEntr

43、opysSS66 例：假定S是一套有关天气的训练样例，描述它的属性为可具有weak和Strong两个值的Wind。假定S中有14个样例，其中正例9个，反例5个。在这14个样例中，假定正例中的6个和反例中的2个有Wind=weak，其他的是Wind=Strong。由于按照属性Wind分类14个样例得到的信息增益计算如下：()(,)()()vvv Values AGain S AEntropy SEntropysSS67,(),9,5 6,2 3,3 9955(,)lglg()1414141486622633330.940lglglglg1488881466660.048weakstrongvvv

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

45、益最大的属性，就相当于是选择平均熵下降最快的属性；69决策树算法的要点是在构造决策树的每一层次(从根向下)时，从尚未检测的属性中挑选一个信息增益最高的属性进行分解70 著名的隐形眼镜例子 对于是否可配戴隐形眼镜，可把人们分为3类：类1：适于配戴硬性隐形眼镜；类2：适于配戴软性隐形眼镜；类3：不适于配戴隐形眼镜 为了判断一个人是否适合配戴隐形眼镜，需要检查以下4种属性：属性a：配戴者年龄，取值a=属性b：配戴者的视力缺陷，取值b=属性c：配戴者是否有散光，取值c=属性d：配戴者泪腺分泌情况，取值d=第6章 机器学习方法71 上述属性和人群分类一律按顺序用数字1,2表示，可以假设根据属性a、b、c

46、、d有如下表的分类(纯属虚拟)计算S初始熵值和各属性分解熵值如下：初始熵值为Entropy(S)=-p1log p1-p2log p2-p3log p3 属于第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章 机器学习方法72第6章 机器学习方法序号abcdw序号abcdw111113132211321112214221223112131522213411221162222351211317311136121221831

47、12371221319312138122212031221921113213211310211222232122112121323322131221221243222373 为了方便地计算各个属性的信息增益，给出下表 从表中可得，X中属性a=2/3的w1元素只有1个，a=1的w1元素是2个/而属性d=1的w3元素共有12个，而此时没有w1/w2分类/如此等等第6章 机器学习方法属性abcd取值123共12共12共12共w12114314044044w22215235505055w3456157815781512315共8882412122412122412122474 利用上表，可以得到如下计

48、算：Entospy(a=1)=-(2/8)log(2/8)-(2/8)log(2/8)-(4/8)log(4/8)=0.5+0.5+0.5=1.5 Entospy(a=2)=-(1/8)log(1/8)-(2/8)log(2/8)-(5/8)log(5/8)=0.375+0.5+0.4238=1.2988 Entospy(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)Entos

49、py(a=3)=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章 机器学习方法75 同样可得：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.0395 Gain(S,c)=1.3261-(12/24)*(0+0.5263+0.4536)+(12/24)*(0.5283+0+0.3900)=1.3261-0.4900-0.4592=0.3769

50、Gain(S,d)=1.3261-(12/24)*(0.5283+0.5263+0.5)=0.5488第6章 机器学习方法76 根据以上计算数据，选择信息增益最大的Gain(S,d)，即以属性d作为第一次划分/此时d=1分支中的元素全部为w=3类别，只需对d=2分支继续进行熵值计算/d=2分支为(X,a,b,c)，X是去掉d=1的元素之后剩下的集合(12个元素)第6章 机器学习方法X,dd=1d=2w3X77 缩小以后集合S的属性取值表如下 序号 a b c w 序号 a b c w 2 1 1 1 2 14 2 2 1 2 4 1 1 2 1 16 2 2 2 3 6 1 2 1 2 18