唐 浩,楊余旺,辛智斌
(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;單遍技術
K-means[1]聚類算法是數據挖掘領域中的一種重要方法,由于計算簡單、收斂速度快,在機器學習、圖像處理等領域應用廣泛。近年來,隨著數據量的不斷攀升,傳統的K-means聚類分析方法已無法滿足大數據[2]的需求,所以亟需對傳統的K-means方法做出改進以支持大規模數據分析。
MapReduce[3]是由谷歌提出的一種大數據并行計算框架。MapReduce的3個主要特點:模型使用方便、適用于大型數據處理、可擴展并內置容錯,使其成為一種理想的大數據處理框架[4]。如今,K-means已經成功地應用在了MapReduce框架中。……