基于布谷鳥算法的K-medoids聚類挖掘與并行優(yōu)化

譚成兵，劉 源，徐 健，3

（1.亳州職業(yè)技術(shù)學(xué)院 智能工程系，安徽 亳州 236813；2.桂林醫(yī)學(xué)院 信息中心，廣西 桂林 541001；3.桂林電子科技大學(xué) 機(jī)電工程學(xué)院，廣西 桂林 541004）

0 引言

聚類作為數(shù)據(jù)分析的常用方法，在多個(gè)行業(yè)得到了深度應(yīng)用，特別是基于大數(shù)據(jù)分析時(shí)，通過對(duì)大規(guī)模數(shù)據(jù)的聚類，可以完成多種看似無(wú)關(guān)聯(lián)的數(shù)據(jù)的歸類，從而降低了大規(guī)模數(shù)據(jù)管理和分析的難度?；诰垲惙治龅膽?yīng)用場(chǎng)景非常多，在電商領(lǐng)域，可根據(jù)用戶消費(fèi)數(shù)據(jù)進(jìn)行分類來(lái)制定合適的營(yíng)銷方案[1]；在線服務(wù)行業(yè)中，可以根據(jù)用戶使用習(xí)慣實(shí)現(xiàn)用戶聚類[2]，為不同類別用戶推薦合適服務(wù)等。在基于互聯(lián)網(wǎng)的數(shù)據(jù)分析平臺(tái)中，隨處可見聚類技術(shù)的影子。

當(dāng)前，關(guān)于聚類挖掘的研究成果較多，主要集中在聚類算法的研究方面。余勝輝和李玲娟采用層次聚類算法來(lái)實(shí)現(xiàn)聚類[3]，為了提高大規(guī)模數(shù)據(jù)的聚類性能，他們應(yīng)用spark平臺(tái)完成并行聚類研究，節(jié)省了聚類時(shí)間；陶瑩等采用K均值聚類算法實(shí)現(xiàn)大規(guī)模樣本數(shù)據(jù)聚類[4]，并研究了不同K值情況下的聚類性能；雷濤等采用模糊聚類算法應(yīng)用于圖像類樣本的聚類[5]，實(shí)現(xiàn)了從文本到圖像聚類的轉(zhuǎn)變，開拓了聚類算法的新應(yīng)用對(duì)象。這些算法實(shí)現(xiàn)了不同規(guī)模和類型的數(shù)據(jù)聚類，取得了較好的聚類準(zhǔn)確率，本文采用K-medoids聚類，通過布谷鳥算法來(lái)進(jìn)行優(yōu)化，提高聚類準(zhǔn)確率；在聚類時(shí)間方面采用了多節(jié)點(diǎn)的并行聚類方法，提高聚類效率[6]。

1 布谷鳥算法

設(shè)鳥群共有N只布谷鳥，鳥巢被宿主發(fā)現(xiàn)概率為Pa，鳥群的初始位置分布為X0，計(jì)算初始適應(yīng)度，選擇較好的鳥巢和對(duì)應(yīng)最優(yōu)解集合分別為。

設(shè)布谷鳥移動(dòng)的方式為[7]：

其中，α為移動(dòng)步，Levy(λ)服從萊維分布，具體表達(dá)式為[8]：

其中，u和v均表示分布參數(shù)，λ=1.5，

其中，Γ為Gamma函數(shù)。通過式（1）位置更新，然后計(jì)算適應(yīng)度，第t次得到的適應(yīng)度最優(yōu)解集合為，其中，1＜t≤T。

設(shè)r∈[0 ,1 ]對(duì)比r與Pa，若r＞Pa，則繼續(xù)進(jìn)行位置更新，鳥巢位置更新方式為[9]：

繼續(xù)迭代直到達(dá)到最大迭代次數(shù)或者適應(yīng)度滿足閾值時(shí)[10]，輸出Xbest和fbest。一般情況下取Pa=0.25，α=1。

2 布谷鳥優(yōu)化的K-medoids聚類

2.1 K-medoids聚類

2.2 布谷鳥優(yōu)化的K-mediods聚類流程

根據(jù)聚類簇構(gòu)建布谷鳥算法模型，采用K-mediods的適應(yīng)度函數(shù)獲得最優(yōu)鳥巢位置，通過萊維分布更新方法，獲取最優(yōu)位置及最優(yōu)適應(yīng)度值，其主要流程如圖1所示。分布式環(huán)境下聚類算法的Reduce具體實(shí)現(xiàn)步驟如表1所示。

圖1 布谷鳥優(yōu)化的K-mediods聚類流程圖

表1 Reduce具體實(shí)現(xiàn)步驟

3 實(shí)例仿真

為了驗(yàn)證布谷鳥算法在K-mediods的聚類性能，對(duì)其進(jìn)行實(shí)例仿真。聚類對(duì)象分別選擇了自有數(shù)據(jù)集和公開UCI的5種類別數(shù)據(jù)集，UCI數(shù)據(jù)集參數(shù)如表2所示。仿真主要測(cè)試布谷鳥算法對(duì)K-mediods聚類的性能影響，以及多個(gè)運(yùn)算節(jié)點(diǎn)同時(shí)參與聚類的并行優(yōu)化性能。

表2 UCI數(shù)據(jù)集參數(shù)

3.1 聚類性能仿真

3.1.1 聚類可視化

選擇某電商公司的2000個(gè)客戶，根據(jù)其消費(fèi)習(xí)慣對(duì)2000個(gè)客戶從3個(gè)維度進(jìn)行分類，類別K=5，分別將客戶數(shù)據(jù)屬性進(jìn)行數(shù)字化和歸一化。

布谷鳥優(yōu)化的K-mediods聚類將2000用戶分成了5個(gè)類別，通過matlab仿真輸出結(jié)果，其對(duì)5個(gè)類別分類的準(zhǔn)確率及標(biāo)準(zhǔn)差如表3所示。

表3 用戶聚類準(zhǔn)確率

從表3可得，2000個(gè)分屬于5個(gè)類別的用戶的聚類準(zhǔn)確率均達(dá)到92%以上，其中A和E等級(jí)的聚類準(zhǔn)確率最高，可能是樣本屬性值差距大，較易分類，而C類別聚類準(zhǔn)確率略低，這可能是由于其用戶屬性和B、D類別較近，不容易分類造成的。在標(biāo)準(zhǔn)差方面，不同類別的聚類性能差異較小。

3.1.2 UCI數(shù)據(jù)集聚類準(zhǔn)確率

為了進(jìn)一步驗(yàn)證布谷鳥算法在K-mediods的聚類效果，對(duì)常用UCI數(shù)據(jù)集進(jìn)行布谷鳥算法的K-mediods聚類，K=9，結(jié)果如表4所示。

表4 布谷鳥算法的聚類優(yōu)化性能對(duì)比

通過對(duì)比發(fā)現(xiàn)，經(jīng)過布谷鳥算法優(yōu)化后的K-mediods聚類對(duì)5種UCI數(shù)據(jù)集的聚類準(zhǔn)確率均有所提升，其中g(shù)lass數(shù)據(jù)集提升最明顯，提升了3.565%，seeds數(shù)據(jù)集優(yōu)化性能不顯著。在標(biāo)準(zhǔn)差方面，經(jīng)過布谷鳥優(yōu)化后的性能均有不同程度的提升。

3.2 并行優(yōu)化性能

在并行優(yōu)化聚類時(shí)，共構(gòu)建了基于10個(gè)運(yùn)算節(jié)點(diǎn)的分布式聚類節(jié)點(diǎn)，可以靈活選擇多個(gè)節(jié)點(diǎn)進(jìn)行表1中數(shù)據(jù)集的聚類，初始化隨機(jī)設(shè)置K-mediods的聚類中心數(shù)目，分別對(duì)單機(jī)K-mediods、多節(jié)點(diǎn)K-mediods和布谷鳥優(yōu)化K-mediods進(jìn)行性能仿真。

設(shè)定3種算法的聚類停止條件為聚類準(zhǔn)確率不低于75%，聚類節(jié)點(diǎn)數(shù)為10，其運(yùn)算時(shí)間如圖2所示。

圖2 聚類時(shí)間（樣本容量=32.64GB）

從圖2中可以看出，3種算法的聚類時(shí)間隨著聚類中心數(shù)的增加而增長(zhǎng)，但通過對(duì)比發(fā)現(xiàn)，單機(jī)K-mediods算法聚類時(shí)間增長(zhǎng)較快，多節(jié)點(diǎn)聚類時(shí)間增長(zhǎng)較緩，而且單機(jī)運(yùn)行時(shí)間相比多節(jié)點(diǎn)超出很多，證明并行優(yōu)化在聚類時(shí)間方面性能提升顯著。從圖2中也可得出，采用布谷鳥算法優(yōu)化后，節(jié)省了K-mediods算法對(duì)UCI數(shù)據(jù)集的聚類時(shí)間。

3.3 不同算法的聚類準(zhǔn)確率對(duì)比

最后對(duì)常用聚類算法進(jìn)行聚類性能比較，分別采用均值聚類算法、層次聚類算法、布谷鳥 K-means算法[14-15]和布谷鳥 K-mediods算法方法對(duì)表1中的glass樣本進(jìn)行仿真。參數(shù)Pa=0.25，α=1，聚類準(zhǔn)確率閾值0.75，并行計(jì)算節(jié)點(diǎn)數(shù)10，仿真結(jié)果如圖3所示。

圖3 不同算法聚類準(zhǔn)確率

從圖3中可以看出，對(duì)于glass數(shù)據(jù)集，布谷鳥K-mediods聚類算法的準(zhǔn)確率最高，布谷鳥K-means聚類算法次之，其他兩種算法聚類準(zhǔn)確率差別較小。從聚類時(shí)間來(lái)看，本文中的算法有絕對(duì)優(yōu)勢(shì)，聚類時(shí)間小于100 s，其他聚類時(shí)間均在120 s以上，這是因?yàn)椴捎昧瞬⑿卸喙?jié)點(diǎn)參與聚類，所以節(jié)省了聚類時(shí)間。

4 結(jié)語(yǔ)

采用布谷鳥優(yōu)化的K-mediods聚類，選擇合適布谷鳥算法的宿主發(fā)現(xiàn)概率及適應(yīng)度函數(shù)，分別對(duì)自有數(shù)據(jù)集和UCI公開數(shù)據(jù)集進(jìn)行仿真，均獲得了較好的聚類效果。采用多節(jié)點(diǎn)參與聚類的并行優(yōu)化方法，能夠快速提高大規(guī)模樣本的聚類效率。