李俊麗

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

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

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

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

1 相關(guān)工作

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

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

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

2 基本概念

2.1 互信息

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

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

其中Pij(yi=vik∧yj=vjl) 為特征yi和yj分別等于vik和vjl的概率。公式（1）中di和dj為特征yi和yj的取值個數(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ù)計算任務(wù)的資源需求提出了一種基于列的轉(zhuǎn)換方法。PMS 中的列變換模塊盡量減少互信息計算引起的單屬性值頻率和屬性對值頻率的計算。一旦數(shù)據(jù)被轉(zhuǎn)換，它們就可以被緩存并在隨后的循環(huán)中重用。

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

圖1 列變換過程

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

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

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

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

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

3.1 列變換

列變換主要負(fù)責(zé)將原始數(shù)據(jù)集DS轉(zhuǎn)換為若干特征子集，主要由以下基本步驟完成：首先，使用關(guān)鍵字val定義一個可變長數(shù)組doubleCol用于存放屬性對的計算結(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 定義另一個可變長數(shù)組singleCol用于存放單個屬性的計算結(jié)果。

算法的偽代碼描述如下：

算法1 列變換

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

輸出：兩個變長數(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 互信息計算

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

算法2 計算互信息MI

輸入：兩個變長數(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的互信息并行計算可以用來執(zhí)行一些計算量大的應(yīng)用。本章使用互信息作為相似性度量來度量特征變量之間的相關(guān)性，以用于特征分組。

4.1 特征分組

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

圖2顯示了數(shù)據(jù)集DS中的特征集合Y和特征組集合c之間的關(guān)系。在本例中，數(shù)據(jù)集DS中特征集Y包含12 個分類特征Y={y1,y2,…,y12}，這些特征被分為三個特征組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ù)據(jù)集來進(jìn)行性能評估。整個實驗中使用的所有真實世界的數(shù)據(jù)集都是從UCI機(jī)器學(xué)習(xí)庫中提取的，包括Mushroom、Chess、Connect-4、Breast-cancer 和Splice，如表3所示。

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

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

5 實驗與分析

5.1 環(huán)境配置

PMS 算法的實現(xiàn)環(huán)境為具有24 個節(jié)點(diǎn)的Spark集群，其中每個節(jié)點(diǎn)都有一個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 下實現(xiàn)了PMS算法。在PMS實現(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是一個并行算法，為了測試PMS算法的效率，在偽分布環(huán)境下比較PMS和它對應(yīng)的串行算法的運(yùn)行時間。表5顯示了在UCI數(shù)據(jù)集上運(yùn)行時間的比較。

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

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

5.3 可伸縮性

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

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

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

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

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

5.3.2 維度的影響

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

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

5.4 可擴(kuò)展性

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

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

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

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

6 結(jié)束語

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