线性判别函数课件

第2章线性判别函数2.1线性判别函数和决策面2.2感知准则函数2.3最小平方误差准则函数2.4多类判别问题2.5分段线性判别函数2.6Fisher线性判别函数2.7支持向量机第2章线性判别函数2.1线性判别函数和决策面1课前思考题：

(1)机器能否像人类一样通过例证教育认知事物，修正观念中的错误的成分?

(2)机器学习过程中有教师吗？谁是教师？

(3)什么叫线性分类器?什么条件下才能用线性分类器？

课前思考题：2

2.1线性判别函数和决策面线性判别函数是统计模式识别方法中的一个重要的基本方法。它是由训练样本集提供的信息直接确定决策域的划分。在训练过程中使用的样本集，该样本集中的每个样本的类别已知。2.1线性判别函数和决策面线性判别函数是统计模式3由于决策域的分界面是用数学式子来描述的，如线性函数，或各种非线性函数等。因此确定分界面方程，这包括选择函数类型与确定最佳参数两个部分。一般说来选择函数类型是由设计者确定的，但其参数的确定则是通过一个学习过程来实现的，是一个迭代实现优化的过程。本章讲最简单的函数类型—线性函数。由于决策域的分界面是用数学式子来描述的，如线性函数，或各种非4假设抽取到的模式样本的边界是“整齐”而不是混杂的，而且以后遇到的待分类模式基本上不超过学习样本的分类范围，从而利用这些样本得出的分类边界是无误差的。因此这些模式类之间的分界面，可以利用线性判别函数来进行。对于n维空间中的c

个模式类别各给出一个由n个特征组成的单值函数，这叫做判别函数。在c类的情况下，我们共有c个判别函数，记为g1(x)，g2(x)，…gc(x)，它们分别对应于模式类

1，

2，…

c。假设抽取到的模式样本的边界是“整齐”而不是混杂的，而5

作为判别函数，它应具有如下的性质：假如一个模式X属于第i类，则有：而如果这个模式在第i类和第j类得分界面上，则有：如果判别函数取线性判别函数，它是所有模式特征的线性组合。对于第i类模式，有如下形式：

式中是特征的系数，称为权，为阈值权。

如果对第i类模式定义n维权向量为：

则判别函数可写成更简洁的形式：

作为判别函数，它应具有如下的性质：假如一个模式X属于第6讨论二类情况下的线性判别函数。两个线性判别函数如果X属于，可得：令则二类模式的线性分类器的决策法则是：如果，则决策，即把归到类去；如果，则决策，即把归到类去。线性分类器是指两类决策域的界面方程是单个线性方程。讨论二类情况下的线性判别函数。线性分类器是指两类决策域的界面7

是决策面方程，它是两类模式的分界，对于二维空间情况，它是一条直线；对于三维情况，它是一个平面；而对于高维空间的情况，则是一个超平面。

构造一个二类模式的线性分类器，如下图所示：是决策面方程8

在二类模式的情况下，决策面H把模式空间分成两个半空间，即对的决策域和对的决策域。因为当特征向量

在中时，所以决策面的法向量的方向指向。我们称位于决策面H的正面，位于决策面H的反面。

9为了说明向量W的意义，我们假设在决策平面上有两个特征向量X1与X2，则应有

(*)

其中(X1-X2)也是一个向量，(*)式表明向量W与该平面上任两点组成的向量(X1-X2)正交，因此W的方向就是决策面的法线方向。为了说明向量W的意义，我们假设在决策平面上有两个特征向量X110+=wwxxrp决策面H@右图中，H是决策面，它的方程为，是权向量，也就是决策面的法线方向。是待识别的模式的特征向量。g(X)就是n维空间中任一点X到该决策面距离的代数度量，该决策平面将这两类样本按其到该面距离的正负号确定其类别。若把X表示成：式中Xp:是在H上的投影向量，r:是到H的垂直距离，：是w方向上的单位向量。wwxx+=wwxxrp决策面H@右图中，H是决策面，它的方程为11结论：利用线性判别函数进行决策，就是用一个超平面把特征空间分割成两个决策区域，超平面方向由权向量W决定，它的位置由阈值权w0确定。将上式代入，可得：

()+=0xwxwgT(x)=+0wgwT+wwxrp)(+=0xpwwT+wWTwr=w(x)gr=0如果，则原点在H的正面；如果，则原点在H的反面。对于图所示情况，。若，则判别函数有齐次形式:说明超平面H通过原点。

（因为）若X为坐标系原点，则坐标原点到该决策面的距离为。

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

2.2感知准则函数感知准则函数是五十年代由Rosen14线性判别函数可改写为：于是线性判别函数就变成了(n+1)维空间的齐次线性函数。定义增广模式向量:定义广义权向量:对于二类模式问题，在这个(n+1)维空间的决策面H的方程就是：因为阈值为0，所以超平面H通过原点。这样，找寻决策面的问题就简化为求权向量的问题。线性判别函数15在线性可分条件下，广义权向量A合适的话应有：

为了方便起见，如果我们令则合适的A能使所有的Y’满足ATY’>0。（后面用Y表示Y’）经过这样的规格化处理后，问题就转化为：求使每一个样本Y满足ATY>0的权向量A的问题了。权向量A称为解权向量。线性可分是说该训练样本集中的两类样本可以用一个线性分界面正确无误的分开。在线性可分条件下，广义权向量A合适的话应有：

为了方便起见，16

这里是由于使用权向量A而被误分类的样本集合。当一个样本被误分类时，就有，所以，可见，是解权向量的函数。仅当时，达到极小值，即。或者说，当对于某个向量，准则函数达到极小值的话，就是解权向量，这时没有样本被错分类。在几何上，感知准则函数正比于被错分样本到决策面的距离之和。

为了求解线性不等式组ATY>0，构造一个准则函数：感知准则函数：因为（）为了求解线性不等式组ATY>0，构造一个准17有了准则函数，需要用最优化方法寻找达到极小值的解权向量A。可以采用梯度下降算法来求解。是一个正的比例因子，称为步长或增量。有了准则函数，需要用最优化方法寻找18梯度下降法的算法步骤：（1）先任意选择一个初始的权向量（2）把第K次的权向量加上被误分类的样本的和与某个常数的乘积，就得到第（K+1）次的权向量。（3）理论上可以证明，只要二类样本是线性可分的，无论初值如何选取，经过有限次迭代，这个算法总可以收敛，即使得每一个样本满足ATY>0。该算法的缺点是：每次迭代必须遍历全部样本，才能得到当前权向量下的误分样本集，从而进一步纠正的值。梯度下降法的算法步骤：该算法的缺点是：每次迭代必须遍历全部样19固定增量算法及其收敛性固定增量算法是解线性不等式组的一种最简单的方法。它可以由梯度下降法作如下两点改变得到：（1）把全部样本看作是一个序列，每当前一步迭代的权向量把某个样本错误分类时，就对这个权向量做一次修正，而不是等当前权向量对全部样本计算后再找出错分类样本集去进行修改。（2）考虑每次迭代时保持不变，这就是固定增量的情况，也就是说乘上一个固定的比例因子。固定增量算法及其收敛性固定增量算法是解线性不20二类情况下用固定增量法求解权向量的方法：设已知二类模式的样本集和，这些样本都已变成增广模式的形式，要求用固定增量算法决定一个超平面，使它能正确划分样本集。开始时，可以任意假定为域决策界面的那一边，也可以任意选择广义权向量的初始值。然后把训练集中的增广模式向量依次取出，计算的内积，权向量用如下规则调整：

①

如果，而，则用代替；

②

如果，而，则用代替；

③

如果，而，则保持不变；④

如果，而，则保持不变。二类情况下用固定增量法求解权向量的方法：21属于的全部模式向量都用上述方法处理一遍，成为一次迭代。这个算法继续重新执行，直到某次迭代后中的成员都通过这个程序而权向量不再变化为止，这时称为程序收敛。如果在某一次迭代中权向量已经保持不变，则权向量即解权向量。所以在程序收敛后即无必要进一步执行迭代了。如果不是线性可分的，则程序不会收敛，而迭代将无限进行下去，所以在编制程序时应考虑或在一定时间限度内停止，或当权向量在一个不收敛区域内循环而停止。

这个算法可以推广到下述更一般的情况：

①模式不一定是二值的；

②执行迭代时，增广模式向量集中成员的次序可任意选定；

③不要求中有相等数量的模式；

④初始权向量可以任意选择。属于的全部模式向量222.3最小平方误差准则函数

最小平方误差准则函数是一个基于全体样本的准则函数，要求满足等式，，其中是一些任意指定的正常数。令为一个矩阵，它的各行是向量，令为一个列向量，则问题变为：对于给定的和要求找到一个权向量，使得

多数情况下，只可能找到一个这样的解权向量，它使与之间的误差极小化。如果定义误差向量e为

则求为最优的方法是使误差向量e的长度的平方极小。这就是使误差平方和准则函数

极小化。这就是矛盾方程组的最小二乘解（MSE解）。2.3最小平方误差准则函数最小平方误差准则23对准则函数求导并令其为零，得准则函数极小化的必要条件：于是将解的问题转化为解。这里是一个维方阵，且常为非奇异。如果它是非奇异的，可以得到的唯一解：此处矩阵称为的伪逆。如果为奇异阵，得到的解不唯一。

MSE解依赖于向量b，b的不同选择可以给予解以不同的性质。当b任意给定时，MSE解在线性可分的情况下不会总是产生一个正确的分界面，但可以找到一个有用的判别函数。

d

n对准则函数求导并令其为零，得准则函数极小化的必要条件：dn24

为避免上述缺点，可以采用梯度下降算法。梯度下降算法为：（1）首先任意制订初始权向量；（2）如第k步不能满足要求则按下式求第（k+1）步的权向量可以证明，如果，其中是任意常数，则这个算法产生的权向量序列，收敛于满足方程式。且不管是否为奇异矩阵，这个下降算法总能产生一个解。MSE方法的计算工作量很大，要求解维矩阵的逆，并证明是非奇异的。为避免上述缺点，可以采用梯度下降算法。MSE252.4多类判别问题以上讨论的都是两类别问题，但是实际问题中常遇到的是多类别问题。可以把两类别问题中使用的线性判别函数方法推广到多类别问题中，但可有不同做法。2.4多类判别问题以上讨论的都是两类别问题，但是26一种最简单作法是将C类别问题化为(C-1)个两类问题，即将第i类与所有非i类样本，按两类问题确定其判别函数与决策面方程。因此对于C类，则总共有(C-1)个两类别问题，如图所示。这种做法存在两个问题，一是可能会出现一些不定区域，如图中阴影所示，在这些区域中的样本无法确定其类别。原因是用线性判别函数对i类及所有非i类进行划分并不能保证获得性能良好的划分，硬性使用线性分类器可能会产生很不好的效果。W1非W1不定区域一种最简单作法是将C类别问题化为(C-1)个两类问题，即将第27另一种相对麻烦些的做法是将C类中的每两类别单独设计其线性判别函数，因此总共有C(C-1)/2个线性判别函数。这种方法如图所示。这种方法由于每个判别函数针对每两类别样本设计，预期可有好效果，但仍有不定区域，在该区域内样本类别无法确定。

另一种相对麻烦些的做法是将C类中的每两类别单独设计其线性判别28由于样本在特征空间分布的复杂性，许多情况下采用线性判别函数不能取得满意的分类效果。也就是说，在n维模式样本集线性可分的情况下，如果训练集足够大，就可能得到较好的分类结果。所以它应用于简单的线性可分集是一个很好的工具。对于比较复杂的问题，当样本不是线性可分时，用超平面分类，就会导致较大的分类错误率。2.5分段线性判别函数由于样本在特征空间分布的复杂性，许多情况下采用线性判别函数不29线性判别函数ppt课件30

为了解决比较复杂的线性不可分样本分类问题，提出了非线性判别函数。这个分界面是一个超曲面。如图所示的分界面Ⅱ所示。但是非线性判别函数计算复杂，实际应用上受到较大的限制。解决问题的另一个方法是采用多个线性分界面，将它们分段连接，用分段线性划分去逼近分界的超曲面。如图分界面Ⅲ所示。他的决策面由几个超平面段组成。它有可能利用已知的线性判别函数来解决分类问题，并较好地逼近分类的超曲面，从而减少分类误差。

为了解决比较复杂的线性不可分样本分类问题，提31

分段线性判别函数的算法很多，它的计算量较之非线性判别函数大大减少。难点是如何舍弃这些超平面的无效部分而根据任务正确地将有效区段相互连接的问题。

下面的分段线性划分算法较易实现，它用全部正确分类的超平面将空间划分为若干区域，每个区域都是凸的超多面体。在这些超多面体中的样本都是属于同一类的。如果将每个超平面分割的正面半空间赋予“1”，反面赋予“0”，则这些超多面体可用所有的超平面的正反面的编码来代表。这就达到了用分段线性划分来分类的目的，见图。分段线性判别函数的算法很多，它的计算量较之非32

由于分段线性划分的解可能由不同的样本分割方式形成，一般情况下不是唯一的。但每个解都能满足要求。分段线性划分也存在误差。处理分类误差可有二种方法：（1）增加超平面数目，达到满足当前样本正确分类的目的；（2）适当限制超平面数目，而允许一定的分类误差存在。因为问题是非参数的，我们除了分类好的样本外一无所知，所以在有限样本的情况下，我们仅能讨论是当前样本下误差最小，这可以在多个可能解中用误分样本数最小或误差平方和最小作为准则来达到。一般说来，当样本足够大时，分段线性分界面是渐进于真实的超曲面分界的，因而这样的分界面是可行的。而在小样本的情况下，很难说一个算法得到的结果是最优的。由于分段线性划分的解可能由不同的样本分割方式33下面介绍两种二类线性判别函数推广得到的分段线性判别函数的算法。如图所示，先用二类线性判别函数找出一个分界面，它将样本大致分成两类。因为样本集不是线性可分的，所以两面的模式都会混杂。再对的正反面的模式样本分别应用线性判别函数求得和，如此继续下去，直至每个分界面都将样本正确分类为止。连接相应的各分界面，，即得分段线性判别函数所决定的决策面。对这个方法可以采用遗传算法，它提供当前样本下的最优解。下面介绍两种二类线性判别函数推广得到的分段线34第二种方法是用一个超平面将空间划分为两个半空间，它的正面仅包含一类“纯”的样本；它的反面则允许两类样本混杂。下一步则是对反面的混杂样本再次使用一个超平面分割，其正面分离出一类纯样本，而反面允许二类样本混杂。继续进行程序直至样本被超平面完全划分为止。划分的过程中要求每次划分的正面得到的纯样本数最多。第二种方法是用一个超平面将空间划分为两个半空间35

应用统计方法解决模式识别问题时，维数或特征个数是个非常重要的问题。在低维空间里解析上或计算上行得通的方法，在高维空间里往往行不通。因此，降低维数有时就成为处理实际问题的关键。2.6Fisher线性判别函数

Fisher方法的基本思想是：把d维空间的所有模式投影到一条过原点的直线上，就能把维数压缩到1。关键在于要找到这样一条最优的投影方向，使这些模式的投影能较好地区分开。

应用统计方法解决模式识别问题时，维数或特征个数是个非36如图所示，表示了在一个二维空间两个类别样本在两个不同的向量w1与w2上投影分布的情况。其中用红点及蓝点分别表示不同类别的样本。显然对w1向量的投影能使这两类有明显可分开的区域，而对向量w2的投影，则使两类数据部分交迭在一起，无法找到一个能将它们截然分开的界面。Fisher准则的基本原理，就是要找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。

如图所示，表示了在一个二维空间两个类别样本在两个不同的向量w37设给定两类模式样本集和，它们各有和个d维样本。我们的目标就是找到这样一条直线，使得模式样本在这条直线上的投影最有利于分类。设为这条直线正方向的单位向量，。于是由和对直线的投影相应地得到集合和。每个就是在单位向量上的投影。于是有：为了找到最有利于分类的方向，需要建立一个准则函数，它能反映不同类别模式在这条直线上投影分离程度的好坏。设给定两类模式样本集和，它们各有和38

为了使类别分离得好，应使各类模式投影均值彼此间相距尽可能大，还应使同类模式的投影比较密集。设是第类d维样本的均值：

则这些样本在直线上的投影的均值就是：

从而投影均值间的距离就是：

因为和对于给定的两类样本集是不变的，所以改变的方向，就可能改变投影均值间的距离。

定义一类模式投影的类内离散度为：则总的类内离散度为：它代表整个样本集合中各类样本投影的密集程度。为了更好的分类结果，应选择直线使得类内总离散度尽可能小。

为了使类别分离得好，应使各类模式投影均值彼此39综合上述考虑，定义Fisher准则函数。我们希望投影后，在一维Y空间里各类样本尽可能分得开些，即希望两类均值之差越大越好，同时希望各类样本内部尽量密集，即类内离散度越小越好。因此可以定义Fisher准则函数为：显然，应该寻找使的分子尽可能大，而分母尽可能小，也就是尽可能大的W作为投影方向。J(W)J(W)综合上述考虑，定义Fisher准则函数。我们希望投影后，在一40构造Fisher判别函数

它使准则函数达到极大。

为了把表示成的明显形式，作以下定义：（1）第类离散度矩阵

（2）类内离散度矩阵

（3）类间离散度矩阵

可以得到

构造Fisher判别函数41又

根据以上推导，准则函数可改写为：

这就是Rayleigh比。易证Rayleigh比的如下性质：

①，a是一个实数。②的极值与的大小无关，只与的方向有关。

用Lagrange乘数法求极值（略）。又42

经过计算可以得到

这就是使准则函数极大的解。就是使模式样本的投影在类间最分散，类内最集中的最优解。有了后，得就可将各样本由d维空间投影到一维空间，即直线上，变成一维样本，它们给出较好的分类结果。

需要注意的是，这样得到的结果是有一定局限的。它只是对准则函数最优，即最大，在许多情况下，结果并不完全理想。另外，它没有利用样本分布的信息，虽然计算简单，但错误率达不到最小。经过计算可以得到需要注意的是，这样得到的结果是有一定局限的43

支持向量机(SupportVectorMachine,简称SVM)是基于统计学习理论的一种分类器设计方法，是近年来在理论及实际问题中都有重大影响的一种新方法。在线性可分条件下，即两个类别训练样本集可用线性分界面