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

基于云环境K-means聚类的并行算法 Parallel Algorithm Based on K-means Clustering in Cloud Environment 高榕 GAO Rong 1 first-author 李晶 LI Jing 1 肖雅夫 XIAO Yafu 1 祝孙静 ZHU Sunjing 1 彭卫平 PENG Weiping 2 武汉大学计算机学院 武汉大学计算机学院 School of Computer,Wuhan University School of Computer,Wuhan University 武汉大学动力与机械学院 武汉大学动力与机械学院 School of Power and Mechanical,Wuhan University School of Power and Mechanical,Wuhan University K-means聚类算法只能保证算法收敛到局部最优,从而导致聚类结果对初始点的选择非常依赖,同时在面对海量数据时容易因运算次数增多而使聚类过程耗时增加.针对上述问题及结合海量数据的特性,本文提出了一种基于云环境的并行聚类算法,该算法利用Canopy聚类算法思想并结合二分查找思想对K-means算法进行优化,同时采用"极限点"原则使之避免了聚类过程中的局部最优,然后利用顺序组合式MapReduce编程模型实现了算法的并行化扩展.实验结果表明:在大数据集上,该算法比同样部署在Hadoop集群上运行的K-means算法,在加速比、准确率、扩展率、算法效率方面具有较大的优势. K-means clustering algorithm can only guarantee convergence to local optimum,which results in great dependence on the initial point selection,as well as the additional time consumption in the clustering process due to the operation number increase in coping with the massive data.To solve the problems in K-means algorithm,and learning characteristics of data,aparallel clustering algorithm based on cloud computing platform is developed in this thesis.Considering the principle"Limit point",based on Canopy algorithm and dichotomy algorithm,the proposed algorithm globally optimizes efficient clustering the original massive data and avoids the local optimum in the process of clustering.Then it uses sequential combined MapReduce programming framework for parallel programming on the improved algorithm.Experiments on large size of dataset demonstrate that our proposed algorithm shows better performance on speed-up ratio,rate of expansion,and higher accuracy and efficiency than the parallel K-means algorithm on Hadoop does. 海量数据 聚类 K-means算法 Canopy算法 MapReduce massive data cluster K-means algorithm Canopy algorithm MapReduce 10.14188/j.1671-8836.2015.04.012 TP301.6 国家高技术研究发展计划（863）（2012AA040910）;国家自然科学基金（51275362）资助项目 2015-04-01 2021-03-31 4 61