«上一篇/Previous Article|本期目录/Table of Contents|下一篇/Next Article»

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:

27

期数:

2017年09期

页码:

26-30

栏目:

智能、算法、系统工程

出版日期:

2017-09-10

文章信息/Info

Title:

 A Single-pass K-means Clustering Algorithm with MapReduce

文章编号:

1673-629X（2017)09-0026-05

作者:

 唐浩[1]; 杨余旺[1]; 辛智斌[2]

1. 南京理工大学 计算机科学与工程学院；2.淮海集团工业有限公司

Author(s):

 TANG Hao[1]; YANG Yu-wang[1]; XIN Zhi-bin[2]

关键词:

 ; MapReduce框架; 数据聚类; K-means++ ; Mahout ; 单遍技术

Keywords:

 ; MapReduce framework; data clustering; K-means++; Mahout ; single-pass

分类号:

TP301.6

文献标志码:

A

摘要:

 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算法在执行速度和聚类效果方面具有更好的优势.

Abstract:

 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.

常用功能

更新日期/Last Update: 2017-10-19