云環境下K-means算法的并行化

何佩佩，謝穎華（1.數字化紡織服裝技術教育部工程研究中心，上海 201620；2.東華大學 信息科學與技術學院，上海 201620）

云環境下K-means算法的并行化

何佩佩1，2，謝穎華1，2
（1.數字化紡織服裝技術教育部工程研究中心，上海 201620；2.東華大學 信息科學與技術學院，上海 201620）

隨著大數據時代的到來，傳統的聚類算法很難高效地處理海量數據，而云計算平臺憑借負載均衡、網絡存儲、虛擬化等技術，有效地突破了耗時耗能的瓶頸，為海量數據的處理提供了良好的解決方案。主要研究了Hadoop平臺下的MapReduce編程模型及傳統K-means算法，提出了一種基于MapReduce的并行化K-means算法的設計方案，包括Map函數和Reduce函數的設計。通過實驗，驗證了并行化K-means算法適用于較大規模數據集的分析和挖掘。

云計算；數據挖掘；MapReduce編程模型；K-means聚類算法；并行化

0 引言

隨著信息化社會的發展，各個行業中產生的數據都在以爆炸式的速度增長。典型的聚類算法——K-means算法是基于劃分的聚類算法，因其快速、簡單的特性而被廣泛應用。但在面對海量數據時，傳統的K-means算法無論是在時間復雜度還是空間復雜度上都遇到了瓶頸［1］，而云計算技術的出現為海量數據的處理提供了良好的解決方案。

云計算是一種基于互聯網的計算方式。Hadoop則是云計算技術的開源實現，具有高容錯、跨平臺等優勢。它主要包含兩個部分：分布式文件系統（HDFS）和MapReduce編程模型。本文在基于 Hadoop云計算平臺，利用MapReduce編程模型實現了傳統K-means聚類算法的并行化設計，并進行了相關實驗的驗證。

1 Ma p Re d u c e編程模型

MapReduce編程模型，顧名思義，由Map（映射）階段和Reduce（規約）階段組成，分別用兩個函數表示，即Map函數和Reduce函數［2］。MapReduce作業流程如圖1所示。

圖1 MapReduce作業流程圖

Map階段：Map任務運行在集群的從節點上，多個Map任務相互間是獨立運行的。原始數據在進入 Map函數前，會將原始大數據集劃分并格式化為＜key1，value1＞鍵值對的形式。經過Map函數的運算處理后產生一個或多個中間鍵值對＜key2，value2＞。

Shuffle階段：它由Partition（數據分割）和 Combine（數據合并）組成。Combine就是將Map任務輸出的中間結果中有相同 key2的＜key2，value2＞對合并成一對。Partition則是采用默認 hash函數將中間結果按照 key2值的范圍分成R份，發送并保證某一范圍內的key2由同一個Reduce任務來處理。

Reduce階段：每個 Reduce任務需要從多個 Map任務節點取得其負責的key2區間內的中間結果。Reduce函數接收到形如＜key2，（list of value2）＞形式的輸入，進行處理后產生鍵值對＜key3，value3＞作為結果，并將結果輸出到HDFS上。

為了方便理解，上述過程中數據格式的變化如圖2所示。

圖2 MapReduce程序數據變化的基本模型

2基于MapReduce的并行K-means算法的設計

2.1 K-means聚類算法的基本思路

K-means算法是聚類算法中使用最廣泛的基于劃分的算法，其基本思想是：將空間中的n個對象集合以K個點為中心進行簇的劃分，歸類到與其距離最近的中點［3］。通過迭代的方式，逐次更新聚類中心的值并重新劃分簇，直至目標函數收斂。K-means算法采用距離作為相似性的評價指標，其目標函數可表示為：

其中，xi表示數據集 X=｛x1，x2，…，xN｝中第 i個樣本，N為樣本總數；Cj表示第 j個簇，K為簇的總個數，zj則表示第j個簇的中心。

假設共有n個數據對象，計劃劃分為K個簇，t為迭代次數，O為一次迭代中計算某一對象到各個類的中心距離的時間復雜度，那么串行實現K-means算法的時間復雜度為n×K×t×O［4］。由此可見，當面對大數據時，算法的時間復雜度將成倍地增加。

2.2 K-means聚類算法的MapReduce化的設計

K-means算法中，計算數據對象與聚類中心距離是該算法中反復進行的操作，并且每個數據對象到聚類中心距離的計算過程都是相互獨立的。圖3描述了基于MapReduce的并行K-means算法的設計方法，其中數據的分片由MapReduce環境自行完成，只需要編寫Map函數和Reduce函數的實現代碼即可。

2.2.1 Map函數的設計

首先，Map函數逐行掃描數據段，按行作為數據對象，記錄為＜行號，數據內容＞鍵值對；接著，與保存在全局變量中聚類中心進行運算，得出數據對象與各個聚類中心的距離；最后，將數據對象分配給距離最近的類中，產生＜聚類ID，數據內容＞鍵值對作為函數輸出。Map函數的偽代碼如下：

圖3 基于MapReduce的并行K-means算法

2.2.2 Reduce函數的設計

首先，將擁有相同聚類ID的數據對象分配給同一個Reduce任務；接著，Reduce函數將記錄所接收到的樣本個數并將數據對象各個維坐標分別累加；最后，將各維坐標之和除以樣本個數得到各個維坐標的均值，計算結果就是該類新的聚類中心。Reduce函數的偽代碼如下：

將本輪 reduce函數輸出的聚類中心與上一輪的聚類中心比較，若目標函數收斂，則算法結束；否則，本輪的聚類中心將寫入中心文件，作為新的聚類中心。

3 實驗與分析

實驗目的是比較在相同的硬件配置下，Hadoop集群中1個運算節點和普通計算機分別使用并行 K-means算法和傳統串行K-means處理相同規模數據的能力。考慮到K-means算法對初始聚類中心有較強的依賴性，在相同數據集的條件下重復進行實驗10次，取平均值作為最終的實驗數據，實驗結果如表1所示。

表1中，t1表示使用傳統串行 K-means算法處理數據集所花的時間；t2表示使用并行化 K-means算法處理數據集所花的時間。通過實驗數據可以發現，當數據集的規模較小時，串行K-means算法的執行效率優于并行化K-means算法的執行效率，這是由于數據量小時，其計算任務所消耗的資源較少，但是在 Hadoop平臺上啟動、分配任務以及進行作業間的交互卻需要耗費固定的資源。但隨著數據集規模的增大，計算任務所占用的資源的比例將不斷增大，使并行化算法的優勢得以體現，其運行時間的增長速度遠小于串行算法。另外，由于串行算法所消耗的資源快速地增長，系統將會報告內存不足。

表1 實驗結果

4 結論

本文對 Hadoop的 MapReduce編程模型以及聚類算法K-means進行了研究，給出了基于MapReduce的并行化K-means算法的設計方案并進行了實驗驗證。實驗結果表明，基于MapReduce的并行化K-means算法適用于處理較大規模的數據挖掘任務，并且具有較好的計算效率。

［1］謝雪蓮，李蘭友.基于云計算的并行 K-means聚類算法研究［J］.計算機測量與控制，2014，22（5）：1510-1512.

［2］冀素琴，石洪波.基于MapReduce的K-means聚類集成［J］.計算機工程，2013，39（9）：84-87.

［3］周婷，張君瑛，羅成.基于 Hadoop的 K-means聚類算法的實現［J］.計算機技術與發展，2013，23（7）：18-21.

［4］趙衛中，馬慧芳，傅燕翔，等.基于云計算平臺 Hadoop的并行 K-means聚類算法設計研究［J］.計算機科學與探索，2011，38（10）：166-168，176.

圖7 課程顯示界面

界面代碼執行流程如下：

（1）用戶點擊主界面課程表模塊，軟件跳轉至課程顯示界面，軟件通過查詢校歷獲取當前周次以及星期，默認顯示當天的課表；

（2）用戶點擊某節課程信息，跳轉至該節次課程詳情界面；

（3）用戶點擊右上角周次選擇按鈕，彈出周次選擇面板，用戶可以選擇周次，查詢所選周次課表情況。

4.3 自習室模塊

自習室模塊提供用戶自習室查詢功能，用戶可以通過選擇日期、教學區域查詢自習室信息。自習室查詢界面如圖8所示。

圖8 自習室查詢界面

5 結論

在整個軟件開發中注重軟件的可用性、易用性以及可持續性，努力提升用戶的操作體驗。由于需求的不斷更新和技術的不斷發展，軟件還需要進一步完善，需要在以后的使用反饋中不斷進行優化升級。

參考文獻

［1］李曉.基于Android平臺的手持終端應用功能開發與設計［D］.武漢：湖北大學，2010.

［2］陳昱，江蘭帆.基于 Google Android平臺的移動開發研究［J］.福建電腦，2008（11）：156-157.

［3］姜波.嵌入式數據庫SQLite調試器的研究與實現［D］.昆明：昆明理工大學，2012.

［4］岑冬梅.基于 SQLite的空間數據庫存儲技術的研究與實現［D］.武漢：武漢科技大學，2009.

［5］初雅莉，陳昌穩，崔召金.基于 Android的智慧校園手機系統［J］.微型機與應用，2013，32（15）：15-17.

［6］張立.一種基于 Android系統網絡模塊功耗的評估和分析［J］.計算機科學，2012，39（6）：289-292.

（收稿日期：2015-07-30）

作者簡介：

盧照（1983-），男，碩士，主要研究方向：并行處理，智能算法。

K-means algorithm parallelization in Cloud environment

He Peipei1，2，Xie Yinghua1，2
（1.Engineering Research Center of Digitized Textile＆amp；Apparel Technology，Ministry of Education，Shanghai 201620，China；2.Information Science and Technology College，Donghua University，Shanghai 201620，China）

The era of big data is coming and the current clustering algorithms are ineffecicient.The Cloud computing platform breaks the state of consuming energy through load balance，network storage and virtualization technology.The paper analyzed the MapReduce programming model in Hadoop Cloud computing platform and the traditional K-means algorithm.The parallel K-means algorithm based on MapReduce was designed including Map function and Reduce function.The result of experiments shows that it fits to data mining on massive datasets.

Cloud computing；data mining；MapReduce；K-means algorithm；parallel algorithm

TP311

A

1674-7720（2015）24-0025-03

何佩佩，謝穎華.云環境下K-means算法的并行化［J］.微型機與應用，2015，34（24）：25-27，31.

2015-07-23）

何佩佩（1991-），通信作者，女，碩士研究生，主要研究方向：數據分析、數據挖掘。E-mail：hpp1991_06@126.com。

謝穎華（1972-），女，博士，副教授，主要研究方向：通信與信息系統、智能信息處理、無線網絡。