【正文】 1 ??W設(shè)其權(quán)向量初值為： 第 k次迭代時(shí)，一個(gè)屬于 ωi類的模式樣本 X 被送入分類器， 計(jì)算所有判別函數(shù) 訓(xùn)練樣本為增廣向量形式，但 不需要規(guī)范化處理 。 ? ? T11T 1,0,1)5()6(,00)5( ????? XWWXW 故? ? T2T 1,0,1( 6 ))7(,01)6( ???? WWXW 故? ? T33T 0,0,2)7()8(,00)7( ????? XWWXW 故? ? T4T 0,0,2)8()9(,02)8( ???? WWXW 故第二輪： ? ? T11T 1,0,2)9()10(,00)9( ????? XWWXW 故( 1 0 ))11(,01)10( 2T WWXW ??? 故)11()12(,01)11( 3T WWXW ??? 故)12()13(,01)12( 4T WWXW ??? 故第三輪： )13()14(,01)13( 1T WWXW ??? 故( 1 4 ))15(,01)14( 2T WWXW ??? 故)15()16(,01)15( 3T WWXW ??? 故)16()17(,01)16( 4T WWXW ??? 故第四輪： ? ? T1,0,2?W該輪迭代的分類結(jié)果全部正確，故解向量 12)( 1 ?? xd X相應(yīng)的判別函數(shù)為： 當(dāng) c、 W(1)取其他值 時(shí)，結(jié)果可能不一樣， 所以 感知器算法的解不是單值的。 ? ?T1 1,0,0?X ? ?T2 1,1,0?X ? ?T3 1,0,1 ?X ? ?T4 1,1,1 ?X用感知器算法求出將模式分為兩類的權(quán)向量解和判別函數(shù)。 收斂條件：模式類別線性可分。 感知器算法是一種賞罰過程： 3. 收斂性 收斂性：經(jīng)過算法的有限次迭代運(yùn)算后，求出了一個(gè)使所有樣本都能正確分類的 W，則稱算法是收斂的。 分類器對(duì)第 i個(gè)模式做了錯(cuò)誤分類， ( ) ，若 0≤Tik XW① ( ) ( ) ickk XWW +=1+權(quán)向量校正為： ( ) ( )kk WW =1+統(tǒng)一寫為： 分類正確，權(quán)向量不變： ( ) ，若 0Tik XW② ( ) =1+kW( ) ick XW +( )kW ( ) 0T ik XW若( ) 0≤T ik XW若（ 3）分析分類結(jié)果：只要有一個(gè)錯(cuò)誤分類，回到（ 2），直至 對(duì)所有樣本正確分類。 （ 2）用全部訓(xùn)練樣本進(jìn)行一輪迭代，計(jì)算 WT(k)Xi 的值，并修 正權(quán)向量。任取權(quán)向量初始 值 W(1)，開始迭代。 2. 感知器算法 （ perception approach） 兩類線性可分的模式類： ，設(shè) 21,?? XWX T)( ?d其中， ， ? ?T121 , ?? nn w ?W ? ?T21 1, nxxx ??X應(yīng)具有性質(zhì) ????????21T,0,0)(??XXXWX若若d對(duì)樣本進(jìn)行規(guī)范化處理，即 ω2類樣本全部乘以 (－ 1)，則有： 0)( T ?? XWXd 感知器算法通過對(duì)已知類別的訓(xùn)練樣本集的學(xué)習(xí)，尋找 一個(gè)滿足上式的權(quán)向量。 2）確定性分類器 處理確定可分情況的分類器。 對(duì)線性判別函數(shù)，當(dāng)模式維數(shù)已知時(shí)，判別函數(shù)的形式實(shí)際上已經(jīng)確定，如：三維時(shí) ? ?T321 1, xxx?X ? ? T4321 , w?W3）感知器 對(duì)一種分類學(xué)習(xí)機(jī)模型的稱呼，屬于有關(guān)機(jī)器學(xué)習(xí)的仿生學(xué)領(lǐng)域中的問題，由于 無法實(shí)現(xiàn)非線性分類 而下馬。 1）訓(xùn)練與學(xué)習(xí) 學(xué)習(xí)：從分類器的角度講 非監(jiān)督學(xué)習(xí) 監(jiān)督學(xué)習(xí) 訓(xùn)練 ? ? XWX T4332211 ????? wxwxwxwd只要求出權(quán)向量，分類器的設(shè)計(jì)即告完成。 Fisher線性判別 — 降維 /兩類 ?線性判別函數(shù) y = g(x) = wTx : ? 樣本向量 x各分量的線性加權(quán) ? 樣本向量 x與權(quán)向量 w的向量 點(diǎn)積 ? 如果 || w ||=1，則視作向量 x在 w上的 投影 ?Fisher準(zhǔn)則的基本原理 ： 找到一個(gè) 最理想的投影軸 ，使兩類樣本在該軸上投影之間的距離盡可能遠(yuǎn)，而每一類樣本的投影盡可能緊湊，從而使分類效果為最佳 Fisher線性判別 圖例 x1 x2 w1 H: g=0 w2 Fisher準(zhǔn)則的描述：用投影后數(shù)據(jù)的統(tǒng)計(jì)性質(zhì) — 均值和離散度的函數(shù) 作為判別優(yōu)劣的標(biāo)準(zhǔn) d維 X空間樣本分布的描述量 ? 各類 樣本均值向量 mi 1 1 , 2mx????iixKiiN? 樣本 類內(nèi)離散度矩陣 Si與 總類內(nèi)離散度矩陣 Sw ( ) ( ) , 1 , 2xS x m x m??? ??iTi i i i12S S S??w? 樣本 類間離散度 矩陣 Sb： 1 2 1 2( ) ( )S m m m m? Tb離散度矩陣在形式上與協(xié)方差矩陣很相似 一維 Y空間樣本分布的描述量 ? 各類 樣本均值 ? 樣本 類內(nèi)離散度 和總 類內(nèi)離散度 ? 樣本 類間離散度 以上定義描述 d維空間樣本點(diǎn)到一向量 投影后 的分散情況 2,1,1 ????iyNmiyii ?2,1,)(~ 2 ?? ??imySy ii ?21~~~ SSSw ??221 )(~ mmS b ?原樣本與其投影統(tǒng)計(jì)量間的關(guān)系 ?樣本 x與其投影 y 的統(tǒng)計(jì)量之間的關(guān)系： 221 )(~ mmS b ?樣本與其投影統(tǒng)計(jì)量間的關(guān)系 2)(~ ? ?? ?y iimyS21~~~ SSSw ??Fisher準(zhǔn)則函數(shù) ?評(píng)價(jià)投影方向 w的原則，使原樣本向量在該方向上的投影能兼顧類間分布盡可能分開，類內(nèi)盡可能密集的要求 ?Fisher準(zhǔn)則函數(shù)的定義： ? Fisher最佳投影方向的求解 * a r g m a x ( )www? FJFisher最佳投影方向的求解 ?采用拉格朗日乘子算法解決 *112()w m m?wSm1m2是一向量，對(duì)與 (m1m2)平行的向量投影可使兩均值點(diǎn)的距離最遠(yuǎn)。 X 1 ① X 2 X 3 X 4 ② ③ ④ ⑤ ⑥ ⑦ ⑧ 若不限制判別函數(shù)的形式， N個(gè) n維模式用判別函數(shù)分成兩 類的二分法總數(shù)為 2N。是一種基本的分類方法。 O W 的解區(qū) + w 2 w 1 + + + － － － － 解 向量 02211 ?? xwxw 12 ?x例：二維權(quán)空間，超平面的方程為： 超平面：過原點(diǎn)的直線； 陰影部分：解區(qū)。 在權(quán)空間中尋找向量 W使判別函數(shù) d(X)能把 ω1類和 ω2類 分開，就是尋找一個(gè)權(quán)向量，其在（ p+q）個(gè)超平面的正側(cè)的 交迭區(qū)域里 (W的解區(qū) )。 1?類： X11， X12， … ， X1p 類： X21， X22， … ， X2q 2?設(shè)增廣樣本向量： 使 d(X)將 ω1和 ω2分開，需滿足 pid i ,2,1,0)( 1 ???Xqid i ,2,1,0)( 2 ???X給 ω2的 q個(gè)增廣模式乘以（－ 1），統(tǒng)一為 0)( ?Xd??????qipiXii,2,1,2,1,21??XX, 其中 —— 樣本的規(guī)范化 過程。 權(quán)空間與權(quán)向量解 1. 概念 權(quán)空間：以 的權(quán)系數(shù)為 坐標(biāo)變量的（ n+1）維歐氏空間 ? ? 12211 ??????? nnn wx wxwxwd X增廣權(quán)向量的表示：點(diǎn)、有向線段。 X到超平面的距離： 0)(WXdr ?—— 點(diǎn) X到超平面的代數(shù)距離（帶正負(fù)號(hào)）正比于 d(X)函數(shù)值。 設(shè)超平面的單位法線向量為 U： 00WWU ?222210 n ???? ?W O W 0 + － X 1 X 2 ( X 1 － X 2 ) d ( X ) = 0 x2 x1 (2) X不在超平面上 將 X向超平面投影得向量 Xp， 構(gòu)造向量 R： 00WWrr ??? URr： X到超平面的垂直距離。 2. 討論 1. 概念 ? ? T210 , n ??W ? ? T21 , nxxx ??X式中， ， 。 模式向量的表示：點(diǎn)、有向線段。 問題： 維數(shù)大大增加： 維數(shù)災(zāi)難。 ? ? ? ? ? ? T121T ,** ???? kk wdd ?WXXWX (311) 隨著小樣本學(xué)習(xí)理論和支持向量機(jī)的迅速發(fā)展，廣義線性 判別函數(shù)的 “維數(shù)災(zāi)難”問題在一定程度上找到了解決的辦法。 廣義形式的模式向量定義為： (310) ? ? ? ? ? ?? ? T21T**2*1 1,]1,[ XXXX kk fffxxx ?? ???這里 X*空間的維數(shù) k高于 X空間的維數(shù) n， (39)式可寫為 上式是線性的。 設(shè)一訓(xùn)練用模式集， {X}在模式空間 X中線性不可分，非線 性判別函數(shù)形式如下： ? ? 1nnn2211 ??????? wxwxwxwd X (39) ? ? ? ? ? ? ? ?12211 ??????? kkk wfwfwfwd XXXX ? ????? 11kiii fw X式中 是模式 X的單值實(shí)函數(shù)， 。 j??i1．非線性多項(xiàng)式函數(shù) 非線性判別函數(shù)的形式之一是非線性多項(xiàng)式函數(shù)。當(dāng) M3時(shí)，后者需要更多個(gè)判別式（缺點(diǎn)），但對(duì)模式的線性可分的可能性要更大一些（優(yōu)點(diǎn)）。 一旦線性判別函數(shù)的系數(shù) Wk被確定以后，這些函數(shù)就可以 作為模式分類的基礎(chǔ)。 類的判決函數(shù)： 2?類的判決函數(shù)： 3? ? ? 0 ) ( 2 1 ? X d X d 2 3 1 3 d d d d ? ? x2 ? ? ? ? 0 ) ( 3 1 ? X d X d ? ? 0 ) ( 3 2 ? X d X d 3 2 1 2 d d d d ? ? 3 1 2 1 d d d d ? ? 1 1 ?1 ?2 ?3 x1 ? O 2 x 1 x ? ? 0 ) ( 2 1 ? X X d d ? ? ? ? ? 0 ) ( 3 1 ? X X d d ? ? 0 ) ( 3 2 ? X X d d 例 已知判決界面的位置和正負(fù)側(cè)，分析三類模式的分布 區(qū)域 。 i?? ?ijj ???23212211)(1)()(xdxxdxxd?????XXX例 一個(gè)三類模式（ M=3）分類器，其判決函數(shù)為： 試判斷 X0=[1,1]T屬于哪一類，且分別給出三類的判決界面。 2 3 1 3 d d d d ? ? 0 1 ? 2 ? 2 x 1 x ? ? 0 ) ( 2 1 ? X d X d ? ? ? ? 0 ) ( 3 1 ? X d X d ? ? 0 ) ( 3 2 ? X d X d 3 2 1 2 d d d d ? ? 3 1 2 1 d d d d ? ? 3 ? ③ 把 M 類情況分 成了 (M 1)個(gè)兩類 問題。 特點(diǎn)： ① 是第二種情況的特例。,)( ?或： ? ?? ? iki Mkdd ???? XXX 若,1,m a x)( ?