期刊首页 优先出版 当期阅读 过刊浏览 作者中心 关于期刊 English

《中国工程科学》 >> 2007年 第9卷 第11期

基于层次的K-means初始化算法

南京理工大学计算机系,南京210094

资助项目 :湖南省教育厅优秀青年基金资助项目(07B022);湖南省教育厅基金资助项目(03C495) 收稿日期: 2006-07-14 修回日期: 2006-09-13

下一篇 上一篇

摘要

K-means算法是一种常用的聚类算法,但是聚类中心的初始化是其中的一个难点。笔者提出了一个基于层次思想的初始化方法。一般聚类问题均可看作加权聚类,通过层层抽样减少数据量,然后采用自顶向下的方式,从抽样结束层到原始数据层,每层都进行聚类,其中每层初始聚类中心均通过对上层聚类中心进行换算得到,重复该过程直到原始数据层,可得原始数据层的初始聚类中心。模拟数据和真实数据的实验结果均显示基于层次抽样初始化的K-means算法不仅收敛速度快、聚类质量高,而且对噪声不敏感,其性能明显优于现有的相关算法。

参考文献

[ 1 ] Keim D A, Hinneburg A.Clustering techniques for large data sets—from the past to the future [ A] .In: Proc Tutorial Notes 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining [ C] .San Diego, 1999.141 ~181 链接1

[ 2 ] Duda R O, Hart P E.Pattern Classification and Scene Analysis [ M] .New York: John Wiley and Sons, 1973

[ 3 ] Pena J M, Lozano J A, Larranaga P.An empirical comparison of four initialization methods for the K -means algorithm [ J ] . Pattern Recognition Letters, 1999 , 20 ( 10 ) : 27 ~40 链接1

[ 4 ] Kaufman L, Rousseeuw P J. Finding Groups in Data: An Introduction to Cluster Analysis [ M] .Wiley, Canada, 1990

[ 5 ] Forgy E. Cluster analysis of multivariate data: efficiency vs interpretability of classifications [ J] .Biometrics 1965 , 21 : 768 链接1

[ 6 ] MacQueen J B.Some methods for classification and analysis of multivariate observations [ A ] . In: Proc Symposium on Mathematics and Probability, 5th, Berkely, Vol 1 , AD 669871 [ M] .University of California Press, Berkeley, CA, 1967.281 ~297 链接1

[ 7 ] Fayyad U M, Renia C A, Bradley P S.Initialization of iterative refinement clustering algorithm [ A ] . In: Proceedings of the International Conference on Knowledge Discovery and Data Mining ( KDD'98 ) [ C] .New York, 1998.94 ~98 链接1

[ 8 ] Bradley P S, Fayyad U.Refining INITIAL Points for K -means clustering [ A] .In: Proc 5 th Int Conf Machine Learning [ C] . Morgan Kaumann, 1998 链接1

[ 9 ] Khan S S, Ahmad A.Cluster center initialization algorithm for K -means clustering [ J] .Pattern Recognition Letters, 2004 , 25 ( 11 ) : 1293 ~1302 链接1

[10] Du Q, Faber V, Gunzburger M.Centroidal voronoi tessellations, theory, applications and algorithms [ J ] .SIAM Review, 1999 , 41 ( 4 ) : 637 ~676 链接1

相关研究