改进的k-means法及其应用

《改进的k-means法及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中山大学硕士学位论文改进的K．means法及其应用ADevelopedK-meansMethodandItsApplications专业：流行病与卫生统计学研究生：鲁婧婧导师：骆福添教授答辩委员会主席：答辩委员会委员：专秘协2007年5月·广州摘要改进的K—means法及其应用专业：硕士研究生指导老师：流行病与卫生统计学鲁婧婧骆福添教授研究背景人们对客观事物的研究总是从无认识到有认识，步步深入，渐渐明朗化的。对事物进行分类则是人类认识世界的基本手段之一。在数据分类不明确时，对其进行探索性的分类是极为必要的

2、。聚类分析作为一种无监督的分类方法，在分类方法学中起到了举足轻重的作用。聚类分析包括很多种，其中K-means法作为快速聚类法(又称动态聚类法)中最常用的一种，由于在计算速度上具有无可比拟的优势，常被作为大样本聚类分析的首选方案。其基本原理为：人为地或按照某种标准选择初始凝聚点，依据样品点到各初始凝聚点的欧氏距离，将样品划分到与其距离最近的类别中，形成初始分类。再对初始分类进行修正，直到分类比较合理，刁i必再修正为iE。实践表明，由于该方法在聚类过程中采取距离就近原则，故更倾向于产生大小相等的球状类。而在

3、实际研究中常存在几个类在“空间”所占容=

4、

5、}{大小不等的情况。例如亚健康问题，健康的人大都相似，处于亚健康状态的人却因为症状各彳；相同而存在较大的变异度。在这种情况下，K．means法常常无法得到令人满意的结果。本研究通过模拟和实例分析来探讨对jJ：并类在“空n_

6、J”所占容积(对应于方差)大小不等的类，如何聚类。町以达到较好的效果。材料与方法本研究旨在提出⋯种改进的K—means法，在对方差不等的类进行聚类时，可以取得较好的效果。崽想来源：样品来自两个方差不等的类的可能性不但与该样品与类中心的距摘要离

7、有关，还与类内相似度有关。故在每次聚类过程中，对样品与类之间距离的量化，应考虑类内方差的大小。基本思想：不同的类相似度可能不同。故在计算样品与类的距离时，依据类内相似度的大小为其赋予升i同的权重。当类内相似度比较大时，为其赋予较大的权重。当类内相似度比较小时，为其赋予较小的权重。类内相似度可以通过类内方差的大小来度量。方差人，说明类内相似度比较小；方差小，则说明类内相似度比较大。故将权重定义为方差的倒数。算法描述：1、初始凝聚点的选择在选择初始凝聚点的过程中，如果仅仅基于距离因素，往往会找到许多孤立点作为

8、初始凝聚点。实际上，初始凝聚点除了尽量分散，能使各类被恰当地区分之外，还应该具有一定的代表性，即具有较高的密度。因此，在初始凝聚点的选择中，除了考虑其散布程度外，还应考虑密度因素。本文所提出的聚类方法，引入了每类的方差，若仍以孤立点为初始凝聚点，聚类的效率会受到很大影响。因此，本文所提出的方法，选择密度法作为初始凝聚点的选择方法。2、距离的定义由于考虑了各类方差的影响，故定义样品到各类的“相对距离”而非“绝对距离”作为聚类准则。所谓相对距离即样品点到类中心的欧氏距离平方与类内方差之比。考虑到极端点对方差的

9、影响，故此处对方差进行修正。修正方法为选择与类中心的欧氏距离平方最近的80％的样品点，计算方差。3、聚类效果的评价概括地说，对聚类效果的评价主要有三种方法。一种是基于外部的准则，该准则基于数据集上的。个预定义的结构来评价聚类算法的结果。另外一种是基⋯J二内部的准则，即利用数据集本身的特征来评价聚类结果。第三种是相对准则，即在同一个数据集上，用同一种聚类算法但参数取值不同的多次聚类结果的比较来进行算法的评价。基于以上各准则的评价指标很多，且各有优缺点。本研究采用的模拟数据和实际数据为已知分类的数据，故可采用

10、外部准则对其进行评价。聚类准确度定义为分类结果与预定义类别一致的个体数与参与聚类的全部个体数的比。该指标容易理解，是对聚类结果进行评价的一个常用外部评价指标。但是聚类结果中所给II摘要出的类标签，与金标准并无明确的对应关系，故该指标如何计算十分模糊。本研究利用SAS软件编写程序，寻找聚类结果与金标准之间的对应关系，并计算聚类准确率。从而使聚类结果更加直观。模拟实验：利用SAS产生两类服从双变量正态分布的数据。要求两类数据具有不同的方差比，对丁所选取的每个固定的方差比，设置不同的类间距。每类样本量为300，

11、每种情况抽样次数为100。实例分析：应用改进的K—means法对真实数据进行分析，并对聚类结果进行评价。算法实现：采用SAS软件编写改进的K．means法的实现程序以及产生模拟数据、产生初始凝聚点以及准确度度量的程序。结果与讨论模拟试验的结果显示：当两类方差比为9，6，4，3时，改进的K—means法的聚类效果优于传统的K—means方法。当两类方差比为2时，改进的K．means法未体现出优越性。比较两种方法的聚类准则，可以看