基于云环境K-means聚类的并行算法

被引：12

作者：

高榕 ^{[1
]}

李晶 ^{[1
]}

肖雅夫 ^{[1
]}

祝孙静 ^{[1
]}

彭卫平 ^{[2
]}

机构：

[1] 武汉大学计算机学院

[2] 武汉大学动力与机械学院

来源：

武汉大学学报(理学版) | 2015年 / 61卷 / 04期

关键词：

海量数据; 聚类; K-means算法; Canopy算法; MapReduce;

D O I：

10.14188/j.1671-8836.2015.04.012

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

K-means聚类算法只能保证算法收敛到局部最优,从而导致聚类结果对初始点的选择非常依赖,同时在面对海量数据时容易因运算次数增多而使聚类过程耗时增加.针对上述问题及结合海量数据的特性,本文提出了一种基于云环境的并行聚类算法,该算法利用Canopy聚类算法思想并结合二分查找思想对K-means算法进行优化,同时采用"极限点"原则使之避免了聚类过程中的局部最优,然后利用顺序组合式MapReduce编程模型实现了算法的并行化扩展.实验结果表明:在大数据集上,该算法比同样部署在Hadoop集群上运行的K-means算法,在加速比、准确率、扩展率、算法效率方面具有较大的优势.

引用

页码：368 / 374

页数：7

共 11 条

[1] 基于云计算平台Hadoop的并行k-means聚类算法设计研究 [J].

赵卫中 ;

马慧芳 ;

傅燕翔 ;

史忠植 .

计算机科学, 2011, 38 (10) :166-168+176

[2]

云计算:系统实例与研究现状[J]. 陈康,郑纬民.软件学报. 2009(05)

[3] 基于改进K-means聚类和霍夫变换的稀疏源混合矩阵盲估计算法 [J].

付宁 ;

乔立岩 ;

彭喜元 .

电子学报, 2009, 37(S1) (S1) :92-96

[4] 聚类算法研究 [J].

孙吉贵 ;

刘杰 ;

赵连宇 .

软件学报, 2008, (01) :48-61

[5] 一种基于“基因表达谱”的并行聚类算法 [J].

郎显宇 ;

陆忠华 ;

迟学斌 .

计算机学报, 2007, (02) :311-316

[6] 基于遗传算法的图论聚类方法 [J].

张爱华 .

武汉大学学报(理学版), 2005, (S2) :19-21

[7] 基于免疫规划的K-means聚类算法 [J].

行小帅 ;

潘进 ;

焦李成 .

计算机学报, 2003, (05) :605-610

[8] 从多角度分析现有聚类算法(英文) [J].

钱卫宁 ;

周傲英 .

软件学报, 2002, (08) :1382-1394

[9]

The WEKA data mining software[J] . Mark Hall,Eibe Frank,Geoffrey Holmes,Bernhard Pfahringer,Peter Reutemann,Ian H. Witten.ACM SIGKDD Explorations Newsletter . 2009 (1)

[10] Time-focused clustering of trajectories of moving objects [J].

Nanni, Mirco ;

Pedreschi, Dino .

JOURNAL OF INTELLIGENT INFORMATION SYSTEMS, 2006, 27 (03) :267-289

← 1 2 →