模式识别-线性判别函数

模式识别

PatternClassification

第六章:线性判别函数线性判别函数原理利用判别函数将特征空间划分为若干个决策区域，然后根据待识别样本位于的决策区域来进行判类是模式识别的重要方法之一3AppliedPatternRecognitionCSE616线性判别函数判别函数的概念判别函数即是直接用来进行模式分类的准则函数例如在Bayes决策方法中，对c类模式有：这里的即可视为模式分类的准则函数判别函数4AppliedPatternRecognitionCSE616线性判别函数在特征空间中，判别函数还具有特殊的几何意义和性质5AppliedPatternRecognitionCSE616线性判别函数对图（a）所示的两类模式，可以用一条直线（界面）将其分开，设直线方程为：

则可令判别函数

则对类模式有对类模式有6AppliedPatternRecognitionCSE616线性判别函数可用判别函数进行模式分类，即当待识样本X到来时若，则判X属于类若，则判X属于类7AppliedPatternRecognitionCSE616线性判别函数对图（b）所示的两类模式，用直线已不能将两类模式分开，分界线为二次曲线，判别函数为此时分界面仍具有如下性质：若，则判X属于类若，则判X属于类8AppliedPatternRecognitionCSE616线性判别函数判界面由所决定的界面称为判别面，对判别面上（决策面）任一点均有判别面正面、反面的区域称为判别面的正面，的区域称为判别界的反面9AppliedPatternRecognitionCSE616线性判别函数问题判别函数的形式（线性、非线性）？根据先验知识决定判别函数中的系数？由已知类别的学习样本确定多类问题？化解为多个二类问题10AppliedPatternRecognitionCSE616线性判别函数及其几何性质

定义

d维特征空间中，若判别函数具有如下形式：其中：权向量阀值11AppliedPatternRecognitionCSE616线性判别函数及其几何性质则称满足上述定义的函数为线性判别函数由线性判别函数决定的判别面（决策面）方程为：12AppliedPatternRecognitionCSE616线性判别函数及其几何性质若令则线性判别函数可写为，此时决策面为过原点的超平面

13AppliedPatternRecognitionCSE616线性判别函数及其几何性质线性可分d维空间中的模式类如果能用线性判别函数将其分开，则称模式类为线性可分的线性可分线性不可分14AppliedPatternRecognitionCSE616线性判别函数及其几何性质线性判别函数的几何性质15AppliedPatternRecognitionCSE616线性判别函数及其几何性质下面以二维二类情况为例，分析线性判别函数的几何性质设、为判别面上的任意两点，则有即：

g(X)=0WX1X216AppliedPatternRecognitionCSE616线性判别函数及其几何性质性质一：权向量w与判别面上任一向量正交，即w决定了判别界的方向17AppliedPatternRecognitionCSE616线性判别函数及其几何性质设x为特征空间中的任一向量，则有：其中：18AppliedPatternRecognitionCSE616线性判别函数及其几何性质将其代入中有：

由于为判别界上的点,故19AppliedPatternRecognitionCSE616线性判别函数及其几何性质因此有：性质二：是以为单位的X到判决面的距离。若Ｘ在判别面的正面，则g(x)>0,若Ｘ在判别面的反面，则g(x)<0，判别界上g(x)=0。20AppliedPatternRecognitionCSE616线性判别函数及其几何性质对于原点x=0，则性质三：线性判别函数中的阀值W0表征了原点到判别界的距离。若W0>0，则原点位于判别界的正面；反之原点位于判别界反面。21AppliedPatternRecognitionCSE616多类情况下的线性判别函数问题：多类情况下，如何用线性判别函数进行分类？解决方案：化为多个二类问题来解决！分三种情况来讨论22AppliedPatternRecognitionCSE616多类情况下的线性判别函数情况一每个模式类均可用一个单独的线性判别界与其余模式类分开

23AppliedPatternRecognitionCSE616多类情况下的线性判别函数共需c个判别函数，且具有如下性质：

24AppliedPatternRecognitionCSE616多类情况下的线性判别函数当待识样本到来时，若，且对所有的j，，则判该方法实质上是在特征空间中划分出c个区域，并根据待识样本落入的区域来决定属于哪一类模式。但该方法存在失效区或不定区，如图中阴影部分，即存在多于一个的判别函数大于０，或所有的判别函数都小于０。25AppliedPatternRecognitionCSE616多类情况下的线性判别函数情况二线性判别界只能将模式类两两分开26AppliedPatternRecognitionCSE616多类情况下的线性判别函数则需个判别函数具有如下性质：

显然，应有：27AppliedPatternRecognitionCSE616多类情况下的线性判别函数识别过程为：当待识样本Ｘ到来时，若对所有的j均有则判该方法仍然存在不定区，对不定区待识样本，采用拒识策略28AppliedPatternRecognitionCSE616多类情况下的线性判别函数情况三不考虑二类问题的线性判别函数，采用Ｃ个线性判别函数将Ｃ个模式分开。判别函数为：识别准则为：对所有的，若则判29AppliedPatternRecognitionCSE616多类情况下的线性判别函数该方法实际上是将特征空间划分为R1,……，Rc

共C个判别区域，当模式在Ri中时,具有最大的函数值如果Ri与Rj相邻，则决策面是方程的一部分该方法不存在不定区30AppliedPatternRecognitionCSE616多类情况下的线性判别函数R1R2R3R4g1(X)g4(X)g3(X)g2(X)31AppliedPatternRecognitionCSE616小结由上述分析可得，应用线性判别函数的方法实际上是如何应用学习样本来确定线性判别函数参数的方法由于多类问题可化为多个二类问题来处理，故以下介绍二类问题的线性判别函数学习算法32AppliedPatternRecognitionCSE616线性判别函数的学习算法线性判别函数一般具有如下一般形式：现将其扩展到增广特征空间，即：33AppliedPatternRecognitionCSE616线性判别函数的学习算法则线性判别函数可写为：判别面为过原点的超平面根据判别函数的性质，对于二类问题有：若，则类若，则类34AppliedPatternRecognitionCSE616线性判别函数的学习算法现对类样本进行归一化处理，即令所有类样本则二类分类问题变为：由Ｎ个学习样本，找到权向量Ａ，使得对所有的学习样本有：35AppliedPatternRecognitionCSE616线性判别函数的学习算法满足上述条件的向量A称为解向量可见每个学习样本都对解向量进行了限制，解向量并不唯一。显然，若存在解向量A使得二类样本分类正确，则样本是线性可分的36AppliedPatternRecognitionCSE616线性判别函数的学习算法解向量并不唯一：解区域

37AppliedPatternRecognitionCSE616感知准则梯降法欲求解向量Ａ，即是根据学习样本求解不等式组直接求解不等式是困难的！38AppliedPatternRecognitionCSE616感知准则梯降法可将求Ａ的问题转化为标量准则函数求极值的问题，即定义一个标量函数J(A)，它具有如下的性质：J(A)的值越小，判别面的分割质量越高39AppliedPatternRecognitionCSE616感知准则梯降法求标题函数对矢量的极值问题，可用优化方法中的梯度下降法来解决标量函数J(A)关于矢量Ａ的的梯度是一个向量，即：40AppliedPatternRecognitionCSE616感知准则梯降法的方向是J(A)在向量Ａ处增加最快的方向反之，负梯度是J(A)在向量Ａ处减小得最快的方向的值的大小表示J(A)在Ａ处变化率的大小梯度等于０的点即是函数J(A)的极值点41AppliedPatternRecognitionCSE616感知准则梯降法标量函数关于向量的梯度

42AppliedPatternRecognitionCSE616感知准则梯降法梯降法求解向量的一般思路：定义一个标量准则函数J(A,Y)，该函数不仅与解向量A有关，还与学习样本Y有关当准则函数达到极值时，判别界的质量最高通过迭代的方法找到函数J(A,Y)的极值点，即找到使得

J(A,Y)＝０的最佳解向量A43AppliedPatternRecognitionCSE616感知准则梯降法如何用迭代方法求J(A,Y)极值点？如何定义标量函数？44AppliedPatternRecognitionCSE616感知准则梯降法迭代方法求J(A,Y)极值点k=1，任意选取初始解向量计算准则函数在Ak处的梯度

向负梯度方向跨一步，令若，则显然，停止。否则，令k=k+1，重复第二步，直到结束。45AppliedPatternRecognitionCSE616感知准则梯降法感知准则函数定义为：其含义是选择了解向量Ａ后，被错分类的样本到判别面的距离之和可见满足，其存在极小值０，此时无错分类样本

达到极小值时的解向量Ａ即是欲求的解向量！46AppliedPatternRecognitionCSE616感知准则梯降法如何求感知准则函数的梯度？即感知准则函数的梯度为选取解向量Ａ后，所有被错分类的样本之和的负值47AppliedPatternRecognitionCSE616感知准则梯降法则迭代公式为：48AppliedPatternRecognitionCSE616感知准则梯降法迭代方法求感知准则函数极值点k=1，任意选取初始解向量遍历所有样本，计算找出选择后被错分类的样本（即的样本）令：若，则停止。否则，令k=k+1，重复第三步，直到结束49AppliedPatternRecognitionCSE616固定增量算法感知准则算法需一次获取所有学习样本，并在迭代算法中一次遍历所有样本在实际应用中，有时样本是分批获取固定增量算法即是针对上述情况的改进感知准则算法基本思想是：每次修改解向量时，不需遍历所有的样本，而是将学习样本序贯输入，每考察一个样本就对修改一次。50AppliedPatternRecognitionCSE616固定增量算法固定增量迭代算法任意选取初始解向量顺序取出学习样本，计算若，则不变若，则遍历所有样本，即，完成一次迭代令k=k+1，重复上述迭代，直至51AppliedPatternRecognitionCSE616固定增量算法存在的问题初始解向量的选择问题？步长的选取问题？收敛性问题？（感知收敛定理）结论：只要二类样本是线性可分的，则固定增量算法一定收敛52AppliedPatternRecognitionCSE616最小平方误差算法原理将求线性判别函数的不等式问题转化为求解等式的问题，即令：其中为任意指定的正常数53AppliedPatternRecognitionCSE616最小平方误差算法方法定义矩阵，其第i行是学习样本Ｙi的各元素，即：54AppliedPatternRecognitionCSE616最小平方误差算法令：

n为学习样本总数

则等价于55AppliedPatternRecognitionCSE616最小平方误差算法假如是非奇异矩阵，则可直接计算解向量但通常情况下，的行数常大于列数，即是方程式数目大于未知数数目的矛盾方程，一般无精确解56AppliedPatternRecognitionCSE616最小平方误差算法此时可考虑寻找解向量Ａ，它使与b之间的误差极小化定义误差向量将平方误差定义为准则函数

即平方误差函数

57AppliedPatternRecognitionCSE616最小平方误差算法具有极小值０，此时Ａ即为的解如何求平方误差函数的极值?求平方误差函数极值方法伪逆法梯降法58AppliedPatternRecognitionCSE616最小平方误差算法伪逆法则梯度令即59AppliedPatternRecognitionCSE616最小平方误差算法伪逆法可得解得最佳解向量为：称为的伪逆矩阵60AppliedPatternRecognitionCSE616最小平方误差算法伪逆法特点：①伪逆法要求为非奇异矩阵，其逆才存在②计算较为复杂61AppliedPatternRecognitionCSE616最小平方误差算法梯降法由于则梯降法的迭代公式为：算法过程与感知准则梯降法相同62AppliedPatternRecognitionCSE616Ｆisher线性函数基本思想：在d维特征空间中，将所有样本投影到一条过原点的直线上，将维数压缩到１维目标：找到一个最优的投影方向，使投影后的样本最易于分类63AppliedPatternRecognitionCSE616Ｆisher线性函数WW64AppliedPatternRecognitionCSE616Ｆisher线性函数设给定两类学习样本集和，共n个学习样本，其中类样本个，类样本个现将任意学习样本与权向量作内积：则即是在方向上投影后的样本65AppliedPatternRecognitionCSE616Ｆisher