譚成兵，劉 源，徐 健，3

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

0 引言

聚類作為數據分析的常用方法，在多個行業(yè)得到了深度應用，特別是基于大數據分析時，通過對大規(guī)模數據的聚類，可以完成多種看似無關聯的數據的歸類，從而降低了大規(guī)模數據管理和分析的難度?；诰垲惙治龅膽脠鼍胺浅６?，在電商領域，可根據用戶消費數據進行分類來制定合適的營銷方案[1]；在線服務行業(yè)中，可以根據用戶使用習慣實現用戶聚類[2]，為不同類別用戶推薦合適服務等。在基于互聯網的數據分析平臺中，隨處可見聚類技術的影子。

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

1 布谷鳥算法

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

設布谷鳥移動的方式為[7]：

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

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

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

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

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

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

2.1 K-medoids聚類

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

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

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

表1 Reduce具體實現步驟

3 實例仿真

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

表2 UCI數據集參數

3.1 聚類性能仿真

3.1.1 聚類可視化

選擇某電商公司的2000個客戶，根據其消費習慣對2000個客戶從3個維度進行分類，類別K=5，分別將客戶數據屬性進行數字化和歸一化。

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

表3 用戶聚類準確率

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

3.1.2 UCI數據集聚類準確率

為了進一步驗證布谷鳥算法在K-mediods的聚類效果，對常用UCI數據集進行布谷鳥算法的K-mediods聚類，K=9，結果如表4所示。

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

通過對比發(fā)現，經過布谷鳥算法優(yōu)化后的K-mediods聚類對5種UCI數據集的聚類準確率均有所提升，其中glass數據集提升最明顯，提升了3.565%，seeds數據集優(yōu)化性能不顯著。在標準差方面，經過布谷鳥優(yōu)化后的性能均有不同程度的提升。

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

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

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

圖2 聚類時間（樣本容量=32.64GB）

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

3.3 不同算法的聚類準確率對比

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

圖3 不同算法聚類準確率

從圖3中可以看出，對于glass數據集，布谷鳥K-mediods聚類算法的準確率最高，布谷鳥K-means聚類算法次之，其他兩種算法聚類準確率差別較小。從聚類時間來看，本文中的算法有絕對優(yōu)勢，聚類時間小于100 s，其他聚類時間均在120 s以上，這是因為采用了并行多節(jié)點參與聚類，所以節(jié)省了聚類時間。

4 結語

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