黄庆明模式识别与机器学习作业

1、在一个10类的模式识别问题中， 有3类单独满足多类情况1，其余的类别满足多类情况 2。 问该模式识别问题所需判别函数的最少数目是多少？c 7*6应该是 3，1，C7 = 4 , = 4，21 = 252其中加一是分别3类和7类一个三类问题，其判别函数如下：d1(x)=-x1, d2(x)=x1+x2-1, d3(x)=x1-x2-1(1)设这些函数是在多类情况1条件下确定的，绘出其判别界面和每一个模式类别的区域。(2)设为多类情况 2,并使：d12(x)= d1(x), d13(x)= d2(x), d23(x)= d3(x)。绘出其判别界面和多类 情况2的区域。两类模式，每类包括 5个3维不

2、同的模式，且良好分布。如果它们是线性可分的，问权向量至少需要几个系数分量？假如要建立二次的多项式判别函数，又至少需要几个系数分量?（设模式的良好分布不因模式变化而改变。）如果线性可分，则 4个建立二次的多项式判别函数，贝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的训练样本乘以(-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)因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第二轮迭代。 第二轮迭代：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)因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第三轮迭代。第三轮迭代:w(25)=(2 -2 -2 0);因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第四轮迭代。第四轮迭代：w(33)=(2 -2 -2 1)因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第五轮迭代。第五轮迭代：w(41)=(2 -2 -2 1)因为该轮迭代的权向量对全部模式都能正确判别。所以权向量即为(2 -2 -2 1),相应的判别函数为 d(x) =2x1 -2x2 -2x3 1(2)编写求解上述问题的感知器算法程序。见附件-用多类感知器

8、算法求下列模式的判别函数：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作为训练样本。因 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作为训练样本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作为训练样本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作为训练样本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作为训练样本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作为训练样本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作为训练样本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三个判别函数：d1(x)=- x 1 -x2-1d2(x)=0d3(x)=2x 1+2x2-22(7)

14、 , d1(7)>d 3(7),分类结果正确，故权向量不变。六、七次迭代中x、x、x均已正确分类，所以权向量的解为:T-采用梯度法和准则函数1 tTJ(w, x,b) = (w x b) - w x b8|xi式中实数b>0,试导出两类模式的分类算法。=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当 wTx-b>0时，则w(k+1) = w(k),此时不对权向量进行修正；当wTx-b M 0时，则w(

15、k+1)=w(k) + Cxk2 (w/x -b),需对权向量进行校正,l|xk|初始权向量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用二次埃尔米特多项式的势函数算法求解以下模式的分类问题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、势函数定义，得到势函数9K(x,xQ =' *(x)*(Xk)i A其中 X=(X1,X2)T, Xk = (Xk1 , Xk2 )T(2)通过训练样本逐步计算累积位势K(x)给定训练样本：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=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)其中第七步到第十步的迭代过程中对全部训练样本都能正确分类，因此算法收敛于判 别函数d(X) =K10(X) = -32x12 32x；-用下列势函数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,在二维情况下势函数为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