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

第四章線性判別函數(shù)1主要內(nèi)容引言Fisher線性判別感知器準(zhǔn)則最小平方誤差準(zhǔn)則多類問題分段線性判別函數(shù)24.1引言基于樣本的Bayes分類器：通過估計類條件概率密度函數(shù)，設(shè)計相應(yīng)的判別函數(shù)MAXg1...g2gc...x1x2xna(x)最一般情況下適用的“最優(yōu)”分類器：錯誤率最小，對分類器設(shè)計在理論上有指導(dǎo)意義。獲取統(tǒng)計分布及其參數(shù)很困難，實際問題中并不一定具備獲取準(zhǔn)確統(tǒng)計分布的條件。訓(xùn)練樣本集樣本分布的

統(tǒng)計特征：

概率密度函數(shù)決策規(guī)則：

判別函數(shù)

決策面方程分類器

功能結(jié)構(gòu)3直接確定判別函數(shù)基于樣本的直接確定判別函數(shù)方法：針對各種不同的情況，使用不同的準(zhǔn)則函數(shù)，設(shè)計出滿足這些不同準(zhǔn)則要求的分類器。這些準(zhǔn)則的“最優(yōu)”并不一定與錯誤率最小相一致：次優(yōu)分類器。實例：正態(tài)分布最小錯誤率貝葉斯分類器在特殊情況下，是線性判別函數(shù)g(x)=wTx（決策面是超平面），能否基于樣本直接確定w?訓(xùn)練樣本集決策規(guī)則：

判別函數(shù)

決策面方程選擇最佳準(zhǔn)則4判別函數(shù)假設(shè)對一模式X已抽取n個特征，表示為：模式識別問題就是根據(jù)模式X的n個特征來判別模式屬于ω1,ω2,

…,

ωc類中的那一類。判別函數(shù)：表示類分界面的函數(shù)。5兩類的分類問題，它們的邊界線就是一個判別函數(shù)判別函數(shù)（續(xù)）6兩類問題中線性不可分的實例判別函數(shù)（續(xù)）7三類的分類問題，它們的邊界線也是一個判別函數(shù)判別函數(shù)（續(xù)）8判別函數(shù)包含兩類：一類是線性判別函數(shù)：線性判別函數(shù)廣義線性判別函數(shù)

（所謂廣義線性判別函數(shù)就是把非線性判別函數(shù)映射到另外一個空間變成線性判別函數(shù)）分段線性判別函數(shù)另一類是非線性判別函數(shù)判別函數(shù)（續(xù)）9線性判別函數(shù)d維空間中的線性判別函數(shù)的一般形式：x是樣本向量，即樣本在d維特征空間中的描述，w是權(quán)向量，w0是一個常數(shù)(閾值權(quán))。兩類問題的分類決策規(guī)則:10線性判別函數(shù)的幾何意義決策面(decisionboundary)H方程：g(x)=0向量w是決策面H的法向量g(x)是點x到?jīng)Q策面H的距離的一種代數(shù)度量x1x2wxxprH:g=011證明：權(quán)向量是決策面的法向量設(shè)點、在決策面H中，故它們滿足方程，有：上兩式相減，可得：這表明向量與向量正交，由于、是H平面中的任意兩點，故與決策面H正交，是H平面的法向量。12證明：判別函數(shù)g(x)絕對值正比于x到?jīng)Q策面H的距離設(shè)平面H的單位法矢量由平面H的方程可得：設(shè)P是平面H中的任一點，X是特征空間中任一點，點X到平面H的距離為差矢量（X-P）在n上的投影的絕對值，即：pwx-pnH:g=0x13判別函數(shù)g(x)絕對值正比于x到?jīng)Q策面H的距離14證明：判別函數(shù)值的正負(fù)表示出特征點位于哪個半空間中兩矢量n和（x-p）的數(shù)積為：當(dāng)和夾角小于90度時，即在指向的半空間中

當(dāng)和夾角大于90度時，即在背向的半空間中

由于，故和同號

15廣義線性判別函數(shù)線性判別函數(shù)是形式最為簡單的判別函數(shù)，但是它不能用于復(fù)雜情況。例：設(shè)計一個一維分類器，使其功能為：要用二次判別函數(shù)才可把二類分開：16廣義線性判別函數(shù)二次函數(shù)的一般形式：g(x)又可表示成：

如果作非線性變換，則原來的一維特征空間映射為三維特征空間。原來一維非線性可分

三維線性可分。17廣義線性判別函數(shù)(2)按照上述原理，任何非線性函數(shù)g(x)用級數(shù)展開成高次多項式后，都可轉(zhuǎn)化成線性判別函數(shù)來處理。一種特殊映射方法：增廣樣本向量y與增廣權(quán)向量a線性判別函數(shù)的齊次簡化：增廣樣本向量使特征空間增加了一維，但保持了樣本間的歐氏距離不變，對于分類效果也與原決策面相同，只是在Y空間中決策面是通過坐標(biāo)原點的，這在分析某些問題時具有優(yōu)點，因此經(jīng)常用到。18下圖所示兩類模式為線性不可分19經(jīng)過非線性變換，兩類模式為線性可分20線性分類器設(shè)計步驟線性分類器設(shè)計任務(wù)：給定樣本集K，確定線性判別函數(shù)g(x)=wTx的各項系數(shù)w。步驟：收集一組樣本K={x1,x2,…,xN}按需要確定一準(zhǔn)則函數(shù)J(K,w)，其值反映分類器的性能，其極值解對應(yīng)于“最好”決策。用最優(yōu)化技術(shù)求準(zhǔn)則函數(shù)J的極值解w*，從而確定判別函數(shù)，完成分類器設(shè)計。對于未知樣本x，計算g(x)，判斷其類別214.2Fisher線性判別線性判別函數(shù)y=g(x)=wTx:樣本向量x各分量的線性加權(quán)樣本向量x與權(quán)向量w的向量點積如果||w||=1，則視作向量x在向量w上的投影Fisher準(zhǔn)則的基本原理：找到一個最合適的投影軸，使兩類樣本在該軸上投影之間的距離盡可能遠(yuǎn)，而每一類樣本的投影盡可能緊湊，從而使分類效果為最佳。22二維模式向一維空間投影示意圖oxyoxy23Fisher線性判別圖例H:g=0Fisher準(zhǔn)則的描述：用投影后數(shù)據(jù)的統(tǒng)計性質(zhì)

—均值和離散度的函數(shù)作為判別優(yōu)劣的標(biāo)準(zhǔn)。oxy24d維空間樣本分布的描述量各類樣本均值向量mi樣本類內(nèi)離散度矩陣Si與總類內(nèi)離散度矩陣Sw

樣本類間離散度矩陣Sb：離散矩陣在形式上與協(xié)方差矩陣很相似，但協(xié)方差矩陣是一種期望值，而離散矩陣只是表示有限個樣本在空間分布的離散程度25一維Y空間樣本分布的描述量各類樣本均值樣本類內(nèi)離散度和總類內(nèi)離散度樣本類間離散度

以上定義描述d維空間樣本點到一向量投影的分散情況，因此也就是對某向量w的投影在w上的分布。樣本離散度的定義與隨機(jī)變量方差相類似26樣本與其投影統(tǒng)計量間的關(guān)系樣本x與其投影y的統(tǒng)計量之間的關(guān)系：2728Fisher準(zhǔn)則函數(shù)評價投影方向w的原則，使原樣本向量在該方向上的投影能兼顧類間分布盡可能分開，類內(nèi)樣本投影盡可能密集的要求Fisher準(zhǔn)則函數(shù)的定義：Fisher最佳投影方向的求解29Fisher公式的推導(dǎo)30Fisher最佳投影方向的求解采用拉格朗日乘子算法解決m1-m2是一向量，對與(m1-m2)平行的向量投影可使兩均值點的距離最遠(yuǎn)。但是如從使類間分得較開，同時又使類內(nèi)密集程度較高這樣一個綜合指標(biāo)來看，則需根據(jù)兩類樣本的分布離散程度對投影方向作相應(yīng)的調(diào)整，這就體現(xiàn)在對m1-m2

向量按Sw-1作一線性變換，從而使Fisher準(zhǔn)則函數(shù)達(dá)到極值點31判別函數(shù)的確定前面討論了使Fisher準(zhǔn)則函數(shù)極大的d維向量w*的計算方法，投影后的類判別Y0（閾值）可采用以下幾種方法確定：分類規(guī)則:324.3

感知器準(zhǔn)則感知準(zhǔn)則函數(shù)是五十年代由Rosenblatt提出的一種自學(xué)習(xí)判別函數(shù)生成方法，由于Rosenblatt企圖將其用于腦模型感知器，因此被稱為感知準(zhǔn)則函數(shù)。其特點是隨意確定的判別函數(shù)初始值，在對樣本分類訓(xùn)練過程中逐步修正直至最終確定。33基本概念線性可分性：訓(xùn)練樣本集中的兩類樣本在特征空間可以用一個線性分界面正確無誤地分開。在線性可分條件下，對合適的(廣義)權(quán)向量a應(yīng)有：規(guī)范化樣本向量

：將第二類樣本取其反向向量

34解向量與解區(qū)35感知器準(zhǔn)則函數(shù)對于任何一個增廣權(quán)向量a

，對樣本y正確分類，則有：aTy>0對樣本y錯誤分類，則有：aTy<0定義一準(zhǔn)則函數(shù)JP(a)(感知準(zhǔn)則函數(shù))：被錯分類的規(guī)范化增廣樣本集恒有JP(a)≥0，且僅當(dāng)a為解向量，Yk為空集（不存在錯分樣本）時，JP(a)=0，即達(dá)到極小值。確定向量a的問題變?yōu)閷P(a)求極小值的問題。36梯度下降算法梯度下降算法：對(迭代)向量沿某函數(shù)的負(fù)梯度方向修正，可較快到達(dá)該函數(shù)極小值。37算法(stepbystep)1.初值:任意給定一向量初始值a(1)2.迭代:第k+1次迭代時的權(quán)向量a(k+1)等于第k次的權(quán)向量a(k)加上被錯分類的所有樣本之和與rk的乘積3.終止:對所有樣本正確分類任意給定一向量

初始值a(1)a(k+1)=

a(k)+rk×Sum

(被錯分類的所有樣本)所有樣本

正確分類得到合理的a

完成

分類器設(shè)計NY38感知器方法例解固定增量法與可變增量法批量樣本修正法與單樣本修正法單樣本修正法：樣本集視為不斷重復(fù)出現(xiàn)的序列，逐個樣本檢查，修正權(quán)向量批量樣本修正法：樣本成批或全部檢查后，修正權(quán)向量39感知器方法小結(jié)感知準(zhǔn)則函數(shù)方法的思路是：先隨意找一個初始向量a(1)，然后用訓(xùn)練樣本集中的每個樣本來計算。若發(fā)現(xiàn)一個y出現(xiàn)aTy<0，則只要a(k+1)=a(k)+rky，rk為正(步長系數(shù))，則必有a(k+1)Ty=a(k)Ty+rkyTy，就有趨勢做到使a(k+1)Ty>0。當(dāng)然，修改后的a(k+1)還可以使某些y出現(xiàn)a(k+1)Ty<0的情況，理論證明，只要訓(xùn)練樣本集線性可分，無論a(1)的初值是什么，經(jīng)過有限次疊代，都可收斂。404.4最小錯分樣本數(shù)準(zhǔn)則感知準(zhǔn)則函數(shù)及其梯度下降算法只適用于線性可分情況。對于線性不可分情況，迭代過程永遠(yuǎn)不會終結(jié)，即算法不收斂。x1X4(1,1)X2(1,0)X1(0,0)X3(0,1)x2x1X4(1,1)X2(1,0)X1(0,0)X3(0,1)x241在實際問題中往往無法事先知道樣本集是否線性可分，因此，希望找到一種既適用于線性可分情況，又適用于線性不可分情況的算法。4.4最小錯分樣本數(shù)準(zhǔn)則42算法應(yīng)具有以下特點：對于線性可分問題，可以得到一個如感知準(zhǔn)則函數(shù)那樣的解向量a*，使得對兩類樣本集做到將全部樣本正確分類；對于線性不可分問題，則得到一個使兩類樣本集錯分?jǐn)?shù)目最少的權(quán)向量a，記為a*。這樣的算法準(zhǔn)則稱為最小錯分樣本數(shù)準(zhǔn)則。4.4最小錯分樣本數(shù)準(zhǔn)則43d維向量樣本集{x1，x2，…，xN

},變成增廣向量樣本集{y1，y2，…，yN

},再通過得到規(guī)范化增廣樣本向量，線性判別函數(shù)可寫作：4.4最小錯分樣本數(shù)準(zhǔn)則44如果存在權(quán)向量a，使得下式成立則y’n被正確分類。對單個樣本y’n存在線性不等式解。4.4最小錯分樣本數(shù)準(zhǔn)則45設(shè)計線性分類器可以看成求一組N個線性不等式的解的問題：若不等式組有解，即不等式組存在公共解(相一致的情況)，說明樣本集是線性可分的，找到這個解向量a*。若不等式組無解，即不等式組無公共解(不一致的情況)，說明樣本集是線性不可分的。4.4最小錯分樣本數(shù)準(zhǔn)則46在線性不可分的前提下，對于任何權(quán)向量a，必有某些樣本被錯分類。尋找一個滿足最多數(shù)目的不等式的權(quán)向量a的問題轉(zhuǎn)變成解線性不等式組的問題。4.4最小錯分樣本數(shù)準(zhǔn)則474.4最小錯分樣本數(shù)準(zhǔn)則48引入余量b,其維數(shù)為N,數(shù)值大于零，任何實數(shù)，使得下列等式成立。4.4最小錯分樣本數(shù)準(zhǔn)則49目前已提出不少最優(yōu)化這種準(zhǔn)則的算法，這里僅介紹兩種算法。兩種算法：共軛梯度法和搜索法前者定義的準(zhǔn)則為(1)式，后者定義的準(zhǔn)則為(2)式：4.4最小錯分樣本數(shù)準(zhǔn)則504.4.1共軛梯度法定義的準(zhǔn)則為:準(zhǔn)則的理解：如果Ya>b，則(Ya-b)和|Ya-b|同號，其結(jié)果Jq1(a)=0。如果存在某些規(guī)范化增廣樣本向量yi，使得yia<b，則(Ya-b)和|Ya-b|異號，其結(jié)果Jq1(a)>0。yia<b的樣本向量yi個數(shù)越多，Jq1(a)越大。

Jq1(a)與

權(quán)向量a成函數(shù)關(guān)系。51

Jq1(a)與權(quán)向量a成函數(shù)關(guān)系，與它的極小值相應(yīng)的權(quán)向量a則為最優(yōu)解a*。4.4.1共軛梯度法524.4.1共軛梯度法534.4.2搜索法定義的準(zhǔn)則為:Jq2(a)所表示是權(quán)向量a所滿足的不等式的數(shù)目54a(0)=H1nH2I1={3,5,7}a(1)=H3nH2I2={1,5}a(2)=H3nH1a(2)=H3nH5a(1)=H5nH2I2={1,4,8}最優(yōu)解：a(2)=H3nH1或a(2)=H5nH44.4.2搜索法554.5最小平方誤差準(zhǔn)則函數(shù)(MSE)感知準(zhǔn)則函數(shù)及其梯度下降算法的缺點：只適用于線性可分情況，對于線性不可分情況，選代過程永遠(yuǎn)不會終結(jié)，即算法不收斂。在實際問題，事先無法知道樣本是否線性可分，因此需要尋求更適合一般情況的算法。對于兩類問題，已知N個訓(xùn)練樣本，尋找權(quán)向量a，使得aTyi大于零，i=1,2,…,N。564.5最小平方誤差準(zhǔn)則規(guī)范化增廣樣本向量yi，增廣權(quán)向量a，正確分類要求：aTyi>0,i=1,…,N線性分類器設(shè)計

求一組N個線性不等式的解樣本集增廣矩陣Y及一組N個線性不等式的的矩陣表示：引入余量(目標(biāo)向量)b=[b1,b2,…,bN]T，bi任意給定正常數(shù)，aTyi=bi>0N個線性方程的的矩陣表示：5758樣本數(shù)N總是大于維數(shù)(d+1)

，因此Y是長方陣。一般為列滿秩陣。方程個數(shù)多于未知數(shù)，它為矛盾方程組，通常沒有精確解存在。但可以尋找最小二乘解。定義一個誤差向量e59平方誤差準(zhǔn)則函數(shù)定義誤差向量

e=Ya-b：定義平方誤差準(zhǔn)則函數(shù)Js(a):最小二乘近似解（MSE解）：MSE方法的思想：對每個樣本，設(shè)定一個“理想”的判別函數(shù)輸出值，以最小平方誤差為準(zhǔn)則求最優(yōu)權(quán)向量60YTY是(d+1)(d+1)方陣。存在逆矩陣。解向量a*是依賴向量b。Y的

偽逆矩陣4.5.1MSE準(zhǔn)則函數(shù)的偽逆解61MSE方法與Fisher方法的關(guān)系與Fisher方法的關(guān)系：當(dāng)N1個訓(xùn)練樣本屬于1,N2個訓(xùn)練樣本屬于2則在線性可分的情況下，MSE解與Fisher線性判別函數(shù)等價，MSE解等價于Fisher解。62MSE方法與Bayes方法的關(guān)系當(dāng)N→∞，b=uN=[1,1,…,1]T時，則它以最小均方誤差逼近Bayes判別函數(shù)：63計算上式偽逆存在問題：逆矩陣常常要求是非奇異的。計算量大。采用梯度下降法遞歸求解：批量樣本修正法4.5.2MSE準(zhǔn)則函數(shù)的梯度下降算法64樣本看成無限重復(fù)的序列，即單樣本修改權(quán)向量，Widrow-Hoff算法。隨機(jī)MSE準(zhǔn)則函數(shù)及其隨機(jī)逼近算法---樣本看成是隨機(jī)樣本集，權(quán)向量求解也看隨機(jī)最優(yōu)化問題。單樣本修正法65舉例利用MSE求解權(quán)向量x2x1X4(1,1)X3(1,0)X1(0,0)X2(0,1)已知模式樣本為：66674.6多類問題兩類別問題可以推