現(xiàn)代模式識別

模式識別主講：蔡宣平教授

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

E-mail：xpcai@

單位:電子科學與工程學院信息工程系1

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

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

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

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

3.2線性判別函數(shù)

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

則判

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

。則此模式X就無法作出確切的判決。如圖另一種情況是IR2區(qū)域，判別函數(shù)都為負值。IR1，IR2，IR3，IR4。都為不確定區(qū)域。131、第一種情況（續(xù)）解：三個判別邊界分別為：141、第一種情況（續(xù)）結(jié)論：因為所以它屬于ω2類。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ū)，分析簡單，是最常用的一種方法。時，法比法需要更多當?shù)呐袆e函數(shù)式，這是一個缺點。類與其余的開，而法是將類和類分開，顯然法是將但是類區(qū)分法使模式更容易線性可分，這是它的優(yōu)點。273.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間

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

第三章判別域代數(shù)界面方程法29圖3.3.1點面距離及界面的正負側(cè)示意圖2x1xo+-0)(=xdrnrprpxrr-30313233證明：判別函數(shù)值的正負表示出特征點位于哪個半空間中。34背向的半空間中時，當在這說明判別函數(shù)值的正負表示出特征點位于哪個半空間中，或者換句話說，表示特征點位于界面的哪一側(cè)。和，故同號。由于在指向的半空間中時，即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)空間及解空間先看一個簡單的情況。設(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)空間及解空間先看一個簡單的情況。設(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)空間及解空間先看一個簡單的情況。設(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)空間及解空間先看一個簡單的情況。設(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)空間及解空間先看一個簡單的情況。設(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)空間及解空間先看一個簡單的情況。設(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)空間及解空間每一個訓(xùn)練模式都對解區(qū)提供一個約束，訓(xùn)練模式越多，解區(qū)的限制就越多，解區(qū)就越小，就越靠近解區(qū)的中心，解矢量就越可靠，由它構(gòu)造的判別函數(shù)錯分的可能性就越小。48(4)余量3.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間49(4)余量3.3.2權(quán)空間、解矢量與解空間3.3判別函數(shù)值的鑒別意義、權(quán)空間及解空間引入了余量可有效地避免量測的誤差、引入的誤差以及某些算法求得的解矢量收斂于解區(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準則函數(shù)5657類間離差度為：58并使其最大,上式稱為Fisher準則函數(shù)。59利用二次型關(guān)于矢量求導(dǎo)的公式可得：（2)求解Fisher最佳鑒別矢量令可得：6061上式右邊后兩項因子的乘積為一標量，令其為，于是可得式中為一標量因子，其不改變軸的方向，可以取為1,于是有62此時的可使Fisher準則函數(shù)取最大值，即是n

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

由于變換后的模式是一維的，因此判別界面實際上是各類模式所在軸上的一個點，所以可以根據(jù)訓(xùn)練模式確定一個閾值yt，于是Fisher判別規(guī)則為:（3)求解Fisher判別函數(shù)判別閾值可取兩個類心在u方向上軸的投影連線的中點作為閾值，即:6566（7）計算。（8）計算yt。（9）對未知模式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利用給定的一個樣本數(shù)據(jù)編寫100元B面與50元A面的Fisher判別門限的程序，并用另一個樣本數(shù)據(jù)驗證之。上機練習753.5一次準則函數(shù)及梯度下降法3.5.1感知器算法(PerceptronApproach)任選一初始增廣權(quán)矢量用訓(xùn)練樣本檢驗分類是否正確對所有訓(xùn)練樣本都正確分類？YesENDYesNo對權(quán)值進行校正No感知器算法流程圖流程:763.5一次準則函數(shù)及梯度下降法3.5.1感知器算法(PerceptronApproach)77

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

--如果和，則

--如果和，則

--如果和，或和，則

(4)如果k<N，令k=k+1，返至⑵。如果k=N，檢驗判別函數(shù)對是否都能正確分類。若是，結(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)練樣本分量增廣化及符號規(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準則求其決策面方程。863.5.2一次準則函數(shù)及梯度下降法一、梯度下降法采用梯度下降法沿負梯度方向，選擇適當?shù)牟介L進行搜索，求解函數(shù)的極小值點。

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

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

對于c類問題，應(yīng)建立c個判別函數(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個權(quán)矢量wi(i=1,2,…,c)賦任意的初值，選擇正常數(shù)，置步數(shù)k=1。算法步驟：(2)輸入已知類別的增廣訓(xùn)練模式xk，計算c個判別函數(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個權(quán)矢量wi(i=1,2,…,c)賦任意的初值，選擇正常數(shù)，置步數(shù)k=1。算法步驟：(2)輸入已知類別的增廣訓(xùn)練模式xk，計算c個判別函數(shù)di(xk)=wi’xk(i=1,2,…,c)(4)ifk<N,令k=k+1,返至⑵；

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

試求解向量w1、w2和w3。

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

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

試求解向量w1、w2和w3。

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

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

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

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

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

求偽逆Step3.計算

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(梯度法)算法檢驗下列模式的線性可分性。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在一維空間──坐標軸上分布如圖3-9-1所示，兩類的類域為和

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