黃慶明模式識別與機(jī)器學(xué)習(xí)作業(yè)

1、在一個10類的模式識別問題中， 有3類單獨(dú)滿足多類情況1，其余的類別滿足多類情況 2。 問該模式識別問題所需判別函數(shù)的最少數(shù)目是多少？c 7*6應(yīng)該是 3，1，C7 = 4 , = 4，21 = 252其中加一是分別3類和7類一個三類問題，其判別函數(shù)如下：d1(x)=-x1, d2(x)=x1+x2-1, d3(x)=x1-x2-1(1)設(shè)這些函數(shù)是在多類情況1條件下確定的，繪出其判別界面和每一個模式類別的區(qū)域。(2)設(shè)為多類情況 2,并使：d12(x)= d1(x), d13(x)= d2(x), d23(x)= d3(x)。繪出其判別界面和多類 情況2的區(qū)域。兩類模式，每類包括 5個3維不

2、同的模式，且良好分布。如果它們是線性可分的，問權(quán)向量至少需要幾個系數(shù)分量？假如要建立二次的多項式判別函數(shù)，又至少需要幾個系數(shù)分量?（設(shè)模式的良好分布不因模式變化而改變。）如果線性可分，則 4個建立二次的多項式判別函數(shù)，貝U C；=10個-(1)用感知器算法求下列模式分類的解向量w:3 1： (0 0 0)T, (1 0 0)T, (1 0 1)T, (1 1 0)T ,TTTT3 2： (0 0 1) , (0 1 1) , (0 1 0) , (1 1 1) 將屬于3 2的訓(xùn)練樣本乘以(-1 ),并寫成增廣向量的形式。x=(0 0 0 1)T, x =(1 0 0 1) T, x =(1 0

3、 1 1)T, x =(1 1 0 1) TT =0 > 0,故 w(2)=w(1)+ x =(0 0 0 1)T =1>0，故 w(3)=w(2)=(0 0 0 1) TT=1>0,故 w(4)=w(3) =(0 0 0 1) TT=1>0,故 w(5)=w(4)=(0 0 0 1) TT=-1 > 0,故 w(6)=w(5)+ x =(0 0 -1 0) TT=1>0,故 w(7)=w(6)=(0 0 -1 0) TT=0> 0,故 w(8)=w(7)+ x =(0 -1 -1 -1) t=3>0,故 w(9)=w(8) =(0 -1 -1

4、-1)x=(0 0 -1 -1) T, x =(0 -1 -1 -1) T, x =(0 -1 0 -1) T, x =(-1 -1 -1 -1) 第一輪迭代：取 C=1, w(1)=(0 0 0 0) T 因 wT (1) x =(0 0 0 0)(0 0 0 1) 因 wT(2) x =(0 0 0 1)(1 0 0 1) 因 w/r(3)x =(0 0 0 1)(1 0 1 1) 因 w/r(4)x =(0 0 0 1)(1 1 0 1) 因 w/(5)x =(0 0 0 1)(0 0 -1 -1) 因 wr(6)x =(0 0 -1 0)(0 -1 -1 -1) T因 w(7)x =(

5、0 0 -1 0)(0 -1 0 -1) 因 wr(8)x =(0 -1 -1 -1)(-1 -1 -1 -1)因?yàn)橹挥袑θ磕Ｊ蕉寄苷_判別的權(quán)向量才是正確的解，因此需進(jìn)行第二輪迭代。 第二輪迭代：T=-1 >0,故 w(10)=w(9)+ x =(0 -1 -1 0)因 w/r(9)x =(0 -1 -1 -1)(0 0 0 1)因討(10以=(0-1-10)(1001)因/(11以=(1-1-11)(1011)因/(12以=(1-1-11)(1101)因討(13以=(1-1-11)(00-1-1)T因 w(14)x =(1 -1 -2 0)( 0 -1 -1 -1)因 w/(15)

6、x =(1 -1 -2 0)( 0 -1 0 -1)T因 w(16)x =(1 -1 -2 0)( -1 -1 -1 -1)T=0>0,故 w(11)=w(10)+ x =(1 -1 -1 1) TT=1>0,故 w(12)=w(11) =(1 -1 -1 1) TT=1>0,故 w(13)=w(12) =(1 -1 -1 1)T=0> 0,故 w(14)=w(13)+ x =(1 -1 -2 0)t=3>0,故 w(15)=w(14) =(1 -1 -2 0)T=1>0,故 w(16)=w(15) =(1 -1 -2 0)t=2>0,故 w(17)=

7、w(16) =(1 -1 -2 0)因?yàn)橹挥袑θ磕Ｊ蕉寄苷_判別的權(quán)向量才是正確的解，因此需進(jìn)行第三輪迭代。第三輪迭代:w(25)=(2 -2 -2 0);因?yàn)橹挥袑θ磕Ｊ蕉寄苷_判別的權(quán)向量才是正確的解，因此需進(jìn)行第四輪迭代。第四輪迭代：w(33)=(2 -2 -2 1)因?yàn)橹挥袑θ磕Ｊ蕉寄苷_判別的權(quán)向量才是正確的解，因此需進(jìn)行第五輪迭代。第五輪迭代：w(41)=(2 -2 -2 1)因?yàn)樵撦喌臋?quán)向量對全部模式都能正確判別。所以權(quán)向量即為(2 -2 -2 1),相應(yīng)的判別函數(shù)為 d(x) =2x1 -2x2 -2x3 1(2)編寫求解上述問題的感知器算法程序。見附件-用多類感知器

8、算法求下列模式的判別函數(shù)：31： (-1 -1)T32： (0 0)T33： (1 1)T將模式樣本寫成增廣形式：x=(-1 -1 1) T, x =(0 0 1) T, x =(1 1 1) T取初始值 w1(1)=w 2(1)=w 3(1)=(0 0 0)第一輪迭代(T, C=1。d1(1)=w； (1) x=(0 0 0)(-1 -1 1)T=0d2(1)=w：(1) x=(0 0 0)(-1 -1 1)T=0d3(1)=w；(1) x=(0 0 0)(-1 -1 1)T=0k=1):以 x =(-1 -1 1)T作為訓(xùn)練樣本。因 d1(1) > d2(1) , d1(1) >

9、; d3(1),故wi(2)=w i(1)+x =(-1 -1 1) Tw2=w 2(1)-x a)=(1 1 -1)Tws=w 3(1)-x =(1 1 -1)T第二輪迭代(k=2):以x=(0 0 1) T作為訓(xùn)練樣本d2(2)= w； (2) x=(1 1 -1)(0 0 1)T=-1 ck(2)= w； (2) x=(1 1 -1)(0 0 1) T=-1因 d2(2) > d1(2) , d2(2) >ds(2),故 w1(3)=w 1(2)-x =(-1 -1 0) T wa(3)=w 2(2)+x =(1 1 0) TTw3(3)=w 3(2)-x =(1 1 -2)

10、第三輪迭代(k=3):以x=(1 1 1) T作為訓(xùn)練樣本d1(3)= wT(3)x =(-1 -1 0)(1 1 1)t=-2d2(3)= w； (3) x=(1 1 0)(1 1 1)T=2d3(3)= w； (3) x=(1 1 -2)(1 1 1)T=0因 d3(3) > d2(3),故w(4)=w 1(3) =(-1 -1 0) T一 八 Twa(4)=w 2(3)-x =(0 0 -1)w3(4)=w 3(3)+x =(2 2 -1) T第四輪迭代(k=4):以x=(-1 -1 1) T作為訓(xùn)練樣本d1(4)= w： (4) x=(-1 -1 0)(-1 -1 1)T=2d2

11、(4)= w； (4) x=(0 0 -1)(-1 -1 1)T=-1d3(4)= w； (4) x=(2 2 -1)(-1 -1 1)；=-5因 d1(4)>d 2(4) , d1(4)>d 3(4),故 T w>(5)=w 1(4) =(-1 -1 0)w?(5)=w 2(4) =(0 0 -1) Tw3(5)=w 3(4) =(2 2 -1) T第五輪迭代(k=5):以x=(0 0 1) T作為訓(xùn)練樣本d1(5)= w； (5) x=(-1 -1 0)(0 0 1)T=0d2(5)= w； (5) x®=(0 0 -1)(0 0 1)T=-1d3(5)= w；

12、 (5) x®=(2 2 -1)(0 0 1)T=-1因 d2(5)> d1(5) , d2(5) > d3(5),故w(6)=w 1(5)-x =(-1-1-1)w?(6)=w 2(5)+x =(0 0 0)w3(6)=w 3(5)-x =(2 2 -2)第六輪迭代(k=6):以x=(1 1 1) T作為訓(xùn)練樣本d1(6)= w； (6)x=(-1 -1 -1)(1 1 1)T=-3ch(6)= w； (6) x=(0 0 0)(1 1 1)T=0d3(6)= w； (6) x=(2 2 -2)(1 1 1)T=2因 d3(6)>d 1，d3(6)>d 2(

13、6),故W1(7)=w 1(6)wa(7)=w 2(6)W3(7)=w 3(6)第七輪迭代(k=7):以x=(-1 -1 1) T作為訓(xùn)練樣本d1(7)= w： (7) x=(-1 -1 -1)(-1 -1 1)T=1d2(7)= £ (7) x=(0 0 0)(-1 -1 1)T=0d3(7)= w： (7) x® =(2 2 -2)(-1 -1 1)T=-6因 d1(7)>d由于第五、w>=(-1 -1 -1)w2=(0 0 0) Tw3=(2 2 -2)T三個判別函數(shù)：d1(x)=- x 1 -x2-1d2(x)=0d3(x)=2x 1+2x2-22(7)

14、 , d1(7)>d 3(7),分類結(jié)果正確，故權(quán)向量不變。六、七次迭代中x、x、x均已正確分類，所以權(quán)向量的解為:T-采用梯度法和準(zhǔn)則函數(shù)1 tTJ(w, x,b) = (w x b) - w x b8|xi式中實(shí)數(shù)b>0,試導(dǎo)出兩類模式的分類算法。=2 (wTx -b) - | wTx - b |" k- x* sign(wTx - b) -w 4l|x|其中,sign(wTx -b) = *if wT x - b 0-1 if wT x b & 0當(dāng) wTx-b>0時，則w(k+1) = w(k),此時不對權(quán)向量進(jìn)行修正；當(dāng)wTx-b M 0時，則w(

15、k+1)=w(k) + Cxk2 (w/x -b),需對權(quán)向量進(jìn)行校正,l|xk|初始權(quán)向量w(1)的值可任選。即w(k 1) = w(k) CxkITXTii20(WkTXk -b)if wTx - b 0if wT x - b _ 0第一步：取 x=(0 1) Te 3 1,貝U K(X) = expx2 (x2 1)2用二次埃爾米特多項式的勢函數(shù)算法求解以下模式的分類問題3 1： (0 1)丁, (0 -1)33 2: (1 0)T, (-1 0)T(1)1(x)= 1(X1,X2)=H°(X1)H°(X2)=12(X) = 2(X1，X2) =H°(X)H

16、1(X2) =2X23(X)= 3 (x1, x2)= H 0(x1 )H2 (x2)= 4x2 - 24(X)= 4 (x1,x2)= H1(x1)H0(x2)= 2x15(X) = 5(x1, X2) = H1(x1)H1(X2) = 4x1x26(x) = %(X1,X2) =E(X)H2(X2) =2x(4x；-2)7(X)= 7 (X1, x2)= H2(X1)H0 (X2)= 4x1 - 2 28(X) = %(X1,X2) =H2(X)H(X2) =2X2(4X1 -2)9(x) = 3(X1,&) =H2(X1)H2(X2) =(4x12 -2)(4x2 -2)按第一類

17、勢函數(shù)定義，得到勢函數(shù)9K(x,xQ =' *(x)*(Xk)i A其中 X=(X1,X2)T, Xk = (Xk1 , Xk2 )T(2)通過訓(xùn)練樣本逐步計算累積位勢K(x)給定訓(xùn)練樣本：3 1類為x=(0 1) T, x=(0 -1) T3 2 類為 x=(1 0) T, x =(-1 0) T累積位勢K(x)的迭代算法如下第一步：取 X 0)=(0 1) W 3 1,故K1(X) =T5 20x2 40x2 24x2 -32x；x2 -64x2x；第二步：取 x®=(0 -1) W 3 1,故 K(x )=5因 K1(x )>0 且 x £ 3 1,故

18、K2(x)=K 1(x)第三步：取 x=(1 0) W 3 2,故Kz(x)=9因K>(x)>0且X£ 3 2,故K3(X) =K2(X) K(X,X3) =20x2 16x2 一20X 一 16X12第四步：取 x=(-1 0) W 3 2,故Ki(x)=4因0x)>0且x£ 3 2,_2_222 2K4(X) =K3(X) -K(X,X4) =15 20x2 56x： 8x； 32x；x 64x；x；將全部訓(xùn)練樣本重復(fù)迭代一次，得第五步：取 x=x=(0 1) TC 3 1, K(x )=27>0故 K5(x)=K 4(x)第六步：取 x=x&#

19、174;=(0 -1) W 3 1, K5(x )=-13<0故 K6(X) =K5(X) K(X,X6) =-32x； 32x2第七步：取 x=乂=(1 0) Te 3 2, K6(x )=-32<0故 K7(x) = K 6(x)第八步：取 x®=x®=(-1 0) W 3 2, K7(x )=-32<0故 K8(x) = K 7(x)第九步：取 x=x0)=(0 1) Tc 3 1 , K8(x)=32>0故 K9(x)=K 8(x)第十步：取 x®=x® =(0 -1) W 3 1, K9(x )=32>0故 Ki0

20、(x)=K 9(x)其中第七步到第十步的迭代過程中對全部訓(xùn)練樣本都能正確分類，因此算法收斂于判 別函數(shù)d(X) =K10(X) = -32x12 32x；-用下列勢函數(shù)K(X,Xk) =eT|Xk|2求解以下模式的分類問題31: (0 1)T, (0 -1)T32； (1 0)T, (-1 0)Tx *kK(x,xQ = e取a =1,在二維情況下勢函數(shù)為4( x1 ：坷)2 (x2 ： k2 ) 2 =e這里：3 1 類為 x=(0 1) T, x =(0 -1) T3 2 類為 x® =(1 0) T, x = (-1 0)可以看出，這兩類模式是線性不可分的。算法步驟如下: 第二

21、步：取X=(0 -1) W 3 1因 K(x )=e-(4+0)=e-4>0，故 K(x)=K i(x)第三步：取X=(1 0) W 3 2因 K2(x )=e-(1+1) =e-2>0,故K3(X) = J(X) - K(X, X3) =exp-x； -次-1)2 -exp -(為 -1)2 - xj第四步：取x=(-1 0) TC 3 2因 E(x )=e-(1+1) - e -(4+0) =e-2-e -4>0,故Kq(X) =Ka(X) -K(X,X4)=exp-x -g -1)-exp-(x-1)- x?-exp-(x1) -x?第五步：取x=(0 1) TC 3 1因 K4(x )=1-e -(1+1) - e -(1+1) =1-e -2