ch4机器学习课件

1、第六章 机器学习概述决策树学习神经网络学习机器学习 概述1.机器学习的基本概念：按照人工智能大师西蒙的观点，学习就是系统在不断重复的工作中对本身能力的增强或者改进，使得系统在下一次执行同样任务或类似任务时，会比现在做得更好或效率更高。2.机器学习的定义机器学习是研究如何使用机器来模拟人类学习活动的一门学科。稍为严格的提法是：机器学习是一门研究机器获取新知识和新技能，并识别现有知识的学问。机器能否象人类一样能具有学习能力呢？1959年美国的塞缪尔(Samuel)设计了一个下棋程序，这个程序具有学习能力，它可以在不断的对奕中改善自己的棋艺。4年后，这个程序战胜了设计者本人。又过了3年，这个程序战胜

2、了美国一个保持8年之久的常胜不败的冠军。这个程序向人们展示了机器学习的能力，提出了许多令人深思的社会问题与哲学问题。 机器学习 概述机器学习的任务获得对于输入的数据进行分类的能力。获得解决问题，行为计划和行为控制等的能力。 机器学习 概述为什么要研究机器学习？当前人工智能研究的主要障碍和发展方向之一就是机器学习。包括学习的计算理论和构造学习系统。现在的人工智能系统还完全没有或仅有很有限的学习能力。系统中的知识由人工编程送入系统，知识中的错误也不能自动改正。也就是说，现有的大多数人工智能是演绎的、没有归纳推理，因而不能自动获取和生成知识。机器学习 概述实现的困难： 预测难：学习后知识库发生了什么

3、变化，系统功能的变化的预测。 归纳推理：现有的归纳推理只保证假，不保证真。演绎推理保真。而且，归纳的结论是无限多的，其中相当多是假的，给生成的知识带来不可靠性。 机器目前很难观察什么重要、什么有意义。 机器学习 概述发展历史50年代中期60年代中期（热烈时期）学习的统计计算模型自组织、自适应方法模式识别的产生(指纹、掌心、头骨骼等)，至今还在沿用60年代中期70年代中期（冷清时期）Winston积木世界学习系统 Michalski 大豆病诊断规则程序 概念学习过程，高级知识的符号描述 70年代中期80年代中期（复兴时期） 多个概念的学习，多种学习策略 机器学习与各种应用结合起来 80年：CMU

4、召开了第一次机器学习研讨会 86年：Machine Learning创刊机器学习的最新阶段始于1986年。 决策树学习决策树(Decision Tree) 一种描述概念空间的有效的归纳推理办法。基于决策树的学习方法可以进行不相关的多概念学习，具有简单快捷的优势，已经在各个领域取得广泛应用。决策树学习（概述）决策树学习是以实例为基础的归纳学习。从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。概念分类学习算法：来源于Hunt,Marin和Stone 于1966年研制的CLS学习系统，用于学习单个概念。1979年, J.R. Quinlan 给出ID3算法，并在1983年和1986年对

5、ID3 进行了总结和简化，使其成为决策树学习算法的典型。Schlimmer 和Fisher 于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。1988年，Utgoff 在ID4基础上提出了ID5学习算法，进一步提高了效率。1993年，Quinlan 进一步发展了ID3算法，改进成C4.5算法。另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例决策树学习（概述）1 建立决策树，利用训练样本生成决策树模型。 开始，数据都在根节点递归的进行数据分片2 使用决策树

6、对未知数据进行分类 按照决策树上采用的分割属性逐层往下，直到一个叶子节点判定树分类算法output训练集决策树input决策树学习（决策树）判定结构可以机械的转变成产生式规则。可以通过对结构进行广度优先搜索，并在每个节点生成“IFTHEN”规则来实现。 IF “个子大” THEN IF “脖子短” THEN IF “鼻子长” THEN 可能是大象形式化表示成决策树学习（决策树）构造一棵决策树要解决四个问题：收集待分类的数据，这些数据的所有属性应该是完全标注的。设计分类原则，即数据的哪些属性可以被用来分类，以及如何将该属性量化。分类原则的选择，即在众多分类准则中，每一步选择哪一准则使最终的树更令

7、人满意。设计分类停止条件，实际应用中数据的属性很多，真正有分类意义的属性往往是有限几个，因此在必要的时候应该停止数据集分裂：决策树学习（学习） Shannon信息熵自信息量设信源X发出ai 的概率p(ai)，在收到符号ai之前，收信者对ai 的不确定性定义为ai的自信息量I(ai)。 I(ai) = -logp(ai)。信息熵自信息量只能反映符号的不确定性，而信息熵用来度量整个信源整体的不确定性，定义为： 其中，r为信源X发出的所有可能的符号类型。信息熵反应了信源每发出一个符号所提供的平均信息量。 决策树学习（学习）Shannon信息熵条件熵设信源为X，收信者收到信息Y，用条件熵H(X|Y)来

8、描述收信者在收到Y后对X的不确定性估计。设X的符号ai，Y的符号bj，p(ai|bj)为当Y为bj时，X为ai的概率，则有：平均互信息量用平均互信息量来表示信号Y所能提供的关于X的信息量的大小，用I(X, Y)表示： ID3算法设学习的实例集为 其中Si为学习实例，T实例集大小。对于有指导的学习，任一个Si具有明确标定的类别 ， 向量表示该实例的特性，即Si的信息为，如果一个观测值具有属性则应该划归为类，应该有下面的规则总结出来 信息增益度度量 任意样本分类的期望信息： I(s1,s2,sm)=Pi log2(pi) （i=1,m） S是s个数据样本的集合。类别属性具有m个不同值Ci。si是类

9、Ci中的样本数。pi是任意样本属于Ci的概率，并用si/s估计。由非类别属性A划分为子集的熵：E(A)= (s1j+ +smj)/s * I(s1j， ，smj) 非类别属性A具有v个不同值a1，a2，av。利用A将S划分为v个子集S1，S2，Sv； 其中Sj包含S中在A上具有值aj的样本。Sij是子集Sj中类Ci的样本数。 信息增益：Gain(A)= I(s1,s2,sm) E(A)ID3的基本思想 构造决策树，决策树的每个节点对应一个非类别属性，每条边对应该属性的每个可能值。以信息熵的下降速度作为选取测试属性的标准，即所选的测试属性是从根到当前节点的路径上尚未被考虑的具有最高信息增益的属性

10、。天气温度湿度风况运动晴8585无不适合晴8090有不适合多云8378无适合有雨7096无适合有雨6880无适合有雨6570有不适合多云6465有适合晴7295无不适合晴6970无适合有雨7580无适合晴7570有适合多云7290有适合多云8175无适合有雨7180有不适合决策树天气?overcast湿度?风况?75无有天晴有雨不适合不适合不适合适合适合多云第六章 机器学习概述决策树学习神经网络学习概述什么叫人工神经网络采用物理可实现的系统来模仿人脑神经细胞的结构和功能的系统。为什么要研究神经网络用计算机代替人的脑力劳动。 计算机速度为纳秒级，人脑细胞反应时间是毫秒级。而计算机不如人。 长期以

11、来人类的梦想，机器既能超越人的计算能力，又有类似于人的识别、分析、联想等能力。概述发展史1890年，美国生物学家W.James出版了Physiology（生理学）一书。首次阐明了有关人脑结构及其功能，以及相关学习、联想、记忆的基本规律。指出：人脑中当两个基本处理单元同时活动，或两个单元靠得比较近时，一个单元的兴奋会传到另一个单元。而且一个单元的活动程度与他周围的活动数目和活动密度成正比。概述 发展史1943年McCulloch（心理学家）和Pitts（数理逻辑学家）发表文章，提出M-P模型。描述了一个简单的人工神经元模型的活动是服从二值（兴奋和抑制）变化的。总结了神经元的基本生理特性，提出了神

12、经元的数学描述和网络的结构方法。标志神经计算时代的开始 概述 发展史MP模型的意义：M-P模型能完成一定的逻辑运算 第一个采用集体并行计算结构来描述人工神经元和网络工作。 为进一步的研究提供了依据 （可以完成布尔逻辑计算）概述 发展史1949年Donala U.Hebb（心理学家）论著The Organization of Behavior（行为自组织），提出突触联系强度可变的假设，认为学习的过程最终发生在神经元之间的突触部位，突触的联系强度随着突触前后神经元的活动而变化。赫布规则 多用于自组织网络的学习。即：若两个神经元输出兴奋，则它们之间的连接权加强，反之减少。 Wji(t+1)=wji(

13、t)+ xi(t)xj(t)概述 发展史赫布规则意义（提出了变化的概念）提出了一个神经网络里信息是储藏在突触连接的权中的概念 连接权的学习律是正比于两个被连接神经细胞的活动状态值的乘积 假设权是对称的 细胞的互相连接的结构是他们权的改变创造出来的 概述 发展史1957年Frank Rosenblatt定义了一个神经网络结构，称为感知器(Perceptron) 。意义：第一次把神经网络研究从纯理论的探讨推向工程实现，在IBM704计算机上进行了模拟，证明了该模型有能力通过调整权的学习达到正确分类的结果。掀起了神经网络研究高潮。概述 发展史1969M.Minsky和S. Papert发表了Perc

14、eptrons的论著，指出感知器仅能解决一阶谓词逻辑，只能做线性划分。对于非线性或其他分类会遇到很大困难。一个简单的XOR问题的例子就证明了这一点。神经网络研究一度达到低潮。原因还有：计算机不够发达、VLSI还没出现、而人工智能和专家系统正处于发展高潮。概述 发展史七十年代,据说全球只有几十个人在研究，但还是成功的。如：日本Fukusima的Neocognitron； 芬兰Kohonen的自组织神经网络；Stephen Crossberg的共振自适应理论ART网络等 。概述 发展史1982年John J. Hopfield（物理学家）提出了全联接网络，离散的神经网络模型。全新的具有完整理论基础

15、的神经网络模型。基本思想是对于一个给定的神经网络，对于一个能量函数，这个能量函数是正比于每一个神经元的活动值和神经元之间的联接权。而活动值的改变算法是向能量函数减少的方向进行，一直达到一个极小值为止。证明了网络可达到稳定的离散和连续两种情况。年后AT&T等做出了半导体芯片。神经网络复兴时期开始。 概述 发展史1986年美国的一个平行计算研究小组提出了前项反馈神经网络的Back Propagation（BP）学习算法。成为当今应用最广泛的方法之一。该方法克服了感知器非线性不可分类问题，给神经网络研究带来了新的希望。 概述 发展史1987年在美国召开了第一届世界神经网络大会1000人参加。IJCN

16、N等大会Neural Computing, IEEE Neural Network 等期刊概述符号主义与神经网络共同之处：研究怎样使用计算机来模仿人脑工作过程。学习实践再学习再实践 。不同之处：符号主义研究人脑的推理、学习、思考、规划等思维活动，解决需人类专家才能处理的复杂问题。神经网络企图阐明人脑结构及其功能，以及一些相关学习、联想记忆的基本规则（联想、概括、并行搜索、学习和灵活性） 概述基本原理神经元模型基本原理神经元模型神经元每一个细胞处于两种状态。突触联接有强度。多输入单输出。实质上传播的是脉冲信号，信号的强弱与脉冲频率成正比。 基本原理神经元模型特性函数：神经细胞的输出对输入的反映。

17、(a)xf(x)10神经元中的某些特性（激励）函数(a) 二值函数(b) S形函数 (c) 分段函数(c)xf(x)1(b)f(x)x10基本原理网络结构人脑神经网络：人脑中约有亿个神经细胞，根据Stubbz的估计这些细胞被安排在约个主要模块内，每个模块上有上百个神经网络，每个网络约有万个神经细胞。 基本原理网络模型前馈网络：每层只与前层相联接 基本原理网络模型输入输出有反馈的前馈网络：输出层上存在一个反馈回路，将信号反馈到输入层。而网络本身还是前馈型的基本原理网络模型前馈内层互联网络：外部看还是一个前向网络，内部有很多自组织网络在层内互联着。基本原理网络模型反馈型全互联网络：所有计算单元之间

18、都有联接。如：Hopfield网络 基本原理基本属性基本属性：非线性非局域性非定常性非凸性基本原理优缺点评价优点：并行性；分布存储；容错性；学习能力 缺点：不适合高精度计算；学习问题没有根本解决，慢；目前没有完整的设计方法，经验参数太多。 前馈型神经网概述最初称之为感知器。应用最广泛的一种人工神经网络模型，最要原因是有BP学习方法。前馈网络结构是分层的，信息只能从下一层单元传递到相应的上一层单元。上层单元与下层所有单元相联接。特性函数可以是线性阈值的。 前馈型神经网单层感知器前馈型神经网基本原理，结构简单。很少在实际应用中出现。采用阶跃函数作为特性函数。输出yi等于：(1)其中前馈型神经网单层

19、感知器分类方法：如果输入x有k个样本，xp, p=1, 2, , k, xRn当将这些样本分别输入到单输出的感知器中，在一定的和下，输出有两种可能+1或-1。举个例子：银行贷款：什么情况下可以，什么情况下不可以分为条件x1, x2, x3 , , xk，过去有很多贷款实例。形成一个表：0 x1, x2, x3,xk贷款101010101011211001010100。1+X1X2二维输入感知器及其在状态空间中的划分 简单感知器引入的学习算法称之为误差学习算法： 误差型学习规则： (1)选择一组初始权值wi(0)。 (2)计算某一输入模式对应的实际输出与期望输出的误差(3)如果小于给定值，返回2

20、，否则继续。 (4)更新权值(阈值可视为输入恒为1的一个权值)： wi（t+1） wi（t+1）- wi（t） dy(t)xi。 式中为在区间(0，1)上的一个常数，称为学习步长，它的取值与训练速度和w收敛的稳定性有关；d、y为神经元的期望输出和实际输出；xi为神经元的第i个输入。 (5)返回(2)，重复，直到对所有训练样本模式，网络输出均能满足要求。 简单的分类例题(XOR) 其中a, b是输入单元，c, d是隐单元，e是输出单元。单元的激活值规定取1或0，每个单元的输出函数都取为等价函数，即a=o。单元的net值是所有输入的加权和：net=wo 。单元的激活函数采用阈值函数，阈值为0.01

21、。即当单元的net值大于0.01时该单元的激活值取1，否则取0。dbcae+1+1+1+1-1-1 输入 输出 阈值 ( 0 0 ) 0 =0.01 ( 0 1 ) 1 ( 1 0 ) 1 ( 1 1 ) 0=0.01 =0.01 =0.01 简单的分类计算 1. 输入为(0, 0)时，oa=ob=0 netc = oawca + obwcb = 01+ 0(-1)= 0 netd = oawda + obwdb = 0(-1)+ 01= 0 因为 netc0.01，netc 0.01，所以 ac=0，ad=0 得到oc=0, od=0。所以 nete = ocwec + odwed = 01

22、 + 01 = 0 因为 nete0.01 所以 oe=ae=0 即当输入为(0, 0)时，网络的输出为0。dbcae+1+1+1+1-1-1=0.01 =0.01 =0.01 简单的分类计算 2. 网络输入为(0, 1)时，oa=0, ob=1 netc = oawca + obwcb = 01+1(-1)= -1 netd = oawda + obwdb = 0(-1)+ 11= 1 因为 netc 0.01 所以 oc= ac= 0, od= ad= 1。得 nete = ocwec + odwed = 01 + 11 = 10.01 oe=ae=1 即当输入为(0, 1)时，网络的输出

23、为1。dbcae+1+1+1+1-1-1=0.01 =0.01 =0.01 例题总结 同样当网络输入为(1, 0)时，网络的输出为1。 当网络输入为(1, 1)时，网络的输出为0。 因此，神经网络完成了一个影射，起到了函数的作用。由于其中的机理不清楚，也称“黑箱”。dbcae+1+1+1+1-1-1=0.01 =0.01 =0.01 “黑箱” 或函数 F 输入 ( 0 0 ) ( 0 1 ) ( 1 0 ) ( 1 1 )输出 0 1 1 0前馈型神经网多层感知器 多层感知器的输入输出关系与单层感知器完全相同。前一层的输出是下一层的输入。也被称为BP网络。反向传播(BP)网络的基本结构主要有以

24、下特点： 1. 至少有一层隐单元； 2.增加隐藏层的层数和隐藏层神经元个数不一定总能够提高网络精度和表达能力。BP网一般都选用三层网络。 3. 单元的激活函数是它总输入的非递减可微函数，实际应用中常选取S型函数，如 Logsigmoid或Tansigmoid函数 4.包括两个过程： i) 正向的计算传播； ii) 逆向的误差传播过程。dbcaewvv dbcagwufe 网络的拓扑结构x0y0输出层隐藏层输入层x1y1Ym-1Xn-1W1WlogSigmoid函数基本形式及图形01BP网络的学习其根本思想是： i) 建立描述网络实际输出与目标输出的差值ii) 找到使E最小的一个权重集合iii)

25、E中yl是权值wij的函数 所以E也是权值wij的函数。为使E最小，需选取E曲面上一个梯度下降最快的方向修改wij。即：权值的改变量与E的负导数成比例 wij=- (E/wij) BP网络权重学习算法的最一般形式 E中的权重分为两种，连接到隐单元的和到输出单元的。因而从wij=- (E/wij)中导出的权值计算就有两种: i) 对于输出单元的连接权ii) 对于隐单元的连接权 程序结构分析。 网络初始设定：随机权重W、随机阈值B、学习率、网络误差E、隐结点个数等。初始设定前向计算误差传播权值修改 网络训练是建立网络模型的核心内容，是一个循环体，分为前向计算、误差逆向传播、权值修改等。然后根据初始设定的误差决定是否停止训练。样本检验参数存储 训练结束后，继续使用检验样本对网络进行适应性验证。 当考证网络具备所要求的性能后，将网络涉及的各种参数存储，以备建立实际系统。例：保定市的降水模型 通过对降水过程的总结，建立保定降水的简单预报模型：1、东高西低：高空天气形势应该具备东部是高压或高压脊，西部有低压或低压槽，保定位于南或西南气流里，简称东高西低；2、垂直运动条件：降水时一定存在低层要有水平辐合，高层水平辐散，有上