基于MapReduce的分布式貪心EM算法*

曹家慶, 吳觀茂

(安徽理工大學(xué) 計算機科學(xué)與工程學(xué)院，安徽 淮南 232001)

0 引言

期望最大化算法(Expectation Maximization Algorithm，EM算法)是一種在概率模型中尋找參數(shù)最大似然估計或者最大后驗估計的迭代算法，可以極大地降低求解最大似然估計的計算復(fù)雜度。然而傳統(tǒng)EM算法作為數(shù)據(jù)挖掘中非常重要的聚類算法，在面對TB級別、PB級別等大規(guī)模數(shù)據(jù)集和高維數(shù)據(jù)集時，其缺陷顯得越來越突出。因此如何對傳統(tǒng)EM算法進行優(yōu)化是機器學(xué)習(xí)算法的研究熱點之一?，F(xiàn)階段對于EM算法優(yōu)化的具體方向便是如何有效地處理如下兩個問題：(1)初始模型成分數(shù)目需要人為設(shè)定；(2)收斂速度隨著數(shù)據(jù)規(guī)模的增大而急劇減慢。

針對上述第一個問題，在傳統(tǒng)EM算法的基礎(chǔ)上使用貪心策略(貪心EM算法)，通過對僅含一個模型成分的高斯混合模型迭代增加新模型分量，直到滿足某種終止條件為止。雖然該算法有效地提高了算法的準(zhǔn)確度，但是上述第二個問題仍未得到有效解決。

為了解決上述問題，本文提出了一種分布式貪心EM算法。

1 相關(guān)工作

在EM算法和MapReduce的領(lǐng)域內(nèi),國內(nèi)外已經(jīng)有很多學(xué)者進行過深入的研究，因此本文基于EM算法和MapReduce的相關(guān)工作做進一步研究。

1.1 EM算法的相關(guān)工作

文獻[1]中提出了一種基于MapReduce的EM算法，通過MapReduce的并行化處理解決了傳統(tǒng)EM算法收斂速度隨著數(shù)據(jù)規(guī)模變大而減慢的問題，但存在初始模型數(shù)需要預(yù)先設(shè)定的問題。文獻[2]中通過使用牛頓法求解beta分布參數(shù)的算法，并提出一個合適的初值選擇算法，使得EM算法能夠有效地求解隱回歸模型的參數(shù)，但是對所有的分布都采用beta分布作為自變量的假設(shè)會帶來一定的偏差。文獻[3]中提出了一種基于密度檢測的EM算法，通過基于密度和距離的方法對初始值進行選擇，降低傳統(tǒng)EM算法的初始值選擇對收斂效果的影響，但算法性能仍需提高。文獻[4]中提出了一種快速、魯棒的有限高斯混合模型聚類算法，通過對模型成分混合系數(shù)及樣本所屬成分的概率系數(shù)施加熵懲罰算子的方法，使算法在很少的迭代次數(shù)內(nèi)收斂到確定值，但算法運行效率還需進一步提高。文獻[5]中提出了一種快速、貪心的高斯混合模型EM算法，通過采用貪心的策略以及對隱含參數(shù)設(shè)置適當(dāng)閾值的方法，使算法能快速收斂，并在很少的迭代次數(shù)內(nèi)獲取高斯混合模型的模型成分數(shù)，但是不能保證有噪聲數(shù)據(jù)集的聚類效果。

1.2 MapReduce的相關(guān)工作

文獻[6]中對Hadoop云平臺下的聚類算法進行了研究。文獻[7]中采用MapReduce編程模型，對特征選擇算法進行了研究。文獻[8]中提出了基于MapReduce模型的高效頻繁項集挖掘算法，利用MapReduce框架對Apriori算法進行了改進，提高了Apriori算法運行速度。文獻[9]中提出了一種基于MapReduce的Bagging決策樹算法，運用MapReduce框架對決策樹算法進行了并行化處理，提高了決策樹算法對大數(shù)據(jù)集的分析能力。文獻[10]中提出了一種基于MapReduce的文本聚類算法，運用MapReduce分布式框架對K-means算法進行了改進。文獻[11]中對MapReduce近年來在文本處理各個方面的應(yīng)用進行分類總結(jié)和處理，并對MapRedcue的系統(tǒng)和性能方面的研究做了一些介紹。文獻[12]中總結(jié)了近年來基于MapReduce編程模型的大數(shù)據(jù)處理平臺與算法的研究進展。文獻[13]中基于MapReduce計算框架，對傳統(tǒng)蟻群算法進行了改進，使得算法能夠快速有效地處理大規(guī)模數(shù)據(jù)集。

2 分布式貪心EM算法

2.1 貪心EM算法

貪心EM算法的關(guān)鍵是通過全局搜索將原始數(shù)據(jù)集初始化為一個僅含有一個模型分量的高斯混合模型，然后通過局部搜索逐漸增加新的模型分量到原有的高斯混合模型中，不斷更新混合模型分量的參數(shù)使得似然度最大。算法過程如下：

假設(shè)樣本集X={x1,x2,x3,…,xm}，并服從高斯混合分布，則高斯混合分布的概率密度函數(shù)fk(x)[14]為：

(1)

其中，xi是p維向量，Φj(xi;θj)是第j個高斯模型分量的概率密度，θj是它的參數(shù)，wj是第j個分量的混合系數(shù)，表示第j個高斯模型分量包含的樣本所占樣本總數(shù)的比例,k是高斯混合模型的模型成分數(shù)[15]。θj=(μj,Σj)，μj為高斯模型分量均值，Σj為高斯模型分量協(xié)方差矩陣。其中高斯分量概率密度Φj(xi;θj)表達式為：

(2)

此時將某一新分量δ(x;θ)加入一個已有k個分量的混合密度函數(shù)fk(x)，則生成的新的高斯混合模型密度函數(shù)如下式所示:

fk+1(x)=(1-α)fk(x)+αδ(x;θ)

(3)

其中，α是新增模型分量的混合系數(shù)，0<α<1。則新生成的對數(shù)似然函數(shù)為：

(4)

已知新的高斯混合模型包括混合模型分量和新增分量，而混合模型fk(x)已被設(shè)置為不變，所以貪心EM算法的核心就是優(yōu)化新增模型分量的混合系數(shù)α以及新增分量的參數(shù)，使新生成對數(shù)似然函數(shù)Lk+1最大化。所以，首先通過全局搜索找到一組新增分量的初始參數(shù)μ0、Σ0和α0。在α0處展開Lk+1的二階泰勒公式并且最大化關(guān)于α的二次函數(shù)得到似然函數(shù)的一個近似:

(5)

(6)

則Lk+1在α0=0.5附近的對數(shù)似然局部最優(yōu)可以寫成：

(7)

(8)

在求出新增模型分量估計值之后，通過傳統(tǒng)EM算法可得:

(9)

(10)

通過公式迭代獲取新增模型參數(shù)最優(yōu)解{αk+1,μk+1,Σk+1}，從而獲取新的高斯混合模型的對數(shù)似然函數(shù)值Lk+1。

2.2 分布式貪心EM算法

依據(jù)MapReduce的框架結(jié)構(gòu)，在設(shè)計分布式貪心EM算法時，首要的考慮便是定義Map函數(shù)和Reduce函數(shù)。算法過程如下：

(1)Mapper階段

(2)Reducer階段

步驟三：將所有節(jié)點得到的鍵值對進行整合，將高斯混合模型密度函數(shù)進行求和，然后再取對數(shù)，得到整合后的對數(shù)似然函數(shù)為：

(11)

步驟五:判斷滿足收斂條件的Fk是否滿足Fk+1≤Fk，如不滿足則重新進行步驟一，如果滿足則結(jié)束算法，輸出理想模型成分數(shù)k。

具體算法流程如下所示：

算法：分布式貪心EM算法

輸入：樣本集X={x1,x2,x3,…,xm}

輸出：高斯混合模型理想模型成分數(shù)k

1 將數(shù)據(jù)集平均分配到h個節(jié)點中

2 While(true)

3 對于每個節(jié)點：

4 初始化節(jié)點，設(shè)置迭代次數(shù)ε=1

9 ifλ<10-6，則收斂結(jié)束

10 else跳轉(zhuǎn)到步驟4，ε+1

11 end if

12 ifFk+1≤Fk，輸出理想模型成分數(shù)為k，break

13 else跳轉(zhuǎn)到步驟2。

14 end if

15 end while

本算法主要是在Map(映射)、Reduce(歸化)、判斷的過程中得到最優(yōu)的最大似然Fk，從而得到理想模型成分值k。

上述算法中，步驟1～7為Mapper階段，首先對每個節(jié)點初始化高斯混合模型參數(shù)，然后通過更新參數(shù)得到最新的高斯混合模型密度函數(shù)，最后將數(shù)據(jù)映射處理并生成相應(yīng)的鍵值對，并作為Reducer階段的輸入。步驟8～11為Reducer階段，此階段是將Mapper階段傳遞過來的鍵值對進行整合得到Fk，再利用判斷因子λ判斷是否滿足收斂條件，當(dāng)λ<10-6時，F(xiàn)k達到收斂值，迭代結(jié)束。步驟12～15，因為在對原高斯混合模型添加新模型分量的過程中，數(shù)據(jù)集的對數(shù)似然函數(shù)值呈逐漸增長的趨勢，所以當(dāng)高斯混合模型的對數(shù)似然函數(shù)取得最大值，即當(dāng)Fk+1≤Fk時，F(xiàn)k為收斂值，即為最優(yōu)解，則算法循環(huán)結(jié)束，k即為理想模型成分數(shù)。

算法復(fù)雜度分析如下：

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

3.1 實驗環(huán)境

整個實驗是在Hadoop平臺下進行的，所用的版本為Hadoop2.6.5。每臺主機系統(tǒng)使用的是Unbuntu14.04版本。建立的集群由1個主節(jié)點、4個從節(jié)點組成。所有節(jié)點的硬件設(shè)備為聯(lián)想主機，其中使用了主頻為3.3 GHz的Intel四核處理器，內(nèi)存為2 GB。

3.2 實驗數(shù)據(jù)

實驗數(shù)據(jù)來自UCI機器學(xué)習(xí)和知識發(fā)現(xiàn)研究中使用的大型數(shù)據(jù)集KDD數(shù)據(jù)庫存儲庫。其中第一組數(shù)據(jù)大小為0.6 GB，包含200個數(shù)據(jù)，模型成分數(shù)為9；第二組數(shù)據(jù)大小為1.4 GB，包含500個數(shù)據(jù)，模型成分數(shù)為9；第三組數(shù)據(jù)大小為2.0 GB，包含1 000個數(shù)據(jù)，模型成分數(shù)為15；第四組數(shù)據(jù)大小為3.2 GB，包含1 500個數(shù)據(jù)，模型成分數(shù)為15。

3.3 實驗結(jié)果及分析

3.3.1運行時間

將本文算法與傳統(tǒng)EM算法、貪心EM算法在求解高斯混合模型理想成分數(shù)的時間上作比較。固定節(jié)點個數(shù)為8個，分別使用本文算法、傳統(tǒng)EM算法、貪心算法對4組實驗試驗數(shù)據(jù)求解高斯混合模型的成分數(shù)，并進行時間對比，實驗結(jié)果如圖1所示。

圖1 算法運行時間比較圖

三種算法下對于第一組和第二組實驗輸出模型成分數(shù)都為9，第三組和第四組實驗輸出模型成分數(shù)都為15，輸出結(jié)果正確。由圖1可以看出，對于這4組實驗數(shù)據(jù)，本文算法相對于傳統(tǒng)EM算法以及貪心EM算法在處理數(shù)據(jù)集時運行時間大幅減少，當(dāng)數(shù)據(jù)規(guī)模更大時，速度優(yōu)勢更為明顯，同時可以看出，隨著數(shù)據(jù)集的變大，本文算法的運行時間基本呈線性增長，具有較好的數(shù)據(jù)可擴展性。

3.3.2系統(tǒng)的可擴展性

實驗二通過改變節(jié)點個數(shù)，設(shè)置節(jié)點數(shù)分別為2，4，6，8，觀察本文算法下求解4組數(shù)據(jù)的模型成分數(shù)的時間變化，實驗結(jié)果如圖2所示。

圖2 不同節(jié)點下算法運行時間

由圖2可以看出，隨著節(jié)點數(shù)的增加，本文算法運行時間逐漸減少，因此可以通過增加計算節(jié)點的個數(shù)來增加本算法運行速度。同時在數(shù)據(jù)集較小的時候，隨著節(jié)點數(shù)的增加，算法運行時間減少的幅度非常小，這是由于在小規(guī)模數(shù)據(jù)集下算法迭代計算的時間很小，時間大部分都花費在節(jié)點與節(jié)點之間的通信上。

4 結(jié)論

本文在貪心EM算法的基礎(chǔ)上，提出了一種基于MapReduce分布式框架的貪心EM算法，該算法在保證了無需預(yù)先指定初始模型成分數(shù)目并能準(zhǔn)確得到模型成分數(shù)的前提下，極大地提高了處理大數(shù)據(jù)集時的收斂速度。實驗結(jié)果與分析表明，本文算法較之傳統(tǒng)EM算法和貪心EM算法在處理大規(guī)模數(shù)據(jù)上有明顯的加速效果，并且隨著節(jié)點數(shù)的增加可以進一步提高收斂速度，并且具有很好的擴展性。實驗僅對求解高斯混合模型的模型成分數(shù)的時間進行了對比，并未對聚類的準(zhǔn)確度進行實驗，因此后續(xù)研究者可以就高斯混合模型聚類的準(zhǔn)確度作進一步研究。

[1] 胡愛娜. 基于MapReduce的分布式EM算法的研究與應(yīng)用[J]. 科技通報, 2013(6):68-70.

[2] 韓忠明, 呂濤, 張慧,等. 帶隱變量的回歸模型EM算法[J]. 計算機科學(xué), 2014, 41(2):136-140.

[3] 戴月明, 張朋, 吳定會. 基于密度檢測的EM算法[J]. 計算機應(yīng)用研究, 2016, 33(9):2697-2700.

[4] 胡慶輝, 丁立新, 陸玉靖,等. 一種快速、魯棒的有限高斯混合模型聚類算法[J]. 計算機科學(xué), 2013, 40(8):191-195.

[5] 邢長征, 苑聰. 一種快速、貪心的高斯混合模型EM算法研究[J]. 計算機工程與應(yīng)用, 2015, 51(20):111-115.

[6] 譚躍生, 楊寶光, 王靜宇,等. Hadoop云平臺下的聚類算法研究[J]. 計算機工程與設(shè)計, 2014, 35(5):1683-1687.

[7] 陸江, 李云. 基于MapReduce的特征選擇并行化研究[J]. 計算機科學(xué), 2015, 42(8):44-47.

[8] 朱坤, 黃瑞章, 張娜娜. 一種基于MapReduce模型的高效頻繁項集挖掘算法[J]. 計算機科學(xué), 2017, 44(7):31-37.

[9] 張元鳴, 陳苗, 陸佳煒,等. 基于MapReduce的Bagging決策樹優(yōu)化算法[J]. 計算機工程與科學(xué), 2017, 39(5):841-848.

[10] 李釗, 李曉, 王春梅,等. 一種基于MapReduce的文本聚類方法研究[J]. 計算機科學(xué), 2016, 43(1):246-250.

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

[12] 宋杰, 孫宗哲, 毛克明,等. MapReduce大數(shù)據(jù)處理平臺與算法研究進展[J]. 軟件學(xué)報, 2017, 28(3):514-543.

[13] 凌海峰, 劉超超. 基于MapReduce框架的并行蟻群優(yōu)化聚類算法[J]. 計算機工程, 2015, 41(8):168-173.

[14] 馬江洪，葛詠，圖像線狀模式的有限混合模型及其EM算法[J].計算機學(xué)報,2007,30(2):288-296.

[15] 李斌，鐘潤添，王先基，等. 一種基于遞增估計GMM的連續(xù)優(yōu)化算法[J].計算機學(xué)報，2007，30(6):979-985.