模式识别第五章几何分类器
第五章 几何分类器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，则属于类；若d(X)=0，则此时落在分界线上，即的类别处于不确定状态。这一概念不仅适用于两类别情况，还可推广到有限维欧式空间中的非线性边界的更一般情况。） 三个特征每类模式有三个特征，样品是三维的，判别边界为一平面。） 三个以上特征每类模式有三个以上特征，判别边界为一超平面。对于n维空间，用矢量来表示模式，一般的线性判别函数形式为： (5-2)式中称为权矢量或参数矢量。如果在所有模式矢量的最末元素后再附加元素，则式(5-2)可以写成 (5-3)的形式。式中和分别称为增1模式矢量和权矢量。式（5-3）仅仅是为了方便而提出来的，模式类的基本几何性质并没有改变。在两类别情况下，判别函数d(X)有下述性质，即 （5-4）满足的点为两类的判别边界。d1dmMAXxn决策d2x2x1最大值选择器图5-3 判别函数构成的多类分类器形式. 多类情况对于多类别问题，假设有m类模式。对于n维空间中的m个类别，就要给出m个判别函数：d1(X), d2(X), dm(X),分类器基本形式如图5-3所示，若X属于第i类，则有 (5-5)） 第一种情况每一个类别可用单个判别平面分割，因此m类有m个判别函数，具有下面的性质 (5-6)如图5-4所示，有3个模式类，每一类别可用单个判别边界与其余的类别划分开。例如手写数字共有10个类，m=10。对任一未知的手写数字，代入判别函数后若只有d7(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，则属于；若d(X)=0，落在分界线上，类别不确定。样品是三维的，判别边界为一平面同上有三个以上特征，判别边界为一超平面为两类的判别边界多类情况（见图5-3）每一个类别可用单个判别平面分割，m类有m个判别函数。i=1,2,m存在不满足条件的不确定区域每两个类别之间可用判别平面分割，m(m-1) /2个判别函数。存在不满足条件的不确定区域 若，有，则X属于类。存在m个判别函数i=1,2,m除了边界以外，没有不确定区域，是第二种情况的特殊状态。在此种情况下可分，则在第二种情况下也可分，反之不然。 把X代入m个判别函数中，判别函数最大的那个类，就是X所属类别（1） 确定使用的判别函数类型或决策面方程类型，如线性分类器、分段线性分类器、非线性分类器或近邻法等。（2） 按需要确定一准则函数J，如Fisher准则、感知器算法、增量校正算法、LMSE算法。增量校正算法与感知器算法的实现相似，只不过是在进行权矢量修正时加上了权系数，LMSE算法以最小均方误差作为准则。（3） 确定准则函数J达到极值时及的具体数值，从而确定判别函数，完成分类器设计。 在计算机上确定各权值时采用的是“训练”或“学习”的方法，就是挑选一批已分类的样品，把这批样品输入到计算机的“训练”程序中去，通过多次迭代后，准则函数J达到极值，得到正确的线性判别函数。5.4 感知器算法1.理论基础既然判别函数分类器的训练过程就是确定该函数的权集，为叙述方便起见，从判别函数的一般形式着手。对于两类问题，设有判别函数 (5-9)并已知训练集XA,XB,XC,XD，且因而对它们来说 又因而对它们来说设则判别函数可以联立成即因此判别函数可写成一般方程形式XW>0 (5-10)其中W为权矢量X为各样品特征值的增1矩阵，即训练过程就是对判断好的样品集求解权矢量W，即根据已知类别的样品求出权系数，形成判别界线（面），再对未知类别的样品求出其类别。这是一个线性联立不等式的求解问题，只对线性可分问题方程（5-10）才有解。对这样的问题来说，如果有解，其解也不一定是单值的，因而就有一个按不同条件取得最优解的问题，因此出现了多种不同的算法，这里介绍梯度法。2梯度下降法因为求某一函数f(W)的数值解，通常只能求出在某种意义下的最优解，即先定义一个准则函数，然后在此函数最大或最小的情况下，求出f(W)的解。梯度法就是先确定一准则函数J(W)，然后选一初值W(1)，这样可用迭代式W(k+1)=W(k)-C·J(W(k) (5-11)找到W的数值解。设有一组样品X1,X2,XN，其中Xi是规范化增广样品向量，目的是找一个解向量W*，使得WTXi>0, i=1,2,N (5-12)显然，对于线性可分情况，问题才有解。为此这里首先考虑处理线性可分问题的算法。可将准则函数J的形式选为J(W,X)=k(WTX-WTX) (5-13)1）当X被错分类时，就有WTX<0。因此式（5-13）
