模式识别第二章习题解答

题1：画出给定迭代次数为n的系统聚类法的算法流程框图开始选择距离函数的形式；选择聚类的方法输入N个模式样本的特征向量计算NN维距离矩阵(0)D迭代次数设置nN求距离矩阵中的元素ijD——应按不同的距离函数计算，将二类合并，建立新的距离矩阵(1)NnD1nn0n？输出聚类的分级树停是否题2：对如下5个6维模式样本，用最小聚类准则进行系统聚类分析x1:0,1,3,1,3,4x2:3,3,3,1,2,1x3:1,0,0,0,1,1x4:2,1,0,2,2,1x5:0,0,1,0,1,0第1步：将每一样本看成单独一类，得(0)(0)(0)112233(0)(0)4455{},{},{}{},{}GxGxGxGxGx计算各类之间的欧式距离，可得距离矩阵(0)D(0)1G(0)2G(0)3G(0)4G(0)5G(0)1G0(0)2G230(0)3G25240(0)4G241570(0)5G26253120第2步：矩阵(0)D中最小元素为3，它是(0)3G和(0)5G之间的距离，将他们合并为一类，得新的分类为(1)(0)(1)(0)(1)(0)(0)(1)(0)112233544{},{},{,},{}GGGGGGGGG计算聚类后的距离矩阵(1)D(1)1G(1)2G(1)3G(1)4G(1)1G0(1)2G230(1)3G25240(1)4G241570第3步：由于(1)D中距离最小者为7，它是(1)3G与(1)4G之间的距离，于是合并(1)3G和(1)4G，得新的分类为(2)(1)(2)(2)(2)(1)(1)1122334{},{},{,}GGGGGGG同样，按最小距离准则计算距离矩阵(2)D，得(2)1G(2)2G(2)3G(2)1G0(2)2G230(2)3G24150第4步：同理得(3)(2)(3)(2)(2)11223{},{,}GGGGG满足聚类要求，如聚为2类，聚类完毕。题3：选2k，11210(1),(1)zxzx，用K-均值算法进行聚类分析第一步：选取1121007(1),(1)06zxzx第二步：根据聚类中心进行聚类，得到1123456782910111220(1){,,,,,,,}(1){,,,,}SxxxxxxxxSxxxxx第三步：计算新的聚类中心121128(1)1291020(1)21.250011(2)()1.125087.666711(2)()7.333312xSxSzxxxxNzxxxxN第四步：因(2)(1),1,2jjzzj，故回到第二步第二步：根据新的聚类中心重新进行聚类，得到1123456782910111220(2){,,,,,,,}(2){,,,,}SxxxxxxxxSxxxxx第三步：计算新的聚类中心121128(2)1291020(2)21.250011(3)()1.125087.666711(3)()7.333312xSxSzxxxxNzxxxxN第四步：(3)(2),1,2jjzzj，所以算法收敛，得聚类中心为121.25007.6667,1.12507.3333zz迭代结束。题4：画出ISODATA算法的流程框图（第一步）输入参数（第二步）近邻聚类计算聚类中心、均值等最后一次？2cKN最后一次？偶次或2cNK（第十一步）合于合并条件？（第八步）分裂运算合并运算置0c（第七步）是是否不完成完成是否END改变输入不改变输入是否否非最后一次题5：试用ISODATA算法对如下模式分布进行聚类分析：{x1(0,0),x2(3,8),x3(2,2),x4(1,1),x5(5,3),x6(4,8),x7(6,3),x8(5,4),x9(6,4),x10(7,5)}从题目中我们可知，10N。假如取初始值1cN，100z，则具体运算步骤为：第一步：取参数2,1,1,4,0,4NscKLI。第二步：因只有一个聚类中心，故11210{,,,}Sxxx和110N。第三步：因1NN，无子集可抛弃。第四步：修改聚类中心1113.9013.80xSzxN第五步：计算jD11111||||3.0749xSDxzN第六步：计算D13.0749DD第七步：因还不是最后一次迭代，且/2cNK，故进入第八步。第八步：求1S中的标准差向量12.21132.5219第九步：1中最大分量是2.5219，因此1max2.5219第十步：因1maxS且/2cNK，可将1z分裂成两个新的聚类。设max0.51.26jjr，则13.905.06z，23.902.54z，cN增加1，跳回到第二步。第二步：新的样本集为1268910{,,,,}Sxxxxx，213457{,,,,}Sxxxxx则125NN。第三步：因1N和2N都大于N，无子集可抛弃。第四步：修改聚类中心15.005.80z，22.801.80z第五步：计算,1,2jDj12.28D，22.41D第六步：计算D2.3450D第七步：因这是偶迭代次数，因此进入第十一步第十一步：因0L，故聚类中心不发生合并，转至第十四步第十四步：因还不是最后一次迭代，且经判断不需要修改给定的参数，回到第二步第二步：新的样本集为12678910{,,,,,}Sxxxxxx，21345{,,,}Sxxxx则126,4NN。第三步：因1N和2N都大于N，无子集可抛弃。第四步：修改聚类中心15.175.33z，22.001.50z第五步：计算,1,2jDj12.27D，21.87D第六步：计算D2.11D第七步：该步中没有一种情况可被满足，继续执行第八步。第八步：计算12678910{,,,,,}Sxxxxxx和21345{,,,}Sxxxx中的标准差121.341.87,1.971.12第九步：1max1.97S，且1DD和12(1)NN则将1z分裂成两个新的聚类。设max0.50.99jjr，则1235.175.172.00,,6.324.351.50zzz，cN增加1，跳回到第二步。第二步：新的样本集为：126{,}Sxx，2578910{,,,,}Sxxxxx，3134{,,}Sxxx1232,5,3NNN第三步：因1N，2N和3N都大于N，无子集可抛弃。第四步：修改聚类中心1233.505.801.00,,8.003.801.00zzz第五步：计算,1,2,3jDj10.50D，20.95D，30.94D第六步：计算D0.86D第七步：因为最后一次迭代，跳到第十四步第十四步：最后一次迭代，故算法结束。最终将原样本集聚成三类126{,}Sxx，2578910{,,,,}Sxxxxx，3134{,,}Sxxx。