【文章內(nèi)容簡(jiǎn)介】 與協(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)。但是如果從使類間分得較開，同時(shí)又使類內(nèi)密集程度較高這樣一個(gè)綜合指標(biāo)來(lái)看，則 需根據(jù)兩類樣本的分布離散程度對(duì)投影方向作相應(yīng)的調(diào)整 ，這就體現(xiàn)在對(duì) m1m2 向量按 Sw1作一線性變換，從而使 Fisher準(zhǔn)則函數(shù)達(dá)到極值點(diǎn) ( , ) ( )w w w w w??? TTbwL S S c定 義 判別函數(shù)的確定 ?前面討論了使 Fisher準(zhǔn)則函數(shù)極大的 d維向量w*的計(jì)算方法，判別函數(shù)中的另一項(xiàng) w0（閾值）可采用以下幾種方法確定： 010200w x xw x x??? ? ? ? ?? ? ? ?TTywyw? 分類規(guī)則 : 2~~210mmw ??2)](/)([2~~2121210 ???NNPPInmmw ??mw ~0 ?Fisher準(zhǔn)則舉例 例 1： 設(shè)兩類樣本的類內(nèi)離散矩陣分別為 S1， S2，各類樣本均值分別為m1=(2, 0)T, m2=(2, 2)T, 試用 Fisher準(zhǔn)則求其決策面方程 解 121 1211???????S122 1211???????S由于兩類樣本分布形狀是相同的（只是方向不同），因此 w0應(yīng)為（投影后）兩類均值的中點(diǎn) 122002W??? ? ?????S S S*1w 1 20 .5 0 0 0()0 0 .5 2 1 ? ? ? ? ? ?? ? ?? ? ? ? ? ?? ? ? ? ? ?w S m mT1 2 1 20m m * ( ) 122w??? ? ?w m mFisher準(zhǔn)則最佳投影 T02*01wx???wx即 ：Fisher準(zhǔn)則最佳分界面 Fisher最佳線性分界面 R1 R2 圖中綠線為最佳分界面 x1 x2 感知器算法 1. 概念理解 訓(xùn)練：用已知類別的模式樣本指導(dǎo)機(jī)器對(duì)分類規(guī)則進(jìn)行反復(fù)修 改，最終使分類結(jié)果與已知類別信息完全相同的過程。 1）訓(xùn)練與學(xué)習(xí) 學(xué)習(xí)：從分類器的角度講 非監(jiān)督學(xué)習(xí) 監(jiān)督學(xué)習(xí) 訓(xùn)練 ? ? XWX T4332211 ????? wxwxwxwd只要求出權(quán)向量，分類器的設(shè)計(jì)即告完成。本節(jié)開始介紹如何通過各種算法，利用已知類別的模式樣本 訓(xùn)練出權(quán)向量 W。 對(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)域中的問題，由于 無(wú)法實(shí)現(xiàn)非線性分類 而下馬。但“賞罰概念（ rewardpunishment concept）” 得到廣泛應(yīng)用。 2）確定性分類器 處理確定可分情況的分類器。通過幾何方法將特征空間 分解為對(duì)應(yīng)不同類的子空間，又稱為幾何分類器。 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)向量。 感知器算法步驟： （ 1）選擇 N個(gè)分屬于 ω1和 ω2類的模式樣本構(gòu)成訓(xùn)練樣本集 { X1, …, XN } 構(gòu)成增廣向量形式，并進(jìn)行規(guī)范化處理。任取權(quán)向量初始 值 W(1)，開始迭代。迭代次數(shù) k=1 。 （ 2）用全部訓(xùn)練樣本進(jìn)行一輪迭代，計(jì)算 WT(k)Xi 的值，并修 正權(quán)向量。 分兩種情況，更新權(quán)向量的值： c：正的校正增量。 分類器對(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ì)所有樣本正確分類。 分類正確時(shí)，對(duì)權(quán)向量“賞” ——這里用“不罰”，即權(quán)向量不變； 分類錯(cuò)誤時(shí)，對(duì)權(quán)向量“罰” ——對(duì)其修改，向正確的方向轉(zhuǎn)換。 感知器算法是一種賞罰過程： 3. 收斂性 收斂性：經(jīng)過算法的有限次迭代運(yùn)算后，求出了一個(gè)使所有樣本都能正確分類的 W，則稱算法是收斂的。 可以證明感知器算法是收斂的。 收斂條件：模式類別線性可分。 例 已知兩類訓(xùn)練樣本 解：所有樣本 寫成增廣向量形式； 進(jìn)行規(guī)范化處理，屬于 ω2的樣本乘以 (－ 1)。 ? ?T1 1,0,0?X ? ?T2 1,1,0?X ? ?T3 1,0,1 ?X ? ?T4 1,1,1 ?X用感知器算法求出將模式分為兩類的權(quán)向量解和判別函數(shù)。 :1? ? ?T1 0,0?X:2?? ?T2 1,0?X? ?T3 0,1?X ? ?T4 1,1?X任取 W(1)=0，取 c=1，迭代過程為： 第一輪： ? ? 0,1000,0,0)1( 1T ????????????XW ? ? T1 1,0,0)1()2(,0 ???? XWW故? ? 1,1101,0,0)2( 2T ????????????XW ? ? T1,0,0)2()3(,0 ??? WW故? ? 1 ,1011,0,0)3( 3T ????????????XW ? ?T3 0,0,1)3()4(,0 ???? XWW故? ? 1,1110,0,1)4( 4T ????????????XW ? ? T0,0,1)4()5(,0 ??? WW故有兩個(gè) WT(k)Xi ≤0的情況（錯(cuò)判），進(jìn)行第二輪迭代。 ? ? 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é)果可能不一樣， 所以 感知器算法的解不是單值的。 判別界面 d(X)=0如圖示。 2x ? ? 012 1 ??? xd X ? ?0,13X ? ?1,02X ? ?1,14X 1x 1?? 2?? ? ?0,01X 采用多類情況 3的方法時(shí)，應(yīng)有： 4. 感知器算法用于多類情況 Mj ,1= ?i??X ? ? ,)( ijdd ji ??? XX若 ，則 ? ?Mid i ,1, ??對(duì)于 M類模式應(yīng)存在 M個(gè)判決函數(shù)： 算法主要內(nèi)容： M??? , 21 ?設(shè)有 M 種模式類別： ? ? Mjj ,1,1 ??W設(shè)其權(quán)向量初值為： 第 k次迭代時(shí)，一個(gè)屬于 ωi類的模式樣本 X 被送入分類器， 計(jì)算所有判別函數(shù) 訓(xùn)練樣本為增廣向量形式，但 不需要規(guī)范化處理 。 分二種情況修改權(quán)向量： ? ? ? ? Mjkkd jj ,1,T ??? XW② 若第 l個(gè)權(quán)向量使 ，則相應(yīng)的權(quán)向量作調(diào)整，即： ? ? ? ?? ? ? ?? ? ? ??????????????lijkkckkckkjjllii,111WWXWWXWW 可以證明：只要模式類在情況 3判別函數(shù)時(shí)是可分的，則 經(jīng)過有限次迭代后算法收斂。 ， c為正的校正增量 例 設(shè)有三個(gè)線性可分的模式類，三類的訓(xùn)練樣本分別為 ① 若 則權(quán)向量不變； ? ? ? ? Mjijkdkdji ,2,1。, ?????? ? ? ? Mjkk jj ,2,1,1 ???? WW( ) ( )kdkd li ≤? ? ? ? ? ? T33T22T11 1,11,10,0 ??? XXX ：；：；： ???現(xiàn)采用多類情況 3的方式分類，試用感知器算法求出判別函數(shù)。 解：增廣向量形式： ? ? ? ? ? ? T3T2T1 1 , 1,1,1 , 1,1,1,0,0 ??? XXX注意，這里任一類的樣本都不能乘以（－ 1）。 任取初始權(quán)向量 T321 ]0,0,0[)1()1()1( ??? WWW ； c=1 第一次迭代： ? ? ? ? 0111T11 ?? XWd? ? ? ? 011 1T22 ?? XWd? ? ? ? 011 1T33 ?? XWd三個(gè)權(quán)向量都需要修改： 11 ??X ? ? ? ?11 21 dd ? ? ? ? ?11 31 dd ?，但 且 不成立， ? ? T111 1,0,0)1()2( ??? XWW? ? T122 1,0,0)1()2( ?? XWW? ? T133 1,0,0)1()2( ?? XWW第二次迭代： ? ? ? ? 1222T11 ?? XWd? ? ? ? 122 2T22 ?? XWd? ? ? ? 122 2T33 ?? XWd22 ??X ? ? ? ?22 12 dd ? ? ? ? ?22 32 dd ?，但 且 不成立，修改權(quán)向量： ? ? T211 0,1,1)2()3( ?? XWW? ? T222 0,1,1)2()3( ??? XWW? ? T233 2,1,1)2()3( ?? XWW