Spark平臺(tái)下類別數(shù)據(jù)互信息計(jì)算的并行化

李俊麗

晉中學(xué)院 信息技術(shù)與工程學(xué)院，山西 晉中 030619

互信息是對兩個(gè)隨機(jī)變量之間共享的信息量的度量。在現(xiàn)實(shí)世界中，互信息計(jì)算常被用來檢測兩個(gè)屬性之間的相關(guān)性。互信息計(jì)算具有廣泛的應(yīng)用，如特征選擇[1，2]、特征分組[3]、聚類[4]和離群點(diǎn)檢測[5]等。由于互信息計(jì)算量非常大，互信息的計(jì)算過程成了許多應(yīng)用程序的瓶頸。尤其在單機(jī)上運(yùn)行互信息計(jì)算[1-3]更是由于計(jì)算資源和存儲(chǔ)資源的限制，導(dǎo)致性能下降。

近年來，Spark[6]內(nèi)存計(jì)算平臺(tái)已經(jīng)成為一個(gè)有吸引力的并行計(jì)算模型。Spark最大的優(yōu)勢是可以將中間結(jié)果保存到內(nèi)存中，而不會(huì)導(dǎo)致I/O訪問HDFS很慢，很多研究都充分利用Spark平臺(tái)來進(jìn)行迭代數(shù)據(jù)的計(jì)算。

本文結(jié)合大數(shù)據(jù)研究背景，給出一種基于Spark 的類別數(shù)據(jù)的并行互信息計(jì)算方法PMS（Parallel Mutualinformation computation on Spark），主要貢獻(xiàn)如下：充分考慮并行分布式計(jì)算的因素，緊密結(jié)合Spark 內(nèi)存計(jì)算框架，提出適合并行實(shí)現(xiàn)的大規(guī)模類別數(shù)據(jù)互信息計(jì)算方法。為了減少特征對之間互信息計(jì)算量大、重復(fù)性的特點(diǎn)，采用了列變換的方法將數(shù)據(jù)集進(jìn)行了轉(zhuǎn)換。最后在具有24個(gè)節(jié)點(diǎn)的Spark集群上進(jìn)行廣泛的實(shí)驗(yàn)，使用人工合成數(shù)據(jù)集和UCI 數(shù)據(jù)集驗(yàn)證了PMS 的有效性、可伸縮性和可擴(kuò)展性。

1 相關(guān)工作

互信息是信息論中對兩個(gè)隨機(jī)變量關(guān)聯(lián)程度的統(tǒng)計(jì)描述，可以表示為這兩個(gè)隨機(jī)變量概率的函數(shù)。從觀測樣本中估計(jì)互信息是其最基本的操作[7]，在一些數(shù)據(jù)挖掘任務(wù)[8]和獨(dú)立性測試[9]中都很有用?，F(xiàn)在，互信息被用作特性之間冗余的度量，以及評估每個(gè)特性相關(guān)性的依賴性度量[8]。文獻(xiàn)[1]提出了一種基于互信息的標(biāo)簽分布特征選擇算法，挖掘出每個(gè)實(shí)例中隱藏的標(biāo)簽意義。文獻(xiàn)[2]提出了一種基于互信息的混合屬性數(shù)據(jù)特征選擇方法，將互信息推廣到混合屬性數(shù)據(jù)，但文獻(xiàn)[1-2]僅適用于特征選擇。文獻(xiàn)[3]將互信息應(yīng)用于特征分組算法，但由于在單機(jī)上運(yùn)行，效率較低。

隨著大數(shù)據(jù)時(shí)代的到來，為了提高互信息計(jì)算的效率，也提出了多種有效的并行互信息計(jì)算方法。例如，文獻(xiàn)[10]提出了一種計(jì)算圖像配準(zhǔn)互信息的并行計(jì)算方法，Adinetz 等人[11]提出了多GPU 圖像配準(zhǔn)互信息度量的計(jì)算方法，然而文獻(xiàn)[10-11]的并行計(jì)算方法大多是基于GPU和多核處理器計(jì)算平臺(tái)，而Spark計(jì)算平臺(tái)在并行計(jì)算中優(yōu)勢更足。文獻(xiàn)[12]雖然是在Spark平臺(tái)上對互信息進(jìn)行計(jì)算，但沒考慮互信息計(jì)算中對列操作的優(yōu)勢。

本文提出的PMS 算法是在Spark 計(jì)算平臺(tái)上并行計(jì)算互信息的，主要使用互信息來度量類別數(shù)據(jù)特征之間的相似性，而且采用列變換對數(shù)據(jù)集進(jìn)行轉(zhuǎn)換，并將并行互信息計(jì)算應(yīng)用于類別數(shù)據(jù)的特征分組。

2 基本概念

2.1 互信息

在信息論中，熵和互信息可以代表相互依賴的信息度量[13]，這是反映特征組的特征之間相互關(guān)系的最顯著的特征。

考慮一個(gè)包含n個(gè)對象的數(shù)據(jù)集DS，每個(gè)對象都由m個(gè)特征表示。使用H(yi,yj)和MI(yi;yj)分別表示集合DS上計(jì)算的特征yi和yj之間的熵和互信息[14]。熵H(yi,yj)可寫成：

其中Pij(yi=vik∧yj=vjl) 為特征yi和yj分別等于vik和vjl的概率。公式（1）中di和dj為特征yi和yj的取值個(gè)數(shù)；vik和vjl可以在集合D(yi)和D(yj)中找到，其中D(yi)={vi1,…,vidi},D(yj)={vj1,…,vjdj}。熵H(yi,yj)是概率Pij和lbPij的乘積的函數(shù)。

MI(yi;yj)作為特征yi和yj之間的互信息?；バ畔(yi,yj)表示如下：

其中概率Pij、特征yi和yj、值vik和vjl、域di和dj、集合D(yi)和D(yj)與（1）中的相同，Pi和Pj分別為特征yi和yj等于vik和vjl的概率。

2.2 列變換

在本節(jié)中，根據(jù)計(jì)算任務(wù)的資源需求提出了一種基于列的轉(zhuǎn)換方法。PMS 中的列變換模塊盡量減少互信息計(jì)算引起的單屬性值頻率和屬性對值頻率的計(jì)算。一旦數(shù)據(jù)被轉(zhuǎn)換，它們就可以被緩存并在隨后的循環(huán)中重用。

列變換過程如圖1所示。首先，根據(jù)屬性的相互獨(dú)立性，將原始數(shù)據(jù)集DS劃分為若干屬性子集。其次，針對迭代過程中重復(fù)使用互信息計(jì)算的問題，采用兩個(gè)變長數(shù)組保存計(jì)算互信息的單屬性值頻率和屬性對值頻率的結(jié)果。假設(shè)數(shù)據(jù)集DS 的大小為n，每個(gè)數(shù)據(jù)對象有m個(gè)屬性，即y1～ym。根據(jù)計(jì)算任務(wù)的不同，將DS劃分為不同的屬性子集。每個(gè)屬性子集形成一個(gè)獨(dú)立于其他屬性子集的RDD對象。

圖1 列變換過程

此外，為了解決互信息的重復(fù)計(jì)算問題，單一屬性值和屬性對值的頻率計(jì)算緩存到兩個(gè)分別叫singleCol和doubleCol的變長數(shù)組，然后廣播給所有從節(jié)點(diǎn)。然后，計(jì)算任務(wù)在特征分組過程中從singleCol和doubleCol數(shù)組中加載相應(yīng)的數(shù)據(jù)，從而有效地重用了單屬性和屬性對數(shù)據(jù)。由于兩個(gè)屬性之間的互信息值相同，因此MI(yi;yj)和MI(yj;yi)的值相同。在計(jì)算屬性對值出現(xiàn)頻率的過程中，每個(gè)屬性對只需要計(jì)算一次，如表2所示。表1 和表2 舉例說明了PMS 的變長數(shù)組singleCol和doubleCol。

表1 PMS的變長數(shù)組singleCol舉例

表2 PMS的變長數(shù)組doubleCol舉例

3 PMS算法的具體實(shí)現(xiàn)

本章給出了基于Spark分布式操作的大規(guī)模分類數(shù)據(jù)PMS 算法的實(shí)現(xiàn)細(xì)節(jié)。首先描述了列變換的實(shí)現(xiàn)，然后進(jìn)行了大數(shù)據(jù)環(huán)境下并行互信息計(jì)算的實(shí)現(xiàn)。

3.1 列變換

列變換主要負(fù)責(zé)將原始數(shù)據(jù)集DS轉(zhuǎn)換為若干特征子集，主要由以下基本步驟完成：首先，使用關(guān)鍵字val定義一個(gè)可變長數(shù)組doubleCol用于存放屬性對的計(jì)算結(jié)果。其次，使用map 映射操作將RDD 數(shù)據(jù)datapre 轉(zhuǎn)換為鍵值對的形式，即pair((x(m);x(n));1）。值得注意的是，((x(m);x(n))是屬性對m和n的取值；1 表示屬性對的值出現(xiàn)一次，并且記錄每一對屬性對取值的整體出現(xiàn)情況。最后，使用關(guān)鍵字val 定義另一個(gè)可變長數(shù)組singleCol用于存放單個(gè)屬性的計(jì)算結(jié)果。

算法的偽代碼描述如下：

算法1 列變換

輸入：數(shù)據(jù)集DS(n×m)

輸出：兩個(gè)變長數(shù)組singleCol和doubleCol

1. valdoubleCol=new Array[ArrayBuffer[Map[（String，String），Long]]]（dimension）

2. for（m=0；m<=dimension；m++）

3. for（n=0；n<=dimension；n++）

4.doubleCol（m）（n）+=datapre：map（x=>（（x（m）；x（n））；1））：countByKey（）：toMap

5. end for

6. end for

7. valsinglecol=ArrayBuffer[Map[String，Long]]（）

8. for（k=0；k<=dimension；k++）

9.singlecol+=datapre：map（x=>（x（k）；1））：countByKey（）：toMap

10. end for

3.2 互信息計(jì)算

互信息計(jì)算過程利用單屬性值和屬性對值的頻率計(jì)算屬性對的互信息。由算法1得到了兩個(gè)數(shù)組singleCol和doubleCol作為算法2 的輸入。算法2 開始計(jì)算屬性對之間的互信息，首先定義兩個(gè)函數(shù)Pr1和Pr2。Pr1計(jì)算任何單個(gè)屬性值出現(xiàn)的概率，Pr2計(jì)算任何屬性對值出現(xiàn)的概率。其次，從輸入中得到屬性對的列號（例如(y1;y2)），t1從doubleCol中提取屬性對(y1;y2)的所有值，t2和t3分別從singleCol中提取與單個(gè)屬性y1和y2對應(yīng)的所有值。最后根據(jù)公式（2）先計(jì)算三個(gè)概率，然后再計(jì)算互信息并返回互信息值MI。下面給出了算法2計(jì)算互信息的偽代碼。

算法2 計(jì)算互信息MI

輸入：兩個(gè)變長數(shù)組singleColanddoubleCol

輸出：屬性對之間的互信息MI

1. functionPr1（t：Map [String，Long]，k：String）：Double

2. varp1：Double=0

3. for（i

4. if（i.equals（k））

5.p1=t（i）/n

6. endif

7. endfor

8. functionPr2（t：Map[（String，String），Long]，k（String，String））：Double

9. varp2：Double=0

10. for（i

11. if（i.equals（k））

12.p2=t（i）/n

13. endif

14. endfor

15.function CalculateMI（y1：Int；y2：Int）：Double

16.valt1=doubleCol（y1）（y2）

17.valt2=singleCol（y1）

18.valt3=singleCol（y2）

19.var MI：Double=0

20. for（i

21. valp1=Pr2（t1；i）

22. valp2=Pr1（t2；i._1）

23. valp3=Pr1（t3；i._2）

24. MI+=Pr2?Math：log（p1=（p2?p3））

25. end for

26.return MI

4 PMS應(yīng)用

基于Spark的互信息并行計(jì)算可以用來執(zhí)行一些計(jì)算量大的應(yīng)用。本章使用互信息作為相似性度量來度量特征變量之間的相關(guān)性，以用于特征分組。

4.1 特征分組

由于互信息能夠揭示特征之間的一般依賴關(guān)系，常被用于特征之間的相似性度量，以用于特征分組。相似性是定量測量兩個(gè)特征之間相關(guān)性強(qiáng)弱的度量指標(biāo)。特征分組的目的是將一組高度相關(guān)的特征放到一個(gè)組中，廣泛用于數(shù)據(jù)挖掘的各類算法中[15]。

圖2顯示了數(shù)據(jù)集DS中的特征集合Y和特征組集合c之間的關(guān)系。在本例中，數(shù)據(jù)集DS中特征集Y包含12 個(gè)分類特征Y={y1,y2,…,y12}，這些特征被分為三個(gè)特征組C={C1,C2,C3}。其中，C1={y1,y3,y7}，C2={y2,y5,y9,y10,y12}，C3={y4,y6,y8,y11}。

圖2 數(shù)據(jù)集中的特征分組

4.2 數(shù)據(jù)集

PMS 使用人工合成數(shù)據(jù)集和現(xiàn)實(shí)世界的分類數(shù)據(jù)集來進(jìn)行性能評估。整個(gè)實(shí)驗(yàn)中使用的所有真實(shí)世界的數(shù)據(jù)集都是從UCI機(jī)器學(xué)習(xí)庫中提取的，包括Mushroom、Chess、Connect-4、Breast-cancer 和Splice，如表3所示。

表3 人工合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集

通過以下兩個(gè)步驟生成人工合成數(shù)據(jù)集。首先使用GAClust 創(chuàng)建一個(gè)相對較小的數(shù)據(jù)集。接下來，復(fù)制第一步中創(chuàng)建的數(shù)據(jù)集，以擴(kuò)大數(shù)據(jù)集的大小。合成數(shù)據(jù)集有100 個(gè)特征；這些數(shù)據(jù)集的大小分別為8 GB、16 GB、24 GB 和32 GB，如表3 所示。使用人工數(shù)據(jù)集可以定量地評估POS 算法的可擴(kuò)展性和可伸縮性。

5 實(shí)驗(yàn)與分析

5.1 環(huán)境配置

PMS 算法的實(shí)現(xiàn)環(huán)境為具有24 個(gè)節(jié)點(diǎn)的Spark集群，其中每個(gè)節(jié)點(diǎn)都有一個(gè)Intel 處理器（E5-1620 v2系列3.7 GHz），4 芯16 GB RAM；主節(jié)點(diǎn)硬盤配置為500 GB，其他節(jié)點(diǎn)的磁盤容量是2 TB。集群中的所有數(shù)據(jù)節(jié)點(diǎn)都通過千兆以太網(wǎng)連接；使用SSH協(xié)議保證節(jié)點(diǎn)之間的通信。在Spark 的獨(dú)立模式standalone 下實(shí)現(xiàn)了PMS算法。在PMS實(shí)現(xiàn)中使用的編程語言是Scala，它是一種在Java 虛擬機(jī)（JVM）上運(yùn)行的函數(shù)式面向?qū)ο笳Z言；Scala無縫集成了現(xiàn)有的Java程序。最后，使用集成開發(fā)環(huán)境IntelliJ IDEA來開發(fā)PMS，軟件配置如表4所示。

表4 Spark集群軟件配置

5.2 PMS算法的效率

PMS是一個(gè)并行算法，為了測試PMS算法的效率，在偽分布環(huán)境下比較PMS和它對應(yīng)的串行算法的運(yùn)行時(shí)間。表5顯示了在UCI數(shù)據(jù)集上運(yùn)行時(shí)間的比較。

表5 運(yùn)行時(shí)間比較 s

如表5所示，PMS算法在所有情況下都優(yōu)于Sequential PMS算法。例如，Sequential PMS在較小的數(shù)據(jù)集Breastcancer中耗時(shí)6.22 s，而PMS僅花費(fèi)4.61 s。但是在較大的數(shù)據(jù)集Connect-4 中，Sequential PMS 耗時(shí)568.24 s，而PMS 僅花費(fèi)40.18 s。實(shí)驗(yàn)結(jié)果表明，算法的效率隨著數(shù)據(jù)集的大小差異較大，數(shù)據(jù)集越大，PMS算法效率提高越明顯。因此，PMS更適用于大規(guī)模數(shù)據(jù)處理。

5.3 可伸縮性

這組實(shí)驗(yàn)使用各種人工合成數(shù)據(jù)集在Spark集群上運(yùn)行PMS算法。評估當(dāng)被測數(shù)據(jù)集的維度和數(shù)據(jù)集大小持續(xù)增長時(shí)PMS 的可擴(kuò)展性，目標(biāo)是檢測PMS 算法在處理大數(shù)據(jù)時(shí)的表現(xiàn)。計(jì)算節(jié)點(diǎn)數(shù)量分別設(shè)置為4、8、16和24。

5.3.1 數(shù)據(jù)集大小的影響

從圖3（a）可以看出，隨著數(shù)據(jù)集大小從8 GB 增加到32 GB，PMS的執(zhí)行時(shí)間總體上呈快速增長趨勢。這種趨勢是可以預(yù)見的，因?yàn)樘幚砀蟮臄?shù)據(jù)集需要更多的時(shí)間。另一方面，從圖3（a）可以看出，集群中計(jì)算節(jié)點(diǎn)數(shù)量的增加導(dǎo)致算法執(zhí)行時(shí)間的減少，這說明節(jié)點(diǎn)越多，集群計(jì)算能力越強(qiáng)。

圖3（b）引入了一個(gè)稱為時(shí)間比的度量標(biāo)準(zhǔn)將圖3（a）中的結(jié)果標(biāo)準(zhǔn)化。選擇4 GB 數(shù)據(jù)集的PMS 運(yùn)行時(shí)間作為基線，即4 GB數(shù)據(jù)的時(shí)間比設(shè)置為1。數(shù)據(jù)集的時(shí)間比計(jì)算為該數(shù)據(jù)集的處理時(shí)間與基線之間的比值。圖3（b）描述了在Spark集群上處理4個(gè)不同大小數(shù)據(jù)集的PMS 執(zhí)行時(shí)間比。從圖3（b）可以看出，越大型的集群越能更好地處理大規(guī)模數(shù)據(jù)集。例如，在4 GB 數(shù)據(jù)集中，4節(jié)點(diǎn)集群PMS的執(zhí)行時(shí)間比為1.0；而當(dāng)計(jì)算節(jié)點(diǎn)數(shù)設(shè)置為24時(shí)，時(shí)間仍為1.0。而在32 GB數(shù)據(jù)集中，4節(jié)點(diǎn)集群PMS的執(zhí)行時(shí)間比為10.5；而當(dāng)計(jì)算節(jié)點(diǎn)數(shù)設(shè)置為24時(shí)，時(shí)間比變?yōu)?.8，差距較大。這說明對于大規(guī)模數(shù)據(jù)集，計(jì)算節(jié)點(diǎn)越多，算法效率提高越明顯。

圖3 數(shù)據(jù)集大小對PMS運(yùn)行時(shí)間的影響

5.3.2 維度的影響

圖4（a）顯示了當(dāng)數(shù)據(jù)集維度從50 逐漸增加200 時(shí)的性能趨勢?？梢钥吹接捎赑MS算法需要計(jì)算任意一對特征之間的互信息MI，隨著維數(shù)的增加，計(jì)算速度會(huì)減慢。保持維數(shù)不變，擴(kuò)展計(jì)算節(jié)點(diǎn)的數(shù)量可以顯著縮短計(jì)算時(shí)間。這種趨勢表明增加計(jì)算節(jié)點(diǎn)的數(shù)量會(huì)加速計(jì)算。圖4（b）描述了不同維度下PMS執(zhí)行時(shí)間的時(shí)間比。選擇有50 個(gè)維度的數(shù)據(jù)集的運(yùn)行時(shí)間作為基線。同樣，觀察到，當(dāng)計(jì)算節(jié)點(diǎn)數(shù)量相對較少時(shí)，執(zhí)行時(shí)間對維度更加敏感。例如，在一個(gè)4節(jié)點(diǎn)Spark集群中，當(dāng)維度數(shù)量從50個(gè)激增到200個(gè)時(shí)，執(zhí)行時(shí)間增加到最高的比率19.7；然而在24 節(jié)點(diǎn)集群上，時(shí)間比下降到8.3。結(jié)果表明，對于大型集群而言，PMS算法能夠加快互信息的計(jì)算。

圖4 維度大小對PMS運(yùn)行時(shí)間的影響

5.4 可擴(kuò)展性

現(xiàn)在通過增加計(jì)算節(jié)點(diǎn)的數(shù)量（分別設(shè)置為4、8、16和24）來評估PMS的執(zhí)行性能。同樣，將數(shù)據(jù)集大小配置為8 GB、16 GB、24 GB 和32 GB，同時(shí)對PMS 的可擴(kuò)展性進(jìn)行分析，如圖5所示。

圖5 PMS的可擴(kuò)展性分析

圖5（a）顯示了Spark集群中節(jié)點(diǎn)數(shù)量對運(yùn)行時(shí)間的影響。由圖5（a）可以看出，隨著計(jì)算節(jié)點(diǎn)數(shù)量的增加，PMS 的執(zhí)行時(shí)間明顯減少。大數(shù)據(jù)集（如32 GB）的下降趨勢非常明顯。當(dāng)數(shù)據(jù)集較小時(shí)（例如4 GB），集群擴(kuò)展性能提高很微弱。結(jié)果表明，PMS是一種對大數(shù)據(jù)集具有高擴(kuò)展性的并行算法。

圖5（b）展示了計(jì)算節(jié)點(diǎn)數(shù)量對算法加速的影響。從圖5（b）可以看出，對于所有測試數(shù)據(jù)集來說，PMS的加速率接近線性。這樣的結(jié)果表明，本文并行算法PMS能夠保持大規(guī)模數(shù)據(jù)集計(jì)算時(shí)的高性能。

6 結(jié)束語

隨著大數(shù)據(jù)時(shí)代的到來，數(shù)據(jù)量越來越大，互信息的計(jì)算量隨之增加。本文開發(fā)了基于Spark的互信息并行計(jì)算方法PMS。在并行化過程中，在Spark集群上進(jìn)行了列變換。列變換實(shí)現(xiàn)了單特征值和特征對值數(shù)據(jù)的重復(fù)使用，有效地解決了大規(guī)模類別數(shù)據(jù)互信息計(jì)算量大，復(fù)雜的問題。最后在24節(jié)點(diǎn)的Spark集群上通過人工合成和UCI真實(shí)數(shù)據(jù)集驗(yàn)證了算法的性能，實(shí)驗(yàn)結(jié)果驗(yàn)證了PMS 算法在執(zhí)行效率、可伸縮性和可擴(kuò)展性等方面的優(yōu)勢。