翟俊海, 田石, 張素芳, 王謨瀚, 宋丹丹

(1. 河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院 河北省機(jī)器學(xué)習(xí)與計(jì)算智能重點(diǎn)實(shí)驗(yàn)室, 河北 保定 071002;2. 中國(guó)氣象局 氣象干部培訓(xùn)學(xué)院河北分院，河北 保定 071000)

聚類分析是數(shù)據(jù)挖掘的基本任務(wù)之一，已成功應(yīng)用于許多領(lǐng)域，聚類算法可大致分為2類：層次聚類算法和劃分聚類算法[1].K-means算法是著名的劃分聚類算法，在2006年舉行的國(guó)際數(shù)據(jù)挖掘?qū)W術(shù)會(huì)議上評(píng)出的十大數(shù)據(jù)挖掘算法中[1]，K-means名列第2位.K-means算法是一種硬聚類算法，具有非此即彼的性質(zhì)，即一個(gè)樣例只能屬于一個(gè)簇.Bezdek[2]對(duì)K-means算法進(jìn)行了改進(jìn)，提出了模糊K-means算法.模糊聚類建立了樣例對(duì)類別的不確定性描述，更能客觀地反映現(xiàn)實(shí)世界，往往比清晰聚類能獲得更好的聚類效果.不管是清晰聚類還是模糊聚類，都容易受聚類個(gè)數(shù)與初始聚類中心的影響，研究人員提出了許多自適應(yīng)確定聚類個(gè)數(shù)的方法.針對(duì)K-均值聚類算法，Gupta等[3]提出了一種利用最小化聚類中心之間距離快速自動(dòng)確定聚類個(gè)數(shù)的方法.受人類觀察視野范圍內(nèi)山峰峰頂?shù)膯l(fā)，Masud等[4]提出了一種確定聚類個(gè)數(shù)的新方法，該方法用混合高斯模型對(duì)觀測(cè)點(diǎn)和對(duì)象之間距離的分布進(jìn)行建模.Lord等[5]提出了一種利用對(duì)象的穩(wěn)定性確定聚類個(gè)數(shù)的方法，定義了一個(gè)聚類中對(duì)象的穩(wěn)定性指標(biāo).Yu等[6]提出了一種利用決策理論粗糙集自動(dòng)確定聚類個(gè)數(shù)的方法，文獻(xiàn)[7]和[8]對(duì)確定聚類個(gè)數(shù)的方法進(jìn)行了全面深入的綜述.隨著大數(shù)據(jù)時(shí)代的到來(lái)，聚類算法在大數(shù)據(jù)環(huán)境中的可擴(kuò)展性研究引起了研究人員的極大關(guān)注，已有一些大數(shù)據(jù)聚類方面的研究成果.例如，Havens等[9]研究了FCM(Fuzzy C-Means)算法在大數(shù)據(jù)環(huán)境中的可擴(kuò)展性問(wèn)題，對(duì)3種FCM的擴(kuò)展方法(抽樣方法、增量方法和核化方法)進(jìn)行了比較研究，得出了一些有價(jià)值的結(jié)論.Ludwig[10]研究了FCM算法并行化實(shí)現(xiàn)問(wèn)題，提出了基于MapReduce的FCM算法，并討論了其穩(wěn)定性.Bharill等[11]提出了一種可擴(kuò)展的迭代抽樣FCM算法，可對(duì)大數(shù)據(jù)進(jìn)行聚類，并用大數(shù)據(jù)開源平臺(tái)Spark實(shí)現(xiàn)了該算法.Wu等[12]研究了模糊一致性聚類問(wèn)題，定義了模糊一致性度量指標(biāo)，提出了基于模糊一致性的大數(shù)據(jù)聚類算法，并在Spark平臺(tái)上實(shí)現(xiàn)了該算法.王磊等[13]也研究了基于Spark的大數(shù)據(jù)聚類及系統(tǒng)實(shí)現(xiàn).李應(yīng)安[14]和陽(yáng)美玲[15]分別研究了基于MapReduce的大數(shù)據(jù)聚類算法.基于動(dòng)態(tài)信任評(píng)估.張彬等[16]討論了針對(duì)政務(wù)大數(shù)據(jù)分析的云服務(wù)平臺(tái)設(shè)計(jì)問(wèn)題.高學(xué)偉等[17]討論了基于Hadoop大數(shù)據(jù)建模問(wèn)題.吳信東等[18]對(duì)MapReduce與Spark用于大數(shù)據(jù)分析進(jìn)行了全面的比較.宋杰等[19]對(duì)MapReduce大數(shù)據(jù)處理平臺(tái)與算法的研究進(jìn)展進(jìn)行了全面而深入的分析.翟俊海等[20]提出了基于Spark和SimHash的大數(shù)據(jù)K-近鄰算法.張素芳等[21]對(duì)大數(shù)據(jù)與大數(shù)據(jù)機(jī)器學(xué)習(xí)研究進(jìn)行了全面的綜述，具有很高的參考價(jià)值.然而，目前還未見到基于Hadoop和Spark的大數(shù)據(jù)模糊K-means算法的比較研究，從算法執(zhí)行時(shí)間、同步次數(shù)、文件數(shù)目、容錯(cuò)性能、資源消耗這5方面進(jìn)行比較，得出的結(jié)論對(duì)從事大數(shù)據(jù)研究的人員具有較高的參考價(jià)值.

1 模糊K-均值算法

模糊K-均值算法[2]是K-均值算法的改進(jìn)，它允許一個(gè)樣例點(diǎn)以不同的隸屬度屬于不同的簇.模糊K-均值算法最小化下面的目標(biāo)函數(shù)：

(1)

其中，N是樣例數(shù)，m是大于1的參數(shù)，uij是樣例xi屬于第j個(gè)簇的隸屬度，cj是第j個(gè)簇的中心.與K-均值算法一樣，模糊K-均值算法也是一個(gè)迭代算法，在迭代過(guò)程中，模糊隸屬度uij用公式(2)更新，簇中心cj用公式(3)更新.

(2)

(3)

算法的迭代停止條件為

(4)

在公式(4)中，ε∈(0,1)，n表示迭代次數(shù).

2 基于MapReduce的模糊K-均值算法

基于MapReduce的模糊K-均值算法包括下面2個(gè)MapReduce過(guò)程.

第1個(gè)MapReduce過(guò)程用于計(jì)算聚類中心.這一過(guò)程包括下面3步：

1) 首先，系統(tǒng)會(huì)從HDFS中讀取數(shù)據(jù)并隨機(jī)生成每個(gè)數(shù)據(jù)隸屬于每一簇的隸屬度.然后，對(duì)數(shù)據(jù)進(jìn)行分片，每個(gè)分片傳入一個(gè)Map節(jié)點(diǎn)進(jìn)行處理.并且Map任務(wù)在計(jì)算完畢后會(huì)對(duì)中間數(shù)據(jù)進(jìn)行排序，使其分區(qū)內(nèi)有序.

2) combiner會(huì)將每個(gè)Map的計(jì)算結(jié)果進(jìn)行合并以減少數(shù)據(jù)傳輸，提高運(yùn)行效率.

3) Reduce會(huì)將combiner傳來(lái)的數(shù)據(jù)進(jìn)行合并，從而計(jì)算出聚類中心.

第2個(gè)MapReduce過(guò)程用于計(jì)算隸屬度.這一過(guò)程系統(tǒng)依然會(huì)從HDFS中讀取數(shù)據(jù)，進(jìn)行分片，傳遞給Map節(jié)點(diǎn)并利用之前計(jì)算出的聚類中心重新計(jì)算隸屬度，多個(gè)Map節(jié)點(diǎn)都會(huì)將計(jì)算結(jié)果傳遞給Reduce節(jié)點(diǎn)進(jìn)行比較隸屬度是否收斂，不收斂則繼續(xù)迭代，收斂則終止運(yùn)行.

不同的Map階段、combiner階段、Reduce階段之間互不干擾，都是一個(gè)獨(dú)立的任務(wù)，只有前面的任務(wù)全都完成之后才能進(jìn)行后面的任務(wù)，并且每一個(gè)任務(wù)的計(jì)算結(jié)果都要寫入磁盤.圖1通過(guò)一個(gè)例子展示了MapReduce一次迭代的流程.

圖1 MapReduce一次迭代的流程Fig.1 Schematic diagram of one iteration by MapReduce

基于MapReduce的模糊K-均值算法包括4個(gè)作業(yè)、16個(gè)任務(wù)和4次Shuffle.下面給出基于MapReduce的模糊K-均值算法的偽代碼.

1) class Mapper

2) method Map(key ,value ,context)

3) for(i= 1 tok)

4) 隸屬度的2次方

5) for(j= 1 ton)

6) 數(shù)據(jù)與隸屬度的2次方相乘

7) end

8) end

9) class Combiner

10) method combiner(key ,value ,context)

11) 具有相同鍵的數(shù)據(jù)將其值進(jìn)行相加

12) class Reducer

13) method Reduce(key ,value ,context)

14) 具有相同鍵的數(shù)據(jù)將其值進(jìn)行相加

15) 計(jì)算聚類中心

16) class Mapper

17) method Map(key ,value ,context)

18) 根據(jù)聚類中心重新計(jì)算隸屬度

19) class Reducer

20) method Reduce(key ,value ,context)

21) 計(jì)算前后2次隸屬度之差的絕對(duì)值

22) 判斷隸屬度之差的絕對(duì)值的最大值是否小于閾值

3 基于Spark的模糊K-均值算法

Spark是一種基于內(nèi)存計(jì)算的大數(shù)據(jù)處理平臺(tái)，它用RDD(resident distributed dataset)將數(shù)據(jù)組織在內(nèi)存中，并通過(guò)RDD算子對(duì)數(shù)據(jù)進(jìn)行操作.基于Spark的模糊K-均值算法需要5次轉(zhuǎn)換操作，共產(chǎn)生5個(gè)RDD.圖2通過(guò)一個(gè)例子展示了5個(gè)RDD的轉(zhuǎn)換過(guò)程.

圖2 Spark一次迭代的流程Fig.2 Schematic diagram of one iteration by Spark

Spark在一次迭代過(guò)程中需要進(jìn)行2次Shuffle操作，可以劃分成3個(gè)階段.基于Spark的模糊K-均值算法迭代2次被劃分為4個(gè)階段，包括8個(gè)任務(wù)和3次Shuffle.與MapReduce相比，減少了任務(wù)數(shù)和Shuffle次數(shù)，提高了運(yùn)行效率.下面給出基于Spark的模糊K-均值算法的偽代碼.

1) rdd = sc.textFile(Data) //讀取名為Data的文件

2) memdeg[n][k] //初始化隸屬度

3) memdegRDD = sc.parallelize(memdeg) //并行化

4) while (x是否大于閾值)

5) 計(jì)算隸屬度的2次方

6) 將數(shù)據(jù)與隸屬度的2次方進(jìn)行相乘

7) 計(jì)算聚類中心

8) 更新隸屬度

9) 計(jì)算前后2次隸屬度之差的絕對(duì)值的最大值x

4 基于2種開源平臺(tái)的大數(shù)據(jù)模糊K-means算法的理論比較

受文獻(xiàn)[18]的啟發(fā)，下面從算法執(zhí)行時(shí)間、同步次數(shù)、文件數(shù)目這3方面，對(duì)2種大數(shù)據(jù)模糊K-means算法進(jìn)行理論比較.

1)算法執(zhí)行時(shí)間

基于MapReduce模糊K-means算法的執(zhí)行時(shí)間主要用于中間數(shù)據(jù)排序和文件傳輸.中間數(shù)據(jù)排序只存在于MapReduce中，這是為了對(duì)數(shù)據(jù)進(jìn)行初步的歸并操作，避免因?yàn)閭鬏斘募?shù)量過(guò)多給網(wǎng)絡(luò)造成重大壓力.在運(yùn)算時(shí)，MapReduce需要執(zhí)行2次MapReduce操作.在第1次操作中，每個(gè)Map需要比較的次數(shù)為3，每個(gè)Combiner需要比較的次數(shù)為1；在第2次操作中，每個(gè)Map需要比較的次數(shù)為1.因此在一次迭代任務(wù)中，MapReduce任務(wù)需要比較4次，而Spark在處理數(shù)據(jù)時(shí)不需要中間結(jié)果有序，所以不需要比較.

在MapReduce中，假設(shè)平均每個(gè)Map任務(wù)處理m條數(shù)據(jù)，平均每個(gè)Reduce處理r條數(shù)據(jù)，可以得出排序時(shí)間為O(mlogm)，而在Spark中，排序時(shí)間為O(0).

關(guān)于中間數(shù)據(jù)的傳輸時(shí)間，在不考慮網(wǎng)絡(luò)傳輸性能帶來(lái)的差異的情況下，假設(shè)其傳輸速度為Cr，需要處理的數(shù)據(jù)大小為D，所以傳輸時(shí)間為D×Cr.在MapReduce任務(wù)中，數(shù)據(jù)是由執(zhí)行Map任務(wù)的節(jié)點(diǎn)發(fā)送到Reduce節(jié)點(diǎn)的，需要執(zhí)行2次Map-Reduce任務(wù)，2次發(fā)送的數(shù)據(jù)量D1=8，D2=8，所以1次迭代時(shí)間為16Cr，2次迭代時(shí)間為32Cr.Spark任務(wù)的執(zhí)行過(guò)程與MapReduce相同，需要發(fā)送2次數(shù)據(jù)，第1次傳送數(shù)據(jù)D1=4，D2=8，所以1次迭代時(shí)間為為12Cr，2次迭代時(shí)間為為24Cr.

2)文件數(shù)目

如果文件數(shù)目過(guò)多，在執(zhí)行計(jì)算時(shí)就會(huì)有大量I/O操作，嚴(yán)重影響系統(tǒng)性能.所以應(yīng)該盡量減少數(shù)據(jù)文件的數(shù)量.

在MapReduce處理數(shù)據(jù)的過(guò)程之中，每個(gè)Map節(jié)點(diǎn)都會(huì)產(chǎn)生一個(gè)文件，即使是不同的分區(qū)，數(shù)據(jù)也會(huì)存儲(chǔ)在一個(gè)文件之中，這是由MapReduce的數(shù)據(jù)存儲(chǔ)原理決定的，即每個(gè)數(shù)據(jù)都是由鍵值對(duì)的形式存儲(chǔ)，面對(duì)不同的分區(qū)可以設(shè)置不同的鍵.而在Spark中，不需要對(duì)數(shù)據(jù)進(jìn)行預(yù)排序，因此需要對(duì)數(shù)據(jù)進(jìn)行分區(qū)存儲(chǔ).

因?yàn)镸apReduce一次迭代共產(chǎn)生4個(gè)Map任務(wù)，所以產(chǎn)生2+2=4個(gè)文件；在Spark中，每個(gè)Map任務(wù)被劃分為2個(gè)分區(qū)，從而共產(chǎn)生2*2+2*2=8個(gè)文件.

3)同步次數(shù)

因?yàn)樵贛apReduce計(jì)算模型中，只有所有的Map任務(wù)完成后才可以進(jìn)行Reduce任務(wù)，所以MapReduce是同步模型.而Spark可以看作為異步模型，在需要網(wǎng)絡(luò)傳輸時(shí)，它才需要同步.在算法執(zhí)行的過(guò)程中，同步次數(shù)執(zhí)行的越少，算法的執(zhí)行速度就越快.

在執(zhí)行模糊K-均值聚類時(shí)，MapReduce與Spark的1次迭代同步次數(shù)都為2次，2次迭代MapReduce的同步次數(shù)為4次，Spark為3次.隨著算法迭代次數(shù)的增多，Spark比MapReduce的優(yōu)勢(shì)會(huì)越來(lái)越明顯.

4)容錯(cuò)性能

在實(shí)際應(yīng)用中，難免遇到用戶代碼錯(cuò)誤、進(jìn)程崩潰、機(jī)器宕機(jī)等情況，良好的容錯(cuò)性能能使系統(tǒng)快速地從故障中恢復(fù)過(guò)來(lái)，合理的容錯(cuò)機(jī)制是算法執(zhí)行的保證[20].使用MapReduce的好處是它有很強(qiáng)的容錯(cuò)能力，使你的Job能夠成功完成.MapReduce通過(guò)冗余備份實(shí)現(xiàn)容錯(cuò)，雖然會(huì)產(chǎn)生大量的I/O操作，但是在計(jì)算出現(xiàn)問(wèn)題時(shí)容易恢復(fù)，安全性比較高.而Spark通過(guò)血緣關(guān)系實(shí)現(xiàn)容錯(cuò)，文獻(xiàn)[19]系統(tǒng)分析了MapReduce和Spark的容錯(cuò)能力，證明了MapReduce的容錯(cuò)性能確實(shí)比Spark要好.

5)資源消耗

在處理大數(shù)據(jù)問(wèn)題時(shí)，不同的算法對(duì)計(jì)算機(jī)性能的要求是不同的，如排序和查詢算法需要有大量的I/O操作，對(duì)網(wǎng)絡(luò)帶寬要求比較高；而執(zhí)行K-均值、PageRank等迭代算法時(shí)需要做大量的計(jì)算，對(duì)CPU要求比較高.當(dāng)使用MapReduce與Spark運(yùn)行模糊K-均值算法時(shí)，MapReduce在內(nèi)存、網(wǎng)絡(luò)以及磁盤的占用率上都要低于Spark.顯然，MapReduce對(duì)硬件要求比Spark更低，成本更低.

5 基于MapReduce和Spark的大數(shù)據(jù)模糊K-means算法的實(shí)驗(yàn)比較

實(shí)驗(yàn)所用的數(shù)據(jù)集包括3個(gè)人工大數(shù)據(jù)集和4個(gè)UCI數(shù)據(jù)集，對(duì)基于2種開源平臺(tái)的大數(shù)據(jù)模糊K-means算法從運(yùn)行時(shí)間和迭代次數(shù)2方面進(jìn)行了實(shí)驗(yàn)比較.為描述方便，基于MapReduce的模糊K-均值算法記為MK-Means，基于Spark的模糊K-均值算法記為SK-Means.4個(gè)UCI數(shù)據(jù)集分別是Covtype、HT_Sensor、Poker-hand-testing和SUSY；3個(gè)人工大數(shù)據(jù)集都是用高斯分布生成的.第1個(gè)人工數(shù)據(jù)集GAUSS1是一個(gè)2類包含100萬(wàn)個(gè)點(diǎn)的數(shù)據(jù)集，每類包含50萬(wàn)個(gè)樣例.2類服從的高斯分布為p(x|ωi)～N(μi,∑i),i=1,2，參數(shù)列于表1中.

表1 GAUSS1的參數(shù)

第2個(gè)人工數(shù)據(jù)集GAUSS2是一個(gè)包含3類樣例的數(shù)據(jù)集，每一類包含40萬(wàn)個(gè)樣例，服從的概率分布分別為

第3個(gè)人工數(shù)據(jù)集GAUSS3是一個(gè)4類包含100萬(wàn)個(gè)點(diǎn)的3維數(shù)據(jù)集，每類250 000個(gè)點(diǎn)，每類服從的高斯分布為p(x|ωi)～N(μi,∑i),i=1,2,3,4,參數(shù)如表2所示.

表2 GAUSS3的參數(shù)

實(shí)驗(yàn)客戶端開發(fā)環(huán)境為Eclipse，JDK版本為jdk-7u80-windows-x64.實(shí)驗(yàn)所用集群開發(fā)環(huán)境主、從節(jié)點(diǎn)的基本信息如表3所示.

表3 實(shí)驗(yàn)環(huán)境的基本信息

在人工數(shù)據(jù)集的實(shí)驗(yàn)中，隱去數(shù)據(jù)集的類別標(biāo)簽，并設(shè)置聚類數(shù)據(jù)K為實(shí)際的類別數(shù)，實(shí)驗(yàn)結(jié)果列于表4中.

表4 2種算法實(shí)驗(yàn)比較的結(jié)果

從表4可以看出，相同的數(shù)據(jù)在不同平臺(tái)迭代次數(shù)并不完全相同，是因?yàn)閿?shù)據(jù)的初始隸屬度的確定具有隨機(jī)性，具有一定的差異.其中，GAUSS3，HT_Sensor與SUSY差異較大一些，是因?yàn)镚AUSS3，HT_Sensor數(shù)據(jù)集的類別數(shù)較多，SUSY的數(shù)據(jù)量較大，隨機(jī)性也相對(duì)大一些，迭代次數(shù)差異相較于其他數(shù)據(jù)自然也大一些.

5 結(jié)束語(yǔ)

本文對(duì)基于MapReduce和Spark的2種大數(shù)據(jù)模糊-K均值算法進(jìn)行了比較研究，得出如下結(jié)論：1)從算法執(zhí)行時(shí)間上看，基于MapReduce的模糊K-均值算法較慢，基于Spark的模糊K-均值算法較快；2)從需要緩存的文件數(shù)目方面來(lái)看，基于MapReduce的模糊K-均值算法需要緩存的較少，基于Spark的模糊K-均值算法需要緩存的較多；3)從同步次數(shù)方面來(lái)看，基于MapReduce的模糊K-均值算法需要的同步次數(shù)較多，基于Spark的模糊K-均值算法需要的同步次數(shù)較少；4)從容錯(cuò)性能方面來(lái)看，基于MapReduce的模糊K-均值算法較強(qiáng)，而基于Spark的模糊K-均值算法較弱，這種容錯(cuò)性能差異是由大數(shù)據(jù)開源平臺(tái)決定的，而不是由模糊K-均值算法決定的；5)從資源消耗方面來(lái)看，基于MapReduce的模糊K-均值算法資源消耗較少，基于Spark的模糊K-均值算法資源消耗較多.