模式識別-第5章線性判別函數(shù)

第五章線性判別函數(shù)5.1線性判別函數(shù)和判別界面線性不可分情況線性判別函數(shù)x=(x1,x2,…,xd)t:特征矢量；w=(w1,w2,…,wd)t:權(quán)矢量；w0：偏置(bias)。線性判別函數(shù)的增廣形式y(tǒng)=(1,x1,x2,…,xd)t:增廣的特征矢量；a=(w0,w1,w2,…,wd)t:增廣的權(quán)矢量；兩類問題線性判別準(zhǔn)則線性分類器的分類界面分類界面的幾何解釋線性分類界面H是d維空間中的一個超平面；分類界面將d維空間分成兩部分，R1，R2分別屬于兩個類別；判別函數(shù)的權(quán)矢量w是一個垂直于分類界面H的矢量，其方向指向區(qū)域R1

；偏置w0與原點到分類界面H的距離有關(guān)：多類問題（情況一）每一類模式可以用一個超平面與其它類別分開；c類問題c個兩類問題，需要c個線性分類界面；第i類與其它類別之間的判別函數(shù)：多類問題（情況一）分類界面多類問題（情況一）判別規(guī)則若存在i，使得gi(x)>0，gj(x)<0，j≠i，則判別x屬于ωi類；其它情況，拒識。多類問題（情況二）每兩個類別之間可以用一個超平面分開；c類問題c(c-1)/2個兩類問題；第i類與第j類之間的判別函數(shù)為：多類問題（情況二）分類界面多類問題（情況二）判別準(zhǔn)則如果對任意j≠i

，有g(shù)ij(x)≥0

，則決策x屬于ωi。其它情況，則拒識。多類問題（情況三）情況三是情況二的特例，不存在拒識區(qū)域。多類問題（情況三）判別函數(shù)c個類別需要c個線性函數(shù)：判別準(zhǔn)則：5.2線性判別函數(shù)的學(xué)習(xí)問題的提出：假設(shè)有一個包含n個樣本的集合y1,y2,…,yn,一些標(biāo)記為ω1,另一些標(biāo)記為ω2，用這些樣本來確定一個判別函數(shù)g(y)=aty的權(quán)矢量a。在線性可分的情況下，希望得到的判別函數(shù)能夠?qū)⑺械挠?xùn)練樣本正確分類；線性不可分的情況下，判別函數(shù)產(chǎn)生錯誤的概率最小。訓(xùn)練樣本的規(guī)范化非規(guī)范化：規(guī)范化：解區(qū)域的幾何解釋(特征空間中）特征空間中：矢量a是垂直于分類界面的矢量：解區(qū)域的幾何解釋(權(quán)空間中）權(quán)空間中，atyi=0是一個通過原點的超平面，yi是法向量，而a是空間中一個點。一般求解方法—梯度下降法求解不等式組采用最優(yōu)化的方法：定義一個準(zhǔn)則函數(shù)J(a)，當(dāng)a是解向量時，J(a)為最??；采用最優(yōu)化方法求解標(biāo)量函數(shù)J(a)的極小值。最優(yōu)化方法采用最多的是梯度下降法，設(shè)定初始權(quán)值矢量a(1)，然后沿梯度的負方向迭代計算：其中η(k)稱為學(xué)習(xí)率，或稱步長。5.3感知器算法(Perceptron)最直觀的準(zhǔn)則函數(shù)定義是最少錯分樣本數(shù)準(zhǔn)則：

JN(a)=樣本集合中被錯誤分類的樣本數(shù)；感知器準(zhǔn)則以錯分樣本到判別界面距離之和作為準(zhǔn)則（感知器準(zhǔn)則）：感知器算法(批量調(diào)整版本)begininitialize,,θ,k0do

kk+1

untilreturnaend感知器算法(單樣本調(diào)整版本)begininitialize,k0dok(k+1)modnifyk

ismisclassifiedbyathenuntilallpatternsproperlyclassifiedreturnaend例5.1有兩類模式的訓(xùn)練樣本：

ω1：{(0,0),(0,1)}

ω2：{(1,0),(1,1)}

用感知器算法求取判別函數(shù)，將兩類樣本分開。感知器算法的特點當(dāng)樣本線性可分情況下，學(xué)習(xí)率合適時，算法具有收斂性；收斂速度較慢；當(dāng)樣本線性不可分情況下，算法不收斂，且無法判斷樣本是否線性可分。5.4最小平方誤差算法(LMSE)LMSE方法的基本思想是將求解線性不等式組的問題轉(zhuǎn)化為求解線性方程組：最小平方誤差的準(zhǔn)則函數(shù)定義誤差矢量e，用e長度的平方作為準(zhǔn)則函數(shù)（LMSE準(zhǔn)則）：權(quán)值矢量的求解(偽逆求解法)稱為偽逆矩陣?yán)?.2有兩類模式的訓(xùn)練樣本：

ω1：{(0,0),(0,1)}

ω2：{(1,0),(1,1)}

用LMSE算法求取判別函數(shù)，將兩類樣本分開。權(quán)值矢量的求解(迭代求解法)begininitializea(0),b,θ,η(?),k0；

dokk+1；

untilreturnaendLMSE算法的特點算法的收斂依靠η(k)的衰減，一般取η(k)=η(1)/k；算法對于線性不可分的訓(xùn)練樣本也能夠收斂于一個均方誤差最小解；取b=1時，當(dāng)樣本數(shù)趨于無窮多時，算法的解以最小均方誤差逼近貝葉斯判別函數(shù)；當(dāng)訓(xùn)練樣本線性可分的情況下，算法未必收斂于一個分類超平面。LMSE算法5.5支持矢量機(SVM,SupportVectorMachine)問題的提出：函數(shù)間隔和幾何間隔函數(shù)間隔：樣本xi到分類界面g(x)=0的函數(shù)間隔定義為：幾何間隔：最優(yōu)分類界面樣本集與分類界面之間的間隔定義為樣本與分類界面之間幾何間隔的最小值。最優(yōu)分類界面：給定線性可分樣本集，能夠?qū)颖痉珠_的最大間隔超平面。支持矢量距離最優(yōu)分類界面最近的這些訓(xùn)練樣本稱為支持矢量；最優(yōu)分類界面完全由支持矢量決定，然而支持矢量的尋找比較困難。SVM的準(zhǔn)則函數(shù)給定兩類問題的線性可分樣本集合{(y1,z1),…,(yn,zn)}，其中z為樣本的類別標(biāo)號：可分性約束：能夠?qū)颖揪€性分開的分類界面滿足： 亦即可以通過調(diào)整權(quán)值w和w0將樣本集合的最小函數(shù)間隔調(diào)整為1。SVM的準(zhǔn)則函數(shù)樣本集到分類界面的幾何間隔：最大，亦即||w||最小，所以SVM可以變?yōu)槿缦碌膬?yōu)化問題：在滿足 的條件下，最小化準(zhǔn)則函數(shù)（SVM準(zhǔn)則）：Kuhn-Tucker構(gòu)造法構(gòu)造Lagrange函數(shù)分別對參數(shù)w和w0求導(dǎo)：Kuhn-Tucker構(gòu)造法因此有：帶入Lagrange函數(shù)，有：Kuhn-Tucker構(gòu)造法因此SVM的優(yōu)化問題可以轉(zhuǎn)化為一個經(jīng)典的二次規(guī)劃問題： 約束條件：SVM解的討論這是一個典型的不等式約束條件下的二次優(yōu)化問題，其解法的基礎(chǔ)是Kuhn-Tucker定理；首先求解的是n個Lagrange乘子，n為訓(xùn)練樣本數(shù)。但根據(jù)Kuhn-Tucker定理，有：滿足第2，3個條件的yi稱為支持矢量。支持向量和Lagrange系數(shù)SVM解的討論根據(jù)找到的支持矢量yi以及相應(yīng)的Lagrange乘子αi，計算權(quán)矢量w：偏置w0可以用支持矢量滿足的條件求得：Matlab實現(xiàn)BioinformaticsToolbox中包含了LibSVM的實現(xiàn)函數(shù)；學(xué)習(xí)函數(shù)：

SVMSTruct=svmtrain(X,L,

’KERNELFUNCTION’,

’linear’,‘BOXCONSTRAIN’,C,

‘AUTOSCALE’,false）；

X:n*d矩陣，L：n*1矢量識別函數(shù)：

Labels=svmclassify(X,SVMSTruct);5.6多類別線性判別函數(shù)的學(xué)習(xí)方法一：根據(jù)5.1節(jié)介紹的前兩種情況，分別轉(zhuǎn)換為c個兩類問題，或c(c-1)/2個兩類問題分別處理；方法二：對于情況三，可以采用Kesler構(gòu)造法訓(xùn)練；方法三：設(shè)計感知器網(wǎng)絡(luò)進行識別。Kesler構(gòu)造法（擴展的感知器算法）初始化c個權(quán)向量ai(1)，k1；輸入增廣特征矢量yk（只增加一維1，不改變特征的符號），計算c個判別函數(shù)的輸出：修改權(quán)矢量：

若yk屬于ωi類，而存在gi(yk)≤gj(yk)，則：

ai(k+1)=ai(k)+yk；

aj(k+1)=aj(k)-yk

al(k+1)=al(k)，l≠j,i重復(fù)上述過程，直到全部樣本被正確分類為止。兩類問題的感知器網(wǎng)絡(luò)多類問題的感知器網(wǎng)絡(luò)兩層感知器網(wǎng)絡(luò)的訓(xùn)練樣本給定樣本集合(y1,t1),(y2,t2),…,(yn,tn)，其中yi為增廣特征矢量，ti稱為期望輸出；c個輸出層神經(jīng)元時，可設(shè)定期望輸出為：

第1類樣本：(+1,-1,-1,-1)第2類樣本：(-1,+1,-1,-1)

第3類樣本：(-1,-1,+1,-1)第4類樣本：(-1,-1,-1,+1)編碼輸出時：

第1類樣本：(-1,-1)

第2類樣本：(-1,+1)

第3類樣本：(+1,-1)

第4類樣本：(+1,+1)兩層感知器網(wǎng)絡(luò)的訓(xùn)練方法可以采用最小均方誤差算法，權(quán)值調(diào)整公式為：

其中A為權(quán)值矢量矩陣，ti為第i個樣本yi

的期望輸出矢量。5.7線性分類器的局限性線性分類器的分類能力不強，能夠很好地解決線性可分的問題，而對非線性可分的問題無法解決，如著名的異或問題：解決途徑廣義線性判別函數(shù)；分段線性判別函數(shù)；多層感知器；核函數(shù)方法。廣義線性判別函數(shù)增加特征