计算机工程与应用 ›› 2016, Vol. 52 ›› Issue (8): 74-79.

• 大数据与云计算 • 上一篇    下一篇

基于MapReduce的随机抽样K-means算法

王永贵,武  超,戴  伟   

  1. 辽宁工程技术大学,辽宁 葫芦岛 125105
  • 出版日期:2016-04-15 发布日期:2016-04-19

K-means algorithm of random sample based on MapReduce

WANG Yonggui, WU Chao, DAI Wei   

  1. Liaoning Technical University, Huludao, Liaoning 125105, China
  • Online:2016-04-15 Published:2016-04-19

摘要: K-means算法处理海量数据时,易产生系统内存溢出的现象。利用MapReduce框架改进K-means虽然解决了这个问题,但也存在着聚类效果不稳定以及准确率不高等问题,提出一种改进算法,利用MapReduce框架实现K-means时,采用多次随机抽样,通过计算密度、距离与平方误差等方法,最终选取较优的初始聚类中心,并在迭代中采用新的中心点计算方法。实验结果证明,改进后的算法具有较好的稳定性、准确性和加速比。

关键词: K-means, 随机抽样, 海量数据, MapReduce

Abstract: The K-means algorithm when dealing with massive data, is easy to bring the phenomenon of memory overflow. Although this problem is solved by using the MapReduce framework to improve K-means, the phenomenon clustering effect is not so stable and the accuracy is not so high. It is necessary to raise an improved algorithm, which uses MapReduce framework to implement the K-means, by means of random sampling, calculating density, distance and the square difference. Finally, it selects the best initial cluster center and adopts the new method of center point calculation in the iteration. Experimental results show that, the improved algorithm has good stability, accuracy and accelerating ratio.

Key words: K-means, random sampling, massive data, MapReduce