K-Means算法的研究与改进.PDF

第22卷　 第10期 计 算机 技 术 与发 展 Vol.22　 No.10 2012年10月 　 　 　 　 　 　 　 　 　 　 COMPUTERTECHNOLOGY AND DEVELOPMENT　 　 　 　 　 　 　 　 　 　 Oct.　 2012 K-Means算法的研究与改进 周爱武,陈宝楼,王　 琰 (安徽大学计算机科学与技术学院,安徽 合肥 230039) 摘　 要:K-Means算法是一种基于划分方法的经典聚类算法,已经在很多领域得到广泛的应用。 虽然该算法有很多优点, 但其也存在自身的局限性,比如需要用户输入聚类簇个数,初始聚类中心是随机性选择的,算法容易陷入局部最优解,对 孤立点比较敏感等。 文中首先应用统计学中的标准分数对样本进行孤立点分析,然后提出一种新的初始聚类中心确定策 略。 对改进的算法和原算法分别做实验进行比较,实验结果表明,改进的算法在准确率、收敛速度和稳定性方面都有很大 的提高。 关键词:K-Means算法;孤立点;初始聚类中心 中图分类号:TP301.6　 　 　 　 　 　 文献标识码:A　 　 　 　 　 　 文章编号:1673-629X(2012)10-0101-04 Research and Improvement of K-Means Algorithm ZHOU Ai-wu,CHEN Bao-lou,WANG Yan (College of Computer Science and Technology,Anhui University,Hefei230039,China) Abstract:K-Meansalgorithm isaclassicclusteringalgorithmbasedontheclassificationmethodhasbeenwidelyappliedinmanyfields. Although the algorithm hasmany advantages,therearealsotheir own limitations,such asuser input thenumber of clusters,initial cluster centersisrandom selection,thealgorithmiseasytofallintolocaloptimal solutionismoresensitivetooutlierandsoon.Itfirstlyanalyses sample outlierby statisticsstandardscores,andthenputsforwardanewstrategytodeterminetheinitialclusteringcenters.Improvedalgo- rithm and theoriginalalgorithmweredoingexperimentstocompare,theexperimentalresultsshowthattheimprovedalgorithmsaccuracy rate,convergence speed and stability are improved greatly. Key words:K-Means;outlier;initial clustering centers 0　 引　 言 迭代进行优化。 在初始聚类中心选择方面,主要有以 随着数据挖掘的应用不断发展,聚类分析已经广 下三种经典的改进算法。 文献[5]提出的一种简单聚 泛地应用到了很多领域,包括市场研究、数据分析、模 类探索方法,文献[6]给出的一种二元分裂方法,文献 式识别、图像处理、人工智能和 Web 文档分类等领 [7]给出的K值评估方法。 [1,2] 传统K-Me