第9部分机器学习与知识发现教案资料

《第9部分机器学习与知识发现教案资料》由会员分享，可在线阅读，更多相关《第9部分机器学习与知识发现教案资料（122页珍藏版）》请在金锄头文库上搜索。

1、第 9 章 机器学习与知识发现,9.1 机器学习概述 9.2 符号学习 9.3 神经网络学习 9.4 知识发现与数据挖掘 习题九,9.1 机器学习概述,9.1.1 机器学习的概念 心理学中对学习的解释是: 学习是指(人或动物)依靠经验的获得而使行为持久变化的过程。人工智能和机器学习领域的几位著名学者也对学了各自的说法。 如Simon认为:如果一个系统能够通过执行某种过程而改进它的性能, 这就是学习。Minsky认为: 学习是在人们头脑中(心理内部)进行有用的变化。Tom M. Mitchell在机器学习一书中对学习的定义是: 对于某类任务T和性能度P, 如果一个计算机程序在T上以P衡量的性能随

2、着经验E而自我完善, 那么, 我们称这个计算机程序从经验E中学习。 ,9.1.2 机器学习的原理 从以上对于学习的解释可以看出: (1) 学习与经验有关。 (2) 学习可以改善系统性能。 (3) 学习是一个有反馈的信息处理与控制过程。因为经验是在系统与环境的交互过程中产生的,而经验中应该包含系统输入、响应和效果等信息。因此经验的积累、性能的完善正是通过重复这一过程而实现的。,图 9-1 机器学习原理1,图9-1所示的学习方式现在一般称为记忆学习。例如, Samuel的跳棋程序就采用这种记忆学习方法。还有,基于范例的学习也可以看作是这种记忆学习的一个特例。记忆学习实际上也是人类和动物的一种基本学

3、习方式。然而, 这种依靠经验来提高性能的记忆学习存在严重不足。其一,由于经验积累是一个缓慢过程, 所以系统性能的改善也很缓慢; 其二,由于经验毕竟不是规律, 故仅凭经验对系统性能的改善是有限的, 有时甚至是靠不住的。 所以, 学习方式需要延伸和发展。可想而知,如果能在积累的经验中进一步发现规律, 然后利用所发现的规律即知识来指导系统行为,那么,系统的性能将会得到更大的改善和提高，于是, 我们有图9-2所示的机器学习原理2。,图 9-2 机器学习原理2,可以看出,这才是一个完整的学习过程。它可分为三个子过程, 即经验积累过程、知识生成过程和知识运用过程。事实上,这种学习方式就是人类和动物的技能训

4、练或者更一般的适应性训练过程, 如骑车、驾驶、体操、游泳等都是以这种方式学习的。所以, 图9-2所示这种学习方式也适合于机器的技能训练, 如机器人的驾车训练。 但现在的机器学习研究一般都省去了上面的经验积累过程, 而是一开始就把事先组织好的经验数据(包括实验数据和统计数据)直接作为学习系统的输入, 然后对其归纳推导而得出知识, 再用所得知识去指导行为、改善性能, 其过程如图9-3所示。在这里把组织好的经验数据称为训练样本或样例, 把由样例到知识的转换过程称为学习或训练。,图 9-3 机器学习原理3,考察上面的图9-1、 图9-2和图9-3可以发现, 从经验数据中发现知识才是机器学习的关键环节。

5、所以, 在机器学习中, 人们就进一步把图9-3所示的机器学习过程简化为只有知识生成一个过程(如图9-4 所示), 即只要从经验数据归纳推导出知识就算是完成了学习。 可以看出, 图9-4所示的这类机器学习已经与机器学习的本来含义不一致了, 实际上似乎已变成纯粹的知识发现了。,图 9-4 机器学习原理4,图 9-5 机器学习原理5,9.1.3 机器学习的分类 从图9-5可以看出, 机器学习可分为信息、发现和知识三个要素, 它们分别是机器学习的对象、方法和目标。那么, 谈论一种机器学习, 就要考察这三个要素。而分别基于这三个要素, 就可以对机器学习进行分类。例如,由于信息有语言符号型与数值数据型之分

6、, 因此基于信息,机器学习可分为符号学习和数值学习; 而基于知识的形式,机器学习又可分为规则学习和函数学习等; 若基于发现的逻辑方法, 则机器学习可分为归纳学习、演绎学习和类比学习等等。 这样的分类也就是分别从“从哪儿学？”、“怎样学？” 和“学什么？”这三个着眼点对机器学习进行的分类。,1. 基于学习策略的分类 1) 模拟人脑的机器学习 (1) 符号学习: 模拟人脑的宏观心理级学习过程, 以认知心理学原理为基础, 以符号数据为输入, 以符号运算为方法, 用推理过程在图或状态空间中搜索, 学习的目标为概念或规则等。符号学习的典型方法有记忆学习、示例学习、演绎学习、 类比学习、解释学习等。 (2

7、) 神经网络学习(或连接学习):模拟人脑的微观生理级学习过程, 以脑和神经科学原理为基础,以人工神经网络为函数结构模型, 以数值数据为输入, 以数值运算为方法,用迭代过程在系数向量空间中搜索,学习的目标为函数。典型的连接学习有权值修正学习、拓扑结构学习等。,2) 直接采用数学方法的机器学习 这种机器学习方法主要有统计机器学习。而统计机器学习又有广义和狭义之分。 广义统计机器学习指以样本数据为依据,以概率统计理论为基础,以数值运算为方法的一类机器学习。在这个意义下, 神经网络学习也可划归为统计学习范畴。 统计学习又可分为以概率表达式函数为目标和以代数表达式函数为目标两大类。 前者的典型有贝叶斯学

8、习、贝叶斯网络学习等, 后者的典型有几何分类学习方法和支持向量机(SVM)。 经典文献(1)Vladimir N. Vapnik（弗拉基米尔）,译者：许建华，统计学习理论ISBN号：978-7-121-08372-3，2009-03 (2)王双成. 贝叶斯网络学习、推理与应用,立信会计出版社,2. 基于学习方法的分类 1) 归纳学习 (1) 符号归纳学习: 典型的符号归纳学习有示例学习、 决策树学习等。 (2) 函数归纳学习(发现学习): 典型的函数归纳学习有神经网络学习、示例学习、发现学习、 统计学习等。 2) 演绎学习 3) 类比学习 典型的类比学习有案例(范例)学习。 4) 分析学习 典

9、型的分析学习有案例(范例)学习和解释学习等。,3. 基于学习方式的分类 (1) 有导师学习(监督学习,supervised learning):利用一组已知类别的样本调整分类器的参数，使其达到所要求性能的过程，也称为监督训练或有教师学习。正如人们通过已知病例学习诊断技术那样，计算机要通过学习才能具有识别各种事物和现象的能力。用来进行学习的材料就是与被识别对象属于同类的有限数量样本。监督学习中在给予计算机学习样本的同时，还告诉计算各个样本所属的类别。若所给的学习样本不带有类别信息,就是无监督学习。任何一种学习都有一定的目的,对于模式识别来说，就是要通过有限数量样本的学习，使分类器在对无限多个模式

10、进行分类时所产生的错误概率最小。 (2) 无导师学习(无监督学习，unsupervised learning):设计分类器时候，用于处理未被分类标记的样本集。输入数据中无导师信号, 采用聚类方法,学习结果为类别。典型的无导师学习有发现学习、聚类学习、竞争学习等。 (3) 强化学习(增强学习): 以环境反馈(奖/惩信号)作为输入, 以统计和动态规划技术为指导的一种学习方法。,4. 基于数据形式的分类 (1) 结构化学习: 以结构化数据为输入,以数值计算或符号推演为方法。典型的结构化学习有神经网络学习、统计学习、决策树学习和规则学习。 (2) 非结构化学习:以非结构化数据为输入, 典型的非结构化学

11、习有类比学习、案例学习、解释学习、文本挖掘、图像挖掘、 Web挖掘等。,5. 基于学习目标的分类 (1) 概念学习: 即学习的目标和结果为概念, 或者说是为了获得概念的一种学习。典型的概念学习有示例学习。 (2) 规则学习: 即学习的目标和结果为规则, 或者说是为了获得规则的一种学习。典型的规则学习有决策树学习。 (3) 函数学习: 即学习的目标和结果为函数, 或者说是为了获得函数的一种学习。典型的函数学习有神经网络学习。,(4) 类别学习: 即学习的目标和结果为对象类, 或者说是为了获得类别的一种学习。 典型的类别学习有聚类分析。 (5) 贝叶斯网络学习: 即学习的目标和结果是贝叶斯网络,

12、或者说是为了获得贝叶斯网络的一种学习。其又可分为结构学习和参数学习。 当然, 以上仅是机器学习的一些分类而并非全面分类。 事实上,除了以上分类外, 还有许多其他分法。 例如, 有些机器学习还需要背景知识作指导, 这就又有了基于知识的机器学习类型。 如解释学习就是一种基于知识的机器学习。,9.2 符号学习,9.2.1 记忆学习 记忆学习也称死记硬背学习或机械学习。这种学习方法不要求系统具有对复杂问题求解的能力, 也就是没有推理能力, 系统的学习方法就是直接记录与问题有关的信息, 然后检索并利用这些存储的信息来解决问题。例如, 对于某个数据x, 经过某种计算过程得到的结果是y, 那么系统就把(x,

13、 y)作为联想对存储起来, 以后再要对x 作同样的计算时,就可通过查询(而不是计算)直接得到y。又如,对于某个事实A, 经过某种推理而得到结论B, 那么就可把序对(A, B)作为一条规则而记录下来, 以后就可以由A直接得到B。,使用记忆学习方法的一个成功例子是Samuel的跳棋程序(1959年开发), 这个程序是靠记住每一个经过评估的棋局势态, 来改进弈棋的水平。程序采用极小极大分析的搜索策略来估计可能的未来棋盘局势, 学习环节只存储这些棋盘势态估值及相应的索引, 以备以后弈棋使用。 例如某一个势态A轮到程序走步, 这时程序考虑向前搜索三步, 根据假设的端节点静态值, 用极小极大法可求得A的倒

14、推值Av。这时系统记住了该棋局及其倒推值A,Av。现在假定以后弈棋中, 棋局E的搜索树端节点中出现了A,这时就可以检索已存的Av来使用, 而不必再去计算其静态估值。这不仅提高了搜索效率,更重要的是A的倒推值比A的静态值更准确。用了所记忆的A倒推值,对棋局E来说, 相当于局部搜索深度加大到6, 因而E的结果得到了改善。根据文献报道,Samuel程序由于有机械学习机制, 最后竟能战胜跳棋冠军。,机械学习是基于记忆和检索的办法, 学习方法很简单, 但学习系统需要几种能力。 (1) 能实现有组织的存储信息。为了使利用一个已存的信息比重新计算该值来得快, 必须有一种快速存取的方法。如在Samuel的程序

15、中,通过对棋子位置的布局上加几个重要特征(如棋盘上棋子的数目)做为索引以利于检索。 ,(2) 能进行信息综合。通常存储对象的数目可能很大, 为了使其数目限制在便于管理的范围内, 需要有某种综合技术。 在Samuel程序中, 被存储的对象数目就是博弈中可能出现的各种棋局棋子位置数目, 该程序用简单的综合形式来减少这个数目, 例如只存储一方棋子位置, 就可使存储的棋子位置数目减少一半, 也可以利用对称关系进行综合。,(3) 能控制检索方向。 当存储对象愈多时, 其中可能有多个对象与给定的状态有关,这样就要求程序能从有关的存储对象中进行选择, 以便把注意力集中到有希望的方向上来。Samuel程序采用

16、优先考虑相同评分下具有较少走步就能到达那个对象的方向。,9.2.2 示例学习 示例学习也称实例学习, 它是一种归纳学习。示例学习是从若干实例(包括正例和反例)中归纳出一般概念或规则的学习方法。 例如学习程序要学习“狗”的概念, 可以先提供给程序以各种动物, 并告知程序哪些动物是“狗”, 哪些不是“狗”, 系统学习后便概括出“狗”的概念模型或类型定义, 利用这个类型定义就可作为动物世界中识别“狗”的分类的准则。 这种构造类型定义的任务称为概念学习, 当然这个任务所使用的技术必须依赖于描述类型(概念)的方法。 下面我们使用Winston(1975年开发) 的结构化概念学习程序的例子作为模型来说明示例学习的过程。,Winston的程序是在简单的积木世界领域中运行,其目的是要建立积木世界中物体概念定义的结构化表示,例如学习房子、帐篷和拱的概念,构造出这些概念定义的结构化描述。 系统的输入是积木世界某物体(或景象)的线条图, 使用语义网络来表示该物体结构化的描述。例如系统要学习拱桥概念, 就给学习程序输入第一个拱桥示例,得到的描述如图 9-6所示,这个结构化的描述就是拱桥概