現(xiàn)代模式識(shí)別

模式識(shí)別主講：蔡宣平教授

電話：73441（O）,73442（H）

E-mail：xpcai@

單位:電子科學(xué)與工程學(xué)院信息工程系1

第三章判別域代數(shù)界面方程法3.1

用判別域界面方程分類的概念3.2線性判別函數(shù)3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間3.4Fisher線性判別3.5一次準(zhǔn)則函數(shù)及梯度下降法3.6二次準(zhǔn)則函數(shù)及其解法3.9廣義線性判別函數(shù)3.10二次判別函數(shù)3.12位勢(shì)函數(shù)分類法有監(jiān)督分類2

3.1用判別域界面方程分類的概念3兩類的分類問題，它們的邊界線就是一個(gè)判別函數(shù)4兩類問題中線性不可分的實(shí)例5三類的分類問題，它們的邊界線也是一個(gè)判別函數(shù)63.1用判別域界面方程分類的概念

第三章判別域代數(shù)界面方程法7

3.2線性判別函數(shù)

第三章判別域代數(shù)界面方程法8910多類問題圖例（第一種情況）?不確定區(qū)域111、第一種情況（續(xù)）判別規(guī)則為：如果

則判

比如對(duì)圖的三類問題,如果對(duì)于任一模式如果它的則該模式屬于ω1類。121、第一種情況（續(xù)）如果某個(gè)X使二個(gè)以上的判別函數(shù)di>0

。則此模式X就無法作出確切的判決。如圖另一種情況是IR2區(qū)域，判別函數(shù)都為負(fù)值。IR1，IR2，IR3，IR4。都為不確定區(qū)域。131、第一種情況（續(xù)）解：三個(gè)判別邊界分別為：141、第一種情況（續(xù)）結(jié)論：因?yàn)樗运鼘儆讦?類。151、第一種情況（續(xù)）16172、第二種情況（續(xù)）多類問題圖例（第二種情況）1819d12(x)=-d21(x)=–x1–x2+5=0d12(x)為正兩分法例題圖示0123456789987654321d21(x)為正20d12(x)為正兩分法例題圖示0123456789987654321d21(x)為正d23(x)=-d32(x)=–x1+x2=0d32(x)為正d23(x)為正21d12(x)為正兩分法例題圖示0123456789987654321d21(x)為正d32(x)為正d23(x)為正d13(x)=-d31(x)=–x1+3=0d31(x)為正d13(x)為正221類判別區(qū)域

d12(x)>0d13(x)>02類判別區(qū)域

d21(x)>0d23(x)>0d12(x)為正兩分法例題圖示0123456789987654321d21(x)為正d32(x)為正d23(x)為正d31(x)為正d13(x)為正3類判別區(qū)域

d31(x)>0d32(x)>0IR23243、第三種情況（續(xù)）多類問題圖例（第三種情況）25。26上述三種方法小結(jié):方法⑶判別函數(shù)的數(shù)目和方法⑴相同，但沒有不確定區(qū)，分析簡(jiǎn)單，是最常用的一種方法。時(shí)，法比法需要更多當(dāng)?shù)呐袆e函數(shù)式，這是一個(gè)缺點(diǎn)。類與其余的開，而法是將類和類分開，顯然法是將但是類區(qū)分法使模式更容易線性可分，這是它的優(yōu)點(diǎn)。273.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間

第三章判別域代數(shù)界面方程法28此方程表示一超平面。它有以下三個(gè)性質(zhì):(1)系數(shù)矢量，是該平面的法矢量。(2)判別函數(shù)的絕對(duì)值正比于到超平面的距離。(3)判別函數(shù)值的正負(fù)表示出特征點(diǎn)位于哪個(gè)半空間中。3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間

第三章判別域代數(shù)界面方程法29圖3.3.1點(diǎn)面距離及界面的正負(fù)側(cè)示意圖2x1xo+-0)(=xdrnrprpxrr-30313233證明：判別函數(shù)值的正負(fù)表示出特征點(diǎn)位于哪個(gè)半空間中。34背向的半空間中時(shí)，當(dāng)在這說明判別函數(shù)值的正負(fù)表示出特征點(diǎn)位于哪個(gè)半空間中，或者換句話說，表示特征點(diǎn)位于界面的哪一側(cè)。和，故同號(hào)。由于在指向的半空間中時(shí)，即35例3.3.1：利用判別函數(shù)的鑒別意義，試分析d(x1,x2)＝x1+x2+1。d(x1,x2)＝0＋－×××××××××××××－－－－－－－－－－－－-1-1363.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間37(2)解矢量3.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間38(2)解矢量3.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間393.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間40(3)解空間3.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間先看一個(gè)簡(jiǎn)單的情況。設(shè)一維數(shù)據(jù)1，2屬于w1,-1，-2屬于w2求將w1和w2區(qū)分開的w0

，w1。w0w141(3)解空間3.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間先看一個(gè)簡(jiǎn)單的情況。設(shè)一維數(shù)據(jù)1，2屬于w1,-1，-2屬于w2求將w1和w2區(qū)分開的w0

，w1。w0w142(3)解空間3.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間先看一個(gè)簡(jiǎn)單的情況。設(shè)一維數(shù)據(jù)1，2屬于w1,-1，-2屬于w2求將w1和w2區(qū)分開的w0

，w1。w0w143(3)解空間3.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間先看一個(gè)簡(jiǎn)單的情況。設(shè)一維數(shù)據(jù)1，2屬于w1,-1，-2屬于w2求將w1和w2區(qū)分開的w0

，w1。w0w144(3)解空間3.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間先看一個(gè)簡(jiǎn)單的情況。設(shè)一維數(shù)據(jù)1，2屬于w1,-1，-2屬于w2求將w1和w2區(qū)分開的w0

，w1。w0w145(3)解空間3.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間先看一個(gè)簡(jiǎn)單的情況。設(shè)一維數(shù)據(jù)1，2屬于w1,-1，-2屬于w2求將w1和w2區(qū)分開的w0

，w1。w0w146(3)解空間3.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間473.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間每一個(gè)訓(xùn)練模式都對(duì)解區(qū)提供一個(gè)約束，訓(xùn)練模式越多，解區(qū)的限制就越多，解區(qū)就越小，就越靠近解區(qū)的中心，解矢量就越可靠，由它構(gòu)造的判別函數(shù)錯(cuò)分的可能性就越小。48(4)余量3.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間49(4)余量3.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間引入了余量可有效地避免量測(cè)的誤差、引入的誤差以及某些算法求得的解矢量收斂于解區(qū)的邊界上，從而提高了解的可靠性。50設(shè)一3類問題有如下判決函數(shù)

d1(x)=-x1

d2(x)=x1+x2-1

d3(x)=x1-x2-1

試畫出下列各種情況的判決邊界及各類的區(qū)域：

（1）滿足3.4.2節(jié)中的第一種情況；

（2）滿足3.4.2節(jié)中的第二種情況,且令

d12(x)=d1(x)，d13(x)=d2(x)，d23(x)=d3(x)；

（3）滿足3.4.2節(jié)中的第三種情況。作業(yè)513.4Fisher線性判別

第三章判別域代數(shù)界面方程法52二維模式向一維空間投影示意圖uroxy53二維模式向一維空間投影示意圖uroxy54二維模式向一維空間投影示意圖oxyoxy55（1)求解Fish準(zhǔn)則函數(shù)5657類間離差度為：58并使其最大,上式稱為Fisher準(zhǔn)則函數(shù)。59利用二次型關(guān)于矢量求導(dǎo)的公式可得：（2)求解Fisher最佳鑒別矢量令可得：6061上式右邊后兩項(xiàng)因子的乘積為一標(biāo)量，令其為，于是可得式中為一標(biāo)量因子，其不改變軸的方向，可以取為1,于是有62此時(shí)的可使Fisher準(zhǔn)則函數(shù)取最大值，即是n

維空間到一維空間投影軸的最佳方向，由和JF最大值為:’63即稱為Fisher變換函數(shù)JF=64

由于變換后的模式是一維的，因此判別界面實(shí)際上是各類模式所在軸上的一個(gè)點(diǎn)，所以可以根據(jù)訓(xùn)練模式確定一個(gè)閾值yt，于是Fisher判別規(guī)則為:（3)求解Fisher判別函數(shù)判別閾值可取兩個(gè)類心在u方向上軸的投影連線的中點(diǎn)作為閾值，即:6566（7）計(jì)算。（8）計(jì)算yt。（9）對(duì)未知模式x判定模式類。67以100元A面數(shù)據(jù)和50元A面數(shù)據(jù)為例100元A面:(64,76,99,84,98,95,88,83),…50元A面:(65,67,82,80,89,94,86,92),…N1=N2=60算得:m1=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)m2=(59.2,55.5,81.9,63.9,95.1,91.0,91.1,86.5)68m1=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)m2=(59.2,55.5,81.9,63.9,95.1,91.0,91.1,86.5)69m1=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)m2=(59.2,55.5,81.9,63.9,95.1,91,91.1,86.5)70m1=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)m2=(59.2,55.5,81.9,63.9,95.1,91,91.1,86.5)71m1=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)m2=(59.2,55.5,81.9,63.9,95.1,91,91.1,86.5)727374利用給定的一個(gè)樣本數(shù)據(jù)編寫100元B面與50元A面的Fisher判別門限的程序，并用另一個(gè)樣本數(shù)據(jù)驗(yàn)證之。上機(jī)練習(xí)753.5一次準(zhǔn)則函數(shù)及梯度下降法3.5.1感知器算法(PerceptronApproach)任選一初始增廣權(quán)矢量用訓(xùn)練樣本檢驗(yàn)分類是否正確對(duì)所有訓(xùn)練樣本都正確分類？YesENDYesNo對(duì)權(quán)值進(jìn)行校正No感知器算法流程圖流程:763.5一次準(zhǔn)則函數(shù)及梯度下降法3.5.1感知器算法(PerceptronApproach)77

(3)調(diào)整增廣權(quán)矢量，規(guī)則是

--如果和，則

--如果和，則

--如果和，或和，則

(4)如果k<N，令k=k+1，返至⑵。如果k=N，檢驗(yàn)判別函數(shù)對(duì)是否都能正確分類。若是，結(jié)束；若不是,令k=1，返至⑵。78權(quán)空間中感知器算法權(quán)矢量校正過程示意圖)(ikxr+-)(ikxr)(kwr)1(+kwr)(jkxr+-)(jkxr-)(kwr)1(+kwr79二、收斂定理：

如果訓(xùn)練模式是線性可分的，感知器訓(xùn)練算法在有限次迭代后便可以收斂到正確的解矢量。。證明思路：

如果第k+1次迭代生成的權(quán)矢量比第k次迭代生成的權(quán)矢量更接近解矢量，則收斂，即：80、

、

81

(1)訓(xùn)練樣本分量增廣化及符號(hào)規(guī)范化。82

83

84852.用感知器算法求解向量,訓(xùn)練樣本為:w1:{(0,0,0)T,(1,0,0)T,(1,0,1)T,(1,1,0)T}w2:{(0,0,1)T,(0,1,1)T,(0,1,0)T,(1,1,1)T}作業(yè)設(shè)兩類樣本的類內(nèi)離差矩陣分別為:試用Fisher準(zhǔn)則求其決策面方程。863.5.2一次準(zhǔn)則函數(shù)及梯度下降法一、梯度下降法采用梯度下降法沿負(fù)梯度方向，選擇適當(dāng)?shù)牟介L(zhǎng)進(jìn)行搜索，求解函數(shù)的極小值點(diǎn)。

第三章判別域代數(shù)界面方程法8788增廣權(quán)矢量的修正迭代公式為：令k=1/2，求得準(zhǔn)則函數(shù)的梯度其中符號(hào)函數(shù)89增廣權(quán)矢量修正迭代公式：稱為單樣本修正，實(shí)際也可構(gòu)造批量修正：式中的是被錯(cuò)分類的模式集。

90913.5.3感知器訓(xùn)練算法在多類問題中的應(yīng)用判別規(guī)則：

對(duì)于c類問題，應(yīng)建立c個(gè)判別函數(shù)：

di(x)=wi’xi(i=1,2,…,c)

如果xi，則有wi’x>wj’x(ji)

因此判別規(guī)則是

若di(x)>dj(x)ji則判xi

第三章判別域代數(shù)界面方程法92(1)賦初值,分別給c個(gè)權(quán)矢量wi(i=1,2,…,c)賦任意的初值，選擇正常數(shù)，置步數(shù)k=1。算法步驟：(2)輸入已知類別的增廣訓(xùn)練模式xk，計(jì)算c個(gè)判別函數(shù)

di(xk)=wi’xk(i=1,2,…,c)(3)修正權(quán)矢量，修正規(guī)則是：

if(xki)and(di(xk)>dj(xk))(ji)then

wi(k+1)=wi(k)(i=1,2,…,c)(正確分類)

if(xki)and(di(xk)dl(xk))(li)then

wi(k+1)=wi(k)+xk

wl(k+1)=wl(k)-xk

wj(k+1)=wj(k)(ji,l)93(1)賦初值,分別給c個(gè)權(quán)矢量wi(i=1,2,…,c)賦任意的初值，選擇正常數(shù)，置步數(shù)k=1。算法步驟：(2)輸入已知類別的增廣訓(xùn)練模式xk，計(jì)算c個(gè)判別函數(shù)di(xk)=wi’xk(i=1,2,…,c)(4)ifk<N,令k=k+1,返至⑵；

ifk=N，檢驗(yàn)判別函數(shù)是否對(duì)都能正確分類，若是，結(jié)束；否則，令k=1，返至⑵。(3)修正權(quán)矢量。94例題:已知訓(xùn)練樣本(0,0)T1，(1,1)T2，(-1,1)T3,

試求解向量w1、w2和w3。

（2）運(yùn)用感知器訓(xùn)練算法。置k=1，增量=1，賦初值：w1=(0,0,0)T,w2=(0,0,0)T,w3=(0,0,0)T,進(jìn)行迭代運(yùn)算：解:（1）訓(xùn)練樣本分量增廣化。將訓(xùn)練樣本變成增廣訓(xùn)練模式：x1=(0,0,1)T,x2=(1,1,1)T,x3=(-1,1,1)T,

這里的下標(biāo)恰是所屬類別，各類樣本不需符號(hào)規(guī)范化。95例題:已知訓(xùn)練樣本(0,0)T1，(1,1)T2，(-1,1)T3,

試求解向量w1、w2和w3。

k=1,xk=x11,因?yàn)閐1(x1)=d2(x1)=0，d1(x1)=d3(x1)=0，錯(cuò)分，所以:w1(2)=w1(1)+x1=(0,0,1)Tw2(2)=w2(1)-x1=(0,0,-1)Tw3(2)=w3(1)-x1=(0,0,-1)Tk=2,xk=x22,因?yàn)閐2(x2)=-1<d1(x2)=1，d2(x2)=d3(x2)=-1，錯(cuò)分，所以w1(3)=w1(2)-x2=(-1,-1,0)Tw2(3)=w2(2)+x2=(1,1,0)T

w3(3)=w3(2)-x2=(-1,-1,-2)T96例題:已知訓(xùn)練樣本(0,0)T1，(1,1)T2，(-1,1)T3,

試求解向量w1、w2和w3。

k=3,xk=x33,因?yàn)閐3(x3)=-2<d1(x3)=0，d3(x3)=d2(x3)=0，錯(cuò)分，所以w1(4)=w1(3)-x3=(0,-2,-1)Tw2(4)=w2(3)-x3=(2,0,-1)T

w3(4)=w3(3)+x3=(-2,0,-1)Tk=4,xk=x11,因?yàn)閐1(x1)=d2(x1)=-1，d1(x1)=d3(x1)=-1，錯(cuò)分，所以w1(5)=w1(4)+x1=(0,-2,0)Tw2(5)=w2(4)-x1=(2,0,-2)T

w3(5)=w3(4)-x1=(-2,0,-2)T97例題:已知訓(xùn)練樣本(0,0)T1，(1,1)T2，(-1,1)T3,

試求解向量w1、w2和w3。

k=5,xk=x22,因?yàn)閐2(x2)=0>d1(x2)=-2，d2(x2)=0>d3(x2)=-4，正確，所以w1(6)=w1(5)=(0,-2,0)Tw2(6)=w2(5)=(2,0,-2)T

w3(6)=w3(5)=(-2,0,-2)Tk=6,xk=x33,因?yàn)閐3(x3)=0>d1(x3)=-2，d3(x3)=0>d2(x3)=-4，正確，所以w1(7)=w1(6)=(0,-2,0)Tw2(7)=w2(6)=(2,0,-2)T

w3(7)=w3(6)=(-2,0,-2)T98例題:已知訓(xùn)練樣本(0,0)T1，(1,1)T2，(-1,1)T3,

試求解向量w1、w2和w3。

k=7,xk=x11,因?yàn)閐1(x1)=0>d2(x1)=-2，d1(x1)=0>d3(x1)=-2，正確，三個(gè)權(quán)矢量不再變化，因此可以確定所有訓(xùn)練樣本均已被正確分類，由此得到三個(gè)解矢量：w1*=w1(5)，w2*=w2(5)，w3*=w3(5)同時(shí)可得三個(gè)判別函數(shù): d1(x)=-2x2 d2(x)=2x1-2 d3(x)=-2x1-299

3.6二次準(zhǔn)則函數(shù)及其解法問題：一次準(zhǔn)則函數(shù)及其算法（如感知器算法）只適用于線性可分的情況，如果是線性不可分的，分類過程將不收斂!能否找到一種算法，使之能夠測(cè)試出模式樣本集是否線性可分，并且對(duì)線性不可分的情況也能給出“次最優(yōu)”的解？

第三章判別域代數(shù)界面方程法100如果訓(xùn)練模式是線性不可分不等式組是不一致的，不等式組沒解。此時(shí)，目標(biāo)最少的訓(xùn)練模式被錯(cuò)分。（一）最小錯(cuò)分模式數(shù)目準(zhǔn)則：如果訓(xùn)練模式是線性可分的，則存在權(quán)矢量使不等式組成立。對(duì)線性不可分樣本集，求一解矢量使得錯(cuò)分的模式數(shù)目最少。

101102如果方程組有唯一解,說明訓(xùn)練模式集是線性可分的,如果方程組無解,極小點(diǎn)值是最小二乘解。一般情況下使極小等價(jià)于誤分模式數(shù)目最少。103104求矩陣的廣義逆計(jì)算量較大，引入的誤差也可能很大，在實(shí)際中多采用下面的梯度法。105106為了減少計(jì)算量和存儲(chǔ)量，可以仿照單樣本修正法:由于：此算法通常稱為W－H(Widrow－Hoff)算法

107W-H算法有兩個(gè)性質(zhì)108109⑶H-K算法求解最佳權(quán)矢量的方法——H-K算法的迭代公式為：其中110111H-K算法步驟Step2.置初值Step1.將訓(xùn)練樣本符號(hào)規(guī)范化，得X

求偽逆Step3.計(jì)算

112H-K算法步驟Step6.k=k+1;gotoStep3;Step5.113114115作業(yè)1以下列兩類模式為樣本，用LMSE(梯度法)算法求解判決函數(shù)。（令w(1)=(-1,-2,-2)’

）

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

2：{(0,0,1)’,(0,1,1)’,(0,1,0)’,(1,1,1)’,}2用LMSE(梯度法)算法檢驗(yàn)下列模式的線性可分性。1：{(0,1)’，(0,-1)’}，2：{(1,0)’，(-1,0)’}。3已知1：{(0,0)’},2：{(1,1)’},3：{(-1,1)’}。用感知器算法求該三類問題的判別函數(shù)，并畫出解區(qū)域。116

設(shè)一維兩類模式x在一維空間──坐標(biāo)軸上分布如圖3-9-1所示，兩類的類域?yàn)楹?/p>

3.9廣義線性判別函數(shù)圖3.9.1一維特征空間中非線性可分的圖示117顯然，這兩類不是線性可分的，因不能用一個(gè)分界點(diǎn)將兩類分開。但是，對(duì)于一條穿過a、b兩點(diǎn)的二次曲線，當(dāng)即或時(shí),當(dāng)即時(shí),118原來的一維非線性可分的模式在所映射的二維特征空間中是線性可分的，即:119使在特征空間是線性可分的,稱其為廣義線性判別函