基于MapReduce的GEP_K均值聚類算法

古凌嵐

（廣東輕工職業(yè)技術(shù)學(xué)院計算機(jī)工程系，廣州　510300）

基于MapReduce的GEP_K均值聚類算法

古凌嵐

（廣東輕工職業(yè)技術(shù)學(xué)院計算機(jī)工程系，廣州510300）

0　引言

K均值算法是一種簡單有效的聚類分析方法，但存在k值難以確定、易陷入局部最優(yōu)和大數(shù)據(jù)量效率低等問題［1］，在實(shí)際應(yīng)用中有一定的局限性?；虮磉_(dá)式編程（Gene Expression Programming，GEP）是借鑒生物選擇和進(jìn)化機(jī)制發(fā)展起來的一種通用的、簡單高效的隨機(jī)搜索算法，具有全局尋優(yōu)能力，能夠在缺乏先驗(yàn)知識的情況下，自動挖掘數(shù)據(jù)間隱含的關(guān)系。將GEP引入K均值算法，可以克服其初始值敏感、易陷入局部最優(yōu)的缺陷。文獻(xiàn)［2，3］將GEP的全局尋優(yōu)能力與K均值的局部搜索能力相結(jié)合，提出了GEP_K均值自動聚類算法。該算法無需事先確定K值，且在收斂速度和尋優(yōu)精度上都有較大的提高，但計算效率較低，主要表現(xiàn)在從染色體生成聚類中心時表達(dá)式樹（ET）的構(gòu)建和遍歷的時空復(fù)雜度高，適應(yīng)度評價中各數(shù)據(jù)點(diǎn)到簇中心距離的計算環(huán)節(jié)較為耗時，隨著問題規(guī)模的不斷擴(kuò)大，時間和空間上的消耗將會明顯增加，導(dǎo)致算法的處理效率大幅下降。

MapReduce是一種簡化的分布式編程模型和高效的任務(wù)調(diào)度模型［4］。它通過Map（映射）過程先對已分割成相互獨(dú)立的數(shù)據(jù)塊高度并行處理，再經(jīng)Reduce（歸并）匯集整理形成結(jié)果。使得用戶編寫的程序可在由普通機(jī)器組成的大規(guī)模集群上運(yùn)行，且執(zhí)行性能高。現(xiàn)已有研究用MapReduce設(shè)計實(shí)現(xiàn)進(jìn)化算法和K均值的并行化，如文獻(xiàn)［5］基于MapReduce框架實(shí)現(xiàn)遺傳算法（Genetic Algorithms，GA）的并行化，提高了進(jìn)化效率。文獻(xiàn)［6］將MapReduce與GA結(jié)合，提出了適合于大規(guī)模變量的并行遺傳算法，得到了較好的加速比。文獻(xiàn)［7］用實(shí)驗(yàn)驗(yàn)證了在MapReduce框架下實(shí)現(xiàn)的K均值算法，能夠?qū)崿F(xiàn)大規(guī)模數(shù)據(jù)的有效聚類，且算法效率也得到了明顯提高。這些成果為改善算法的效率提供了有用的借鑒和參考。

本文提出了基于MapReduce的基因表達(dá)式編程K均值聚類算法（MRGEP_K均值）。首先，提出一種快速操作染色體生成聚類中心的方法，無需構(gòu)建和遍歷ET樹，借助線性數(shù)據(jù)結(jié)構(gòu)即可完成；其次，利用MapReduce編程模型，設(shè)計實(shí)現(xiàn)適應(yīng)度評價并行化；最后，在Hadoop平臺上對于UCI和人工數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，以驗(yàn)證算法在處理效率上的提升。

1　MRGEP_K均值聚類算法

GEP_K均值算法［2-3］的主要步驟為：隨機(jī)生成初始種群；GEP染色體編碼/解碼生成可能的簇中心；計算個體適應(yīng)度；遺傳操作進(jìn)化種群。重復(fù)上述步驟直到達(dá)到迭代次數(shù)。本文利用MapReduce框架優(yōu)化GEP_K均值算法（MRGEP_K均值）的基本思路是：采用直接操作基因的方法，完成GEP染色體基因的表達(dá)求解計算，得到可能的簇中心點(diǎn)，避免構(gòu)建聚類ET樹（編碼）和多次遍歷聚類ET樹（解碼）的繁復(fù)操作；利用Map和Reduce任務(wù)實(shí)現(xiàn)各數(shù)據(jù)點(diǎn)到各簇中心距離計算過程的并行化，完成適應(yīng)度評價，提高計算效率，以適應(yīng)處理大規(guī)模數(shù)據(jù)的需要。MRGEP_K均值算法流程如圖1所示。

圖1　MRGEP_K均值算法的并行實(shí)現(xiàn)流程

1.1染色體基因表達(dá)求解方法的改進(jìn)

構(gòu)建和遍歷聚類ET樹的目的是實(shí)現(xiàn)簇的合并與分割［2-3］，若能從基因結(jié)構(gòu)中發(fā)現(xiàn)聚類運(yùn)算符（F）節(jié)點(diǎn)及其操作對象（T）節(jié)點(diǎn)，就可實(shí)現(xiàn)相應(yīng)的簇合并與分割。因此，本文引入動態(tài)數(shù)組arrayList1、arrayList2，利用arrayList1存放基因元素，arrayList2存放參與合并操作的節(jié)點(diǎn)位置編號序列，通過對兩個數(shù)組各遍歷一次，完成簇的合并與分割，得到聚類簇的中心點(diǎn)。算法步驟為：

Reduce階段

（1）讀取染色體R＝f1f2…fhx1x2…xt，其中fi∈F，xi∈T，F(xiàn)=｛f|f為聚類運(yùn)算符∪和∩｝，∪為分割，∩為合并，T= ｛x|x為數(shù)據(jù)點(diǎn)｝，存入arrayList1，初始化變量r=2，由r定位F節(jié)點(diǎn)的第一個操作節(jié)點(diǎn)的位置，初始化arrayList2，并定義輔助數(shù)組arrayList3保存所生成的聚類中心點(diǎn)。

（2）從前向后遍歷arrayList1，每次讀取元素ei、er+1和er+2的位置編號，即運(yùn)算符節(jié)點(diǎn)及其操作對象節(jié)點(diǎn)的位置，在arrayList2查找是否存在包含序號i的元素，若存在則用r+1，r+2替換之，否則①當(dāng)編號i對應(yīng)∩運(yùn)算符時，則將 ei、er+1和 er+2的位置編號序列加入 arrayList2；②當(dāng)編號i對應(yīng)∪運(yùn)算符，且r+1，r+2對應(yīng)的元素均為T時，則將r+1，r+2對應(yīng)的T節(jié)點(diǎn)加入arrayList3，實(shí)現(xiàn)簇分割。然后設(shè)置r=r+2以定位i+1個F節(jié)點(diǎn)的第一個操作節(jié)點(diǎn)的位置，直到i=h，h為基因頭部長度，從而得到一（多）組參與合并操作的節(jié)點(diǎn)的位置編號序列。

（3）從前向后遍歷arrayList2，對于每個元素中的位置編號序列，計算對應(yīng)的T節(jié)點(diǎn)均值，并加入arrayList3，實(shí)現(xiàn)簇的合并。

（4）將簇中心點(diǎn)寫入聚類中心信息文件。

由于T類元素是操作對象，必然是聚類ET樹中的葉子節(jié)點(diǎn)，因而，②只需遍歷前h個F節(jié)點(diǎn)即可。圖2是實(shí)現(xiàn)簇的合并與分割的示意圖。圖2（a）i=1，其子節(jié)點(diǎn)為序號2，3的F節(jié)點(diǎn)，因arrayList2無元素，到達(dá)圖2 （b）i=2的節(jié)點(diǎn)為∩，將序號2，4，5加入arrayList2，圖2 （c）i=3的節(jié)點(diǎn)為∪，且其節(jié)點(diǎn)為T，將x1、x2加入arrayList3，實(shí)現(xiàn)簇的分割，圖2（d）i=4的節(jié)點(diǎn)為∩，用序號8，9替換arrayList2中的序號4，類似地圖2（d）序號5被替換，圖2（f）遍歷arrayList2，得到序號2對應(yīng)T節(jié)點(diǎn)（序號8、9、10、11）的均值，實(shí)現(xiàn)簇的合并。

1.2適應(yīng)度評價的并行化

Map階段完成各數(shù)據(jù)點(diǎn)到簇中心的距離，以及簇劃分。map函數(shù)輸出中間結(jié)果＜key，value＞對的形式為＜個體號，數(shù)據(jù)點(diǎn)信息＞，value包括中心點(diǎn)號、數(shù)據(jù)對象、到簇中心的最小距離；Reduce階段完成個體適應(yīng)度的計算。reduce函數(shù)輸出結(jié)果＜key，value＞對的形式為確良＜個體號，適應(yīng)度＞，保存在適應(yīng)度值信息文件中。算法步驟：

Map階段

①加載從Job1得到的k個聚類中心C，接收分塊數(shù)據(jù)集D；

②計算每個數(shù)據(jù)點(diǎn)Dj與C1，C2，…，Ck的距離Dist （j，1），Dist（j，2），…，Dist（j，k）；

③將數(shù)據(jù)點(diǎn)Dj劃分到Distmin（j，i）對應(yīng)的簇i中；

④輸出聚類簇劃分，及各點(diǎn)到其簇中心最小距離。

Reduce階段

①接收Map階段的聚類劃分，及各點(diǎn)到其簇中心最小距離；

③輸出適應(yīng)度f。

圖2　染色體基因表達(dá)求解示意圖

1.3遺傳操作的實(shí)現(xiàn)

Reduce階段加載Job2得到的個體適應(yīng)度值，對種群進(jìn)行進(jìn)化操作，生成新一代種群。輸出結(jié)果＜key，value＞對的形式為＜個體號，個體信息＞，更新種群信息文件。該步無Map。

Reduce階段

①讀取種群信息文件和個體適應(yīng)度值信息文件；

②保留最優(yōu)個體；

③按照一定策略進(jìn)行選擇、交叉和變異操作；

④輸出新種群。

1.4算法的復(fù)雜度分析

GEP_K均值的時間復(fù)雜度為O（mks+ts），m為樣本數(shù)，k為分類數(shù)，s為迭代次數(shù)，t為染色體基因長度，空間復(fù)雜度O（t+1），MRGEP_K均值算法利用線性數(shù)據(jù)結(jié)構(gòu)，完成基因的表達(dá)求解，無需動態(tài)開辟和維護(hù)額外空間，空間復(fù)雜度為O（1），串行執(zhí)行的時間復(fù)雜度為O （mks+hs），h為基因頭部長度，在MapReduce框架下，數(shù)據(jù)點(diǎn)到各簇中心距離的計算被分散到多個Mapper節(jié)點(diǎn)并行處理，當(dāng)節(jié)點(diǎn)數(shù)為n時，時間復(fù)雜度為O（mks/ n+hs），計算時間復(fù)雜度大幅降低，隨著集群規(guī)模的增大，運(yùn)行效率會有更明顯的提高。

2　實(shí)驗(yàn)結(jié)果與分析

2.1實(shí)驗(yàn)環(huán)境、數(shù)據(jù)集和評價指標(biāo)

實(shí)驗(yàn)環(huán)境為Hadoop平臺，由7臺普通PC構(gòu)成，其中1臺為主節(jié)點(diǎn)，另6臺為從節(jié)點(diǎn)，硬件配置為Intel Core i3 CPU，4GB RAM，軟件配置為Java1.6和Hadoop 1.2.1。算法的基本參數(shù)設(shè)置為種群規(guī)模N=40，交叉概率Pc=0.77，變異概率Pm=0.05，迭代次數(shù)t＝50。測試數(shù)據(jù)采用UCI的3個數(shù)據(jù)集（見表1），其中Iris是測試無監(jiān)督聚類方法效果的典型數(shù)據(jù)集。另外，為了進(jìn)一步驗(yàn)證算法的并行性能，將Iris擴(kuò)展為10維樣本數(shù)5×105、1× 106、2×106的3個數(shù)據(jù)集DW1、DW2、DW3，規(guī)模分別為20M、50M、100M。

表1　實(shí)驗(yàn)樣本數(shù)據(jù)集

對于算法的計算效率，本文通過運(yùn)行時間和占用內(nèi)存進(jìn)行評價。對于算法的并行性能，則采用加速比和可擴(kuò)展性來衡量。

2.2實(shí)驗(yàn)結(jié)果分析

（1）改進(jìn)的基因表達(dá)求解方法性能分析

通過兩組實(shí)驗(yàn)，對GEP_K均值（算法1）、MRGEP _K均值 （算法2）中基因表達(dá)求解方法的性能進(jìn)行比較，隨機(jī)產(chǎn)生測試基因，對于每組參數(shù)，進(jìn)行10次實(shí)驗(yàn)，結(jié)果取平均值。第一組，測試當(dāng)基因長度變化時，算法執(zhí)行時間變化情況，設(shè)置N=1000，h為10～60的6組參數(shù)；第二組，測試當(dāng)種群規(guī)模增長時，算法運(yùn)行時間和內(nèi)存占用情況的變化，設(shè)置h=20，N為10000-60000 的6組參數(shù)。兩組實(shí)驗(yàn)的運(yùn)行結(jié)果如表2所示。

表2　基因表達(dá)求解方法性能分析實(shí)驗(yàn)結(jié)果

由實(shí)驗(yàn)結(jié)果可知，無論是基因長度增長，還是種群規(guī)模擴(kuò)大，算法2的運(yùn)行時間都遠(yuǎn)遠(yuǎn)小于算法1，前者僅為后者的1/3～1/4；在內(nèi)存占用方面，算法1內(nèi)存消耗是算法2的4倍以上，同時隨著種群規(guī)模的增長，算法1內(nèi)存消耗明顯增加，當(dāng)N＝60000時，內(nèi)存溢出，而算法2的內(nèi)存消耗基本不變。由此可見，在運(yùn)行時間開銷上算法2比算法1提高了3～4倍，且沒有額外的空間開銷。

（2）并行MRGEP_K均值的有效性分析

對于表1中3個數(shù)據(jù)集，采用串行MRGEP_K均值和并行MRGEP_K均值（單機(jī)處理）分別運(yùn)行20次，得到的結(jié)果平均值如表3所示。

表3　有效性分析實(shí)驗(yàn)結(jié)果

由表3可知，就執(zhí)行時間而言，并行MRGEP_K均值時間明顯較長，原因是MapReduce操作啟動map和reduce任務(wù)的時間代價較大，因而，單個運(yùn)算節(jié)點(diǎn)MapReduce處理小數(shù)據(jù)量，不具優(yōu)勢，但它與其串行算法的聚類效果較為一致，實(shí)驗(yàn)結(jié)果數(shù)據(jù)非常接近，說明并行MapReduce框架并未影響算法的聚類質(zhì)量。

（3）并行混合聚類算法的加速比分析

加速比反映了算法的并行性使運(yùn)行時間減少所獲得的性能提升，其計算公式為S=Ts/Tp，其中Ts、Tp分別表示串行和并行算法計算所消耗的時間。采用DW1、DW2、DW3數(shù)據(jù)集，分別選擇1、2、4、6個運(yùn)算節(jié)點(diǎn)參與計算，T為30次，進(jìn)行多次測試，算法的平均運(yùn)行時間與節(jié)點(diǎn)數(shù)的關(guān)系如圖3所示，對應(yīng)的加速比結(jié)果如圖4所示。由實(shí)驗(yàn)數(shù)據(jù)可知，隨著集群中計算機(jī)節(jié)點(diǎn)的增加，平均運(yùn)行時間不斷降低，降幅逐步減少，表明算法具有較好的加速比，能夠明顯提高數(shù)據(jù)的處理能力，但節(jié)點(diǎn)數(shù)增加的同時，也會增多節(jié)點(diǎn)間通信消耗；隨著數(shù)據(jù)集規(guī)模的擴(kuò)大，加速比也隨之增加，則說明算法對于大規(guī)模數(shù)據(jù)的處理效率更高。

圖3　運(yùn)行時間與節(jié)點(diǎn)數(shù)關(guān)系

圖4　加速比實(shí)驗(yàn)結(jié)果

（4）并行MRGEP_K均值算法的可擴(kuò)展性分析

可擴(kuò)展性是指并行算法有效利用集群中運(yùn)算節(jié)點(diǎn)增加的能力，其計算公式為E=S/P，其中S為加速比，P為集群節(jié)點(diǎn)數(shù)。分別選擇2、4、6個運(yùn)算節(jié)點(diǎn)，以及不同規(guī)模的DW1、DW2和DW3數(shù)據(jù)集，計算并行效率。計算結(jié)果如圖5所示。計算結(jié)果表明，對于較大的數(shù)據(jù)集，其并行效率更高，最高達(dá)到0.86；當(dāng)數(shù)據(jù)規(guī)模和節(jié)點(diǎn)數(shù)都增加時，并行處理能力穩(wěn)定，表現(xiàn)出較好的可擴(kuò)展性。

圖5　可擴(kuò)展性實(shí)驗(yàn)結(jié)果

3　結(jié)語

本文采用MapReduce并行編程模型，實(shí)現(xiàn)適應(yīng)度評價的并行化，借助線性數(shù)據(jù)結(jié)構(gòu)改善基因表達(dá)求解環(huán)節(jié)的計算復(fù)雜度，構(gòu)建了基于MapReduce的GEP_K均值聚類算法。實(shí)驗(yàn)結(jié)果表明，本文算法與GEP_K均值相比，迭代處理的時間明顯減少，尤其是較大規(guī)模的數(shù)據(jù)集，運(yùn)行效率的提高更為明顯。對于高維數(shù)據(jù)集，采用歐氏距離函數(shù)作為聚類準(zhǔn)則，很難度量數(shù)據(jù)對象間的相似性，優(yōu)化聚類準(zhǔn)則提高聚類質(zhì)量將是下一步研究工作的重點(diǎn)。

［1］孫吉貴，劉杰，趙連宇.聚類算法的研究［J］.軟件學(xué)報，2008，19（1）：49-60.

［2］陳瑜，唐常杰，葉尚玉，等.基于基因表達(dá)式編程的自動聚類方法［J］.四川大學(xué)學(xué)報：工程科學(xué)版，2007，39（2）：107-112.

［3］姜代紅，張三友.基于基因表達(dá)式編程的K均值自動聚類算法［J］.計算機(jī)仿真，2010，27（12）：216-219.

［4］李成華，張新訪，金海，等.MapReduce：新型的分布式并行計算編程模型［J］.計算機(jī)工程與科學(xué)，2011，33（3）：129-135.

［5］VERMA A，LLORA X，GOLDBERG D E，et al.Scaling genetic algorithms using MapReduce［C］//ISDA'09：Intelligent Systems Design and Applications，2009 9th International Conference on.IEEE，2009：13-18.

［6］李東，潘志松.一種適用于大規(guī)模變量的并行遺傳算法研究［J］.計算機(jī)科學(xué)，2012，39（7）：182-184.

［7］AMRESH K，KIRAN M，B.R.PRATHAP.Verification and validation of MapReduce program model for parallel K-means algorithm on Hadoop cluster［C］//2013 International Conference on Computing，Communications and Networking Technologies.Tiruchengode：IEEE，2013：1-8.

［8］KEMILLY D G，MURILO C N.Multiple parallel MapReduce K-means clustering with validation and selection［C］.2014 Brazilian Conference on Intelligent Systems.Sao Paulo：IEEE，2014：432-437.

［9］彭昱忠，元昌安，麥雄發(fā)，等.基因表達(dá)式編程的理論研究綜述［J］.計算機(jī)應(yīng)用研究，2011，2（28）：414-438.

［10］張雪萍，龔康莉，趙廣才.基于MapReduce的K-Medoids并行算法［J］.計算機(jī)應(yīng)用，2013，33（4）：1023-1025，1035.

［11］Mukhopadhyay A，Maulik U，Bandyopadhyay S.An interactive approach to multiobjective clustering of Gene Expression Patterns［J］. IEEE Transactions on Biomedical Engineering，2013，60（1）：35-41.

［12］王小平，曹立明.遺傳算法：理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安：西安交通大學(xué)出版社，2002.

K-means；Gene Expression Programming（GEP）；MapReduce；Parallel；Massive Data

GEP_K-means Clustering Algorithm Based on MapReduce

GU Ling-lan
（Department of Computer Engineering，Guangdong Industry Technical College，Guangzhou 510300）

1007-1423（2015）20-0010-06

10.3969/j.issn.1007-1423.2015.20.003

古凌嵐（1965-），女，廣東梅州人，本科，副教授，研究方向?yàn)閿?shù)據(jù)挖掘、Web服務(wù)2015-05-12

2015-07-04

針對基于基因表達(dá)式編程的K均值聚類算法（GEP_K均值）中聚類中心生成和適應(yīng)度評價環(huán)節(jié)的計算效率較低的問題，提出一種基于MapReduce框架的GEP_K均值聚類算法。采用MapReduce分布式并行編程模式，對適應(yīng)度評價環(huán)節(jié)進(jìn)行并行化改進(jìn)，以減少算法處理時間，借助線性數(shù)據(jù)結(jié)構(gòu)直接操作染色體基因，以降低染色體基因表達(dá)求解生成聚類中心的時間和空間復(fù)雜度，并在Hadoop平臺上通過仿真實(shí)驗(yàn)對算法的性能進(jìn)行驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，該算法獲得了較好的加速比和可擴(kuò)展性，且無需額外空間開銷，適用于聚類數(shù)未知的大規(guī)模數(shù)據(jù)集的聚類分析。

K均值；基因表達(dá)式編程；MapReduce；并行；大數(shù)據(jù)集

廣東省檔案局科研技項目（YDK-95-2014）

In order to improve the computation efficiency of cluster center generation and fitness evaluation in K-means clustering algorithm based on Gene Expression Programming.Proposes a hybrid clustering algorithm of K-means and GEP based on MapReduce framework.As a distributional parallel programming model，MapReduce is used to parallel the computation of fitness evaluation in order to reduce processing time，and uses linear data structure to operated directly on chromosome genes in order to reduce the time and space complexities of genes expression to solve the cluster center.Verifies the algorithm on Hadoop by simulations.Experimental results show that the algorithm has high speedup and good stability，and no extra space overhead，fits to clustering analysis on massive data.