模式识别_作业2

1、作业一：在一个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、多类情况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个系数分量；如果要建立二次的多项式判别函数，则至少需要个系数分量。作业四：用感知器算法求下列模式分类

3、的解向量w:1: (0 0 0)T, (1 0 0)T, (1 0 1)T, (1 1 0)T2: (0 0 1)T, (0 1 1)T, (0 1 0)T, (1 1 1)T答案：将属于2的训练样本乘以（-1），并写成增广向量的形式。x=(0 0 0 1)T,x=(1 0 0 1)T,x=(1 0 1 1)T,x=(1 1 0 1)Tx=(0 0 -1 -1)T,x=(0 -1 -1 -1)T,x=(0 -1 0 -1)T,x=(-1 -1 -1 -1)T第一轮迭代：取C=1，w(1)=(0 0 0 0)T因wT(1)x =(0 0 0 0)(0 0 0 1)T=00，故w(2)=w(1)+

4、x=(0 0 0 1)因wT(2)x=(0 0 0 1)(1 0 0 1)T =1>0，故w(3)=w(2)=(0 0 0 1)T因wT(3)x=(0 0 0 1)(1 0 1 1)T=1>0，故w(4)=w(3)=(0 0 0 1)T因wT(4)x=(0 0 0 1)(1 1 0 1)T=1>0，故w(5)=w(4)=(0 0 0 1)T因wT(5)x=(0 0 0 1)(0 0 -1 -1)T=-10，故w(6)=w(5)+x=(0 0 -1 0)T因wT(6)x=(0 0 -1 0)(0 -1 -1 -1)T=1>0，故w(7)=w(6)=(0 0 -1 0)T因

5、wT(7)x=(0 0 -1 0)(0 -1 0 -1)T=00，故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)(0 0 0 1)T=-10，故w(10)=w(9)+x =(0 -1 -1 0)T因wT(10)x=(0 -1 -1 0)(1 0 0 1)T=00，故w(11)=w(10)+x =(1 -1 -1 1)T因wT(11)x

6、=(1 -1 -1 1)(1 0 1 1)T=1>0，故w(12)=w(11) =(1 -1 -1 1)T因wT(12)x=(1 -1 -1 1)(1 1 0 1)T=1>0，故w(13)=w(12) =(1 -1 -1 1)T因wT(13)x=(1 -1 -1 1)(0 0 -1 -1)T=00，故w(14)=w(13)+x =(1 -1 -20)T因wT(14)x=(1 -1 -2 0)(0 -1 -1 -1)T=3>0，故w(15)=w(14) =(1 -1 -2 0)T因wT(15)x=(1 -1 -2 0)(0 -1 0 -1)T=1>0，故w(16)=w(1

7、5) =(1 -1 -2 0)T因wT(16)x=(1 -1 -2 0)(-1 -1 -1 -1)T=2>0，故w(17)=w(16) =(1 -1 -2 0)T因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第三轮迭代。第三轮迭代：w(25)=(2 -2 -2 0);因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第四轮迭代。第四轮迭代：w(33)=(2 -2 -2 1)因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第五轮迭代。第五轮迭代：w(41)=(2 -2 -2 1)因为该轮迭代的权向量对全部模式都能正确判别。所以权向量即为(2 -2

8、-2 1),相应的判别函数为作业五：编写求解上述问题的感知器算法程序。程序源码：#include <iostream>using namespace std;int scale; /每个样本的维数，最多支持十维int W1_N,W2_N; /第一类的个数以及第二类的个数double W11000,W21000;/第一、二类的所有样本的增广向量int C;/初始的算法中的C值double W10;/初始的算法中的W向量int main()cin>>scale>>W1_N>>W2_N;for(int i=0;i<W1_N*(scale+1);i

9、+)cin>>W1i;if(i%(scale+1)=2) /转化成增广向量W1+i=1;for(int i=0;i<W2_N*(scale+1);i+)cin>>W2i;W2i=-1*W2i;if(i%(scale+1)=2) /转化成增广向量W2+i=-1;scale=scale+1;cin>>C;for(int i=0;i<scale;i+)cin>>Wi;bool flag=false;while(!flag)bool flag1=true;for(int i=0;i<W1_N;i+)doubletmp=0.0;for(i

10、nt j=0;j<scale;j+)tmp+=W1i*scale+j*Wj;if(tmp<=0)flag1=false;for(int j=0;j<scale;j+)Wj=Wj+W1i*scale+j;for(int i=0;i<W2_N;i+)doubletmp=0.0;for(int j=0;j<scale;j+)tmp+=W2i*scale+j*Wj;if(tmp<=0)flag1=false;for(int j=0;j<scale;j+)Wj=Wj+W2i*scale+j;if(flag1)flag=true;cout<<”最后的权

11、向量为：”<<endl;cout<<W0;for(int i=1;i<scale;i+)cout<<" "<<Wi;cout<<endl;return 0;程序运行截图：作业六：用多类感知器算法求下列模式的判别函数：1: (-1 -1)T2: (0 0)T3: (1 1)T将模式样本写成增广形式：x=(-1-1 1)T,x=(00 1)T,x=(1 1 1)T取初始值w1(1)=w2(1)=w3(1)=(0 0 0)T，C=1。第一轮迭代（k=1）：以x=(-1 -1 1)T作为训练样本。d1(1)=x=(0

12、 0 0)(-1 -1 1)T=0d2(1)=x=(0 0 0)(-1 -1 1)T=0d3(1)=x=(0 0 0)(-1 -1 1)T=0因d1(1)d2(1)，d1(1)d3(1)，故w1(2)=w1(1)+x=(-1 -1 1)Tw2(2)=w2(1)-x=(11 -1)Tw3(2)=w3(1)-x=(11 -1)T第二轮迭代（k=2）：以x=(0 0 1)T作为训练样本d1(2)=x=(-1 -1 1)(0 0 1)T=1d2(2)=x=(1 1 -1)(0 0 1)T=-1d3(2)=x=(11 -1)(0 0 1)T=-1因d2(2)d1(2)，d2(2)d3(2)，故w1(3)

13、=w1(2)-x=(-1 -1 0)Tw2(3)=w2(2)+x=(1 1 0)Tw3(3)=w3(2)-x=(1 1 -2)T第三轮迭代（k=3）：以x=(1 1 1)T作为训练样本d1(3)=x=(-1 -1 0)(1 1 1)T=-2d2(3)=x=(1 1 0)(1 1 1)T=2d3(3)=x=(1 1 -2)(1 1 1)T=0因d3(3)d2(3)，故w1(4)=w1(3) =(-1 -1 0)Tw2(4)=w2(3)-x=(0 0 -1)Tw3(4)=w3(3)+x=(2 2 -1)T第四轮迭代（k=4）：以x=(-1 -1 1)T作为训练样本d1(4)=x=(-1 -1 0)

14、(-1 -1 1)T=2d2(4)=x=(0 0 -1)(-1 -1 1)T=-1d3(4)=x=(2 2 -1)(-1 -1 1)T=-5因d1(4)>d2(4)，d1(4)>d3(4)，故w1(5)=w1(4) =(-1 -1 0)Tw2(5)=w2(4) =(0 0 -1)Tw3(5)=w3(4) =(2 2 -1)T第五轮迭代（k=5）：以x=(0 0 1)T作为训练样本d1(5)=x=(-1 -1 0)(0 0 1)T=0d2(5)=x=(0 0 -1)(00 1)T=-1d3(5)=x=(2 2 -1)(00 1)T=-1因d2(5) d1(5)，d2(5) d3(5)

15、，故w1(6)=w1(5)-x=(-1 -1 -1)w2(6)=w2(5)+x=(0 0 0)w3(6)=w3(5)-x=(2 2 -2)第六轮迭代（k=6）：以x=(1 1 1)T作为训练样本d1(6)=x=(-1 -1 -1)(1 1 1)T=-3d2(6)=x=(0 0 0)(1 1 1)T=0d3(6)=x=(2 2 -2)(1 1 1)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 -1 1)T作为训练样本d1(7)=x=(-1 -1 -1)(-1 -1 1)T

16、=1d2(7)=x=(0 0 0)(-1 -1 1)T=0d3(7)=x=(2 2-2)(-1 -1 1)T=-6因d1(7)>d2(7)，d1(7)>d3(7)，分类结果正确，故权向量不变。由于第五、六、七次迭代中x、x、x均已正确分类，所以权向量的解为：w1=(-1 -1 -1)Tw2=(0 0 0)Tw3=(2 2 -2)T三个判别函数：d1(x)=-x1 -x2-1d2(x)=0d3(x)=2x1+2x2-2作业七：采用梯度法和准则函数式中实数b>0，试导出两类模式的分类算法。答案：J对w的微分式：定义：则由梯度法中w(k+1)和w(k)的关系有：其中xk是训练模式样

17、本，k是指第k次迭代。可以看出，当时，则w(k+1) = w(k)，此时不对权向量进行修正；当时，则w(k+1) = w(k) + C，需对权向量进行校正，初始权向量w(1)的值可任选。作业八：用二次埃尔米特多项式的势函数算法求解以下模式的分类问题1: (0 1)T, (0 -1)T2: (1 0)T, (-1 0)T答案：（1）按第一类势函数定义，得到势函数其中，（2）通过训练样本逐步计算累积位势K(x)给定训练样本：1类为x=(01)T, x=(0 -1)T2类为x=(1 0)T, x=(-10)T累积位势K(x)的迭代算法如下第一步：取x=(0 1)T1，故第二步：取x=(0 -1)T1

18、，故K1(x)=5因K1(x)>0且x1，故K2(x)=K1(x)第三步：取x=(1 0)T2，故K2(x)=9因K2(x)>0且x2，故第四步：取x=(-1 0)T2，故K3(x)=4因K3(x)>0且x2，将全部训练样本重复迭代一次，得第五步：取x=x=(01)T1，K4(x)=27>0故K5(x)=K4(x)第六步：取x=x=(0 -1)T1，K5(x)=-13<0故第七步：取x=x=(1 0)T2，K6(x)=-32<0故K7(x)=K6(x)第八步：取x=x=(-1 0)T2，K7(x)=-32<0故K8(x)=K7(x) 第九步：取x=x=(01)T1，K8(x)=32>0 故K9(x)=K8(x) 第十步：取x=x=(0 -1)T1，K9(x)=32>0 故K10(x)=K9(x)其中第七步到第十步的迭代过程中对全部训练样本都能正确分类，因此算法收敛于判别函数 作业九：用下列势函数求解以下模式的分类问题1: (0 1)T, (0 -1)T2: (1 0)T, (-1 0)T答案：取=1，在二维情况下势函数为这里：1类为x=(0 1)T, x=(0 -1)T2类为x=(1 0)T, x=(-1 0)T可以看出，这两