基于Mapreduce的afsa_km聚類(lèi)算法并行實(shí)現(xiàn)

陳書(shū)會(huì) 周蓮英

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

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

DOIDOI：10.11907/rjdk.161281

中圖分類(lèi)號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2016）007005103

0引言

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

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

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

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

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

追尾行為：若當(dāng)前魚(yú)的狀態(tài)為 Xi，搜索其視野范圍 Visual內(nèi)相鄰伙伴，得到其中的最優(yōu)個(gè)體狀態(tài) Xj。若 Xj優(yōu)于當(dāng)前狀態(tài) Xi，且其周?chē)膿頂D程度不大于λ ，則當(dāng)前魚(yú)以步長(zhǎng)Step向該狀態(tài)前進(jìn)一步，否則進(jìn)行覓食行為。

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

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

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

公告板：用來(lái)記錄目標(biāo)函數(shù)值、最優(yōu)人工魚(yú)個(gè)體狀態(tài)和歷史最優(yōu)人工魚(yú)個(gè)體狀態(tài)。每條人工魚(yú)在行動(dòng)一次后就將自身狀態(tài)與公告板進(jìn)行比較，如果優(yōu)于公告板狀態(tài)，就改寫(xiě)公告板狀態(tài)。

將人工魚(yú)尋找食物的過(guò)程作為聚類(lèi)時(shí)尋找類(lèi)中心點(diǎn)的過(guò)程，滿(mǎn)足誤差平方和公式（1）即可認(rèn)為找到最優(yōu)中心點(diǎn)。

式（1）中k為聚類(lèi)中心個(gè)數(shù)，ci為聚類(lèi)中心，xj為聚類(lèi)對(duì)象。

1.2kmeans聚類(lèi)算法

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

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

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

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

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

Map階段的處理：

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

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

更新公告牌。

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

2.2并行kmeans算法

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

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

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

3實(shí)驗(yàn)結(jié)果

3.1實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)中的Hadoop集群由6臺(tái)電腦組成，其中1臺(tái)作為master，其它5臺(tái)作為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準(zhǔn)確性實(shí)驗(yàn)

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

3.3集群性能實(shí)驗(yàn)

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

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