模式识别_作业2.

作业一：在一个10类的模式识别问题中，有3类单独满足多类情况1，其余的类别满足多类情况2。问该模式识别问题所需判别数的最少数目是多少？：将10类问题可看作4类满足多类情况1的问题，可将3类单独满足多类情况1的类找出来，剩下的7类全部划到4类中剩下的一个子类中。再在此子类中，运用多类情况2的判别法则进行分类，此时需要7*（7-1）/2=21个判别函数。故共需要4+21=25个判别函数。作业二：一个三类问题，其判别函数如下：d1(x)=-x1,d2(x)=x1+x2-1,d3(x)=x1-x2-11. 设这些函数是在多类情况1条件下确定的，绘出其判别界面和每一个模式类别的区域。2. 设为多类情况2，并使：d12(x)=d1(x),d13(x)=d2(x),d23(x)=d3(x)。绘出其判别界面和多类情况2的区域。3.设d1(x),d2(x)和d3(x)是在多类情况3的条件下确定的，绘出其判别界面和每类的区域。答案：123作业三：两类模式，每类包括5个3维不同的模式，且良好分布。如果它们是线性可分的，问权向量至少需要几个系数分量？假如要建立二次的多项式判别函数，又至少需要几个系数分量？（设模式的良好分布不因模式变化而改变。）答案：如果它们是线性可分的，则至少需要4个系数分量；如果要建立二次的多项式判别函数，则至少需要个系数分量。作业四：用感知器算法求下列模式分类的解向量w: ω1:{(000)T,(100)T,(101)T,(110)T} ω2:{(001)T,(011)T,(010)T,(111)T}答案：将属于ω2的训练样本乘以（-1），并写成增广向量的形式。x①=(0001)T,x②=(1001)T,x③=(1011)T,x④=(1101)Tx⑤=(00-1-1)T,x⑥=(0-1-1-1)T,x⑦=(0-10-1)T,x⑧=(-1-1-1-1)T第一轮迭代：取C=1，w(1)=(0000)T因wT(1)x①=(0000)(0001)T=0≯0，故w(2)=w(1)+x①=(0001)因wT(2)x②=(0001)(1001)T=1>0，故w(3)=w(2)=(0001)T因wT(3)x③=(0001)(1011)T=1>0，故w(4)=w(3)=(0001)T因wT(4)x④=(0001)(1101)T=1>0，故w(5)=w(4)=(0001)T因wT(5)x⑤=(0001)(00-1-1)T=-1≯0，故w(6)=w(5)+x⑤=(00-10)T因wT(6)x⑥=(00-10)(0-1-1-1)T=1>0，故w(7)=w(6)=(00-10)T因wT(7)x⑦=(00-10)(0-10-1)T=0≯0，故w(8)=w(7)+x⑦=(0-1-1-1)T因wT(8)x⑧=(0-1-1-1)(-1-1-1-1)T=3>0，故w(9)=w(8)=(0-1-1-1)T因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第二轮迭代。第二轮迭代：因wT(9)x①=(0-1-1-1)(0001)T=-1≯0，故w(10)=w(9)+x①=(0-1-10)T因wT(10)x②=(0-1-10)(1001)T=0≯0，故w(11)=w(10)+x②=(1-1-11)T因wT(11)x③=(1-1-11)(1011)T=1>0，故w(12)=w(11)=(1-1-11)T因wT(12)x④=(1-1-11)(1101)T=1>0，故w(13)=w(12)=(1-1-11)T因wT(13)x⑤=(1-1-11)(00-1-1)T=0≯0，故w(14)=w(13)+x⑤=(1-1-20)T因wT(14)x⑥=(1-1-20)(0-1-1-1)T=3>0，故w(15)=w(14)=(1-1-20)T因wT(15)x⑧=(1-1-20)(0-10-1)T=1>0，故w(16)=w(15)=(1-1-20)T因wT(16)x⑦=(1-1-20)(-1-1-1-1)T=2>0，故w(17)=w(16)=(1-1-20)T因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第三轮迭代。第三轮迭代：w(25)=(2-2-20);因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第四轮迭代。第四轮迭代：w(33)=(2-2-21)因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第五轮迭代。第五轮迭代：w(41)=(2-2-21)因为该轮迭代的权向量对全部模式都能正确判别。所以权向量即为(2-2-21),相应的判别函数为作业五：编写求解上述问题的感知器算法程序。程序源码：#include<iostream>usingnamespacestd;intscale;//每个样本的维数，最多支持十维intW1_N,W2_N;//第一类的个数以及第二类的个数doubleW1[1000],W2[1000];//第一、二类的所有样本的增广向量intC;//初始的算法中的C值doubleW[10];//初始的算法中的W向量intmain(){ cin>>scale>>W1_N>>W2_N; for(inti=0;i<W1_N*(scale+1);i++) { cin>>W1[i]; if(i%(scale+1)==2)//转化成增广向量 W1[++i]=1; } for(inti=0;i<W2_N*(scale+1);i++) { cin>>W2[i]; W2[i]=-1*W2[i]; if(i%(scale+1)==2)//转化成增广向量 W2[++i]=-1; } scale=scale+1; cin>>C; for(inti=0;i<scale;i++) cin>>W[i]; boolflag=false; while(!flag) { boolflag1=true; for(inti=0;i<W1_N;i++) { doubletmp=0.0; for(intj=0;j<scale;j++) tmp+=W1[i*scale+j]*W[j]; if(tmp<=0) { flag1=false; for(intj=0;j<scale;j++) W[j]=W[j]+W1[i*scale+j]; } } for(inti=0;i<W2_N;i++) { doubletmp=0.0; for(intj=0;j<scale;j++) tmp+=W2[i*scale+j]*W[j]; if(tmp<=0) { flag1=false; for(intj=0;j<scale;j++) W[j]=W[j]+W2[i*scale+j]; } } if(flag1) flag=true; } cout<<”最后的权向量为：”<<endl;cout<<W[0]; for(inti=1;i<scale;i++) cout<<""<<W[i]; cout<<endl; return0;}程序运行截图：作业六：用多类感知器算法求下列模式的判别函数： ω1:(-1-1)T ω2:(00)T ω3:(11)T将模式样本写成增广形式：x①=(-1-11)T,x②=(001)T,x③=(111)T取初始值w1(1)=w2(1)=w3(1)=(000)T，C=1。第一轮迭代（k=1）：以x①=(-1-11)T作为训练样本。d1(1)=x①=(000)(-1-11)T=0d2(1)=x①=(000)(-1-11)T=0d3(1)=x①=(000)(-1-11)T=0因d1(1)≯d2(1)，d1(1)≯d3(1)，故w1(2)=w1(1)+x①=(-1-11)Tw2(2)=w2(1)-x①=(11-1)Tw3(2)=w3(1)-x①=(11-1)T第二轮迭代（k=2）：以x②=(001)T作为训练样本d1(2)=x②=(-1-11)(001)T=1d2(2)=x②=(11-1)(001)T=-1d3(2)=x②=(11-1)(001)T=-1因d2(2)≯d1(2)，d2(2)≯d3(2)，故w1(3)=w1(2)-x②=(-1-10)Tw2(3)=w2(2)+x②=(110)Tw3(3)=w3(2)-x②=(11-2)T第三轮迭代（k=3）：以x③=(111)T作为训练样本d1(3)=x③=(-1-10)(111)T=-2d2(3)=x③=(110)(111)T=2d3(3)=x③=(11-2)(111)T=0因d3(3)≯d2(3)，故w1(4)=w1(3)=(-1-10)Tw2(4)=w2(3)-x③=(00-1)Tw3(4)=w3(3)+x③=(22-1)T第四轮迭代（k=4）：以x①=(-1-11)T作为训练样本d1(4)=x①=(-1-10)(-1-11)T=2d2(4)=x①=(00-1)(-1-11)T=-1d3(4)=x①=(22-1)(-1-11)T=-5因d1(4)>d2(4)，d1(4)>d3(4)，故w1(5)=w1(4)=(-1-10)Tw2(5)=w2(4)=(00-1)Tw3(5)=w3(4)=(22-1)T第五轮迭代（k=5）：以x②=(001)T作为训练样本d1(5)=x②=(-1-10)(001)T=0d2(5)=x②=(00-1)(001)T=-1d3(5)=x②=(22-1)(001)T=-1因d2(5)≯d1(5)，d2(5)≯d3(5)，故w1(6)=w1(5)-x②=(-1-1-1)w2(6)=w2(5)+x②=(000)w3(6)=w3(5)-x②=(22-2)第六轮迭代（k=6）：以x③=(111)T作为训练样本d1(6)=x③=(-1-1-1)(111)T=-3d2(6)=x③=(000)(111)T=0d3(6)=x③=(22-2)(111)T=2因d3(6)>d1(6)，d3(6)>d2(6)，故w1(7)=w1(6)w2(7)=w2(6)w3(7)=w3(6)第七轮迭代（k=7）：以x①=(-1-11)T作为训练样本d1(7)=x①=(-1-1-1)(-1-11)T=1d2(7)=x①=(000)(-1-11)T=0d3(7)=x①=(22-2)(-1-11)T=-6因d1(7)>d2(7)，d1(7)>d3(7)，分类结果正确，故权向量不变。由于第五、六、七次迭代中x①、x②、x③均已正确分类，所以权向量的解为：w1=(-1-1-1)Tw2=(000)Tw3=(22-2)T三个判别函数：d1(x)=-x1-x2-1d2(x)=0d3(x)=2x1+2x2-2作业七：采用梯度法和准则函数 式中实数b>0，试导出两类模式的分类算法。答案：J对w的微分式：定义：则由梯度法中w(k+1)和w(k)的关系有：其中xk是训练模式样本，k是指第k次迭代。可以看出，当时，则w(k+1)=w(k)，此时不对权向量进行修正；当时，则w(k+1)=w(k)+C，需对权向量进行校正，初始权向量w(1)的值可任选。作业八：用二次埃尔米特多项式的势函数算法求解以下模式的分类问题 ω1:{(01)T,(0-1)T} ω2:{(10)T,(-10)T}答案：（1）按第一类势函数定义，得到势函数其中，（2）通过训练样本逐步计算累积位势K(x)给定训练样本：ω1类为x①=(01)T,x②=(0-1)Tω2类为x③=(10)T,x④=(-10)T累积位势K(x)的迭代算法如下第一步：取x①=(01)T∈ω1，故第二步：取x②=(0-1)T∈ω1，故K1(x②)=5因K1(x②)>0且x②∈ω1，故K2(x)=K1(x)第三步：取x③=(10)T∈ω2，故K2(x③)=9因K2(x③)>0且x③∈ω2，故第四步：取x④=(-10)T∈ω2，故K3(x④)=4因K3(x④)>0且x④∈ω2，将全部训练样本重复迭代一次，得第五步：取x⑤=x①=(01)T∈ω1，K4(x⑤)=27>0故K5(x)=K4(x)第六步：取x⑥=x②=(0-1)T∈ω1，K5(x⑥)=-13<0故第七步：取x⑦=x③=(10)T∈ω2，K6(x⑦)=-32<0故K7(x)=K6(x)第八步：取x⑧=x④=(-10)T∈ω2，K7(x⑧)=-32<0故K8(x)=K7(x) 第九步：取x⑨=x①=(01)T∈ω1，K8(x⑨)=32>0 故K9(x)=K8(x) 第十步：取x⑩=x②=(0-1)T∈ω1，K9(x⑩)=32>0 故K10(x)=K9(x)其中第七步到第十步的迭代过程中对全部训练样本都能正确分类，因此算法收敛于判别函数• 作业九：用下列势函数 求解以下模式的分类问题 ω1:{(01)T,(0-1)T} ω2:{(10)T,(-10)T}答案：取α=1，在二维情况下势函数为 这里：ω1类为x①=(01)T,x②=(0-1)Tω2类为x③=(10)T,x④=(-10)T 可以看出，这两类模式是线性不可分的。算法步骤如下：第一步：取x①=(01)T∈ω1，则第二步：取x②=(0-1)T∈ω1 因K1(x②)=e-(4+0)=e-4>0，故K2(x)=K1(x) 第三步：取x③=(10)T∈ω2因K2(x③)=e-(1+1)=e-2>0，故第四步：取x④=(-10)T∈ω2 因K3(x④)=e-(1+1)-e-(4+0)=e-2-e-4>0，故 第五步：取x⑤=(01)T∈ω1因K4(x⑤)=1-e-(1+1)-e-(1+1)=1-e-2-e-2>0，故K5(x)=K4(x)第六步：取x⑥=(0-1)T∈ω1因K5(x⑥)=e-(0+4)-e-(1+1)-e-(1+1)=e-4-e-2-e-2<0，故第七步：取x⑦=(10)T∈ω2因K6(x⑦)=e-(1+1)+e-(1+1)–1-e-(4+0)=e-2+e-2-1-e-4<0 故 第八步：取x⑧=(-10)T∈ω2因K7(x⑧)=e-(1+1)+e-(1+1)-e-(4+0)-1=e-2+e-2-e-4-1<0 故 第九步：取x⑨=(01)T∈ω1因K8(x⑨)=e-(0+4)+1-e-(1+1)-e-(1+1)=e-4+1-e-2-e-2>0故第十步：取x⑩=(0-1)T∈ω1因K8(x⑨)=1+e-(0+4)-e-(1+1)-e-(1+1)=1+e-4-e-2-e-2>0故最后，从第七步到第十步的迭代过程中，全部模式都已正确分类，故算法已经收敛于判别函数：