《模式识别导论三.pptx》由会员分享,可在线阅读,更多相关《模式识别导论三.pptx(49页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、会计学1模式识别导论三模式识别导论三2023/4/17 3-1 3-1 线性分类器的设计线性分类器的设计线性分类器的设计线性分类器的设计 上一章我们讨论了线性判别函数形式为上一章我们讨论了线性判别函数形式为:g(x)=W:g(x)=WT TX X 其中其中 X=(XX=(X1 1,X,X2 2XXn n)n)n维特征向量维特征向量 W=(WW=(W1 1,W,W2 2 WWn n,W,Wn+1n+1)n)n维权向量维权向量 通常通过特征抽取可以获得通常通过特征抽取可以获得n n维特征向量,因此维特征向量,因此n n维维权向量是要求解的。权向量是要求解的。求解权向量的过程就是分类器的训练过程,使
2、用已求解权向量的过程就是分类器的训练过程,使用已知类别的有限的学习样本来获得分类器的权向量被称为知类别的有限的学习样本来获得分类器的权向量被称为有监督的分类。有监督的分类。第1页/共49页2023/4/17利用已知类别学习样本来获得权向量的训练过程如下利用已知类别学习样本来获得权向量的训练过程如下利用已知类别学习样本来获得权向量的训练过程如下利用已知类别学习样本来获得权向量的训练过程如下已知已知x x1 1 1 1,通过检测调整权向量,最终使通过检测调整权向量,最终使x x1 1 1 1已知已知x x2 2 2 2,通过检测调整权向量,最终使通过检测调整权向量,最终使x x2 2 2 2这样就
3、可以通过有限的样本去决定权向量这样就可以通过有限的样本去决定权向量x1x2.xn1w1w2wnwn+10 x1检测(已知类别)W1X1W2X2WnXnWn+100 -X -X1d1dW W1 1-X-X2d2dW W2 2-W-W3 3 00所以所以 g(x)=Wg(x)=WT TX 0X 0 其中其中W=(WW=(W11,W,W2 2,W,W3 3)T T为各模式增为各模式增1 1矩阵矩阵 为为N*(n+1N*(n+1)矩阵)矩阵N N为样本数,为样本数,n n为特征数为特征数第4页/共49页2023/4/17训训练练过过程程就就是是对对已已知知类类别别的的样样本本集集求求解解权权向向量量w
4、 w,这是一个线这是一个线性性联立不等式方程组求解的过程。联立不等式方程组求解的过程。求解时:求解时:只有对线只有对线性性可分的问题,可分的问题,g(x)=Wg(x)=WT TX X才有解才有解 联联立立方方程程的的解解是是非非单单值值,在在不不同同条条件件下下,有有不同的解,所以就产生了求最优解的问题不同的解,所以就产生了求最优解的问题 求求解解WW的的过过程程就就是是训训练练的的过过程程。训训练练方方法法的的共共同同点点是是,先先给给出出准准则则函函数数,再再寻寻找找使使准准则则函函数数趋趋于于极极值值的的优优化化算算法法,不不同同的的算算法法有有不不同同的的准准则则函函数数。算算法法可可
5、以以分分为为迭迭代代法法和和非非迭迭代法。代法。第5页/共49页2023/4/17一、梯度下降法一、梯度下降法一、梯度下降法一、梯度下降法迭代法迭代法迭代法迭代法欲对不等式方程组欲对不等式方程组WWT TX0X0求解,首先定义准则函数求解,首先定义准则函数(目目标函数标函数)J(W)J(W),再求,再求J(W)J(W)的极值使的极值使WW优化。因此求解权优化。因此求解权向量的问题就转化为对一标量函数求极值的问题。解决向量的问题就转化为对一标量函数求极值的问题。解决此类问题的方法是梯度下降法。此类问题的方法是梯度下降法。方法就是从起始值方法就是从起始值WW1 1开始,算出开始,算出WW1 1处目
6、标函数的梯度处目标函数的梯度矢量矢量J(WJ(W1 1),则下一步的,则下一步的w w值为:值为:W W2 2=W=W1 1-1 1J(WJ(W1 1)WW1 1为起始权向量为起始权向量 1 1为迭代步长为迭代步长 J(WJ(W1 1)为目标函数为目标函数J(WJ(W1 1)为为WW1 1处的目标函数的梯度矢量处的目标函数的梯度矢量第6页/共49页2023/4/17在第在第K K步的时候步的时候W Wk+1 k+1=W=Wk k-k kJ(WJ(Wk k)k k为正比例因子为正比例因子这就是梯度下降法的迭代公式。这样一步步迭代这就是梯度下降法的迭代公式。这样一步步迭代就可以收敛于解矢量,就可以
7、收敛于解矢量,k k取值很重要取值很重要 k k太大,迭代太快,引起振荡,甚至发散。太大,迭代太快,引起振荡,甚至发散。k k太小,迭代太慢。太小,迭代太慢。应该选最佳应该选最佳 k k。第7页/共49页2023/4/17 选最佳选最佳选最佳选最佳 k k 目标函数目标函数J(W)J(W)二阶台劳级数展开式为二阶台劳级数展开式为 J(W)J(WJ(W)J(Wk k)+)+J JT T(W-W(W-Wk k)+(W-W)+(W-Wk k)T TD(W-WD(W-Wk k)T T/2 /2 其中其中DD为当为当W=WW=Wk k时时 J(W)J(W)的二阶偏导数矩阵的二阶偏导数矩阵 将将W=WW=
8、Wk+1 k+1=W=Wk k-k kJ(WJ(Wk k)代入代入式得:式得:J(WJ(Wk+1k+1)J(W)J(Wk k)-)-k k|J|J|2 2+k k2 2J JT T DDJ J 其中其中J=J=J(WJ(Wk k)对对 k k求导数求导数 ,并令导数为零有,并令导数为零有 最佳步长为最佳步长为 k k=|=|J|J|2 2/J JT TDDJ J这就是最佳这就是最佳 k k的计算公式,但因二阶偏导数矩阵的计算公式,但因二阶偏导数矩阵DD的计算的计算量太大,因此此公式很少用。量太大,因此此公式很少用。第8页/共49页2023/4/17若令若令W=WW=Wk+1k+1上式为上式为J
9、(WJ(Wk+1k+1)=J(W)=J(Wk k)+)+J JT T(W(Wk+1k+1-W-Wk k)+(W)+(Wk+1k+1-W-Wk k)T TD(WD(Wk+1k+1-W-Wk k)T T/2 /2 对对WWk+1k+1求导,并令导数为零可得:求导,并令导数为零可得:最佳迭代公式:最佳迭代公式:WWk+1k+1=W=Wk k-D-D-1-1J J 牛顿法的迭代公式牛顿法的迭代公式 DD-1-1是是DD的逆阵的逆阵讨讨论论:牛牛顿顿法法比比梯梯度度法法收收敛敛的的更更快快,但但是是DD的的计计算算量量大大并并 且要计算且要计算DD-1-1。当。当DD为奇异时,无法用牛顿法。为奇异时,无
10、法用牛顿法。第9页/共49页2023/4/17二、感知器法二、感知器法二、感知器法二、感知器法感知器的原理结构为:第10页/共49页2023/4/17通过对通过对WW的调整,可实现判别函数的调整,可实现判别函数g(x)=Wg(x)=WT TX RX RT T 其中其中R RT T为响应阈值为响应阈值定义感知准则函数:只考虑错分样本定义感知准则函数:只考虑错分样本定义:定义:其中其中x x0 0为错分样本为错分样本当分类发生错误时就有当分类发生错误时就有WWT TX 0X 0,X 0,所以所以J(W)J(W)总是正值,错误分类愈少,总是正值,错误分类愈少,J(W)J(W)就愈小。就愈小。理想情况
11、为理想情况为 即求最小值的问题。即求最小值的问题。第11页/共49页2023/4/17求最小值对求最小值对WW求梯度求梯度代入迭代公式中代入迭代公式中WWk+1 k+1=W=Wk k-k kJ J 由由J(W)J(W)经第经第K+1K+1次迭代的时候,次迭代的时候,J(W)J(W)趋于趋于0 0,收敛于所求的,收敛于所求的WW值值第12页/共49页2023/4/17WW的训练过程:的训练过程:例如例如:x:x1 1,x,x2,2,x x3 3 1 1 作作 x x1 1,x,x3 3的垂直线可得解区的垂直线可得解区(如图如图)假设假设起始权向量起始权向量w w1 1=0=0 k k=1=1 1
12、.x 1.x1 1,x,x2,2,x x3 3三个矢量相加得矢量三个矢量相加得矢量2,2,垂直于矢量垂直于矢量2 2的超平面的超平面HH将将x x3 3错分错分.2.x 2.x3 3与矢量与矢量2 2相加得矢量相加得矢量3,3,垂直于矢量垂直于矢量3 3的超平面的超平面HH1 1,将将x x1 1错分错分.3.3.依上法得矢量依上法得矢量4,4,垂直于矢量垂直于矢量4 4做超平面做超平面,H,H2 2将将x x3 3错分错分 4.x4.x3 3与矢量与矢量4 4相加得矢量相加得矢量5,5,矢量矢量5 5在解区内在解区内,垂直于矢量垂直于矢量5 5的超平面可以的超平面可以把把 x x1 1,x,
13、x2,2,x x3 3分成一类分成一类 。x1x2x32H3H14H25W区间第13页/共49页2023/4/17n n感知器算法:感知器算法:1.1.错误分类修正错误分类修正w wk k 如如w wk kT Tx x 0 0并且并且x x 1 1 w wk+1k+1=w=wk k-k kxx 如如w wk kT Tx x 0 0并且并且x x 2 2 w wk+1k+1=w=wk k-k kxx2.2.正确分类正确分类,w wk k不修正不修正如如w wk kT Tx x0 0并且并且x x 1 1如如w wk kT Tx x0 0并且并且x x 2 2w wk+1k+1=w=wk k+-H
14、wk+1kxwk权值修正过程第14页/共49页2023/4/17n n k k选择准则选择准则 固定增量原则固定增量原则 k k固定非负数固定非负数 绝对修正规则绝对修正规则 k k 部分修正规则部分修正规则 k k=0 022第15页/共49页2023/4/17例题:有两类样本例题:有两类样本 1 1=(x x1 1,x,x2 2)=(1,0,1),(0,1,1)=(1,0,1),(0,1,1)2 2=(x x3 3,x,x4 4)=(1,1,0),(0,1,0)=(1,1,0),(0,1,0)解:先求四个样本的增值模式解:先求四个样本的增值模式 x x1 1=(1,0,1,1)x=(1,0
15、,1,1)x2 2=(0,1,1,1)=(0,1,1,1)x x3 3=(1,1,0,1)x=(1,1,0,1)x4 4=(0,1,0,1)=(0,1,0,1)假设初始权向量假设初始权向量 w w1 1=(1,1,1,1)=(1,1,1,1)k k=1=1第一次迭代:第一次迭代:w w1 1T Tx x1 1=(1,1,1,1)(1,0,1,1)=(1,1,1,1)(1,0,1,1)T T=30 =30 所以不修正所以不修正 w w1 1T Tx x2 2=(1,1,1,1)(0,1,1,1)=(1,1,1,1)(0,1,1,1)T T=30 =30 所以不修正所以不修正 w w1 1T Tx
16、 x3 3=(1,1,1,1)(1,1,0,1)=(1,1,1,1)(1,1,0,1)T T=30 =30 所以修正所以修正w w1 1 w w2 2=w=w1 1-x-x3 3=(0,0,1,0)=(0,0,1,0)w w2 2T Tx x4 4=(0,0,1,0)=(0,0,1,0)T T(0,1,0,1)=0 (0,1,0,1)=0 所以修正所以修正w w2 2 w w3 3=w=w2 2-x-x4 4=(0,-1,1,-1)=(0,-1,1,-1)第一次迭代后第一次迭代后,权向量权向量w w3 3=(0,-1,1,-1),=(0,-1,1,-1),再进行第再进行第2,3,2,3,次迭代
17、次迭代如下表如下表第16页/共49页2023/4/17 直到在一个迭代过程中权向量相同,训练结束。直到在一个迭代过程中权向量相同,训练结束。w w6 6=w=(0,1,3,0)=w=(0,1,3,0)判别函数判别函数g(x)=-xg(x)=-x2 2+3x+3x3 3n n感知器算法只对线性可分样本有收敛的解感知器算法只对线性可分样本有收敛的解,对非线性可对非线性可分样本集会造成训练过程的振荡分样本集会造成训练过程的振荡,这是它的缺点这是它的缺点.训练样本训练样本wkTx修正式修正式修正后的权值修正后的权值wk1迭代次数迭代次数x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4
18、0 1 0 1+0w1w1w1-x3w2-x41 1 1 11 1 1 10 0 1 00 1 1 -1 1x1 1 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
19、 3 04第17页/共49页2023/4/17线性不可分样本集的分类解线性不可分样本集的分类解线性不可分样本集的分类解线性不可分样本集的分类解(取近似解取近似解取近似解取近似解)对于线性可分的样本集,可以用上述方法解到正确分对于线性可分的样本集,可以用上述方法解到正确分类的权向量。当样本集线性不可分时,用上述方法求权类的权向量。当样本集线性不可分时,用上述方法求权值时算法不收敛。如果我们把循环的权向量取平均值作值时算法不收敛。如果我们把循环的权向量取平均值作为待求的权向量,或就取其中之一为权向量,一般可以为待求的权向量,或就取其中之一为权向量,一般可以解到较满意的近似结果。解到较满意的近似结果
20、。例:在样本例:在样本 1 1:X X1 1=(0,20,2)X X3 3=(2,02,0)X X5 5=(-1,-1-1,-1)2 2:X X2 2=(1,11,1)X X4 4=(0,-20,-2)X X6 6=(-2,0-2,0)求权向量的近似解求权向量的近似解x2x1x6x1x32x52x4x211H第18页/共49页2023/4/17解:此为线性不可分问题,利用感知器法求权向量解:此为线性不可分问题,利用感知器法求权向量权向量产生循环权向量产生循环(-1,2,0),(0,2,2),(-1,1,1),(-1,1,1)(-1,2,0),(0,2,2),(-1,1,1),(-1,1,1)(
21、-1,1,1),(0,0,0),(-1,2,0)(-1,1,1),(0,0,0),(-1,2,0)因此算法不收敛,我们可以取循环中任一权值,例如取因此算法不收敛,我们可以取循环中任一权值,例如取W=(0,2,2)W=(0,2,2)T T则判别函数为:则判别函数为:g(x)=2xg(x)=2x1 1+2x+2x2 2判别面方程为:判别面方程为:g(x)=2xg(x)=2x1 1+2x+2x2 20 0 所以所以x x1 1+x+x2 20 0由图看出判别面由图看出判别面HH把二类分开,但其中把二类分开,但其中x x2 2错分到错分到 1 1类,类,而而x x1 1错分到错分到 2 2类,但大部分
22、分类还是正确的。类,但大部分分类还是正确的。第19页/共49页2023/4/17n n作业:已知四个训练样本作业:已知四个训练样本 w w1 1=(0,0),(0,1)=(0,0),(0,1)w w2 2=(1,0),(1,1)=(1,0),(1,1)使用感知器固定增量法求判别函数使用感知器固定增量法求判别函数设设w w1 1=(1,1,1,1)=(1,1,1,1)k k=1=1要求编写程序上机运行,写出判别函数,并打出图表。要求编写程序上机运行,写出判别函数,并打出图表。第20页/共49页2023/4/17三、最小平方误差准则三、最小平方误差准则三、最小平方误差准则三、最小平方误差准则(MS
23、E(MSE法法法法)-)-非迭代法非迭代法非迭代法非迭代法前前面面我我们们研研究究了了线线性性不不等等式式方方程程组组g(x)g(x)=W=WT TX0X0的的解解法法。它们共同点是企图找一个权向量它们共同点是企图找一个权向量WW,使错分样本最小。,使错分样本最小。现在我们把不等式组变成如下形式:现在我们把不等式组变成如下形式:WWT TX Xi i=b=bi i00 则有联立方程则有联立方程XW=b XW=b 这是矛盾方程组,方程数大于未知这是矛盾方程组,方程数大于未知数,所以没有精确解的存在。数,所以没有精确解的存在。每个样本有n个特征第21页/共49页2023/4/17定义误差向量:定义
24、误差向量:e=XW-be=XW-b 0 0 把平方误差作为目标函数把平方误差作为目标函数 WW的优化就是使的优化就是使J(W)J(W)最小。最小。求求J(W)J(W)的梯度并为的梯度并为0 0。解上方程得解上方程得 X XT TXW=XXW=XT Tb b这样把求解这样把求解XW=bXW=b的问题,转化为对的问题,转化为对X XT TXW=XXW=XT Tb b求解,这求解,这一有名的方程最大好处是因一有名的方程最大好处是因X XT TX X是方阵且通常是非奇异的,是方阵且通常是非奇异的,所以可以得到所以可以得到WW的唯一解。的唯一解。MSE准则函数第22页/共49页2023/4/17只要计算
25、出只要计算出X+X+就可以得到就可以得到WW取:取:最小平方误差法同最小平方误差法同FisherFisher法是一致的。法是一致的。(MSE解)其中N/N1有N1个,N/N2有N2个第23页/共49页2023/4/17 四、韦四、韦四、韦四、韦霍氏法(霍氏法(霍氏法(霍氏法(LMSLMS法)迭代法法)迭代法法)迭代法法)迭代法上节得到上节得到MSEMSE法的法的WW解为:解为:W=XW=X+b b在计算在计算X X+时,时,1 1 要求要求X XT TX X矩阵为非奇异矩阵为非奇异 2 2 由于计算量太大而引入比较大误差由于计算量太大而引入比较大误差 所以要用迭代法来求所以要用迭代法来求求求J
26、(W)J(W)的梯度的梯度J(W)=2XJ(W)=2XT T(XW-b)(XW-b)代入迭代公式代入迭代公式WW1 1任意设定任意设定 WWk+1 k+1=W=Wk k-k kX XT T(XW(XWk k-b)-b)此法可收敛于此法可收敛于WW值。值。WW满足满足:X XT T(XW-b)=0(XW-b)=0计算量很大第24页/共49页2023/4/17因此下降算法不论因此下降算法不论X XT TX X是否奇异,总能产生一个解。是否奇异,总能产生一个解。若训练样本无限的重复出现,则简化为若训练样本无限的重复出现,则简化为 WW1 1任意任意任意任意 WWk+1k+1=W=Wk k+k k(b
27、(bk k-W-Wk kT TX Xk k)X)Xk k k k随迭代次数随迭代次数k k而减少,以保证算法收敛于满意而减少,以保证算法收敛于满意的的WW值值第25页/共49页2023/4/17五、何五、何五、何五、何卡氏法卡氏法卡氏法卡氏法 (判断迭代过程中是否线性可分判断迭代过程中是否线性可分判断迭代过程中是否线性可分判断迭代过程中是否线性可分)若训练样本线性可分时,感知器法可求出界面,但对不可分问题不若训练样本线性可分时,感知器法可求出界面,但对不可分问题不收敛只能取平均。最小平方误差法不论样本是否线性可分都能给出收敛只能取平均。最小平方误差法不论样本是否线性可分都能给出一加权矢量,但不
28、能保证此矢量就是分界矢量,下面介绍一种方法一加权矢量,但不能保证此矢量就是分界矢量,下面介绍一种方法可以检测迭代过程中是否线性可分。可以检测迭代过程中是否线性可分。n n因最小平方误差法的因最小平方误差法的J(W)J(W)的解为的解为n n因为因为XW=b bXW=b b应应为正值为正值n nc c为矫正系数为矫正系数 当(当(XWXWk k-b-bk k)0 0 时时 当(当(XWXWk k-b-bk k)0 0 时时第26页/共49页2023/4/17n n引入误差矢量引入误差矢量e ek k e ek k=XW=XWk k-b-bk k判断是否线性可分判断是否线性可分n n所以所以J(W
29、)J(W)的解为的解为初始条件初始条件 WW1 1=X=X+b b1 1并且并且b b1 100n n迭代时检测迭代时检测如果如果e ek k 0 0时,时,XWXW bb,系统线性可分,迭代收敛,系统线性可分,迭代收敛如果如果e ek k00时,时,XWXW bb,系统线性不可分,迭代不收敛,系统线性不可分,迭代不收敛n n我们用下面的例子来说明我们用下面的例子来说明e ek k的作用的作用因此上式可以写成第27页/共49页2023/4/17n n例题:例题:1 1=(0,0)=(0,0)T T,(0,1),(0,1)T T 2 2=(1,0)=(1,0)T T,(1,1),(1,1)T T
30、 n n解:正规化解:正规化对对 2 2取负,有取负,有 X的规范矩阵为x2x1x1x2x3x4第28页/共49页2023/4/17取取b b1 1=(1,1,1,1)=(1,1,1,1)T T c=1 Wc=1 W1 1=X=X+b b1 1=(-2,0,1)=(-2,0,1)T T 所以所以WW1 1为所求解为所求解 e e1 1=XW=XW1 1-b-b1 1=0 =0 系统线性可分系统线性可分因为第29页/共49页2023/4/17 若四个样本变成:若四个样本变成:1 1=(0,0)=(0,0)T T,(1,1),(1,1)T T 2 2=(0,1)=(0,1)T T,(1,0),(1
31、,0)T T 解:解:取取b b1 1=(1,1,1,1)=(1,1,1,1)T T c=1c=1 W W1 1=X=X+b b1 1=(0,0,0)=(0,0,0)T T e e1 1=XW=XW1 1-b-b1 1=(-1,-1,-1,-1)=(-1,-1,-1,-1)T T00 系统线性不可分系统线性不可分 C C为校正系数为校正系数,取取0 0 C1C1在算法进行过程中,应在每一次迭代时,检测在算法进行过程中,应在每一次迭代时,检测e ek k 的值。的值。只要出现只要出现e ek k0 0 X 0 X 1 1 X=-W X=-WT TX-WX-W0 0 0 X0 X0 X1 1 Y=
32、WY=WT TX-WX-W0 0 0 X0 X0 则则X X 1 1;Y=W;Y=WT TX0 XW Wi i n n(k)(k)l l x xj j i=1,2,i=1,2,MM类类 j=1,2,j=1,2,l li i子类子类i i j j 则权向量则权向量WWi i 1 1(k)(k),WWi i 2 2(k)(k),,W,Wi i li li (k)(k)不影响分类,不影响分类,所以权向量不需要修正。所以权向量不需要修正。若有某个或某若有某个或某几几个子类不满足条件即:个子类不满足条件即:存在存在WWi i n n(k)(k)使使WWj j n n(k)x(k)xj j WWi i n
33、 n(k)(k)l l x xj j i i j j 所以所以x xj j 错分类,要修改权向量。错分类,要修改权向量。设设WWi i n n(k)(k)l l x xj j=max Wmax Wi i n n(k)(k)l l x xj j n=1,2,n=1,2,l li i i i j j则修改权向量则修改权向量WWj jn n(k+1)=W(k+1)=Wj j n n(k)(k)k kx xj j 重复以上迭代重复以上迭代,直到收敛直到收敛,此法此法类似于固定增量法类似于固定增量法.第38页/共49页2023/4/17 3.3.未知子类数目时的设计方法未知子类数目时的设计方法 当每类应
34、分成的子类数也不知当每类应分成的子类数也不知 时,这是最一般情况,方法很时,这是最一般情况,方法很 多,举例如下。多,举例如下。树状分段线性分类器树状分段线性分类器:设设两类情况两类情况 1 1,2 2。如图所示如图所示 先用两类线性判别函数求先用两类线性判别函数求 出出WW1 1,超平面超平面HH1 1分成两个区分成两个区 间间,每个区间包含两类。每个区间包含两类。再利用二类分类求出再利用二类分类求出WW2 2(H(H2 2),),W W3 3(H(H3 3)。如果每个部分仍包含两类如果每个部分仍包含两类,继续上面的过程继续上面的过程。第39页/共49页2023/4/17n n关关键键是是初
35、初始始权权向向量量WW1 1的的选选择择:一一般般先先选选两两类类中中距距离离最最近近的的两两个个子子类类的的均均值值连连线线做做垂垂直直线线作作为为HH1 1(w(w1 1)初初始始值值再求最优解。再求最优解。w1Tx0w4Tx0w3Tx0w2Tx0YNYYNN1122NY1树状决策框图第40页/共49页2023/4/173-3 3-3 非线性分类器的设计非线性分类器的设计非线性分类器的设计非线性分类器的设计n n电电位位函函数数分分类类器器,用用非非线线性性判判别别函函数数区区分分线线性性不不可可分分的的类别类别n n电电位位函函数数分分类类器器:每每个个特特征征作作为为一一个个点点电电荷
36、荷,把把特特征征空空间作为能量场间作为能量场.电位分布函数有下面三种形式。电位分布函数有下面三种形式。为系数为系数 x xk k为某一特定点为某一特定点上图是这些函数在一维时的图形,第三条是振荡曲线,上图是这些函数在一维时的图形,第三条是振荡曲线,只有第一周期才是可用范围。只有第一周期才是可用范围。xK(x)x321第41页/共49页2023/4/17电位函数算法的训练过程是在逐个样本输入时,逐渐积电位函数算法的训练过程是在逐个样本输入时,逐渐积累电位的过程,对于二类问题,经过若干循环后,如积累电位的过程,对于二类问题,经过若干循环后,如积累电位方程的运算结果能以正、负来区分二类样本,则累电位
37、方程的运算结果能以正、负来区分二类样本,则训练就可结束。训练就可结束。算法算法:设初始电位为设初始电位为K K0 0(x)=0(x)=01.1.输入样本输入样本x x1 1计算积累电位计算积累电位K K1 1(x)(x)若若x x 1 1 K K1 1(x)=K(x)=K0 0(x)+K(xx(x)+K(xx1 1)若若x x 2 2 K K1 1(x)=K(x)=K0 0(x)-K(xx(x)-K(xx1 1)设设 1 1为正电荷为正电荷,2 2为负电荷为负电荷 在在K K0 0(x)=0(x)=0时时 若若x x1 1 1 1 K K1 1(x)=K(xx(x)=K(xx1 1)若若x x
38、1 1 2 2 K K1 1(x)=-K(xx(x)=-K(xx1 1)第42页/共49页2023/4/172.2.输入样本输入样本x x2 2计算积累电荷有以下几种情况计算积累电荷有以下几种情况 a.a.若若x x2 2 1 1 并且并且K K1 1(x(x2 2)0)0 若若x x2 2 2 2 并且并且K K1 1(x(x2 2)0)0)0或或x xk+1k+1 2 2 并且并且K Kk k(x(xk+1k+1)0)0)0时时 r rk+1k+1=0=0 x xk+1k+1 1 1并且并且K Kk k(x(xk+1k+1)0 0时时 r rk+1k+1=1=1 x xk+1k+1 2 2
39、并且并且K Kk k(x(xk+1k+1)0)0 )0 不修正不修正 K K2 2(x)=K(x)=K1 1(x)=exp-(x(x)=exp-(x1 12 2+x+x2 22 2)输入输入x x3 3=(1,1)=(1,1)T T x x3 3 2 2代入代入 K K2 2(x(x3 3)=exp-(1)=exp-(12 2+1+12 2)0 )0 所以需要修正所以需要修正 K K3 3(x)=K(x)=K2 2(x)-K(xx(x)-K(xx3 3)=exp-(x)=exp-(x1 12 2+x+x2 22 2)-exp-(x -exp-(x1 1-1)-1)2 2+(x+(x2 2-1)
40、-1)2 2第45页/共49页2023/4/17 输入输入x x4 4=(1,-1)=(1,-1)T T x x3 3 2 2代入代入K K3 3(x(x4 4)=e)=e-2-2-e-e-4-40 0 所以需要修正所以需要修正K K4 4(x)=K(x)=K3 3(x)-K(xx(x)-K(xx4 4)=exp-(x =exp-(x1 12 2+x+x2 22 2)-exp-(x)-exp-(x1 1-1)-1)2 2+(x+(x2 2-1)-1)2 2 -exp-(x -exp-(x1 1-1)-1)2 2+(x+(x2 2+1)+1)2 2 n n第二次迭代第二次迭代 输入输入x x5
41、5=x=x1 1=(0,-0)=(0,-0)T T x x5 5 1 1代入代入K K4 4(x(x5 5)=1-e)=1-e-2-2-e-e-4-40 0 K K5 5(x)=K(x)=K4 4(x)(x)输入输入x x6 6=x=x2 2=(2,0)=(2,0)T T x x6 6 1 1代入代入 K K5 5(x(x6 6)=e)=e-4-4-e-e-2-2-e-e-2-2=0 =0 所以需要修正所以需要修正 K K6 6(x)=K(x)=K5 5(x)+K(xx(x)+K(xx6 6)=exp-(x =exp-(x1 12 2+x+x2 22 2)-exp-(x)-exp-(x1 1-
42、1)-1)2 2+(x+(x2 2-1)-1)2 2 -exp-(x -exp-(x1 1-1)-1)2 2+(x+(x2 2+1)+1)2 2+-exp-(x+-exp-(x1 1-2)-2)2 2+x+x2 22 2第46页/共49页2023/4/17 输入输入x x7 7=x=x3 3=(1,1)=(1,1)T T x x7 7 2 2代入代入 K K6 6(x(x7 7)=e)=e-2-2-e e0 0 -e-e-4-4+e+e-2-20 0 所以不需要修正所以不需要修正 K K7 7(x)=K(x)=K6 6(x)(x)输入输入x x8 8=x=x4 4=(1,-1)=(1,-1)T
43、 T x x8 8 2 2代入代入 K K7 7(x(x8 8)=e)=e-2-2-e-e-2-2-e e0 0 +e+e-2-20 0 0 所以不需要修正所以不需要修正 K K9 9(x)=K(x)=K8 8(x)(x)g(x)0g(x)0g(x)0第47页/共49页2023/4/17同理得到同理得到:K:K1010(x)=K(x)=K9 9(x)=K(x)=K8 8(x)=K(x)=K7 7(x)=K(x)=K6 6(x),(x),经一个完经一个完整的循环可得整的循环可得判别函数为:判别函数为:g(x)=exp-(xg(x)=exp-(x1 12 2+x+x2 22 2)-exp-(x)-exp-(x1 1-1)-1)2 2+(x+(x2 2-1)-1)2 2 -exp-(x -exp-(x1 1-1)-1)2 2+(x+(x2 2+1)+1)2 2+exp-(x+exp-(x1 1-2)-2)2 2+x+x2 22 2 上边的非线性判别函数形成的边界如图所示。虽然它上边的非线性判别函数形成的边界如图所示。虽然它可以把线性不可分的样本分开,但当样本很多时,使方可以把线性不可分的样本分开,但当样本很多时,使方程的项数太多,增大计算量。程的项数太多,增大计算量。第48页/共49页
限制150内