《3-模式识别导论-分类器的设计.ppt》由会员分享,可在线阅读,更多相关《3-模式识别导论-分类器的设计.ppt(49页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章分类器的设计n线性分类器的设计n分段线性分类器的设计n非线性分类器的设计3-1线性分类器的设计上一章我们讨论了线性判别函数形式为:g(x)=WTX其中X=(X1,X2Xn)n维特征向量W=(W1,W2Wn,Wn+1)n维权向量通常通过特征抽取可以获得n维特征向量,因此n维权向量是要求解的。求解权向量的过程就是分类器的训练过程,使用已知类别的有限的学习样本来获得分类器的权向量被称为有监督的分类。利用已知类别学习样本来获得权向量的训练过程如下已知x11,通过检测调整权向量,最终使x11已知x22,通过检测调整权向量,最终使x22这样就可以通过有限的样本去决定权向量x1x2.xn1w1w2wn
2、wn+10 x1检测(已知类别)W1X1W2X2WnXnWn+10 -X1dW1-X2dW2-W3 0所以 g(x)=WTX 0 其中W=(W1,W2,W3)T为各模式增1矩阵为N*(n+1)矩阵N为样本数,n为特征数训练过程就是对已知类别的样本集求解权向量w,这是一个线性联立不等式方程组求解的过程。求解时:只有对线性可分的问题,g(x)=WTX才有解联立方程的解是非单值,在不同条件下,有不同的解,所以就产生了求最优解的问题求解W的过程就是训练的过程。训练方法的共同点是,先给出准则函数,再寻找使准则函数趋于极值的优化算法,不同的算法有不同的准则函数。算法可以分为迭代法和非迭代法。一梯度下降法迭
3、代法欲对不等式方程组WTX0求解,首先定义准则函数(目标函数)J(W),再求J(W)的极值使W优化。因此求解权向量的问题就转化为对一标量函数求极值的问题。解决此类问题的方法是梯度下降法。方法就是从起始值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目标函
4、数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-kJ(Wk)代入式得:J(Wk+1)J(Wk)-k|J|2+k2JTDJ其中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牛顿法的迭代公式
5、D-1是D的逆阵讨论:牛顿法比梯度法收敛的更快,但是D的计算量大并且要计算D-1。当D为奇异时,无法用牛顿法。二感知器法感知器的原理结构为:通过对W的调整,可实现判别函数g(x)=WTXRT其中RT为响应阈值定义感知准则函数:只考虑错分样本定义:其中x0为错分样本当分类发生错误时就有WTX0,所以J(W)总是正值,错误分类愈少,J(W)就愈小。理想情况为即求最小值的问题。求最小值对W求梯度代入迭代公式中Wk+1=Wk-kJ由J(W)经第K+1次迭代的时候,J(W)趋于0,收敛于所求的W值W的训练过程:例如:x1,x2,x31作x1,x3的垂直线可得解区(如图)假设起始权向量w1=0k=11.x
6、1,x2,x3三个矢量相加得矢量2,垂直于矢量2的超平面H将x3错分.2.x3与矢量2相加得矢量3,垂直于矢量3的超平面H1,将x1错分.3.依上法得矢量4,垂直于矢量4做超平面,H2将x3错分4.x3与矢量4相加得矢量5,矢量5在解区内,垂直于矢量5的超平面可以把x1,x2,x3分成一类。x1x2x32H3H14H25W区间+n感知器算法:1.错误分类修正wk如wkTx0并且x1wk+1=wk-kx如wkTx0并且x2wk+1=wk-kx2.正确分类,wk不修正如wkTx0并且x1如wkTx0并且x2wk+1=wk+-Hwk+1kxwk权值修正过程nk选择准则固定增量原则k固定非负数绝对修正
7、规则k部分修正规则k=02例题:有两类样本1=(x1,x2)=(1,0,1),(0,1,1)2=(x3,x4)=(1,1,0),(0,1,0)解:先求四个样本的增值模式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
8、,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+3x3n感知器算法只对线性可分样本有收敛的解,对非线性可分样本集会造成训练过程的振荡,这是它的缺点.训练样本训练样本wkTx修正式修正式修正后的权值修正后的权值wk1迭代次数迭代次数x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 1+0w1w1w1-x3w2-x41 1 1 11 1 1 10 0 1 00 1 1 -1 1x1 1
9、 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 10+0-w3+x1w4w4-x3w51 1 2 01 1 2 00 2 2 10 2 2 -1 2x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 1+-w5w5+x2w6w60 2 2 10 1 3 00 1 3 00 1 3 0 3x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 1+-w6w6w6w60 1 3 00 1 3 00 1 3 00 1 3 04线性不可分样本集的分类解(取近似解)对于线性可分的样本集,可以用上述方法解到正确分类的权向量。当样本集线性
10、不可分时,用上述方法求权值时算法不收敛。如果我们把循环的权向量取平均值作为待求的权向量,或就取其中之一为权向量,一般可以解到较满意的近似结果。例:在样本1:X1=(0,2)X3=(2,0)X5=(-1,-1)2:X2=(1,1)X4=(0,-2)X6=(-2,0)求权向量的近似解x2x1x6x1x32x52x4x211H解:此为线性不可分问题,利用感知器法求权向量权向量产生循环(-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+2
11、x2判别面方程为:g(x)=2x1+2x20所以x1+x20由图看出判别面H把二类分开,但其中x2错分到1类,而x1错分到2类,但大部分分类还是正确的。n作业:已知四个训练样本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这是矛盾方程组,方程数大于未知数,所以没有精确
12、解的存在。每个样本有n个特征定义误差向量:e=XW-b0把平方误差作为目标函数W的优化就是使J(W)最小。求J(W)的梯度并为0。解上方程得XTXW=XTb这样把求解XW=b的问题,转化为对XTXW=XTb求解,这一有名的方程最大好处是因XTX是方阵且通常是非奇异的,所以可以得到W的唯一解。MSE准则函数只要计算出X+就可以得到W取:最小平方误差法同Fisher法是一致的。(MSE解)其中N/N1有N1个,N/N2有N2个四韦霍氏法(LMS法)迭代法上节得到MSE法的W解为:W=X+b在计算X+时,1要求XTX矩阵为非奇异2由于计算量太大而引入比较大误差所以要用迭代法来求求J(W)的梯度J(W
13、)=2XT(XW-b)代入迭代公式W1任意设定Wk+1=Wk-kXT(XWk-b)此法可收敛于W值。W满足:XT(XW-b)=0计算量很大因此下降算法不论XTX是否奇异,总能产生一个解。若训练样本无限的重复出现,则简化为W1任意任意 Wk+1=Wk+k(bk-WkTXk)Xkk随迭代次数k而减少,以保证算法收敛于满意的W值五何卡氏法(判断迭代过程中是否线性可分)若训练样本线性可分时,感知器法可求出界面,但对不可分问题不收敛只能取平均。最小平方误差法不论样本是否线性可分都能给出一加权矢量,但不能保证此矢量就是分界矢量,下面介绍一种方法可以检测迭代过程中是否线性可分。n因最小平方误差法的J(W)的
14、解为n因为XW=bb应为正值nc为矫正系数当(XWk-bk)0时当(XWk-bk)0时n引入误差矢量ekek=XWk-bk判断是否线性可分n所以J(W)的解为初始条件W1=X+b1并且b10n迭代时检测如果ek0时,XWb,系统线性可分,迭代收敛如果ek0时,XWb,系统线性不可分,迭代不收敛n我们用下面的例子来说明ek的作用因此上式可以写成n例题:1=(0,0)T,(0,1)T2=(1,0)T,(1,1)Tn解:正规化对2取负,有X的规范矩阵为x2x1x1x2x3x4取b1=(1,1,1,1)Tc=1W1=X+b1=(-2,0,1)T所以W1为所求解e1=XW1-b1=0系统线性可分因为若四
15、个样本变成:1=(0,0)T,(1,1)T2=(0,1)T,(1,0)T解:取b1=(1,1,1,1)Tc=1W1=X+b1=(0,0,0)Te1=XW1-b1=(-1,-1,-1,-1)T0系统线性不可分C为校正系数,取0C1在算法进行过程中,应在每一次迭代时,检测ek的值。只要出现ek0X1X=-WTX-W00X1Y=WTX-W00则X1;Y=WTXWin(k)lxji=1,2,M类j=1,2,li子类ij则权向量Wi1(k),Wi2(k),,Wili(k)不影响分类,所以权向量不需要修正。若有某个或某几个子类不满足条件即:存在Win(k)使Wjn(k)xjWin(k)lxjij所以xj错
16、分类,要修改权向量。设Win(k)lxj=maxWin(k)lxjn=1,2,liij则修改权向量Wjn(k+1)=Wjn(k)kxj重复以上迭代,直到收敛,此法类似于固定增量法.3.未知子类数目时的设计方法当每类应分成的子类数也不知时,这是最一般情况,方法很多,举例如下。树状分段线性分类器:设两类情况1,2。如图所示先用两类线性判别函数求出W1,超平面H1分成两个区间,每个区间包含两类。再 利 用 二 类 分 类 求 出W2(H2),W3(H3)。如果每个部分仍包含两类,继续上面的过程。n关键是初始权向量W1的选择:一般先选两类中距离最近的两个子类的均值连线做垂直线作为H1(w1)初始值再求
17、最优解。w1Tx0w4Tx0w3Tx0w2Tx0YNYYNN1122NY1树状决策框图3-3非线性分类器的设计n电位函数分类器,用非线性判别函数区分线性不可分的类别n电位函数分类器:每个特征作为一个点电荷,把特征空间作为能量场.电位分布函数有下面三种形式。为系数xk为某一特定点上图是这些函数在一维时的图形,第三条是振荡曲线,只有第一周期才是可用范围。xK(x)x321电位函数算法的训练过程是在逐个样本输入时,逐渐积累电位的过程,对于二类问题,经过若干循环后,如积累电位方程的运算结果能以正、负来区分二类样本,则训练就可结束。算法:设初始电位为K0(x)=01.输入样本x1计算积累电位K1(x)若
18、x1K1(x)=K0(x)+K(xx1)若x2K1(x)=K0(x)-K(xx1)设1为正电荷,2为负电荷在K0(x)=0时若x11K1(x)=K(xx1)若x12K1(x)=-K(xx1)2.输入样本x2计算积累电荷有以下几种情况a.若x21并且K1(x2)0若x22并且K1(x2)0或xk+12并且Kk(xk+1)0时rk+1=0 xk+11并且Kk(xk+1)0时rk+1=1xk+12并且Kk(xk+1)0不修正K2(x)=K1(x)=exp-(x12+x22)输入x3=(1,1)Tx32代入K2(x3)=exp-(12+12)0所以需要修正K3(x)=K2(x)-K(xx3)=exp-
19、(x12+x22)-exp-(x1-1)2+(x2-1)2输入x4=(1,-1)Tx32代入K3(x4)=e-2-e-40所以需要修正K4(x)=K3(x)-K(xx4)=exp-(x12+x22)-exp-(x1-1)2+(x2-1)2-exp-(x1-1)2+(x2+1)2n第二次迭代输入x5=x1=(0,-0)Tx51代入K4(x5)=1-e-2-e-40K5(x)=K4(x)输入x6=x2=(2,0)Tx61代入K5(x6)=e-4-e-2-e-2=0所以需要修正K6(x)=K5(x)+K(xx6)=exp-(x12+x22)-exp-(x1-1)2+(x2-1)2-exp-(x1-1
20、)2+(x2+1)2+-exp-(x1-2)2+x22输入x7=x3=(1,1)Tx72代入K6(x7)=e-2-e0-e-4+e-20所以不需要修正K7(x)=K6(x)输入x8=x4=(1,-1)Tx82代入K7(x8)=e-2-e-2-e0+e-20所以不需要修正K9(x)=K8(x)g(x)0g(x)0g(x)0同理得到:K10(x)=K9(x)=K8(x)=K7(x)=K6(x),经一个完整的循环可得判别函数为:g(x)=exp-(x12+x22)-exp-(x1-1)2+(x2-1)2-exp-(x1-1)2+(x2+1)2+exp-(x1-2)2+x22上边的非线性判别函数形成的边界如图所示。虽然它可以把线性不可分的样本分开,但当样本很多时,使方程的项数太多,增大计算量。