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

第六章 机器学习,概述 几种机器学习,第六章 机器学习,概述 几种机器学习,,机器学习 — 概述,参考书 本书展示了机器学习中的核心算法和理论，并阐明了算法的过行过程。书中主要涵盖了目前机器学习中各种最实用的理论和算法，包括概念学习、决策树、神经网络、贝叶斯学习、基于实例的学习、遗传算法、规则学习、基于解释的学习和增强学习等。对每一个主题，作者不仅进行了十分详尽和直观的解释，还给出了实用的算法流程。本书被卡内基梅隆等许多大学作为机器学习课程的教材。,机器学习 — 概述,什么是机器学习？ Simon（1983）：学习就是系统中的变化，这种变化使系统比以前更有效地去做同样的工作。 Minsky (1985)：学习是在我们头脑中（心里内部）进行有用的变化。 学习是一种具有多侧面的现象。学习的过程有：获取新的陈述性知识、通过教育或实践发展机械技能和认知能力、将新知识组织成为通用化和有效的表达形式、借助观察和实验发现新的事实和新的理论。,机器学习 — 概述,基本形式：知识获取和技能求精 知识获取：学习的本质就是获取新的知识。包括物理系统和行为的描述和建模，构造客观现实的表示。——知识获取 通过实践逐渐改造机制和认知技能。例：骑自行车。这些技能包括意识的或机制的协调。这种改进又是通过反复实践和从失败的行为中纠正偏差来进行的。——技能求精,机器学习 — 概述,基本形式 知识获取的本质可能是一个自觉的过程，其结果是产生新的符号知识结构和智力模型。而技能求精则是下意识地借助于反复地实践来实现的。本章只涉及学习的知识获取问题。,机器学习 — 概述,为什么要研究机器学习？ 人工智能主要是为了研究人的智能，模仿其机理将其应用于工程的科学。在这个过程中必然会问道：“人类怎样做才能获取这种特殊技能（或知识）？”。 .......….,机器学习 — 概述,为什么要研究机器学习？ .......…. 当前人工智能研究的主要障碍和发展方向之一就是机器学习。包括学习的计算理论和构造学习系统。现在的人工智能系统还完全没有或仅有很有限的学习能力。系统中的知识由人工编程送入系统，知识中的错误也不能自动改正。也就是说，现有的大多数人工智能是演绎的、没有归纳推理，因而不能自动获取和生成知识。 .......….,机器学习 — 概述,为什么要研究机器学习？ ……….. 未来的计算机将有自动获取知识的能力，它们直接由书本学习，通过与人谈话学习，通过观察学习。它们通过实践自我完善，克服人的存储少、效率低、注意力分散、难以传送所获取得知识等局限性。一台计算机获取的知识很容易复制给任何其它机器。,机器学习 — 概述,实现的困难： 预测难：学习后知识库发生了什么变化，系统功能的变化的预测。 归纳推理：现有的归纳推理只保证假，不保证真。演绎推理保真。而且，归纳的结论是无限多的，其中相当多是假的，给生成的知识带来不可靠性。 机器目前很难观察什么重要、什么有意义。,机器学习 — 概述,机器学习模型 学习是建立理论、形成假设和进行归纳推理的过程。 整个过程包括：信息的存储、知识的处理两部分,,环境,学习环节,,知识库,执行环节,,,,,,,对环境所提供的信息进行处理，以便改善知识库中的显式知识。,机器学习 — 概述,发展历史 神经系统模型和决策理论的研究 50年代开始。其特点是对开始与无初始结构和面向作业知识的通用学习系统感兴趣。包括构造多种具有随机或部分随机的初始结构的基于神经模型的机器。这些系统一般称为神经网络或自组织系统。由于当时计算机技术状态，多停留在理论和硬件上。这些元件类似于神经元，他们实现简单的逻辑功能。 ………,机器学习 — 概述,发展历史 神经系统模型和决策理论的研究 ……… 1965年左右，神经网络经验模式导致了模式识别这一新学科以及机器学习的决策理论方法。这种方法中学习就是从给定的一组经过选择的例子中获得判断函数，有线性的、多项式的、或相关的形式。 当时，Samuel(1059-1963)的跳棋程序是最著名的成功的学习系统之一。达到了跳棋大师的水平。,机器学习 — 概述,符号概念获取的研究 60年代中期提出的基于符号表示的概念学习系统研究。这类学习过程通过分析一些概念的正例和反例构造出这些概念的符号表示。表示的形式一般是逻辑表达式、决策树、产生式规则或语义网络。代表有Winston的ARCH。,机器学习 — 概述,基于知识的学习系统的研究 70年代中期注重基于知识的学习系统研究。人们不再局限于构造概念学习系统和获取上下文知识，同时也结合了问题求解中的学习、概念聚类、类比推理及机器发现的工作。一些成熟的方法开始用于辅助构造专家系统，并不断地开发新的学习方法，使机器学习达到一个新的时期。这时期的工作特点主要有三个方面：,机器学习 — 概述,基于知识的学习系统的研究 基于知识的方法：着重强调应用面向任务的知识和指导学习过程的约束。从早先的无知识学习系统的失败中吸取的教训就是：为获取新的知识，系统必须事先具备大量的初始知识。 开发各种各样的学习方法，除了早先从例子中学习外，各种有关的学习策略相继出现，如示教学习, 观察和发现学习。同时也出现了如类比学习和基于解释的学习等方法。 结合生成和选择学习任务的能力：应用启发式知识于学习任务的生成和选择，包括提出收集数据的方式、选择要获取的概念与控制系统的注意力等。,机器学习 — 概述,联接学习和符号学习的深入研究 第四时期开始于八十年代后期，联接学习和符号学习的深入研究导致机器学习领域的极大繁荣。 首先，神经网络的研究重新迅速崛起，并在声音识别、图象处理等诸多领域得到很大成功。从事研究的学者，发现了用隐含层神经元来计算和学习非线性函数的方法，克服了早期神经元模型的局限性。计算机硬件技术的高速发展也为开发大规模和高性能的人工神经网络扫清了障碍，使得基于人工神经网络的联接学习从低谷走出，发展迅猛，并向传统的基于符号的学习提出了挑战。,机器学习 — 概述,联接学习和符号学习的深入研究 同时，符号学习已经历了三十多年的发展历程，各种方法日臻完善，出现了应用技术蓬勃发展的景象。最突出的成就有分析学习（特别是解释学习）的发展, 遗传算法的成功和加强学习方法的广泛应用。特别是近几年来，随着计算机网络的发展，基于计算机网络的各种自适应、具有学习功能的软件系统的研制和开发都将机器学习的研究推向新的高度，网络环境已成为人工智能和机器学习的重要试验床。,机器学习 — 概述,机器学习进入新阶段的重要表现：（近十年） 机器学习已成为新的边缘科学并在高校形成一门课程。它综合应用心理学、生物学和神经生理学以及数学、自动化和计算机科学形成机器学习理论基础。,机器学习 — 概述,机器学习进入新阶段的重要表现：（近十年） 结合各种学习方法，取长补短的多种形式的集成学习系统的研究正在兴起。特别是连接学习，符号学习的耦合可以更好地解决连续性信号处理中知识与技能的获取与求精问题而受到重视。,机器学习 — 概述,机器学习进入新阶段的重要表现：（近十年） 机器学习与人工智能各种基础问题的统一性观点正在形成。例如：学习与问题求解结合进行，知识表达便于学习的观点产生了通用智能系统SOAR的组块学习。类比学习与问题求解结合的基于案例学习已成为经验学习的重要方向。,机器学习 — 概述,机器学习进入新阶段的重要表现：（近十年） 各种学习方法的应用范围不断扩大，一部分已形成商品。归纳学习的知识获取工具已在诊断分类性专家系统中广泛应用。连接学习在声图文识别中占优势。分析学习用于设计综合性专家系统。遗传算法与强化学习在工程控制中有较好的应用前景。与符号系统耦合的神经网络连接学习将在企业的智能管理与智能机器人运动规划中发挥作用。,机器学习 — 概述,机器学习进入新阶段的重要表现：（近十年） 与机器学习有关的学术活动空前活跃。国际上除每年一次的机器学习研究会外，还有计算机学习理论会议及遗传算法会议。,机器学习 — 概述,分类（由低到高）,,通过归纳总结学习 （自学习） 通过书本资料学习 （独立研究） 通过实际事例学习 （启发式学习） 通过提问学习 （注入式学习） 通过机械记忆学习 （死记硬背式）,,,,,高  低,机器学习 — 概述,分类：(按学习策略分类) 机械式学习和直接输入新知识（记忆学习） 学习者不需要进行任何推理或知识转换，将知识直接装进机器中。 根据示教学习（传授学习、指点学习） 从老师或其它有结构的事物获取知识。要求学习者将输入语言的知识转换成它本身的内部表示形式。并把新的信息和它原有的知识有机地结合为一体。,机器学习 — 概述,通过类推学习（演绎学习） 学习者找出现有知识中所要产生的新概念或技能十分类似的部分。将它们转换或扩大成适合新情况的形式，从而取得新的事实或技能。 从例子中学习（归纳学习） 给学习者提供某一概念的一组正例和反例，学习者归纳出一个总的概念描述，是它适合于所有的正例且排除所有的反例。（目前研究较多的一种方法）,机器学习 — 概述,类比学习 演绎学习与归纳学习的组合。匹配不同论域的描述、确定公共的结构。以此作为类比映射的基础。寻找公共子结构是归纳推理，而实现类比映射是演绎推理。 基于解释的学习 学生根据教师提供的目标概念、该概念的一个例子、领域理论及可操作准则，首先构造一个解释来说明为什么该例子满足目标概念，然后将解释推广为目标概念的一个满足可操作准则的充分条件。,机器学习 — 概述,分类： (按综合分类) 机器学习近几年来发展很快，无论是符号学习还是联接学习都派生出了许多分支和新的方法，研究领域不断扩大，使得不少机器学习方法很难用加以归类。综合分类方式则在对机器学习方法进行分类时，综合考虑各种学习方法出现的历史渊源、知识表示、推理策略、结果评估的相似性、研究人员交流的相对集中性以及应用领域等诸因素。综合分类方式将机器学习方法区分为以下六类：,机器学习 — 概述,按综合分类 经验性归纳学习(empirical inductive learning)。经验性归纳学习采用一些数据密集的经验方法（例如，版本空间法、ID3法，定律发现方法）对例子进行归纳学习。其例子和学习结果一般都采用属性、谓词、关系等符号表示。它相当于基于学习策略分类中的归纳学习，但扣除联接学习、遗传算法、加强学习的部分。,机器学习 — 概述,按综合分类 经验性归纳学习--决策树构造法ID3。如果学习的任务是对一个大的例子集作分类概念的归纳定义，而这些例子又都是用一些无结构的属性值对来表示，则可以采用示例学习方法的一个变种──决策树学习，其代表性的算法是昆兰（J.R.Quinlan，1986）提出的ID3。,机器学习 — 概述,按综合分类 决策树构造法-- ID3。ID3的输入是描述各种已知类别实例的列表。例子由预先定义的属性值对来表示。归纳推理产生的结果不是以往讨论的那种合取表达式，而是一棵决策树（也称判别树，并可转而表示为决策规则的一个集合），用它可正确地区分所有给定例子的类属。,机器学习 — 概述,按综合分类 决策树构造法-- ID3。树中的每一非叶节点对应一个需测试的属性，每个分叉就是该属性可能的取值；树的叶节点则指示一个例子事物的类别。 ID3的显著优点是归纳学习花费的时间和所给任务的困难度（取决于例子个数，用来描述对象的属性数，所学习概念的复杂度即决策树的节点数等）仅成线性增长关系。当然，ID3只能处理用属性-值对表示的例子。,机器学习 — 概述,按综合分类 分析学习（analytic learning）。分析学习方法是从一个或少数几个实例出发，运用领域知识进行分析。其主要特征为：　☆推理策略主要是演绎，而非归纳；　☆使用过去的问题求解经验（实例）指导新的问题求解，或产生能更有效地运用领域知识的搜索控制规则。　分析学习的目标是改善系统的性能，而不是新的概念描述。分析学习包括应用解释学习、演绎学习、多级结构组块以及宏操作学习等技术。,机器学习 — 概述,按综合分类 类比学习。它相当于基于学习策略分类中的类比学习。目前，在这一类型的学习中比较引人注目的研究是通过与过去经历的具体事例作类比来学习，称为基于范例的学习(case_based learning)，或简称范例学习。 基于范例的推理（Case-Based Ressoning, CBR）是指利用过去经历的典型事例（称为范例）求解或理解当前问题。,机器学习 — 概述,按综合分类 基于范例的推理。这种推理形式在现实生活中非常常见。例如，有经验的建筑设计师在设计新的建筑结构时，往往会回想起以往类似的例子。在烹饪、日常活动安排及其它许多方面都存在类似情况，即处理问题时不是从头开始考虑各种细节及其关系，而是依据过去典型的事例，做适当调整以处理当前问题。因而基于范例推理又被称为"即时推理"（instant reasoning），特别适合于知识缺乏或知识太复杂而经验又相对丰富、稳定的领域。,机器学习 — 概述,按综合分类 基于范例的推理是一种类比推理方式。与一般的类比推理相比, 基于范例推理有以下两个特点：　1)作为过去经验的范例一般有比较固定的表示结构，通常用框架形式表示；　2)欲求解的问题与范例中的问题同属于一个领域，且一般是同性质的，即是两类同性质问题的类比。,机器学习 — 概述,基于范例的推理不仅是一种有效的推理方法，也可用于建立一种很好的机器学习方法--基于范例的学习（Case Based Learning，CBL），其学习能力主要表现在： 1)通过记忆和调整老问题的解，使得新问题的求解不必从头做起，因而推理更有效率。2)通过记忆更多的正、反范例，使得系统的推理能力更强。3)通过对范例库中同类范例的归纳，可抽象出更一般、有用的结论。,机器学习 — 概述,按综合分类 遗传算法（genetic algorithm,GA）。是一种基于进化论优胜劣汰、适者生存的物种遗传思想的搜索算法。遗传算法模拟生物繁殖的突变、交换和达尔文的自然选择（在每一生态环境中适者生存）。它把问题可能的解编码为一个向量，称为个体，向量的每一个元素称为基因，并利用目标函数（相应于自然选择标准）对群体（个体的集合）中的每一个个体进行评价，根据评价值（适应度）对个体进行选择、交换(基因重组)、变异(突变)等遗传操作，从而得到新的群体。,机器学习 — 概述,按综合分类 遗传算法（genetic algorithm,GA）。美国密执根大学的霍勒德（J.H.Holland）于70年代初提出并创立了遗传算法。 在霍勒德的GA算法中采用二进制串来表示个体。考虑到物种的进化或淘汰取决于它们在自然界中的适应程度，GA算法为每一个体计算一个适应值或评价值，以反映其好坏程度。,机器学习 — 概述,按综合分类 遗传算法（genetic algorithm,GA） 因而，个体的适应值越高，就有更大的可能生存和再生，即它的表示特征有更大的可能出现在下一代中。遗传操作“交换”旨在通过交换两个个体的子串来实现进化；遗传操作“突变”则随机地改变串中的某一（些）位的值，以期产生新的遗传物质或再现已在进化过程中失去的遗传物质。 霍勒德提出的遗传算法也称为简单遗传算法（SGA），是一种基本的遗传算法。,机器学习 — 概述,按综合分类 简单遗传算法（simple genetic algorithm,SGA） SGA以0、1组成的串表示问题域中待进化的个体（初始解）。利用遗传操作──交换和突变，SGA从当前个体的集合──群体的各串中产生下一代群体。这一过程循环进行，直到满足了结束条件（如循环了指定次，或群体性能不再改进）。SGA的处理过程如下：,机器学习 — 概述,按综合分类 简单遗传算法（simple genetic algorithm,SGA） begin　　　1. 选择适当表示，生成初始群体；　　　　2. 评估群体；　　　　　3. While 未达到要求的目标 do　　　　　　　begin　　　　　　　　1. 选择作为下一代群体的各个体；　　　　　　　　2. 执行交换和突变操作；　　　　　　　　3. 评估群体；　　　　　　　end　　end,机器学习 — 概述,按综合分类 简单遗传算法（simple genetic algorithm,SGA） 因此，对于一个SGA算法来说主要涉及以下内容：　　　 ·编码和初始群体生成；　　　·群体的评价；　　　·个体的选择；　　　·交换；　　　·突变；,机器学习 — 概述,按综合分类 遗传算法（genetic algorithm）。遗传算法适用于非常复杂和困难的环境，比如，带有大量噪声和无关数据、事物不断更新、问题目标不能明显和精确地定义，以及通过很长的执行过程才能确定当前行为的价值等。 遗传算法作为一种解决复杂问题的崭新的有效优化方法，近年来得到了广泛的实际应用，同时也渗透到人工智能、机器学习、模式识别、图像处理、软件技术等计算机学科领域。GA在机器学习领域中的一个典型应用就是利用GA技术作为规则发现方法应用于分类系统。,机器学习 — 概述,按综合分类 联接学习。典型的联接模型实现为人工神经网络，其由称为神经元的一些简单计算单元以及单元间的加权联接组成。,机器学习 — 概述,按综合分类 加强学习（reinforcement learning）。加强学习的特点是通过与环境的试探性（trial and error）交互来确定和优化动作的选择，以实现所谓的序列决策任务。在这种任务中，学习机制通过选择并执行动作，导致系统状态的变化，并有可能得到某种强化信号（立即回报），从而实现与环境的交互。强化信号就是对系统行为的一种标量化的奖惩。系统学习的目标是寻找一个合适的动作选择策略，即在任一给定的状态下选择哪种动作的方法，使产生的动作序列可获得某种最优的结果（如累计立即回报最大）。,机器学习 — 概述,研究目的 希望得到通用的算法 研究了解学习知识的模型、认知模型 解决实际问题的知识库域系统，达到工程目标 研究特点 不可预测性,第六章 机器学习,概述 几种机器学习,,第六章 机器学习,概述 几种机器学习,,,机械式学习,概述 是一种最简单的机器学习系统。外界以一种推理机可直接使用的知识表示形式提供信息，学习系统无需作任何处理。它所要做的是记住所有的信息，考察系统已解决的问题，记住问题和结论。 模型： (x1,…,x2)  (y1,…,y2)  [(x1,…,x2),(y1,…,y2)] 输入模式 执行 输出值 数据对（已解决问题结果） 函数 是一种基于记忆和检索的办法，因此储存器的组织问题将影响检索的效率。,f 存储,指导式学习,概述 通过和用户的相互对话，把用户的一般性意见或指示具体化；或协助用户补充和修改原有的知识库。 该方法既避免系统自己分析、归纳和发现知识的困难，又无需提供知识的领域专家了解系统内部表示和组织知识的实际细节。是目前智能系统中采用较多的方法之一。,指导式学习,模型,,,,,,,,,,,,,,专家,,用户,指导式学习,步骤 征询：请求并接受专家的指导。 解释：消化吸收成内部表示（系统规定的形式）。 加工：转换成推理机可直接使用的形式。 归并：归并到知识库中，主要检查冗余性、一致性和完整性。 评价：对执行结果进行评价。,示例学习,概述 50年代兴起的示例学习是归纳学习的一种。目前示例学习在某些系统中的应用已成为机器学习走向实践的先导。 环境提供给系统一些特殊的示例，这些示例事先由施教者划分为正例和反例。示例学习系统由此进行归纳推理得到一般规则。 环境提供给学习环节的正例和反例是低水平的信息，这是特殊情况下执行环节的行为。学习环节归纳出的规则是高水平的信息，可以在一般情况下用这些规则指导执行环节的工作。,示例学习,示例学习的学习模型,验证,搜索,解释,形成规则,实验计划,,,,,,,,,,,,示例学习,示例学习的学习模型 1）示例空间：所有可能对系统进行训练的示例集合。 2）搜索：从示例空间中搜索出所需的示例。 3）解释：从所选的示例中抽象出信息，提供给规则空间。 4）形成规则：从解释处接收示例，抽取所需信息，将它们归纳成一般性规则。 5）规则空间：存放已形成的规则。 6）实验计划：一旦规则假设形成，系统就要选择更多的示例来验证和精练它们，甚至修正它们，以形成正确的知识。,示例学习,示例学习的两个空间模型,示例学习－ 两个空间模型,描述 例子空间的描述语言可以描述所有例子；规则空间的可以描述所有规则。 例如：纸牌， 同花5张 正例：{(2, c), (3, c), (5, c), (J, c), (A, c)}, 其中c，草花club 规则：描述一手牌的全部谓词表达式的集合。 符号：SUIT(花色)，RANK（点数） 常量：A, 2, 3, …, 10. J, Q, K, clubs(草花), diamonds(方块), hearts（红桃）, spades(黑桃) 合取连接词∧， 存在量词 所以有规则：对c1, c2, c3, c4, c5 SUIT(c1, x)∧SUIT(c2, x)∧SUIT(c3, x)∧SUIT(c4, x)∧SUIT(c5, x),示例学习－ 两个空间模型,例子空间 示教例子的质量。不能有错，同时提供正例和反例，逐步分批有选择地送入。 选择的条件：最有力地划分规则空间；证实肯定假设规则的集合；否定否定假设规则的集合。 搜索方法。,示例学习－ 两个空间模型,规则空间 最根本，真正学习的部分。 定义：一套符号来规定表示规则的算符、术语，所有的描述都在其中。 归纳方法：从特殊到一般的推理（P.221） 常量化为变量。例，从几个正例中找到共性的部分改成变量。 去掉条件。同上例。去掉牌点数这个条件 增加选择（析取）。例人脸牌。从RANK(c1, J), RANK(c2, K)推出还有RANK(c3, Q) 曲线拟合。几组值，解方程或用最小二乘法拟合成一条曲线或曲面。,示例学习－ 两个空间模型（规则空间）,不管是去掉还是增加，都是扩大范围。把已有的知识总结归纳推广。但是要小心。越快越强的方法越容易出错。原因是归纳推理方法是保假不保真。 实际上没有很严格的具体方法。 因此，用归纳方法的过程就是搜索过程。找到包含在少数例子中的正确信息。归纳出错就要回溯。要经常检验，用新例子去否定归纳出的错误规则。即解释例子和选择例子的反复，反复于例子空间和规则空间之间。,示例学习－ 两个空间模型（规则空间）,对规则空间的要求 表示要适应于归纳。如：有谓词才可以增减；有状态空间才能拟合。不同的归纳方法要求不同的规则表示方法。如果规则空间描述的语言的表达能力较弱，可以使用的归纳方法就比较少，规则空间的搜索反谓就比较小，搜索就比较容易。但解决的问题就较少。因此，设计是在规则空间表达能力与规则空间搜索难度之间进行权衡。 表示和例子的一致。如相差很大，解释例子和选择例子的过程就很复杂。 引入新术语（规则空间）。当表示语言不能描述学习过程中产生的新状态时，要产生新的术语。,示例学习－ 例,有两组数据,通过学习,得到描述规则 1 .[发色=金色 ∨ 红色] ∧ [眼睛=蓝色 ∨ 灰色] 2 .[发色=黑色] ∨ [眼睛=黑色],示例学习－ 例,有两组数据（决策树学习）,,,决策树学习,决策树(Decision Tree) 一种描述概念空间的有效的归纳推理办法。基于决策树的学习方法可以进行不相关的多概念学习，具有简单快捷的优势，已经在各个领域取得广泛应用。,决策树学习（概述）,决策树学习是以实例为基础的归纳学习。 从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。 概念分类学习算法：来源于 Hunt,Marin和Stone 于1966年研制的CLS学习系统，用于学习单个概念。 1979年, J.R. Quinlan 给出ID3算法，并在1983年和1986年对ID3 进行了总结和简化，使其成为决策树学习算法的典型。 Schlimmer 和Fisher 于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。 1988年，Utgoff 在ID4基础上提出了ID5学习算法，进一步提高了效率。 1993年，Quinlan 进一步发展了ID3算法，改进成C4.5算法。 另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。 其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。,决策树学习（概述）,随着决策树学习算法的广泛应用，包括C4.5和CART的各种算法得到进一步改进。 当前比较引人注目的有斜超平面分割的多变决策树(Multi-Variance Decision Tree， MDT)算法，将遗传算法、神经元网络和C4.5相结合的GA-NN-C4.5 算法， SVM决策树算法。 这些改进算法旨在结合各种方案的优势，取得更合理的分类效果，总结出更通用的规则。,决策树学习（概述）,决策树学习采用的是自顶向下的递归方法。 决策树的每一层节点依照某一属性值向下分为子节点，待分类的实例在每一节点处与该节点相关的属性值进行比较，根据不同的比较结果向相应的子节点扩展，这一过程在到达决策树的叶节点时结束，此时得到结论。 从根节点到叶节点的每一条路经都对应着一条合理的规则，规则间各个部分（各个层的条件）的关系是合取关系。整个决策树就对应着一组析取的规则。 决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练例子进行较好的标注，就能够进行学习。如果在应用中发现不符合规则的实例，程序会询问用户该实例的正确分类，从而生成新的分枝和叶子，并添加到树中。,决策树学习（决策树）,树是由节点和分枝组成的层次数据结构。节点用于存贮信息或知识，分枝用于连接各个节点。树是图的一个特例，图是更一般的数学结构，如贝叶斯网络。 决策树是描述分类过程的一种数据结构，从上端的根节点开始，各种分类原则被引用进来，并依这些分类原则将根节点的数据集划分为子集，这一划分过程直到某种约束条件满足而结束。,决策树学习（决策树）,可以看到，一个决策树的内部结点包含学习的实例，每层分枝代表了实例的一个属性的可能取值，叶节点是最终划分成的类。如果判定是二元的，那么构造的将是一棵二叉树，在树中每回答一个问题就降到树的下一层，这类树一般称为CART（Classification And Regression Tree）。 判定结构可以机械的转变成产生式规则。可以通过对结构进行广度优先搜索，并在每个节点生成“IF…THEN”规则来实现。如图6-13的决策树可以转换成下规则： IF “个子大” THEN IF “脖子短” THEN IF “鼻子长” THEN 可能是大象 形式化表示成,,决策树学习（决策树）,构造一棵决策树要解决四个问题： 收集待分类的数据，这些数据的所有属性应该是完全标注的。 设计分类原则，即数据的哪些属性可以被用来分类，以及如何将该属性量化。 分类原则的选择，即在众多分类准则中，每一步选择哪一准则使最终的树更令人满意。 设计分类停止条件，实际应用中数据的属性很多，真正有分类意义的属性往往是有限几个，因此在必要的时候应该停止数据集分裂： 该节点包含的数据太少不足以分裂， 继续分裂数据集对树生成的目标(例如ID3中的熵下降准则)没有贡献， 树的深度过大不宜再分。 通用的决策树分裂目标是整棵树的熵总量最小，每一步分裂时，选择使熵减小最大的准则，这种方案使最具有分类潜力的准则最先被提取出来,,决策树学习（性质）,证据由属性值对表示 证据由固定的的属性和其值表示，如属性（温度），值（热）最简单的学习情况时每个属性拥有少量的不相关的值。 目标函数有离散输出值 决策树分配一个二值的树，很容易扩展成为多于两个的输出值。 需要不相关的描述 决策树原则上是表述不相关的表示 容忍训练数据的错误 对训练样本和表述样本的属性值的错误都有较强的鲁棒性。 训练数据可以缺少值 可以采用缺少属性值的样本学习。（不是所有样本都有）,决策树学习（应用）,根据病情对病人分类 根据起因对故障分类 根据付款信用情况对贷款申请者分类 这些都是将输入样本分类成可能离散集 分类问题,决策树学习（学习）,Shannon信息熵 自信息量 设信源X发出ai 的概率p(ai)，在收到符号ai之前，收信者对ai 的不确定性定义为ai的自信息量I(ai)。I(ai) = -logp(ai)。 信息熵 自信息量只能反映符号的不确定性，而信息熵用来度量整个信源整体的不确定性，定义为： 其中，r为信源X发出的所有可能的符号类型。信息熵反应了信源每发出一个符号所提供的平均信息量。 条件熵 设信源为X，收信者收到信息Y，用条件熵H(X|Y)来描述收信者在收到Y后对X的不确定性估计。设X的符号ai，Y的符号bj，p(ai|bj)为当Y为bj时，X为ai的概率，则有： 平均互信息量 用平均互信息量来表示信号Y所能提供的关于X的信息量的大小，用I(X, Y)表示：,,,,,决策树学习（学习）,设学习的实例集为 其中Si为学习实例，T实例集大小。对于有指导的学习，任一个Si具有明确标定的类别， 向量表示该实例的特性，即 Si的信息为，如果一个观测值具有属性则应该划归为类，应该有下面的规则总结出来 式中Xi为事件所具有的第i个属性。这里的属性和类具有广泛的意义。,,,,,基于遗传算法的机器学习应用,简单遗传算法（simple genetic algorithm,SGA） 一个SGA算法来说主要涉及以下内容：　　　 ·编码和初始群体生成；　　　·群体的评价；　　　·个体的选择；　　　·交换；　　　·突变；,基于遗传算法的机器学习应用,1. 编码和初始群体的生成 GA的工作基础是选择适当的方法表示个体和问题的解（作为进化的个体）。SGA要求个体均以0、1组成的串来表示，且所有个体串都是等长的。实际上，可以任意指定有限元素组成的串来表示个体，而不影响GA的基本算法。 对于同一问题，可以有不同的编码表示方法。由于遗传操作直接作用于所表示的串上，因而不同的表示方法对SGA的效率和结果都会有影响。,基于遗传算法的机器学习应用,1. 编码和初始群体的生成 从原理上讲，任何取值为整数（或其它有限可枚举的值）的变量，均可用有限长度的0、1串来表示，而任何取值为连续实数的变量也均可用有限长度的0、1串来近似表示。因此，对任何一个变量，均可在一定程度上用0、1串来表示（编码），而当问题的解涉及多个变量时，则可用各变量对应串的拼接（形成一个长串）来表示相应解。 一般可用随机方法来产生初始群体，当然最好能考虑各个体的代表性和分布概率。,基于遗传算法的机器学习应用,2. 群体的评价　　 对群体中各个体的适应性评价常需直接利用待优化问题的目标函数。这一目标函数也可称为适应函数，个体选择（或再生）过程正是基于这一函数来评价当前群体中各个体的再生概率。,基于遗传算法的机器学习应用,3. 个体的选择　　选择操作是对自然界“适者生存”的模拟。评价值（目标函数值）较大的个体有较高的概率生存，即在下一代群体中再次出现。　　一种常用的选择方法是按比例选择，即若个体i的适应值（目标函数值）是fi，则个体i在下一代群体中复制（再生）的子代个数在群体中的比例将为：　　　　　　　　 fi /∑ fi 。　　其中，∑ fi是指所有个体适应值之和。,基于遗传算法的机器学习应用,3. 个体的选择　　若当前群体与下一代群体的个数均维持在n，则每一个体i在下一代群体中出现的个数将是：　　　　　　　　n* fi /∑ fi = fi /f , 　　其中f=∑ fi /n是群体评价的平均值。 fi /f的值不一定是一个整数。 为了确定个体在下一代中的确切个数，可将fi /f的小数部分视为产生个体的概率。如，若fi /f为2.7，则个体i有70％的可能再生2+1=3个，而有30％的可能只再生2个。,基于遗传算法的机器学习应用,3. 个体的选择　　SGA采用称为旋转盘（roulette wheel）的方法来产生各个体的再生数。方法是：　　每一个体均对应于旋转盘中的一个以园点为中心的扇形区域，区域角度为2π* fi /∑ fi ，因而，各个体的区域角度之和等于2π。然后随机产生一个0到2π的值，根据该值所对应的区域，再生一个对应个体，直到产生的个体个数达到所需的数目，从而生成下一代的原始群体。这个群体还需进一步应用交换和突变操作。,基于遗传算法的机器学习应用,4. 交换　　交换是GA中最主要的遗传操作，其工作于选择过程结束后产生的下一代群体。交换操作应用于从这一群体中随机选择的一系列个体对（串对）。　　SGA采用的是单点交换。 设串长为L，交换操作将随机选择一个交换点（对应于从1到L-1的某个位置序号），紧接着两串交换点右边的子串互换，从而产生了两个新串。,基于遗传算法的机器学习应用,4. 交换　　例如，设Ａ1，Ａ2为要交换的串，交换点被随机选择为7（串长为10）。　　 Ａ1＝1000011111　　 Ａ2＝1111111011交换得新串Ａ1'，Ａ2'：　　 Ａ1'＝1000011011　 　Ａ2'＝1111111111　　当然，并非所有选中的串对都会发生交换。这些串对发生交换的概率是Pc。Pc为事先指定的0－1之间的值，称为交换率。,基于遗传算法的机器学习应用,5. 突变　　另一种遗传操作是突变，它一般在交换后进行。突变操作的对象是个体（即串），旨在改变串中的某些位的值，即由0变为1，或由1变为0。并非所有位都能发生变化，每一位发生变化的概率是Pm。Pm为事先指定的0－1之间的某个值，称为突变率。 串中每一位的突变是独立的，即某一位是否发生突变并不影响其它位的变化。突变的作用是引进新的遗传物质或恢复已失去的遗传物质。例如，若群体的各串中每一位的值均为0，此时无论如何交换都不能产生有1的位，只有通过突变。,基于遗传算法的机器学习应用,5. 突变　下面举一例子来说明遗传算法的一个进化循环。 设每一串的长度为10，共有4个串组成第一代群体（POP1），目标函数（适应函数）为各位值之和，因而函数值为0－10。 POP1中四个串的适应值分别为：3，6，6，9，所以再生的比例个数为：0.5，1，1，1.5。若最后实际的再生个数为0，1，1，2，则产生选择后的群体POP2。 下一步对POP2中各串配对，随机选择串1和串4为一对，串2和串3为另一对。,基于遗传算法的机器学习应用,5. 突变　群体POP1　　　　　　　　　串　　　　　 　适应值　 　　　　　　0000011100 　　　　　　 3　 　　　　　　1000011111 　 　　　　　6　 　　　　　　0110101011 　 　　　　　6　 　　　　　　1111111011 　 　　　　　9 群体POP2（选择后）　　　　 　　 　　串 　　 　　 　适应值　 　　　　　　1000011111　 　　　　　 6　 　　　　　　0110101011 　 　　　　　6　 　　　　　　1111111011 　 　　　　　9　 　　　　　　1111111011 　 　　　　　9,