模式識別第二章DiscriminantFunction

1、 2.1判別函數(shù) 2.2Fisher線性判別 2.3感知器準則函數(shù) 2.4最小平方誤差準則和最小錯分樣本準則 2.5分段線性判別函數(shù) 2.6二次判別函數(shù)第二章 判別函數(shù)2.1 判別函數(shù)v假設對一模式X已抽取n個特征，表示為：v模式識別問題就是根據(jù)模式X X的n n個特征來判別模式屬于1 ,2 , , m 類中的那一類。維空間的一個向量是n),.,(321XxxxxXTn2.1 判別函數(shù)v例如下圖：三類的分類問題，它們的邊界線就是一個判別函數(shù)123邊界2x1xv判別函數(shù)包含兩類：v一類 是線性判別函數(shù)：線性判別函數(shù)廣義線性判別函數(shù) （所謂廣義線性判別函數(shù)就是把非線性判別函數(shù)映射到另外一個空間變成

2、線性判別函數(shù)）分段線性判別函數(shù)v另一類是非線性判別函數(shù)2.1.1 線性判別函數(shù)v我們現(xiàn)在對兩類問題和多類問題分別進行討論。v(一)兩類問題 即: v v1. 二維情況 ：取兩個特征向量v 這種情況下 判別函數(shù): 2,),(21MTi2,)(2,1nxxxT32211)(wxwxwxg為坐標分量為參數(shù)，21, xxwv在兩類別情況，判別函數(shù) g (x) 具有以下性質：v這是二維情況下判別由判別邊界分類.v情況如圖：21, 0, 0)(xxxgi不定xxg,0)(32211)(wxwxwxg211x2x2. n維情況v現(xiàn)n個特征為：v判別函數(shù)： v另外一種表示方法：Tnxxxx),.,(321x1

3、2211.)(nnnwxwxwxwxg10nTwxW為增廣模式向量。，為增廣權向量，TnnTnnxxxxxwwwwW),.,(),.,(121121xWxgT)(為模式向量。為權向量，TnTnxxxxwwwW),.,(),.,(21210v模式分類：v當 g1(x) =WTx=0 為判別邊界 。當n=2時，二維情況的判別邊界為一直線。當n=3時，判別邊界為一平面，n3時，則判別邊界為一超平面。21,0,0)(xxxWxgT2. n維情況(二) 多類問題v對于多類問題，模式有 1 ,2 , , M 個類別?？煞秩N情況：1。第一種情況：每一模式類與其它模式類間可用單第一種情況：每一模式類與其它模

4、式類間可用單個判別平面把一個類分開。個判別平面把一個類分開。這種情況，M類可有M個判別函數(shù)，且具有以下性質：被稱作： 分法權向量。個判別函數(shù)的為第式中iwwwwWTniiniii),.,()1(21ii。其它MixxWxgiTii,.,2 , 1, 0, 0)(v右圖所示，每一類別可用單個判別邊界與其它類別相分開 。v如果一模式X屬于1，則由圖可清楚看出:這時g1(x) 0而g2(x) 0 ， g3(x) 0 , g2(x) 0 , g3(x) 0 。則此模式X就無法作出確切的判決。如圖中 IR1,IR3，IR4區(qū)域。v另一種情況是IR2區(qū)域，判別函數(shù)都為負值。IR1，IR2，IR3，IR4。

5、都為不確 定區(qū)域。1.1.第一種情況（續(xù)）第一種情況（續(xù)）30)(0)(0)(321xgxgxg12000321)x(g)x(g)x(g0)(0)(0)(321xgxgxg 4IR3IR1IR2IR1x2x0)(1xg0)(2xg0)(3xg551v問當x=(x1,x2)T=(6,5)T時屬于那一類v結論： g1(x) 0 , g3(x) g2(x) 和 g1(x) g3(x) 。v假設判別函數(shù)為：v則判別邊界為：3.第三種情況（續(xù)）23212211)(1)()(xxgxxxgxxxg012)()(02)()(012)()(21322131121xxxgxgxxxgxgxxgxg2)()(21

6、xgxg)()(32xgxg)()(31xgxg13v結論：不確定區(qū)間沒有了，所以這種是最好情況。v用上列方程組作圖如下：3.第三種情況（續(xù)）1)()()()(3121xgxgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32xgxg0)()(21xgxg0)()(31xgxg0.15.05.0v問假設未知模式 x = (x1,x2)T= (1,1)T ，判斷x屬于那一類。v把它代入判別函數(shù)：v得判別函數(shù)為：v因為v所以模式x= (1,1)T屬于 類。3. 第三種情況（續(xù)）2)()(),()(1232xgxgxgxg1)(, 1)(, 0

7、)(321xgxgxg).(),(),(321xgxgxg1)()()()(3121xgxgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32xgxg0)()(21xgxg0)()(31xgxg0.15.05.0NOTE: （1）判別函數(shù)在特征空間中表現(xiàn)出的是某條直線(平面、超平面），這條直線由判別函數(shù)的方程決定的。模式類別在空間的分布是確定的，模式類的分布與直線的相對關系不同從而導致會出現(xiàn)前面介紹的三類情況。 NOTE: （2）如前面所介紹，其正負標記完全是由求解 得來的。對于二維情況，滿足大于0的（x1，x2）的區(qū)域標記為正，小于0的

8、（x1，x2）的區(qū)域標記為負。21, 0, 0)(xxxwxdt如如2.1.2 模式空間和權空間 統(tǒng)一判別形式 判別函數(shù)d(x)=wtx, 其中w,x為增廣向量。Wtx0為分類的判別界面。通常 i, 0)(xxwxdt則j, 0)(xxwxdt則j, 0)()(xxwxdt則i, 0)(xxwxdt則對兩類問題的等價預處理，使之具有統(tǒng)一的判斷形式。對兩類問題的等價預處理，使之具有統(tǒng)一的判斷形式。同時研究判別函數(shù)（判別界面在空間中的特性與類的同時研究判別函數(shù)（判別界面在空間中的特性與類的位置）空間位置）空間(1) 增廣空間和非增廣空間增廣空間和非增廣空間(2)模式空間和權空間模式空間和權空間2.

9、1.2 模式空間和權空間 模式空間 對一個線性方程w1x1+w2x2+w3x3=0，它在三維空間(x1 x2 x3)中是一個平面方程式，w=(w1 w2 w3)T是方程的系數(shù)。 把w向量作為該平面的法線向量，則該線性方程決定的平面通過原點且與w垂直。 模式空間 若x是二維模式增廣后的向量，此時x3=1判別函數(shù)是下列聯(lián)立方程的解 w1x1+w2x2+w3 x3 =0 x3=1即為這兩個平面相交的直線AB 此時， 在非增廣的模式空間中即為x1, x2 二維坐標， w =(w1 w2)T為非增廣的權向量，它與直線AB垂直；AB將平面分為正、負兩側，w離開直線的一側為正， w射向直線的一側為負。模式空

10、間增廣向量決定的平面(a) 非增廣向量決定的直線 權空間 若將方程x1w1+x2w2+w3=0繪在權向量w=(w1 w2 w3)T的三維空間中，則x=(x1 x2 1)T為方程的系數(shù)。 若以x向量作為法線向量，則該線性方程所決定的平面為通過原點且與法線向量垂直的平面，它同樣將權空間劃分為正、負兩邊。 在系數(shù)x不變的條件下， 若w值落在法線向量離開平面的一邊，則wTx0 若w值落在法線向量射向平面的一邊，則wTx 0,W指向1，為H的正側，反之為H的負側.上矢量一定在HxxxxWwxWwxWTnTnT)( , 0)(021211211W1x2X1X2xH12g(x)0g(x)n則分類界面在x*中

11、是線性的，在x中是非線性的，此時只要將模式x進行非線性變換，使之變換后得到維數(shù)更高的模式x*，就可以用線性判別函數(shù)來進行分類kixfwwxfwxfwxfwxgkiiikkk,.,2 , 1, )()(.)()()(1112211v這樣一個非線性判別函數(shù)通過映射，變換成線性判別函數(shù)。1)(,)(1xfxfki是單值函數(shù)式中v判別函數(shù)的一般形式：2111,0,0)()()(xxYgYWxfwxgTyxkiii空間變換空間0YWT判別平面：)( ,)(.)()()( ,., 0, 0)()()(21212111增廣模式向量。廣義權向量其中：空間變換空間xfxfxfYwwwWxxYgYWxfwxgkk

12、Tyxkiii21,xaxbxbxorax則則0bax二次判別函數(shù)1212321212123211,0,0)()(,0,0)(xxYaaaWxxYgYWxgxxxaxaaxgT映射：v要用二次判別函數(shù)才可把二類分開：)1 , 1, 1 ()25.0 , 5 .0 , 1 (),0 , 0 , 1 (321YYY05 .011y3y2yW平面oYWTx121015 . 012)(1,2112, 1, 12123212321321YWYxxxxxgyyyxxYaaaWaaayT空間判別平面：即：空間它的判別邊界：設討論在推出v從圖可以看出：在陰影上面是1類，在陰影下面是2類，v結論：在X空間的非線

13、性判別函數(shù)通過變換到Y空間成為線性的，但X變?yōu)楦呔S空間05 .011y3y2yW平面oYWTx1212.1.5 設計線性分類器的步驟 就是用標有類別的樣本去訓練分類器，分類器有線性判別函數(shù)的性質。只是參數(shù)未知。 其實就是找到最佳W的過程 所以線性分類器設計過程： 1.得到標有類別的樣本，確定線性分類器的維數(shù)。 2.根據(jù)實際情況選擇準則函數(shù)J，要求： J能反映分類器的性能，它的極值對應“最好”的決策 J是樣本集、W的函數(shù) 3.利用最優(yōu)技術得到準則函數(shù)的極值解：分類器設計好以后，對于未知類別的樣本x，我們就計算g(x)，然后根據(jù)判別式得到x的類別*W 我們后面講的都是線性分類器的設計方法： 包括

14、Fisher準則 感知器準則 最小均方誤差準則 最小錯分樣本數(shù)準則2.2 Fisher線性判別 考慮將樣本的維數(shù)降到1維，那么如果可以找到一個最好的投影線，那么在一維上我們可以找出那個分界點來做分類。 若 ，則g(x)就是x在W方向上的投影。)(,)()()(021WWWrWxgrWrWWWrWWrWrWxgwxWHpTTTTnpT是投影的絕對值上。在因為11)()(npTnTwrxWwxWxg1nTpTwrWxW1W 假設對于兩類問題d維的樣本，共有N個，其中2211HNHN21我們記為合個樣本，這些樣本的集類有；同樣合我們記為個樣本，這些樣本的集類有Nnyn,21，性變換得到標量：我們對所

15、有的樣本做線xwt 我們現(xiàn)在已知判別函數(shù)的形式，下來就是怎么求準則函數(shù)，以及最優(yōu)化問題。 在定義fisher的準則函數(shù)之前，我們先定義幾個必要的基本參量： 1.d維的X空間 1）iHxiiiixN1mm21，各類樣本的均值向量 2） 3） 4）iHxiiiiim-(xm-(xSS21)，類內(nèi)離散度矩陣t21wwSSSS總類內(nèi)離散度矩陣t)2121bbm-(mm-(mSS類間離散度矩陣 2.在一維Y空間 1） 2） 3）iyyiiiiyN1mm21，各類樣本的均值向量iyyi2i2iim-(ySS21)2，類內(nèi)離散度矩陣2221wwSSSS總類內(nèi)離散度矩陣現(xiàn)在我們定義fisher的準則函數(shù)：上式

16、并不是w的顯式函數(shù)，我們將它改寫222121SSm-m()(2wJFitHxitHxtiyyiimwxN1wxwN1yN1miii)(其中wSwwwtttbt2121t2121wmmmmwmmm-m()()()22所以分子wSwm-(xm-(xwmw-x(wm-(ySitixxitxxittyyi2iiiiwt)22wSw)wSSwSSwt21t2221(所以分母wSwwwtbtwSwJF)(*)(w最大值時的下面我們求使wJF 用lagrange乘子法求解 令*b1-w*w*bwbwtbtwtwwSS0wS-wSwS-wSw)L(w,c)-wS(w-wSw)L(w,0cwSw)()()()(

17、)()(*211-w*211-w*211-w*b1-w*21212121*bmmSwmmSRwRmmSwSSwmm RRmmmmmmwS所以標量對方向沒有影響。找方向，為一個標量，我們只是wwtt閾值才能判斷類別我們還需要一個一維的降到一維以后，現(xiàn)在我們已把一個n維的問題轉化為一維的問題?，F(xiàn)在一維空間設計 Fisher分類器:W0的選擇 2010XWXWYXWXWYTT2.1210YYW2121212102122.2NNXWNXWNNNYNYNWTT Yki表示第i類中第k個樣本的投影值 N1為1樣本數(shù) N2為2樣本數(shù) 當W0選定后，對任一樣本X，只要判斷Y=WTX W0 則X1; Y=WTX

18、 W0 則X2。分類問題就解決了NYYNYYNYYYYYWkkkkkk2211111211221121120)(.32.3 感知器準則函數(shù)2.3.1 幾個基本概念1.線性可分性：v一組模式樣本不一定是線性可分的，所以需要研究線性分類能力的方法，對任何容量為N的樣本集，線性可分的概率多大呢？v（如下圖（a），線性不可分）v例：4個樣本有幾種分法。v圖（b）直線把x1分開，每條直線可把4個樣本分成1 2 類，4個樣本分成二類的總的可能的分法為24=16類，其中有二種是不能用線性分類實現(xiàn)的線性可分的是14。即概率為14/16。（a）x1x2x3x4 （b）v結論：N個樣品線性可分數(shù)目(條件：樣本分布

19、良好）：為特征數(shù)為樣本數(shù)其中nNkNkNCkN,)!1( !)!1(1nkkNNnNCnNnND011,21,2),(若若v對N和n各種組合的D(N,n)值，表示在下表中，從表中可看出，當N，n緩慢增加時D(N,n)卻增加很快。1234561222222244444436888884814161616165102230323232n),(nNDNnkkNNNnNCnNnNDnNP0111,21, 12),(),(若若v線性可分概率：),(nNP0 .15 .00543211n5n15nn1nN強。說明樣本少時二分能力范圍，即在。時，線性可分概率為時，即值，對于任意。處出現(xiàn)明顯的門限效應時，曲線

20、急劇下降，在由當, 1),(),1(22: )(21),() 1(22: )(21: )(nNPnNcnNPnNnbnav把上式用曲線表示成下圖：圖中橫坐標用=N/n+1表示。v由圖討論：.2),1(2: )(,),1(22: )(0是最好情況即二分能力）的估計：個樣本的線性可分性（對多線性可分能力越差。說明樣本越線性可分概率急劇下降范圍，即在nNNenNdv結論：在實際工作中，分類的訓練非常重要，由已知樣本來訓練。因為已知樣本有限，而未知樣本無限。選擇已知類別的訓練樣本數(shù)方法如下：),(nNP0 .15 .00543211n5n15nn1nNv：如果訓練樣本N RT 其中RT為響應閾值定義感

21、知準則函數(shù)：只考慮錯分樣本定義： 其中x0為錯分樣本當分類發(fā)生錯誤時就有WTX 0, 所以J(W) 總是正值，錯誤分類愈少， J(W)就愈小。理想情況為 即求最小值的問題。0)(XXXWWJT0)(WJ 感知器準則求最優(yōu)方法： 1.錯誤分類修正wk 如wkTx0并且x1 wk+1= wk+ kx 如wkTx0并且x2 wk+1= wk- kx 2.正確分類 ，wk不修正 如wkTx0并且x1 如wkTx0并且x2 wk+1= wk 感知器的訓練算法 感知器算法實質上是一種賞罰過程 對正確分類的模式則“賞”，實際上是“不罰”，即權向量不變。 對錯誤分類的模式則“罰”，使w(k)加上一個正比于xk

22、的分量。 當用全部模式樣本訓練過一輪以后，只要有一個模式是判別錯誤的，則需要進行下一輪迭代，即用全部模式樣本再訓練一次。 如此不斷反復直到全部模式樣本進行訓練都能得到正確的分類結果為止。（1） 給定兩個訓練模式集合，分屬于和類1 2 ，初始向量為W(1)。并將特征向量寫成增增廣形式廣形式，將屬于類2的訓練樣本全部乘以（1）。得到新的樣本集合A， NOTE：本過程實際上是預處理，使后續(xù)修正判斷具有統(tǒng)一的表達形式，該預處理，并不改變樣本的分類結果。 （2）錯誤分類修正wk 如wkTx0 wk+1= wk+ kx 如wkTx0 wk+1= wk （3）用全部樣本訓練過一次以后，如果有一個樣本的判別是

23、錯誤的，則繼續(xù)進行下一輪，直到全部的樣本都能正確分類為止。 k選擇準則 固定增量原則 k固定非負數(shù) =1 絕對修正規(guī)則 k 部分修正規(guī)則 k= 02xxxwTT|xxxwTT|例題：有兩類樣本 解：先求四個樣本的增值模式,并對第二類樣本乘以-1假設初始權向量 k=1第一次迭代： w1Tx1=(1,1,1,1) (1,0,1,1)T=30 所以不修正 w1Tx2=(1,1,1,1) (0,1,1,1)T=30 所以不修正 w1Tx3=(1,1,1,1) (-1,-1,0,-1)T=-30求解，首先定義準則函數(shù)(目標函數(shù))J(W)，再求J(W)的極值使W優(yōu)化。因此求解權向量的問題就轉化為對一標量函

24、數(shù)求極值的問題。解決此類問題的方法是梯度下降法。方法就是從起始值W1開始，算出W1處目標函數(shù)的梯度矢量J(W1)，則下一步的w值為：W2 = W1-1J(W1)W1為起始權向量 1為迭代步長 J(W1) 為目標函數(shù)J(W1)為W1處的目標函數(shù)的梯度矢量在第K步的時候Wk+1 = Wk-kJ(Wk) k為正比例因子這就是梯度下降法的迭代公式。這樣一步步迭代就可以收斂于解矢量，k取值很重要 k太大，迭代太快，引起振蕩，甚至發(fā)散。 k太小，迭代太慢。 應該選最佳k。選最佳選最佳k 目標函數(shù)J(W)二階泰勒級數(shù)展開式為 J(W)J(Wk)+ JT(W- Wk)+(W- Wk)TD(W- Wk)T/2

25、其中D為當W = Wk時 J(W)的二階偏導數(shù)矩陣 將W=Wk+1 = Wk-kJ(Wk)代入式得： J(Wk+1) J(Wk)- k|J|2+ 0.5k2JT DJ 其中J=J(Wk) 對k求導數(shù) ，并令導數(shù)為零有 最佳步長為k=|J|2/JTDJ這就是最佳k的計算公式，但因二階偏導數(shù)矩陣D的計算量太大，因此此公式很少用。 若令W=Wk+1 式為J(Wk+1)=J(Wk)+JT(Wk+1-Wk)+(Wk+1-Wk)TD(Wk+1-Wk)T/2 對Wk+1求導，并令導數(shù)為零可得：最佳迭代公式：Wk+1= Wk- D-1J 牛頓法的迭代公式 D-1是D的逆陣討論：牛頓法比梯度法收斂的更快，但是D

26、的計算量大并且要計算D-1。當D為奇異時，無法用牛頓法。求最小值對W求梯度代入迭代公式中Wk+1 = Wk-kJ 由J(W)經(jīng)第K+1次迭代的時候，J(W)趨于0，收斂于所求的W值0)(XXXWWJJ01XXXWWkkk即感知器迭代公式：0)(XXXWWJT最小值的問題對于感知器算法求W的訓練過程：例如:x1, x2, x31 作 x1, x3的垂直線可得解區(qū)(如圖) 假設起始權向量w1=0 k = 1 1. x1, x2, x3三個矢量相加得矢量2,垂直于矢量2的超平面H將x3錯分. 2. x3與矢量2相加得矢量3,垂直于矢量3的超平面H1,將x1錯分. 3.依上法得矢量4,垂直于矢量4做超

27、平面, H2將x3錯分 4. x3與矢量4相加得矢量5,矢量5在解區(qū)內(nèi),垂直于矢量5的超平面可以把 x1, x2, x3分成一類 。x1x2x32H3H14H25W區(qū)間2.4 最小平方誤差準則(MSE法)-非迭代法前面我們研究了線性不等式方程組g(x) =WTX0的解法。它們共同點是企圖找一個權向量W，使錯分樣本最小?，F(xiàn)在我們把不等式組變成如下形式：WTXi=bi0 則有聯(lián)立方程XW=b 這是矛盾方程組，方程數(shù)大于未知數(shù)，所以沒有精確解的存在。NnNNnNXXXXXXXXXXX.21211121121變換后的值是增廣并乘令) 1(,XXTN . 2,1,XXX給定的任意正常數(shù)N . 2,1,b

28、bbTb 每個樣本有n-1個特征定義誤差向量：e=XW-b0 把平方誤差作為目標函數(shù) W的優(yōu)化就是使J(W)最小。求J(W)的梯度并為0。解上方程得 XTXW=XTb這樣把求解XW=b的問題，轉化為對XTXW=XTb求解，這一有名的方程最大好處是因XTX是方陣且通常是非奇異的，所以可以得到W的唯一解。 NiiitbXWbXWeWJ1222)(|)(MSE準則函數(shù) 0)(2)(21bXWXXbXWTiNiiitJ(W)只要計算出 就可以得到W取： 最小平方誤差法同F(xiàn)isher法是一致的。 bXbXXXTWT1的偽逆（規(guī)范矩陣）稱為其中XXXXTXT1221.1/./NNNNNNNNb（MSE 解

29、）其中N/N1有N1個，N/N2有N2個X2.4.1 何卡氏法(Ho-Kashyap) 若訓練樣本線性可分時，感知器法可求出界面，但對不可分問題不收斂只能取平均。最小平方誤差法不論樣本是否線性可分都能給出一加權矢量，但不能保證此矢量就是分界矢量，下面介紹一種方法一種方法可以檢測迭代過程中是否線性可分可以檢測迭代過程中是否線性可分。我們的目的是求解XW=b ，前面的最小均方誤差法使用的統(tǒng)一的一個b,我們可以在每一步用不同的最優(yōu)的b，讓收斂速度加快。定義：則每次采用最優(yōu)的b，則還應該滿足每次b的每個分量應該大于0NiiitbXWWJ12)()(21)(21)(bXWbXWtbXbXXXWTT*1)

30、()() 1(kbbbJckbkb采用梯度法 因為XW=b b應為正值 c為矯正系數(shù)，一個正值 當（XWk-bk）0 時 當（XWk-bk） 0 時|kkkkkbXWbXWcbb的增量為kkkbbkkbbbJcbbb)(1前后兩次迭代后，對的增量為其中bbk0kb2kkkbXWcb 引入誤差矢量ek ek=XWk-bk判斷是否線性可分 所以J(W)的解為 初始條件 W1=X+b1并且b10 迭代時檢測 如果ek=0時，XW=b，系統(tǒng)線性可分，迭代收斂 如果ek0時，XW b0，系統(tǒng)線性可分，迭代收斂,可繼續(xù)迭代，使ek趨于0 如果ek全為非正，但不全為0，系統(tǒng)線性不可分，迭代不收斂 我們用下面

31、的例子來說明ek的作用|kkkeecb|11kKkkKkKKkeeXcWbXbXbbXbXW因此上式可以寫成 例題： 1=(0,0)T,(0,1)T 2=(1,0)T,(1,1)T 解：正規(guī)化 對2取負，有 111101110100X2/12/12/12/311111111211XXXTXTX的偽逆為x2x1x1x2x3x4取b1=(1,1,1,1)T c=1 W1=X+b1=(-2,0,1)T 所以W1為所求解 e1=XW1-b1=0 系統(tǒng)線性可分01111102111101110100, , ,1TWX因為 若四個樣本變成：1=(0,0)T,(1,1)T 2=(0,1)T,(1,0)T解： 取b1=(1,1,1,1)T c=1 W1=X+b1=(0,0,0)T e1=XW1-b1=(-1,-1,-1,-1)TWi n (k)t xj i =1,2,M n =1,2,Li子類 ij 即