【正文】 xxdd XX)()( 1331 XX dd ?)()( 2332 XX dd ?類的判決函數(shù)： 1?② 判決界面如圖所示。 1?3?2?(1) 明確概念：線性可分。 3. 小結(jié) (2) 分法的比較： j???? iii 與 對(duì)于 M類模式的分類， 兩分法共需要 M個(gè)判別函數(shù)，但 兩分法需要 M(M1)/2個(gè)。 j??iii ??原因： 一種類別模式的分布要比 M1類模式的分布更為聚集， 分法受到的限制條件少，故線性可分的可能性大。 廣義線性判別函數(shù) 目的： 對(duì)非線性邊界：通過(guò)某映射，把模式空間 X變成 X*，以便 將 X空間中非線性可分的模式集，變成在 X*空間中線性可分的 模式集。 ? ?? ?kifi ,2,1, ??X ? ? 11 ?? Xkffi(X)取什么形式及 d(X)取多少項(xiàng)，取決于非線性邊界的復(fù)雜程度。討論線性判別函數(shù)并不會(huì)失去一般性的意義。 非線性變換可能非常復(fù)雜 。 例 假設(shè) X為二維模式向量， fi(X)選用二次多項(xiàng)式函數(shù)，原判 別函數(shù)為 32211222221122111)( wxwxwxwxxwxwd ??????X? ? 2233* xfx ?? X ? ? 144* xfx ?? X ? ? 255* xfx ?? X? ? 2111* xfx ?? X ? ? 2122* xxfx ?? X定義： d(X)線性化為： ? ? ** T XWX ?d? ? T21222121 1,* xxxxxx?X ? ?T321221211 , ?W即： 廣義線性判別函數(shù)： 線性判別函數(shù)的幾何性質(zhì) 模式空間與超平面 模式空間：以 n維模式向量 X的 n個(gè)分量為坐標(biāo)變量的歐氏空間。 線性分類：用 d(X)進(jìn)行分類，相當(dāng)于用超平面 d(X)=0把模式空 間分成不同的決策區(qū)域。 ? ? 1T0 ??? nwd XWX設(shè)判別函數(shù)： 超平面： ? ? 01T0 ??? ?nwd XWX(1) 模式向量 X1和 X2在超平面上 12T011T0 ?? ??? nn ww XWXW0)( 21T0 ? XXW—— W0是超平面的法向量， 方向由超平面的負(fù)側(cè)指向正側(cè)。有 － O W 0 + X p d ( X ) = 0 x 2 X R x 1 (r) 00WWXRXX rpp ????? ? 1T0 ??? nwd XWX100T0 )()( ???? np wrd WWXWX00T01T0 )( WWWXW rwnp ???? ?0Wr?—— 判別函數(shù) d(X) 正比于點(diǎn) X到超平面的代數(shù)距離。 (3) X在原點(diǎn) 1?? nw010 W?? nwr? ? 1T0 ??? nwd XWX得 —— 超平面的位置由 閾值權(quán) wn+1決定： wn+1 0時(shí)，原點(diǎn)在超平面的正側(cè)； wn+1 0時(shí)，原點(diǎn)在超平面負(fù)側(cè)； wn+1= 0 時(shí) ，超平面通過(guò)原點(diǎn)。 2. 線性分類 判別函數(shù)形式已定，只需確定權(quán)向量。 對(duì)每個(gè)已知的 X， d(X)=0在權(quán)空間確定一個(gè)超平面，共 (p+q)個(gè)。 X： 規(guī)范化增廣樣本向量 。 二分法 二分法（ Dichotomies）：用判別函數(shù) d(X)將給定的 N個(gè)模式 分成兩類的方法。 判別函數(shù)的不同分類能力可以通過(guò)二分法總數(shù)衡量。 若限定用線性判別函數(shù)，并且樣本在模式空間是良好分布 的，可以證明， N個(gè) n維模式用線性判別函數(shù)分成兩類的方法總 數(shù)，即線性二分法總數(shù)為 ??????????nNnNCnNDNnjjN1212),( 01或線性二分法概率： ???????????nNnNCnNDnNPnjjNNN11122),(),( 0 11 只要模式的個(gè)數(shù) N小于或等于增廣模式的維數(shù)（ n+1）， 模式類總是線性可分的， 例： 4個(gè)良好分布的 2維模式，若用線性判別函數(shù)分類 線性二分法總數(shù)： 142)2,4(2014 ?? ??jjCD線性二分法概率： ?? ???201441 872)2,4(jjCP 0 P ( N , n ) )1( ?? nN? 1 2 3 4 5 n= ∞ n= 1 ( 維數(shù) ) n= 5 n= 25 圖 線性二分法的概率 )1(20 ?? nN將 λ=2時(shí)的 N值定義為閾值 N0，稱為二分法能力，即 通過(guò) N0，可以對(duì)任意 N個(gè)樣本的線性可分性進(jìn)行粗略估計(jì)。但是如果從使類間分得較開，同時(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é)果與已知類別信息完全相同的過(guò)程。本節(jié)開始介紹如何通過(guò)各種算法，利用已知類別的模式樣本 訓(xùn)練出權(quán)向量 W。但“賞罰概念（ rewardpunishment concept）” 得到廣泛應(yīng)用。通過(guò)幾何方法將特征空間 分解為對(duì)應(yīng)不同類的子空間，又稱為幾何分類器。 感知器算法步驟： （ 1）選擇 N個(gè)分屬于 ω1和 ω2類的模式樣本構(gòu)成訓(xùn)練樣本集 { X1, …, XN } 構(gòu)成增廣向量形式，并進(jìn)行規(guī)范化處理。迭代次數(shù) k=1 。 分兩種情況，更新權(quán)向量的值： c：正的校正增量。 分類正確時(shí)，對(duì)權(quán)向量“賞” ——這里用“不罰”，即權(quán)向量不變； 分類錯(cuò)誤時(shí)，對(duì)權(quán)向量“罰” ——對(duì)其修改，向正確的方向轉(zhuǎn)換。 可以證明感知器算法是收斂的。 例 已知兩類訓(xùn)練樣本 解：所有樣本 寫成增廣向量形式； 進(jìn)行規(guī)范化處理，屬于 ω2的樣本乘以 (－ 1)。 :1? ? ?T1 0,0?X:2?? ?T2 1,0?X? ?T3 0,1?X ? ?T4 1,1?X任取 W(1)=0，取 c=1，迭代過(guò)程為： 第一輪： ? ? 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)行第二輪迭代。 判別界面 d(X)=0如圖示。 分二種情況修改權(quán)向量： ? ? ? ? Mjkkd jj ,1,T ??? XW② 若第 l個(gè)權(quán)向量使 ，則相應(yīng)的權(quán)向量作調(diào)整，即： ? ? ? ?? ? ? ?? ? ? ??????????????lijkkckkckkjjllii,111WWXWWXWW 可以證明：只要模式類在情況 3判別函數(shù)時(shí)是可分的，則 經(jīng)過(guò)有限次迭代后算法收斂。, ?????? ? ? ? Mjkk jj ,2,1,1 ???? WW( ) ( )kdkd li ≤? ? ? ? ? ? T33T22T11 1,11,10,0 ??? XXX ：；：；： ???現(xiàn)采用多類情況 3的方式分類，試用感知器算法求出判別函數(shù)。 任取初始權(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第三次迭代： 修改為權(quán)向量。 第四次迭代： … … 在第五、六、七迭代中，對(duì)所有三個(gè)樣本都已正確分類。 1. 梯度概念 梯度向量的最重要性質(zhì)之一：指出函數(shù) f 在其自變量增加 時(shí)，增長(zhǎng)最快的方向。 ——梯度算法的依據(jù)。將兩類樣本分開的判決函數(shù) d(X)應(yīng)滿足： 梯度算法的目的仍然是求一個(gè)滿足上述條件的權(quán)向量， 主導(dǎo) 思想是將聯(lián)立不等式求解 W的問(wèn)題，轉(zhuǎn)換成求準(zhǔn)則函數(shù)極小值的 問(wèn)題。 用負(fù)梯度向量的值對(duì)權(quán)向量 W進(jìn)行修正，實(shí)現(xiàn)使準(zhǔn)則函數(shù)達(dá) 到極小值的目的。一般關(guān)系表示成從 W(k)導(dǎo)出 W(k+1)： 其中 c是正的比例因子。 權(quán)向量修正為： ? ?)(?,?)(?kiJkJWWWXW??? ? ? ? )(1 kJckk ??? WW迭代次數(shù) k加 1，輸入下一個(gè)訓(xùn)練樣本，計(jì)算新的權(quán)向量，直至對(duì)全部訓(xùn)練樣本完成一輪迭代。否則， W不再變化，算法收斂。設(shè)第 k次迭代時(shí)輸入樣本為 Xi，此時(shí) 已有權(quán)向量 W(k)，求 ： )(kJ