基于MapReduce的GEP_K均值聚類算法

古凌嵐

（廣東輕工職業技術學院計算機工程系，廣州　510300）

基于MapReduce的GEP_K均值聚類算法

古凌嵐

（廣東輕工職業技術學院計算機工程系，廣州510300）

0　引言

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

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

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

1　MRGEP_K均值聚類算法

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

圖1　MRGEP_K均值算法的并行實現流程

1.1染色體基因表達求解方法的改進

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

Reduce階段

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

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

（3）從前向后遍歷arrayList2，對于每個元素中的位置編號序列，計算對應的T節點均值，并加入arrayList3，實現簇的合并。

（4）將簇中心點寫入聚類中心信息文件。

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

1.2適應度評價的并行化

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

Map階段

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

②計算每個數據點Dj與C1，C2，…，Ck的距離Dist （j，1），Dist（j，2），…，Dist（j，k）；

③將數據點Dj劃分到Distmin（j，i）對應的簇i中；

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

Reduce階段

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

③輸出適應度f。

圖2　染色體基因表達求解示意圖

1.3遺傳操作的實現

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

Reduce階段

①讀取種群信息文件和個體適應度值信息文件；

②保留最優個體；

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

④輸出新種群。

1.4算法的復雜度分析

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

2　實驗結果與分析

2.1實驗環境、數據集和評價指標

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

表1　實驗樣本數據集

對于算法的計算效率，本文通過運行時間和占用內存進行評價。對于算法的并行性能，則采用加速比和可擴展性來衡量。

2.2實驗結果分析

（1）改進的基因表達求解方法性能分析

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

表2　基因表達求解方法性能分析實驗結果

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

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

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

表3　有效性分析實驗結果

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

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

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

圖3　運行時間與節點數關系

圖4　加速比實驗結果

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

可擴展性是指并行算法有效利用集群中運算節點增加的能力，其計算公式為E=S/P，其中S為加速比，P為集群節點數。分別選擇2、4、6個運算節點，以及不同規模的DW1、DW2和DW3數據集，計算并行效率。計算結果如圖5所示。計算結果表明，對于較大的數據集，其并行效率更高，最高達到0.86；當數據規模和節點數都增加時，并行處理能力穩定，表現出較好的可擴展性。

圖5　可擴展性實驗結果

3　結語

本文采用MapReduce并行編程模型，實現適應度評價的并行化，借助線性數據結構改善基因表達求解環節的計算復雜度，構建了基于MapReduce的GEP_K均值聚類算法。實驗結果表明，本文算法與GEP_K均值相比，迭代處理的時間明顯減少，尤其是較大規模的數據集，運行效率的提高更為明顯。對于高維數據集，采用歐氏距離函數作為聚類準則，很難度量數據對象間的相似性，優化聚類準則提高聚類質量將是下一步研究工作的重點。

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

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

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

［4］李成華，張新訪，金海，等.MapReduce：新型的分布式并行計算編程模型［J］.計算機工程與科學，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］李東，潘志松.一種適用于大規模變量的并行遺傳算法研究［J］.計算機科學，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］彭昱忠，元昌安，麥雄發，等.基因表達式編程的理論研究綜述［J］.計算機應用研究，2011，2（28）：414-438.

［10］張雪萍，龔康莉，趙廣才.基于MapReduce的K-Medoids并行算法［J］.計算機應用，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］王小平，曹立明.遺傳算法：理論、應用與軟件實現［M］.西安：西安交通大學出版社，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-），女，廣東梅州人，本科，副教授，研究方向為數據挖掘、Web服務2015-05-12

2015-07-04

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

K均值；基因表達式編程；MapReduce；并行；大數據集

廣東省檔案局科研技項目（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.