模式识别-3分类器的设计

第三章分类器的设计线性分类器的设计分段线性分类器的设计非线性分类器的设计[e-mail]2009[e-mail]123456§3-1线性分类器的设计上一章我们讨论了线性判别函数形式为:g(x)=WTX其中X=(X1,X2…Xn)n维特征向量W=(W1,W2…Wn,Wn+1)n维权向量通常通过特征抽取可以获得n维特征向量，因此n维权向量是要求解的。求解权向量的过程就是分类器的训练过程，使用已知类别的有限的学习样本来获得分类器的权向量被称为有监督的分类。0)(,0)(,21xgxxgx分类准则利用已知类别学习样本来获得权向量的训练过程如下已知x1∈ω1,通过检测调整权向量，最终使x1∈ω1已知x2∈ω2,通过检测调整权向量，最终使x2∈ω2这样就可以通过有限的样本去决定权向量x1x2…….xn1w1w2wnwn+1∑0x∈ω1检测(已知类别)W1X1W2X2WnXnWn+10x∈ω2g(x)=wTxWW1利用方程组来求解权向量对二类判别函数g(x)=W1X1+W2X2+W3已知训练集：Xa,Xb,Xc,Xd且当(Xa,Xb)∈W1时g(x)＞0当(Xc,Xd)∈W2时g(x)＜0设Xa=(X1a,X2a)TXb=(X1b,X2b)TXc=(X1c,X2c)TXd=(X1d,X2d)T判别函数可联立成：X1aW1+X2aW2+W3＞0①X1bW1+X2bW2+W3＞0②X1cW1+X2cW2+W3＜0③X1dW1+X2dW2+W3＜0④求出W1,W2,W3将③④式正规化，得-X1cW1-X2cW2-W30-X1dW1-X2dW2-W30所以g(x)=WTX0其中W=(W1,W2,W3)T为各模式增1矩阵为N*(n+1）矩阵N为样本数，n为特征数111121212121ddccbbaaXXXXXXXXX训练过程就是对已知类别的样本集求解权向量w，这是一个线性联立不等式方程组求解的过程。求解时：①只有对线性可分的问题，g(x)=WTX才有解②联立方程的解是非单值，在不同条件下，有不同的解，所以就产生了求最优解的问题③求解W的过程就是训练的过程。训练方法的共同点是，先给出准则函数，再寻找使准则函数趋于极值的优化算法，不同的算法有不同的准则函数。算法可以分为迭代法和非迭代法。一梯度下降法—迭代法欲对不等式方程组WTX0求解，首先定义准则函数(目标函数)J(W)，再求J(W)的极值使W优化。因此求解权向量的问题就转化为对一标量函数求极值的问题。解决此类问题的方法是梯度下降法。方法就是从起始值W1开始，算出W1处目标函数的梯度矢量▽J(W1)，则下一步的w值为：W2=W1-ρ1▽J(W1)W1为起始权向量ρ1为迭代步长J(W1)为目标函数▽J(W1)为W1处的目标函数的梯度矢量在第K步的时候Wk+1=Wk-ρk▽J(Wk)ρk为正比例因子这就是梯度下降法的迭代公式。这样一步步迭代就可以收敛于解矢量，ρk取值很重要ρk太大，迭代太快，引起振荡，甚至发散。ρk太小，迭代太慢。应该选最佳ρk。选最佳ρk目标函数J(W)二阶台劳级数展开式为J(W)≈J(Wk)+▽JT(W-Wk)+(W-Wk)TD(W-Wk)T/2①其中D为当W=Wk时J(W)的二阶偏导数矩阵将W=Wk+1=Wk-ρk▽J(Wk)代入①式得：J(Wk+1)≈J(Wk)-ρk||▽J||2+ρk2▽JTD▽J其中▽J=▽J(Wk)对ρk求导数，并令导数为零有最佳步长为ρk=||▽J||2/▽JTD▽J这就是最佳ρk的计算公式，但因二阶偏导数矩阵D的计算量太大，因此此公式很少用。21若令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-1▽J—牛顿法的迭代公式D-1是D的逆阵讨论：牛顿法比梯度法收敛的更快，但是D的计算量大并且要计算D-1。当D为奇异时，无法用牛顿法。二感知器法感知器的原理结构为：通过对W的调整，可实现判别函数g(x)=WTXRT其中RT为响应阈值定义感知准则函数：只考虑错分样本定义：其中x0为错分样本当分类发生错误时就有WTX0，或－WTX0,所以J(W)总是正值，错误分类愈少，J(W)就愈小。理想情况为即求最小值的问题。0)(XXXWWJT0)(WJ求最小值对W求梯度代入迭代公式中Wk+1=Wk-ρk▽J由J(W)经第K+1次迭代的时候，J(W)趋于0，收敛于所求的W值0)(XXXWWJJ01XXXWWkkk即感知器迭代公式：+感知器算法：1.错误分类修正wk如wkTx≤0并且x∈ω1wk+1=wk-ρkx如wkTx≥0并且x∈ω2wk+1=wk-ρkx2.正确分类，wk不修正如wkTx＞0并且x∈ω1如wkTx＜0并且x∈ω2wk+1=wk+-Hwk+1ρkxwk权值修正过程ρk选择准则①固定增量原则ρk固定非负数②绝对修正规则ρk③部分修正规则ρk=λ0＜λ≤2xxxwTT||xxxwTT||例题：有两类样本ω1=（x1,x2）={(1,0,1),(0,1,1)}ω2=（x3,x4）={(1,1,0),(0,1,0)}解：先求四个样本的增1模式x1=(1,0,1,1)x2=(0,1,1,1)x3=(1,1,0,1)x4=(0,1,0,1)假设初始权向量w1=(1,1,1,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所以修正w1w2=w1-x3=(0,0,1,0)w2Tx4=(0,0,1,0)T(0,1,0,1)=0所以修正w2w3=w2-x4=(0,-1,1,-1)第一次迭代后,权向量w3=(0,-1,1,-1),再进行第2,3,…次迭代如下表直到在一个迭代过程中权向量相同，训练结束。w6=w=(0,1,3,0)判别函数g(x)=-x2+3x3感知器算法只对线性可分样本有收敛的解,对非线性可分样本集会造成训练过程的振荡,这是它的缺点.训练样本wkTx修正式修正后的权值wk＋1迭代次数x11011x20111x31101x40101+++0w1w1w1-x3w2-x41111111100100–11-11x11011x20111x31101x401010+0-w3+x1w4w4-x3w51–1201–1200–22–10–22-12x11011x20111x31101x40101+---w5w5+x2w6w60–22–10–1300–1300–1303x11011x20111x31101x40101++--w6w6w6w60–1300–1300–1300–1304线性不可分样本集的分类解(取近似解)对于线性可分的样本集，可以用上述方法解到正确分类的权向量。当样本集线性不可分时，用上述方法求权值时算法不收敛。如果我们把循环的权向量取平均值作为待求的权向量，或就取其中之一为权向量，一般可以解到较满意的近似结果。例：在样本ω1:X1=（0,2）X3=（2,0）X5=（-1,-1）ω2:X2=（1,1）X4=（0,-2）X6=（-2,0）求权向量的近似解x2x1x6x1x3－2x5－2x4x211H解：此为线性不可分问题，利用感知器法求权向量权向量产生循环(-1,2,0),(0,2,2),(-1,1,1),(-1,1,1)(-1,1,1),(0,0,0),(-1,2,0)因此算法不收敛，我们可以取循环中任一权值，例如取W=(0,2,2)T则判别函数为：g(x)=2x1+2x2判别面方程为：g(x)=2x1+2x2＝0所以x1+x2＝0由图看出判别面H把二类分开，但其中x2错分到ω1类，而x1错分到ω2类，但大部分分类还是正确的。作业：已知四个训练样本w1={(0,0),(0,1)}w2={(1,0),(1,1)}使用感知器固定增量法求判别函数设w1=(1,1,1,1)ρk=1要求编写程序上机运行，写出判别函数，并打出图表。三最小平方误差准则(MSE法)---非迭代法前面我们研究了线性不等式方程组g(x)=WTX0的解法。它们共同点是企图找一个权向量W，使错分样本最小。现在我们把不等式组变成如下形式：WTXi=bi0则有联立方程XW=b这是矛盾方程组，方程数大于未知数，所以没有精确解的存在。NnNNnNXXXXXXXXXXX.................................21211121121N.....2,1,XXXTX令给定的任意正常数N.....2,1,bbbTb每个样本有n个特征定义误差向量：e=XW-b≠0把平方误差作为目标函数W的优化就是使J(W)最小。求J(W)的梯度并为0。解上方程得XTXW=XTb这样把求解XW=b的问题，转化为对XTXW=XTb求解，这一有名的方程最大好处是因XTX是方阵且通常是非奇异的，所以可以得到W的唯一解。NibiXiWTbXWeWJ1222||||||||)(MSE准则函数0)(22J(W)1bXWXXbiXiWTTiNi只要计算出X+就可以得到W取：最小平方误差法同Fisher法是一致的。bXbXXXTWT1的伪逆（规范矩阵）称为其中XXXXTXT1221..........1/......///NNNNNNNNb（MSE解）其中N/N1有N1个，N/N2有N2个四韦—霍氏法（LMS法）迭代法上节得到MSE法的W解为：W=X+b在计算X+时，1．要求XTX矩阵为非奇异2．由于计算量太大而引入比较大误差所以要用迭代法来求求J(W)的梯度▽J(W)=2XT(XW-b)代入迭代公式W1任意设定Wk+1=Wk-ρkXT(XWk-b)此法可收敛于W值。W满足:XT(XW-b)=0为任意常数其中令11kkXXXTXT1伪逆计算量很大因此下降算法不论XTX是否奇异，总能产生一个解。若训练样本无限的重复出现，则简化为W1任意Wk+1=Wk+ρk(bk-WkTXk)Xkρk随迭代次数k而减少，以保证算法收敛于满意的W值k1K取五何—卡氏法（判断迭代过程中是否线性可分）若训练样本线性可分时，感知器法可求出界面，但对不可分问题不收敛只能取平均。最小平方误差法不论样本是否线性可分都能给出一加权矢量，但不能保证此矢量就是分界矢量，下面介绍一种方法可以检测迭代过程中是否线性可分。因最小平方误差法的J(W)的解为因为XW=bb应为正值c为矫正系数当（XWk-bk）≤0时当（XWk-bk）＞0时bXbXXXTWT1|]|[kkkkkbXWbXWcbb＝的增量为kkkbbbb1前后两次迭代后，对的增量为其中bbk0＝kb][2kkkbXWcb＝引入误差矢量ekek=XWk-bk判断是否线性可分所以J(W)的解为初始条件W1=X+b1并且b10迭代时检测如果ek≥0时，XWb，系统线性可分，迭代收敛如果ek0时，XWb，系统线性不可分，迭代不收敛我们用下面的例子来说明ek的作用|]|[kkkeeCb]|[][|11kKkkKkKKkeeXcWbXbXbbXbXW因此上式可以写成例题：ω1={(0,0)T,(0,1)T}ω2={(1,0)T,(1,1)T}解：正规化对ω2取负，有111101110100X2/12/12/12/311