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

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

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

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

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

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

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

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算法,迭代計算：,k=k+1，返回第3步，繼續(xù)。,3.3 多類別線性判別函數(shù)的學習,情況一：M類問題轉(zhuǎn)化為M個兩類問題：i樣本作為一類，其它樣本作為另一類進行訓練； 情況二：M類問題問題轉(zhuǎn)化為M(M-1)/2個兩類問題， i樣本作為一類， j樣本作為另一類，訓練Wij；,多類問題情況三,采用擴展的感知器算法 初始化L個權(quán)向量Wi(1)，選擇常數(shù)C，置步數(shù)k=1； 輸入增廣特征矢量Xk，計算L各判別函數(shù)的輸出：,擴展的感知器算法,修改權(quán)矢量，規(guī)則為： 若Xk屬于i，并且di(Xk)dj(Xk)，對任意的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,擴展的感知器算法,重復2，3步，當k=M時，檢測L個判別函數(shù)是否能夠?qū)θ坑柧殬颖菊_分類，如正確分類，則結(jié)束，否則k=1，轉(zhuǎn)2，繼續(xù)。,3.4 非線性判別函數(shù)的學習,一、二次判別函數(shù) 二、分段線性函數(shù) 三、其它非線性判別函數(shù)