第3章 判別函數(shù)及幾何分類(lèi)法

1、第第3章章 判別函數(shù)及幾何分類(lèi)法判別函數(shù)及幾何分類(lèi)法3.1 判別函數(shù)判別函數(shù)3.2 線性判別函數(shù)線性判別函數(shù)3.3 廣義線性判別函數(shù)廣義線性判別函數(shù)3.4 線性判別函數(shù)的幾何性質(zhì)線性判別函數(shù)的幾何性質(zhì)3.5 感知器算法感知器算法3.6 梯度法梯度法3.7 最小平方誤差算法最小平方誤差算法3.8 非線性判別函數(shù)非線性判別函數(shù)3.1 判別函數(shù)判別函數(shù)聚類(lèi)分析法（第七章）判決函數(shù)法幾何分類(lèi)法確定性事件分類(lèi)（第三章）概率分類(lèi)法隨機(jī)事件分類(lèi)（第二章）線性判決函數(shù)法統(tǒng) 計(jì) 決 策 方 法非線性判決函數(shù)法復(fù)習(xí)與引申：復(fù)習(xí)與引申：模式識(shí)別統(tǒng)計(jì)若分屬于1，2的兩類(lèi)模式可用一方程d(x) =0來(lái)劃分，那么稱(chēng)d(x

2、) 為判別函數(shù)，或稱(chēng)判決函數(shù)、決策函數(shù)。3.1 判別函數(shù)判別函數(shù)(discriminant function) 直接用來(lái)對(duì)模式進(jìn)行分類(lèi)的準(zhǔn)則函數(shù)。例：一個(gè)二維的兩類(lèi)判別問(wèn)題，模式分布如圖示，這些分屬于1，2兩類(lèi)的模式可用一直線方程 d(x)=0來(lái)劃分。0)(32211wxwxwd x21,xx為坐標(biāo)變量，321,www為方程參數(shù)。式中：圖3.2 兩類(lèi)二維模式的分布1判別函數(shù)的定義判別函數(shù)的定義若 ，則若 ，則 類(lèi)；若 ，則 類(lèi)；0)(xd1x0)(xd2x0)(xd21xx或 或拒絕將某一未知模式 x 代入：維數(shù)=3時(shí)：判別邊界為一平面。維數(shù)3時(shí)：判別邊界為一超平面。32211)(wxwxwd

3、x d(x) 表示的是一種分類(lèi)的標(biāo)準(zhǔn)，它可以是1、2、3維的，也可以是更高維的。 判別界面的正負(fù)側(cè)，是在訓(xùn)練判別函數(shù)的權(quán)值時(shí)確定的。2判別函數(shù)正負(fù)值的確定判別函數(shù)正負(fù)值的確定圖3.3 判別函數(shù)正負(fù)的確定1）判決函數(shù)d(x)的幾何性質(zhì)。它可以是線性的或非線性的函 數(shù)，維數(shù)在特征提取時(shí)已經(jīng)確定。如：已知三維線性分類(lèi) 判決函數(shù)的性質(zhì)就確定了判決函數(shù) 的形式：4332211)(wxwxwxwdx3. 確定判別函數(shù)的兩個(gè)因素確定判別函數(shù)的兩個(gè)因素例：非線性判決函數(shù)2）判決函數(shù)d(x)的系數(shù)。用所給的模式樣本確定。3.2 線性判別函數(shù)線性判別函數(shù)3.2.1 線性判別函數(shù)的一般形式線性判別函數(shù)的一般形式將二

4、維模式推廣到n維，線性判別函數(shù)的一般形式為：t1 122nn00 dw xw xw xwwxw x (3-2)t21,.,nxxxx式中：1 122nn012t120 11nndw xw xw xwxxwwwwxl lmxw xt120,.,nwwwwwt211 ,.,nxxxx增廣向量的形式：式中：為增廣權(quán)向量，為增廣模式向量。t12,.,nw www權(quán)向量3.2.2 線性判別函數(shù)的性質(zhì)線性判別函數(shù)的性質(zhì)21t, 0, 0)(xxxwx若若d1. 兩類(lèi)情況d(x) = 0：不可判別情況，可以或拒絕或21xx） 對(duì)m個(gè)線性可分模式類(lèi)，1， 2， m，有三種劃分方式：2. 多類(lèi)情況 ii兩分法j

5、i兩分法ji兩分法特例ii兩分法(1)多類(lèi)情況1： 用線性判別函數(shù)將屬于i類(lèi)的模式與其余不屬于i類(lèi)的模式分開(kāi)。將某個(gè)待分類(lèi)模式 x 分別代入 m 個(gè)類(lèi)的d (x)中，若只有di(x)0，其他d(x)均0的條件超過(guò)一個(gè)，或全部的di(x)dj(x)就相當(dāng)于多類(lèi)情況2中的dij(x) 0。ji兩分法特例(3)多類(lèi)情況3： 因此對(duì)具有判別函數(shù) midii, 1,)(txwx的m類(lèi)情況，判別函數(shù)性質(zhì)為： ijimjiijddxxx若, 2 , 1,;,)(或： ikimkddxxx若, 1,max)( 識(shí)別分類(lèi)時(shí)： 判別界面需要做差值。對(duì)i類(lèi)，應(yīng)滿足： di其他所有dj2313dddd0122x1x

6、0)(21-xdxd- 0)(31-xdxd 0)(32-xdxd3212dddd3121dddd3 除邊界區(qū)外，沒(méi)有不確定區(qū)域。特點(diǎn)： 是第二種情況的特例。由于dij(x)= di (x) dj(x) ，若在第三種情況下可分，則在第二種情況下也可分，但反過(guò)來(lái)不一定。2313dddd0122x1x 0)(21-xdxd- 0)(31-xdxd 0)(32-xdxd3212dddd3121dddd3 把 m 類(lèi)情況分成了(m -1)個(gè)兩類(lèi)問(wèn)題。并且 類(lèi)的判別界面全部與 類(lèi)的判別界面相鄰（向無(wú)窮遠(yuǎn)處延伸的區(qū)域除外）。iijj特別的定義23212211)(1)()(xdxxdxxd-xxx例例3.5

7、 一個(gè)三類(lèi)模式（m=3）分類(lèi)器，其判決函數(shù)為： 試判斷x0=1,1t屬于哪一類(lèi)，且分別給出三類(lèi)的判決界面。解： 2003020102030201)()()()(1)(1111)(011)(-xxxxxxxxddddddd012)()(121-xddxx02)()(2131-xxddxx012)()(112-xddxx012)()(2132-xxddxx)()(1331xxdd-)()(2332xxdd-類(lèi)的判決函數(shù)：1判決界面如圖所示。類(lèi)的判決函數(shù)：2類(lèi)的判決函數(shù)：3- 0)(21-xdxd2313dddd0.5x2- 0)(31-xdxd 0)(32-xdxd3212dddd3121dddd

8、110.5123x1-o2x1x 0)(21-xxdd- 0)(31-xxdd 0)(32-xxdd例例3.6 已知判決界面的位置和正負(fù)側(cè)，分析三類(lèi)模式的分布 區(qū)域 。132(1) 明確概念：線性可分。 一旦線性判別函數(shù)的系數(shù)wk被確定以后，這些函數(shù)就可以作為模式分類(lèi)的基礎(chǔ)。3. 小結(jié)小結(jié)(2) 分法的比較：jiii與 對(duì)于m類(lèi)模式的分類(lèi)， 兩分法共需要m個(gè)判別函數(shù)，但 兩分法需要m(m-1)/2個(gè)。當(dāng)時(shí)m3時(shí)，后者需要更多個(gè)判別式（缺點(diǎn)），但對(duì)模式的線性可分的可能性要更大一些（優(yōu)點(diǎn)）。 jiii原因： 一種類(lèi)別模式的分布要比m-1類(lèi)模式的分布更為聚集， 分法受到的限制條件少，故線性可分的可能

9、性大。jiii兩分法 全部不屬任何類(lèi) ir，可能 屬于1或3 1230)(2xd0)(3xdir，可能 屬于3或2 -0)(1xd0, 0312ddd0, 0321ddd0, 0,321dddir，可能屬于1或2 0, 0213ddd2x1x若只有di(x)0，其他d(x)均 0時(shí)，原點(diǎn)在超平面的正側(cè)；wn+1 tik xw()=1+kw( )ickxw+( )kw( )0tik xw若( )0tik xw若（3）分析分類(lèi)結(jié)果：只要有一個(gè)錯(cuò)誤分類(lèi)，回到（2），直至 對(duì)所有樣本正確分類(lèi)。 分類(lèi)正確時(shí)，對(duì)權(quán)向量“賞”這里用“不罰”，即權(quán)向量不變；分類(lèi)錯(cuò)誤時(shí)，對(duì)權(quán)向量“罰”對(duì)其修改，向正確的方向轉(zhuǎn)換

10、。感知器算法是一種賞罰過(guò)程：感知器算法是一種賞罰過(guò)程：3. 收斂性收斂性收斂性：經(jīng)過(guò)算法的有限次迭代運(yùn)算后，求出了一個(gè)使所有樣本都能正確分類(lèi)的w，則稱(chēng)算法是收斂的?？梢宰C明感知器算法是收斂的。收斂條件：模式類(lèi)別線性可分。 例例3.8 已知兩類(lèi)訓(xùn)練樣本解：所有樣本寫(xiě)成增廣向量形式； 進(jìn)行規(guī)范化處理，屬于2的樣本乘以(1)。t11 , 0 , 0xt21 , 1 , 0xt31, 0 , 1 -xt41, 1, 1-x用感知器算法求出將模式分為兩類(lèi)的權(quán)向量解和判別函數(shù)。 :1t10,0x:2t21 ,0xt30, 1xt41 , 1x任取w(1)=0，取c=1，迭代過(guò)程為：第一輪： 0,1000

11、, 0 , 0) 1 (1txwt11 , 0 , 0) 1 () 2(, 0xww故1,1101 , 0 , 0)2(2txwt1 , 0 , 0) 2() 3 (, 0ww故-1,1-01-1 , 0 , 0)3(3txwt30 , 0 , 1-) 3 () 4(, 0xww故1,1-1-1-0 , 0 , 1-)4(4txwt0 , 0 , 1-) 4() 5 (, 0ww故有兩個(gè)wt(k)xi 0的情況（錯(cuò)判），進(jìn)行第二輪迭代。t11t1 , 0 , 1-)5()6(,00)5(xwwxw故t2t1 , 0 , 1-(6)7(,01)6(wwxw故t33t0 , 0 , 2-)7()8

12、(,00)7(xwwxw故t4t0 , 0 , 2-)8()9(,02)8(wwxw故第二輪：t11t1 , 0 , 2-)9()10(,00)9(xwwxw故(10)11(,01)10(2twwxw故)11()12(,01)11(3twwxw故)12()13(,01)12(4twwxw故第三輪：)13()14(,01)13(1twwxw故(14)15(,01)14(2twwxw故)15()16(,01)15(3twwxw故)16()17(,01)16(4twwxw故第四輪：t1 , 0 , 2-w該輪迭代的分類(lèi)結(jié)果全部正確，故解向量1+2=)(1xd x相應(yīng)的判別函數(shù)為： 當(dāng)c、w(1)取其

13、他值時(shí)，結(jié)果可能不一樣，所以感知器算法的解不是單值的。判別界面d(x)=0如圖示。采用多類(lèi)情況3的方法時(shí)，應(yīng)有：4. 感知器算法用于多類(lèi)情況感知器算法用于多類(lèi)情況mj, 1= ix ,)(ijddjixx若，則 midi, 1,對(duì)于m類(lèi)模式應(yīng)存在m個(gè)判決函數(shù)：算法主要內(nèi)容：m,21設(shè)有 m 種模式類(lèi)別： mjj, 1,1w設(shè)其權(quán)向量初值為： 第k次迭代時(shí)，一個(gè)屬于i類(lèi)的模式樣本 x 被送入分類(lèi)器，計(jì)算所有判別函數(shù)訓(xùn)練樣本為增廣向量形式，但不需要規(guī)范化處理不需要規(guī)范化處理。 分二種情況修改權(quán)向量： mjkkdjj, 1,txw 若第l個(gè)權(quán)向量使 ，則相應(yīng)的權(quán)向量作調(diào)整，即： -lijkkckkc

14、kkjjllii,111wwxwwxww 可以證明：只要模式類(lèi)在情況3判別函數(shù)時(shí)是可分的，則經(jīng)過(guò)有限次迭代后算法收斂。， c為正的校正增量例例3.9 設(shè)有三個(gè)線性可分的模式類(lèi)，三類(lèi)的訓(xùn)練樣本分別為 若 則權(quán)向量不變； mjijkdkdji, 2 , 1;, mjkkjj, 2 , 1,1ww( )( )kdkdli t33t22t111 , 11 , 10 , 0-xxx：；：；：現(xiàn)采用多類(lèi)情況3的方式分類(lèi)，試用感知器算法求出判別函數(shù)。 解：增廣向量形式：t3t2t11,1, 1,1,1, 1,1 , 0 , 0-xxx注意，這里任一類(lèi)的樣本都不能乘以（1）。任取初始權(quán)向量t3210 , 0

15、, 0) 1 () 1 () 1 (www；c=1 第一次迭代： 0111t11xwd 0111t22xwd 0111t33xwd三個(gè)權(quán)向量都需要修改：11x 1121dd 1131dd，但且不成立，t1111 , 0 , 0) 1 ()2(xwwt1221, 0 , 0) 1 ()2(-xwwt1331, 0 , 0) 1 ()2(-xww第二次迭代： 1222t11xwd 1222t22-xwd 1222t33-xwd22x 2212dd 2232dd，但且不成立，修改權(quán)向量：t2110 , 1, 1)2() 3(-xwwt2220 , 1 , 1)2() 3(xwwt2332, 1, 1

16、)2()3(-xww第三次迭代： 修改為權(quán)向量。33x 3313dd 3323dd，但且不成立， 以上進(jìn)行的一輪迭代運(yùn)算中，三個(gè)樣本都未正確分類(lèi)，進(jìn)行下一輪迭代。第四次迭代： 在第五、六、七迭代中，對(duì)所有三個(gè)樣本都已正確分類(lèi)。權(quán)向量的解：t11110 , 2, 0)5()6()7(-wwwwt22222, 0 , 2)5()6()7(-wwwwt33332, 0 , 2)5()6()7(-wwww判別函數(shù)：212)(xd-x22)(12-xdx22)(13-xdx 設(shè)函數(shù)f (y)是向量 的函數(shù)，則f (y)的梯度定義為：3.6 梯度法梯度法t21,nyyyy t21,ddnyfyfyfffy

17、yy梯度的方向方向是函數(shù) f (y) 在y點(diǎn)增長(zhǎng)最快的方向，梯度的模模是f (y)在增長(zhǎng)最快的方向上的增長(zhǎng)率 (增長(zhǎng)率最大值)。1. 梯度概念梯度概念 梯度向量的最重要性質(zhì)之一：指出函數(shù)梯度向量的最重要性質(zhì)之一：指出函數(shù) f 在其自變量增加在其自變量增加時(shí)，增長(zhǎng)最快的方向。時(shí)，增長(zhǎng)最快的方向。3.6.1 梯度法基本原理梯度法基本原理顯然：負(fù)梯度指出了最陡下降方向。梯度算法的依據(jù)。即：2. 梯度算法梯度算法 設(shè)兩個(gè)線性可分的模式類(lèi)1和2的樣本共n個(gè)，2類(lèi)樣本乘(-1)。將兩類(lèi)樣本分開(kāi)的判決函數(shù)d(x)應(yīng)滿足： 梯度算法的目的仍然是求一個(gè)滿足上述條件的權(quán)向量，主導(dǎo)思想是將聯(lián)立不等式求解w的問(wèn)題，轉(zhuǎn)

18、換成求準(zhǔn)則函數(shù)極小值的問(wèn)題。nidii, 2 , 10)(txwxn個(gè)不等式 準(zhǔn)則函數(shù)的選取原則： 具有唯一的最小值，并且這個(gè)最小值發(fā)生在w txi0時(shí)。 用負(fù)梯度向量的值對(duì)權(quán)向量w進(jìn)行修正，實(shí)現(xiàn)使準(zhǔn)則函數(shù)達(dá)到極小值的目的。 基本思路： 定義一個(gè)對(duì)錯(cuò)誤分類(lèi)敏感的準(zhǔn)則函數(shù)j(w, x)，在j的梯度方向上對(duì)權(quán)向量進(jìn)行修改。一般關(guān)系表示成從w(k)導(dǎo)出w(k+1)：其中c是正的比例因子。 梯度法求解步驟： jckjckk-www)(1 kjckkwwwxwww-,1（1）將樣本寫(xiě)成規(guī)范化增廣向量形式，選擇準(zhǔn)則函數(shù)，設(shè)置初始權(quán)向量w(1)，括號(hào)內(nèi)為迭代次數(shù)k=1。 權(quán)向量修正為：)(,)(kijkjw

19、wwxw )(1kjckk-ww迭代次數(shù)k加1，輸入下一個(gè)訓(xùn)練樣本，計(jì)算新的權(quán)向量，直至對(duì)全部訓(xùn)練樣本完成一輪迭代。 （3）在一輪迭代中，如果有一個(gè)樣本使 ，回到(2)進(jìn)行下 一輪迭代。否則， w不再變化，算法收斂。0j（2）依次輸入訓(xùn)練樣本x。設(shè)第k次迭代時(shí)輸入樣本為xi，此時(shí) 已有權(quán)向量w(k)，求 ：)(kj例例3.10 選擇準(zhǔn)則函數(shù) ， ，簡(jiǎn)單地考慮x為一維增廣模式的情況x=1，此時(shí)w=w，兩者均為標(biāo)量，xwxwxwtt),(-jwwj-),(xw錯(cuò)誤分類(lèi)時(shí)： 22,1-wwwwwjjxxww0010twwxw ckckk221-www， 對(duì)權(quán)向量校正。 jckk-ww1正確分類(lèi)時(shí)：0

20、010twwxw0-wwwj kckkwww-01， 對(duì)權(quán)向量不做修正。說(shuō)明： 隨著權(quán)向量w向理想值接近，準(zhǔn)則函數(shù)關(guān)于w的導(dǎo)數(shù) ( )越來(lái)越趨近于零，這意味著準(zhǔn)則函數(shù)j 越來(lái)越接近最小值。當(dāng) 最終 時(shí)，j達(dá)到最小值，此時(shí)w不再改變，算法收斂。j0j 將感知器算法中聯(lián)立不等式求解w的問(wèn)題，轉(zhuǎn)換為求函數(shù)j極小值的問(wèn)題。 kjckjckkwwwxwwww-,1 c) 梯度算法是求解權(quán)向量的一般解法，算法的具體計(jì)算形式取決于準(zhǔn)則函數(shù)j(w, x)的選擇，j(w, x)的形式不同，得到的具體算法不同。a) b) c值的選擇很重要，如c值太小，收斂太慢；但若太大，搜索又可能過(guò)頭，甚至引起發(fā)散。3.6.2

21、固定增量法固定增量法準(zhǔn)則函數(shù)：求w(k)的遞推公式：1. 求j的梯度?,wxwjj方法：函數(shù)對(duì)向量求導(dǎo)=函數(shù)對(duì)向量的分量求導(dǎo)，即t1,nxfxffx該準(zhǔn)則函數(shù)有唯一最小值“0”，且發(fā)生在 的時(shí)候。 0txw設(shè) ，t211 ,nxxxxt121,nnwwwwwxwxwxwtt21),(-j部分：niniiwxw11twwxwt111111,iniininiikniniiwxwwwxwwwxwwxt11 ,nkxxxnnddddixxxxtt 111111tnnnnxxiwxwxwt首先求另：矩陣論中有xwxwxwtt21),(-jxxwxwxw-tsgn21,jj其中 -0, 10, 1sgnt

22、ttxwxwxw若若 由的結(jié)論 有： xwxwtxwxwwxwxwttt0時(shí)，xwxwwxwxw-ttt0時(shí)，xxwwxwttsgnxwxwxwtt21),(-j kjckjckkwwwxwwww-,12. 求w(k+1)將 代入得： xxwxww-)(sgn211tkckk 0)(,0)(, 0ttxwxxwwkckk若若 xwxxw)(sgn2tkck-xxwxwxw-tsgn21,jj 由此可以看出，感知器算法是梯度法的特例。即：梯度法是將感知器算法中聯(lián)立不等式求解w的問(wèn)題，轉(zhuǎn)換為求函數(shù)j極小值的問(wèn)題，將原來(lái)有多個(gè)解的情況，變成求最優(yōu)解的情況。上式即為固定增量算法，與感知器算法形式完全相

23、同 。 0)(,0)(, 01ttxwxxwwwkckkk若若即： 0, 0,1ttiiikckkkkxwxwxwww若若只要模式類(lèi)是線性可分的，算法就會(huì)給出解。n線性分類(lèi)器設(shè)計(jì)任務(wù)：給定樣本集k，確定線性判別函數(shù)g(x)=wtx的各項(xiàng)系數(shù)w。步驟：1.抽取類(lèi)別標(biāo)志明確的樣本集合 k=x1,x2,xn作為訓(xùn)練樣本集。2.確定一準(zhǔn)則函數(shù)j(k,w)，其值反映分類(lèi)器的性能，其極值解對(duì)應(yīng)于“最好”決策。3.用最優(yōu)化技術(shù)求準(zhǔn)則函數(shù)j的極值解w*，從而確定判別函數(shù)，完成分類(lèi)器設(shè)計(jì)。*argmax (,)j kwwwn對(duì)于未知樣本x，計(jì)算g(x)，判斷其類(lèi)別4.2 fisher線性判別線性判別n線性判別函

24、數(shù)y=g(x)=wtx:n樣本向量x各分量的線性加權(quán)n樣本向量x與權(quán)向量w的向量點(diǎn)積n如果| w |=1，則視作向量x在向量w上的投影 nfisher準(zhǔn)則的基本原理：找到一個(gè)最合適的投影方向，使兩類(lèi)樣本在該方向上投影之間的距離盡可能遠(yuǎn)，而每一類(lèi)樣本的投影盡可能緊湊，從而使分類(lèi)效果為最佳。fisher線性判別線性判別圖例圖例fisher判別x1x2w1h: g=0w2fisher準(zhǔn)則的描述：用投影后數(shù)據(jù)的統(tǒng)計(jì)性質(zhì)均值和離散度的函數(shù)作為判別優(yōu)劣的標(biāo)準(zhǔn)。d維空間樣本分布的描述量維空間樣本分布的描述量fisher判別n各類(lèi)樣本均值向量mi1 1,2iix kiinmxn樣本類(lèi)內(nèi)離散度類(lèi)內(nèi)離散度矩陣si

25、與總類(lèi)內(nèi)離散度矩陣sw ()() , 1,2itiiii-xsxmxm12wsssn樣本類(lèi)間離散度類(lèi)間離散度矩陣sb：1212()()tb-smmmm離散度矩陣在形式上與協(xié)方差矩陣很相似，但協(xié)方差矩陣是一種期望值，而離散矩陣只是表示有限個(gè)樣本在空間分布的離散程度一維一維y空間樣本分布的描述量空間樣本分布的描述量n各類(lèi)樣本均值1, 1,2iiyimyinn樣本類(lèi)內(nèi)離散度和總類(lèi)內(nèi)離散度2() , 1,2iiiysymi-12wsssn樣本類(lèi)間離散度 212()bsmm-以上定義描述d維空間樣本點(diǎn)到一向量投影的分投影的分散情況散情況，因此也就是對(duì)某向量w的投影在w上的分布。樣本離散度的定義與隨機(jī)變量

26、方差相類(lèi)似 nfisher準(zhǔn)則函數(shù)定義的原則為，希望投影后，在一維空間中樣本類(lèi)別區(qū)分清晰，即兩類(lèi)距離越大越好，也就是類(lèi)間離散度越大越好；各類(lèi)樣本內(nèi)部密集，即類(lèi)內(nèi)離散度越小越好，根據(jù)上述準(zhǔn)則，構(gòu)造fisher準(zhǔn)則函數(shù)。12wsss2121212()( )bfsmmjwssss-樣本與其投影統(tǒng)計(jì)量間的關(guān)系樣本與其投影統(tǒng)計(jì)量間的關(guān)系22()()()()iiiiiyttix kttiiix ktssym-w xw mwwxmxwwm1212()ttwssssswwww2212121212()()()()tttbtbtssmm-w mw mwwmmmmwwfisher準(zhǔn)則函數(shù)準(zhǔn)則函數(shù)n評(píng)價(jià)投影方向w的原

27、則，使原樣本向量在該方向上的投影能兼顧類(lèi)間分布盡可能分開(kāi)，類(lèi)內(nèi)盡可能密集的要求nfisher準(zhǔn)則函數(shù)的定義：12( )tbbftwssjwssswwwwnfisher最佳投影方向的求解*argmax( )fjwwwfisher最佳投影方向的求解最佳投影方向的求解n采用拉格朗日乘子算法解決*112()ws-wmmm1-m2是一向量，對(duì)與(m1-m2)平行的向量投影可使兩均值點(diǎn)的距離最遠(yuǎn)。但是如從使類(lèi)間分得較開(kāi)，同時(shí)又使類(lèi)內(nèi)密集程度較高這樣一個(gè)綜合指標(biāo)來(lái)看，則需根據(jù)兩類(lèi)樣本的分布離散程度對(duì)投影方向作相應(yīng)的調(diào)整，這就體現(xiàn)在對(duì)m1-m2 向量按sw-1作一線性變換，從而使fisher準(zhǔn)則函數(shù)達(dá)到極值點(diǎn)

28、判別函數(shù)的確定n前面討論了使fisher準(zhǔn)則函數(shù)極大的d維向量w*的計(jì)算方法，判別函數(shù)中的另一項(xiàng)w0（閾值）可采用以下幾種方法確定：1202mmw1122012n mn mwmnn1212012ln()/()22ppmmwnn-0102ttywyww xxw xxn分類(lèi)規(guī)則:fisher公式的推導(dǎo)公式的推導(dǎo)12( )tbbftwssjwssswwwwc0twsww令 lagrange:( , )()ttbwlssc-wwwww定義函數(shù) ( , ):0bwlss-wwww令 1wbss-ww111212112()()()twbwwssssr-wwmmmmwmm*111212()()wwrss-w

29、mmmm*112()ws-wmm3.7 最小平方誤差算法最小平方誤差算法（least mean square error, lmse；亦稱(chēng)ho-kashyap算法） 上述的感知器算法、梯度算法、固定增量算法或其他類(lèi)似方法，只有當(dāng)模式類(lèi)可分離時(shí)才收斂，在不可分的情況下，算法會(huì)來(lái)回?cái)[動(dòng)，始終不收斂。當(dāng)一次次迭代而又不見(jiàn)收斂時(shí)，造成不收斂現(xiàn)象的原因分不清，有兩種可能：a) 迭代過(guò)程本身收斂緩慢b) 模式本身不可分對(duì)可分模式收斂。對(duì)于類(lèi)別不可分的情況也能指出來(lái)。lmse算法特點(diǎn)：1. 分類(lèi)器的不等式方程分類(lèi)器的不等式方程-nnnnnnnnnnnnnwxwxwxwwxwxwxwwxwxwxwxxx對(duì)對(duì)對(duì)

30、00012211212222211111122111類(lèi)1類(lèi)20tixw 兩類(lèi)分類(lèi)問(wèn)題的解相當(dāng)于求一組線性不等式的解。如果給出分屬于 ， 兩個(gè)模式類(lèi)的訓(xùn)練樣本集 ，應(yīng)滿足：12, 2 , 1,niix其中，xi是規(guī)范化增廣樣本向量， 。t21 1,iniiixxxx上式分開(kāi)寫(xiě)為：寫(xiě)成矩陣形式為 ： 令n (n+1) 的長(zhǎng)方矩陣為x，則 , 變?yōu)椋?tixw0xw0-11112112122221112110000111nnnnnnnnnnnnwwwwxxxxxxxxx-nnnnnnnnnnnnnwxwxwxwwxwxwxwwxwxwxwxxx對(duì)對(duì)對(duì)0001221121222221111112211

31、1類(lèi)1類(lèi)21,.inl式中：t121,nnwwwww121tt1tt2t1-nnnnixxxxxx0xw0-11112112122221112110000111nnnnnnnnnnnnwwwwxxxxxxxxx0為零向量 感知器算法是通過(guò)解不等式組 ，求出w。0xw2. lmse算法算法1) 原理原理的求解。式中： 兩式等價(jià)。t21,nibbbbb為各分量均為較小正值的矢量。lmse算法把對(duì)滿足 xw 0 的求解，改為滿足bxw 在方程組系數(shù)矩陣中當(dāng)行數(shù)列數(shù)時(shí)，通常無(wú)解，稱(chēng)為矛盾方程組，一般求近似解。在模式識(shí)別中，通常訓(xùn)練樣本數(shù)n總是大于模式的維數(shù)n，因此方程的個(gè)數(shù)(行數(shù))模式向量的維數(shù)(列數(shù)

32、)，是矛盾方程組，只能求近似解w*，即說(shuō)明：極小-bxw * lmse算法的出發(fā)點(diǎn)：選擇一個(gè)準(zhǔn)則函數(shù)，使得當(dāng)j達(dá)到最小值時(shí)，xw=b 可得到近似解（最小二乘近似解）。 lmse算法的思路：bwbxwxw、通過(guò)求準(zhǔn)則函數(shù)極小找求解對(duì)求解對(duì) 0轉(zhuǎn)化為轉(zhuǎn)化為準(zhǔn)則函數(shù)定義為： 221,bxwbxw-j“最小二乘”： 最?。菏狗匠探M兩邊誤差最小， 也即使j最小。 二乘：次數(shù)為2，乘了兩次最小平方（誤差算法）1111121111221111111111-nninnnnnnnnininnbbbwwwwxxxxxxxxbxw-nniinnnnnnninnininnnbbbbwwxwxbwwxwxbwwxwxx

33、wxwxwtt11t1111111111111向量各分量的平方和向量各分量的平方和-22bxw-niiinnbbb12t2t211t2xwxwxwbxw考察向量(xwb) 有：可以看出： 當(dāng)函數(shù)j達(dá)到最小值，等式xw=b有最優(yōu)解。即又將問(wèn)題轉(zhuǎn)化為求準(zhǔn)則函數(shù)極小值的問(wèn)題。 因?yàn)閖有兩個(gè)變量w和b，有更多的自由度供選擇求解，故可望改善算法的收斂速率。21t22121,-niiibjxwbxwbxwxw=b 的近似解也稱(chēng)“最優(yōu)近似解”： 使方程組兩邊所有誤差之和最?。醋顑?yōu)）的解。準(zhǔn)則函數(shù)：bxbxxxwbxxwxbxwx#t1tttt0-使j 對(duì)w求最小，令 ，得：2) 推導(dǎo)推導(dǎo)lmse算法遞推公

34、式算法遞推公式與問(wèn)題相關(guān)的兩個(gè)梯度： bxwxw-tjbxwbxwb-21j (3-46)(3-47)由(3-47)式可知：只要求出b，就可求出w。求遞推公式：(1) 求w 的遞推關(guān)系x為n(n+1)長(zhǎng)方陣，x#為(n+1) n 長(zhǎng)方陣。t1t#xxxx-稱(chēng)為x的偽逆，式中： (3-45)0wj(2) 求b(k+1)的迭代式 kjckkbbbbb-1 kkkkckkbxwbxwbb-21(3-46)代入，得cc 2 kkkebxw- 令，定義(3-49) kkckkeebb1(3-50)(3-46)bxwbxwb-21j利用梯度算法公式有： kjckkwwwxwww-,1 kkbbxxxxx-

35、#t1t kckckexexbx#(3) 求w(k+1)的迭代式將(3-50)代入(3-47)式w=x#b 有： kkckkkeebxbxw#11 kkkbxwxxxex-t1t#=0 kckexw#0 kkkebxw-(3-49) kkckkeebb1(3-50) 11#bxw kkkbxwe- kckkexww#1 kkckkeebb111#kkbxw總結(jié)：設(shè)初值b(1)，各分量均為正值，括號(hào)中數(shù)字代表迭代次數(shù) 。w(k+1)、b(k+1)互相獨(dú)立，先后次序無(wú)關(guān)。求出b，w后，再迭代出下一個(gè)e，從而計(jì)算出新的b， w。 11#bxw kkkbxwe- kkckkeebb1或另一算法：先算b

36、(k+1)，再算w(k+1)。3）模式類(lèi)別可分性判別）模式類(lèi)別可分性判別 如果e(k)0 ，表明xw(k)b(k) 0， 隱含有解。繼續(xù)迭代， 可使e(k) 0 。 如果e(k)0，有解。分以下幾種情況：111-kkkbxwe kkww1 kkee1 kkbb111#kkbxw情況分析： kkckkeebb1e(k)0，線性可分，若進(jìn)入(5)可使e(k) 0 ，得最優(yōu)解。如果e(k)0，線性不可分，停止迭代，無(wú)解，算法結(jié)束。如果e(k)=0，線性可分，解為w(k)，算法結(jié)束。否則，說(shuō)明e(k)的各分量值有正有負(fù)，進(jìn)入(5)。 kckkexww#1 kkckkeebb1 kkckkeebb111

37、#kkbxw(5) 計(jì)算w(k+1)和b(k+1)。方法1：分別計(jì)算方法2：先計(jì)算再計(jì)算迭代次數(shù)k加1，返回(4)。3. 算法特點(diǎn)算法特點(diǎn)(1) 算法盡管略為復(fù)雜一些，但提供了線性可分的測(cè)試特征。(2) 同時(shí)利用n個(gè)訓(xùn)練樣本，同時(shí)修改w和b，故收斂速度快。(3) 計(jì)算矩陣 復(fù)雜，但可用迭代算法計(jì)算。1t-xx例3.11 已知兩類(lèi)模式訓(xùn)練樣本： tt11 ,0,0,0:tt21 ,1,0,1:試用lmse算法求解權(quán)向量。-111101110100x解：(1) 寫(xiě)出規(guī)范化增廣樣本矩陣： aij是aij的代數(shù)余子式，注意兩者的行和列的標(biāo)號(hào)互換。 t1t#xxxx- (2) 求偽逆矩陣-4222212

38、12111101110100111110101100txx*11aaa-求逆矩陣：333231232221131211aaaaaaaaaa332313232212312111*aaaaaaaaaa若，則 |a|a的行列式a*a的伴隨矩陣422221212txx 劃去aij所在的行和列的元素，余下元素構(gòu)成的行列式做aij的余子式，記作mij ，將 叫做元素aij的代數(shù)余子式。例：代數(shù)余子式定義： ijijam ji1- 323112113231121132231-aaaaaaaaa-322240204413222402041t1txxxx44884416422221212t-xx行列式: 333

39、231232221131211aaaaaaaaaa*11aaa-1113222222224111111010110032224020441#x -1024084111111113222222224111#bxw(3) 取 和 c=1 開(kāi)始迭代： t1 , 1 , 1 , 11 b -0000111111111111102111101110100111bxwe 121-xd x解為 w(1) ，判斷函數(shù)為：t1t#xxxx-圖示如下：例3.12 已知模式訓(xùn)練樣本： ，tt11 , 1,0 ,0:tt20, 1,1 ,0:-101110111100x( 2) 求 ：t1t#xxxx-1113222

40、2222241#x解：(1) 規(guī)范化增廣樣本矩陣：(3) 取 和c=1，迭代： t1 , 1 , 1 , 11 b用lmse算法求解權(quán)向量。 t#00011bxw ttt111111110000111-bxwe e(1)全部分量為負(fù)，無(wú)解，停止迭代。為線性不可分模式。 小結(jié)：小結(jié)：(1) 感知器法、梯度法、最小平方誤差算法討論的分類(lèi)算法都是通過(guò)模式樣本來(lái)確定判別函數(shù)的系數(shù)，所以要使一個(gè)分類(lèi)器設(shè)計(jì)完善，必須采用有代表性的數(shù)據(jù)，訓(xùn)練判別函數(shù)的權(quán)系數(shù)。它們能合理反映模式數(shù)據(jù)的總體。(2) 要獲得一個(gè)有較好判別性能的線性分類(lèi)器，所需要的訓(xùn)練樣本的數(shù)目的確定。用指標(biāo)二分法能力n0來(lái)確定訓(xùn)練樣本的數(shù)目：通

41、常訓(xùn)練樣本的數(shù)目不能低于n0 ，選為 n0的510倍左右。二維：不能低于6個(gè)樣本，最好選在3060個(gè)樣本之間。三維：不能低于8個(gè)樣本，最好選在4080個(gè)樣本之間。120nnn為模式維數(shù)如3.8 非線性判別函數(shù)非線性判別函數(shù)3.8.1 分段線性判別函數(shù)分段線性判別函數(shù)線性判別函數(shù)的特點(diǎn)：形式簡(jiǎn)單，容易學(xué)習(xí)； 用于線性可分的模式類(lèi)。非線性判別函數(shù)：用于線性不可分情況。分段線性、超曲面。 特點(diǎn)基本組成為超平面。* 相對(duì)簡(jiǎn)單；* 能逼近各種形狀的超曲面。1一般分段線性判別函數(shù)一般分段線性判別函數(shù)設(shè)有m類(lèi)模式，將i類(lèi)（i=1,2, ,m）劃分為li個(gè)子類(lèi)：miiliiii, 2 , 1,:21其中第n個(gè)

42、子類(lèi)的判別函數(shù)： milndinini, 2 , 1;, 2 , 1)()(txwxi類(lèi)的判別函數(shù)定義為：, 2 , 1),(max)(iniilnddxxm類(lèi)的判決規(guī)則： , 2 , 1),(max)(middijxxjx若，則用各類(lèi)判別函數(shù)進(jìn)行分類(lèi)判決實(shí)際是用各類(lèi)選出的子類(lèi)判別函數(shù)進(jìn)行判決判別面由各子類(lèi)的判別函數(shù)決定若i類(lèi)的第n個(gè)子類(lèi)和j類(lèi)的第m個(gè)子類(lèi)相鄰，判別界面方程為：)()(xxmjnidd子類(lèi)之間的判別界面組成各類(lèi)之間的判別界面類(lèi)間判別界面分段線性2基于距離的分段線性判別函數(shù)基于距離的分段線性判別函數(shù)設(shè) 1類(lèi)均值向量：11111niinxm21221niinxm2類(lèi)均值向量：n1，

43、n2：兩類(lèi)樣本數(shù)。 任一模式x到m1和m2的歐氏距離平方：211|)(mxx-d222|)(mxx-d判決規(guī)則：)()(21xxdd1x若， 則)()(12xxdd2x若， 則判別界面方程：2221|mxmx-1）最小距離分類(lèi)器化簡(jiǎn)得：0)()(21t12t2t21-mmmmxmm x的線性方程，確定一個(gè)超平面。 最小距離分類(lèi)器 2）分段線性距離分類(lèi)器 設(shè)：m類(lèi)模式，其中i類(lèi)劃分為li個(gè)子類(lèi)，第n個(gè)子類(lèi)的均值向量為 。每個(gè)子類(lèi)的判別函數(shù)：nimmilndinini, 2 , 1;, 2 , 1,|)(2-mxx每類(lèi)的判別函數(shù)： , 2 , 1),(min)(iniilnddxx判決規(guī)則：, 2

44、 , 1),(min)(middijxx若jx則mi, 2 , 13.8.2 分段線性判別函數(shù)的學(xué)習(xí)方法分段線性判別函數(shù)的學(xué)習(xí)方法1已知子類(lèi)劃分時(shí)的學(xué)習(xí)方法已知子類(lèi)劃分時(shí)的學(xué)習(xí)方法* 每個(gè)子類(lèi)看成獨(dú)立的類(lèi)；* 在一類(lèi)范圍內(nèi)根據(jù)多類(lèi)情況3，學(xué)習(xí)各子類(lèi)判別函數(shù)；* 繼而得到各類(lèi)判別函數(shù)。 2已知子類(lèi)數(shù)目時(shí)的學(xué)習(xí)方法已知子類(lèi)數(shù)目時(shí)的學(xué)習(xí)方法 用類(lèi)似于固定增量算法的錯(cuò)誤修正算法學(xué)習(xí)分段線性判別函數(shù) 3未知子類(lèi)數(shù)目時(shí)的學(xué)習(xí)方法未知子類(lèi)數(shù)目時(shí)的學(xué)習(xí)方法樹(shù)狀分段線性分類(lèi)器 樹(shù)狀分段線性分類(lèi)器判別函數(shù)的學(xué)習(xí)及分類(lèi)過(guò)程 暫停點(diǎn)暫停點(diǎn)：，； ：，3.8.3 勢(shì)函數(shù)法勢(shì)函數(shù)法1. 勢(shì)函數(shù)概念勢(shì)函數(shù)概念劃分屬于1和2

45、類(lèi)模式樣本： 樣本是模式空間中的點(diǎn)， 將每個(gè)點(diǎn)比擬為點(diǎn)能源，在點(diǎn)上勢(shì)能達(dá)到峰值，隨著與該點(diǎn)距離的增大，勢(shì)能分布迅速減小。 1類(lèi)樣本勢(shì)能為正勢(shì)能積累形成 “高地”； 2類(lèi)樣本勢(shì)能(-1)勢(shì)能積累形成 “凹地”； 在兩類(lèi)電勢(shì)分布之間，選擇合適的等勢(shì)面（如零等勢(shì)面），即可認(rèn)為是判別界面了。借用點(diǎn)能源的勢(shì)能概念解決模式分類(lèi)問(wèn)題。 kx),(kxxkxo一個(gè)樣本xk的勢(shì)能分布用勢(shì)函數(shù)k( x , xk )表示)(xkxo12積累勢(shì)函數(shù)一維情況示例2. 勢(shì)函數(shù)法判別函數(shù)的產(chǎn)生勢(shì)函數(shù)法判別函數(shù)的產(chǎn)生依次輸入樣本，利用勢(shì)函數(shù)逐步積累勢(shì)能的過(guò)程。 判別函數(shù)由模式空間中樣本向量 的勢(shì)函數(shù)k(x, xk)累加產(chǎn)生，

46、分類(lèi)器計(jì)算積累勢(shì)k(x)，最后取d(x)=k(x)。21,2, 1,kkkxx且設(shè)初始積累勢(shì)函函數(shù) ，下標(biāo)為迭代次數(shù)。0)(0xk勢(shì)函數(shù)法：勢(shì)函數(shù)法：第一步：加入訓(xùn)練樣本 x1 ，k1(x) 描述了加入第一個(gè)樣本后的邊界劃分。-211011101),()(),()()(xxxxxxxxx若若kkkkk第二步：加第二個(gè)訓(xùn)練樣本x2，分三種情況：)()(12xxkk分類(lèi)正確，勢(shì)函數(shù)不變：0)(2112xxk且若0)(2122xxk且或21212,),()()(xxxxxxxxkkkkk，錯(cuò)誤分類(lèi)，修改勢(shì)函數(shù)：0)(2112xxk但若，錯(cuò)誤分類(lèi)，修改勢(shì)函數(shù)：0)(2122xxk但若21212,),(

47、)()(xxxxxxxxkkkkk- 第k步：設(shè)kk(x) 為加入訓(xùn)練樣本x1 ，x2 ，xk后的積累勢(shì)函數(shù)， 則加入第k+1個(gè)樣本，有：)(1xkk正確分類(lèi)， 0)(111kkkkxx且若0)(121kkkkxx且或)(1xkk，錯(cuò)誤分類(lèi)：0)(111kkkk xx但若0)(121kkkk xx但若 ，錯(cuò)誤分類(lèi)：)(1xkk以上決定積累位勢(shì)的迭代算法可寫(xiě)為：其中rk+1 為校正項(xiàng)系數(shù)，定義為：)(xkk),()(1kkkkxxx),()(1-kkkkxxx),()()(111kkkkkrkkxxxx(3-57)-0, 10, 10,00,01211111211111kkkkkkkkkkkkk

48、kkkkrxxxxxxxx且對(duì)于且對(duì)于且對(duì)于且對(duì)于(3-58)從所給的訓(xùn)練樣本集 中略去不使積累勢(shì)發(fā)生變化的那些樣本，可得一簡(jiǎn)化樣本序列 （校正錯(cuò)誤的樣本），算法可規(guī)納為：,21kxxx,21jxxx),()(1jjxjkkkxxx即：由(k+1)個(gè)訓(xùn)練樣本產(chǎn)生的積累勢(shì)，等于兩類(lèi)中校正錯(cuò)誤 的樣本的總勢(shì)能之差。 -21,1,1jjjxx對(duì)于對(duì)于式中， ),()()(111kkkkkrkkxxxx-0, 10, 10, 00, 01211111211111kkkkkkkkkkkkkkkkkrxxxxxxxx且對(duì)于且對(duì)于且對(duì)于且對(duì)于(3-59)(3-60) 從勢(shì)函數(shù)算法可看出，積累勢(shì)函數(shù)起著判別函

49、數(shù)的作用，因此可直接用作判別函數(shù)，故取 d(x)=k(x) 。由(3-57)式得：式中rk+1按(3-58)式取值：1111sgn121-kkkkkdrx也可簡(jiǎn)寫(xiě)成：-0, 10, 10,00,01211111211111kkkkkkkkkkkkkddddrxxxxxxxx且對(duì)于且對(duì)于且對(duì)于且對(duì)于式中 取值同(3-60) ：1k-211,1,1jjkxx對(duì)于對(duì)于),()()(111kkkkkrkkxxxx(3-57),()()(111kkkkkrddxxxx(3-61) 兩個(gè)n維向量 x 和 xk 的函數(shù)k(x, xk) ，如同時(shí)滿足下列三個(gè)條件，都可做為勢(shì)函數(shù)：3. 勢(shì)函數(shù)的選擇勢(shì)函數(shù)的選擇，當(dāng)且僅當(dāng) x = xk 時(shí)達(dá)到最大值。)