模式识别导论习题参考答案-齐敏

第2章聚类分析习题解答2.1设有10个二维模式样本，如图2.13所示。若21，试用最大最小距离算法对他们进行聚类分析。解：①取T11]0,0[XZ。②选离1Z最远的样本作为第二聚类中心2Z。201012221D，831D，5841D，4551D5261D，7471D，4581D，5891D，651,10D∵最大者为D71，T72]7,5[XZ742121ZZT③计算各样本与21,ZZ间距离，选出其中的最小距离。7412D，5222D，3432D，…，132,10D}13,20,17,0,2,5,4,8,2,0{),min(21iiDD④742120)},max{min(9221TDDDii,T93]3,7[XZ⑤继续判断是否有新的聚类中心出现：58740131211DDD，40522232221DDD，…113653,102,101,10DDD}1,0,1,0,2,5,4,8,2,0{),,min(321iiiDDD74218)},,max{min(31321TDDDDiii寻找聚类中心的步骤结束。⑥按最近距离分到三个聚类中心对应的类别中：3211,,:XXX；76542,,,:XXXX；10983,,:XXX135791357X1X4X3X5X8X9X7X10X2X6x1x2图2.1310个二维模式样本2.2设有5个二维模式样本如下：T1]0,0[X，T2]1,0[X，T30,2X，T4]3,3[X，T54,4X定义类间距离为最短距离，且不得小于3。利用层次聚类法对5个样本进行分类。解：(1)将每一样本看作单独一类，得11)0(XG，22)0(XG，33)0(XG，44)0(XG，55)0(XG计算各类间欧氏距离：2112)0(XXD212221222111][xxxx110212)0(3113XXD同理可求得：)0(14D，)0(15D；)0(23D，)0(24D，)0(25D；)0(34D，)0(35D；)0(45D；得距离矩阵D(0)为D(0))0(1G)0(2G)0(3G)0(4G)0(5G)0(1G0)0(2G10)0(3G250)0(4G1813100)0(5G32252020(2)将最小距离1对应的类)0(1G和)0(2G合并为一类，得到新的分类)0(),0()1(2112GGG，)0()1(33GG，)0()1(44GG，)0()1(55GG按最短距离法计算类间距离，由D(0)矩阵递推得到聚类后的距离矩阵D(1)为D(1))1(12G)1(3G)1(4G)1(5G)1(12G0)1(3G20)1(4G13100)1(5G252020(3)将D(1)中最小值2对应的类合并为一类，得D(2)。D(2))2(12G)2(3G)2(45G)2(12G0)2(3G20)2(45G13100(4)将D(2)中最小值2对应的类合为一类，得D(3)。D(3))3(123G)3(45G)3(123G0)3(45G100D(3)中的最小元素为310，聚类结束，结果为：3211,,XXXG，542,XXG2.3用K-均值算法对下列6个模式样本进行聚类分析，设聚类中心数K=2。T10,0X，T20,1X，T3]1,1[XT4]4,4[X，T54,5X，T65,5X解：①因2K，任选两个聚类中心T110,0)1(XZ和T22]0,1[)1(XZ。②计算距离，聚类：1X：11000||)1(||0||)1(||22212111ZXZXDD)1(1121SXDD2X：0||)1(||1||)1(||222121ZXZXDD)1(2212SXDD3X：1||)1(||2||)1(||232131ZXZXDD)1(2312SXDD4X：5||)1(||24||)1(||242141ZXZXDD)1(2412SXDD…可得到：1},{)1(111NSX5},,,,,{)1(2654322NSXXXXX③计算新的聚类中心：T110,0)2(XZT6321228.2,2.3)(511)2(2XXXXZXSN④判断：)1()2(jjZZ，2,1j，故返回第②步。⑤由新的聚类中 心得 信息技术培训心得 下载关于七一讲话心得体会关于国企改革心得体会关于使用希沃白板的心得体会国培计划培训心得体会 ：1X：||)2(||||)2(||212111ZXZXDD)2(11SX2X：||)2(||||)2(||222121ZXZXDD)2(12SX3X：||)2(||||)2(||132131ZXZXDD)2(13SX同理有：)2(24SX，)2(25SX，)2(26SX得3},,,{)2(13211NXXXS3},,,{)2(26442NXXXS⑥重新计算聚类中心：T3212113.0,7.0)(311)3(1XXXXZXSNT6542223.4,7.4)(311)3(2XXXXZXSN⑦)2()3(jjZZ，2,1j，返回第②步，以Z1(3)，Z2(3)为中心进行聚类。⑧按新的聚类中心分类，求得的分类结果与前一次迭代结果相同，即)2()3(11SS，)2()3(22SS○9计算新聚类中心向量值，聚类中心与前一次结果同，即T113.0,7.03)4(ZZ，T223.4,7.43)4(ZZ算法结束。聚类中心为：T13.0,7.0Z，T23.4,7.4Z聚类结果为：},,{)2(3211XXXS，},,{)2(6442XXXS2.4用ISODATA算法对题2.1中的10个模式样本进行聚类分析。解：10个模式样本为T1]0,0[X，T2]1,1[X，T32,2X，T4]7,3[X，T56,3XT6]6,4[X，T7]7,5[X，T83,6X，T9]3,7[X，T104,7X(1)第一步：任意预选NC=1，T110,0XZ，K=3，1N，2S，4C，L=0，I=5。(2)第二步：按最近邻规则聚类。目前只有一类，10},,,{110211NS，XXX。(3)第三步：因NN1，无聚类删除。(4)第四步：修改聚类中心1111SNXXZ90.380.347373675646373221100101(5)第五步：计算类内平均距离1D。11111SNDXZX1101211101ZXZXZX2222229.348.379.318.319.308.3010119.388.31101(6)第六步：计算总体平均距离D。因只有一类，19.31DD。(7)第七步：不是最后一次迭代，且2KNC，故进入第八步进行分裂运算。(8)第八步：求S1的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 差向量T12,111σ。2111,10211212111111101zxzxzx2228.378.318.3010132.26.531012122,10212222121212101zxzxzx2229.349.319.3010139.29.56101得T39.2,32.21σ。(9)第九步：1σ的最大分量39.2max1。(10)第十步：因Smax1且2KNC，将Z1分裂为两个新的聚类中心。因max1是1σ的第二个分量，故在Z1的第二个分量方向上进行分裂，分裂系数k选为0.5，得TTTmax1110.5,80.339.25.090.3,80.35.090.3,80.3ZTTTmax1171.2,80.339.25.090.3,80.35.090.3,80.3Z令11ZZ，12ZZ，NC加1，迭代次数加1（I=2）。跳回到第二步，进行第2次迭代运算。(11)第二步：按最近邻规则对所有样本聚类。78.2171.2080.30||||45.4010.5080.30||||222112221111ZXZXDD211112SDDX76.1071.2180.31||||65.2410.5180.31||||222222221221ZXZXDD222122SDDX…222102,10221101,1071.2480.37||||10.5480.37||||ZXZXDD1102,101,10SDDX得到两个聚类分别为1076541,,,,XXXXXS，N1=5983212,,,,XXXXXS，N2=5(12)第三步：因N1和N2都大于N，无聚类删除。(13)第四步：修改聚类中心，得T1076541]00.6,40.4[30225151XXXXXZT983212]80.1,20.3[9165151XXXXXZ(14)第五步：计算类内平均距离1D和2D，得11017161514151ZXZXZXZXZXD22222200.6440.4700.6640.4300.6740.435159.12928232221251ZXZXZXZXZXD22222280.1320.3780.1120.3180.1020.305185.2(15)第六步：计算总体平均距离D，得22.285.2559.151015510112121jjjDDDNND(16)第七步：因这是偶数次迭代，符合第七步的第（3）条，进入第十一步。(17)第十一步：计算聚类中心之间的距离，得37.42112ZZD。(18)第十二步：比较D12与C，这里CD12。(19)第十三步：根据上一步结果，聚类中心不发生合并。(20)第十四步：不是最后一次迭代，不修改参数，迭代次数加1（I=3），回到第二步。进行第3次迭代运算。(21)第二步到第六步：与前一次迭代计算的结果相同。(22)第七步：不满足任何一种情况，继续执行第八步，进入分裂程序。(23)第八步：计算S1和S2的标准差向量T12,111σ和T22,212σ。2111,10211712116121151211411151zxzxzxzxzx2222240.4740.4540.4440.4340.435150.12122,10212722126221252212421251zxzxzxzxzx2222200.6400.6700.6600.6600.675110.122119221812213122121221112151zxzxzxzxzx2222220.3720.3620.3220.3120.305179.222229222822223222222222122251zxzxzxzxzx2222280.1380.1380.1280.1180.105117.1即：T110.1,50.1σ和T217.1,79.2σ。(24)第九步：5.1max1，79.2max2。(25)第十步：Smax2，且满足DD2和)1(22NN，Z2满足分裂条件。因max2是2σ的第一个分量，故在Z2的第一个分量方向上进行分裂，分裂系数k选为0.5，得TTTmax1271.2,20.571.2,79.25.080.371.2,5.080.3ZTTTmax1271.2,41.271.2,79.25.080.371.2,5.080.3Z令22ZZ，23ZZ，NC加1，迭代次数加1（I=4）。跳回到第二步，进行第4次迭代运算。(26)第二步：按最近邻规则对所有样本聚类。15.1371.2041.20||||38.3471.2020.50||||45.4010.5080.30||||223113222112221111ZXZXZXDDD3113SDX最小4.9171.2141.21||||20.5671.215.21||||65.2410.5180.31||||223232222222221221ZXZXZXDDD3232SDX最小…22.7371.2441.27||||4.9071.2405.27||||11.4510.5480.37||||22310310222102,10221101,10ZXZXZX，DDD2102,10SDX最小得到三个聚类分别为76541,,,XXXXS，N1=410982,,XXXS，N2=33213,,XXXS，N3=3(27)第三步：因N1，N2，N3都大于N，无聚类删除。(28)第四步：修改聚类中心，得T76541]50.6,75.3[26154141XXXXZT10982]33.3,67.6[10203131XXXZT3213]00.1,00.1[333131XXXZ(29)第五步：计算类内平均距离1D，2D，2D得17161514141ZXZXZXZXD222250.6675.3350.6775.33{41}50.6775.3550.6675.34222293.02102928231ZXZXZXD22222233.3467.6733.3367.6733.3367.663166.0333231331ZXZXZXD2222221212111110103194.0(30)第六步：计算总体平均距离D，得213213341011jjjDDDDNND85.094.0366.0393.04101(31)第七步：因是偶数次迭代，符合第七步的第（3）条，进入第十一步。(32)第十一步：计算所有聚类中心之间的距离。31.433.350.667.675.3222112ZZD15.6150.6175.3223113ZZD13.6133.3167.6223223ZZD(33)第十二步：比较所有聚类中心间的距离与C的大小，这里均大于C。(34)第十三步：根据上一步结果，聚类中心不发生合并。(35)第十四步：不是最后一次迭代，不修改参数，迭代次数加1（I=5），回到第二步。进行第5次迭代运算。(36)第二步到第六步：与前一次迭代计算的结果相同。(37)第七步：此为最后一次迭代，置0C，跳到第十一步。(38)第十一步：计算所有聚类中心之间的距离，结果同前。(39)第十二步：与前一次迭代结果相同。(40)第十三步：没有合并发生。(41)第十四步：是最后一次迭代，故算法结束。聚类结果为：76541,,,:XXXX；10982,,:XXX；3213,,:XXX2.5给出最大最小距离算法程序框图，编写程序，自选一组分别属于三类的二维模式样本，并对它们进行聚类分析。（略）2.6给出K-均值算法的程序框图，编写程序，自选一组分别属于三类的三维模式样本，并对它们进行聚类分析。（略）2.7给出ISODATA算法的程序框图，编写程序，利用题2.1数据进行聚类分析，在确认程序编写正确之后，选用附录C数据进行聚类分析。（略）第3章判别函数及几何分类法习题解答3.1在一个10类的模式识别问题中，有三类单独满足多类情况1，其余的类别满足多类情况2。问该模式识别问题所需判别函数的最少数目为多少？答：满足多类情况1的3类问题，需要3个判别函数，满足多类情况2的7类问题，需要212)17(7个判别函数，3+21=24即共需24个判别函数。3.2一个三类问题，其判别函数为42211xxdX，44212xxdX，313xdX（1）设这些函数是在多类情况1条件下确定的，绘出判别界面及每一模式类别的区域。（2）设为多类情况2，并使XX112dd，XX213dd，XX323dd，绘出判别界面及每一模式类别区域。（3）设X1d，X2d和X3d是在多类情况3的条件下确定的，绘出其判别界面及每一模式类别的区域。解：（1）多类情况1时的判别界面及每一模式类别的区域如解图3.1所示。（2）多类情况2时的判别界面及每一模式类别的区域如解图3.2所示。（3）多类情况3：三个判别界面方程为：086)44()42()()(2212121xxxxxddXX，即0432x0722)3()42()()(2112131xxxxxddXX0142)3()44()()(2112132xxxxxddXX满足0)()(21XdXd且0)()(31XdXd的区域属于1类分布区域。满足0)()(12XdXd且0)()(32XdXd的区域属于2类分布区域。满足0)()(13XdXd且0)()(23XdXd的区域属于3类分布区域。判别界面及各模式类的区域如解图3.3所示。0)(3xd12132x1x0)(1xd0)(2xd22340-40)(23xd11322x1x0)(12xd0)(13xd22340-4解图3.1多类情况1时的判别界面及各类别的区域解图3.2多类情况2时的判别界面及各类别的区域3.3有5个良好分布的二维模式，问把它们任意线性地分为两组的概率是多少？解：∵nNnNCnNPnjjNN1112),(011∴20241404415516875.01611)(212)2,5(jjCCCCP即所求概率为0.6875。3.4设准则函数为2TT2||)(||||81),,(bbbJXWXWXXW式中实数b>0，试导出两类模式的分类算法。解：用梯度法求识别两类模式的判别函数权向量的递推式。WXWbJJ,,WXWXXWXWXbbbTTT2||)(2||||81)(sgn||)(||||41TTT2bbbXWXXXWXWX其中，0,10,1sgnTTTbbbXWXWXW若若当0TbXW时，0J；当0TbXW时，)(||||2)(2||||41T2T2bbJXWXXXXWX。由此得：JckkWW121321322x1x0)(21XdXd2313dddd0)(31XdXd0)(32XdXd3212dddd3121dddd03414解图3.3多类情况3时的判别界面及各类别的区域0),(||||0,0TT2TbbcbkXWXWXXXWW若若3.5已知两类训练样本为1：TTTT]0,1,1[,]1,0,1[,]0,0,1[,]0,0,0[2：TTTT]1,1,1[,]0,1,0[,]1,1,0[,]1,0,0[设T]0,2,2,1[)1(W，用感知器算法求解判别函数，并绘出判别界面。解：感知器算法为：0,0,1TTiiikckkkkXWXWXWWW若若，c为正的校正增量。首先，将所有样本写成增广向量的形式并编号，属于2的样本乘以(-1)：T1]1,0,0,0[X，T2]1,0,0,1[X，T3]1,1,0,1[X，T4]1,0,1,1[XT5]1,1,0,0[X，T6]1,1,1,0[X，T7]1,0,1,0[X，T8]1,1,1,1[X取c=1开始迭代：第一轮：001000]0221[)1(1TXW，故T1]1,2,2,1[)1(2XWW001001]1221[)2(2TXW，故T2]2,2,2,0[)2(3XWW001101]2220[)3(3TXW，故T3]3,1,2,1[)3()4(XWW021011]3121[)4(4TXW，故)4()5(WW021100]3121[)5(5TXW，故T5]2,2,2,1[)5()6(XWW)6()7(021110]2221[)6(6TWWXW，故T77T]1,2,3,1[)7()8(001010]2221[)7(XWWXW，故)8()9(031111]1231[)8(8TWWXW，故第二轮：)9()10(01)9(1TWWXW，故)10()11(02)10(2TWWXW，故T33T]2,1,3,2[)11()12(00)11(XWWXW，故)12()13(01)12(4TWWXW，故T55T]1,2,3,2[)13()14(01)13(XWWXW，故)14()15(04)14(6TWWXW，故)15()16(02)15(7TWWXW，故)16()17(02)16(8TWWXW，故第三轮：)17()18(01)17(1TWWXW，故)18()19(03)18(2TWWXW，故)19()20(01)19(3TWWXW，故T44T]2,2,2,3[)20()21(00)20(XWXWW，故T55T]1,3,2,3[)21()22(00)21(XWWXW，故)22()23(04)22(6TWWXW，故)23()24(01)23(7TWWXW，故)24()25(01)24(8TWWXW，故第四轮：)25()26(01)25(1TWWXW，故)26()27(04)26(2TWWXW，故)27()28(01)27(3TWWXW，故)28()29(02)28(4TWWXW，故)29()30(02)29(5TWWXW，故)30()31(04)30(6TWWXW，故)31()32(01)31(7TWWXW，故)32()33(01)32(8TWWXW，故该轮迭代分类结果全部正确，故解向量T]1,3,2,3[W，对应的判别函数为：1323321xxxdX判别界面0Xd如解图3.4所示，图中虚线为判别界面与坐标面21oxx，31oxx，32oxx的交线。x3.6已知三类问题的训练样本为1：T]1,1[，2：T]0,0[，3：T]1,1[试用多类感知器算法求解判别函数。解：将训练样本写成增广形式：T1]1,1,1[X，T2]1,0,0[X，T3]1,1,1[X取初始值T321]0,0,0[111WWW，c=1，迭代过程如下：第一次迭代，以1X作为训练样本，计算得0111T11XWd0111T22XWd0111T33XWd因为1121dd且1131dd不成立，故T121]1,1,1[12XWWT122]1,1,1[12XWW-T133]1,1,1[12XWW第二次迭代，以2X作为训练样本，计算得1222T11XWd1222T22XWd1222T33XWd因为2212dd且2232dd不成立，故T211]0,1,1[23XWWT222]0,1,1[23XWWT233]2,1,1[23XWW第三次迭代，以3X作为训练样本，计算得2333T11XWd2333T22XWd0333T33XWd因为3313dd，但3323dd不成立，故T11]0,1,1[34WWT322]1,0,0[34XWW解图3.4判别界面T333]1,2,2[34XWW第四次迭代：以1X作为训练样本，计算得：2441T11XWd1441T22XWd5441T33XWd因为4421dd且4431dd，故：4511WW，4522WW，4533WW第五次迭代：以2X作为训练样本，计算得：0552T11XWd1552T22XWd1552T33XWd因为5512dd且5532dd不成立，故T211]1,1,1[56XWWT222]0,0,0[56XWWT233]2,2,2[56XWW第六次迭代：以3X作为训练样本，计算得：3663T11XWd，062d，263d因为6613dd且6623dd，故：6711WW，6722WW，6733WW第七次迭代：以1X作为训练样本，计算得：1771T11XWd，072d，673d因为7721dd且7731dd，故：7811WW，7822WW，7833WW第八次迭代：以2X作为训练样本，计算得：1882T11XWd0882T22XWd2882T33XWd因为8812dd且8832dd，故：8911WW，8922WW，8933WW第六、七、八次迭代中，对三个样本都已正确分类，故权向量的解为：T3T2T1]2,2,2[]0,0,0[]1,1,1[WWW，，相应的三个判别函数为：1211xxdX02Xd222213xxdX3.7用LMSE算法求解3.5题中两类模式的判别函数，并绘出判别界面。解： 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 化增广样本矩阵为：11111010111011001011110110011000X首先求伪逆矩阵T1T#XXXX：84444422424242241111101011101100101111011001100011111111101101001110100010001110TXX*TT1T1XXXXXX422242224444242224444422224444422242422442424844442424844422424844422442442422424844422424844442424844442422442424422844424422844442422844442424844444224242422412111120010201002121321616161632001603201600321921111111111011010011101000100011102111120010201002121T1T#XXXX11010012111111111111111111111111121取初值T1,1,1,1,1,1,1,11B和c=1，开始迭代：(1)11BXW#613131311111111111010012111111111111111111111111121(2)111BXWeTT1,1,1,1,1,1,1,161,61,21,61,61,61,21,61T65,65,21,65,65,65,21,65此时，1e的分量全部为负值，停止迭代。观察到0T61,61,21,61,61,61,21,611XW故有解，解为T61,31,31,311W。判别函数为：6313131321xxxdX判别界面如解图3.5所示，图中虚线为判别界面分别与坐标面21oxx，31oxx，32oxx的交线。3.8已知两类模式1：TT]1,0[,]1,0[；2：TT]0,1[,]0,1[用LMSE算法检验模式样本的线性可分性。解：规范化增广样本矩阵为：101101110110X求得伪逆矩阵为：11110022220041T1T#XXXX取初值T1,1,1,11B和c=1，则T0,0,011BXW#T]0,0,0,0[)1(XWT1,1,1,121111BXWe01/2-1/21/2x2x3x1解图3.5判别界面因为)1(e的全部分量均为负值，停止迭代，可能为线性不可分情况。考虑此时0)1(XW不成立，故模式线性不可分。3.9用二次埃尔米特多项式的势函数法计算3.8题中两类模式的判别函数。解：埃尔米特多项式的前三项为：24)(2)(1)(2210xxHxxHxH，，根据题意，建立二维的正交函数集：1)()(),()(20102111xHxHxxX24)()(),()(2222102122xxHxHxxX24)()(),()(2120122133xxHxHxxX生成势函数：)24)(24()24)(24(1)()(),(2121222231xxxxKkkiikikXXXX式中：T21T21],[],[kkkxxxxXX，。设初始积累势函数0)(0XK。逐步计算积累势函数)(XK：(1)11T1]1,0[XX，，所以188),(),()()(21221101xxKKKKXXXXXX(2)12T2]1,0[XX，，因09108)1(8)(2212XK，分类正确，所以)()(12XXKK。(3)23T3]0,1[XX，，因0711808)(2223XK，分类正确，所以)()(23XXKK。(4)24T4]0,1[XX，，因071)1(808)(2234XK，分类正确，所以)()(34XXKK。(5)11T1]1,0[XX，，因0910818)(2241XK，分类正确，所以)()(45XXKK。以上对全部训练样本都能正确分类，故算法收敛于判别函数：188)()(21225xxKdXX3.10用指数型势函数2exp),(kkKXXXX求解3.8题中两类模式的判别函数，设1。解：设T21T21],[],[kkkxxxxXX，，指数型势函数在二维时的形式为：222211)()(exp),(kkkxxxxKXX设初始积累势函数0)(0XK，对样本T2T11]1,0[]1,0[:XX，；T4T32]0,1[]0,1[:XX，迭代过程如下：(1)1T1]1,0[X，所以),(),()()(1101XXXXXXKKKK])1([22212221])1()0[(expxxexx(2)1T2]1,0[X，因0)(4)40(21eeKX，所以)()(12XXKK。(3)2T3]0,1[X，因0)(2)11(32eeKX，所以])1[(])1([32322212221),()()(xxxxeeKKKXXXX(4)2T4]0,1[X，因0)(4243eeKX，所以])1[(])1[(])1([434222122212221),()()(xxxxxxeeeKKKXXXX(5)1T15]1,0[XX，因0)(22054eeeKX，所以)()(45XXKK。(6)1T26]1,0[XX，因0)(22465eeeKX，所以])1([])1[(])1[(])1([6562221222122212221),()()(xxxxxxxxeeeeKKKXXXX(7)2T37]0,1[XX，因0)(22026eeeeK7X，所以)()(67XXKK。(8)2T48]0,1[XX，因0)(204287eeeeKX，所以)()(78XXKK。(9)1T19]1,0[XX，因0)(422098eeeeKX，所以)()(89XXKK。(10)1T210]1,0[XX，因0)(0224109eeeeKX，所以)()(910XXKK。从模式7X到10X的四次迭代过程中，全部模式都已正确分类，故算法收敛于判别函数：])1([])1[(])1[(])1([102221222122212221)()(xxxxxxxxeeeeKdXX3.11给出感知器算法程序框图，编写算法程序，解习题3.5，然后采用附录C中的数据。（略）3.12给出LMSE算法程序框图，编写算法程序，解习题3.7，然后采用附录C中的数据。（略）3.13编写二次埃尔米特多项式的势函数算法程序，解习题3.9。（略）1第5章特征选择与特征提取习题解答5.1假定iω类的样本集为},,,{4321XXXX，它们分别为T1]2,2[X，T2]2,3[X，T3]3,3[X，T4]2,4[X（1）求类内散布矩阵；（2）求类内散布矩阵的特征值和对应的特征向量；（3）求变换矩阵A，将二维模式变换为一维模式。解：（1）41493243323224141iiXM类内散布矩阵：41TT41iiiMMXXC49,34932,4243,3332,3232,222411630021168142742792127273841（2）①由0||CI求特征值。01630021016321211，1632②由0)(1uCI解得1对应的特征向量1u为T]0,1[1u。由0)(2uCI解得2对应的特征向量2u为T]1,0[2u。（3）①选择较小特征值1632对应的特征向量T]1,0[2u构成变换矩阵。22u已为归一化特征向量，直接构成变换矩阵：1,0][T2uA②变换：222]1,0[1*1AXX223]1,0[2*2AXX333]1,0[3*3AXX224]1,0[3*3AXX5.2给定两类样本，分别为1ω：T1]5,5[X，T2]4,5[XT3]5,4[X，T4]6,5[XT5]5,6[X2ω：T6]5,5[X，T7]6,5[XT8]4,5[X，T9]5,4[X利用自相关矩阵R作K-L变换，进行一维特征提取。解：①91T91jjjXXR5,4544,5455,555914.254.244.242.2422922022021891②求特征值。由0||IR有304.254.244.242.24032.196.49228.486.49232.19146.496.492得2.491，4.02，选择较大的特征值1λ。③求变换矩阵U。a)计算1λ对应的特征向量T12111],[uuu：由011uIR有02.494.254.244.242.492.241211uu得T1]02.1,1[u，归一化为T1]02.1,1[04.21u。变换矩阵][1uU。④K-L变换。由XUXT*有06.71T*1XUX3.62T*2XUX3.6*3X，8.7*4X，8.7*5X，06.7*6X，8.7*7X，3.6*8X，3.6*9X。5.3设有8个三维模式，分别属于两类，5.0)()(21ωPωP。各类的样本为1ω：T1]1,0,0[X，T2]1,1,0[XT3]0,1,0[X，T4]1,1,1[X2ω：T5]0,0,0[X，T6]1,0,1[XT7]0,0,1[X，T8]0,1,1[X（1）求类内散布矩阵及其特征值、特征向量，以小特征值对应的特征向量构成变换矩阵，对模式向量进行一维特征提取。（2）利用类间散布矩阵作K-L变换，进行一维特征提取。4（3）利用总体散布矩阵作K-L变换，进行一维特征提取。解：（1）①类内散步矩阵21T}))({()(iiiiwEPMXMXS，iX85T22T241T11T1)41)(()41)((kkkkkkPPMMXXMMXX2211)()(CCPP其中，411331411110101101004141kkXM852113410110011010004141kkXM41T11T141kkkMMXXC1,1,11110,1,00101,1,01101,0,0100413,3,141331413111311131619939933311613212311114185T22T2)41kkkMMXXC011011001001101101000000411134111341531113111316111311333916110101111341即：31113111316121CCC。又5.0)()()(21PPP。3111311131610.52)(2CCCSPw②特征值由0||wSI得421，13。③选13对应的特征向量构成变换矩阵，进行一维特征提取。13对应的归一化特征向量为：T3]1,1,1[31u。变换矩阵：T3]1,1,1[31][uU。31100]1,1,1[311T*1XUX32110]1,1,1[312T*2XUX31010]1,1,1[31*3X31111]1,1,1[31*4X0*5X，0*6X，31*7X，0*8X。6（2）利用类间散布矩阵作K-L变换，进行一维特征提取。①21T00))()((iiiibPMMMMS其中，1112111381331812121)(21210MMMMiiiP11141111213314101MM11141111211134102MMT02022T01011))()(())()((MMMMMMMMSPPb111411114121111411114121111111111161111111111321111111111321②特征值由0||bSI得31，032。③选大特征值31对应的特征向量：T1]1,1,1[31u。变换矩阵：T1]1,1,1[31][uU。特征提取结果同（1）。（3）利用总体散布矩阵作K-L变换，进行一维特征提取。①wbtSSS710001000141111111111161311131113161②特征值由0||tSI得：1321。③11对应的特征向量：T1]0,0,1[u变换矩阵：T1]0,0,1[][uU0100]0,0,1[1T*1XUX0110]0,0,1[2T*2XUX0010]0,0,1[*3X1111]0,0,1[*4X0*5X，1*6X，1*7X，1*8X。1第6章句法模式识别习题解答6.1用链码法描述5～9五个数字。解：用弗利曼链码表示，基元如解图6.1所示：数字5~9的折线化和量化结果如解图6.2所示：各数字的链码表示分别为：“5”的链码表示为434446600765x；“6”的链码表示为3444456667012x；“7”的链码表示为00066666x；“8”的链码表示为21013457076543x；“9”的链码表示为5445432107666x。20134567解图6.1弗利曼链码基元解图6.2数字5~9的折线化和量化结果26.2定义所需基本基元，用PDL法描述印刷体英文大写斜体字母“H”、“K”和“Z”。解：设基元为：用PDL法得到“H”的链描述为)))))(~((((ddcddxH；“K”的链描述为))((baddxK；“Z”的链描述为))((ccgxZ。6.3设有文法),,,(SPVVGTN，NV，TV和P分别为},,{BASVN，},{baVT：P①aBS，②bAS，③aA，④aSA⑤bAAA，⑥bB，⑦bSB，⑧aBBB写出三个属于)(GL的句子。解：以上句子ab，abba，abab，ba，baab，baba均属于)(GL。6.4设有文法),,,(SPVVGTN，其中},,,{CBASVN，}1,0{TV，P的各生成式为①AS0，②BS1，③CS1bcadeabbaabbAabSaBS①⑦②③abaBS①⑥babAS②③abababaBabSaBS①⑦①⑥baabbaaBbaSbAS②④①⑥babababAbaSbAS②④②③3④AA0，⑤BA1，⑥1A⑦0B，⑧BB0，⑨CC0，⑩1C问00100x是否属于语言)(GL？解：由可知00100x属于语言)(GL。6.5写出能产生图示树的扩展树文法，设基元a，b分别为“→”和“↓”，它所描述的模式是什么？解：1.写出生成树的扩展树文法生成式集：2.检查非终止符的等价性。a$ababaaab