第3章 判別函數(shù)及幾何分類法ppt課件

1、第第3章章 判別函數(shù)及幾何分類法判別函數(shù)及幾何分類法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ù)聚類分析法第七章）判決函數(shù)法幾何分類法確定性事件分類（第三章）概率分類法隨機(jī)事件分類（第二章）線性判決函數(shù)法統(tǒng) 計(jì) 決 策 方 法非線性判決函數(shù)法復(fù)習(xí)與引申：復(fù)習(xí)與引申：模式識(shí)別統(tǒng)計(jì)若分屬于1，2的兩類模式可用一方程d(X) =0來(lái)劃分，那么稱d(X) 為判別函數(shù)，或稱判決函

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

3、表示的是一種分類的標(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)確定。如：已知三維線性分類 判決函數(shù)的性質(zhì)就確定了判決函數(shù) 的形式：4332211)(wxwxwxwdX3. 確定判別函數(shù)的兩個(gè)因素確定判別函數(shù)的兩個(gè)因素例：非線性判決函數(shù)2判決函數(shù)d(X)的系數(shù)。用所給的模式樣本確定。3.2 線性判別函數(shù)線性判別函數(shù)3.2.1 線性判別函數(shù)的一般形式線性判別函數(shù)的一般形式將二維模式推廣到n維，

4、線性判別函數(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. 兩類情況d(X) = 0：不可判別情況，可以或拒絕或21XX） 對(duì)M個(gè)線性可分模式類，1， 2， M，有三種劃分方式：2. 多類情況 ii兩分法ji兩分法ji兩分法

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

6、d- 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 類情況分成了(M -1)個(gè)兩類問(wèn)題。并且 類的判別界面全部與 類的判別界面相鄰向無(wú)窮遠(yuǎn)處延伸的區(qū)域除外）。iijj特別的定義23212211)(1)()(xdxxdxxd-XXX例例3.5 一個(gè)三類模式一個(gè)三

7、類模式M=3分類器，其判決函數(shù)為：分類器，其判決函數(shù)為： 試判斷X0=1,1T屬于哪一類，且分別給出三類的判決界面。解： 2003020102030201)()()()(1)(1111)(011)(-XXXXXXXXddddddd012)()(121-xddXX02)()(2131-xxddXX012)()(112-xddXX012)()(2132-xxddXX)()(1331XXdd-)()(2332XXdd-類的判決函數(shù)：1判決界面如圖所示。類的判決函數(shù)：2類的判決函數(shù)：3- 0)(21-XdXd2313dddd0.5x2- 0)(31-XdXd 0)(32-XdXd3212dddd312

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

9、的分布更為聚集， 分法受到的限制條件少，故線性可分的可能性大。jiii兩分法 全部不屬任何類 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分析分類結(jié)果：只要有一個(gè)錯(cuò)誤分類，回到2），直至 對(duì)所有樣本正確分類。 分類正確時(shí)，對(duì)權(quán)向量“賞”這里用“不罰”，即權(quán)向量不變；

10、分類錯(cuò)誤時(shí)，對(duì)權(quán)向量“罰”對(duì)其修改，向正確的方向轉(zhuǎn)換。感知器算法是一種賞罰過(guò)程：感知器算法是一種賞罰過(guò)程：3. 收斂性收斂性收斂性：經(jīng)過(guò)算法的有限次迭代運(yùn)算后，求出了一個(gè)使所有樣本都能正確分類的W，則稱算法是收斂的?？梢宰C明感知器算法是收斂的。收斂條件：模式類別線性可分。 例例3.8 已知兩類訓(xùn)練樣本已知兩類訓(xùn)練樣本解：所有樣本寫(xiě)成增廣向量形式； 進(jìn)行規(guī)范化處理，屬于2的樣本乘以(1)。T11 , 0 , 0XT21 , 1 , 0XT31, 0 , 1 -XT41, 1, 1-X用感知器算法求出將模式分為兩類的權(quán)向量解和判別函數(shù)。 :1T10,0X:2T21 ,0XT30, 1XT41 ,

11、1X任取W(1)=0，取c=1，迭代過(guò)程為：第一輪： 0,1000 , 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

12、)7(,01)6(WWXW故T33T0 , 0 , 2-)7()8(,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該輪迭代的分類結(jié)果全部正確，故

13、解向量1+2=)(1xd X相應(yīng)的判別函數(shù)為： 當(dāng)c、W(1)取其他值時(shí)，結(jié)果可能不一樣，所以感知器算法的解不是單值的。判別界面d(X)=0如圖示。采用多類情況3的方法時(shí)，應(yīng)有：4. 感知器算法用于多類情況感知器算法用于多類情況Mj, 1= iX ,)(ijddjiXX假設(shè)，那么 Midi, 1,對(duì)于M類模式應(yīng)存在M個(gè)判決函數(shù)：算法主要內(nèi)容：M,21設(shè)有 M 種模式類別： Mjj, 1,1W設(shè)其權(quán)向量初值為： 第k次迭代時(shí)，一個(gè)屬于i類的模式樣本 X 被送入分類器，計(jì)算所有判別函數(shù)訓(xùn)練樣本為增廣向量形式，但不需要規(guī)范化處理。 分二種情況修改權(quán)向量： Mjkkdjj, 1,TXW 若第l個(gè)權(quán)向量

14、使 ，則相應(yīng)的權(quán)向量作調(diào)整，即： -lijkkckkckkjjllii,111WWXWWXWW 可以證明：只要模式類在情況3判別函數(shù)時(shí)是可分的，那么經(jīng)過(guò)有限次迭代后算法收斂。， c為正的校正增量例例3.9 設(shè)有三個(gè)線性可分的模式類，三類的訓(xùn)練樣本分別為設(shè)有三個(gè)線性可分的模式類，三類的訓(xùn)練樣本分別為 假設(shè) 則權(quán)向量不變； Mjijkdkdji, 2 , 1;, Mjkkjj, 2 , 1,1WW( )( )kdkdli T33T22T111 , 11 , 10 , 0-XXX：；：；：現(xiàn)采用多類情況3的方式分類，試用感知器算法求出判別函數(shù)。 解：增廣向量形式：T3T2T11,1, 1,1,1,

15、1,1 , 0 , 0-XXX注意，這里任一類的樣本都不能乘以（1）。任取初始權(quán)向量T3210 , 0 , 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

16、 , 1, 1)2()3(-XWWT2220 , 1 , 1)2() 3(XWWT2332, 1, 1)2()3(-XWW第三次迭代： 修改為權(quán)向量。33X 3313dd 3323dd，但且不成立， 以上進(jìn)行的一輪迭代運(yùn)算中，三個(gè)樣本都未正確分類，進(jìn)行下一輪迭代。第四次迭代： 在第五、六、七迭代中，對(duì)所有三個(gè)樣本都已正確分類。權(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)是向量 的函

17、數(shù)，則f (Y)的梯度定義為：3.6 梯度法梯度法T21,nyyyY T21,ddnyfyfyfffYYY梯度的方向是函數(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è)線性可分的模式類1和2的樣本共N個(gè)，2類樣本乘(-1)。將兩類樣本分開(kāi)的判決函數(shù)d(X)

18、應(yīng)滿足： 梯度算法的目的仍然是求一個(gè)滿足上述條件的權(quán)向量，主導(dǎo)思想是將聯(lián)立不等式求解W的問(wèn)題，轉(zhuǎn)換成求準(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ò)誤分類敏感的準(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)

19、則函數(shù)，設(shè)置初始權(quán)向量W(1)，括號(hào)內(nèi)為迭代次數(shù)k=1。 權(quán)向量修正為：)(,)(kiJkJWWWXW )(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ù)選擇準(zhǔn)則函數(shù) ， ，簡(jiǎn)單地考慮，簡(jiǎn)單地考慮X為一維增廣模式的情況為一維增廣模式的情況X=1，此時(shí)，此時(shí)W=w，兩者均為標(biāo)量，兩者均為標(biāo)量，XWXWXWTT),(-Jww

20、J-),(XW錯(cuò)誤分類時(shí)： 22,1-wwwwwJJXXWW0010TwwXW ckckk221-WWW， 對(duì)權(quán)向量校正。 Jckk-WW1正確分類時(shí)：0010TwwXW0-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)的選

21、擇，J(W, X)的形式不同，得到的具體算法不同。a) b) c值的選擇很重要，如c值太小，收斂太慢；但若太大，搜索又可能過(guò)頭，甚至引起發(fā)散。3.6.2 固定增量法固定增量法準(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 1

22、11111TnnnnXXIWXWXWT首先求另：矩陣論中有XWXWXWTT21),(-JXXWXWXW-Tsgn21,JJ其中 -0, 10, 1sgnTTTXWXWXW若若 由的結(jié)論 有： XWXWTXWXWWXWXWTTT0時(shí)，XWXWWXWXW-TTT0時(shí)，XXWWXWTTsgnXWXWXWTT21),(-J kJckJckkWWWXWWWW-,12. 求W(k+1)將 代入得： XXWXWW-)(sgn211Tkckk 0)(,0)(, 0TTXWXXWWkckk若若 XWXXW)(sgn2Tkck-XXWXWXW-Tsgn21,JJ 由此可以看出，感知器算法是梯度法的特例。即：梯度法

23、是將感知器算法中聯(lián)立不等式求解W的問(wèn)題，轉(zhuǎn)換為求函數(shù)J極小值的問(wèn)題，將原來(lái)有多個(gè)解的情況，變成求最優(yōu)解的情況。上式即為固定增量算法，與感知器算法形式完全相同 。 0)(,0)(, 01TTXWXXWWWkckkk若若即： 0, 0,1TTiiikckkkkXWXWXWWW若若只要模式類是線性可分的，算法就會(huì)給出解。*argmax (,)J KwwwFisher判別x1x2w1H: g=0w2Fisher準(zhǔn)則的描述：用投影后數(shù)據(jù)的統(tǒng)計(jì)性質(zhì)均值和離散度的函數(shù)作為判別優(yōu)劣的標(biāo)準(zhǔn)。Fisher判別1 1,2iix KiiNmx()() , 1,2iTiiii-xSxmxm12wSSS1212()()T

24、b-Smmmm離散度矩陣在形式上與協(xié)方差矩陣很相似，但協(xié)方差矩陣是一種期望值，而離散矩陣只是表示有限個(gè)樣本在空間分布的離散程度1, 1,2iiyimyiN2() , 1,2iiiySymi-12wSSS212()bSmm-以上定義描述d維空間樣本點(diǎn)到一向量投影的分散情況，因此也就是對(duì)某向量w的投影在w上的分布。樣本離散度的定義與隨機(jī)變量方差相類似 12wSSS2121212()( )bFSmmJwSSSS-22()()()()iiiiiyTTix KTTiiix KTSSym-w xw mwwxmxwwm1212()TTwSSSSSwwww2212121212()()()()TTTbTbTSS

25、mm-w mw mwwmmmmww12( )TbbFTwSSJwSSSwwww*argmax( )FJwww*112()wS-wmmm1-m2是一向量，對(duì)與是一向量，對(duì)與(m1-m2)平行的向量投影可使平行的向量投影可使兩均值點(diǎn)的距離最遠(yuǎn)。但是如從使類間分得較開(kāi)，同時(shí)又兩均值點(diǎn)的距離最遠(yuǎn)。但是如從使類間分得較開(kāi)，同時(shí)又使類內(nèi)密集程度較高這樣一個(gè)綜合指標(biāo)來(lái)看，則需根據(jù)兩使類內(nèi)密集程度較高這樣一個(gè)綜合指標(biāo)來(lái)看，則需根據(jù)兩類樣本的分布離散程度對(duì)投影方向作相應(yīng)的調(diào)整，這就體類樣本的分布離散程度對(duì)投影方向作相應(yīng)的調(diào)整，這就體現(xiàn)在對(duì)現(xiàn)在對(duì)m1-m2 向量按向量按Sw-1作一線性變換，從而使作一線性變換，從

26、而使Fisher準(zhǔn)則函數(shù)達(dá)到極值點(diǎn)準(zhǔn)則函數(shù)達(dá)到極值點(diǎn)1202mmw1122012N mN mwmNN1212012ln()/()22PPmmwNN-0102TTywyww xxw xx12( )TbbFTwSSJwSSSwwwwc0TwSww令 Lagrange:( , )()TTbwLSSc-wwwww定義函數(shù) ( , ):0bwLSS-wwww令 1wbSS-ww111212112()()()TwbwwSSSSR-wwmmmmwmm*111212()()wwRSS-wmmmm*112()wS-wmm3.7 最小平方誤差算法最小平方誤差算法（least mean square error,

27、LMSE；亦稱Ho-Kashyap算法） 上述的感知器算法、梯度算法、固定增量算法或其他類似方法，只有當(dāng)模式類可分離時(shí)才收斂，在不可分的情況下，算法會(huì)來(lái)回?cái)[動(dòng)，始終不收斂。當(dāng)一次次迭代而又不見(jiàn)收斂時(shí)，造成不收斂現(xiàn)象的原因分不清，有兩種可能：a) 迭代過(guò)程本身收斂緩慢b) 模式本身不可分對(duì)可分模式收斂。對(duì)于類別不可分的情況也能指出來(lái)。LMSE算法特點(diǎn)：1. 分類器的不等式方程分類器的不等式方程-NnNnnNNnnnnnnwxwxwxwwxwxwxwwxwxwxwXXX對(duì)對(duì)對(duì)00012211212222211111122111類1類20TiXW 兩類分類問(wèn)題的解相當(dāng)于求一組線性不等式的解。如果給出

28、分屬于 ， 兩個(gè)模式類的訓(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ì)00012211212222211111122111類1類21,.iNL式中：T121,nnwwwwW121TT1TT2T1-nNNNiXXXXXX0XW0-1111211

29、2122221112110000111NnnnnNNnNNnnwwwwxxxxxxxxx0為零向量為零向量 感知器算法是通過(guò)解不等式組 ，求出W。0XW2. LMSE算法算法1) 原理原理的求解。式中： 兩式等價(jià)。T21,NibbbbB為各分量均為較小正值的矢量。LMSE算法把對(duì)滿足 XW 0 的求解，改為滿足BXW 在方程組系數(shù)矩陣中當(dāng)行數(shù)列數(shù)時(shí)，通常無(wú)解，稱為矛盾方程組，一般求近似解。在模式識(shí)別中，通常訓(xùn)練樣本數(shù)N總是大于模式的維數(shù)n，因此方程的個(gè)數(shù)(行數(shù))模式向量的維數(shù)(列數(shù))，是矛盾方程組，只能求近似解W*，即說(shuō)明：極小-BXW * LMSE算法的出發(fā)點(diǎn)：選擇一個(gè)準(zhǔn)則函數(shù)，使得當(dāng)J達(dá)到

30、最小值時(shí)，XW=B 可得到近似解最小二乘近似解）。 LMSE算法的思路：BWBXWXW、通過(guò)求準(zhǔn)則函數(shù)極小找求解對(duì)求解對(duì) 0轉(zhuǎn)化為轉(zhuǎn)化為準(zhǔn)則函數(shù)定義為： 221,BXWBXW-J“最小二乘”： 最小：使方程組兩邊誤差最小， 也即使J最小。 二乘：次數(shù)為2，乘了兩次最小平方誤差算法）1111121111221111111111-NNinnnnNNnNininnbbbwwwwxxxxxxxxBXW-NNiiNNnnNnNinnininnnbbbbwwxwxbwwxwxbwwxwxXWXWXWTT11T1111111111111向量各分量的平方和向量各分量的平方和-22BXW-NiiiNNbbb12

31、T2T211T2XWXWXWBXW考察向量(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 的近似解也稱的近似解也稱“最優(yōu)近似解最優(yōu)近似解”： 使方程組兩邊所有誤差之和最小即最優(yōu)的解。使方程組兩邊所有誤差之和最小即最優(yōu)的解。準(zhǔn)則函數(shù)：BXBXXXWBXXWXBXWX#T1TTTT0-使J 對(duì)W求最小，令 ，得：2) 推導(dǎo)推導(dǎo)LMSE算法遞推公式算法遞推公式與問(wèn)題相關(guān)的兩個(gè)梯度： BXWXW-TJBXW

32、BXWB-21J (3-46)(3-47)由(3-47)式可知：只要求出B，就可求出W。求遞推公式：(1) 求W 的遞推關(guān)系X為為N(n+1)長(zhǎng)方陣，長(zhǎng)方陣，X#為為(n+1) N 長(zhǎng)方陣。長(zhǎng)方陣。T1T#XXXX-稱為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-#T1T kckckeXeXBX#(3)

33、 求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)。互相獨(dú)立，先后次序無(wú)關(guān)。求出B，W后，再迭代出下一個(gè)e，從而計(jì)算出新的B， W。 11#BXW kkkBXWe- kkckkeeBB1或另一算法：先算B(k+1)，再算

34、W(k+1)。3模式類別可分性判別模式類別可分性判別 如果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#kkBXW(5)

35、計(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 已知兩類模式訓(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) 求偽逆矩陣-42222121211110111

36、0100111110101100TXX*11AAA-求逆矩陣：333231232221131211aaaaaaaaaA332313232212312111*AAAAAAAAAA假設(shè)，那么 |A|A的行列式A*A的伴隨矩陣422221212TXX 劃去aij所在的行和列的元素，余下元素構(gòu)成的行列式做aij的余子式，記作Mij ，將 叫做元素aij的代數(shù)余子式。例：代數(shù)余子式定義： ijijAM ji1- 323112113231121132231-aaaaaaaaA-322240204413222402041T1TXXXX44884416422221212T-XX行列式: 33323123222

37、1131211aaaaaaaaaA*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-11132222222241#X

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

39、能低于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í)； 用于線性可分的模式類。非線性判別函數(shù)：用于線性不可分情況。分段線性、超曲面。 特點(diǎn)基本組成為超平面。* 相對(duì)簡(jiǎn)單；* 能逼近各種形狀的超曲面。1一般分段線性判別函數(shù)一般分段線性判別函數(shù)設(shè)有M類模式，將i類i=1,2, ,M劃分為li個(gè)子類：Miiliiii, 2 , 1,:21其中第n個(gè)子類的判別函數(shù)： Mi

40、lndinini, 2 , 1;, 2 , 1)()(TXWXi類的判別函數(shù)定義為：, 2 , 1),(max)(iniilnddXXM類的判決規(guī)則： , 2 , 1),(max)(MiddijXXjX假設(shè)，那么用各類判別函數(shù)進(jìn)行分類判決實(shí)際是用各類選出的子類判別函數(shù)進(jìn)行判決判別面由各子類的判別函數(shù)決定若i類的第n個(gè)子類和j類的第m個(gè)子類相鄰，判別界面方程為：)()(XXmjnidd子類之間的判別界面組成各類之間的判別界面類間判別界面分段線性2基于距離的分段線性判別函數(shù)基于距離的分段線性判別函數(shù)設(shè) 1類均值向量：11111NiiNXM21221NiiNXM2類均值向量：N1，N2：兩類樣本數(shù)。

41、 任一模式X到M1和M2的歐氏距離平方：211|)(MXX-d222|)(MXX-d判決規(guī)則：)()(21XXdd1X假設(shè)， 那么)()(12XXdd2X假設(shè)， 那么判別界面方程：2221|MXMX-1最小距離分類器化簡(jiǎn)得：0)()(21T12T2T21-MMMMXMM X的線性方程，確定一個(gè)超平面。 最小距離分類器 2分段線性距離分類器 設(shè)：M類模式，其中i類劃分為li個(gè)子類，第n個(gè)子類的均值向量為 。每個(gè)子類的判別函數(shù)：niMMilndinini, 2 , 1;, 2 , 1,|)(2-MXX每類的判別函數(shù)： , 2 , 1),(min)(iniilnddXX判決規(guī)則：, 2 , 1),(

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

43、： 樣本是模式空間中的點(diǎn)， 將每個(gè)點(diǎn)比擬為點(diǎn)能源，在點(diǎn)上勢(shì)能達(dá)到峰值，隨著與該點(diǎn)距離的增大，勢(shì)能分布迅速減小。 1類樣本勢(shì)能為正勢(shì)能積累形成 “高地”； 2類樣本勢(shì)能(-1)勢(shì)能積累形成 “凹地”； 在兩類電勢(shì)分布之間，選擇合適的等勢(shì)面如零等勢(shì)面），即可認(rèn)為是判別界面了。借用點(diǎn)能源的勢(shì)能概念解決模式分類問(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)生，分類器計(jì)算積

44、累勢(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分類正確，勢(shì)函數(shù)不變：0)(2112XXK且若0)(2122XXK且或21212,),()()(XXXXXXXXKKKKK，錯(cuò)誤分類，修改勢(shì)函數(shù)：0)(2112XXK但若，錯(cuò)誤分類，修改勢(shì)函數(shù)：0)(2122XXK但若21212,),()()(XX

45、XXXXXXKKKKK- 第k步：設(shè)Kk(X) 為加入訓(xùn)練樣本X1 ，X2 ，Xk后的積累勢(shì)函數(shù)， 則加入第k+1個(gè)樣本，有：)(1XkK正確分類， 0)(111kkkKXX且若0)(121kkkKXX且或)(1XkK，錯(cuò)誤分類：0)(111kkkK XX但若0)(121kkkK XX但若 ，錯(cuò)誤分類：)(1XkK以上決定積累位勢(shì)的迭代算法可寫(xiě)為：其中rk+1 為校正項(xiàng)系數(shù)，定義為：)(XkK),()(1kkKKXXX),()(1-kkKKXXX),()()(111kkkkKrKKXXXX(3-57)-0, 10, 10,00,01211111211111kkkkkkkkkkkkkKKKKrX

46、XXXXXXX且對(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ì)，等于兩類中校正錯(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ù)起著判別函數(shù)的作用，因

47、此可直接用作判別函數(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á)到最大值。),(),(XXXXkkKK 當(dāng)向量 X 與 Xk 的距離趨于無(wú)窮時(shí)，K(X, Xk) 趨于零。 K(X, Xk) 是光滑函數(shù)，且是