基于MapReduce的單遍K-means聚類算法

唐 浩，楊余旺，辛智斌

(1.南京理工大學 計算機科學與工程學院，江蘇 南京 210094；2.淮海集團工業有限公司，山西 長治 046000)

基于MapReduce的單遍K-means聚類算法

唐 浩1，楊余旺1，辛智斌2

(1.南京理工大學 計算機科學與工程學院，江蘇 南京 210094；2.淮海集團工業有限公司，山西 長治 046000)

K-means應用于MapReduce框架的大數據處理可顯著提高K-means對大數據集的處理能力。但K-means聚類算法需要進行多次迭代才能達到可接受的效果，并將每次迭代作為一個獨立map作業執行，需要讀寫整個數據集，從而導致顯著的I/O消耗，與MapReduce框架的設計理念不符。為此，提出了一個基于MapReduce的單遍K-means算法(MRSK)。該算法采用流數據單遍算法讀取數據，聚類時采用K-means++初始化seeding算法得到初始聚類中心。在理論分析MRSK算法復雜度的基礎上，進行了MRSK算法的測試驗證和相關分析。驗證實驗結果表明，相對于基于MapReduce和基于數據流的K-means聚類算法，所提出的MRSK算法在執行速度和聚類效果方面具有更好的優勢。

MapReduce框架；數據聚類；K-means++；Mahout；單遍技術

0 引 言

K-means[1]聚類算法是數據挖掘領域中的一種重要方法，由于計算簡單、收斂速度快，在機器學習、圖像處理等領域應用廣泛。近年來，隨著數據量的不斷攀升，傳統的K-means聚類分析方法已無法滿足大數據[2]的需求，所以亟需對傳統的K-means方法做出改進以支持大規模數據分析。

MapReduce[3]是由谷歌提出的一種大數據并行計算框架。MapReduce的3個主要特點：模型使用方便、適用于大型數據處理、可擴展并內置容錯，使其成為一種理想的大數據處理框架[4]。如今，K-means已經成功地應用在了MapReduce框架中。……