第2章 线性判别函数

第2章线性判别函数

2.1线性判别函数和决策面2.2感知准则函数2.3最小平方误差准则函数2.4

Fisher线性判别函数2.5多类情况下的线性判别函数2.6分段线性判别函数2.1线性判别函数和决策面线性判别函数是决策论模式识别方法中的一种重要的基本方法，是形式最简单的判别函数，由于它具有计算简单，在一定条件下能够实现最优分类的性质，因此在实际中得到了广泛的应用。此外，许多其它决策论识别方法也可用判别函数来研究（非线性判别函数），它也是研究神经网络的基础。现在我们就从线性判别函数开始介绍统计模式识别的各种方法。返回本章首页在统计模式识别方法中，首先应把能代表模式的那些特征抽取出来，构成一个代表这个模式的特征向量，表示为当我们观察待分类模式时，每次观察到的样本都是不同的，他们可以看成是随机产生的。所以每次抽取到的模式特征都应看成是随机变量，从而代表这些模式的n维向量也应是随机向量。下面看一个三类模式例子，如图所示。三类模式可用边界线AD、BD和CD分开。返回本章首页返回本章首页所以，如果根据以往大量的观察，知道模式类别的分布，从而能找出n维空间中模式类之间的分界，就能解决模式的分类问题。这在实际上是一个通过给定样本的学习过程。简便起见，在本章中我们假定抽取到的模式样本的边界是“整齐”而不混杂的，而且以后遇到的待分类模式基本上不超过学习样本的分布范围，从而利用这些样本得出的分类边界是无误差的。为找出这些模式之间的分界面，可以利用判别函数来进行。对于n维空间中的c个模式类别各给出一个由n

个特征组成的单值函数，这叫做判别函数。在c

类的情况下，我们共有c个判别函数，记为返回本章首页判别函数的性质假如一个模式X

属于第i

类，则有而如果这个模式在第i

类和第j

类的分界面上，则有事实上，这是由n

维模式降为1维或1个数的一种变换。线性判别函数是所有模式特征的线性组合，表示为返回本章首页二类情况下的线性判别函数令用其可以构造一个二类模式的线性分类器，如图所示。返回本章首页可将其任意分类，或拒绝返回本章首页二类情况下，决策面与模式向量的几何关系是决策面方程，它是两类模式的分界，对于二维空间的情况，它是一条直线。下面，对一些关系作几何解释，如图所示。返回本章首页返回本章首页2.2

感知准则函数2.2.1几个基本概念2.2.2感知准则函数及其梯度下降算法返回本章首页1线性可分性讨论如下的两个问题①对于4个二维样本，其在平面上的分布如图所示。若把每个样本任意分到两种类别之一或，举出其中的两种线性不可分情况。②验证

N

个d维样本线性可分的概率阀值是返回本章首页2.2.1几个节本概念2样本的规范化二类模式的线性分类器的决策规则为引入增广模式向量和广义权向量返回本章首页可将其任意分类，或拒绝代入，决策规则可变为取可得叫做规范化增广样本向量，为方便起见仍用表示3解向量和解区返回本章首页返回本章首页返回本章首页返回本章首页对解区的限制对解区加以限制的目的在于使解向量更可靠。因为越靠近解区中间的解向量越能对新的样本正确分类。同时也可避免求解向量的算法不致收敛到解区边界的某点上。为了解线性不等式（

已规范化

）需要构造一个准则函数。这里我们介绍一种常用的准则函数即所谓的感知准则函数，定义为如下的形式：

是由于使用权向量而被误分类的样本集合。返回本章首页2.2.2感知准则函数及其梯度下降算法也就是说，当对于某个向量，准则函数达到极小值的话，就是解权向量，这时没有样本被错分类。现在用最优化方法——梯度下降算法寻找使达到极小值的解权向量。梯度下降算法基本思想函数在某点的梯度是一个向量，它的方向与过点的等量面的法线方向重合，指向增加的一方，是准则函数变化率最大的方向。反之，负梯度的方向则是函数减少得最快的方向。所以在求准则函数的极小值时，沿负梯度方向搜索有可能最快地找到极小值。返回本章首页梯度下降算法的实现先任意选择一个初始的权向量，计算上的梯度，从出发在最陡方向（负梯度）上移动一个距离以得到下一个权向量值，用迭代公式表示为请简述梯度下降算法？

返回本章首页梯度下降算法应用举例——单样本修正法参考教材P94，把样本看作一个不断重复出现的序列而逐个加以考虑，样本组成的样本序列为：返回本章首页返回本章首页返回本章首页2.3最小平方误差准则函数

2.2.1平方误差准则函数及其伪逆解2.2.2MSE准则函数的梯度下降算法返回本章首页前面我们介绍的感知器准则函数是在误分类样本的基础上建立的，它要求对于所有样本都能满足不等式本节介绍的最小平方误差准则函数，它是一个基于全体样本的准则函数，要求满足等式这样就可以将原来解一组线性不等式的问题转化为解一组线性方程组的问题。返回本章首页2.3.1平方误差准则函数及其伪逆解引入其中是规范化增广样本向量将写成联立方程组得形式①若是非奇异方阵，则可以得到解；②若是长方阵（一般为列满秩），则是矛盾方程组，没有精确解。定义误差向量返回本章首页引入其中是规范化增广样本向量将写成联立方程组得形式①若是非奇异方阵，则可以得到解；②若是长方阵（一般为列满秩），则是矛盾方程组，没有精确解存在。返回本章首页定义误差向量定义平方和准则函数为使广义权向量为最优，只需使平方和准则函数极小化，然后把相应的作为问题的解，称其为矛盾方程组的最小二乘解（MSE解）。

返回本章首页

返回本章首页这里是一个维方阵，且常为非奇异；方阵称为的伪逆（矩阵论里称其为广义逆），且具有以下性质：①当为非奇异方阵时，的伪逆和它的逆相等②③一般来说返回本章首页从上述推倒过程可以看出，MSE解依赖于向量，的不同选择可以给予解以不同的性质（参考教材P102）。返回本章首页从前面的推导过程我们可以看到，用MSE方法按式的计算工作量很大，首先要求证明是非奇异的，然后计算，为维矩阵的逆。这样，我们引入梯度下降算法以避免这种问题。误差平方和准则函数的梯度返回本章首页2.3.2MSE准则函数的梯度下降算法梯度下降算法为：（1）首先任意指定初始权向量；（2）如第

k步不能满足要求

则按下式求第(k+1)步的权向量对于任意的正常数，算法得到的权向量序列收敛于使返回本章首页2.4Fisher线性判别函数在以后的统计模式识别方法中，维数或特征数是一个很大的问题，因此，降低维数有时就成为处理实际问题的关键。Fisher线性判别函数法就是其中一种，是R.A.Fisher（1936）在他的一篇论文中提出来的，其基本思想是把d

维模式投影到一条通过原点的直线上，把维数压缩到1。参照如图所示的例子，进行分析。返回本章首页返回本章首页基于这个例子可以看到，投影线的方向起着至关重要的作用。下面着重讨论如何从数学上寻求最优的投影线方向。首先讨论从d

维空间到1维空间的数学变换，从几何上看，就是相对应的到方向为的直线上的投影。寻找最好的投影方向即是寻找最好的变换向量的问题。返回本章首页为了使类别分离的好，应使各类模式投影均值彼此间相距尽可能大。第i类d

维样本的均值样本在直线上的投影的均值是投影的均值间的距离是返回本章首页为了使类别分离得好，还应使同类模式的投影比较密集。用类内离散度来度量。定义为总的类内离散度为：它代表整个样本集合中各类样本投影的密集程度返回本章首页这里建立一个准则函数，它能反映不同类别模式在直线上投影分离程度的好坏。综合上述考虑，希望两类模式投影均值之差越大越好；同时希望同类模式的投影内部尽量密集。定义Fisher准则函数寻找使分子尽可能大，而分母尽可能小，也就是使尽可能大的作为投影方向。返回本章首页将变为的显函数返回本章首页返回本章首页称为Rayleigh比,其具有以下性质：①，a是一个实数；②的极值与的大小无关，只与的方向有关。下面求准则函数的极大值。将标量对向量求导并令其为零向量，注意到的分子分母均为标量，利用二次型关于向量求导的公式可得：返回本章首页上式表明：是矩阵相应于特征值

的特征向量（本特值）。返回本章首页由于我们的目的是寻求最好的投影方向，的比例因子对此并无影响，因此，可得返回本章首页MSE最小平方误差方法与Fisher线性判别的关系在此，我们将通过适当选择b来说明MSE判别函数是和Fisher线性判别有直接联系的。我们假设一组d维样本集，其中个属于类的样本记为子集，其中个属于类的样本记为子集。进一步，得到增广模式向量，并进行规范化。不失一般性，可以假设前个样本属于类，后个样本属于。这样矩阵就可以写成分块矩阵返回本章首页是个1的列向量，是一个矩阵，它的行是属于。接下来，我们将证明MSE解和Fisher线性判别关系。返回本章首页返回本章首页返回本章首页返回本章首页对于任意的，向量都是在的方向上，则就有代入2.5多类情况下的线性判别函数前面我们重点讨论了二类模式情况下的线性判别方法，不难把它们推广到多类别的情况。可以把多类问题化为二类问题来解决，也可以直接按多类问题来解。1、按二类问题解①是把c类问题转化为个二类模式的分类问题。其中第i个问题就是用线性判别函数把属于类的模式同不属于的模式分开。②是用次二类模式线性判别，每次只从样本集中判别指定的二类的决策面。两种方法都会产生模糊区域，结合下图进行分析。返回本章首页返回本章首页返回本章首页2按多类问题解（结合第一节内容）如果不用区别二类问题的线性判别函数，可采用一般的c类线性判别函数：如果对于所有的，有则把模式归到

类去而如果这个模式在第i

类和第j

类的分界面上，则有返回本章首页返回本章首页返回本章首页线性机器的决策区域的特点（1）所有决策区域是凸的；（2）每个决策区域都是单连通的；（3）不存在拒绝分类的死区；返回本章首页2.6分段线性判别函数以上我们介绍了线性判别函数，它的一个显著的优点是：算法简单和具有“学习”的能力，就是说，给定分好类的样本集后，能够根据样本“学习”，自动找到线性分界面。它的另一个优点是：如果给定的分好类的n维模式样本集是线性可分的，则基于感知准则函数的算法一定收敛。不足是：必须线性可分，得到的分界面是一个超平面，应用有限，对于比较复杂的问题，如果样本不是线性可分时，就会导致较大的分类错误率。返回本章首页返回本章首页为了解决比较复杂的线性不可分样本分类问题，提出了非线性判别函数，如图的分界面Ⅱ所示，为超曲面，非线性判别函数计算复杂，实际应用上受到较大的限制。解决问题比较简便的方法是采用多个线性分界面，将它们分段连接，用分段线性判别划分去逼近分界的超曲面，如图Ⅲ。其优点是：由于它的各段都是超平面，有可能利用已知的线性判别函数来解决分类问题；