第三章模识作业

第三章判别函数1、在一个10类的模式识别问题中，有3类单独满足多类情况1，其余的类别满足多类情况2。问该模式识别问题所需判别函数的最少数目是多少？解:判别满足多类情况1的3类情况需N1=3个判别函数；判别满足多类情况2的7类情况需N2=C72=21个判别函数。故至少需要N=N1+N2=24个判别函数。2、一个三类问题，其判别函数如下：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的区域。(3)设d1(x),d2(x)和d3(x)是在多类情况3的条件下确定的，绘出其判别界面和每类的区域。解：(1)判别界面如下1x的模式，应同时满足：d1(x)0，d2(x)0，d3(x)02x的模式，应同时满足：d1(x)0，d2(x)0，d3(x)03x的模式，应同时满足：d1(x)0，d2(x)0，d3(x)0(2)判别界面如下1x的模式，应同时满足：d12(x)0，d13(x)02x的模式，应同时满足：d21(x)0，d23(x)03x的模式，应同时满足：d31(x)0，d32(x)0(3)判别界面如下1x的模式，应同时满足：d1(x)d2(x)，d1(x)d3(x)2x的模式，应同时满足：d2(x)d1(x)，d2(x)d3(x)3x的模式，应同时满足：d3(x)d1(x)，d3(x)d2(x)3、两类模式，每类包括5个3维不同的模式，且良好分布。如果它们是线性可分的，问权向量至少需要几个系数分量？假如要建立二次的多项式判别函数，又至少需要几个系数分量？（设模式的良好分布不因模式变化而改变。）解：(1)线性可分时，所需权向量至少1313C个系数分量。(2)建立二次的多项式判别函数,所需权向量至少23210C个系数分量。4、用感知器算法求下列模式分类的解向量w:ω1:{(000)T,(100)T,(101)T,(110)T}ω2:{(001)T,(011)T,(010)T,(111)T}解：将属于ω2的训练样本乘以（-1），并写成增广向量的形式。x1=(0001)T,x2=(1001)T,x3=(1011)T,x4=(1101)T,x5=(00-1-1)T,x6=(0-1-1-1)T,x7=(0-10-1)T,x8=(-1-1-1-1)T第一轮迭代：取C=1，w(1)=(0000)T因wT(1)x1≯0，故w(2)=w(1)+x1=(0001)T因wT(2)x20，故w(3)=w(2)=(0001)T因wT(3)x30，故w(4)=w(3)=(0001)T因wT(4)x40，故w(5)=w(4)=(0001)T因wT(5)x5≯0，故w(6)=w(5)+x5=(00-10)T因wT(6)x60，故w(7)=w(6)=(00-10)T因wT(7)x7≯0，故w(8)=w(7)+x(7)=(0-1-1-1)T因wT(8)x80，故w(9)=w(8)=(0-1-1-1)T第二轮迭代：因wT(9)x1≯0，故w(10)=w(9)+x1=(0-1-10)T因wT(10)x2≯0，故w(11)=w(10)+x2=(1-1-11)T因wT(11)x30，故w(12)=w(11)=(1-1-11)T因wT(12)x40，故w(13)=w(12)=(1-1-11)T因wT(13)x5≯0，故w(14)=w(13)+x5=(1-1-20)T因wT(14)x60，故w(15)=w(14)=(1-1-20)T因wT(15)x70，故w(16)=w(15)=(1-1-20)T因wT(16)x80，故w(17)=w(16)=(1-1-20)T第三轮迭代：因wT(17)x1≯0，故w(18)=w(17)+x1=(1-1-21)T因wT(18)x20，故w(19)=w(18)=(1-1-21)T因wT(19)x3≯0，故w(20)=w(19)+x3=(2-1-12)T因wT(20)x40，故w(21)=w(20)=(2-1-12)T因wT(21)x5≯0，故w(22)=w(21)+x5=(2-1-21)T因wT(22)x60，故w(23)=w(22)=(2-1-21)T因wT(23)x7≯0，故w(24)=w(23)+x7=(2-2-20)T因wT(24)x80，故w(25)=w(24)=(2-2-20)T第四轮迭代：因wT(25)x1≯0，故w(26)=w(25)+x1=(2-2-21)T因wT(26)x20，故w(27)=w(26)=(2-2-21)T因wT(27)x3≯0，故w(28)=w(27)+x3=(2-2-21)T因wT(28)x40，故w(29)=w(28)=(2-2-21)T因wT(29)x5≯0，故w(30)=w(29)+x5=(2-2-21)T因wT(30)x60，故w(31)=w(30)=(2-2-21)T因wT(31)x7≯0，故w(32)=w(31)+x7=(2-2-21)T因wT(32)x80，故w(33)=w(32)=(2-2-21)T第五轮迭代：因wT(33)x10，故w(34)=w(33)=(2-2-21)T至此，迭代结果全部正确，因此解向量w=(2-2-21)T，相应的判别函数为：d(x)=2x1-2x2-2x3+1感知器算法程序见GANZHIQI.txt，程序运行结果如下•5、用多类感知器算法求下列模式的判别函数：ω1:(-1-1)Tω2:(00)Tω3:(11)T解：将模式样本写成增广形式：x1=(-1-11)T,x2=(001)T,x3=(111)T取初始值w1(1)=w2(1)=w3(1)=(000)T，C=1。第一轮迭代（k=1）：以x1=(-1-11)T作为训练样本d1(1)=)1(1Twx1=0d2(1)=)1(2Twx1=0d3(1)=)1(3Twx1=0因d1(1)≯d2(1)，d1(1)≯d3(1)，故w1(2)=w1(1)+x1=(-1-11)Tw2(2)=w2(1)-x1=(11-1)Tw3(2)=w3(1)-x1=(11-1)T第二轮迭代（k=2）：以x2=(001)T作为训练样本d1(2)=)2(1Twx2=1d2(2)=)2(2Twx2=-1d3(2)=)2(3Twx2=-1因d2(2)≯d1(2)，d2(2)≯d3(2)，故w1(3)=w1(2)-x2=(-1-10)Tw2(3)=w2(2)+x2=(110)Tw3(3)=w3(2)-x2=(11-2)T第三轮迭代（k=3）：以x3=(111)T作为训练样本d1(3)=)3(1Twx3=-2d2(3)=)3(2Twx3=2d3(3)=)3(3Twx3=0因d3(3)d1(3)，d3(3)≯d2(3)，故w1(4)=w1(3)=(-1-10)Tw2(4)=w2(3)-x3=(00-1)Tw3(4)=w3(3)+x3=(22-1)T第四轮迭代（k=4）：以x1=(-1-11)T作为训练样本d1(4)=)4(1Twx1=2d2(4)=)4(2Twx1=-1d3(4)=)4(3Twx1=-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）：以x2=(001)T作为训练样本d1(5)=)5(1Twx2=0d2(5)=)5(2Twx2=-1d3(5)=)5(3Twx2=-1因d2(5)≯d1(5)，d2(5)≯d3(5)，故w1(6)=w1(5)-x2=(-1-1-1)w2(6)=w2(5)+x2=(000)w3(6)=w3(5)-x2=(22-2)第六轮迭代（k=6）：以x3=(111)T作为训练样本d1(6)=)6(1Twx3=-3d2(6)=)6(2Twx3=0d3(6)=)6(3Twx3=2因d3(6)d1(6)，d3(6)d2(6)，故w1(7)=w1(6)w2(7)=w2(6)w3(7)=w3(6)第七轮迭代（k=7）：以x1=(-1-11)T作为训练样本d1(7)=)7(1Twx1=1d2(7)=)7(2Twx1=0d3(7)=)7(3Twx1=-6因d1(7)d2(7)，d1(7)d3(7)，故w1(8)=w1(7)w2(8)=w2(7)w3(8)=w3(7)第八轮迭代（k=8）：以x2=(001)T作为训练样本d1(8)=1(8)Twx2=-1d2(8)=2(8)Twx2=0d3(8)=3(8)Twx2=2因d2(8)d1(8)，d2(8)d3(8)，故分类结果正确，故权向量不变。由于第六、七、八次迭代中x1、x2、x3均已正确分类，所以权向量的解为：w1=(-1-1-1)Tw2=(000)Tw3=(22-2)T三个判别函数：d1(x)=-x1-x2-1d2(x)=0d3(x)=2x1+2x2-26、采用梯度法和准则函数221(,,)[()||]8||||TTJwxbwxbwxbx式中实数b0，试导出两类模式的分类算法。解：J对w求偏导：22(),1||||*2[()||]*[sgn(|)]8||||0,TTTTTTwxbxwxbJxwxbwxbxxwxbwxwxb则分类算法为：2()(),||||(1)()(),TTTwxbxwkCwxbxwkwkCJwkwxb7、用二次埃尔米特多项式的势函数算法求解以下模式的分类问题ω1:{(01)T,(0-1)T}ω2:{(10)T,(-10)T}（1）解：建立二维的正交函数集取Hermite多项式第一、三项H0(x)=1,H2(x)=4x2-2,则1)()(),()(20102111xHxHxxx2221221021()(,)()()42xxxHxHxx2331201222()(,)()()42xxxHxHxx224412212212()(,)()()(42)(42)xxxHxHxxx（2）生成势函数按第一类势函数定义，得到势函数121242211222222212(,)()()1(42)(42)(42)(42)(42)(42)(42)(42)kijkikkkKxxxxxxxxxxxx其中Txxx),(21，Tkkkxxx),(21（3）通过训练样本逐步计算累积位势K(x)给定训练样本：ω1类为x①=(01)T,x②=(0-1)Tω2类为x③=(10)T,x④=(-10)T累积位势K(x)的迭代算法如下第一步：取x①=(01)T∈ω1，故K1(x)=K(x,x①)=222212121(42)(2)(42)2(42)(2)(42)2xxxx=222212121884(42)(42)xxxx第二步：取x②=(0-1)T∈ω1，故K1(x②)=1+8*(-4)*(-2)*20K2(x)=K1(x)=222212121884(42)(42)xxxx第三步：取x③=(10)T∈ω2，故K2(x③)=1-8-4*2*(-2)0因K2(x③)0且x③∈ω2，故K3(x)=K2(x)-K(x,x○3)=2222221212121884(42)(42)1(42)2(42)(2)xxxxxx=221211616xx第四步：取x④=(-10)T∈ω2，故K3(x④)0因K3(x④)0且x④∈ω2，故K4(x)=K3(x)=221211616xx将全部训练样本重复迭代一次，得第五步：取x⑤=x①=(01)T∈ω1，K4(x⑤)0故K5(x)=K4(x)=2212116