模式识别第五章几何分类器

第五章 几何分类器5.1 几何分类器的基本概念Bayes决策需要知道统计规律。一个模式通过某种变换影射为一个特征向量后，该特征向量可以理解为特征空间的一个点，在特征空间中属于一个类的点集，在某种程度上总是与属于另一个类的点集相分离，各个类之间是确定可分的，因此如果能够找到一个分离函数（线性或非线性函数），把不同类的点集分开，则分类任务就解决了。几何分类器是通过几何的方法，把特征空间分解为对应于不同类别的子空间，而且呈线性的分离函数将使计算简化。假定样品X有两个特征，即，每一个样品都对应二维空间中的一个点。共分三类：，那么待测X属于哪一类？对这个问题就要看它最接近哪一类，若最接近于则为类，若最接近于则为类，否则为类。在各类之间要有一个边界，若能知道各类之间的边界，那么就知道待测样品属于哪一类了。所以，要进一步知道如何去找这个分界线。找分界线的方法就是几何分类法，几何分类法的结果能提供一个确定的分界线方程，这个分界线方程叫做判别函数，因此判别函数描述了各类之间的分界线是什么形式。几何分类法按照分界函数的形式可以分为线性判别函数和非线性判别函数两大类。线性分类器由于涉及的数学方法简单，在计算机上容易实现，故在模式识别中被广泛应用。但是这并不意味着在模式识别中只有线性分类器就足够了。在模式识别的许多问题中，由于线性分类器固有的局限性，它并不能提供理想的识别效果，必须求助于非线性分类器。而且有些较为简单的线性分类器对某些模式识别问题的解决，既简单，效果又好。5.2 线性判别函数判别函数分为线性判别函数和非线性判别函数。最简单的判别函数是线性判别函数，它是由所有特征量的线性组合构成的。. 两类情况两类别分类器框图如图5-1所示，根据计算结果的符号将分类。d两类情况分类器+1w1-1w2决策阈值单元判别计算x1x2xm） 两个特征每类模式有两个特征，样品是二维的，在二维模式空间中存在一线性判别函数 (5-1)式中是参数或者称为权值，为坐标变量，即模式的特征值。可以很明显地看到属于类的任一模式代入d(X)后为正值，而属于类的任一模式代入d(X)后为负值，如图5-2所示。w2 - + w1 d(X)= w1x1+ w2x2+ w3=0 x2 x1 图5-2 两类模式的线性判别盘函数因此，d(X)可以用来判断某一模式所属的类别，在这里把d(X)称为判别函数。给定某一未知类别的模式，若d(X)0，则属于类；若d(X)0，而其他的均小于0，则该未知的手写数字是7。例5-1 设有一个二维三类问题，判别函数已求得：有一模式x=(6,5)，试判别其类别。解：将该模式特征矢量代入上面三式，有根据上面三式，最后判d1(X)=0d2(X)=0d3(X)=0+-w2w1w3图5-4 多类情况（1） 第二种情况每两个类别之间可用判别平面分开，有m(m-1)/2个判别函数，判别函数形式为 (5-7)若对于，有，则X属于类。没有一个类别可以用一个判别平面与其他类分开，如图5-5所示，每一个边界只能分割两类。对于一未知的手写数字，若d71, d72, d73, d74, d75, d76, d78, d79, d70均大于零，则可知该手写数字为7。例5-2设有一个二维三类问题，三个判别函数为有一模式x=(4,3)，试判别其类别。解：将该模式特征矢量代入上面三式，有上面三式等效为由于所以判d23(X)=0d13(X)=0+-w3w2w1图5-5 多类情况（2）d12(X)=0） 第三种情况存在m个类别函数，判别函数形式为 (5-8)把X代入m个类别函数中，判别函数最大的那个类就是X所属类别。与第一种情况的区别在于此种情况下可以有多个判别函数的值大于0，第一种情况下只有一个判别函数的值大于0。对任一未知的手写数字，代入判别函数后若为d7(X)最大值，则该未知的手写数字是7。例5-3设有一个二维三类模式分类器，其判别函数为有一模式x=(1,1)，试判别其类别。解：将该模式特征矢量代入上面三式，有由于，故判d1(X)-d2(X)=0d2(X)- d3(X)=0w2w1w3图5-6 多类情况（3）d1(X)- d3(X)=0若可用以上几种情况中的任一种线性判别函数来进行分类，则这些模式类称为线性可分的。总结如表5-1所示。模式分类方案取决于两个因素：判别函数d(X)的形式和系数W的确定。前者与所研究模式类的集合形式直接有关。一旦前者确定后，需要确定的就是后者，它们可通过模式的样品来确定。5.3 线性判别函数的实现前面介绍了判别函数的形式，对于判别函数来说，应该确定两个内容，一个是方程的形式，另一个是方程的系数。对于线性判别函数来说，方程的形式固定为线性，维数固定为特征向量的维数，方程组的数量取决于待识别对象的类数。既然方程组的数量、维数和形式已定，则对判别函数的设计就是确定函数的各系数，即线性方程的各个权值。下面将讨论如何确定线性判别函数的系数。首先按需要确定一准则函数J，如Fisher准则、感知器算法、增量校正算法、LMSE算法。确定准则函数J达到极值时及的具体数值，从而确定判别函数，完成分类器设计。线性分类器设计任务是在给定样品集条件下，确定线性判别函数的各项系数，对待测样品进行分类时，能满足相应的准则函数J为最优的要求。这种方法的具体过程可大致分为以下几个步骤。表5-1 线性分类器判别函数形式类别情况判别平面判别函数形式两类情况（见图5-1）样品是二维的，判别边界为一直线若d(X)0，则属于；若d(X)0 (5-10)其中W为权矢量X为各样品特征值的增1矩阵，即训练过程就是对判断好的样品集求解权矢量W，即根据已知类别的样品求出权系数，形成判别界线（面），再对未知类别的样品求出其类别。这是一个线性联立不等式的求解问题，只对线性可分问题方程（5-10）才有解。对这样的问题来说，如果有解，其解也不一定是单值的，因而就有一个按不同条件取得最优解的问题，因此出现了多种不同的算法，这里介绍梯度法。2梯度下降法因为求某一函数f(W)的数值解，通常只能求出在某种意义下的最优解，即先定义一个准则函数，然后在此函数最大或最小的情况下，求出f(W)的解。梯度法就是先确定一准则函数J(W)，然后选一初值W(1)，这样可用迭代式W(k+1)=W(k)-CJ(W(k) (5-11)找到W的数值解。设有一组样品X1,X2,XN，其中Xi是规范化增广样品向量，目的是找一个解向量W*，使得WTXi0, i=1,2,N (5-12)显然，对于线性可分情况，问题才有解。为此这里首先考虑处理线性可分问题的算法。可将准则函数J的形式选为J(W,X)=k(WTX-WTX) (5-13)1）当X被错分类时，就有WTX0，有J(W,X)= Jmin(W,X)=0，如图5-7所示，在坐标原点右侧J(W,X)=0，W获得一确定解的区域。矢量的方向主要是由其取值最大的分量决定的，故负梯度向量J(W)，指出了W的最陡下降方向。当梯度向量为0时，达到了函数的极值。对联立不等式（5-10）求解W的问题，可转化为求函数极小值的问题。若准则函数J的梯度收敛为0，则表明达到J的极值，从而就是方程（5-10）的最优解。3“奖惩”算法将感知器算法具体化，就是“奖惩”算法。（1）两类情况若且，或且，则无须修正，即W(k+1)=W(k)。反之，则须修正，即 若且，则W(k+1)=W(k)+CX(k)； 若且,则W(k+1)=W(k)+CX(k)。JW(k+1)JW(k)W(k)W(k+1)W0J(W,X)图5-7 X为常量时的准则函数（2）多类情况对于多类问题，可以采用判别函数最大值方法来训练，即对于m个类，应该有m个判别函数。设有m类样品，并且在k次迭代时出现的样品，如果采用感知器算法，则m个判别函数都应该加以计算。对于，则权矢量不必加以修正，即 (5-19)对于，则按下式修正权矢量： (5-20)4实例说明用感知器算法对三类模式求判别函数，每类仅含一个样品，即解：样品的增广形式为(0,0,1)T, (1,1,1)T,(-1,1,1)T取参数C=1，初始值W1(1)= W2(1)= W3(1)= (0,0,0)T。步骤如下：（1）输入样品X（1），则 因，而dX(1)均为0，d1X(1)不是最大值，故需根据式（5-20）来修改权矢量（2）输入样品X（2），则因，d2X(2)不是最大值，故需修改权矢量（3）输入样品X（3），则因，d3X(3)不是最大值，故需修改权矢量至此已完成一次迭代，但未得到对三类模式均为正确的权矢量，故令X(4)=X(1), X(5)=X(2), X(6)=X(3),再次进行迭代。（4）输入样品X（4），得到因，而d1X(4)不是最大值，应修正权矢量（5）输入样品X（5），得到因，而d2X(5)是最大值，这一判别结果是正确的，因而权矢量不须修正（6）输入样品X（6），得到因，而d3X(6)是最大值，这一判别结果是正确的，因而权矢量不须修正（7）输入样品X（7）=(0,0,1)T，得到因，而d1X(7)是最大值，这一判别结果是正确的。至此为止，所有样品都通过了检验，因而权矢量为于是三个判别函数为d1(X)=-2x2 d2(X)=-2x1-2d3(X)=-2x1-25.实现步骤1）设各个权矢量的初始值伪，即W0= W1= = Wm=0。2）第k次输入一个样品X(k)，计算第k次迭代计算的结果为3）若，判断diX(k)是不是最大值，若是，则各个权值不须修正，否则，各权值须修正4）循环执行第2）、3）步，直到输入所有的样品，权值都不需要修正为止。注意：对于几何分类器样品数不需要过多。13