模式識(shí)別第三章 判別函數(shù)分類器.ppt

1、第三章 判別函數(shù)分類器,矢量,矢量X可以看作是N維歐氏空間中的一個(gè) 點(diǎn)，用一個(gè)列矢量表示：,矩陣,矩陣可以看作是由若干個(gè)矢量構(gòu)成的：,矩陣的秩,矩陣所有行向量的最大無關(guān)組個(gè)數(shù)稱為行秩； 矩陣所有列向量的最大無關(guān)組個(gè)數(shù)稱為列秩； 一個(gè)矩陣的行秩等于列秩，稱為矩陣的秩。,轉(zhuǎn)置,列矢量W的轉(zhuǎn)置WT為一個(gè)行矢量； N*M的矩陣A的轉(zhuǎn)置AT為一個(gè)M*N的矩陣。,矢量與矢量的乘法(1),設(shè)W和X為N維列矢量,結(jié)果是一個(gè)數(shù)。,矢量與矢量的乘法(2),設(shè)W和X為N維列矢量,結(jié)果是一個(gè)N*N維的矩陣。,矢量與矩陣的乘法,設(shè)W為N維列矢量，A為一個(gè)N*M的矩陣：,結(jié)果是一個(gè)N維列矢量。,正交,設(shè)W和X為N維列矢量

2、，如果W與X的內(nèi)積等于零：,則稱W與X正交，也稱W垂直于X。,逆矩陣,A為一個(gè)N*N的方陣，A的逆陣用A-1表示，滿足：,其中I為單位陣。 一個(gè)矩陣的逆陣存在條件：1)是一個(gè)方陣，2)是一個(gè)滿秩矩陣，矩陣的秩為N,矩陣的特征值和特征向量,A為一個(gè)N*N的方陣，如果有：,數(shù)稱為A的特征值，矢量稱為A的特征矢量。,矩陣的跡和行列式值,A為一個(gè)N*N的方陣，A的跡為主對(duì)角線元素之和：,A為一個(gè)N*N的方陣，A的跡為主對(duì)角線元素之和：,矩陣的跡、行列式值與特征值之間的關(guān)系,矩陣A有N個(gè)特征值1，2， N，則有如下關(guān)系：,矩陣對(duì)數(shù)值變量微分,矩陣A(t)=aij(t)M*N，元素aij(t)是變量t的函

3、數(shù)，矩陣A(t)對(duì)t的微分：,矩陣函數(shù)對(duì)矩陣的微分,矩陣X=(xij)M*N，M*N元函數(shù)f(X)，定義f(X)對(duì)矩陣X的導(dǎo)數(shù)：,常用矢量微分的性質(zhì),X和W為N維矢量，A為M*N的矩陣：,3.1 線性判別函數(shù),一、兩類問題 二、多類問題,兩類問題的線性判別函數(shù),X0=(x1, x2, xN)T為待識(shí)模式的特征矢量； W0=(w1, w2, , wN)T稱為權(quán)矢量。,線性判別函數(shù)的增廣形式,X=(x1, x2, xN, 1) T稱為增廣的特征矢量； W=(w1, w2, , wN , 1)T稱為增廣的權(quán)矢量。,兩類問題線性判別準(zhǔn)則,多類問題（情況一）,每一類模式可以用一個(gè)超平面與其它類別分開；

4、這種情況可以把M個(gè)類別的多類問題分解為M個(gè)兩類問題解決；,多類問題（情況一）,多類問題（情況一）判別規(guī)則,當(dāng)d1(X)0，而d2(X)0且d3(X)0時(shí)，判別X屬于1； 當(dāng)d2(X)0，而d1(X)0且d3(X)0時(shí)，判別X屬于2； 當(dāng)d3(X)0，而d1(X)0且d2(X)0時(shí)，判別X屬于3； 其它情況，拒識(shí)。,多類問題（情況二）,每兩類之間可以用一個(gè)超平面分開，但是不能用來把其余類別分開； 需要將M個(gè)類別的多類問題轉(zhuǎn)化為 M(M-1)/2個(gè)兩類問題。 第i類與第j類之間的判別函數(shù)的為：,多類問題（情況二）判別準(zhǔn)則,如果對(duì)任意ji ，有dij(X) )0 ，則決策X屬于i。 其它情況，則拒識(shí)

5、。,多類問題（情況二）,多類問題（情況三）,情況三是情況二的特例，不存在拒識(shí)區(qū)域。,多類問題（情況三）判別函數(shù),M個(gè)類別需要M個(gè)線性函數(shù)：,判別準(zhǔn)則：,3.2 兩類別線性判別函數(shù)的學(xué)習(xí),一、問題的表達(dá) 二、感知器算法 三、最小均方誤差算法(LMSE),問題的表達(dá),已知兩個(gè)類別的訓(xùn)練樣本集合：,求向量W，使得d(X)=WTX，能夠區(qū)分1類和2類。,問題的表達(dá),矩陣形式描述,X稱為增廣矩陣。,權(quán)矢量的解,只有當(dāng)樣本集線性可分的條件下，解才存在； 線性不等式組的解是不唯一；,感知器算法的思想,感知器算法,初始化，置W(1)中的元素為一個(gè)小的隨機(jī)數(shù)； 在第k步學(xué)習(xí)訓(xùn)練樣本Xk，按照如下公式修正權(quán)值W：

6、,重復(fù)第2步，直到所有訓(xùn)練樣本被正確識(shí)別。,LMSE算法的思想,此方法也稱為Ho-Kashyap算法(H-K算法) 將線性不等式組XW0的問題，轉(zhuǎn)化為解線性方程組XW=B的問題。 其中：B=(b1, b2, , bN)T，bi0,問題求解,已知：增廣矩陣X(可由訓(xùn)練樣本集得到)； 求：W和B。 X一般不是方陣，所以問題實(shí)際上無解，只能求近似解。,優(yōu)化的準(zhǔn)則函數(shù),定義誤差矢量e：,定義準(zhǔn)則函數(shù)J(W,B)：,梯度法求解,上面兩個(gè)公式成立的W即為所求。,定義偽逆矩陣X*：,H-K算法,由訓(xùn)練樣本集計(jì)算X，X*=(XTX)-1XT； 初始化 B(0)，每個(gè)分量是一個(gè)小的正值，選常數(shù)C，置k=0； 計(jì)

7、算W(k)=X*B(k)，e(k)=XW(k)-B(k)； 若e(k)=0，停止迭代，輸出W=W(k)； 若e(k)0，停止迭代，線性不可分； 其它情況，繼續(xù)第5步；,H-K算法,迭代計(jì)算：,k=k+1，返回第3步，繼續(xù)。,3.3 多類別線性判別函數(shù)的學(xué)習(xí),情況一：M類問題轉(zhuǎn)化為M個(gè)兩類問題：i樣本作為一類，其它樣本作為另一類進(jìn)行訓(xùn)練； 情況二：M類問題問題轉(zhuǎn)化為M(M-1)/2個(gè)兩類問題， i樣本作為一類， j樣本作為另一類，訓(xùn)練Wij；,多類問題情況三,采用擴(kuò)展的感知器算法 初始化L個(gè)權(quán)向量Wi(1)，選擇常數(shù)C，置步數(shù)k=1； 輸入增廣特征矢量Xk，計(jì)算L各判別函數(shù)的輸出：,擴(kuò)展的感知器算法,修改權(quán)矢量，規(guī)則為： 若Xk屬于i，并且di(Xk)dj(Xk)，對(duì)任意的ji，則： W i(k+1)=W i(k)，i=1,L 若Xk屬于i，而dl(Xk)dj(Xk)，則： W i(k+1)=Wi(k)+CXk； W l(k+1)=Wl(k)+CXk W j(k+1)=Wj(k)，jI, l,擴(kuò)展的感知器算法,重復(fù)2，3步，當(dāng)k=M時(shí)，檢測L個(gè)判別函數(shù)是否能夠?qū)θ坑?xùn)練樣本正確分類，如正確分類，則結(jié)束，否則k=1，轉(zhuǎn)2，繼續(xù)。,3.4 非線性判別函數(shù)的學(xué)習(xí),一、二次判別函數(shù) 二、分段線性函數(shù) 三、其它非線性判別函數(shù)