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

第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的标准差向量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