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

第六章 机器学习概述几种机器学习第六章 机器学习概述几种机器学习机器学习 概述n参考书n本书展示了机器学习中的核心算法和理论，并阐明白算法的过行过程。书中主要涵盖了目前机器学习中各种最好用的理论和算法，包括概念学习、决策树、神经网络、贝叶斯学习、基于实例的学习、遗传算法、规则学习、基于说明的学习和增加学习等。对每一个主题，作者不仅进行了特殊详尽和直观的说明，还给出了好用的算法流程。本书被卡内基梅隆等很多高校作为机器学习课程的教材。机器学习 概述什么是机器学习？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）begin1.选择适当表示，生成初始群体；2.评估群体；3.While 未达到要求的目标 dobegin1.选择作为下一代群体的各个体；2.执行交换和突变操作；3.评估群体；endend 机器学习 概述按综合分类简洁遗传算法（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,c5SUIT(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)曲线拟合。几组值，解方程或用最小二乘法拟合成一条曲线或曲面。示例学习 两个空间模型（规则空间）不管是去掉还是增加，都是扩大范围。把已有的学问总结归纳推广。但是要当心。越快越强的方法越简洁出错。缘由是归纳推理方法是保假不保真。事实上没有很严格的具体方法。因此，用归纳方法的过程就是搜寻过程。找到包含在少数例子中的正确信息。归纳出错就要回溯。要常常检验，用新例子去否定归纳出的错误规则。即说明例子和选择例子的反复，反复于例子空间和规则空间之间。示例学习 两个空间模型（规则空间）对规则空间的要求表示要适应于归纳。如：有谓词才可以增减；有状态空间才能拟合。不同的归纳方法要求不同的规则表示方法。假如规则空间描述的语言的表达实力较弱，可以运用的归纳方法就比较少，规则空间的搜寻反谓就比较小，搜寻就比较简洁。但解决的问题就较少。因此，设计是在规则空间表达实力与规则空间搜寻难度之间进行权衡。表示和例子的一样。如相差很大，说明例子和选择例子的过程就很困难。引入新术语（规则空间）。当表示语言不能描述学习过程中产生的新状态时，要产生新的术语。示例学习 例n有两组数据通过学习通过学习,得到描述规则得到描述规则1.发色发色=金色金色 红色红色 眼睛眼睛=蓝色蓝色 灰色灰色2.发色发色=黑色黑色 眼睛眼睛=黑色黑色示例学习 例n有两组数据（决策树学习）决策树学习决策树(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）。判定结构可以机械的转变成产生式规则。可以通过对结构进行广度优先搜寻，并在每个节点生成“IFTHEN”规则来实现。如图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）。）。11000011111 21111111011交换得新串交换得新串1，2：11000011011 21111111111当然，并非全部选中的串对都会发生交换。这些串对当然，并非全部选中的串对都会发生交换。这些串对发生交换的概率是发生交换的概率是Pc。Pc为事先指定的为事先指定的01之间的值，称之间的值，称为交换率。为交换率。基于遗传算法的机器学习应用 5.突变突变另一种遗传操作是突变，它一般在交换后进行。突变另一种遗传操作是突变，它一般在交换后进行。突变操作的对象是个体（即串），旨在变更串中的某些位的值，操作的对象是个体（即串），旨在变更串中的某些位的值，即由即由0变为变为1，或由，或由1变为变为0。并非全部位都能发生变更，每。并非全部位都能发生变更，每一位发生变更的概率是一位发生变更的概率是Pm。Pm为事先指定的为事先指定的01之间的之间的某个值，称为突变率。某个值，称为突变率。串中每一位的突变是独立的，即某一位是否发生突变串中每一位的突变是独立的，即某一位是否发生突变并不影响其它位的变更。突变的作用是引进新的遗传物质并不影响其它位的变更。突变的作用是引进新的遗传物质或复原已失去的遗传物质。例如，若群体的各串中每一位或复原已失去的遗传物质。例如，若群体的各串中每一位的值均为的值均为0，此时无论如何交换都不能产生有，此时无论如何交换都不能产生有1的位，只有的位，只有通过突变。通过突变。基于遗传算法的机器学习应用 5.突变突变下面举一例子来说明遗传算法的一个进化循环。下面举一例子来说明遗传算法的一个进化循环。设每一串的长度为设每一串的长度为10，共有，共有4个串组成第一代群体个串组成第一代群体（POP1），），目标函数（适应函数）为各位值之和，因而目标函数（适应函数）为各位值之和，因而函数值为函数值为010。POP1中四个串的适应值分别为：中四个串的适应值分别为：3，6，6，9，所以再，所以再生的比例个数为：生的比例个数为：0.5，1，1，1.5。若最终实际的再生个