基于Mapreduce的afsa_km聚類算法并行實現(xiàn)

陳書會 周蓮英

摘要：針對kmeans算法對初始聚類中心敏感的問題，提出利用人工魚群算法去優(yōu)化k均值算法，即先通過人工魚的行為進行全局搜索，得到一個初始的全局最優(yōu)劃分后再進行聚類，運用云平臺Hadoop的并行處理框架Mapreduce對混合算法實施并行處理，從而快速準確地處理大量數(shù)據(jù)。實驗結(jié)果表明，改進后的算法在執(zhí)行速度、準確性、加速比及可擴展性方面都有所提高。

關(guān)鍵詞關(guān)鍵詞：聚類；kmeans算法；人工魚群算法；Mapreduce

DOIDOI：10.11907/rjdk.161281

中圖分類號：TP312文獻標識碼：A文章編號文章編號：16727800（2016）007005103

0引言

kmeans是一種基于劃分的聚類算法，其相似性評價指標為距離，即兩個對象距離越近，其相似度越大。算法隨機地確定初始值，再優(yōu)化初始劃分。如果初始值選擇不合適，算法就易陷入局部最優(yōu)。為解決這一問題，本文采用人工魚群算法（AFSA）進行初始化。

針對大數(shù)據(jù)時代產(chǎn)生的海量數(shù)據(jù)，在高效存儲及計算方面，分布式平臺Hadoop發(fā)揮著重要作用。本文研究了基于Mapreduce的afsa_km聚類算法，通過相關(guān)實驗解決了kmeans對初始值敏感的問題，提高了海量數(shù)據(jù)處理的準確性及效率。1串行afsa_km算法

afsa_km算法利用afsa全局尋優(yōu)特點，先通過魚群行為搜索數(shù)據(jù)集中最優(yōu)或者靠近最優(yōu)的解，再把這些解作為kmeans的初始值。該方式在一定程度上能改善kmeans對初始中心敏感的問題，算法流程如圖1所示。1.1人工魚群算法

一般認為一片水域中食物多的地方會有較多的魚群。全局尋優(yōu)是利用魚群追尾、群聚等行為尋找食物的過程，文獻中詳細說明了算法步驟。

變量定義：X=（x1，x2，…，xn）為個體狀態(tài)，其中xi（i=1，2，…，n）為尋優(yōu)變量，人工魚最大步長為Step，人工魚的視野為Visual，嘗試次數(shù)為Try_number，擁擠度因子為λ，人工魚個體間距離dij=|Xi-Xj|，人工魚當前位置的食物濃度Y=f（X）。

追尾行為：若當前魚的狀態(tài)為 Xi，搜索其視野范圍 Visual內(nèi)相鄰伙伴，得到其中的最優(yōu)個體狀態(tài) Xj。若 Xj優(yōu)于當前狀態(tài) Xi，且其周圍的擁擠程度不大于λ ，則當前魚以步長Step向該狀態(tài)前進一步，否則進行覓食行為。

聚群行為：若當前魚的狀態(tài)為 Xi，搜索其視野范圍Visual內(nèi)相鄰伙伴，得到相鄰伙伴的中心狀態(tài) Xc，若狀態(tài) Xc優(yōu)于當前狀態(tài) Xi，且其周圍的擁擠程度小于λ，則當前魚向該狀態(tài)前進一步，否則進行覓食行為。

覓食行為：若當前魚的狀態(tài)為 Xi，隨機尋找一個在其視野內(nèi)的狀態(tài)Xj。若Xj優(yōu)于當前狀態(tài) Xi，則當前魚以步長Step向該狀態(tài)前進一步，否則繼續(xù)隨機尋找一個新的狀態(tài)。若嘗試一定次數(shù)后，仍沒有優(yōu)于當前的狀態(tài)，則當前魚隨機移動一步。

隨機行為：若當前魚的狀態(tài)為 Xi，在其搜索范圍內(nèi)找不到更優(yōu)的狀態(tài)，為了擴大搜索空間，隨機選擇一個視野范圍內(nèi)的狀態(tài) Xj，便于跳出局部。

公告板：用來記錄目標函數(shù)值、最優(yōu)人工魚個體狀態(tài)和歷史最優(yōu)人工魚個體狀態(tài)。每條人工魚在行動一次后就將自身狀態(tài)與公告板進行比較，如果優(yōu)于公告板狀態(tài)，就改寫公告板狀態(tài)。

將人工魚尋找食物的過程作為聚類時尋找類中心點的過程，滿足誤差平方和公式（1）即可認為找到最優(yōu)中心點。

式（1）中k為聚類中心個數(shù)，ci為聚類中心，xj為聚類對象。

1.2kmeans聚類算法

kmeans是劃分方法中比較經(jīng)典的聚類算法，由于效率高，在對大規(guī)模數(shù)據(jù)進行聚類時廣泛應(yīng)用。算法以k為參數(shù)，把n個對象分成k個簇，使簇內(nèi)有較高的相似度，而簇間的相似度較低。kmeans具體運行過程如下：先隨機選擇k個對象，每個對象代表一個簇的平均值或中心；對剩余的對象，根據(jù)其與簇中心的距離，將它賦給最近的簇，重新計算每個簇的平均值。 這個過程不斷重復(fù)，直到準則函數(shù)收斂，最后輸出k個聚類中心。2并行afsa_km聚類算法

文獻采取的改進afsa_km算法可以很好地彌補kmeans算法的缺陷，提高算法準確度。由于整個程序是串行實現(xiàn)的，在處理大規(guī)模數(shù)據(jù)時，效率較低。人工魚群算法是一種并行算法，可以在Hadoop平臺上執(zhí)行。本文將人工魚群和kmeans算法全都并行化，并在Hadoop上運行。2.1并行人工魚群算法

算法思想是：將魚群劃分為幾個子魚群，每個子魚群在給定的數(shù)據(jù)集中得到本次過程的局部最優(yōu)值，再匯總每個子魚群的最優(yōu)解，得到本次運行的全局最優(yōu)解，算法流程如圖2所示。在Hadoop中，Map函數(shù)主要完成每個子魚群的尋優(yōu)，包括覓食、群聚、追尾，輸出子魚群的最優(yōu)解及適應(yīng)度值。Map函數(shù)輸入key為數(shù)據(jù)的行號，value為待聚類數(shù)據(jù)的各維度值。為了減少網(wǎng)絡(luò)數(shù)據(jù)開銷，使用Combine對Map端進行一次并歸。

設(shè)置全局共享區(qū)域：每次節(jié)點運行完后，將各自節(jié)點上的魚群位置和對應(yīng)的適應(yīng)度值記錄在全局共享區(qū)，供下一次算法執(zhí)行時使用。

算法首先為每個階段初始化子魚群，包括魚群數(shù)量t、視野范圍visual和試探次數(shù)Try_number等參數(shù)。

Map階段的處理：

①計算子魚群適應(yīng)度，設(shè)定子魚群初始狀態(tài)X，求出對應(yīng)的適應(yīng)度值；②評價每條人工魚，選擇要進行的行為，包括覓食行為、聚群行為、追尾行為和隨機行為；③執(zhí)行人工魚選擇的行為，更新人工魚位置信息和適應(yīng)度值；④將新的人工魚位置和適應(yīng)度值傳給數(shù)據(jù)共享區(qū)；⑤輸出鍵值對<1，（位置，適應(yīng)度值）>。

對數(shù)據(jù)列表中的數(shù)據(jù)按子魚群最優(yōu)適應(yīng)度值進行排序。

更新公告牌。

在i次迭代后，滿足終止條件即可停止迭代，輸出k個聚類中心。本文使用迭代次數(shù)作為終止條件，也可以使用均方差的變化作為終止條件。

2.2并行kmeans算法

基于MapReduce的并行kmeans算法的Map函數(shù)主要完成數(shù)據(jù)點的歸類工作，使用上述人工魚群算法輸出的點作為初始聚類中心。

算法開始前，首先設(shè)置一個全局共享區(qū)域，記錄每次迭代得到的聚類中心。

Reduce將Combine輸出結(jié)果進一步并歸，求出本輪迭代的聚類中心，并更新共享區(qū)。當完成規(guī)定的迭代數(shù)之后，整個算法結(jié)束。

3實驗結(jié)果

3.1實驗環(huán)境

實驗中的Hadoop集群由6臺電腦組成，其中1臺作為master，其它5臺作為slaves。硬件配置：master是雙核2.9GHz，8G內(nèi)存；slaves都是雙核2.4GHz，4GHz內(nèi)存。軟件配置：系統(tǒng)版本Ubuntu 14.04；Jdk 1.6.0；hadoop 1.2.1。

3.2準確性實驗

主要對并行算法的準確性和有效性進行測試。采用人工生成的3維數(shù)據(jù)，設(shè)置成5類。測試的數(shù)據(jù)有3組：第1組data1包含2 000條數(shù)據(jù)，不含有孤立點；第2組data2包含2 000條數(shù)據(jù)，有10個孤立點；第3組data3包含20 000條數(shù)據(jù)，不含孤立點。設(shè)定afsa_km中每個子魚群包含20條人工魚，迭代次數(shù)為20次。

3.3集群性能實驗

加速比是用來衡量算法并行處理性能的一個重要評價指標，通過計算單節(jié)點運行時間和多節(jié)點運行時間比值獲得。實驗采用人工生成的3組數(shù)據(jù)集A、B、C，其中A大小為32.3M，B大小為256.2M，C大小為1.8G。實驗結(jié)果如圖4所示。從圖4中可以看出：隨著計算節(jié)點增加，處理相同規(guī)模數(shù)據(jù)有較好的加速比。隨著數(shù)據(jù)規(guī)模增大，加速比和節(jié)點數(shù)成線性增長，表現(xiàn)出良好的擴展性。加速比與對應(yīng)節(jié)點數(shù)的比值即并行效率。圖5所示，在處理規(guī)模較小的數(shù)據(jù)時，集群的啟動和通信消耗的時間占整個處理時間比例較大，影響了算法的效率。處理的數(shù)據(jù)規(guī)模越大，算法效率也越高。綜合結(jié)果是基于Mapreduce的afsa_km算法有處理大規(guī)模數(shù)據(jù)的能力。

第7期 李玲俐：譜聚類算法及其應(yīng)用綜述軟 件 導(dǎo) 刊2016年標題