数据挖掘与数据分析 第九章课后习题及答案

第九章课后习题答案详解1.考虑下图中的10个点，使用K均值聚类法，以（2,7）和（6,3）为初始聚类中心，将图中所有样本点聚为2类。答：整理初始数据，如下表1-1所示：表1-1初始数据坐标(1,9)(2,1)(2,7)(4,3)(4,8)(5,5)(6,3)(7,6)(8,2)(9,4)质心1(2,7)质心2(6,3)（1）计算距离并划分数据计算所有点坐标与初始质心之间的距离，并进行第一次分类。使用欧式距离度量相似性，距离越小则相似度越高。第一次迭代：所有点坐标与初始质心1(2,7)间的距离计算过程如下：(1−((((所有点坐标与初始质心2(6,3)间的距离计算过程如下：(1−((((根据各样本数据与初始质心1和2的距离，将各样本点划分到距离最近的质心所在的类中，则得到Group1(2,7)=[(1,9),(2,7),(4,8)],Group2(6,3)=[(2,1),(4,3),(5,5),(6,3),(7,6),(8,2),(9,4)]。更新各个聚类的质心，得到Mean1(2,7)=((1+2+4)/3，(9+7+8)/3)=(2.33,8);Mean2(6,3)=((2+4+5+6+7+8+9)/7,(1+3+5+3+6+2+4)/7)=(5.86,3.43)。第一次迭代结果汇总如下表1-2所示：表1-2第一次迭代结果坐标(1,9)(2,1)(2,7)(4,3)(4,8)(5,5)(6,3)(7,6)(8,2)(9,4)Distance(2,7)[2.24,6.00,0.00,4.47,2.24,3.61,5.66,5.10,7.81,7.62];Distance(6,3)[7.81,4.47,5.66,2.00,5.39,2.24,0.00,3.16,2.24,3.16]Group1(2,7)[(1,9),(2,7),(4,8)]Group2(6,3)[(2,1),(4,3),(5,5),(6,3),(7,6),(8,2),(9,4)]Mean1(2,7)(2.33,8)Mean2(6,3)(5.86,3.43)（2）使用均值作为新的质心将两个分组中样本数据的均值作为新的质心，并重复之前步骤，迭代计算每个数据点到新质心的距离，将样本数据划分到与其距离最近的类中。表1-3第二次迭代结果坐标(1,9)(2,1)(2,7)(4,3)(4,8)(5,5)(6,3)(7,6)(8,2)(9,4)Distance(2,7)[1.66,7.01,1.05,5.27,1.67,4.02,6.20,5.08,8.26,7.78];Distance(6,3)[7.39,4.56,5.26,1.91,4.93,1.79,0.45,2.81,2.57,3.19]Group1(2.33,8)[(1,9),(2,7),(4,8)]Group2(5.86,3.43)[(2,1),(4,3),(5,5),(6,3),(7,6),(8,2),(9,4)]Mean1(2.33,8)(2.33,8)Mean2(5.86,3.43)(5.86,3.43)（3）算法终止条件此时新求得的质心与原质心相同，满足终止条件，算法结束。则最终所求得两类为，结果展示如下图1：Group1(2.33,8)=[(1,9),(2,7),(4,8)]Group2(5.86,3.43)=[(2,1),(4,3),(5,5),(6,3),(7,6),(8,2),(9,4)]图SEQ图\*ARABIC1K均值聚类结果2.K均值聚类算法有哪几步？答：K均值聚类算法有如下几步：（1）随机选取K个数据点作为（起始的）聚类中心点；（2）按照距离最近原则分配数据点到对应类；（3）计算每类的数据点平均值，找到新的聚类中心；（4）计算数据点到聚类中心的总距离；（5）如果与上一次相比总距离下降，聚类中心替换；（6）重复（2）-（5）直到总距离不再下降或者达到指定计算次数。3.K均值聚类有哪些优缺点?答：K-means优点（1）结构简单，比较容易实现、可解释性比较强（2）收敛速度快、聚类效果较优（3）处理大数据集时算法保持可伸缩性和高效性，（4）当簇接近高斯分布时，算法效果较好。K-means缺点（1）在簇的平均值可被定义的情况下才能使用，可能不适用于某些应用；（2）在K-means算法中K是事先给定的，这个K值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适，而K值选取不当可能会导致较差的聚类结构；（3）在K-means算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果(可能会陷入死循环)；（4）该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，这样得到的结果只是局部最优，因此当数据量非常大时，算法的时间开销是非常大的；（5）若簇中含有异常点，将导致均值偏离严重(即:对噪声和孤立点数据敏感)；（6）不适用于发现非凸形状的簇或者大小差别很大的簇。（7）如果各隐含类别的数据不均衡，会导致聚类效果不佳。K均值聚类算法如何选择最佳K值？答：评价最佳K值最常用的方法叫轮廓系数，其计算步骤如下：（1）对于第i个对象，计算它到所属簇中所有其他对象的平均距离，记ai(体现凝聚度)（2）对于第i个对象和不包含该对象的任意簇，计算该对象到给定簇中所有对象的平均距离，记bi(体现分离度)（3）第i个对象的轮廓系数为si=(bi-ai)/max(ai,bi)（4）从上面可以看出，轮廓系数取值为[-1,1]，其值越大越好，且当值为负时，表明ai（5）将每个样本的轮廓系数求和取平均，即可获得对应k的轮廓系数，选择轮廓系数最高的k为最佳K值K均值聚类算法如何度量样本的相似性？答：K均值聚类是基于距离的聚类算法，使用距离作为相似性评价指标。两个数据对象的