陳書會 周蓮英
摘要:針對kmeans算法對初始聚類中心敏感的問題,提出利用人工魚群算法去優(yōu)化k均值算法,即先通過人工魚的行為進(jìn)行全局搜索,得到一個初始的全局最優(yōu)劃分后再進(jìn)行聚類,運(yùn)用云平臺Hadoop的并行處理框架Mapreduce對混合算法實(shí)施并行處理,從而快速準(zhǔn)確地處理大量數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明,改進(jìn)后的算法在執(zhí)行速度、準(zhǔn)確性、加速比及可擴(kuò)展性方面都有所提高。
關(guān)鍵詞關(guān)鍵詞:聚類;kmeans算法;人工魚群算法;Mapreduce
DOIDOI:10.11907/rjdk.161281
中圖分類號:TP312文獻(xiàn)標(biāo)識碼:A文章編號文章編號:16727800(2016)007005103
0引言
kmeans是一種基于劃分的聚類算法,其相似性評價指標(biāo)為距離,即兩個對象距離越近,其相似度越大。算法隨機(jī)地確定初始值,再優(yōu)化初始劃分。如果初始值選擇不合適,算法就易陷入局部最優(yōu)。為解決這一問題,本文采用人工魚群算法(AFSA)進(jìn)行初始化。
針對大數(shù)據(jù)時代產(chǎn)生的海量數(shù)據(jù),在高效存儲及計算方面,分布式平臺Hadoop發(fā)揮著重要作用。本文研究了基于Mapreduce的afsa_km聚類算法,通過相關(guān)實(shí)驗(yàn)解決了kmeans對初始值敏感的問題,提高了海量數(shù)據(jù)處理的準(zhǔn)確性及效率。1串行afsa_km算法
afsa_km算法利用afsa全局尋優(yōu)特點(diǎn),先通過魚群行為搜索數(shù)據(jù)集中最優(yōu)或者靠近最優(yōu)的解,再把這些解作為kmeans的初始值。該方式在一定程度上能改善kmeans對初始中心敏感的問題,算法流程如圖1所示。1.1人工魚群算法
一般認(rèn)為一片水域中食物多的地方會有較多的魚群。全局尋優(yōu)是利用魚群追尾、群聚等行為尋找食物的過程,文獻(xiàn)中詳細(xì)說明了算法步驟。
變量定義:X=(x1,x2,…,xn)為個體狀態(tài),其中xi(i=1,2,…,n)為尋優(yōu)變量,人工魚最大步長為Step,人工魚的視野為Visual,嘗試次數(shù)為Try_number,擁擠度因子為λ,人工魚個體間距離dij=|Xi-Xj|,人工魚當(dāng)前位置的食物濃度Y=f(X)。
追尾行為:若當(dāng)前魚的狀態(tài)為 Xi,搜索其視野范圍 Visual內(nèi)相鄰伙伴,得到其中的最優(yōu)個體狀態(tài) Xj。若 Xj優(yōu)于當(dāng)前狀態(tài) Xi,且其周圍的擁擠程度不大于λ ,則當(dāng)前魚以步長Step向該狀態(tài)前進(jìn)一步,否則進(jìn)行覓食行為。
聚群行為:若當(dāng)前魚的狀態(tài)為 Xi,搜索其視野范圍Visual內(nèi)相鄰伙伴,得到相鄰伙伴的中心狀態(tài) Xc,若狀態(tài) Xc優(yōu)于當(dāng)前狀態(tài) Xi,且其周圍的擁擠程度小于λ,則當(dāng)前魚向該狀態(tài)前進(jìn)一步,否則進(jìn)行覓食行為。
覓食行為:若當(dāng)前魚的狀態(tài)為 Xi,隨機(jī)尋找一個在其視野內(nèi)的狀態(tài)Xj。若Xj優(yōu)于當(dāng)前狀態(tài) Xi,則當(dāng)前魚以步長Step向該狀態(tài)前進(jìn)一步,否則繼續(xù)隨機(jī)尋找一個新的狀態(tài)。若嘗試一定次數(shù)后,仍沒有優(yōu)于當(dāng)前的狀態(tài),則當(dāng)前魚隨機(jī)移動一步。
隨機(jī)行為:若當(dāng)前魚的狀態(tài)為 Xi,在其搜索范圍內(nèi)找不到更優(yōu)的狀態(tài),為了擴(kuò)大搜索空間,隨機(jī)選擇一個視野范圍內(nèi)的狀態(tài) Xj,便于跳出局部。
公告板:用來記錄目標(biāo)函數(shù)值、最優(yōu)人工魚個體狀態(tài)和歷史最優(yōu)人工魚個體狀態(tài)。每條人工魚在行動一次后就將自身狀態(tài)與公告板進(jìn)行比較,如果優(yōu)于公告板狀態(tài),就改寫公告板狀態(tài)。
將人工魚尋找食物的過程作為聚類時尋找類中心點(diǎn)的過程,滿足誤差平方和公式(1)即可認(rèn)為找到最優(yōu)中心點(diǎn)。
式(1)中k為聚類中心個數(shù),ci為聚類中心,xj為聚類對象。
1.2kmeans聚類算法
kmeans是劃分方法中比較經(jīng)典的聚類算法,由于效率高,在對大規(guī)模數(shù)據(jù)進(jìn)行聚類時廣泛應(yīng)用。算法以k為參數(shù),把n個對象分成k個簇,使簇內(nèi)有較高的相似度,而簇間的相似度較低。kmeans具體運(yùn)行過程如下:先隨機(jī)選擇k個對象,每個對象代表一個簇的平均值或中心;對剩余的對象,根據(jù)其與簇中心的距離,將它賦給最近的簇,重新計算每個簇的平均值。 這個過程不斷重復(fù),直到準(zhǔn)則函數(shù)收斂,最后輸出k個聚類中心。2并行afsa_km聚類算法
文獻(xiàn)采取的改進(jìn)afsa_km算法可以很好地彌補(bǔ)kmeans算法的缺陷,提高算法準(zhǔn)確度。由于整個程序是串行實(shí)現(xiàn)的,在處理大規(guī)模數(shù)據(jù)時,效率較低。人工魚群算法是一種并行算法,可以在Hadoop平臺上執(zhí)行。本文將人工魚群和kmeans算法全都并行化,并在Hadoop上運(yùn)行。2.1并行人工魚群算法
算法思想是:將魚群劃分為幾個子魚群,每個子魚群在給定的數(shù)據(jù)集中得到本次過程的局部最優(yōu)值,再匯總每個子魚群的最優(yōu)解,得到本次運(yùn)行的全局最優(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端進(jìn)行一次并歸。
設(shè)置全局共享區(qū)域:每次節(jié)點(diǎn)運(yùn)行完后,將各自節(jié)點(diǎn)上的魚群位置和對應(yīng)的適應(yīng)度值記錄在全局共享區(qū),供下一次算法執(zhí)行時使用。
算法首先為每個階段初始化子魚群,包括魚群數(shù)量t、視野范圍visual和試探次數(shù)Try_number等參數(shù)。
Map階段的處理:
①計算子魚群適應(yīng)度,設(shè)定子魚群初始狀態(tài)X,求出對應(yīng)的適應(yīng)度值;②評價每條人工魚,選擇要進(jìn)行的行為,包括覓食行為、聚群行為、追尾行為和隨機(jī)行為;③執(zhí)行人工魚選擇的行為,更新人工魚位置信息和適應(yīng)度值;④將新的人工魚位置和適應(yīng)度值傳給數(shù)據(jù)共享區(qū);⑤輸出鍵值對<1,(位置,適應(yīng)度值)>。
對數(shù)據(jù)列表中的數(shù)據(jù)按子魚群最優(yōu)適應(yīng)度值進(jìn)行排序。
更新公告牌。
在i次迭代后,滿足終止條件即可停止迭代,輸出k個聚類中心。本文使用迭代次數(shù)作為終止條件,也可以使用均方差的變化作為終止條件。
2.2并行kmeans算法
基于MapReduce的并行kmeans算法的Map函數(shù)主要完成數(shù)據(jù)點(diǎn)的歸類工作,使用上述人工魚群算法輸出的點(diǎn)作為初始聚類中心。
算法開始前,首先設(shè)置一個全局共享區(qū)域,記錄每次迭代得到的聚類中心。
Reduce將Combine輸出結(jié)果進(jìn)一步并歸,求出本輪迭代的聚類中心,并更新共享區(qū)。當(dāng)完成規(guī)定的迭代數(shù)之后,整個算法結(jié)束。
3實(shí)驗(yàn)結(jié)果
3.1實(shí)驗(yàn)環(huán)境
實(shí)驗(yà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準(zhǔn)確性實(shí)驗(yàn)
主要對并行算法的準(zhǔn)確性和有效性進(jìn)行測試。采用人工生成的3維數(shù)據(jù),設(shè)置成5類。測試的數(shù)據(jù)有3組:第1組data1包含2 000條數(shù)據(jù),不含有孤立點(diǎn);第2組data2包含2 000條數(shù)據(jù),有10個孤立點(diǎn);第3組data3包含20 000條數(shù)據(jù),不含孤立點(diǎn)。設(shè)定afsa_km中每個子魚群包含20條人工魚,迭代次數(shù)為20次。
3.3集群性能實(shí)驗(yàn)
加速比是用來衡量算法并行處理性能的一個重要評價指標(biāo),通過計算單節(jié)點(diǎn)運(yùn)行時間和多節(jié)點(diǎn)運(yùn)行時間比值獲得。實(shí)驗(yàn)采用人工生成的3組數(shù)據(jù)集A、B、C,其中A大小為32.3M,B大小為256.2M,C大小為1.8G。實(shí)驗(yàn)結(jié)果如圖4所示。從圖4中可以看出:隨著計算節(jié)點(diǎn)增加,處理相同規(guī)模數(shù)據(jù)有較好的加速比。隨著數(shù)據(jù)規(guī)模增大,加速比和節(jié)點(diǎn)數(shù)成線性增長,表現(xiàn)出良好的擴(kuò)展性。加速比與對應(yīng)節(jié)點(diǎn)數(shù)的比值即并行效率。圖5所示,在處理規(guī)模較小的數(shù)據(jù)時,集群的啟動和通信消耗的時間占整個處理時間比例較大,影響了算法的效率。處理的數(shù)據(jù)規(guī)模越大,算法效率也越高。綜合結(jié)果是基于Mapreduce的afsa_km算法有處理大規(guī)模數(shù)據(jù)的能力。
第7期 李玲俐:譜聚類算法及其應(yīng)用綜述軟 件 導(dǎo) 刊2016年標(biāo)題