第6章 机器学习

2023/1/311第6章机器学习6.1概述6.2概念学习6.3决策树6.4人工神经网络6.5遗传算法6.1概述6.1.1机器学习的定义6.1.2机器学习系统的基本结构6.1.3一个学习系统的例子6.1.1机器学习的定义学习：系统在不断重复的工作中对本身能力的增强和改进，使得系统在下一次执行同样任务或类似任务时会比现在做得更好或效率更高（西蒙）。机器学习：实现通过经验来提高对某任务处理性能的行为的计算机程序。Michell给出的机器学习的更加形式化的定义：针对某类任务T，如果计算机程序用P衡量的性能根据经验E不断自我完善，那么，我们称这个计算机程序针对某类任务T从经验E中学习，它的性能衡量标准为P。6.1.2机器学习系统的基本结构6.1.2机器学习系统的基本结构环境：提供外界信息，类似于教师的角色。往往以训练数据的形式出现，有些学习系统还需要背景知识，环境所提供信息的水平和质量对学习系统有很大影响。有信息指导的学习系统称为有指导学习，否则称为无指导学习。学习环节：处理环境提供的信息，并接受执行环节的反馈信息，以便得到并改善知识库中的知识，直到满足性能标准，相当于各种学习算法。知识库：学习到的知识，通常是要学习的目标函数的逼近，以某种知识表示形式存储，应便于扩充和改善。执行环节：利用知识库中的知识完成某种任务，目的是测试所学习到的知识的性能，并把执行中的某种情况回送给学习环节（进行评价）。进一步可以运用所学知识解决实际问题。6.1.3一个学习系统的例子设计学习系统包括以下步骤：（1）选择训练经验（环境）；（2）选择目标函数表示形式（知识库）；（3）选择函数逼近算法（学习环节）；（4）选择测试数据测试算法性能（执行环节）1.选择训练经验学习下西洋跳棋程序的训练样例形式为：b：合法棋局，：b的正确走法。显然，环境提供的是直接经验。2.选择目标函数表示形式目标函数ChooseMove：BMB：合法棋局集合M：合法走子集合ChooseMove对输入的棋局产生某个走子（最佳）。或者目标函数V：BRB：合法棋局集合R：实数集合。如采用如下线性函数v计算每个棋局的得分：

其中，b代表一具体格局，由格局特征来描述，其中xi对应棋子的位置、数量等信息，w0~w6是权值，用以区分各个xi的重要程度。3.选择函数逼近算法——选择学习算法利用LMS算法——LMS权值更新法则学习西洋跳棋程序目标函数的过程：步1选一组较小的随机值初始化权值w0~w6。步2对于每一个训练样例<b,vtrain(b)>，使用当前的权值计算：步3对每一个权值wi进行如下更新：

其中，是一个小的常数（如0.1）用来调整权值更新的幅度。可以看出：（1）当为0时，权值不变。（2）当xi为0时，权值也不变。权值更新过程往往要迭代进行多次，其终止的条件可以是：迭代次数达到某固定值，或者是在训练样例上的误差降到某个阈值以下，或者是在分离的验证样例集合上的误差符合某个标准等。

3.选择测试数据测试算法的性能给定一组测试数据<b,vtrain(b)>，按照学习到的函数计算每一个棋局b的得分，考察该得分和vtrain(b)的一致率；或用学习到的函数与人或其他程序对弈，计算它获胜百分比。根据测试结果决定是否需要进一步学习，或修改学习算法。6.2概念学习6.2.1概念学习的FIND-S算法6.2.2FIND-S算法实例2023/1/31126.2.1概念学习的FIND-S算法

概念描述：每个概念可被看作一个对象或事件集合。它是从更大的集合中选取的子集(如从动物的集合中选取鸟类)或者是在较大集合中定义的布尔函数(如在动物集合中定义的函数f，f(鸟类)=true,f(其他动物)=false)。归纳学习：从特殊的训练样例（关于某概念的正例和反例）中归纳出一般的概念描述（函数），它的一般操作是泛化和特化。这也是机器学习的中心问题。(对比定理证明时使用的归纳法)2023/1/31136.2.1概念学习的FIND-S算法概念学习：是归纳学习的一种，指从有关某个布尔函数f（未知）的训练样例(输入,输出)中推断出该布尔函数f，或从样例中逼近布尔函数f。该布尔函数f对未见实例确定其为正例或反例。概念学习的任务可描述为:实例的集合:由各种属性值确定的元组（实例或特征向量）的集合候选假设的集合：为确定目标概念所考虑的概念的范围（假设空间）实例集合上的目标函数（要学习的概念或其逼近，最佳假设）训练样例的集合（训练数据）2023/1/31146.2.1概念学习的FIND-S算法候选假设的形式：<a1，a2，…，an

>实例的各属性的合取式，每个属性可取值：由“?”表示任意本属性可接受的值明确指定的属性值(如Warm)由“”表示不接受任何值如：“Aldo只在寒冷和潮湿的日子里进行水上运动”(并与其他属性无关)是一个假设，可表示为:

<?,cold,high,?,?,?>最一般的假设是每一天都是正例（即每一天都进行水上运动），可表示为:

<?,?,?,?,?,?>最特殊的假设即每一天都是反例（即哪一天都不进行水上运动），表示为:

<,,,,,>6.2.1概念学习的FIND-S算法FIND-S算法基本思想：从最特殊的假设开始，即从“对实例的所有属性取任意值时都是反例”的概念<

，…，>开始然后，在该假设不能正确地划分一个正例时，修改假设，使它更具有一般性（泛化）最终能正确地划分所有的正例如果训练样例没有错误，学习到的假设（目标概念或近似）也能正确地划分所有的反例。这种形式表示的概念也可以转换为规则的形式。2023/1/3116Find－S算法1.将h初始化为H中最特殊假设2.对每个正例x（循环）对h的每个属性约束ai

如果x满足ai

那么不做任何处理

否则将h中ai替换为x满足的更一般的约束3.输出假设h6.2.2FIND-S算法实例下面以FIND-S算法学习目标概念“Aldo进行水上运动的日子”来说明FIND-S算法学习过程。所谓学习目标概念“Aldo进行水上运动的日子”，就是要学习“实例的各个属性满足哪些约束时，Aldo会去做水上运动”。本例中，实例的属性与天气情况有关。2023/1/3118例:

假定给予学习器的一系列训练样例，如表2-1所示。

ExampleSkyAirTempHumidityWindWaterForecastEujoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes6.2.2FIND-S算法实例2023/1/31192.4Find－S：寻找极大特殊假设（3/5）例:

假定给予学习器的一系列训练样例如表2-1所示。FIND-S的第一步是将h初始化为H中最特殊的假设:h<,,,,,>观察第一个训练样例时，它刚好是个正例，这时的h太特殊了。每个属性应该都被替换成能拟合该例的下一个更一般的值约束：

h<Sunny，Warm，Normal，Strong，Warm，Same>第2个训练样例(仍然为正例)迫使该算法进一步将h一般化。这样假设变为:

h<Sunny，Warm，?，Strong，Warm，Same>处理第3个训练样例，这是一个反例，h不变。第4个正例使得h更一般:

h<Sunny，Warm，?，Strong，?，?>6.3决策树6.3.1决策树的表示6.3.2决策树的学习——ID3算法6.3.3ID3算法实例6.3.1决策树的表示1.决策树的表示决策树的根节点和内部节点对应于对实例的某个属性的测试每个节点的所有分支对应于该节点所对应属性的全部可能取值叶子节点给出实例的正确分类从根节点到叶子节点的每一条路径对应一组属性测试的合取整棵树对应这些合取的析取。例如，根据天气情况分类“星期六上午是否适合打网球”的决策树如图6-2所示。对应的概念可以用如下表达式表示：（Outlook=SunnyHumidity=Normal）V（Outlook=Overcast）V（Outlook=RainWind=Weak）还可以表示成IF-THEN规则：IF（Outlook=SunnyHumidity=Normal）

V（Outlook=Overcast）V（Outlook=RainWind=Weak）THENPlayTennis=yes

2.决策树的分类决策树对给定实例的分类过程是按照实例各属性取值情况，在已建好的决策树上从根节点到叶子节点的匹配过程。具体步骤如下：步1从树的根节点开始，测试当前节点指定的属性；步2按照给定实例该属性的取值对应的树枝向下移动，到达下一个节点；步3在以新节点为根的子树上重复步1、2，直到到达叶子节点，得到该实例的正确分类。6.3.2决策树的学习——ID3算法基本的ID3学习算法是通过自顶向下构造决策树来完成的：首先，按照某标准选取一个属性，以该属性作为根节点，以这个属性的全部不同取值作为根节点的分枝，向下增长树，同时按这个属性的不同取值将实例集划分为子集，与相应的分支节点相关联。然后，考察所得的每一个子类，看其中的所有实例的目标值是否完全相同：如果完全相同，则以这个相同的目标值作为相应分枝路径末端的叶子节点；否则，选取一个不同于祖先节点的属性，重复上面过程，直到每个子集中的全部实例的目标值完全相同，得到所有的叶子节点为止基本的ID3学习算法中最关键的问题就是属性选择问题，整个构建过程是从“哪一个属性将在根节点被测试？”开始的。信息增益是用信息论中广泛使用的一个度量标准“熵（entropy）”来定义的：其中S：训练样例集，A：某个属性，Sv：属性A取值为v的样例集，熵的定义是：其中，S：关于某个目标概念的正反样例集，c：目标值的总数，pi：取第i个目标值的样例子集占整个训练样例集的比率。熵刻画了任意样例集的纯度，样例集中只有正例或只有反例时，熵为0，正反例各占一半时，熵为1。通常情况下，熵为0到1之间的值。学习布尔函数的ID3算法ID3（Examples,Target-attribute,Attributes）步1

创建树的Root节点；步2

如果Exampls都为正，那么返回label=+的单节点树Root；步3

如果Exampls都为反，那么返回label=一的单节点树Root；步4如果Attributes为空，则返回单节点树Root,label=Examples中最普遍的Target-attribute值，否则（1）AAttributes中分类Examples能力最好的属性；（2）Root的决策属性

A

；（3）对于A的每个可能值vi：在Root下加一个新的分支对应测试A==vi；令Examples-vi为Examples中满足A属性值为vi的子集；如果Examples-vi为空，则在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target-attribute值；否则，在这个新分支下加一个子树：ID3（Example-vi,Target-attribute,Attributes{A}）步5

返回Root。6.3.3ID3算法实例假定S是一组有关“是否打网球”的训练样例，包含14个样例

DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesDSRainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo6.3.3ID3算法实例属性Wind的信息增益计算如下：类似地，计算其他属性的信息增益：

Gain（S，Outlook）=0.246

Gain（

S，Humidity）=0.151

Gain（

S，Wind）=0.048

Gain（

S，Temperature）=0.0296.3.3ID3算法实例在根节点选择Outlook属性作为测试属性。根节点及其分支的构造如图6-3所示。6.3.3ID3算法实例最终可以得到决策树:2.使用决策树--分类过程给定一个实例：（SunnyMildHighStrong）使用决策树对它进行分类，将沿决策树最左侧分支，得到该实例为反例（No）的分类结果。6.4人工神经网络网络学习的原则是：对于给定的输入，如果网络给出错误的输出，则通过网络的学习，减少其下次犯同样错误的可能性。神经网络学习一般是利用一组训练数据的属性值作为网络的输入，网络按照一定的训练规则（又称学习规则或学习算法）自动调节神经元之间的连接强度或拓扑结构，并计算网络输出。当网络的实际输出满足期望的要求（和训练数据的目标值一致或接近），或者趋于稳定时，则认为学习成功。6.4人工神经网络6.4.1感知器6.4.2线性单元6.4.3多层网络和反向传播算法6.4.4反向传播算法实例6.4.1感知器1.感知器模型如图所示。它以一个实数值向量作为输入，计算这些输入的线性组合，如果结果大于某个阈值，就输出1，否则输出-1。6.4.1感知器2.感知器训练法则从一组随机的权值开始。然后反复地应用这个感知器到每个训练样例，只要它误分类训练样例就修改感知器的权值。重复这个过程，直到感知器正确分类所有的训练样例，即对所有训练样例能够输出正确的目标值。每一步根据如下的感知器训练法则来修改权值：

t是当前训练样例的目标输出，o是感知器的实际输出，是一个正的常数称为学习速率，它的作用是缓和每一步调整权值的幅度。6.4.1感知器单独的一个感知器实现的AND函数：6.4.1感知器双层感知器实现的XOR函数：6.4.2线性单元线性单元可以理解为一个无阈值的感知器，因此，一个线性单元的输出o如下：delta训练法则的关键思想是：使用梯度下降（沿误差曲面下降最快的方向调整权值）来搜索可能的权向量空间，以找到最佳拟合训练样例的权向量。6.4.2线性单元假设训练样例的形式为<x,t>，其中，x是输入值向量，t是目标输出值。是学习速率（例如0.05），用于影响权值调整的幅度。线性单元的梯度下降训练法则--delta法则：步1

初始化每个权wi为某个小的随机值；步2

遇到终止条件之前，做：对于训练样例集中的每个样例<x，t>，做：（1）把实例x输入到线性单元，计算实际输出o；（2）对于线性单元的每个权wi做：终止条件可以选择为：迭代的次数达到某个固定值、或在训练样例上的误差降到某个阈值以下、或在分离的验证样例集合上的误差符合某个标准。6.4.3多层网络和反向传播算法反向传播算法所学习的多层网络则能够表示种类繁多的非线性曲面。6.4.3多层网络和反向传播算法1.sigmoid单元模型sigmoid单元类似于感知器单元，但它对应于一个平滑的可微阈值函数,称为sigmoid函数，也称为logistic函数或挤压函数:6.4.3多层网络和反向传播算法2.分层前向网络6.4.3多层网络和反向传播算法3.分层前向网络的反向传播算法前向网络的反向传播算法（BackPropagation，BP）具有双向操作的特点。其中，网络信号传播是从输入层，到隐藏层，再到输出层。而权值修正则相反，是从输出层到隐藏层，再到输入层。6.4.3多层网络和反向传播算法包含两层sigmoid单元的前向网络的反向传播算法步1

创建具有个输入、个隐藏单元、个输出单元的前向网络步2

初始化所有的网络权值为较小

的随机值（例如－0.05—0.05之间的数）步3

在遇到终止条件前，做：对于训练样例集中的每个样例：把输入沿网络前向传播：把实例x输入网络，并计算网络中每个单元u的输出ou使误差沿网络反向传播：（1）对于网络的每个输出单元k，计算它的误差项k

（2）对于网络的每个隐藏单元h，计算它的误差项k

（3）更新每个网络权值wij：6.4.4反向传播算法实例1981年生物学家格若根（W.Grogan）和维什（W.Wirth）发现了两类蚊子（或飞蠓midges）：Apf和Af。他们测量了这两类蚊子每个个体的翼长和触角长，数据如下：翼长触角长类别1.741.36Af1.641.38Af1.821.38Af1.901.38Af1.701.40Af1.821.48Af1.821.54Af2.081.56Af1.781.14Apf1.961.18Apf1.861.20Apf1.721.24Af2.001.26Apf2.001.28Apf1.961.30Apf如果抓到五只新的蚊子，它们的翼长和触角长分别为[1.78,1.09]，[2.07，1.58]，[1.88，1.40]，[1.90,1.42]，[1.98,1.28]，问它们分别应属于哪一个种类？6.4.4反向传播算法实例1.建立神经网络

6.4.4反向传播算法实例2.准备训练数据因为反向传播算法使用的神经元是sigmoid单元，其输出值在0和1之间，所以规定目标为Apf类时取值0.9，目标为Af类时取值0.1。训练数据为：翼长触角长类别1.781.140.91.961.180.91.861.200.91.721.240.12.001.260.92.001.280.91.961.300.91.741.360.11.641.380.11.821.380.11.901.380.11.701.400.11.821.480.11.821.540.12.081.560.16.4.4反向传播算法实例3.设置隐藏层和输出层单元的权重系数矩阵6.4.4反向传播算法实例4.正向计算各单元的输出（1）对隐藏层单元计算：（2）对输出单元计算：5.反向计算权值修正（1）对输出单元计算：（2）对隐藏层单元计算：6.终止条件设计（1）误差小于某个阈值，如10-4。（2）训练次数达到一定的次数，如40000次。7.实验结果6.5遗传算法6.5.1遗传算法模型6.5.2遗传算法实例6.5.3遗传编程6.5.4遗传编程举例6.5.1遗传算法模型1.假设的表示遗传算法中的个体经常被表示为二进制位串，这种位串也称为染色体，串上的每一位称为基因。规则：

IF（Outlook=OvercastVRain）（Wind=Strong）

THENPlayTennis=yes将被表示为位串：

OutlookWindPlayTennis011101其中，属性outook可以取Sunny、Overcast或Rain

三个值中的任一个，因此，使用一个长度为3的位串顺序地表示Outlook的三个取值，每位对应一个可能值。若某位为1，表示该属性取对应的值（多个位为1表示属性值之间或的关系）。Outlook=Overcast，则编码为010，Outlook=OvercastVRain，编码为011。6.5.1遗传算法模型2.遗传算子遗传算法中，群体的更新换代是通过各种遗传算子完成的，遗传算子作用于染色体上的基因，得到新的染色体。选择：从当前群体中选择一定比例的个体直接进入下一代群体。交叉：将两个双亲染色体中对应的某些基因进行交换，产生新的后代。例如，设有染色体s1=01001011,s2=10010101，交换其后4位基因，得到两个新的子代染色体（个体）：s1’=01000101,s2’=10011011，变异：对染色体的某一基因或某些基因取反，得到新的染色体。例如，设染色体s=11001101，将其第三位上的0变为1,得到一个新的子代染色体：

s=11001101→11101101=s′。6.5.1遗传算法模型2.适应度函数Fitne