一种基于K-Means局部最优性的高效聚类算法

被引：114

作者：

雷小锋 ^{[1
]}

谢昆青 ^{[1
]}

林帆 ^{[1
]}

夏征义 ^{[2
]}

机构：

[1] 北京大学信息科学技术学院智能科学系/视觉与听觉国家重点实验室

[2] 中国人民解放军总后勤部后勤科学研究所

来源：

软件学报 | 2008年 / 07期

关键词：

K-MeanSCAN; 基于密度; K-Means; 聚类; 连通性;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

K-Means聚类算法只能保证收敛到局部最优,从而导致聚类结果对初始代表点的选择非常敏感.许多研究工作都着力于降低这种敏感性.然而,K-Means的局部最优和结果敏感性却构成了K-MeanSCAN聚类算法的基础.K-MeanSCAN算法对数据集进行多次采样和K-Means预聚类以产生多组不同的聚类结果,来自不同聚类结果的子簇之间必然会存在交集.算法的核心思想是,利用这些交集构造出关于子簇的加权连通图,并根据连通性合并子簇.理论和实验证明,K-MeanScan算法可以在很大程度上提高聚类结果的质量和算法的效率.

引用

页码：1683 / 1692

页数：10

共 8 条

[1] CHAMELEON: A hierarchical clustering algorithm using dynamic modeling. Karypis G,Han E H,Kumar V. Computer . 1999
[2] The SEQUOIA 2000 storage benchmark. Stonebraker M,Frew J,Gardels K,Meredith J. Proc.of the ACM SIGMOD Int‘l Conf.on Management of Data . 1993
[3] Data Mining:Concepts and Techniques. Han JW,Kamber M. . 2001
[4] A density-based algorithm for discovering clusters in large spatial database with noise. Ester M,Kriegel HP,Sander J,Xu XW. Proc.of the 2nd Int‘l Conf.on Knowledge Discovery and Data Mining . 1996
[5] BIRCH:An efficient data clustering method for very large databases. Zhang T,Ramakrishnan R,Linvy M. Proc.of the ACM SIGMOD Int‘l Conf.on Management of Data . 1996
[6] CURE:An efficieny clustering algorithm for large databases. Guha S,RastogiR,Shim K. Proc.of the ACM SIOMOD Int‘l Conf.on Management of Data . 1998
[7] OPTICS:Ordering points to identify the clustering structure. Ankerst M,Breuning M,Kriegel HP,Sander J. Proc.of the ACM SIGMOD Int‘l Conf.on Management of Data . 1999
[8] Choosing k for two-class nearest neighbour classifiers with unbalanced classes. Hand DJ,Vinciotti V. Pattern Recognition . 2003

← 1 →