k_means算法研究综述_吴夙慧

《k_means算法研究综述_吴夙慧》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、知识组织与知识管理知识组织与知识管理*K－means算法研究综述1122吴夙慧成颖郑彦宁潘云涛1(南京大学信息管理系南京210093)2(中国科学技术信息研究所北京100038)【摘要】对聚类分析中的基本算法K－means算法中的K值确定、初始聚类中心选择以及分类属性数据处理等主要问题进行综述，理清K－means算法的整个发展脉络及算法研究中的热点和难点，提出改进K－means聚类算法的思路。【关键词】K－means算法聚类算法K值初始聚类中心【分类号】G202SurveyonK－meansAlgorithm1122WuSuhuiChengYin

2、gZhengYanningPanYuntao1(DepartmentofInformationManagement，NanjingUniversity，Nanjing210093，China)2(InstituteofScientific＆TechnicalInformationofChina，Beijing100038，China)【Abstract】ThemainproblemsofK－meansalgorithmwhichisabasicalgorithminclusteringareoutlinedinthispaper，suchasde

3、terminationoftheoptimalclusters，selectionofinitialcenters，andcategoricaldataclustering，etc．Thedevelopment，thehotspotsanddifficultiesofthisalgorithmareclarified，andsomeideasareintroducedtoimprovethealgorithmefficiency．【Keywords】K－meansalgorithmClusteringalgorithmNumberofcluste

4、rsInitialclusteringcenters1引言聚类分析是数据挖掘中的一种重要的分析方法，它的目标是将数据集合分成若干簇，使得同一簇内的数据点相似度尽可能大，而不同簇间的数据点相似度尽可能小。［1］聚类算法的研究有着相当长的历史，早在1975年Hartigan就在其专著《ClusteringAlgorithms》中对聚类算法进行了系统的论述。之后，学界陆续提出了多种基于不同思想的聚类算法，主要有基于划分的算法、基于层次的算法、基于密度的算法、基于网格的算法和基于模型的算法等。这些算法都能取得不错的聚类效果，其中应用最多且算法思想较为简单

5、的是基于划分的K－means算法。本文将对K－means算法在文本聚类研究中的基本问题进行全面的综述，并提出一些改进聚类质量的设想。2K－means算法基础［2］［3］［4］［5］1967年，MacQueen提出了K－means算法，他总结了Cox、Fisher、Sebestyen等的研究成果，给出了K－means收稿日期:2011－03－14收修改稿日期:2011－04－12*本文系国家社会科学基金项目“中文学术信息检索系统相关性集成研究”(项目编号:10CTQ027)、教育部人文社会科学研究规划基金项目“面向用户的相关性标准及其应用研究”(项

6、目编号:07JA870006)和中国科学技术信息研究所合作研究项目的研究成果之一。28现代图书情报技术总第205期2011年第5期算法的详细步骤，并用数学方法进行了证明。MacQueen内相似度尽可能大，而聚簇间相似度尽可能小的基本的算法思想为:给定n个数据点{x1，x2，…，xn}，找到K个原则，聚类收敛函数应该综合考虑类内距离和类间距聚类中心{a1，a2，…，aK}，使得每个数据点与它最近的聚离。为此，学界提出了很多改进的聚类收敛函数，以期类中心的距离平方和最小，并将这个距离平方和称为目标更加全面地反映聚类的质量。其中大多数的改进都是函数，记

7、为Wn，其数学表达式为:采用类内紧密性(Within－clusterScatter)与类间分散nW=∑min

8、x－a

9、2(1)性(Between－clusterSeparation)的比值来作为收敛函n1≤j≤Kiji=1数，这样当收敛函数收敛到极小值时，类内紧密性和类由于K－means算法易于描述，具有时间效率高且间分散性都可以达到较优值。著名的Davies－Bouldin适于处理大规模数据等优点，自20世纪70年代以来，［14］［15］指数(DBI)和Dunn指数(DI)都是采用这种思该算法在国内外已经被应用到包括自然语言处理、土［6－8］想

10、，Davies－Bouldin指数是计算类内距离之和与类间壤、考古等众多领域。在文本聚类领域，K－means距离之和的比值，而Dunn指