基于MapReduce的单遍K-means聚类算法

摘要

The application of fitting K-means into MapReduce framework can greatly improve the processing of K-means on large data-sets. But K-means achieves an acceptable clustering effect through multiple iterations. Each iteration is executed as an independent map job,in which the whole dataset must be read and wrote to slow disks,resulting in high I/O overhead,and it is not consistent with the de-sign concept of the MapReduce framework. Therefore,a single-pass K-means clustering algorithm based on MapReduce,called MRSK, is proposed. It reads the data by single-pass and uses the K-means++ seeding algorithm to get the initial cluster center. On the basis of theoretically analyzing the complexity of the MRSK,a series of test and analysis for MRSK is conducted. The experimental results show that compared with the available MapReduce-based and stream-based K-means variants,MRSK performs both faster execution times and higher quality of clustering results.%K-means应用于MapReduce框架的大数据处理可显著提高K-means对大数据集的处理能力.但K-means聚类算法需要进行多次迭代才能达到可接受的效果,并将每次迭代作为一个独立map作业执行,需要读写整个数据集,从而导致显著的I/O消耗,与MapReduce框架的设计理念不符.为此,提出了一个基于MapReduce的单遍K-means算法(MR-SK).该算法采用流数据单遍算法读取数据,聚类时采用K-means++初始化seeding算法得到初始聚类中心.在理论分析MRSK算法复杂度的基础上,进行了MRSK算法的测试验证和相关分析.验证实验结果表明,相对于基于MapReduce和基于数据流的K-means聚类算法,所提出的MRSK算法在执行速度和聚类效果方面具有更好的优势.