第6章机器学习

1、第六章 机器学习主要内容n机器学习概述n归纳学习(变型空间和候选消除算法)n决策树学习n基于实例的学习n强化学习n小结 6.1.1 机器学习的概念n心理学中对学习的解释是：学习是指（人或动物）依靠经心理学中对学习的解释是：学习是指（人或动物）依靠经验的获得而使行为持久变化的过程。验的获得而使行为持久变化的过程。nSimonSimon认为：如果一个系统能够通过执行某种过程而改进认为：如果一个系统能够通过执行某种过程而改进它的性能，这就是学习。它的性能，这就是学习。nMinskyMinsky认为：学习是在人们头脑中（心理内部）进行有用认为：学习是在人们头脑中（心理内部）进行有用的变化。的变化。nT

2、om M. MitchellTom M. Mitchell在在机器学习机器学习一书中对学习的定义是：一书中对学习的定义是：对于某类任务对于某类任务T T和性能度和性能度P P，如果一个计算机程序在，如果一个计算机程序在T T上以上以P P衡量的性能随着经验衡量的性能随着经验E E而自我完善，那么，我们称这个计而自我完善，那么，我们称这个计算机程序从经验算机程序从经验E E中学习。中学习。n当前关于机器学习的许多文献中也大都认为：学习是一个当前关于机器学习的许多文献中也大都认为：学习是一个有特定目的的知识获取和能力增长过程，其内在行为是获有特定目的的知识获取和能力增长过程，其内在行为是获得知识、

3、积累经验、发现规律等，其外部表现是改进性能、得知识、积累经验、发现规律等，其外部表现是改进性能、适应环境、实现自我完善等。适应环境、实现自我完善等。6.1 机器学习概述一个学习系统应具有以下特点：1.1.具有适当的学习环境具有适当的学习环境 学习系统中环境并非指通常的物理条件，而是指学习系学习系统中环境并非指通常的物理条件，而是指学习系统进行学习统进行学习时所必需的信息来源。时所必需的信息来源。2.2.具有一定的学习能力具有一定的学习能力 一个好的学习方法和一定的学习能力是取得理想的学习一个好的学习方法和一定的学习能力是取得理想的学习效果的重要手段。所以，学习系统应模拟人的学习过程，使效果的重

4、要手段。所以，学习系统应模拟人的学习过程，使系统通过与环境反复多次相互作用，逐步学到有关知识，并系统通过与环境反复多次相互作用，逐步学到有关知识，并且要使系统在学习过程中通过实践验证、评价所学知识的正且要使系统在学习过程中通过实践验证、评价所学知识的正确性。确性。3.3.能用所学的知识解决问题能用所学的知识解决问题 学习的目的在于应用，学习系统能把学到的信息学习的目的在于应用，学习系统能把学到的信息用于对未来的估计、分类、决策和控制。用于对未来的估计、分类、决策和控制。4.4.能提高系统的性能能提高系统的性能 提高系统的性能是学习系统最终目标。通过学提高系统的性能是学习系统最终目标。通过学习，

5、系统随之增长知识，提高解决问题的能力，使习，系统随之增长知识，提高解决问题的能力，使之能完成原来不能完成的任务，或者比原来做得更之能完成原来不能完成的任务，或者比原来做得更好。好。 由此看来由此看来: : 学习系统至少应有环境、知识库、学习环节和执学习系统至少应有环境、知识库、学习环节和执行环节四个基本部分。一种典型的学习系统（迪特里奇行环节四个基本部分。一种典型的学习系统（迪特里奇（DietterichDietterich）学习模型）如下图所示。环境向系统的学习）学习模型）如下图所示。环境向系统的学习部件提供某些信息，学习环节利用这些信息修改知识库，增部件提供某些信息，学习环节利用这些信息修

6、改知识库，增进执行部件的效能；执行环节根据知识库完成任务，同时把进执行部件的效能；执行环节根据知识库完成任务，同时把获得的信息反馈给学习部件。获得的信息反馈给学习部件。环境环境学习单元学习单元知识库知识库执行单元执行单元简单的学习模型简单的学习模型1神经元模型研究阶段神经元模型研究阶段 这个时期主要技术是神经元模型以及基于该模型的决这个时期主要技术是神经元模型以及基于该模型的决策论和控制论策论和控制论; ;机器学习方法通过监督（有教师指导的）机器学习方法通过监督（有教师指导的）学习来实现神经元间连接权的自适应调整，产生线性的模学习来实现神经元间连接权的自适应调整，产生线性的模式分类和联想记忆能

7、力。式分类和联想记忆能力。 具有代表性的工作有具有代表性的工作有FRosenblaftFRosenblaft的感知机（的感知机（19581958年）；年）；NRashevskyNRashevsky数学生物物理学（数学生物物理学（19481948年）；年）；WSMcCullouchWSMcCullouch与与WPittsWPitts的模拟神经元的理论（的模拟神经元的理论（19431943年）年）;RMFriedberg;RMFriedberg对生物进化过程的研究对生物进化过程的研究6.1.2 6.1.2 机器学习的发展简史机器学习的发展简史2 2符号概念获取研究阶段符号概念获取研究阶段 6060

8、年代初期，机器学习的研究进入了第二阶段，在这年代初期，机器学习的研究进入了第二阶段，在这个阶段，心理学和人类学习的模拟占有主导地位，其特点个阶段，心理学和人类学习的模拟占有主导地位，其特点是使用符号而不是数值表示来研究学习问题，其目标是用是使用符号而不是数值表示来研究学习问题，其目标是用学习来表达高级知识的符号描述。在这一观点的影响下，学习来表达高级知识的符号描述。在这一观点的影响下，主要技术是概念获取和各种模式识别系统的应用；研究人主要技术是概念获取和各种模式识别系统的应用；研究人员一方面深入探讨学习的简单概念，另一方面则把大量的员一方面深入探讨学习的简单概念，另一方面则把大量的领域知识并入

9、学习系统，以便它们发现高深的概念。领域知识并入学习系统，以便它们发现高深的概念。 这个阶段代表性的工作是温斯顿（这个阶段代表性的工作是温斯顿（P.H. WinstonP.H. Winston，19751975）的基于示例归纳的结构化概念学习系统。）的基于示例归纳的结构化概念学习系统。3 3基于知识的各种学习系统研究阶段基于知识的各种学习系统研究阶段 机器学习发展的第三个阶段始于机器学习发展的第三个阶段始于7070年代中期，这个阶年代中期，这个阶段不再局限于构造概念学习系统和获取上下文知识，结合了段不再局限于构造概念学习系统和获取上下文知识，结合了问题求解中的学习、概念聚类、类比推理及机器发现的

10、工作。问题求解中的学习、概念聚类、类比推理及机器发现的工作。 相应的有关学习方法相继推出，比如示例学习、示教学相应的有关学习方法相继推出，比如示例学习、示教学习、习、 观察和发现学习、类比学习、基于解释的学习。工作观察和发现学习、类比学习、基于解释的学习。工作特点强调应用面向任务的知识和指导学习过程的约束，应用特点强调应用面向任务的知识和指导学习过程的约束，应用启发式知识于学习任务的生成和选择，包括提出收集数据的启发式知识于学习任务的生成和选择，包括提出收集数据的方式、选择要获取的概念、控制系统的注意力等。方式、选择要获取的概念、控制系统的注意力等。4 4联结学习和符号学习共同发展阶段联结学习

11、和符号学习共同发展阶段 8080年代后期以来，形成了联结学习和符号学习共同发年代后期以来，形成了联结学习和符号学习共同发展的局的第四个阶段。在这个时期，发现了用隐单元来计展的局的第四个阶段。在这个时期，发现了用隐单元来计算和学习非线性函数的方法，从而克服了早期神经元模型算和学习非线性函数的方法，从而克服了早期神经元模型的局限性，同时，由于计算机硬件的迅速发展，使得神经的局限性，同时，由于计算机硬件的迅速发展，使得神经网络的物理实现变成可能，在声音识别、图像处理等领域，网络的物理实现变成可能，在声音识别、图像处理等领域，神经网络取得了很大的成功。神经网络取得了很大的成功。 在这个进期，符号学习伴

12、随人工智能的进展也日益成在这个进期，符号学习伴随人工智能的进展也日益成熟，应用领域不断扩大，最杰出的工作有分析学习（特别熟，应用领域不断扩大，最杰出的工作有分析学习（特别是解释学习）、遗传算法、决策树归纳等。现在基于计算是解释学习）、遗传算法、决策树归纳等。现在基于计算机网络的各种自适应、具有学习功能的软件系统的研制和机网络的各种自适应、具有学习功能的软件系统的研制和开发开发, ,将机器学习的研究推向新的高度。将机器学习的研究推向新的高度。1. 基于学习策略的分类基于学习策略的分类 （1 1）模拟人脑的机器学习）模拟人脑的机器学习符号学习：模拟人脑的宏观心理级学习过程，以认知心理符号学习：模拟

13、人脑的宏观心理级学习过程，以认知心理学原理为基础，以符号数据为输入，以符号运算为方法，学原理为基础，以符号数据为输入，以符号运算为方法，用推理过程在图或状态空间中搜索，学习的目标为概念或用推理过程在图或状态空间中搜索，学习的目标为概念或规则等。符号学习的典型方法有：记忆学习、示例学习、规则等。符号学习的典型方法有：记忆学习、示例学习、演绎学习、类比学习、解释学习等。演绎学习、类比学习、解释学习等。神经网络学习（或连接学习）：模拟人脑的微观生理级学神经网络学习（或连接学习）：模拟人脑的微观生理级学习过程，以脑和神经科学原理为基础，以人工神经网络为习过程，以脑和神经科学原理为基础，以人工神经网络为

14、函数结构模型，以数值数据为输入，以数值运算为方法，函数结构模型，以数值数据为输入，以数值运算为方法，用迭代过程在系数向量空间中搜索，学习的目标为函数。用迭代过程在系数向量空间中搜索，学习的目标为函数。典型的连接学习有权值修正学习、拓扑结构学习。典型的连接学习有权值修正学习、拓扑结构学习。 （2 2）直接采用数学方法的机器学习）直接采用数学方法的机器学习 主要有统计机器学习。主要有统计机器学习。6.1.3 机器学习的分类2. 基于推理策略的分类基于推理策略的分类 （1 1）归纳学习）归纳学习 符号归纳学习：典型的符号归纳学习有示例学习，符号归纳学习：典型的符号归纳学习有示例学习，决策树学习。决策

15、树学习。 函数归纳学习（发现学习）：典型的函数归纳学习函数归纳学习（发现学习）：典型的函数归纳学习有神经网络学习、示例学习，发现学习，统计学习。有神经网络学习、示例学习，发现学习，统计学习。 （2 2）演绎学习）演绎学习 （3 3）类比学习：典型的类比学习有案例（范例）学习。）类比学习：典型的类比学习有案例（范例）学习。 （4 4）分析学习：典型的分析学习有案例（范例）学习、）分析学习：典型的分析学习有案例（范例）学习、解释学习。解释学习。3. 基于学习方式的分类基于学习方式的分类（1 1）有导师学习（监督学习）：输入数据中有导师信号，）有导师学习（监督学习）：输入数据中有导师信号，以概率函数

16、、代数函数或人工神经网络为基函数模型，采以概率函数、代数函数或人工神经网络为基函数模型，采用迭代计算方法，学习结果为函数。用迭代计算方法，学习结果为函数。（2 2）无导师学习（非监督学习）：输入数据中无导师信号，）无导师学习（非监督学习）：输入数据中无导师信号，采用聚类方法，学习结果为类别。典型的无导师学习有发采用聚类方法，学习结果为类别。典型的无导师学习有发现学习、聚类、竞争学习等。现学习、聚类、竞争学习等。（3 3）强化学习（增强学习）：以环境反馈（奖）强化学习（增强学习）：以环境反馈（奖/ /惩信号）作惩信号）作为输入，以统计和动态规划技术为指导的一种学习方法。为输入，以统计和动态规划技

17、术为指导的一种学习方法。4. 基于数据形式的分类基于数据形式的分类（1 1）结构化学习：以结构化数据为输入，以数值计算或符）结构化学习：以结构化数据为输入，以数值计算或符号推演为方法。典型的结构化学习有神经网络学习、统计号推演为方法。典型的结构化学习有神经网络学习、统计学习、决策树学习、规则学习。学习、决策树学习、规则学习。（2 2）非结构化学习：以非结构化数据为输入，典型的非结）非结构化学习：以非结构化数据为输入，典型的非结构化学习有类比学习、案例学习、解释学习、文本挖掘、构化学习有类比学习、案例学习、解释学习、文本挖掘、图像挖掘、图像挖掘、WebWeb挖掘等。挖掘等。 5. 基于学习目标的

18、分类基于学习目标的分类 （1 1）概念学习：即学习的目标和结果为概念，或者说是为了）概念学习：即学习的目标和结果为概念，或者说是为了获得概念的一种学习。典型的概念学习有示例学习。获得概念的一种学习。典型的概念学习有示例学习。 （2 2）规则学习：即学习的目标和结果为规则，或者说是为了）规则学习：即学习的目标和结果为规则，或者说是为了获得规则的一种学习。典型的规则学习有决策树学习。获得规则的一种学习。典型的规则学习有决策树学习。 （3 3）函数学习：即学习的目标和结果为规则，或者说是为了）函数学习：即学习的目标和结果为规则，或者说是为了获得函数的一种学习。典型的函数学习有神经网络学习。获得函数的

19、一种学习。典型的函数学习有神经网络学习。 （4 4）类别学习：即学习的目标和结果为对象类，或者说是为）类别学习：即学习的目标和结果为对象类，或者说是为了获得类别的一种学习。典型的类别学习有聚类分析。了获得类别的一种学习。典型的类别学习有聚类分析。 （5 5）贝叶斯网络学习：即学习的目标和结果是贝叶斯网络，）贝叶斯网络学习：即学习的目标和结果是贝叶斯网络，或者说是为了获得贝叶斯网络的一种学习。其又可分为结构学或者说是为了获得贝叶斯网络的一种学习。其又可分为结构学习和参数学习。习和参数学习。 机器学习的应用非常广泛，利用这门技术，机器学习的应用非常广泛，利用这门技术，计算机已经能够成功地识别人类的

20、讲话计算机已经能够成功地识别人类的讲话(Waibel (Waibel 1989, Lee 1989)1989, Lee 1989)，在高速公路上自动驾驶汽车，在高速公路上自动驾驶汽车(Pomerleau 1989)(Pomerleau 1989)，学习分类新的天文结构，学习分类新的天文结构(Fayyad et al. 1995)(Fayyad et al. 1995)，以接近人类世界冠军的，以接近人类世界冠军的水平对弈西洋双陆棋（水平对弈西洋双陆棋（Tesauro 1992,1995Tesauro 1992,1995）6.1.4 机器学习的应用与研究目标：研究目标有三个：研究目标有三个： (1

21、)(1)人类学习过程的认知模型。研究人类学习机理的人类学习过程的认知模型。研究人类学习机理的认知模型，这种研究对人类的教育，以及对开发机认知模型，这种研究对人类的教育，以及对开发机器学习系统都有重要的意义。器学习系统都有重要的意义。(2)(2)通用学习算法。通过对人类学习过程的研究，探通用学习算法。通过对人类学习过程的研究，探索各种可能的学习方法，建立起具体应用领域的通索各种可能的学习方法，建立起具体应用领域的通用学习算法。用学习算法。(3)(3)构造面向任务的专用学习系统。研究智能系统的构造面向任务的专用学习系统。研究智能系统的建造，解决专门的实际问题，并开发完成这些专门建造，解决专门的实际

22、问题，并开发完成这些专门任务的学习系统。任务的学习系统。主要内容机器学习概述n归纳学习(变型空间和候选消除算法)n决策树学习n基于实例的学习n强化学习n小结 归纳学习归纳学习( (概念学习、经验学习）是符号学习中研究概念学习、经验学习）是符号学习中研究的最为广泛的一种方法。给定关于某个概念的一系列已知的最为广泛的一种方法。给定关于某个概念的一系列已知的正例与反例，其任务是从中归纳出一个一般的概念描述。的正例与反例，其任务是从中归纳出一个一般的概念描述。归纳学习能够获得新的概念，创立新的规则，发现新的理归纳学习能够获得新的概念，创立新的规则，发现新的理论。它的一般操作是泛化论。它的一般操作是泛化

23、(Generalization)(Generalization)和特化和特化(Specialization)(Specialization)。泛化用来扩展一假设的语义信息，以。泛化用来扩展一假设的语义信息，以使其能够包含更多的正例，应用于更多的情况。特化是泛使其能够包含更多的正例，应用于更多的情况。特化是泛化的相反的操作，用于限制概念描述的应用范围。化的相反的操作，用于限制概念描述的应用范围。 6.2.1 6.2.1 归纳学习的基本概念归纳学习的基本概念n归纳学习归纳学习指在从大量的经验数据中归纳抽取出一指在从大量的经验数据中归纳抽取出一般的判定规则和模式，是从特殊情况推导出一般般的判定规则和

24、模式，是从特殊情况推导出一般规则的学习方法。归纳学习的目标是形成合理的规则的学习方法。归纳学习的目标是形成合理的能解释已知事实和预见新事实的一般性结论。能解释已知事实和预见新事实的一般性结论。n归纳学习由于依赖于经验数据，因此又称为经验归纳学习由于依赖于经验数据，因此又称为经验学习学习(Empirical Learning)(Empirical Learning)，由于归纳依赖于数，由于归纳依赖于数据间的相似性，所以也称为基于相似性的学习据间的相似性，所以也称为基于相似性的学习(Similarity Based Learning)(Similarity Based Learning)。n归纳学

25、习的双空间模型如图所示。归纳学习的双空间模型如图所示。1.归纳学习的双空间模型归纳学习的双空间模型 首先由施教者给实例空间提供一些初始示教首先由施教者给实例空间提供一些初始示教例子，由于示教例子在形式上往往和规则形式不例子，由于示教例子在形式上往往和规则形式不同，因此需要对这些例子进行转换，解释为规则同，因此需要对这些例子进行转换，解释为规则空间接受的形式。然后利用解释后的例子搜索规空间接受的形式。然后利用解释后的例子搜索规则空间，由于一般情况下不能一次就从规则空间则空间，由于一般情况下不能一次就从规则空间中搜索到要求的规则，因此还要寻找一些新的示中搜索到要求的规则，因此还要寻找一些新的示教例

26、子，这个过程就是选择例子。程序会选择对教例子，这个过程就是选择例子。程序会选择对搜索规则空间最有用的例子，对这些示教例子重搜索规则空间最有用的例子，对这些示教例子重复上述循环。如此循环多次，直到找到所要求的复上述循环。如此循环多次，直到找到所要求的例子。例子。执行过程描述执行过程描述n归纳学习方法可以划分为单概念学习和多概念学归纳学习方法可以划分为单概念学习和多概念学习两类。这里，概念指用某种描述语言表示的谓习两类。这里，概念指用某种描述语言表示的谓词，当应用于概念的正实例时，谓词为真，应用词，当应用于概念的正实例时，谓词为真，应用于负实例时为假。从而概念谓词将实例空间划分于负实例时为假。从而

27、概念谓词将实例空间划分为正、反两个子集。为正、反两个子集。n对于单概念学习，学习的目的是从概念空间（即对于单概念学习，学习的目的是从概念空间（即规则空间）中寻找某个与实例空间一致的概念；规则空间）中寻找某个与实例空间一致的概念；对于多概念学习任务，是从概念空间中找出若干对于多概念学习任务，是从概念空间中找出若干概念描述，对于每个概念描述，实例空间中均有概念描述，对于每个概念描述，实例空间中均有相应的空间与之对应。相应的空间与之对应。2.归纳学习方法的分类归纳学习方法的分类n典型的单概念学习系统包括米切尔典型的单概念学习系统包括米切尔(Tom Mitchell)(Tom Mitchell)的的基

28、于数据驱动的变型空间法，昆兰基于数据驱动的变型空间法，昆兰(J.R. Quinlan)(J.R. Quinlan)的的ID3ID3方法，狄特利希方法，狄特利希(T.G. Dietterich)(T.G. Dietterich)和米哈尔斯基和米哈尔斯基(R.S. Michalski)(R.S. Michalski)提出的基于模型驱动的提出的基于模型驱动的InduceInduce算法。算法。n典型的多概念学习方法和系统有米哈尔斯基的典型的多概念学习方法和系统有米哈尔斯基的AQ11AQ11、DENDRALDENDRAL和和AMAM程序等。多概念学习任务可以划分成多个程序等。多概念学习任务可以划分成多

29、个单概念学习任务来完成。单概念学习任务来完成。n多概念学习与单概念学习的差别在于多概念学习方法多概念学习与单概念学习的差别在于多概念学习方法必须解决概念之间的冲突问题。必须解决概念之间的冲突问题。归纳学习方法的分类归纳学习方法的分类n变型空间学习方法变型空间学习方法(Learning by Version Space)(Learning by Version Space)，也称为变型空间学习法。也称为变型空间学习法。n变型空间法是变型空间法是TMMitchellTMMitchell于于19771977年提出的一种年提出的一种数据驱动型的学习方法。数据驱动型的学习方法。n该方法以整个规则空间为初

30、始的假设规则集合该方法以整个规则空间为初始的假设规则集合H H。依据示教例子中的信息，系统对集合依据示教例子中的信息，系统对集合H H进行一般化进行一般化或特殊化处理，逐步缩小集合或特殊化处理，逐步缩小集合H H。最后使得。最后使得H H收敛到收敛到只含有要求的规则。由于被搜索的空间只含有要求的规则。由于被搜索的空间H H逐渐缩小，逐渐缩小，故称为变型空间法。故称为变型空间法。6.2.2 6.2.2 变型空间学习变型空间学习n在变型空间中，表示规则的点与点之间存在着一种由一在变型空间中，表示规则的点与点之间存在着一种由一般到特殊的偏序关系。我们定义为覆盖，例如，般到特殊的偏序关系。我们定义为覆

31、盖，例如，color(X,Y)color(X,Y)覆盖覆盖color(ball,Z)color(ball,Z)，于是又覆盖，于是又覆盖color(ball,red)color(ball,red)。(more general than)(more general than)n作为一个简单的例子，考虑有这样一些属性和值的对象作为一个简单的例子，考虑有这样一些属性和值的对象域：域： Sizes=large,smallSizes=large,small Colors=red,white,blue Colors=red,white,blue Shapes=ball,brick,cube Shapes=b

32、all,brick,cuben这些对象可以用谓词这些对象可以用谓词obj(Sizes,Color,Shapes)obj(Sizes,Color,Shapes)来表示。来表示。用变量替换常量这个泛化操作定义用变量替换常量这个泛化操作定义 1 1变型空间的结构变型空间的结构 假设空间假设空间H H由两个子集由两个子集G G和和S S所限定，子集所限定，子集G G中的中的元素表示元素表示H H中的最一般的概念，子集中的最一般的概念，子集S S中的元素表示中的元素表示H H中的最特殊的概念，假设空间中的最特殊的概念，假设空间H H的确切组成是：的确切组成是：G G中包含的假设，中包含的假设，S S中包

33、含的假设以及中包含的假设以及G G和和S S之间偏序之间偏序结构所规定的假设。即：结构所规定的假设。即： H=GSk|GKSH=GSk|GKS 式中式中“”表示变型空间中的偏序关系。表示变型空间中的偏序关系。 示例示例: : Colors=red, ,blue Colors=red, ,blue Shapes=ball, cube Shapes=ball, cube这些对象可以用谓词这些对象可以用谓词obj(Colors, Shapes)obj(Colors, Shapes)来表示。来表示。G:S:(x, y)(red, y)(blue, y)(x, ball)(x, cube)(blue,

34、cube)(blue, ball)(red, cube)(red, ball)GSH没有描述一般示教例子特殊算法算法6.16.1候选项删除算法候选项删除算法（1）把把H初始化为整个规则空间。这时初始化为整个规则空间。这时G仅包含空描述。仅包含空描述。S包含所有最特殊的概念。包含所有最特殊的概念。实际上，为避免实际上，为避免S集合过大，算法把集合过大，算法把S初化为仅包含第一个初化为仅包含第一个示教正例。示教正例。（2）接受一个新的示教例子。如果这个例子是正例，则从）接受一个新的示教例子。如果这个例子是正例，则从G中删除不包含新例的概念，然后修改中删除不包含新例的概念，然后修改S为由新正例和为由

35、新正例和S原原有元素同归纳出最特殊化的泛化。这个过程称为对集合有元素同归纳出最特殊化的泛化。这个过程称为对集合S的修改过程。如果这个例子是反例，则从的修改过程。如果这个例子是反例，则从S中删去包含新中删去包含新例的概念，再对例的概念，再对G作尽量小的特殊化，使之不包含新例。作尽量小的特殊化，使之不包含新例。这个过程称为集合这个过程称为集合G的修改过程。的修改过程。（3）重复步骤）重复步骤，直到，直到G=S，且使这两个集合都只含有一，且使这两个集合都只含有一个元素为止。个元素为止。（4）输出）输出H中的概念（即输出中的概念（即输出G或或S）。）。（sm squ）（sm cir）（lg squ）（

36、lg cir） （sm tri）（sm y）（lg y）（x squ）（x cir）（x tri）（x y）（lg tri）示例示例G0=（x，y ）S0=（sm squ）,（sm cir）,（sm tri）,（lg squ）,（lg cir）,（lg tri）G1=（x y）S1=（sm cir）G2=（x cir），（x squ），（sm y）S2=（sm cir）G3=（x cir）S3=（x cir）6.2.3 6.2.3 归纳偏置归纳偏置 候选消除算法的说明候选消除算法的说明n候选消除算法收敛到正确的假设候选消除算法收敛到正确的假设n训练样例中没有错误训练样例中没有错误nH H中确实

37、包含描述目标概念的正确假设中确实包含描述目标概念的正确假设n如果样例中存在错误如果样例中存在错误n如果给定足够的训练数据，我们会发现如果给定足够的训练数据，我们会发现S S和和G G边界收敛得边界收敛得到一个空的变型空间到一个空的变型空间n如果目标概念不能由假设表示方式所描述如果目标概念不能由假设表示方式所描述n相似情况出现相似情况出现归纳偏置归纳偏置: : 指学习程序用来限制概念空间或者在这指学习程序用来限制概念空间或者在这 个空间中选择概念的任何标准。个空间中选择概念的任何标准。 归纳偏置的强化归纳偏置的强化 : : (1) (1) 经过启发式，推荐新概念描述加到概念描述语经过启发式，推荐

38、新概念描述加到概念描述语言，以确定一个更好的偏置。言，以确定一个更好的偏置。 （2 2）变换推荐的描述成为概念描述语言中已形式）变换推荐的描述成为概念描述语言中已形式化表示的新概念描述，同化任何新概念进入假设的限化表示的新概念描述，同化任何新概念进入假设的限定空间，保持假设空间机制，使得新概念描述语言较定空间，保持假设空间机制，使得新概念描述语言较前面的语言更好。前面的语言更好。 学习正例时，对学习正例时，对S S进行泛化，这往往扩大进行泛化，这往往扩大S S。学习反例时，对学习反例时，对G G进行特化，这往往扩大进行特化，这往往扩大G G。G G和和S S的规模过大会给算法的实用造成困难。算

39、法是的规模过大会给算法的实用造成困难。算法是在训练例子引导下，对规则空间进行宽度优先在训练例子引导下，对规则空间进行宽度优先搜索。对大的规则空间，算法慢得无法接受。搜索。对大的规则空间，算法慢得无法接受。主要缺点主要缺点主要内容机器学习概述归纳学习(变型空间和候选消除算法)n决策树学习n基于实例的学习n强化学习n小结 决策树学习是离散函数的一种树型表示，表示决策树学习是离散函数的一种树型表示，表示能力强，可以表示任意的离散函数，是一种重要的能力强，可以表示任意的离散函数，是一种重要的归纳学习方法。决策树是实现分治策略的数据结构，归纳学习方法。决策树是实现分治策略的数据结构，通过把实例从根节点排

40、列到某个叶子节点来分类实通过把实例从根节点排列到某个叶子节点来分类实例，可用于分类和回归。决策树代表实例属性值约例，可用于分类和回归。决策树代表实例属性值约束的合取的析取式，从树根到树叶的每一条路径对束的合取的析取式，从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析应一组属性测试的合取，树本身对应这些合取的析取。取。 6.3.1 决策树的组成及分类决策树的组成及分类1决策树的组成决策树的组成n决策树由一些决策节点和终端树叶组成，每个决策节点决策树由一些决策节点和终端树叶组成，每个决策节点m m实实现一个具有离散输出的测试函数现一个具有离散输出的测试函数fm(x)fm(x)

41、标记分支。给定一个标记分支。给定一个输入，在每个节点应用一个测试，并根据测试的输出确定输入，在每个节点应用一个测试，并根据测试的输出确定一个分支。这一过程从根节点开始，并递归地重复，直到一个分支。这一过程从根节点开始，并递归地重复，直到到达一个树叶节点。该树叶中的值形成输出。到达一个树叶节点。该树叶中的值形成输出。n每个每个fm(x)fm(x)定义了一个定义了一个d d维输入空间中的判别式，将空间划维输入空间中的判别式，将空间划分成较小区域，在从根节点沿一条路径向下时，这些较小分成较小区域，在从根节点沿一条路径向下时，这些较小的区域被进一步划分。每个树叶节点有一个输出标号，对的区域被进一步划分

42、。每个树叶节点有一个输出标号，对于分类，该标号是类代码，对于回归，则是一个数值。一于分类，该标号是类代码，对于回归，则是一个数值。一个树叶节点定义了输入空间的一个局部区域，落入该区域个树叶节点定义了输入空间的一个局部区域，落入该区域的实例具有相同的输出。依据每个节点所测试的属性的个的实例具有相同的输出。依据每个节点所测试的属性的个数，决策树可分为单变量树和多变量树。数，决策树可分为单变量树和多变量树。2单变量树单变量树 在单变量树中，每个节点的测试值使用一个输入维，也在单变量树中，每个节点的测试值使用一个输入维，也就是只测试一个属性。就是只测试一个属性。w20 x2C1x1w10C2x1w10

43、 x2w20C2C2C1C1YesYesNoNo图6.6单变量树举例3多变量树多变量树 在树的各结点选择多个属性的组合进行测试，一般表现为在树的各结点选择多个属性的组合进行测试，一般表现为通过数学或逻辑算子将一些属性组合起来，形成新的属性作为通过数学或逻辑算子将一些属性组合起来，形成新的属性作为测试属性，因而称这样形成的决策树为多变量决策树。测试属性，因而称这样形成的决策树为多变量决策树。 X2C1C2X1w11x1+w12x2+w100YesNoC2C1图6.7 线性多变量树n如果学习的任务是对一个大的实例集做概念分类的归如果学习的任务是对一个大的实例集做概念分类的归纳定义，而这些例子都是用

44、一些无结构的纳定义，而这些例子都是用一些无结构的“属性属性- -值值”对来表示，那么可以采用决策树学习算法。对来表示，那么可以采用决策树学习算法。n亨特亨特(Hunt)(Hunt)于于19661966年研制了一个概念学习系统年研制了一个概念学习系统CLSCLS，可，可以学习单个概念，并用此学到的概念分类新的实例。以学习单个概念，并用此学到的概念分类新的实例。这是一种早期的基于决策树的归纳学习系统。这是一种早期的基于决策树的归纳学习系统。n 昆兰昆兰(Quinlan)(Quinlan)于于19831983年此进行了发展，研制了年此进行了发展，研制了ID3ID3算算法。该算法不仅能方便地表示概念属

45、性法。该算法不仅能方便地表示概念属性- -值信息的结构，值信息的结构，而且能从大量实例数据中有效地生成相应的决策树模而且能从大量实例数据中有效地生成相应的决策树模型。型。6.3.2 决策树的构造算法决策树的构造算法CLS算法算法6.2 决策树构造算法决策树构造算法CLS：(1)(1)如果如果TRTR中所有实例分类结果均为中所有实例分类结果均为CiCi，则返回，则返回CiCi；(2)(2)从属性表中选择某一属性从属性表中选择某一属性AiAi作为检测属性；作为检测属性；(3)(3)不妨假设不妨假设|ValueType(Ai)|=k|ValueType(Ai)|=k，根据，根据AiAi取值的不同取值

46、的不同, ,将将TRTR划分为划分为k k个训练集个训练集TR1TR1，TR2TR2，TRkTRk，其中：，其中： TRi=|TRTRi=|TR且且V(X,A)V(X,A)为属性为属性A A的第的第i i个个值值 (4)(4)从属性表中去掉已做检测的属性从属性表中去掉已做检测的属性AiAi；(5)(5)对每一个对每一个i(1ik)i(1ik)，用，用TRiTRi和新的属性表递归调用和新的属性表递归调用CLSCLS生成子分支决策树生成子分支决策树DTRiDTRi；(6)(6)返回以属性返回以属性AiAi为根，为根，DTR1DTR1，DTRkDTRk为子树的决策树。为子树的决策树。NoNoNoNo

47、YesNoNo210210alivedead2.52.5No. of WingsBroken WingsStatusArea/weight图图6.8 鸟飞的决策树鸟飞的决策树 6.3.36.3.3基本的决策树算法基本的决策树算法ID3ID3nID3的思想n自顶向下构造决策树自顶向下构造决策树n从从“哪一个属性将在树的根节点被测试哪一个属性将在树的根节点被测试”开始开始n使用统计测试来确定每一个实例属性单独分类训练使用统计测试来确定每一个实例属性单独分类训练样例的能力样例的能力nID3的过程n分类能力最好的属性被选作树的根节点分类能力最好的属性被选作树的根节点n根节点的每个可能值产生一个分支根节

48、点的每个可能值产生一个分支n训练样例排列到适当的分支训练样例排列到适当的分支n重复上面的过程重复上面的过程nID3(Examples, Target_attribute, Attributes)ID3(Examples, Target_attribute, Attributes)n创建树的创建树的rootroot节点节点n如果如果ExamplesExamples都为正都为正, ,返回返回label=+label=+的单节点树的单节点树rootrootn如果如果ExamplesExamples都为反都为反, ,返回返回label=-label=-的单节点树的单节点树rootrootn如果如果At

49、tributesAttributes为空，那么返回单节点为空，那么返回单节点rootroot，label=Exampleslabel=Examples中最普遍中最普遍的的Target_attributeTarget_attribute值值n否则开始否则开始nA AAttributesAttributes中分类中分类examplesexamples能力最好的属性能力最好的属性nrootroot的决策属性的决策属性A An对于对于A A的每个可能值的每个可能值vivin在在rootroot下加一个新的分支对应测试下加一个新的分支对应测试A=viA=vin令令ExamplesExamplesvivi

50、为为ExamplesExamples中满足中满足A A属性值为属性值为vivi的子集的子集n如果如果ExamplesExamplesvivi为空为空n在这个新分支下加一个叶子节点，节点的在这个新分支下加一个叶子节点，节点的label=Exampleslabel=Examples中中最普遍的最普遍的Target_attributeTarget_attribute值值n否则在新分支下加一个子树否则在新分支下加一个子树ID3ID3（ ExamplesExamplesvivi,Target_attribute,Attributes-A,Target_attribute,Attributes-A）n结束

51、结束n返回返回rootrootnID3ID3算法是一种自顶向下增长树的贪婪算法，在每算法是一种自顶向下增长树的贪婪算法，在每个节点选取能最好地分类样例的属性。继续这个过个节点选取能最好地分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或所有的属性程直到这棵树能完美分类训练样例，或所有的属性都已被使用过。都已被使用过。n那么，在决策树生成过程当中，应该以什么样的顺那么，在决策树生成过程当中，应该以什么样的顺序来选取实例集中实例的属性进行扩展呢？即如何序来选取实例集中实例的属性进行扩展呢？即如何选择具有最高信息增益的属性为最好的属性？选择具有最高信息增益的属性为最好的属性？n为了评价属性

52、的重要性，昆兰根据检验每为了评价属性的重要性，昆兰根据检验每一属性所得到的信息量的多少，给出了扩一属性所得到的信息量的多少，给出了扩展属性的选取方法，其中信息量的多少和展属性的选取方法，其中信息量的多少和熵有关。熵有关。信息论简介信息论简介ID3ID3算法算法- -最佳分类属性最佳分类属性- -信息熵，简称熵(1)(1)自信息量自信息量I(a):I(a):设信源设信源X X发出符号发出符号a a的概率为的概率为p(a),p(a),则则I(a)I(a)定定义为义为: : I(a)=-logp(a) ( I(a)=-logp(a) (单位单位:bit):bit) 表示收信者在收到符号表示收信者在收

53、到符号a a之前，对之前，对a a的不确定性，收到后获的不确定性，收到后获得的关于得的关于a a的信息量。的信息量。(2)(2)信息熵信息熵H(X):H(X):设信源设信源X X的概率分布为的概率分布为(X,p(x),(X,p(x),则则H(X)H(X)定义为定义为: : H(X)=-p(x)logp(x) H(X)=-p(x)logp(x) 表示信源表示信源X X的整体不确定性，反应了信源每发出一个符号的整体不确定性，反应了信源每发出一个符号所提供的平均信息量。所提供的平均信息量。(3)(3)条件熵条件熵H(X|Y):H(X|Y):设信源设信源X,YX,Y的联合概率分布为的联合概率分布为p(

54、x,y),p(x,y),则则 H(X|Y)H(X|Y)定义为定义为: : H(X|Y)=- p(x,y)logp(x|y) H(X|Y)=- p(x,y)logp(x|y) 表示收信者在收到表示收信者在收到Y Y后对后对X X的不确定性估计的不确定性估计. .n设给定正负实例的集合为设给定正负实例的集合为S,S,构成训练窗口。构成训练窗口。ID3ID3算法算法视视S S为一个离散信息系统，并用信息熵表示该系统的为一个离散信息系统，并用信息熵表示该系统的信息量。当决策有信息量。当决策有k k个不同的输出时，个不同的输出时，S S的熵为的熵为: :n其中其中P Pi i表示第表示第i i类输出所占

55、训练窗口中总的输出数量类输出所占训练窗口中总的输出数量的比例。的比例。ID3ID3算法算法- -最佳分类属性最佳分类属性kiiiPPSHSEntropy1log)()(n为了检测每个属性的重要性，可以通过属性的信息增益为了检测每个属性的重要性，可以通过属性的信息增益GainGain来评估起重要性。对于属性来评估起重要性。对于属性A A，假设其值域为，假设其值域为(v(v1 1,v,v2 2,v,vn n) )，则训练实例，则训练实例S S中属性中属性A A的信息增益的信息增益GainGain可以可以定义为：定义为：n式中，式中，S Si i表示表示S S中属性中属性A A的值为的值为v vi

56、i的子集；的子集；|S|Si i| |表示集合的势。表示集合的势。ID3ID3算法算法- -最佳分类属性最佳分类属性- -信息增益信息增益niiiSEntropySSSEntropyASGain1)(|)(),()|()(iASEntropySEntropy)|()(iASHSHn昆兰建议选取获得信息量最大的属性作为扩展属性。昆兰建议选取获得信息量最大的属性作为扩展属性。n这一启发式规则又称最小熵原理。因为获得信息量最这一启发式规则又称最小熵原理。因为获得信息量最大，即信息增益大，即信息增益GainGain最大，等价于使不确定性最小，最大，等价于使不确定性最小，即使得熵最小，即条件熵即使得熵最

57、小，即条件熵H(S|AH(S|Ai i) )为最小。为最小。n因此也可以条件熵因此也可以条件熵H(S|AH(S|Ai i) )为最小作为选择属性重要为最小作为选择属性重要性标准。性标准。H(S|AH(S|Ai i) )越小，说明越小，说明A Ai i引入的信息最多，系统引入的信息最多，系统熵下降的越快。熵下降的越快。nID3ID3算法是一种贪婪搜索算法是一种贪婪搜索(Greedy Search)(Greedy Search)算法，即选算法，即选择信息量最大的属性进行决策树分裂，计算中表现为择信息量最大的属性进行决策树分裂，计算中表现为使训练例子集的熵下降最快。使训练例子集的熵下降最快。ID3I

58、D3算法算法- -最佳分类属性最佳分类属性- -信息增益信息增益n现考虑鸟是否能飞的实例，InstancesNo. of WingsBroken WingsLiving statusarea/weightFly120alive2.5T221alive2.5F322alive2.6F420alive3.0T520dead3.2F600alive0F710alive0F820alive3.4T920alive2.0Fn对于上表给出的例子对于上表给出的例子, ,选取整个训练集为训练窗口选取整个训练集为训练窗口, ,有有3 3个正实例个正实例,6,6个负实例个负实例, ,采用记号采用记号3+,6-3+

59、,6-表示总的样表示总的样本数据。则本数据。则S S的熵为的熵为n计算属性计算属性Living StatusLiving Status的信息增益，该属性为值域的信息增益，该属性为值域为为(alive, dead),(alive, dead),则则 S=3+,6-, SS=3+,6-, Salivealive=3+,5-, S=3+,5-, Sdeaddead=0+,1-=0+,1- 先计算先计算Entropy(SEntropy(Salivealive), Entropy(S), Entropy(Sdeaddead) )如下如下: :ID3ID3算法算法- -最佳分类属性最佳分类属性- -例子分

60、析例子分析bitEntropy9179. 0)9/6log(96)9/3log(936 ,3ID3ID3算法算法- -最佳分类属性最佳分类属性- -例子分析例子分析5 ,3)( EntropySEntropyalivebit5835. 0)8/5log(85)8/3log(831 ,0)( EntropySEntropydeadbit0) 1/1log(11) 1/0log(10所以,living status的信息增益为ID3ID3算法算法- -最佳分类属性最佳分类属性- -例子分析例子分析,)(|)(),(deadalivevvvSEntropySSSEntropystatusSGain)