模式識別導(dǎo)論本(三)

1、模式識別導(dǎo)論線性判別函數(shù)與廣義線性判別函數(shù)廣義線性判別函數(shù)的二分能力感知器算法最小平方誤差算法多類模式的分類器迭代算法勢函數(shù)法簡介第三講 判別函數(shù)與確定性分類器 模式識別導(dǎo)論假設(shè)對一模式X已抽取n個特征，表示為：模式識別問題就是根據(jù)模式X X的n n個特征來判別模式屬于1 ,2 , , m 類中的那一類。由于特征向量對應(yīng)于特征空間中的一個點(diǎn)，同類點(diǎn)聚集在一起，因此可以將特征空間分成若干個區(qū)域。線性判別函數(shù)與廣義線性判別函數(shù) 維空間的一個向量是n),.,(321XxxxxXTn模式識別導(dǎo)論例如下圖：三類的分類問題，它們的邊界線就是一個判別函數(shù)。如果該函數(shù)為線性函數(shù)，則線性可分123邊界2x1x模

2、式識別導(dǎo)論判別函數(shù)包含兩類：一類 是線性判別函數(shù)：線性判別函數(shù)廣義線性判別函數(shù)（所謂廣義線性判別函數(shù)就是把非線性判別函數(shù)映射到另外一個空間變成線性判別函數(shù)）分段線性判別函數(shù)另一類是非線性判別函數(shù)模式識別導(dǎo)論我們現(xiàn)在對兩類問題和多類問題分別進(jìn)行討論。(一)兩類問題 即: 1. 二維情況 ：取兩個特征向量 這種情況下 判別函數(shù):2,),(21MTi2,)(2,1nxxXT32211)(wxwxwxg為坐標(biāo)向量為參數(shù)，21, xxw模式識別導(dǎo)論在兩類別情況，判別函數(shù) g (x) 具有以下性質(zhì)：這是二維情況下判別由判別邊界分類.情況如圖：1. 二維情況21, 0, 0)(XXxgi不定Xxg,0)(3

3、2211)(wxwxwxg211x2x模式識別導(dǎo)論2. n維情況現(xiàn)抽取n個特征為：判別函數(shù)： 另外一種表示方法：TnxxxxX),.,(32112211.)(nnnwxwxwxwxg10nTwXW為增值模式向量。，為增值權(quán)向量，TnnTnnxxxxXwwwwW) 1,.,(),.,(21121XWxgT)(為模式向量。為權(quán)向量，TnTnxxxXwwwW),.,(),.,(21210模式識別導(dǎo)論模式分類：當(dāng) g1(x) =WTX=0 為判別邊界 。當(dāng)n=2時，二維情況的判別邊界為一直線。當(dāng)n=3時，判別邊界為一平面，n3時，則判別邊界為一超平面。21,0,0)(xxXWxgT2. n維情況模式識

4、別導(dǎo)論(二) 多類問題iiTiiXXXWxg, 0, 0)(對于多類問題，模式有 1 ,2 , , m 個類別?？煞秩N情況：1。第一種情況：每一模式類與其它模式類間可用單個判第一種情況：每一模式類與其它模式類間可用單個判別平面把一個類分開別平面把一個類分開( (絕對可分絕對可分) )。這種情況，M類問題轉(zhuǎn)化為M1個兩類問題需建立M1個判別函數(shù)，且每個具有以下性質(zhì)：權(quán)向量。個判別函數(shù)的為第式中iwwwwWTininiii) ,.,(121模式識別導(dǎo)論判別界面 將特征空間分劃成兩個子空間，其中一個包含 ，另一個不包含 ，同樣， 也將特征空間分成兩個子空間，其中一個包含 另一個不包含。由這兩個界面

5、分劃的分別包含i和j類的子區(qū)域可能有部分重疊，落在重疊區(qū)的點(diǎn)不能由這兩個判別函數(shù)決定使用這類判別函數(shù)，可能會出現(xiàn)兩個或兩個以上的判別式都大于零或者所有判別式都小于零的情況。出現(xiàn)在這些區(qū)域中的點(diǎn)，不能有判別式判別屬于哪一類。gi(x)0只說明x是在包含i類的半空間中，而這個半空間可能還有其他類別存在i)(xgii)(jxgj模式識別導(dǎo)論如圖所示，每一類別可用單個判別邊界與其它類別相分開 。如果一模式X屬于1，則由圖可清楚看出:這時g1(x) 0而g2(x) 0 ， g3(x) 0 。 1 類與其它類之間的邊界由 g1(x)=0確定. 21x 0)(2xg0)(3xg2x0)(1xg13判別規(guī)則：

6、判別規(guī)則：如果如果則則 ijxgxgji, 0)(0)(ix模式識別導(dǎo)論1)(5)()(23212211xxgxxxgxxxg例：已知三類1,2,3的判別函數(shù)分別為：因此三個判別邊界為：01)(05)(0)(23212211xxgxxxgxxxg模式識別導(dǎo)論v作圖如下：30)(0)(0)(321xgxgxg120)(0)(0)(321xgxgxg0)(0)(0)(321xgxgxg 4IR3IR1IR2IR1x2x0)(1xg0)(2xg0)(3xg551模式識別導(dǎo)論問當(dāng)x=(x1,x2)T=(6,5)T時屬于那一類結(jié)論： g1(x) 0 ， g3(x) 0所以它屬于2類:代入判別函數(shù)方程組1

7、)(5)()(23212211xxgxxxgxxxg.4)(,6)(, 1)(321xgxgxg得：模式識別導(dǎo)論這樣 有 M(M _ 1)/2個判別平面。對于兩類問題，M=2，則有一個判別平面。同理，三類問題則有三個判別平面。判別函數(shù)： 判別邊界：性質(zhì)：第二種情況：第二種情況：XWxgTijij)(0)(xgij任意兩類間可分別用判別平面分開（成對可分）。20)(12xg0)(23xg0)(13xg 3 10,( )0,iTijijjxgxw xx若若模式識別導(dǎo)論但是判別函數(shù)的正負(fù)不能做出x屬于i類還是j類，只能做出x是位于含有i類的半空間中還是位于j類的半空間中，因在某個半空間中可能還有其他

8、類別的存在。因此這種方法的決策規(guī)則是iijxijxg那么如果, 0)(模式識別導(dǎo)論0)(03)(05)(21231132112xxxgxxgxxxg21231132112)(3)(5)(xxxgxxgxxxg假設(shè)判別函數(shù)為：判別邊界為：用方程式作圖：0,023212gg判別區(qū)012)x(g 023)x(g013)x(g 5531x0032313gg判別區(qū)0031121gg判別區(qū)2x模式識別導(dǎo)論問:未知模式X=(x1,x2)T=(4,3)T屬于那一類代入判別函數(shù)可得:把下標(biāo)對換可得:因為結(jié)論：所以X 屬于3類結(jié)論：判別區(qū)間增大，不確定 區(qū)間減小，比第一種情況小的多.1)(, 1)(,2)(231

9、312xgxgxg1)(, 1)(, 2)(323121xgxgxg0)(3xgj0023122gg判別區(qū)0031121gg判別區(qū)0)(12xg 0)(23xg0)(13xg 5530032313gg判別區(qū)1x2x模式識別導(dǎo)論廣義線性判別函數(shù)kixfwwxfwxfwxfwxgkiiikkk,.,2 , 1, )()(.)()()(1112211這樣一個非線性判別函數(shù)通過映射，變換成線性判別函數(shù)。1)(,)(1xfxfki是單值函數(shù)式中判別函數(shù)的一般形式：2111,0,0)()()(xxYgYWxfwxgTyxkiii空間變換空間模式識別導(dǎo)論0YWT判別平面：)( ,)(.)()()( ,.,

10、0, 0)()()(21212111增廣模式向量。廣義權(quán)向量其中：空間變換空間xfxfxfYwwwWxxYgYWxfwxgkkTyxkiii21,則,則xa orxbxbxax例：如右圖。0bax二次判別函數(shù)212模式識別導(dǎo)論2321212123211,0,0)()(,0,0)(xxYaaaWxxYgYWxgxxxaxaaxgT映射：要用二次判別函數(shù)才可把二類分開：)1 , 1, 1()25.0 ,5 .0 , 1(),0 ,0 , 1(321yyy05 .011y3y2yW平面oYWT212x模式識別導(dǎo)論015 . 012)(1,2112, 1, 12123212321321YWYxxxxx

11、gyyyxxYaaaWaaaxT空間判別平面：即：空間它的判別邊界：設(shè)討論在推出從圖可以看出：在陰影上面是1類，在陰影下面是2類，結(jié)論：在X空間的非線性判別函數(shù)通過變換到Y(jié)空間成為線性的，但X變?yōu)楦呔S空間05.011y3y2yW平面oYWT212x模式識別導(dǎo)論一組模式樣本不一定是線性可分的，所以需要研究線性分類能力的方法，對任何容量為N的樣本集，線性可分的概率多大呢？（如下圖（a），線性不可分）例：4個樣本有幾種分法。圖（b）直線把x1分開，每條直線可把4個樣本分成1 2 類，4個樣本分成二類的總的可能的分法為24=16類，其中有二種是不能用線性分類實現(xiàn)的線性可分的是14。即概率為14/16。

12、二分法能力（a）x1x2x3x4 （b）模式識別導(dǎo)論結(jié)論：N個樣品線性可分?jǐn)?shù)目(條件：樣本分布良好）：為特征數(shù)為樣本數(shù)其中nNkNkNCkN,)!1( !)!1(1nkkNNnNCnNnND011,21,2),(若若對N和n各種組合的D(N,n)值，表示在下表中，從表中可看出，當(dāng)N，n緩慢增加時D(N,n)卻增加很快。模式識別導(dǎo)論1234561222222244444436888884814161616165102230323232二分法能力（續(xù)）n),(nNDNnkkNNNnNCnNnNDnNP0111,21, 12),(),(若若線性可分概率：模式識別導(dǎo)論),(nNP0 . 15 . 00

13、543211n5n15nn1nN強(qiáng)。說明樣本少時二分能力范圍，即在。時，線性可分概率為時，即值，對于任意。處出現(xiàn)明顯的門限效應(yīng)時，曲線急劇下降，在由當(dāng), 1),(),1(22: )(21),() 1(22: )(21: )(nNPnNcnNPnNnbna把上式用曲線表示成下圖：圖中橫坐標(biāo)用=N/n+1表示。由圖討論：模式識別導(dǎo)論( ): 在2范圍，即2 (1),線性可分概率急劇下降,說明樣品越多線性可分能力越差。dNn),(nNP0 . 15 .00543211n5n15nn1nN結(jié)論：在實際工作中，分類的訓(xùn)練非常重要，由已知樣本來訓(xùn)練。因為已知樣本有限，而未知樣本無限。選擇已知類別的訓(xùn)練樣本

14、數(shù)方法如下：模式識別導(dǎo)論：如果訓(xùn)練樣本N 0 所以不修正 w1Tx2=(1,1,1,1) (0,1,1,1)T=30 所以不修正 w1Tx3=(1,1,1,1) (1,1,0,1)T=30 所以修正w1 w2=w1-x3=(0,0,1,0) w2Tx4=(0,0,1,0)T (0,1,0,1) =0 所以修正w2 w3=w2-x4=(0,-1,1,-1)第一次迭代后,權(quán)向量w3=(0,-1,1,-1),再進(jìn)行第2,3,次迭代如下表模式識別導(dǎo)論訓(xùn)練樣本訓(xùn)練樣本修正式修正式修正后的權(quán)值修正后的權(quán)值wk1迭代次數(shù)迭代次數(shù)x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 1

15、+0w1w1w1-x3w2-x41 1 1 11 1 1 10 0 1 00 1 1 -1 1x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 10+0-w3+x1w4w4-x3w51 1 2 01 1 2 00 2 2 10 2 2 -1 2x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 1+-w5w5+x2w6w60 2 2 10 1 3 00 1 3 00 1 3 0 3x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 1+-w6w6w6w60 1 3 00 1 3 00 1 3 00 1 3 0 4

16、ktxkw 直到在一個迭代過程中權(quán)向量相同，訓(xùn)練結(jié)束。w6=w=(0,1,3,0) 判別函數(shù)g(x)= -x2+3x3感知器算法只對線性可分樣本有收斂的解,對非線性可分樣本集會造成訓(xùn)練過程的振蕩,這是它的缺點(diǎn).模式識別導(dǎo)論最小平方誤差準(zhǔn)則(MSE法）前述迭代求解權(quán)向量的方法是在模式集線性可分的情況下采用的。但給出一個模式集往往不能預(yù)先告知是否線性可分，LMSE算法就是針對這一問題對準(zhǔn)則函數(shù)引進(jìn)最小平方誤差而建立起來的，它可以在訓(xùn)練過程中判定訓(xùn)練模式集（樣本集）是否線性可分，因而可以判斷權(quán)向量求解的收斂性。2100 xxwxxwtt對于兩類問題: 模式識別導(dǎo)論如果將屬于2第二式也可寫成與第一式一

17、樣的形式，權(quán)向量的求解問題就成為不等式xw0的求解問題，其中每一模式樣本都寫成增廣向量。的模式乘以（-1），則tntittxxxxx2121w=(w1,w2,wn,wn+1)t模式識別導(dǎo)論若把xw0,改寫為xw=b 其中b=(b1,b2,bn)t，其所有分量都為正值。這與不等式xw0是同一意義，求解不等式等價于求解方程XW=b。對于W的估計量 定義誤差向量：e=XW-b0 把平方誤差作為目標(biāo)函數(shù)模式識別導(dǎo)論 W的優(yōu)化就是使J(W)最小。求J(W)的梯度并為0。解上方程得 XTXW=XTb這樣把求解XW=b的問題，轉(zhuǎn)化為對XTXW=XTb求解，這一有名的方程最大好處是因XTX是方陣且通常是非奇異

18、的，所以可以得到W的唯一解。 |21|)(22bXWeWJMSE準(zhǔn)則函數(shù) 0)(2J(W)bXWXT詳細(xì)推導(dǎo)詳細(xì)推導(dǎo)模式識別導(dǎo)論bXbXXXTWT*1的偽逆（規(guī)范矩陣）稱為其中XXXXTXT1*（MSE 解）所以求解W有賴于b的確定。若對b迭代求解，則 kbkbkb1由于b的所有分量必須為正，故可以這樣定義 0200kbkxwkbkxwckbkxwkb當(dāng)模式識別導(dǎo)論上式中C 為某一校正系數(shù)。該式也可以寫為 kbkxwkbkxwckb引入誤差矢量e(k),即 xw(k)-b(k)=e(k) kekeckb kekecxkwkbxkbxkbkbxkbxkw11模式識別導(dǎo)論于是，當(dāng)給定初值 w(1)=x*b(1) 和 b(1)0以及校正系數(shù)C ，便可根據(jù)上面三個式子進(jìn)行迭代運(yùn)算每一次迭代時計算出來的誤差矢量e(k)是研究樣本集線可分性的重要指標(biāo)。 只有在e(k)0（即其每一分量均為正值或零）時xwb，系統(tǒng)才是線性可