模式識別(chapter2)

1、1 第二章第二章 判別域代數(shù)界面方程法判別域代數(shù)界面方程法2.1 2.1 用判別域界面方程分類的概念用判別域界面方程分類的概念2.2 2.2 線性判別函數(shù)線性判別函數(shù)2.3 2.3 判別函數(shù)值的鑒別意義、權(quán)空間及解空間判別函數(shù)值的鑒別意義、權(quán)空間及解空間2.4 Fisher2.4 Fisher線性判別線性判別2.5 2.5 一次準則函數(shù)及梯度下降法一次準則函數(shù)及梯度下降法2.6 2.6 二次準則函數(shù)及其解法二次準則函數(shù)及其解法2.7 2.7 廣義線性判別函數(shù)廣義線性判別函數(shù)2.8 2.8 二次判別函數(shù)二次判別函數(shù)2.9 2.9 位勢函數(shù)分類法位勢函數(shù)分類法有有監(jiān)監(jiān)督督分分類類2 2.1 2.1

2、 用判別域界面方程分類的概念用判別域界面方程分類的概念3 2x1x21o0)(32211wxwxwxd兩類的分類問題，它們的邊界線就是一個判別函數(shù)兩類的分類問題，它們的邊界線就是一個判別函數(shù)4兩類問題中線性不可分的實例兩類問題中線性不可分的實例5123邊界2x1x三類的分類問題，它們的邊界線也是一個判別函數(shù)三類的分類問題，它們的邊界線也是一個判別函數(shù)67 3.2 線性判別函數(shù)線性判別函數(shù)8910多類問題圖例多類問題圖例（第一種情況）（第一種情況）3( )0d x 21x 2( )0d x 2x1( )0d x 13? ?不確定區(qū)域111 1、第一種情況（續(xù)）第一種情況（續(xù)）判別規(guī)則為：判別規(guī)則

3、為：如果如果 ijxdxdji0)(0)(則判則判 ix3( ) 0d x 21x 2( ) 0d x 2x1( ) 0d x 13比如對圖的三類問題比如對圖的三類問題, ,如果對于任一模式如果對于任一模式 如如果它的果它的 則該模式屬于則該模式屬于1 1類。類。 0)(1xd0)(2xd0)(3xdx121 1、第一種情況（續(xù)）第一種情況（續(xù)）3123( )0( )0( )0dxdxdx12123( )0( )0( )0d xdxdx123()0()0()0dxdxdx 4IR3IR1IR2IR1x2x1( )0dx 2( )0d x 3( )0d x 551如果某個如果某個X X使二個以上

4、的判別函數(shù)使二個以上的判別函數(shù) d di i00 。則。則此模式此模式X X就無法作出確切的判決。如圖就無法作出確切的判決。如圖另一種情況是另一種情況是IR2IR2區(qū)域，區(qū)域，判別函數(shù)都為負值。判別函數(shù)都為負值。IR1IR1，IR2IR2，IR3IR3，IR4IR4。都為不。都為不確定區(qū)域。確定區(qū)域。131 1、第一種情況（續(xù)）第一種情況（續(xù)）11221232( )0( )50( )10dxxxdxxxdxx 解：解： 三個判別邊界分別為：三個判別邊界分別為：.1141、第一種情況（續(xù)）第一種情況（續(xù)）123( )0,( )0,( )0d xdxdx結(jié)論：結(jié)論： 因為因為所以它

5、屬于所以它屬于2 2類。類。151 1、第一種情況（續(xù)）第一種情況（續(xù)）3123( )0( )0( )0dxdxdx12123( )0( )0( )0d xdxdx123()0()0()0dxdxdx 1x2x1( )0dx 2( )0d x 3( )0d x 5511617212( )0dx 23( )0dx 13( )0dx 3 12、第二種情況（續(xù)）第二種情況（續(xù)）多類問題圖例多類問題圖例（第二種情況）（第二種情況）1819d12(x) = - d21(x) = x1 x2 + 5 = 0d d1212(x)(x)為正為正兩分法例題圖示兩分法例題圖示ji0 1 2 3 4 5 6 7 8

6、 99876543211x2xd d2121(x)(x)為正為正20d d1212(x)(x)為正為正兩分法例題圖示兩分法例題圖示ji0 1 2 3 4 5 6 7 8 99876543211x2xd d2121(x)(x)為正為正d d2323(x)= -(x)= -d d3232(x)= (x)= x x1 1+ +x x2 2= 0= 0d d3232(x)(x)為正為正d d2323(x)(x)為正為正21d d1212(x)(x)為正為正兩分法例題圖示兩分法例題圖示ji0 1 2 3 4 5 6 7 8 99876543211x2xd d2121(x)(x)為正為正d d3232(x

7、)(x)為正為正d d2323(x)(x)為正為正d d1313(x)= -(x)= -d d3131(x)= (x)= x x1 1+3 = 0+3 = 0d d3131(x)(x)為正為正d d1313(x)(x)為正為正22 1 1類判別區(qū)域類判別區(qū)域 d d1212(x)0(x)0 d d1313(x)0(x)0 2 2類判別區(qū)域類判別區(qū)域 d d2121(x)0(x)0 d d2323(x)0(x)0d d1212(x)(x)為正為正兩分法例題圖示兩分法例題圖示ji0 1 2 3 4 5 6 7 8 99876543211x2xd d2121(x)(x)為正為正d d3232(x)(

8、x)為正為正d d2323(x)(x)為正為正d d3131(x)(x)為正為正d d1313(x)(x)為正為正 3 3類判別區(qū)域類判別區(qū)域 d d3131(x)0(x)0 d d3232(x)0(x)0IR23243、第三種情況（續(xù)）第三種情況（續(xù)）212( )( )d xd x23( )( )d xd x13( )( )dxdx13多類問題圖例多類問題圖例（第三種情況）（第三種情況）25。26上述三種方法小結(jié)上述三種方法小結(jié): 方法判別函數(shù)的數(shù)目和方法相同，但沒有不方法判別函數(shù)的數(shù)目和方法相同，但沒有不確定區(qū)，分析簡單，是最常用的一種方法。確定區(qū)，分析簡單，是最常用的一種方法。3c時，時

9、，ji法比法比ii法需要更多法需要更多當(dāng)當(dāng)?shù)呐袆e函數(shù)式，這是一個缺點。的判別函數(shù)式，這是一個缺點。i類與其余的類與其余的1c開，而開，而ji法是將法是將i類和類和j類分開，顯然類分開，顯然jiii法是將法是將但是但是類區(qū)分類區(qū)分法使模式更容易線性可分，這是它的優(yōu)點。法使模式更容易線性可分，這是它的優(yōu)點。272.3 2.3 判別函數(shù)值的鑒別意義、權(quán)空間及解空間判別函數(shù)值的鑒別意義、權(quán)空間及解空間28此方程表示一超平面此方程表示一超平面 。它有以下。它有以下三個性質(zhì)三個性質(zhì): :n(1)(1)系數(shù)矢量系數(shù)矢量 ，是該平面的法矢量。是該平面的法矢量。n(2)(2)判別函數(shù)判別函數(shù) 的絕對值正比于的絕

10、對值正比于 到超到超平面平面 的距離。的距離。n(3)(3)判別函數(shù)值的正負表示出特征點位于哪個判別函數(shù)值的正負表示出特征點位于哪個半空間中。半空間中。012(,.)nww ww( )d xx( )0d x .3 .3 判別函數(shù)值的鑒別意義、權(quán)空間及解空間判別函數(shù)值的鑒別意義、權(quán)空間及解空間29圖圖2.3.1 2.3.1 點面距離及界面的正負側(cè)示意圖點面距離及界面的正負側(cè)示意圖x2x1xo0)(xdnppx0w303132pnxnpxndx)(pwwxww00000100wwxwwn)(10010 xdwwwxwn33證明：判別函數(shù)值的正負表示出特征點位于哪個證明：判別函數(shù)值的正負表示出特征點

11、位于哪個半空間中。半空間中。34背向的半空間中時，背向的半空間中時，x當(dāng)當(dāng)在在n010nwxw這說明判別函數(shù)值的正負表示出特征點位于這說明判別函數(shù)值的正負表示出特征點位于哪個半空間中，或者換句話說，表示特征點位于哪個半空間中，或者換句話說，表示特征點位于界面的哪一側(cè)。界面的哪一側(cè)。和和00w，故，故)(pxn10nwxw同號。同號。由于由于在在n指向的半空間中時，指向的半空間中時，010nwxwx即即35例例.1：利用判別函數(shù)的鑒別意義，試分析：利用判別函數(shù)的鑒別意義，試分析d(xd(x1 1,x,x2 2) )x x1 1+x+x2 2+1+1。d(x1,x2)d(x1,x2

12、)0 0n -1-1362.3.2權(quán)空間、解矢量與解空間權(quán)空間、解矢量與解空間37(2) (2) 解矢量解矢量2.3.2權(quán)空間、解矢量與解空間權(quán)空間、解矢量與解空間38(2) (2) 解矢量解矢量3940(3) (3) 解空間解空間 先看一個簡先看一個簡單的情況。設(shè)一單的情況。設(shè)一維數(shù)據(jù)維數(shù)據(jù)1，2屬于屬于 1, -1，-2屬屬于于 2 求將求將 1和和 2區(qū)分開的區(qū)分開的w0 ，w1。w0w141(3) (3) 解空間解空間 先看一個簡先看一個簡單的情況。設(shè)一單的情況。設(shè)一維數(shù)據(jù)維數(shù)據(jù)1，2屬于屬于 1, -1，-2屬屬于于 2 求將求將 1和和 2區(qū)分開的區(qū)分開的w0 ，w1。w0w142

13、(3) (3) 解空間解空間 先看一個簡先看一個簡單的情況。設(shè)一單的情況。設(shè)一維數(shù)據(jù)維數(shù)據(jù)1，2屬于屬于 1, -1，-2屬屬于于 2 求將求將 1和和 2區(qū)分開的區(qū)分開的w0 ，w1。w0w143(3) (3) 解空間解空間 先看一個簡先看一個簡單的情況。設(shè)一單的情況。設(shè)一維數(shù)據(jù)維數(shù)據(jù)1，2屬于屬于 1, -1，-2屬屬于于 2 求將求將 1和和 2區(qū)分開的區(qū)分開的w0 ，w1。w0w144(3) (3) 解空間解空間 先看一個簡先看一個簡單的情況。設(shè)一單的情況。設(shè)一維數(shù)據(jù)維數(shù)據(jù)1，2屬于屬于 1, -1，-2屬屬于于 2 求將求將 1和和 2區(qū)分開的區(qū)分開的w0 ，w1。w0w145(3)

14、 (3) 解空間解空間 先看一個簡先看一個簡單的情況。設(shè)一單的情況。設(shè)一維數(shù)據(jù)維數(shù)據(jù)1，2屬于屬于 1, -1，-2屬屬于于 2 求將求將 1和和 2區(qū)分開的區(qū)分開的w0 ，w1。w0w146(3) (3) 解空間解空間47w每一個訓(xùn)練模式都對解區(qū)提供一個約束，訓(xùn)練每一個訓(xùn)練模式都對解區(qū)提供一個約束，訓(xùn)練模式越多，解區(qū)的限制就越多，解區(qū)就越小，就越模式越多，解區(qū)的限制就越多，解區(qū)就越小，就越靠近解區(qū)的中心，解矢量靠近解區(qū)的中心，解矢量 就越可靠，由它構(gòu)就越可靠，由它構(gòu)造的判別函數(shù)錯分的可能性就越小。造的判別函數(shù)錯分的可能性就越小。48(4) (4) 余量余量49(4) (4) 余量余量引入了余

15、量可有效地避免量測的誤差、引入引入了余量可有效地避免量測的誤差、引入的誤差以及某些算法求得的解矢量收斂于解區(qū)的的誤差以及某些算法求得的解矢量收斂于解區(qū)的邊界上，從而提高了解的可靠性。邊界上，從而提高了解的可靠性。50設(shè)一設(shè)一3 3類問題有如下判決函數(shù)類問題有如下判決函數(shù)d d1 1(x) = - x(x) = - x1 1d d2 2(x) = x(x) = x1 1 + x + x2 2 -1 -1d d3 3(x) = x(x) = x1 1 - x - x2 2 -1 -1試畫出下列各種情況的判決邊界及各類的區(qū)試畫出下列各種情況的判決邊界及各類的區(qū)域：域：（1 1）滿足多類問題中的第一種

16、情況；）滿足多類問題中的第一種情況；（2 2）滿足多類問題中的第二種情況）滿足多類問題中的第二種情況, , 且令且令 d d1212(x)=d(x)=d1 1(x)(x)，d d1313(x)=d(x)=d2 2(x)(x)，d d3 3(x)=d(x)=d3 3(x)(x)；（3 3）滿足多類問題中的第三種情況。）滿足多類問題中的第三種情況。作業(yè)作業(yè)512.4 Fisher2.4 Fisher線性判別線性判別 第二章第二章 判別域代數(shù)界面方程法判別域代數(shù)界面方程法52二維模式向一維空間投影示意圖二維模式向一維空間投影示意圖uoxy53二維模式向一維空間投影示意圖二維模式向一維空間投影示意圖t

17、yuoxy54二維模式向一維空間投影示意圖二維模式向一維空間投影示意圖tyoxyoxy55（1)1)求解求解FishFish準則函數(shù)準則函數(shù)5657uSuuSSusssWWWWWW)(2121222uSumumumumummsBB)()(21212212類間離差度為：類間離差度為：58uSuuSussmmuJWBWWF2222121)()(并使其最大并使其最大, ,上式稱為上式稱為FisherFisher準則函數(shù)準則函數(shù)。59利用二次型關(guān)于矢量求導(dǎo)的公式可得：利用二次型關(guān)于矢量求導(dǎo)的公式可得：2)()(2)(2uSuuSuSuuSuSuuSuuSuuuJWWBBWWBF（2) 2) 求解求解F

18、isherFisher最佳鑒別矢量最佳鑒別矢量uSuuSuWB令令uSuSWB可得：可得：6061n上式右邊后兩項因子的乘積為一標(biāo)量，上式右邊后兩項因子的乘積為一標(biāo)量，令其為令其為 ，于是可得，于是可得n式中式中 為一標(biāo)量因子，其不改變軸的方為一標(biāo)量因子，其不改變軸的方向，可以取為向，可以取為1,于是有于是有)(211mmSuW)(211mmSuWummmmSuSSuWBW)(21211162uSuuSuuJWBF)()()(21121mmSmmW此時的此時的 可使可使Fisher準則函數(shù)取最大值，即是準則函數(shù)取最大值，即是n 維維空間到一維空間投影軸的最佳方向，由空間到一維空間投影軸的最佳方

19、向，由u)(211mmSuW)(2121mmmmSB和和JF 最大值為最大值為:)()()()()(2111212112121121mmSSSmmmmSmmmmSmmWWWWW63即即稱稱為為Fisher變換函數(shù)變換函數(shù))()(21121mmSmmWxSmmyW121)(J JF F=64 由于變換后的模式是一維的，因此判別界面實際由于變換后的模式是一維的，因此判別界面實際上是各類模式所在軸上的一個點，所以可以根據(jù)訓(xùn)練上是各類模式所在軸上的一個點，所以可以根據(jù)訓(xùn)練模式確定一個閾值模式確定一個閾值 y yt t，于是，于是FisherFisher判別規(guī)則判別規(guī)則為為: : 21xyyxut221

20、mmyt（3) 3) 求解求解FisherFisher判別函數(shù)判別函數(shù)判別閾值可取兩個類心在判別閾值可取兩個類心在u u方向上軸的投影連線的方向上軸的投影連線的中點作為閾值，即中點作為閾值，即: :6566ijijijijiimuxuNyNm)()(11（7 7） 計算計算 。im221mmyt（8 8） 計算計算yt 。21xyyxut（9 9） 對未知模式對未知模式x判定模式類。判定模式類。67以以100100元元A A面數(shù)據(jù)和面數(shù)據(jù)和5050元元A A面數(shù)據(jù)為例面數(shù)據(jù)為例100100元元A A面面:(64,76,99,84,98,95,88,83),:(64,76,99,84,98,95

21、,88,83),5050元元A A面面:(65,67,82,80,89,94,86,92),:(65,67,82,80,89,94,86,92),N N1 1=N=N2 2=60=60算得算得: :m m1 1=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)m m2 2=(59.2,55.5,81.9,63.9,95.1,91.0,91.1,86.5)=(59.2,55.5,81.9,63.9,95.1,91.0,91.1,86.5)68m m1 1=(=(69.3, 61.

22、9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) )m m2 2=(=(59.2, 55.5, 81.9, 63.9, 95.1, 91.0, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91.0, 91.1, 86.5) )69m m1 1=(=(69.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) )m

23、m2 2=(=(59.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.5) )70m m1 1=(=(69.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) )m m2 2=(=(59.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1,

24、86.5) )71m m1 1=(=(69.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) )m m2 2=(=(59.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.5) )727374 利用給定的一個樣本數(shù)據(jù)編寫利用給定的一個樣本數(shù)據(jù)編寫100100元元B B面與面與5050元元A A面的面的FisherFisher判別門限的程序，并用另一

25、個樣本數(shù)據(jù)判別門限的程序，并用另一個樣本數(shù)據(jù)驗證之。驗證之。上機練習(xí)上機練習(xí)752.5 一次準則函數(shù)及梯度下降法一次準則函數(shù)及梯度下降法2.5.1 感知感知器算法器算法(Perceptron Approach)任選一初始增廣權(quán)矢量任選一初始增廣權(quán)矢量用訓(xùn)練樣本檢驗分類是否正確用訓(xùn)練樣本檢驗分類是否正確對所有訓(xùn)練樣本都正確分類？對所有訓(xùn)練樣本都正確分類？YesYesENDENDYesYesNoNo對權(quán)值進行校正對權(quán)值進行校正NoNo感知器算法流程圖感知器算法流程圖流程:762.5.1 感知感知器算法器算法(Perceptron Approach)77 (3)調(diào)整增廣權(quán)矢量，規(guī)則是調(diào)整增廣權(quán)矢量，

26、規(guī)則是 - 如果如果 和和 ，則，則 - 如果如果 和和 ，則，則 - 如果如果 和和 ， 或或 和和 ，則，則1kx0)(kxkwkxkwkw)() 1(2kxkxkwkw)() 1(0)(kxkw1kx0)(kxkw2kx0)(kxkw)() 1(kwkwxwNxxx,21 (4)如果如果k wx wj jx (x ( j j i)i)因此判別規(guī)則是因此判別規(guī)則是 若若 d di i(x) d(x) dj j(x) (x) j j i i 則判則判x xi i 92(1) (1) 賦初值賦初值, ,分別給分別給c c個權(quán)矢量個權(quán)矢量w wi i(i=1,2,(i=1,2,c),c)賦任意的

27、賦任意的初值，選擇正常數(shù)初值，選擇正常數(shù) ，置步數(shù)，置步數(shù)k=1k=1。算法步驟：算法步驟：(2) (2) 輸入已知類別的增廣訓(xùn)練模式輸入已知類別的增廣訓(xùn)練模式x xk k，計算，計算c c個判別函個判別函數(shù)數(shù) d di i(x(xk k) = w) = wi ix xk k (i=1,2, (i=1,2,c),c)(3) (3) 修正權(quán)矢量，修正規(guī)則是：修正權(quán)矢量，修正規(guī)則是：if (xif (xk ki i) and (d) and (di i(x(xk k)d)dj j(x(xk k) () ( j j i) theni) then w wi i(k+1) = w(k+1) = wi i

28、(k) (i=1,2,(k) (i=1,2,c) (,c) (正確分類正確分類) ) if (xif (xk ki i) and (d) and (di i(x(xk k) ) d dl l(x(xk k) (l) (l i) theni) then w wi i(k+1) = w(k+1) = wi i(k)+ (k)+ x xk k w wl l(k+1) = w(k+1) = wl l(k)- (k)- x xk kw wj j(k+1) = w(k+1) = wj j(k) (k) ( j j i,l) i,l) 93(1) (1) 賦初值賦初值, ,分別給分別給c c個權(quán)矢量個權(quán)矢量

29、w wi i(i=1,2,(i=1,2,c),c)賦任意的賦任意的初值，選擇正常數(shù)初值，選擇正常數(shù) ，置步數(shù)，置步數(shù)k=1k=1。算法步驟：算法步驟：(2) (2) 輸入已知類別的增廣訓(xùn)練模式輸入已知類別的增廣訓(xùn)練模式x xk k，計算，計算c c個判別函個判別函數(shù)數(shù) d di i(x(xk k) = w) = wi ix xk k (i=1,2, (i=1,2,c),c)(4) if kN ,(4) if kN ,令令k=k+1,k=k+1,返至；返至；if k=Nif k=N，檢驗判別函數(shù)是否對都能正確分類，若是，檢驗判別函數(shù)是否對都能正確分類，若是，結(jié)束；否則，令結(jié)束；否則，令k=1k=

30、1，返至。，返至。(3) (3) 修正權(quán)矢量。修正權(quán)矢量。94例題例題:已知訓(xùn)練樣本已知訓(xùn)練樣本(0,0)T1，(1,1)T2 ，(-1,1)T3, 試求解向量試求解向量w1、w2和和w3。 （2 2）運用感知器訓(xùn)練算法。置）運用感知器訓(xùn)練算法。置k=1k=1，增量，增量 =1=1，賦初，賦初值：值：w1 1=(0,0,0)=(0,0,0)T T, , w2 2=(0,0,0)=(0,0,0)T T, , w3 3=(0,0,0)=(0,0,0)T T, ,進行迭代運算：進行迭代運算：解解:（1 1）訓(xùn)練樣本分量增廣化。將訓(xùn)練樣本變成增廣訓(xùn)）訓(xùn)練樣本分量增廣化。將訓(xùn)練樣本變成增廣訓(xùn)練模式：練模

31、式：x1 1=(0,0,1)=(0,0,1)T T, , x2 2=(1,1,1)=(1,1,1)T T, , x3 3=(-1,1,1)=(-1,1,1)T T, , 這里的下標(biāo)恰是所屬類別，各類樣本不需符號規(guī)這里的下標(biāo)恰是所屬類別，各類樣本不需符號規(guī)范化。范化。95例題例題:已知訓(xùn)練樣本已知訓(xùn)練樣本(0,0)T1，(1,1)T2 ，(-1,1)T3, 試求解向量試求解向量w1、w2和和w3。 k=1,k=1,xk k= =x1 11 1, ,因為因為d d1 1( (x1 1)=d)=d2 2( (x1 1)=0)=0，d d1 1( (x1 1)=d)=d3 3( (x1 1)=0)=0

32、，錯錯分，所以分，所以: : w1 1(2)=(2)=w1 1(1)+ (1)+ x1 1=(0,0,1)=(0,0,1)T T w2 2(2)=(2)=w2 2(1)- (1)- x1 1=(0,0,-1)=(0,0,-1)T T w3 3(2)=(2)=w3 3(1)- (1)- x1 1=(0,0,-1)=(0,0,-1)T Tk=2,xk=2,xk k=x=x2 22 2, ,因為因為d d2 2(x(x2 2)=-1d)=-1d1 1(x(x2 2)=1)=1，d d2 2(x(x2 2)=d)=d3 3(x(x2 2)=-1)=-1，錯分，錯分，所以所以 w w1 1(3)=w(3

33、)=w1 1(2)- x(2)- x2 2=(-1,-1, 0)=(-1,-1, 0)T T w w2 2(3)=w(3)=w2 2(2)+ x(2)+ x2 2=( 1, 1, 0)=( 1, 1, 0)T T w w3 3(3)=w(3)=w3 3(2)- x(2)- x2 2=(-1,-1,-2)=(-1,-1,-2)T T96例題例題:已知訓(xùn)練樣本已知訓(xùn)練樣本(0,0)T1，(1,1)T2 ，(-1,1)T3, 試求解向量試求解向量w1、w2和和w3。 k=3,xk=3,xk k=x=x3 33 3, ,因為因為d d3 3(x(x3 3)=-2d)=-2d)=0d1 1(x(x2 2

34、)=-2)=-2，d d2 2(x(x2 2)=0d)=0d3 3(x(x2 2)=-4)=-4，正確，正確，所以所以 w w1 1(6)=w(6)=w1 1(5)=( 0,-2, 0)(5)=( 0,-2, 0)T T w w2 2(6)=w(6)=w2 2(5)=( 2, 0,-2)(5)=( 2, 0,-2)T T w w3 3(6)=w(6)=w3 3(5)=(-2, 0,-2)(5)=(-2, 0,-2)T Tk=6,xk=6,xk k=x=x3 33 3, ,因為因為d d3 3(x(x3 3)=0d)=0d1 1(x(x3 3)=-2)=-2，d d3 3(x(x3 3)=0d)

35、=0d2 2(x(x3 3)=-4)=-4，正確，正確，所以所以 w w1 1(7)=w(7)=w1 1(6)=( 0,-2, 0)(6)=( 0,-2, 0)T T w w2 2(7)=w(7)=w2 2(6)=( 2, 0,-2)(6)=( 2, 0,-2)T T w w3 3(7)=w(7)=w3 3(6)=(-2, 0,-2)(6)=(-2, 0,-2)T T98例題例題:已知訓(xùn)練樣本已知訓(xùn)練樣本(0,0)T1，(1,1)T2 ，(-1,1)T3, 試求解向量試求解向量w1、w2和和w3。 k=7,xk=7,xk k=x=x1 11 1, ,因為因為d d1 1(x(x1 1)=0d)

36、=0d2 2(x(x1 1)=-2)=-2，d d1 1(x(x1 1)=0d)=0d3 3(x(x1 1)=-2)=-2，正確，正確，三個權(quán)矢量不再變化，因此可以確定所有訓(xùn)練樣本均已三個權(quán)矢量不再變化，因此可以確定所有訓(xùn)練樣本均已被正確分類，被正確分類，由此得到三個解矢量：由此得到三個解矢量：w1 1* *= =w1 1(5)(5)，w2 2* *= =w2 2(5)(5)，w3 3* *= =w3 3(5) (5) 同時可得三個判別函數(shù)同時可得三個判別函數(shù): :d d1 1( (x) = -2) = -2x x2 2d d2 2( (x) = 2) = 2x x1 1-2-2d d3 3(

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

38、致不一致的，不等式組沒解。此時，目標(biāo)的，不等式組沒解。此時，目標(biāo)最少的訓(xùn)練模式被最少的訓(xùn)練模式被錯分。錯分。（一）最小錯分模式數(shù)目準則：（一）最小錯分模式數(shù)目準則： 如果訓(xùn)練模式是線性可分的，則存在權(quán)矢量如果訓(xùn)練模式是線性可分的，則存在權(quán)矢量 使不等式組使不等式組w0ixw), 2 , 1(Ni成立。成立。對線性不可分樣本集，求一解矢量使得錯分的對線性不可分樣本集，求一解矢量使得錯分的模式數(shù)目最少。模式數(shù)目最少。 101),(2121NNxxxxxxX102J 如果方程組有唯一解如果方程組有唯一解, ,說明訓(xùn)練模式集是線性說明訓(xùn)練模式集是線性可分的可分的, ,如果方程組無解如果方程組無解, ,

39、極小點值是最小二乘解。極小點值是最小二乘解。一般情況下使一般情況下使 極小等價于誤分模式數(shù)目最少。極小等價于誤分模式數(shù)目最少。103104 求矩陣的廣義逆計算量較大，引入的誤差求矩陣的廣義逆計算量較大，引入的誤差也可能很大，在實際中多采用下面的梯度法。也可能很大，在實際中多采用下面的梯度法。105106為了減少計算量和存儲量，可以仿照單樣本修正法為了減少計算量和存儲量，可以仿照單樣本修正法: :NkkkkxbxwbwXX1)()(由于：由于：此算法通常稱為此算法通常稱為W WH(WidrowH(WidrowHoff)Hoff)算法算法 107W-HW-H算法有兩個性質(zhì)算法有兩個性質(zhì)108109

40、H-KH-K算法算法求解最佳權(quán)矢量的方法求解最佳權(quán)矢量的方法(1)( )( )( )( )bb kb kJb kk H-KH-K算法的迭代公式為：算法的迭代公式為：)(2)(bwXJb0其中其中110111H-K算法步驟;21, 1, 0) 1 (kbStep2.Step2.置初值置初值)(1XXXXStep1.Step1.將訓(xùn)練樣本符號規(guī)范化，得將訓(xùn)練樣本符號規(guī)范化，得X X求偽逆求偽逆)()()()()(kbkwXkekbXkwStep3.Step3.計算計算112H-K算法步驟Step6. Step6. k=k+1; goto Step3; goto Step3;Step5.Step5.

41、);)()()() 1(kekekbkb)()()() 1(kekeXkwkw)()(keXkw1.1114115作業(yè)1 1 以下列兩類模式為樣本，用以下列兩類模式為樣本，用LMSELMSE( (梯度法梯度法) )算法求解算法求解判決函數(shù)。（令判決函數(shù)。（令 w(1) = (-1,-2,-2)w(1) = (-1,-2,-2) ） 1 1：(0,0,0(0,0,0), (1,0,0) (1,0,0), (1,0,1, (1,0,1), (1,1,0), (1,1,0), 2 2：(0,0,1)(0,0,1), (0,1,1), (0,1,1), (0,1,0), (0,1,

42、0), (1,1,1), (1,1,1),2 2 用用LMSELMSE( (梯度法梯度法) )算法檢驗下列模式的線性可分性。算法檢驗下列模式的線性可分性。 1 1：(0,1)(0,1)，(0,-1)(0,-1) ， 2 2：(1,0)(1,0)，(-1,0)(-1,0) 。3 3 已知已知 1 1：(0,0)(0,0), 2 2：(1,1)(1,1), 3 3：(-1,1)(-1,1) 。用感知器算法求該三類問題的判別函數(shù)，并畫出解區(qū)用感知器算法求該三類問題的判別函數(shù)，并畫出解區(qū)域。域。116 設(shè)一維兩類模式設(shè)一維兩類模式 x x 在一維空間在一維空間坐標(biāo)軸上分坐標(biāo)軸上分布如圖布如圖2-7-1

43、2-7-1所示，兩類的類域為所示，兩類的類域為 和和 2.7 2.7 廣義線性判別函數(shù)廣義線性判別函數(shù)),( :1a,)b (),( :2ba圖圖2.7.1 2.7.1 一維特征空間中非線性可分的圖示一維特征空間中非線性可分的圖示117顯然，這兩類不是線顯然，這兩類不是線性可分的，因不能用性可分的，因不能用一個分界點將兩類分一個分界點將兩類分開。但是，對于一條開。但是，對于一條穿過穿過a a、b b兩點的二次兩點的二次曲線，曲線，abxbaxbxaxxd)()()(2當(dāng)當(dāng)1x0)(xd0)(xdax bx 即即或或時時, ,2x當(dāng)當(dāng)bxa即即時時, ,118原來的一維非線性可分的模式在所映射的

44、二維特征空原來的一維非線性可分的模式在所映射的二維特征空間中是線性可分的，即間中是線性可分的，即: :1y0)(yd2y0)(yd11912(),(),()jjjdjyf xfxfx使使在特征空間是線性可在特征空間是線性可分的分的, , 稱其為稱其為廣義線性判別函數(shù)廣義線性判別函數(shù)。120下圖所示兩類模式是線性不可分的。下圖所示兩類模式是線性不可分的。121經(jīng)過非線性變換，兩類模式是線性可分的。經(jīng)過非線性變換，兩類模式是線性可分的。12212211)()()()(dddwxfwxfwxfwxd)(12211ydywwywywywddd),(121dwwww) 1),(,),(),() 1 ,(

45、2121xfxfxfyyyydd式中式中), 2 , 1)(dixfyiix是是 的單值實函數(shù)。的單值實函數(shù)。123124上式右邊前兩項是上式右邊前兩項是x x各分量的二次項求和式，各分量的二次項求和式，顯然它們的項數(shù)分別為顯然它們的項數(shù)分別為n n和和 n(n-1)/2n(n-1)/2。第三項是第三項是x x的各分量一次項求和式，項數(shù)為的各分量一次項求和式，項數(shù)為n n。所以所以d(x)d(x)的項數(shù)為的項數(shù)為: : n+n(n-1)/2+n+1=(n+1)(n+2)/2n+n(n-1)/2+n+1=(n+1)(n+2)/2由于有一個常數(shù)項，變換后的特征空間維數(shù)為由于有一個常數(shù)項，變換后的特

46、征空間維數(shù)為: : (n+1)(n+2)/2-1=n(n+3)/2(n+1)(n+2)/2-1=n(n+3)/2125)()()0(10 xdwxdniniixwxd11)(211122112)(iininiiiixxwxdrrrriiiniiii ininiirxxxwxd211211121)(rrnC11nC21nC1126(0)1( )ndxw( )(1)( )( )( )rrrdxdxdx)()(xdr的項數(shù)為：的項數(shù)為： !)!(rnrn111rkkknC127 的維數(shù)的維數(shù) y1!)!(rnrndnsnssixxxxf2121)(rsssn21令令其中其中128 2.8 2.8 二

47、次判別函數(shù)二次判別函數(shù) 二次判別函數(shù)是一種常用的非線性判別函數(shù)，函二次判別函數(shù)是一種常用的非線性判別函數(shù)，函數(shù)構(gòu)造比較簡單，適用面比線性判別函數(shù)要廣。數(shù)構(gòu)造比較簡單，適用面比線性判別函數(shù)要廣。111112112)( njnjjkjnjnjkjkknkkknwxwxxwxwwxwxWxxd在在 n n 維特征空間中，二次判別函數(shù)的一般表示式為：維特征空間中，二次判別函數(shù)的一般表示式為：129 二次判別函數(shù)圖例二次判別函數(shù)圖例130一般的判別規(guī)則是：一般的判別規(guī)則是：11111NjjxNm )(11111111NjjjmxmxNC), 2 , 1(11Njxj計算訓(xùn)練模式計算訓(xùn)練模式)()()(1

48、1112mxCmxKxd構(gòu)造判別函數(shù)：構(gòu)造判別函數(shù)：210)(0)(xxdxxd當(dāng)當(dāng)對未知模式：對未知模式：131特點：特點：（ 1 1）可直接確定判決函數(shù)）可直接確定判決函數(shù) （ 2 2）適用于非線性和線性可分的情況）適用于非線性和線性可分的情況2.9 2.9 位勢函數(shù)分類法位勢函數(shù)分類法位勢函數(shù)的概念：位勢函數(shù)的概念： 位勢為位勢為0 0的等位線的等位線判決界面（判別函數(shù)）判決界面（判別函數(shù)）對于兩類問題對于兩類問題 1 1， 2 2，認為，認為 如果如果x x1 1，則，則x x 帶正電荷帶正電荷 如果如果x x2 2，則，則x x 帶負電荷帶負電荷132133 位勢函數(shù)圖例位勢函數(shù)圖例134135位勢函數(shù)圖例位勢函數(shù)圖例136137138 與感知器算法類似，位勢函數(shù)訓(xùn)練算法也可以用于多類問題，與感知器算法類似，位勢函數(shù)訓(xùn)練算法也可以用于多類問題，其其技術(shù)要點技術(shù)要點是：是： 設(shè)初始積累位勢函數(shù)設(shè)初始積累位勢函數(shù) ,這里這里 i 表示類別表示類別, i = 1,2,c。 當(dāng)當(dāng) 時，迭代規(guī)