计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (16): 47-54.

• 理论研究、研发设计 • 上一篇    下一篇

一种基于Hadoop的高效[K]-Medoids并行算法

王永贵,戴  伟,武  超   

  1. 辽宁工程技术大学 软件工程学院,辽宁 葫芦岛 125105
  • 出版日期:2015-08-15 发布日期:2015-08-14

Highly efficient parallel algorithm of [K]-Medoids based on Hadoop platform

WANG Yonggui, DAI Wei, WU Chao   

  1. College of Software, Liaoning Technical University, Huludao, Liaoning 125105, China
  • Online:2015-08-15 Published:2015-08-14

摘要: 针对传统[K]-Medoids算法对初始聚类中心敏感、收敛速度慢,以及在大数据环境下所面临的内存容量和CPU处理速度的瓶颈问题,从改进初始中心选择方案和中心替换策略入手,利用Hadoop分布式计算平台结合基于Top [K]的并行随机采样策略,实现了一种高效稳定的[K]-Medoids并行算法,并且通过调整Hadoop平台,实现算法的进一步优化。实验证明,改进的K-Medoids算法不仅有良好的加速比,其收敛性和聚类精度均得到了改善。

关键词: [K]-Medoids, 分布式计算, Hadoop, 并行采样

Abstract:  In view of the traditional [K]-Medoids algorithm is sensitive to the initial clustering center, slow convergence speed, and in large data environment facing the bottleneck problem of memory and CPU processing speed, through improving the initial center options and replacement strategy of using the Hadoop distributed computing platform combined with parallel random sampling strategy based on Top [K], realizes a highly efficient and stable [K]-Medoids parallel algorithm, and by adjusting the Hadoop platform, realize the further optimization of the algorithm. Experiments show that the improved [K]-Medoids algorithm not only has a good speedup, the convergence and the clustering accuracy are also improved.

Key words: [K]-Medoids, distributed computation, Hadoop, parallel sampling