模式识别第二章DiscriminantFunction

1、 2.1判别函数 2.2Fisher线性判别 2.3感知器准则函数 2.4最小平方误差准则和最小错分样本准则 2.5分段线性判别函数 2.6二次判别函数第二章 判别函数2.1 判别函数v假设对一模式X已抽取n个特征，表示为：v模式识别问题就是根据模式X X的n n个特征来判别模式属于1 ,2 , , m 类中的那一类。维空间的一个向量是n),.,(321XxxxxXTn2.1 判别函数v例如下图：三类的分类问题，它们的边界线就是一个判别函数123边界2x1xv判别函数包含两类：v一类 是线性判别函数：线性判别函数广义线性判别函数 （所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间变成

2、线性判别函数）分段线性判别函数v另一类是非线性判别函数2.1.1 线性判别函数v我们现在对两类问题和多类问题分别进行讨论。v(一)两类问题 即: v v1. 二维情况 ：取两个特征向量v 这种情况下 判别函数: 2,),(21MTi2,)(2,1nxxxT32211)(wxwxwxg为坐标分量为参数，21, xxwv在两类别情况，判别函数 g (x) 具有以下性质：v这是二维情况下判别由判别边界分类.v情况如图：21, 0, 0)(xxxgi不定xxg,0)(32211)(wxwxwxg211x2x2. n维情况v现n个特征为：v判别函数： v另外一种表示方法：Tnxxxx),.,(321x1

3、2211.)(nnnwxwxwxwxg10nTwxW为增广模式向量。，为增广权向量，TnnTnnxxxxxwwwwW),.,(),.,(121121xWxgT)(为模式向量。为权向量，TnTnxxxxwwwW),.,(),.,(21210v模式分类：v当 g1(x) =WTx=0 为判别边界 。当n=2时，二维情况的判别边界为一直线。当n=3时，判别边界为一平面，n3时，则判别边界为一超平面。21,0,0)(xxxWxgT2. n维情况(二) 多类问题v对于多类问题，模式有 1 ,2 , , M 个类别。可分三种情况：1。第一种情况：每一模式类与其它模式类间可用单第一种情况：每一模式类与其它模

4、式类间可用单个判别平面把一个类分开。个判别平面把一个类分开。这种情况，M类可有M个判别函数，且具有以下性质：被称作： 分法权向量。个判别函数的为第式中iwwwwWTniiniii),.,()1(21ii。其它MixxWxgiTii,.,2 , 1, 0, 0)(v右图所示，每一类别可用单个判别边界与其它类别相分开 。v如果一模式X属于1，则由图可清楚看出:这时g1(x) 0而g2(x) 0 ， g3(x) 0 , g2(x) 0 , g3(x) 0 。则此模式X就无法作出确切的判决。如图中 IR1,IR3，IR4区域。v另一种情况是IR2区域，判别函数都为负值。IR1，IR2，IR3，IR4。

5、都为不确 定区域。1.1.第一种情况（续）第一种情况（续）30)(0)(0)(321xgxgxg12000321)x(g)x(g)x(g0)(0)(0)(321xgxgxg 4IR3IR1IR2IR1x2x0)(1xg0)(2xg0)(3xg551v问当x=(x1,x2)T=(6,5)T时属于那一类v结论： g1(x) 0 , g3(x) g2(x) 和 g1(x) g3(x) 。v假设判别函数为：v则判别边界为：3.第三种情况（续）23212211)(1)()(xxgxxxgxxxg012)()(02)()(012)()(21322131121xxxgxgxxxgxgxxgxg2)()(21

6、xgxg)()(32xgxg)()(31xgxg13v结论：不确定区间没有了，所以这种是最好情况。v用上列方程组作图如下：3.第三种情况（续）1)()()()(3121xgxgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32xgxg0)()(21xgxg0)()(31xgxg0.15.05.0v问假设未知模式 x = (x1,x2)T= (1,1)T ，判断x属于那一类。v把它代入判别函数：v得判别函数为：v因为v所以模式x= (1,1)T属于 类。3. 第三种情况（续）2)()(),()(1232xgxgxgxg1)(, 1)(, 0

7、)(321xgxgxg).(),(),(321xgxgxg1)()()()(3121xgxgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32xgxg0)()(21xgxg0)()(31xgxg0.15.05.0NOTE: （1）判别函数在特征空间中表现出的是某条直线(平面、超平面），这条直线由判别函数的方程决定的。模式类别在空间的分布是确定的，模式类的分布与直线的相对关系不同从而导致会出现前面介绍的三类情况。 NOTE: （2）如前面所介绍，其正负标记完全是由求解 得来的。对于二维情况，满足大于0的（x1，x2）的区域标记为正，小于0的

8、（x1，x2）的区域标记为负。21, 0, 0)(xxxwxdt如如2.1.2 模式空间和权空间 统一判别形式 判别函数d(x)=wtx, 其中w,x为增广向量。Wtx0为分类的判别界面。通常 i, 0)(xxwxdt则j, 0)(xxwxdt则j, 0)()(xxwxdt则i, 0)(xxwxdt则对两类问题的等价预处理，使之具有统一的判断形式。对两类问题的等价预处理，使之具有统一的判断形式。同时研究判别函数（判别界面在空间中的特性与类的同时研究判别函数（判别界面在空间中的特性与类的位置）空间位置）空间(1) 增广空间和非增广空间增广空间和非增广空间(2)模式空间和权空间模式空间和权空间2.

9、1.2 模式空间和权空间 模式空间 对一个线性方程w1x1+w2x2+w3x3=0，它在三维空间(x1 x2 x3)中是一个平面方程式，w=(w1 w2 w3)T是方程的系数。 把w向量作为该平面的法线向量，则该线性方程决定的平面通过原点且与w垂直。 模式空间 若x是二维模式增广后的向量，此时x3=1判别函数是下列联立方程的解 w1x1+w2x2+w3 x3 =0 x3=1即为这两个平面相交的直线AB 此时， 在非增广的模式空间中即为x1, x2 二维坐标， w =(w1 w2)T为非增广的权向量，它与直线AB垂直；AB将平面分为正、负两侧，w离开直线的一侧为正， w射向直线的一侧为负。模式空

10、间增广向量决定的平面(a) 非增广向量决定的直线 权空间 若将方程x1w1+x2w2+w3=0绘在权向量w=(w1 w2 w3)T的三维空间中，则x=(x1 x2 1)T为方程的系数。 若以x向量作为法线向量，则该线性方程所决定的平面为通过原点且与法线向量垂直的平面，它同样将权空间划分为正、负两边。 在系数x不变的条件下， 若w值落在法线向量离开平面的一边，则wTx0 若w值落在法线向量射向平面的一边，则wTx 0,W指向1，为H的正侧，反之为H的负侧.上矢量一定在HxxxxWwxWwxWTnTnT)( , 0)(021211211W1x2X1X2xH12g(x)0g(x)n则分类界面在x*中

11、是线性的，在x中是非线性的，此时只要将模式x进行非线性变换，使之变换后得到维数更高的模式x*，就可以用线性判别函数来进行分类kixfwwxfwxfwxfwxgkiiikkk,.,2 , 1, )()(.)()()(1112211v这样一个非线性判别函数通过映射，变换成线性判别函数。1)(,)(1xfxfki是单值函数式中v判别函数的一般形式：2111,0,0)()()(xxYgYWxfwxgTyxkiii空间变换空间0YWT判别平面：)( ,)(.)()()( ,., 0, 0)()()(21212111增广模式向量。广义权向量其中：空间变换空间xfxfxfYwwwWxxYgYWxfwxgkk

12、Tyxkiii21,xaxbxbxorax则则0bax二次判别函数1212321212123211,0,0)()(,0,0)(xxYaaaWxxYgYWxgxxxaxaaxgT映射：v要用二次判别函数才可把二类分开：)1 , 1, 1 ()25.0 , 5 .0 , 1 (),0 , 0 , 1 (321YYY05 .011y3y2yW平面oYWTx121015 . 012)(1,2112, 1, 12123212321321YWYxxxxxgyyyxxYaaaWaaayT空间判别平面：即：空间它的判别边界：设讨论在推出v从图可以看出：在阴影上面是1类，在阴影下面是2类，v结论：在X空间的非线

13、性判别函数通过变换到Y空间成为线性的，但X变为高维空间05 .011y3y2yW平面oYWTx1212.1.5 设计线性分类器的步骤 就是用标有类别的样本去训练分类器，分类器有线性判别函数的性质。只是参数未知。 其实就是找到最佳W的过程 所以线性分类器设计过程： 1.得到标有类别的样本，确定线性分类器的维数。 2.根据实际情况选择准则函数J，要求： J能反映分类器的性能，它的极值对应“最好”的决策 J是样本集、W的函数 3.利用最优技术得到准则函数的极值解：分类器设计好以后，对于未知类别的样本x，我们就计算g(x)，然后根据判别式得到x的类别*W 我们后面讲的都是线性分类器的设计方法： 包括

14、Fisher准则 感知器准则 最小均方误差准则 最小错分样本数准则2.2 Fisher线性判别 考虑将样本的维数降到1维，那么如果可以找到一个最好的投影线，那么在一维上我们可以找出那个分界点来做分类。 若 ，则g(x)就是x在W方向上的投影。)(,)()()(021WWWrWxgrWrWWWrWWrWrWxgwxWHpTTTTnpT是投影的绝对值上。在因为11)()(npTnTwrxWwxWxg1nTpTwrWxW1W 假设对于两类问题d维的样本，共有N个，其中2211HNHN21我们记为合个样本，这些样本的集类有；同样合我们记为个样本，这些样本的集类有Nnyn,21，性变换得到标量：我们对所

15、有的样本做线xwt 我们现在已知判别函数的形式，下来就是怎么求准则函数，以及最优化问题。 在定义fisher的准则函数之前，我们先定义几个必要的基本参量： 1.d维的X空间 1）iHxiiiixN1mm21，各类样本的均值向量 2） 3） 4）iHxiiiiim-(xm-(xSS21)，类内离散度矩阵t21wwSSSS总类内离散度矩阵t)2121bbm-(mm-(mSS类间离散度矩阵 2.在一维Y空间 1） 2） 3）iyyiiiiyN1mm21，各类样本的均值向量iyyi2i2iim-(ySS21)2，类内离散度矩阵2221wwSSSS总类内离散度矩阵现在我们定义fisher的准则函数：上式

16、并不是w的显式函数，我们将它改写222121SSm-m()(2wJFitHxitHxtiyyiimwxN1wxwN1yN1miii)(其中wSwwwtttbt2121t2121wmmmmwmmm-m()()()22所以分子wSwm-(xm-(xwmw-x(wm-(ySitixxitxxittyyi2iiiiwt)22wSw)wSSwSSwt21t2221(所以分母wSwwwtbtwSwJF)(*)(w最大值时的下面我们求使wJF 用lagrange乘子法求解 令*b1-w*w*bwbwtbtwtwwSS0wS-wSwS-wSw)L(w,c)-wS(w-wSw)L(w,0cwSw)()()()(

17、)()(*211-w*211-w*211-w*b1-w*21212121*bmmSwmmSRwRmmSwSSwmm RRmmmmmmwS所以标量对方向没有影响。找方向，为一个标量，我们只是wwtt阈值才能判断类别我们还需要一个一维的降到一维以后，现在我们已把一个n维的问题转化为一维的问题。现在一维空间设计 Fisher分类器:W0的选择 2010XWXWYXWXWYTT2.1210YYW2121212102122.2NNXWNXWNNNYNYNWTT Yki表示第i类中第k个样本的投影值 N1为1样本数 N2为2样本数 当W0选定后，对任一样本X，只要判断Y=WTX W0 则X1; Y=WTX

18、 W0 则X2。分类问题就解决了NYYNYYNYYYYYWkkkkkk2211111211221121120)(.32.3 感知器准则函数2.3.1 几个基本概念1.线性可分性：v一组模式样本不一定是线性可分的，所以需要研究线性分类能力的方法，对任何容量为N的样本集，线性可分的概率多大呢？v（如下图（a），线性不可分）v例：4个样本有几种分法。v图（b）直线把x1分开，每条直线可把4个样本分成1 2 类，4个样本分成二类的总的可能的分法为24=16类，其中有二种是不能用线性分类实现的线性可分的是14。即概率为14/16。（a）x1x2x3x4 （b）v结论：N个样品线性可分数目(条件：样本分布

19、良好）：为特征数为样本数其中nNkNkNCkN,)!1( !)!1(1nkkNNnNCnNnND011,21,2),(若若v对N和n各种组合的D(N,n)值，表示在下表中，从表中可看出，当N，n缓慢增加时D(N,n)却增加很快。1234561222222244444436888884814161616165102230323232n),(nNDNnkkNNNnNCnNnNDnNP0111,21, 12),(),(若若v线性可分概率：),(nNP0 .15 .00543211n5n15nn1nN强。说明样本少时二分能力范围，即在。时，线性可分概率为时，即值，对于任意。处出现明显的门限效应时，曲线

20、急剧下降，在由当, 1),(),1(22: )(21),() 1(22: )(21: )(nNPnNcnNPnNnbnav把上式用曲线表示成下图：图中横坐标用=N/n+1表示。v由图讨论：.2),1(2: )(,),1(22: )(0是最好情况即二分能力）的估计：个样本的线性可分性（对多线性可分能力越差。说明样本越线性可分概率急剧下降范围，即在nNNenNdv结论：在实际工作中，分类的训练非常重要，由已知样本来训练。因为已知样本有限，而未知样本无限。选择已知类别的训练样本数方法如下：),(nNP0 .15 .00543211n5n15nn1nNv：如果训练样本N RT 其中RT为响应阈值定义感

21、知准则函数：只考虑错分样本定义： 其中x0为错分样本当分类发生错误时就有WTX 0, 所以J(W) 总是正值，错误分类愈少， J(W)就愈小。理想情况为 即求最小值的问题。0)(XXXWWJT0)(WJ 感知器准则求最优方法： 1.错误分类修正wk 如wkTx0并且x1 wk+1= wk+ kx 如wkTx0并且x2 wk+1= wk- kx 2.正确分类 ，wk不修正 如wkTx0并且x1 如wkTx0并且x2 wk+1= wk 感知器的训练算法 感知器算法实质上是一种赏罚过程 对正确分类的模式则“赏”，实际上是“不罚”，即权向量不变。 对错误分类的模式则“罚”，使w(k)加上一个正比于xk

22、的分量。 当用全部模式样本训练过一轮以后，只要有一个模式是判别错误的，则需要进行下一轮迭代，即用全部模式样本再训练一次。 如此不断反复直到全部模式样本进行训练都能得到正确的分类结果为止。（1） 给定两个训练模式集合，分属于和类1 2 ，初始向量为W(1)。并将特征向量写成增增广形式广形式，将属于类2的训练样本全部乘以（1）。得到新的样本集合A， NOTE：本过程实际上是预处理，使后续修正判断具有统一的表达形式，该预处理，并不改变样本的分类结果。 （2）错误分类修正wk 如wkTx0 wk+1= wk+ kx 如wkTx0 wk+1= wk （3）用全部样本训练过一次以后，如果有一个样本的判别是

23、错误的，则继续进行下一轮，直到全部的样本都能正确分类为止。 k选择准则 固定增量原则 k固定非负数 =1 绝对修正规则 k 部分修正规则 k= 02xxxwTT|xxxwTT|例题：有两类样本 解：先求四个样本的增值模式,并对第二类样本乘以-1假设初始权向量 k=1第一次迭代： w1Tx1=(1,1,1,1) (1,0,1,1)T=30 所以不修正 w1Tx2=(1,1,1,1) (0,1,1,1)T=30 所以不修正 w1Tx3=(1,1,1,1) (-1,-1,0,-1)T=-30求解，首先定义准则函数(目标函数)J(W)，再求J(W)的极值使W优化。因此求解权向量的问题就转化为对一标量函

24、数求极值的问题。解决此类问题的方法是梯度下降法。方法就是从起始值W1开始，算出W1处目标函数的梯度矢量J(W1)，则下一步的w值为：W2 = W1-1J(W1)W1为起始权向量 1为迭代步长 J(W1) 为目标函数J(W1)为W1处的目标函数的梯度矢量在第K步的时候Wk+1 = Wk-kJ(Wk) k为正比例因子这就是梯度下降法的迭代公式。这样一步步迭代就可以收敛于解矢量，k取值很重要 k太大，迭代太快，引起振荡，甚至发散。 k太小，迭代太慢。 应该选最佳k。选最佳选最佳k 目标函数J(W)二阶泰勒级数展开式为 J(W)J(Wk)+ JT(W- Wk)+(W- Wk)TD(W- Wk)T/2

25、其中D为当W = Wk时 J(W)的二阶偏导数矩阵 将W=Wk+1 = Wk-kJ(Wk)代入式得： J(Wk+1) J(Wk)- k|J|2+ 0.5k2JT DJ 其中J=J(Wk) 对k求导数 ，并令导数为零有 最佳步长为k=|J|2/JTDJ这就是最佳k的计算公式，但因二阶偏导数矩阵D的计算量太大，因此此公式很少用。 若令W=Wk+1 式为J(Wk+1)=J(Wk)+JT(Wk+1-Wk)+(Wk+1-Wk)TD(Wk+1-Wk)T/2 对Wk+1求导，并令导数为零可得：最佳迭代公式：Wk+1= Wk- D-1J 牛顿法的迭代公式 D-1是D的逆阵讨论：牛顿法比梯度法收敛的更快，但是D

26、的计算量大并且要计算D-1。当D为奇异时，无法用牛顿法。求最小值对W求梯度代入迭代公式中Wk+1 = Wk-kJ 由J(W)经第K+1次迭代的时候，J(W)趋于0，收敛于所求的W值0)(XXXWWJJ01XXXWWkkk即感知器迭代公式：0)(XXXWWJT最小值的问题对于感知器算法求W的训练过程：例如:x1, x2, x31 作 x1, x3的垂直线可得解区(如图) 假设起始权向量w1=0 k = 1 1. x1, x2, x3三个矢量相加得矢量2,垂直于矢量2的超平面H将x3错分. 2. x3与矢量2相加得矢量3,垂直于矢量3的超平面H1,将x1错分. 3.依上法得矢量4,垂直于矢量4做超

27、平面, H2将x3错分 4. x3与矢量4相加得矢量5,矢量5在解区内,垂直于矢量5的超平面可以把 x1, x2, x3分成一类 。x1x2x32H3H14H25W区间2.4 最小平方误差准则(MSE法)-非迭代法前面我们研究了线性不等式方程组g(x) =WTX0的解法。它们共同点是企图找一个权向量W，使错分样本最小。现在我们把不等式组变成如下形式：WTXi=bi0 则有联立方程XW=b 这是矛盾方程组，方程数大于未知数，所以没有精确解的存在。NnNNnNXXXXXXXXXXX.21211121121变换后的值是增广并乘令) 1(,XXTN . 2,1,XXX给定的任意正常数N . 2,1,b

28、bbTb 每个样本有n-1个特征定义误差向量：e=XW-b0 把平方误差作为目标函数 W的优化就是使J(W)最小。求J(W)的梯度并为0。解上方程得 XTXW=XTb这样把求解XW=b的问题，转化为对XTXW=XTb求解，这一有名的方程最大好处是因XTX是方阵且通常是非奇异的，所以可以得到W的唯一解。 NiiitbXWbXWeWJ1222)(|)(MSE准则函数 0)(2)(21bXWXXbXWTiNiiitJ(W)只要计算出 就可以得到W取： 最小平方误差法同Fisher法是一致的。 bXbXXXTWT1的伪逆（规范矩阵）称为其中XXXXTXT1221.1/./NNNNNNNNb（MSE 解

29、）其中N/N1有N1个，N/N2有N2个X2.4.1 何卡氏法(Ho-Kashyap) 若训练样本线性可分时，感知器法可求出界面，但对不可分问题不收敛只能取平均。最小平方误差法不论样本是否线性可分都能给出一加权矢量，但不能保证此矢量就是分界矢量，下面介绍一种方法一种方法可以检测迭代过程中是否线性可分可以检测迭代过程中是否线性可分。我们的目的是求解XW=b ，前面的最小均方误差法使用的统一的一个b,我们可以在每一步用不同的最优的b，让收敛速度加快。定义：则每次采用最优的b，则还应该满足每次b的每个分量应该大于0NiiitbXWWJ12)()(21)(21)(bXWbXWtbXbXXXWTT*1)

30、()() 1(kbbbJckbkb采用梯度法 因为XW=b b应为正值 c为矫正系数，一个正值 当（XWk-bk）0 时 当（XWk-bk） 0 时|kkkkkbXWbXWcbb的增量为kkkbbkkbbbJcbbb)(1前后两次迭代后，对的增量为其中bbk0kb2kkkbXWcb 引入误差矢量ek ek=XWk-bk判断是否线性可分 所以J(W)的解为 初始条件 W1=X+b1并且b10 迭代时检测 如果ek=0时，XW=b，系统线性可分，迭代收敛 如果ek0时，XW b0，系统线性可分，迭代收敛,可继续迭代，使ek趋于0 如果ek全为非正，但不全为0，系统线性不可分，迭代不收敛 我们用下面

31、的例子来说明ek的作用|kkkeecb|11kKkkKkKKkeeXcWbXbXbbXbXW因此上式可以写成 例题： 1=(0,0)T,(0,1)T 2=(1,0)T,(1,1)T 解：正规化 对2取负，有 111101110100X2/12/12/12/311111111211XXXTXTX的伪逆为x2x1x1x2x3x4取b1=(1,1,1,1)T c=1 W1=X+b1=(-2,0,1)T 所以W1为所求解 e1=XW1-b1=0 系统线性可分01111102111101110100, , ,1TWX因为 若四个样本变成：1=(0,0)T,(1,1)T 2=(0,1)T,(1,0)T解： 取b1=(1,1,1,1)T c=1 W1=X+b1=(0,0,0)T e1=XW1-b1=(-1,-1,-1,-1)TWi n (k)t xj i =1,2,M n =1,2,Li子类 ij 即