郭晨晨，朱紅康

(山西師范大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，山西 臨汾 041000)

?

基于Hadoop MapReduce和粗粒度并行遺傳算法的大數(shù)據(jù)聚類方法改進(jìn)

郭晨晨，朱紅康*

(山西師范大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，山西 臨汾 041000)

為了提高并行遺傳算法在大數(shù)據(jù)聚類問題中的時間效率，通過利用粗粒度遺傳算法的并行化思想，提出了Hadoop平臺上基于MapReduce計算框架的粗粒度遺傳算法的并行化設(shè)計。該思想主要來源于大數(shù)據(jù)體量龐大的特點，聚類算法時間消耗巨大。并行是解決算力不足的一個較為有效的方法，實驗結(jié)果表明，并行化的遺傳算法在處理大數(shù)據(jù)聚類時相比傳統(tǒng)的串行化處理在時間消耗方面有明顯的降低。

大數(shù)據(jù);聚類;MapReduce;數(shù)據(jù)挖掘;并行;粗粒度遺傳算法

聚類[1]作為數(shù)據(jù)挖掘領(lǐng)域的一種重要的方法和手段已在各領(lǐng)域廣泛應(yīng)用。但大數(shù)據(jù)時代的到來給許多原有技術(shù)在實現(xiàn)層面上帶來了很多新的挑戰(zhàn)。為應(yīng)對這些挑戰(zhàn)，出現(xiàn)了很多關(guān)于大數(shù)據(jù)聚類方面的研究。文獻(xiàn)[2]將遺傳算法引入到聚類算法中使得聚類效果明顯優(yōu)于K-means算法；文獻(xiàn)[3]是傳統(tǒng)的遺傳算法與“爬山法”相結(jié)合形成一種混合型聚類算法，以此提高尋優(yōu)速率；文獻(xiàn)[4]將聚類融合引入到遺傳算法的交叉算子中，有效地縮小了算法的探索空間，加快了算法的收斂速度；文獻(xiàn)[5]使用最大屬性值范圍劃分法克服聚類算法對初始值的敏感性,并運(yùn)用兩階段的動態(tài)選擇和變異策略，先進(jìn)行不同聚類數(shù)目的并行搜索,再獲取最優(yōu)的聚類中心。由此可見，將遺傳算法加入到聚類算法中可明顯提高其聚類性能。但串行的算法會造成大量的時間消耗，在實際的應(yīng)用過程中產(chǎn)生諸多不利的影響。由此，產(chǎn)生傳統(tǒng)的并行化技術(shù)。基于MPI的并行化設(shè)計[6]使得計算節(jié)點間的通信需要較多的時間來完成?；谶@樣的缺點，使用MapReduce[7]并行化計算框架在處理大數(shù)據(jù)聚類問題時，節(jié)點間的通信時長會降低。文獻(xiàn)[8-9]是最近通過MapReduce并行處理一些經(jīng)典聚類算法的研究。本文將大數(shù)據(jù)聚類過程分為兩個階段，分別對應(yīng)MapReduce計算框架的Map階段和Reduce階段，犧牲少量聚類正確率換取大量算力的提升。

1　傳統(tǒng)遺傳算法和并行遺傳算法

圖1　遺傳算法基本流程Fig.1　Basic process of genetic algorithm

遺傳算法的靈感來源于大自然的客觀規(guī)律。通過模擬生物進(jìn)化機(jī)制中染色體的交叉、變異、選擇和繼承達(dá)到個體的不斷優(yōu)化，這種啟發(fā)式的算法用于解決基于搜索和優(yōu)化的問題。遺傳算法在其整個運(yùn)行過程中的遺傳操作具有隨機(jī)性，但并不代表遺傳算法是完全隨機(jī)搜索的。因為該算法能利用過去有效的信息來預(yù)測進(jìn)化形成的下一代期望性能有所提升的尋優(yōu)點集。重復(fù)這樣的迭代過程，一代一代的進(jìn)化，最后收斂于所期望出現(xiàn)的最適應(yīng)環(huán)境的個體上，進(jìn)而尋找到最優(yōu)解。遺傳算法的基本流程見圖1。

并行遺傳算法是在傳統(tǒng)的遺傳算法中加入并行化的設(shè)計，該技術(shù)的實現(xiàn)主要基于以下幾個方面工作取得的成就[10-12]：①主從式并行遺傳算法；②細(xì)粒度并行遺傳算法；③粗粒度并行遺傳算法。

主從并行遺傳算法在主處理器執(zhí)行選擇、交叉、變異等操作，操作對象是全部個體。每個個體的適應(yīng)值計算則分配給從處理器并行處理。細(xì)粒度并行遺傳算法整體結(jié)構(gòu)框架與大規(guī)模并行計算機(jī)體系結(jié)構(gòu)相適應(yīng)，操作對象針對于符合特定空間結(jié)構(gòu)模式的單一個體而非全部個體，具有保持種群多樣性、避免早熟等特點。粗粒度并行遺傳算法結(jié)構(gòu)相比于前兩個較為復(fù)雜，一般包含有多個種群，子群通過某種方式交換個體，從而達(dá)到每個子種群中的最優(yōu)化組合。該算法具有較好的全局搜索能力和局部的快速搜索能力，在過去的研究中常常使用單臺計算機(jī)串行地實現(xiàn)該算法，而本文則使用多臺計算機(jī)并行執(zhí)行，進(jìn)一步提高運(yùn)算速度。

2　MapReduce

MapReduce是一種編程模型，也是一種計算框架，用于大規(guī)模數(shù)據(jù)集的并行運(yùn)算。它是建立在大規(guī)模數(shù)據(jù)的分布式集群之上。每次輸入數(shù)據(jù)是分布式文件系統(tǒng)中(Distributed File System)的一個或多個文件塊，這是由于Hadoop將數(shù)據(jù)給到Map進(jìn)行處理之前會使用InputFormat對數(shù)據(jù)進(jìn)行兩方面的預(yù)處理：①對輸入數(shù)據(jù)進(jìn)行切分，生成一組Split，一個Split會分發(fā)給一個Mapper進(jìn)行處理;②針對每個Split，調(diào)用RecordReader讀取Split內(nèi)的數(shù)據(jù)，并按照的形式組織成一條Record傳給Map函數(shù)進(jìn)行處理。

對于生成的鍵-值對，需要經(jīng)過兩個階段的處理，這兩個階段包括Map階段和Reduce階段。

Map階段：Mapper接收通過RecordReader得到的鍵-值對，Mapper運(yùn)用分布式算法處理鍵-值對并且為每一個Reduce任務(wù)建立一個中間文件。

Reduce階段：Reduce函數(shù)的輸入?yún)?shù)是鍵及其關(guān)聯(lián)值表組成的對，將Reduce函數(shù)應(yīng)用到單鍵稱為一個Reducer,對Map階段傳來每一個中間文件進(jìn)行并行處理，合并產(chǎn)生最終輸出數(shù)據(jù)。

MapReduce計算框架見圖2。

圖2　MapReduce計算框架Fig.2　Calculation model of MapReduce

2.1基于MapRuduce的并行遺傳聚類算法的實現(xiàn)

該方法是根據(jù)粗粒度并行遺傳算法的基礎(chǔ)上進(jìn)行的改進(jìn)，該方法成功的關(guān)鍵在于Map和Ruduce兩個階段的聚類。開始，系統(tǒng)調(diào)用Input Format類將輸入數(shù)據(jù)集分成一定大小的文件塊(split)，每一個Split被一個Mapper處理并完成第一階段的聚類。將第一階段產(chǎn)生的數(shù)據(jù)均交給單個Reducer進(jìn)行處理并完成第二階段的聚類。用若干Mapper和單個Reducer可執(zhí)行該算法，具體模型見圖3。

圖3　MapReduce改進(jìn)計算模型Fig.3　Improved computational model of MapReduce

2.2第一聚類階段

1)種群初始化 ：每個Mapper通過接收Split形成種群的初始化個體。每個個體是大小為N的染色體，每一個染色體中包含一個質(zhì)心，質(zhì)心是從接收的Split數(shù)據(jù)點中隨機(jī)選擇的。對每個染色體中的數(shù)據(jù)點進(jìn)行聚類，將數(shù)據(jù)點分配給擁有最近質(zhì)心的簇。

2)適應(yīng)值評估。

3)通過Davies-bouldin指標(biāo)[12]對每個個體的適應(yīng)值進(jìn)行計算。

Davies-bouldin是用于衡量聚類效果的一種方法，該方法定義一個離散度參數(shù)Si，表示第i個類中數(shù)據(jù)點的離散程度。定義如下：

(1)

式中Ti為第i類中數(shù)據(jù)點的個數(shù)；Xi為第i類中第j個數(shù)據(jù)點；Ai為第i類的質(zhì)心(聚類中心)，當(dāng)q=2時，可利用公式求歐式距離。

兩個聚類質(zhì)心間的距離用Mij表示，公式如下：

(2)

式中ai,j為第i類質(zhì)心的第j個屬性。

DBI還定義了一個相似度參數(shù)Ri,j，用來評估第i類與第j類的相似度，公式如下：

(3)

最后得到DBI指數(shù)：

(4)

4)采用交叉和變異技術(shù)對染色體進(jìn)行處理，需要注意的是后代的質(zhì)心是父母相應(yīng)質(zhì)心的算術(shù)平均值。

5)對于染色體的選擇，采用聯(lián)賽選擇算法[14]對進(jìn)化的下一代進(jìn)行選擇，通過聯(lián)賽選擇算法，N個體競爭產(chǎn)生下一代，根據(jù)優(yōu)勝劣汰原則，隨機(jī)挑選N個競爭者，在交配池中競爭每一位基因遺傳，適應(yīng)性最好的將獲得該基因的遺傳權(quán)。

6)第一階段的結(jié)束階段：舊種群被新種群取代，而新種群被更新的種群取代，取代過程伴隨著交叉、變異、選擇等過程。這樣一代一代的更替，直到達(dá)到終止條件結(jié)束。迭代完成得到的“最適應(yīng)種群”交由Reducer處理，從而進(jìn)入第二聚類階段。

2.3第二聚類階段

1)Reducer接收來自所有Mapper的染色體并組合成一條新的染色體。

2)新梁色體中的多個類的那些質(zhì)心間距小于指定閾值的聚類要合并為一個類。合并產(chǎn)生的新的質(zhì)心為原來質(zhì)心的算術(shù)平均值。閾值的計算公式如下：

式中T為閾值；Mi,j為聚類i和聚類j之間的距離；Di和Dj分別為i類和j類中距離各自質(zhì)心距離最遠(yuǎn)點；0.2距離比例系數(shù)由反復(fù)試驗得到。

3)重復(fù)上述過程，直至染色體中所有聚類的質(zhì)心間距有一個大于指定閾值，迭代結(jié)束。

4)最后染色體獲得最佳聚類中心的位置。

3　性能評估

用本文所提方法與傳統(tǒng)串行遺傳算法進(jìn)行比較。采用5臺普通的計算機(jī)搭建Hadoop集群系統(tǒng)來評估本文方法的性能，具體配置見表1。運(yùn)行迭代算法的單節(jié)點處理器配置見表2。

必要的參數(shù)設(shè)定如下: 交叉概率pc=6%； 變異概率pm=0.25%； 迭代運(yùn)算次數(shù)500次； 為每個聚類分配5個Node。

軟件環(huán)境如下： 軟件平臺：Hadoop-1.2.1。 硬件平臺：VMware Workstation虛擬機(jī)上運(yùn)行的Ubuntu16.04系統(tǒng)，分配運(yùn)行內(nèi)存2 G、硬盤200 G。

為了客觀地評價本方法的性能，將聚類正確率的高低和消耗時間的多少作為評判標(biāo)準(zhǔn)，使用系統(tǒng)時鐘測量執(zhí)行時間。測試數(shù)據(jù)集選用Europe map坐標(biāo)數(shù)據(jù)集，該數(shù)據(jù)集包含169 308個實例。

將傳統(tǒng)串行方法設(shè)定為100%，實驗可見，聚類算法的運(yùn)算速度提高了80%，聚類正確率僅下降8%。

表1　實驗硬件配置

表2　單節(jié)點處理器硬件配置

4　結(jié)　論

將MapReduce計算框架融入到聚類中，利用并行遺傳算法相比傳統(tǒng)經(jīng)典聚類算法的性能優(yōu)勢，在損失少量聚類準(zhǔn)確度的情況下，極大提高了算法整體的運(yùn)行速度，更有利于理論在實際中的應(yīng)用。未來的工作將對閾值公式中距離比例系數(shù)做出適當(dāng)?shù)恼{(diào)整，盡量減少經(jīng)驗因素的影響。

[1]Jain A K. Data clustering: 50 years beyond K-means[J].Pattern Recognition Letters, 2010,31(8):651-666.

[2]傅景廣,許剛,王裕國.基于遺傳算法的聚類分析[J].計算機(jī)工程，2004，30(4):122-124.

[3]張婧,楊炳儒.基于混合遺傳算法的聚類模式數(shù)據(jù)挖掘方法[J].微計算機(jī)信息，2006,22(6)：219-221.

[4]何東曉,周栩,王佐,等.復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘—基于聚類融合的遺傳算法[J].自動化學(xué)報，2010，36(8)：1160-1170.

[5]何宏,譚永紅.一種基于動態(tài)遺傳算法的聚類新方法[J].電子學(xué)報，2012，40(2)：254-259.

[6]劉曉平,安竹林,鄭利平.基于 MPI 的主從式并行遺傳算法框架[J].系統(tǒng)仿真學(xué)報，2004，16(9):1938-1940.

[7]劉向東,劉奎,胡飛翔,等.基于MapReduce的并行聚類算法設(shè)計與實現(xiàn)[J].計算機(jī)應(yīng)用與軟件，2014，31(11):251-256.

[8]賈瑞玉,管玉勇,李亞龍.基于MapReduce模型的并行遺傳k-means聚類算法[J].計算機(jī)工程與設(shè)計，2014，35(2)：657-660.

[9]李蘭英,董義明,孔銀,等.改進(jìn)K-means算法的MapReduce并行化研究[J].哈爾濱理工大學(xué)學(xué)報，2016，21(1):31-35.

[10] 李建明,遲忠先,萬單領(lǐng).一種基于GPU加速細(xì)粒度并行遺傳算法的實現(xiàn)方法[J].控制與決策，2008，23(6):697-700.

[11] 程興國,肖南峰.粗粒度并行遺傳算法的MapReduce并行化實現(xiàn)[J].重慶理工大學(xué)學(xué)報，2013，27(10)：66-70.

[12] 劉正龍，楊艷梅，羅玉軍.基于遺傳算法的非線性系統(tǒng)辯識的研究[J].黑龍江大學(xué)自然科學(xué)學(xué)報，2014，31(3)：416-420.

[13] Davies D L,Bouldin D W.A cluster separation measure[C].IEEE Trans.Pattern Anal.Mach.Intelligence，1979，1:224-227.

[14] Xia G M，Zeng J C.Stochastic particle swarm optimization algorithm based on genetic algorithm of tournament selection[J].Computer Engineering & Applications，2007，43(4):51-84.

Improvement of large data clustering method based on Hadoop MapReduce and coarse grain parallel genetic algorithm

GUO Chen-Chen,ZHU Hong-Kang*

(Schoolofmathematicsandcomputerscience,ShanxiNormalUniversity,Linfen041000,China)

Parallel design of coarse grain genetic algorithm based on MapReduce computing framework is proposed in the Hadoop to improve the time efficiency of parallel genetic algorithm in large data clustering,by using the idea of parallel genetic algorithm.This idea is mainly derived from the huge amount of large data, a huge amount of time consumption of clustering algorithm.Parallelism is the solution to the lack of a more effective method. Experimental results show that parallel genetic algorithm in dealing with large data clustering compared to the traditional serial processing in time consumption has decreased significantly.

large data;clustering;MapReduce;data mining;parallel;coarse-grain genetic algorithm

10.13524/j.2095-008x.2016.03.047

2016-05-27;

2016-07-07

山西省自然科學(xué)基金資助項目(2015011040)

郭晨晨(1992-)，男，山西長治人，碩士研究生，研究方向：計算機(jī)應(yīng)用，E-mail:1341290300@qq.com；*通訊作者：朱紅康(1975-)，男，山西汾西人，副教授，博士，碩士研究生導(dǎo)師，研究方向：數(shù)據(jù)挖掘，E-mail:zhuhkyx@126.com。

TP18

A

2095-008X(2016)03-0087-05