线性判别函数ppt课件.ppt

《线性判别函数ppt课件.ppt》由会员分享，可在线阅读，更多相关《线性判别函数ppt课件.ppt（50页珍藏版）》请在三一办公上搜索。

1、第2章 线性判别函数,2.1 线性判别函数和决策面2.2 感知准则函数2.3 最小平方误差准则函数2.4 多类判别问题2.5 分段线性判别函数2.6 Fisher线性判别函数2.7 支持向量机,课前思考题：(1) 机器能否像人类一样通过例证教育认知事物，修正 观念中的错误的成分?(2) 机器学习过程中有教师吗？谁是教师？(3) 什么叫线性分类器? 什么条件下才能用线性分类器？,2.1 线性判别函数和决策面,线性判别函数是统计模式识别方法中的一个重要的基本方法。它是由训练样本集提供的信息直接确定决策域的划分。,在训练过程中使用的样本集，该样本集中的每个样本的类别已知。,由于决策域的分界面是用数学

2、式子来描述的，如线性函数，或各种非线性函数等。因此确定分界面方程，这包括选择函数类型与确定最佳参数两个部分。一般说来选择函数类型是由设计者确定的，但其参数的确定则是通过一个学习过程来实现的，是一个迭代实现优化的过程。本章讲最简单的函数类型线性函数。,假设抽取到的模式样本的边界是“整齐”而不是混杂的，而且以后遇到的待分类模式基本上不超过学习样本的分类范围，从而利用这些样本得出的分类边界是无误差的。因此这些模式类之间的分界面，可以利用线性判别函数来进行。 对于n维空间中的c 个模式类别各给出一个由n个特征组成的单值函数，这叫做判别函数。在c类的情况下，我们共有c个判别函数，记为g1(x)，g2(x

3、)， gc(x) ，它们分别对应于模式类1 ，2 ，c 。,作为判别函数，它应具有如下的性质：假如一个模式X属于第i类，则有： 而如果这个模式在第i类和第j类得分界面上，则有： 如果判别函数取线性判别函数，它是所有模式特征的线性组合。对于第i类模式，有如下形式： 式中 是特征的系数，称为权， 为阈值权。 如果对第i类模式定义n维权向量为： 则判别函数可写成更简洁的形式：,讨论二类情况下的线性判别函数。两个线性判别函数如果X属于 ，可得：令则二类模式的线性分类器的决策法则是： 如果 ，则决策 ，即把 归到 类去； 如果 ，则决策 ，即把 归到 类去。,线性分类器是指两类决策域的界面方程是单个线性

4、方程。,是决策面方程，它是两类模式的分界，对于二维空间情况，它是一条直线；对于三维情况，它是一个平面；而对于高维空间的情况，则是一个超平面。,构造一个二类模式的线性分类器，如下图所示：,在二类模式的情况下，决策面H把模式空间分成两个半空间，即对 的决策域 和对 的决策域 。因为当特征向量 在 中时 ，所以决策面的法向量的方向指向 。我们称 位于决策面H的正面， 位于决策面H的反面。,为了说明向量W的意义，我们假设在决策平面上有两个特征向量X1与X2，则应有 (*)其中(X1-X2)也是一个向量，(*)式表明向量W与该平面上任两点组成的向量(X1-X2)正交，因此W的方向就是决策面的法线方向。,

5、决策面H,右图中，H是决策面，它的方程为 ， 是权向量，也就是决策面的法线方向。 是待识别的模式的特征向量。,g(X) 就是n维空间中任一点X到该决策面距离的代数度量，该决策平面将这两类样本按其到该面距离的正负号确定其类别。若把X表示成：,式中Xp: 是 在H上的投影向量，r : 是 到H的垂直距离， ：是w方向上的单位向量。,x,x,结论：利用线性判别函数进行决策，就是用一个超平面把特征空间分割成两个决策区域，超平面方向由权向量W决定，它的位置由阈值权w0确定。,=0,如果 ，则原点在H的正面；如果 ，则原点在H的反面。对于图所示情况， 。若 ，则判别函数有齐次形式: 说明超平面H通过原点。

6、,坐标原点到该决策面的距离为 。,设计线性分类器，是指所用的判别函数、分界面方程的类型已选定为线性类型，因此主要的设计任务是确定线性方程的两个参数，一个是权向量W，另一个是阈值 。为了使所设计的线性分类器在性能上要满足一定的要求，这种要求通过一种准则来体现，并且要表示成一种准则函数，以便能通过将准则函数值优化的方法确定W与 。,2.2感知准则函数,感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。,线性判别函数 可改

7、写为：,于是线性判别函数 就变成了(n+1)维空间的齐次线性函数。,定义增广模式向量:,定义广义权向量:,对于二类模式问题，在这个(n+1)维空间的决策面H的方程就是：,因为阈值为0，所以超平面H通过原点。这样，找寻决策面的问题就简化为求权向量 的问题。,在线性可分条件下，广义权向量A合适的话应有：,为了方便起见，如果我们令,则合适的A能使所有的Y满足A TY0。（后面用Y表示Y ）经过这样的规格化处理后，问题就转化为：求使每一个样本Y满足A TY0的权向量A的问题了。权向量A称为解权向量。,线性可分是说该训练样本集中的两类样本可以用一个线性分界面正确无误的分开。,这里 是由于使用权向量A而被

8、误分类的样本集合。当一个样本 被误分类时，就有 ，所以 ，可见，是解权向量 的函数。仅当 时， 达到极小值，即 。或者说，当对于某个向量 ，准则函数 达到极小值的话， 就是解权向量，这时没有样本被错分类。在几何上，感知准则函数正比于被错分样本到决策面的距离之和。,为了求解线性不等式组A TY0，构造一个准则函数：,感知准则函数：,因为（ ）,有了准则函数 ，需要用最优化方法寻找 达到极小值的解权向量A。可以采用梯度下降算法来求解。,是一个正的比例因子，称为步长或增量。,梯度下降法的算法步骤：（1）先任意选择一个初始的权向量（2）把第K次的权向量加上被误分类的样本的和与某个常数 的乘积，就得到第

9、（K+1）次的权向量。（3）理论上可以证明，只要二类样本是线性可分的，无论初值如何选取，经过有限次迭代，这个算法总可以收敛，即使得每一个样本满足A TY0 。,该算法的缺点是：每次迭代必须遍历全部样本，才能得到当前权向量 下的误分样本集 ，从而进一步纠正 的值。,固定增量算法及其收敛性,固定增量算法是解线性不等式组的一种最简单的方法。它可以由梯度下降法作如下两点改变得到： （1）把全部样本看作是一个序列，每当前一步迭代的权向量把某个样本错误分类时，就对这个权向量做一次修正，而不是等当前权向量 对全部样本计算后再找出错分类样本集 去进行修改。 （2）考虑每次迭代时 保持不变，这就是固定增量的情况

10、，也就是说乘上一个固定的比例因子。,二类情况下用固定增量法求解权向量的方法： 设已知二类模式的样本集 和 ，这些样本都已变成增广模式的形式，要求用固定增量算法决定一个超平面 ，使它能正确划分样本集 。 开始时，可以任意假定 为域决策界面的那一边，也可以任意选择广义权向量 的初始值 。 然后把训练集 中的增广模式向量 依次取出，计算 的内积 ，权向量 用如下规则调整： 如果 ，而 ，则用 代替 ； 如果 ，而 ，则用 代替 ； 如果 ，而 ，则 保持不变； 如果 ，而 ，则 保持不变。,属于 的全部模式向量都用上述方法处理一遍，成为一次迭代。这个算法继续重新执行，直到某次迭代后中的成员都通过这个

11、程序而权向量 不再变化为止，这时称为程序收敛。如果在某一次迭代中权向量 已经保持不变，则权向量 即解权向量 。所以在程序收敛后即无必要进一步执行迭代了。如果 不是线性可分的，则程序不会收敛，而迭代将无限进行下去，所以在编制程序时应考虑或在一定时间限度内停止，或当权向量在一个不收敛区域内循环而停止。 这个算法可以推广到下述更一般的情况： 模式不一定是二值的； 执行迭代时，增广模式向量集 中成员的次序可任意选定； 不要求 中有相等数量的模式； 初始权向量可以任意选择。,2.3 最小平方误差准则函数,最小平方误差准则函数是一个基于全体样本的准则函数，要求满足等式 ， ，其中 是一些任意指定的正常数。

12、 令 为一个 矩阵，它的各行 是向量 ，令 为一个列向量，则问题变为：对于给定的 和要求找到一个权向量 ，使得 多数情况下，只可能找到一个这样的解权向量 ，它使 与 之间的误差极小化。如果定义误差向量e为 则求 为最优的方法是使误差向量e的长度的平方极小。这就是使误差平方和准则函数 极小化。这就是矛盾方程组的最小二乘解（MSE解）。,对准则函数求导并令其为零，得准则函数极小化的必要条件：于是将解 的问题转化为解 。这里 是一个 维方阵，且常为非奇异。如果它是非奇异的，可以得到 的唯一解：此处 矩阵 称为 的伪逆 。如果 为奇异阵，得到的解不唯一。 MSE解依赖于向量b，b的不同选择可以给予解以

13、不同的性质。当b任意给定时，MSE解在线性可分的情况下不会总是产生一个正确的分界面，但可以找到一个有用的判别函数。,dn,为避免上述缺点，可以采用梯度下降算法。梯度下降算法为： （1）首先任意制订初始权向量 ； （2）如第k步不能满足要求则按下式求第（k+1）步的权向量可以证明，如果 ，其中 是任意常数，则这个算法产生的权向量序列 ， 收敛于满足方程式 。且不管 是否为奇异矩阵，这个下降算法总能产生一个解。,MSE方法的计算工作量很大，要求解 维矩阵的逆，并证明 是非奇异的。,2.4 多类判别问题,以上讨论的都是两类别问题，但是实际问题中常遇到的是多类别问题。可以把两类别问题中使用的线性判别函

14、数方法推广到多类别问题中，但可有不同做法。,一种最简单作法是将C类别问题化为(C-1)个两类问题，即将第i类与所有非i类样本，按两类问题确定其判别函数与决策面方程。因此对于C类，则总共有(C-1)个两类别问题，如图所示。这种做法存在两个问题，一是可能会出现一些不定区域，如图中阴影所示，在这些区域中的样本无法确定其类别。原因是用线性判别函数对i类及所有非i类进行划分并不能保证获得性能良好的划分，硬性使用线性分类器可能会产生很不好的效果。,另一种相对麻烦些的做法是将C类中的每两类别单独设计其线性判别函数，因此总共有C(C-1)/2个线性判别函数。这种方法如图所示。这种方法由于每个判别函数针对每两类

15、别样本设计，预期可有好效果，但仍有不定区域，在该区域内样本类别无法确定。,由于样本在特征空间分布的复杂性，许多情况下采用线性判别函数不能取得满意的分类效果。也就是说，在n维模式样本集线性可分的情况下，如果训练集足够大，就可能得到较好的分类结果。所以它应用于简单的线性可分集是一个很好的工具。对于比较复杂的问题，当样本不是线性可分时，用超平面分类，就会导致较大的分类错误率。,2.5 分段线性判别函数,为了解决比较复杂的线性不可分样本分类问题，提出了非线性判别函数。这个分界面是一个超曲面。如图所示的分界面 所示。但是非线性判别函数计算复杂，实际应用上受到较大的限制。解决问题的另一个方法是采用多个线性

16、分界面，将它们分段连接，用分段线性划分去逼近分界的超曲面。如图分界面 所示。他的决策面由几个超平面段组成。它,有可能利用已知的线性判别函数来解决分类问题，并较好地逼近分类的超曲面，从而减少分类误差。,由于分段线性划分的解可能由不同的样本分割方式形成，一般情况下不是唯一的。但每个解都能满足要求。 分段线性划分也存在误差。处理分类误差可有二种方法： （1）增加超平面数目，达到满足当前样本正确分类的目的； （2）适当限制超平面数目，而允许一定的分类误差存在。 因为问题是非参数的，我们除了分类好的样本外一无所知，所以在有限样本的情况下，我们仅能讨论是当前样本下误差最小，这可以在多个可能解中用误分样本数

17、最小或误差平方和最小作为准则来达到。一般说来，当样本足够大时，分段线性分界面是渐进于真实的超曲面分界的，因而这样的分界面是可行的。而在小样本的情况下，很难说一个算法得到的结果是最优的。,下面介绍两种二类线性判别函数推广得到的分段线性判别函数的算法。,如图所示，先用二类线性判别函数找出一个分界面 ， 它将样本大致分成两类。因为样本集不是线性可分的，所以 两面的模式都会混杂。再对 的正反面的模式样本分别应用线性判别函数求得和 ，如此继续下去，直至每个分界面都将样本正确分类为止。连接相应的各分界面 ，,，即得分段线性判别函数所决定的决策面。对这个方法可以采用遗传算法，它提供当前样本下的最优解。,第二

18、种方法是用一个超平面将空间划分为两个半空间，它的正面仅包含一类“纯”的样本；它的反面则允许两类样本混杂。下一步则是对反面的混杂样本再次使用一个超平面分割，其正面分离出一类纯样本，而反面允许二类样本混杂。继续进行程序直至样本被超平面完全划分为止。划分的过程中要,求每次划分的正面得到的纯样本数最多。,应用统计方法解决模式识别问题时，维数或特征个数是个非常重要的问题。在低维空间里解析上或计算上行得通的方法，在高维空间里往往行不通。因此，降低维数有时就成为处理实际问题的关键。,2.6 Fisher线性判别函数,Fisher方法的基本思想是：把d维空间的所有模式投影到一条过原点的直线上，就能把维数压缩到

19、1。关键在于要找到这样一条最优的投影方向，使这些模式的投影能较好地区分开。,如图所示，表示了在一个二维空间两个类别样本在两个不同的向量w1与w2上投影分布的情况。其中用红点及蓝点分别表示不同类别的样本。显然对w1向量的投影能使这两类有明显可分开的区域，而对向量w2的投影，则使两类数据部分交迭在一起，无法找到一个能将它们截然分开的界面。Fisher准则的基本原理，就是要找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。,设给定两类模式样本集 和 ，它们各有 和 个d维样本。我们的目标就是找到这样一条直线，使得模式样本在这条直线上的投影最有利于分类。设 为这条直线

20、正方向的单位向量， 。于是由 和 对直线的投影相应地得到集合 和 。每个 就是 在单位向量 上的投影。于是有：为了找到最有利于分类的方向 ，需要建立一个准则函数，它能反映不同类别模式在这条直线上投影分离程度的好坏。,为了使类别分离得好，应使各类模式投影均值彼此间相距尽可能大，还应使同类模式的投影比较密集。 设 是第 类d维样本的均值： 则这些样本在直线 上的投影的均值就是： 从而投影均值间的距离就是： 因为 和 对于给定的两类样本集是不变的，所以改变的方向，就可能改变投影均值间的距离。 定义一类模式投影的类内离散度为： 则总的类内离散度为：它代表整个样本集合中各类样本投影的密集程度。为了更好的

21、分类结果，应选择直线 使得类内总离散度尽可能小。,综合上述考虑，定义Fisher准则函数。我们希望投影后，在一维Y空间里各类样本尽可能分得开些，即希望两类均值之差越大越好，同时希望各类样本内部尽量密集，即类内离散度越小越好。因此可以定义Fisher准则函数为：,构造Fisher判别函数 它使准则函数 达到极大。 为了把 表示成 的明显形式，作以下定义： （1）第 类离散度矩阵 （2）类内离散度矩阵 （3）类间离散度矩阵 可以得到,又 根据以上推导，准则函数 可改写为： 这就是Rayleigh比。易证Rayleigh比的如下性质： ，a是一个实数。 的极值与 的大小无关，只与 的方向有关。 用L

22、agrange乘数法求极值（略）。,经过计算可以得到 这就是使准则函数 极大的解。 就是使模式样本的投影在类间最分散，类内最集中的最优解。有了 后，得就可将各样本由d维空间投影到一维空间，即直线 上，变成一维样本 ，它们给出较好的分类结果。,需要注意的是，这样得到的结果是有一定局限的。它只是对准则函数最优，即 最大，在许多情况下，结果并不完全理想。另外，它没有利用样本分布的信息，虽然计算简单，但错误率达不到最小。,支持向量机(Support Vector Machine,简称SVM)是基于统计学习理论的一种分类器设计方法，是近年来在理论及实际问题中都有重大影响的一种新方法。 在线性可分条件下，

23、即两个类别训练样本集可用线性分界面无错误分开的条件下，找到使两类别训练样本正确分类的一个最佳分界面。最佳条件是指两类样本最靠近分界面的样本（称为支持向量）到该分界面的法向距离最大。也就是说使分界面两侧形成的一个隔离带（带中没有任一类训练样本）的间隔最宽。,2.7 支持向量机,SVM的思路是这样的，由于两类别训练样本线性可分，因此在两个类别的样本集之间存在一个隔离带。对一个二维空间的问题，如右图表示，其中用圈和交叉符号分别表示第一类和第二类训练样本，H是将两类分开的分界面，而H1与H2与H平行，H是其平分面，H1上的样本是第一类样本到H最近距离的点，H2的点则是第二类样本距H的最近点，由于这两种

24、样本点很特殊，处在隔离带的边缘上，因此用再附加一个圈表示。这些点称为支持向量，它们决定了这个隔离带。,从图上可以看出能把两类分开的分界面并不止H这一个，如果略改变H的方向，则根据H1、H2与H平行这一条件，H1、H2的方向也随之改变，这样一来，H1与H2之间的间隔(两条平行线的垂直距离)会发生改变。显然使H1与H2之间间隔最大的分界面H是最合理的选择，因此最大间隔准则就是支持向量机的最佳准则。,如图所示是两类线性可分集被超平面隔开的情况。显然，图 (b)比图(a)中两类样本分开的间隔要大，如果图(b)中的H0是具有最大间隔的解平面，则称这个解平面是最优的。,支持向量机是线性判别函数的进一步发展，但它也是基于当前有限模式样本集得到的最优化方法。与线性判别函数相似，它的结果强烈依赖我们所掌握的模式样本集的构造，当样本集容量不大时，这种依赖性尤其明显。此外，将分界面定在最大间隔的中间，对于许多情况来说，也并不是最优的。,本章习题： 1、设五维空间的线性方程为 ，试求出其权向量与样本向量点积的表达式 中的W，X以及增广权向量与增广样本向量形式ATY中的A与Y。,2、上式是一个五维空间的超平面，试求该平面到坐标原点的法向距离。,第1题答：,第2题答：该式的权向量的模为： 而超平面到坐标原点的距离为,