模式识别习题解答第三章

1、答：三种情况分别如下图所示:题1:在一个10类的模式识别问题中，有 3类单独满足多类情况1,其余的类 别满足多类情况2。问该模式识别问题所需判别函数的最少数目是多少？答：将10类问题可看作4类满足多类情况1的问题，可将3类单独满足多类情况1的类找 出来，剩下的7类全部划到4类中剩下的一个子类中。 再在此子类中，运用多类情况2的判 别法则进行分类，此时需要 7* (7-1) /2=21个判别函数。故共需要 4+21=25个判别函数。题2： 一个三类问题，其判别函数如下：d1(x)=-x1, d2(x)=x1+x2-1, d3(x)=x1-x2-11 .设这些函数是在多类情况1条件下确定的，绘出其

2、判别界面和每一个模式类 别的区域。2 .设为多类情况 2,并使：d12(x)= d1(x), d13(x)= d2(x), d23(x)= d3(x)。绘出其 判别界面和多类情况2的区域。3 .设d1(x), d2(x)和d3(x)是在多类情况3的条件下确定的，绘出其判别界面和 每类的区域。1.2.3.题3:两类模式，每类包括5个3维不同的模式，且良好分布。如果它们是线性 可分的，问权向量至少需要几个系数分量？假如要建立二次的多项式判别函数， 又至少需要几个系数分量？(设模式的良好分布不因模式变化而改变。)答：(1)若是线性可分的，则权向量至少需要N =n + 1 = 4个系数分量；5!(2)

3、若要建立二次的多项式判别函数，则至少需要 N =10个系数分量。2!3!题4:用感知器算法求下列模式分类的解向量w: 1: (0 0 0)T, (1 0 0)T, (1 0 1)T, (1 1 0)T 2: (0 0 1)T, (0 1 1)T, (0 1 0)T, (1 1 1)T解：将属于W2的训练样本乘以(-1),并写成增广向量的形式x1=0 0 0 1',x2=1 0 0 1',x3=1 0 1 1',x4=1 1 0 1'x5=0 0 -1 -1,x6=0 -1 -1 -1,x7=0 -1 0 -1',x8=-1 -1 -1 -1'迭代

4、选取C=1, w(1)=(0,0,0,0)则迭代过程中权向量w变化如下：w(2) =(0 0 0 1) ' ； w(3) =(0 0 -1 0) ' ； w(4) =(0 -1 -1 -1) ' ； w(5) = (0 -1 -1 0)'；w(6) =(1-1-1 1)' w=(1-1-2 0)'； w(8)=(1-1-2 1)'； w(9) = (2 -1 -1 2)；w(10)=(2 -1 -2 1)'； w(11) = (2 -2 -2 0)'； w(12) = (2 -2 -2 1)收敛所以最终得到解向量 w =

5、(2 -2 -2 1)',相应的判别函数为 d(x)=2x, 2x22x3+1。题5：用多类感知器算法求下列模式的判别函数: 1: (-1 -1)T, 2: (0 0)T, 3: (1 1)T解：采用一般化的感知器算法，将模式样本写成增广形式，即-1x1 - -110)L x2 = | 0u J取初始值W1 =W2 =W3 = ： 0，取C =1 ,则有第一次迭代：以 方为训练样本，d(1) = d2(1) = d3(1)=0,故-1wzi (2)：-w2(2) -,W3(2)=第二次迭代：以 x2为训练样本，d1 (2) =1,d2(2) =1,d3(2) =-1 ,故-1W (3)

6、=-1w2(3)=, W3 (3)第三次迭代：以 x3为训练样本，d1(3) = 2, d2(3)=2,d3(3) =0,故-1w1(4)=-1 ,w2(4)=<0,W3(4)=第四次迭代：以 x为训练样本，d(4) =202(4) = 14(4) = 5,故W|(5) =w1(4),W2(5) = W2(4), W3(5) = W3(4)第五次迭代：以 x2为训练样本，d1(5) =0,d2(5) =1,d3(5) =T ,故-1-1 , w2 (6)=T0 ,W3(6)-2；第六次迭代：以 x3为训练样本，d1(6) =-3,d2(6) =0,d3(6) =2,故W1(7) 二w1(

7、6), W2(7) =W2(6), W3(7) = W3(6)第七次迭代：以 X为训练样本，d1(7) =1,d2(7) =0,d3(7) = -6 ,故 w1(8) 二w1(7), W2(8) =W2(7), W3(8) =W3(7)第八次迭代：以 x2为训练样本，d1(8) = 1,d2(8) =0,d3(8) = 2,故wi(9) =Wi(8),W2(9) =W2(8), W3(9) = W3(8)*3,不，*2均以正确分类，故权向量的解为:由于第六、七、八次迭代中对2、2,可得三个判别函数为:2di = - % - X2 -1d2 = 0d3 =2% 2x2 -2题6:采用梯度法和准则

8、函数J(w,X,b)(wtx-b) - wtx - b I式中实数b0,试导出两类模式的分类算法J 1 ttt解：=2( w x - b)- | w x - b | x - x sgn(wx-b)：w 4|x|其中:sgn(wtx-b)= <1, wtx - b 0-1,wtx -b - 0得迭代式:Cw(k 1) = w(k) 2( w(k) x -b) - | w(k) x - b |* x - x*sgn( w(k) x -b) 4|x|2f0w(k+1) = w(k)+C (b-wtx)xwtx-b 0wt x - b 0题7:用LMSE算法求下列模式的解向量： 1: (0 0

9、0)T, (1 0 0)T, (1 0 1)T, (1 1 0)T 2： (0 0 1)T, (0 1 1)T, (0 1 0)T, (1 1 1)T解：写出模式的增广矩阵 X:-1-1-1X# =(XtX) 1Xt=(10011011110100-1-10-1-1-10-10-1-1-1-1-101110000010-1-1-10010-1-1 0-11111-1-1-1-1)-10011011110100-1-10-1-1-10 1 10-11 -1 J22、=(2-1-1I2取 b(1) =(1第一次迭代:）-1-1w (1)=4.J-1-1；#X b (1) =-1-1(1e(1)=

10、Xw(1)- b(1)=(-1)t 和C =-11 - 1 0.5)t0.5 0.5 - 0.50.5-0.5 0.5-0.5-0.5)tw (2) = w(1) + CX # e(1) = (1.5 - 1.5 - 1.50.75)tb(2) = b(1)+ C e(1)+ e(1)=(1 2 11121 1)t第二次迭代:e(2)= Xw(2)- b(2)= (- 0.25 0.25 - 0.25 - 0.25 - 0.25 0.25 - 0.25 - 0.25)w= w + CX# e(2) = (1.75 - 1.75 - 1.75 0.875)tb(3)= b(2)+Ce(2)+ e

11、(2) = (1 2.5 1 1 1 2.5 1 1)t第三次迭代：e(3)= Xw(3)- b(3)= (- 0.125 0.125 - 0.125 - 0.125 - 0.125 0.125 - 0.125 - 0.125)w= w(3) + CX # e(3) = (1.875 - 1.875 - 1.875 0.9375),b(4)= b(3)+C e(3)+ e(3) = (1 2.75 1 1 1 2.75 1 1)t第四次迭代：e(4)= Xw(4)- b(4)= (- 0.0625 0.0625 - 0.0625 - 0.0625 - 0.0625 0.0625 - 0.062

12、5 - 0.0625)w(5) = w(4)+ CX# e(4) = (1.9375 - 1.9375 - 1.9375 0.9688)tb(5)= b +C e(4)+ e(4) = (1 2.875 1 1 1 2.875 1 1)t第五次迭代：e(5)= Xw(5)- b(5)= (- 0.0313 0.0313 - 0.0313 - 0.0313 - 0.0313 0.0313 - 0.0313 - 0.0313)w(6) = w(5) + CX# e(5) = (1.9688 - 1.9688 - 1.9688 0.9844)tb(6) = b(5)+C e(5)+ e(5) = (

13、1 2.9375 1 1 1 2.9375 1 1)t第六次迭代：e(6)= Xw(6)- b(6)= (- 0.0156 0.0156 - 0.0156 - 0.0156 - 0.0156 0.0156 - 0.0156 - 0.0156)w(7) = w(6) + CX# e(6) = (1.9844 - 1.9844 - 1.9844 0.9922)tb(7) = b(6)+C e(6)+ e(6) = (1 2.9688 1 1 1 2.9688 1 1)t第七次迭代：e(7)= Xw(7)- b(7)= (- 0.0078 0.0078 - 0.0078 - 0.0078 - 0.0

14、078 0.0078 - 0.0078 - 0.0078)w(8) = w(7) + CX# e(7) = (1.9922 - 1.9922 - 1.9922 0.9961)tb(8)= b(7)+Ce(7)+ e(7) = (1 2.9844 1 1 1 2.9844 1 1)t第八次迭代：e(8)= Xw(8)- b(8)= (- 0.0039 0.0039 - 0.0039 - 0.0039 - 0.0039 0.0039 - 0.0039 - 0.0039)w=w(8)+ CX# e(8) = (1.9961 - 1.9961 - 1.9961 0.9980)tb(9)= b (8)

15、+ C e(8)+ e(8)= (1 2.9922 1 1 1 2.9922 1 1)t第九次迭代：e(9)= Xw(9)- b(9)= (- 0.0020 0.0020 - 0.0020 - 0.0020 - 0.0020 0.0020 - 0.0020 - 0.0020)w(10)= w(9) + CX # e(9) = (1.9980 - 1.9980 - 1.9980 0.9990)tb(10)= b(9)+C e(9)+ e(9) = (1 2.9961 1 1 1 2.9961 1 1)t第十次迭代：e(10=Xw(10) b(10=1.笆103 (- 0.97660.9766-

16、0.9766- 0.98- 0.98 0.98- 0.98- 0.98)w(11)= w(10)+ CX# e(10) = (1.9990 - 1.9990 - 1.9990 0.9995)tb(11)= b(10)+C e(10)+ e(10)= (1 2.9980 1 1 1 2.9980 1 1)t由于e< 1.0? 10-3,可以认为此时权系数调整完毕，最终的权系数为：w ? (22 - 2 1)t相应的判别函数为：d (x) = 2x1 - 2x2 - 2x3 + 1题8:用二次埃尔米特多项式的势函数算法求解以下模式的分类问题 1： (0 1)T, (0 -1)T蓊(1 0)T

17、，(-1 0)T1 (x) = 1(x1,x2)= H 0(x1)H ° (x2)=12(x) = 2(X1, X2) =H0(x1)H1(x2) =2x23(x) = 3(x1,x2)=山(入/2人)=4x2 -24(x) = 4(x1，x2) =H1(x1)H0(x2) =2x15(x)1("供)=乩(、)%(*2)=4取26(x) = 6(x1,x2) = HxJHzd) = 28(4x2 -2)7(x) =97(x1, x2) =H2(x1)H0(x2) =4x228(x) = 8(x1,x2) = H2(x1)H1(x2) =2x2(4x2 -2)9(x) = 9

18、(x1,x2)=山(为/2屋2) =(4x2 -2)(4x2 -2)9所以，势函数 K(x,xk)=vi(x)<(xk)i 1. .一U_ _ _2_2_ _222第一步：取 X1 = w w1,故 K1(X) =15+20x2 +40x2 +24x1 32x1X2 64x1X2第二步：取 X2 =ww1, K1(X2) =5>0,故 K2(X) =K1(X)T第二个：取 X3 =W w2, K2 (X3) = 9 a 0 ,故3。2K3(X)=K2(X) -K(X,X3)=20x2 16x2 -20x1-16x2 _J1)第四步：取 X4 =ww2, K3(X4)=4a0,故K4

19、(X) = K3(X) -K(X,X4) =15 20x2 -56x； -8x2 -32x12x2 64x2x2宜 第五步：取 X5 =Ww1, K4(X5) =27 A0 ,故 K5(X) = K4(X)510第六步：取 X6 =Ww1, K5(X6) = 13<0 ,故K6(X) =K5(X) K(X,X6) - -32x2 32x2f1)第七步：取 X7 =Ww2, K6(X7) = 32 <0,故Ky(X) =K6(X)第八步：取 X8 =Ww2, K7(X8) = 32<0 ,故PIK8(X) =K7(X)第九步：取 X9 =Ww1, K8(X9) =32 >

20、0 ,故9<1J 1K9(X) =K8(X)b'0 第十少：取 X10 =匚 w1, K9(X10) = 32 > 0 ,故S从第七步到第十步的迭代过程中，全部模式都已正确分类，故算法已经收敛于判别函数:d(X) =K10(X) - -32x2 32x2题9:用下列势函数K(X,Xk)=e.|XJ(k|2求解以下模式的分类问题 1: (0 1)T, (0 -1)T 2: (1 0)T, (-1 0)T选取3 =1 ,在二维情况下，势函数为K(X,Xk) =exp-|X -Xk |2 =exp-(Xi-Xki)2 % 2)2以下为势函数迭代算法：.一f0).00第一步：取 X1 =W W1,故 K1(X)=expX12(x2 1)21”方F0 )第二步：取 X2 = 七以，Ki(X2)=exp4 A0 ,故 K2(X)= Ki(X) 11第三步：取 X3 = Iw w2, K2(X3) =exp1 A0 ,故，2222-K3(X) =K2(X)-K(X,X3) =exp-x1 -(x2-1) -exp-函-1)