一種基于MapReduce 的并行聚類模型

顧瑞春，王靜宇

(1.內(nèi)蒙古科技大學(xué)內(nèi)蒙古白云鄂博礦多金屬資源綜合利用重點實驗室，內(nèi)蒙古 包頭 014010；2.內(nèi)蒙古科技大學(xué)信息辦與網(wǎng)絡(luò)中心，內(nèi)蒙古 包頭 014010)

0 引言

數(shù)據(jù)挖掘是從海量數(shù)據(jù)中獲取有效的、新穎的、潛在有用的、最終可理解的模式的非平凡過程。隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展和各種應(yīng)用爆炸式增長，隨之產(chǎn)生的數(shù)據(jù)量也急速膨脹，使用傳統(tǒng)的單機存儲和串行數(shù)據(jù)挖掘算法已經(jīng)無法在有效時間內(nèi)發(fā)現(xiàn)重要信息，而云計算具有海量的存儲能力和彈性化的計算能力，因此在數(shù)據(jù)挖掘領(lǐng)域逐漸發(fā)揮出其顯著優(yōu)勢。Hadoop 平臺是Apache 推出的開源云計算平臺，是Google 云計算平臺的開源實現(xiàn)。

1 MapReduce 簡介

MapReduce 是Google 公司提出的一項極富盛名的并行軟件框架，是基于分布式文件系統(tǒng)之上的并行編程模型，是目前各種云計算平臺的基礎(chǔ)模型。該模型的核心操作是2 個函數(shù)Map 和Reduce。這2 個函數(shù)均可高度并行運行，Map 函數(shù)用來處理多份數(shù)據(jù)，并把一組鍵值(Key/Value)對映射成一組新的鍵值(Key/Value)對，Map 函數(shù)的輸出作為Reduce 的輸入，由并發(fā)的Reduce 函數(shù)來保證所有映射鍵值(Key/Value)對中的每一組都具有相同的Key 鍵值［1-3］。

圖1 MapReduce 工作模式

圖1 是MapReduce 的工作模式。將大數(shù)據(jù)集分解成為成百上千的小數(shù)據(jù)集splits，每個(或若干個)數(shù)據(jù)集分別由集群中的一個節(jié)點執(zhí)行Map 計算任務(wù)并生成中間結(jié)果，然后這些中間結(jié)果又由大量的并行執(zhí)行的Reduce 計算任務(wù)進行處理，形成最終結(jié)果后輸出給用戶［4-7］。

MapReduce 模型主要是針對海量數(shù)據(jù)的高效并行處理，相對傳統(tǒng)的并行分布式計算模型而言，該模型由底層封裝任務(wù)分配、并行處理以及容錯等細節(jié)問題，開發(fā)者僅需關(guān)注自身要解決的分布式計算任務(wù)的表述即可，極大地簡化了分布式程序設(shè)計［8-9］。本文的MapReduce 模型采用CADD 算法作為原型算法進行并行聚類分析，用以對海量數(shù)據(jù)進行處理。

2 CADD 算法介紹

基于密度和自適應(yīng)密度可達算法(Clustering Alogrithm base on Density and Adaptive Dentsity-reachable，CADD)在聚類過程中，首先利用高斯密度函數(shù)f(xi)=計算數(shù)據(jù)集D 中每個數(shù)據(jù)點xi(i=1，2，…，n)的密度值，其中σ 為密度參數(shù)，決定密度函數(shù)的變化梯度［10-11］。然后，尋找局部密度最大吸引點QdensityMax，將其作為第一個簇中心，根據(jù)初始密度可達半徑R0，得到第一個密度可達簇C1，如圖2所示;然后在C1 簇之外的數(shù)據(jù)點中搜索次級局部密度最大點，將其作為第二個促中心，根據(jù)自適應(yīng)密度可達半徑Radaptive 得到第二個密度可達簇C2，以此類推，直到將所有滿足條件的數(shù)據(jù)點都聚集到相應(yīng)的簇中，如C3;最后把不屬于任何簇的數(shù)據(jù)點標記為孤立點O0。

為了能夠提升聚類效率，充分利用閑置資源，采用孟海東［10］等提出使用MPI 方式將CADD 算法并行化，得到了較好結(jié)果。本文采用更為高效的Hadoop平臺下的MapReduce 框架來進行CADD 聚類的并行化處理。

圖2 CADD 算法聚類簇

3 MapReduce 聚類模型

基于MapReduce 的并行聚類模型難點在于規(guī)劃不同輸入與輸出的鍵值(Key/Value)對，海量數(shù)據(jù)的聚類挖掘則需要考慮采用多個Mapreduce 過程來處理，上一個Mapreduce 過程的輸出作為下一個Mapreduce 過程的輸入。該模型采用3 個MapReduce 步驟來實現(xiàn)［12-14］。

步驟1 數(shù)據(jù)準備。

根據(jù)計算節(jié)點的數(shù)量對海量原始數(shù)據(jù)集D 進行劃分，形成p 個子數(shù)據(jù)集D1，D2，…，Dp(p 為節(jié)點個數(shù)或進程數(shù))，然后使用MapReduce 模式對其進行并行處理。

(1)Map 處理:確定各個子數(shù)據(jù)集的Key/Value鍵值對。

(2)Reduce 處理:將Map 處理后輸出的Key/Value 對按照Key 進行排序，將Key 鍵相同的數(shù)據(jù)統(tǒng)一由一個Reduce 進行處理，保存輸出結(jié)果，作為下一個步驟的輸入數(shù)據(jù)。

步驟2 并行聚類。

對第一步處理輸出的結(jié)果分別進行CADD 聚類，形成多個局部聚類結(jié)果，再次進行MapReduce 處理。

(1)Map 處理:每個Mapper 以CADD 聚類后的局部聚類結(jié)果作為輸入，并以簇中心作為Key 值，存儲中間數(shù)據(jù)。

(2)Reduce 處理:對CADD 聚類處理后的數(shù)據(jù)進行Reduce 處理，輸出數(shù)據(jù)中，對所有相同簇中心的各個簇進行合并，形成新的聚類簇。輸出并存儲結(jié)果，作為下一次處理的輸入數(shù)據(jù)。

步驟3 合并結(jié)果。

將步驟2 處理輸出結(jié)果作為輸入，進行MapReduce 處理，該步驟使用多個Mapper 函數(shù)，該步驟的Reduce 階段僅使用一個Reducer 處理函數(shù)，根據(jù)不同特征值合并后的數(shù)據(jù)數(shù)量，將所有聚類結(jié)果根據(jù)聚類特征鍵值進行合并，形成最終處理結(jié)果。

(1)Map 處理:每個Mapper 以第二步輸出的中間結(jié)果作為輸入，以新的聚類簇中心點作為Key 值，存儲中間數(shù)據(jù);

(2)Reduce 處理:最后一步的Reduce 過程中，使用一種改進的BIRCH［15］算法聚類特征，將Mapper 傳來的具有聚類簇進行特征值提取，并對具有相同特征值的聚類簇進行合并，僅適用一個Reducer 函數(shù)，對合并后的數(shù)據(jù)，形成最終聚類結(jié)果。

整個流程如圖3 所示。

圖3 MapReduce 處理過程

4 實驗結(jié)果與分析

使用Hadoop 平臺對該聚類模型進行測試，Hadoop 是Google 云計算平臺的Java 開源實現(xiàn)，其核心主要包括HDFS、MapReduce 和HBase。

實驗使用5 臺計算機，裝有Ubuntu Linux 10.10，Hadoop 版本選用1.0.3。其中，1 臺機器作為Master和JobTracker 服務(wù)節(jié)點，其他4 臺機器作為Slave 和TaskTracker 服務(wù)節(jié)點，5 臺計算機使用1 臺普通百兆交換機進行連接，具體的硬件配置和基本配置如表1和表2 所示。

表1 各個節(jié)點硬件配置情況

表2 各個節(jié)點基本設(shè)置情況

實驗數(shù)據(jù)采用一組內(nèi)蒙古科技大學(xué)校園計費系統(tǒng)日志數(shù)據(jù)，數(shù)據(jù)中包含用戶名、用戶IP、登錄時間、目標URI 等數(shù)據(jù)。逐漸增加數(shù)據(jù)量，分別使用單機和MapReduce 并行處理，進行對比。如圖4 所示。

圖4 二種處理方式效率對比

結(jié)果顯示，當(dāng)處理較小數(shù)據(jù)量時，Hadoop 集群系統(tǒng)處理效率并不占優(yōu)勢，但是當(dāng)采用較大數(shù)據(jù)時，具有良好的收斂性能，且聚類時間大大縮短，聚類效率顯著提高。

5 結(jié)束語

本文采用MapReduce 架構(gòu)可高效并行的優(yōu)勢，設(shè)計了一種基于MapReduce 的并行聚類模型，該模型能夠提高對海量數(shù)據(jù)進行挖掘研究的效率，能夠充分提高普通PC 機組成的Cluster 的計算性能，能夠在短時間內(nèi)得出聚類結(jié)果。實驗表明，在Hadoop 平臺上該模型具有較好的加速比，并能達到較高的準確率。

［1］劉洋.基于MapReduce 的中醫(yī)藥并行數(shù)據(jù)挖掘服務(wù)［D］.杭州:浙江大學(xué)，2010.

［2］李成華，張新訪，金海，等.MapReduce:新型的分布式并行計算編程模型［J］.計算機工程與科學(xué)，2011，33(3):129-135.

［3］郝曉飛，譚躍生，王靜宇.Hadoop 平臺上Apriori 算法并行化研究與實現(xiàn)［J］.計算機與現(xiàn)代化，2013(3):1-5.

［4］施佺，肖仰華，溫文灝，等.基于Mapreduce 的大規(guī)模社會網(wǎng)絡(luò)提取方法研究［J］.計算機應(yīng)用研究，2011，28(1):145-148.

［5］劉永增.基于Hadoop/Hive 的海量Web 日志處理系統(tǒng)的設(shè)計與實現(xiàn)［D］.大連:大連理工大學(xué)，2011.

［6］舒琰，向陽，張騏，等.基于PageRank 的微博排名MapReduce 算法研究［J］.計算機技術(shù)與發(fā)展，2013，23(2):73-76，81.

［7］張宇，程久軍.基于MapReduce 的矩陣分解推薦算法研究［J］.計算機科學(xué)，2013，40(1):19-21，36.

［8］丁光華，周繼鵬，周敏.基于MapReduce 的并行貝葉斯分類算法的設(shè)計與實現(xiàn)［J］.微計算機信息，2010，36(9):190-191，176.

［9］艾樹宇.基于Hadoop/MapReduce 的K_NN 算法［J］.科技傳播，2013(1):203-204，200.

［10］孟海東，楊彥侃.并行聚類算法的設(shè)計與研究［J］.計算機與現(xiàn)代化，2010(8):5-8.

［11］王淑玲.增量聚類算法的設(shè)計與實現(xiàn)［D］.包頭:內(nèi)蒙古科技大學(xué)，2009.

［12］戎翔，李玲娟.基于MapReduce 的頻繁項集挖掘方法［J］.西安郵電學(xué)院學(xué)報，2011，16(4):37-39，43.

［13］梁建武，周楊.一種異構(gòu)環(huán)境下的Hadoop 調(diào)度算法［J］.中國科技論文，2012，7(7):495-498.

［14］李銳，王斌.文本處理中的MapReduce 技術(shù)［J］.中文信息學(xué)報，2012，26(4):9-20.

［15］周迎春，駱嘉偉.一種改進的BIRCH 聚類分析算法及其應(yīng)用研究［J］.湛江師范學(xué)院學(xué)報，2009，30(3):83-87.