基于優化粒計算下微粒子動態搜索的K—medoids聚類算法

宋紅海 顏宏文

摘 要：K-medoids算法具有對初始聚類中心敏感，聚類準確度不高及時間復雜度大的缺點?；诖?，文中提出一種優化的K-medoids算法；該算法在已有的粒計算初始化基礎上進行了改進，以對象之間的相似性作為判斷依據，結合最大最小法初始化聚類中心，能有效地獲取最佳或近似最佳的聚類中心；在優化的粒計算前提下，提出了基于微粒子動態搜索策略，以初始中心點作為基點，粒子內所有對象到其中心的平均距離為半徑，形成一個微粒子；在微粒子內部，采用離中心點先近后遠的原則進行搜索，能有效地縮小搜索范圍，提高聚類準確率。實驗結果表明：在UCI多個標準數據集中測試，且與其他改進的K-medoids算法比較分析，該算法在有效縮短收斂時間的同時保證了算法聚類準確率。

關鍵字：聚類；K-medoids算法；粒計算；相似性；微粒子動態搜索

文獻標志碼： A 中圖分類號：TP301.6文章編號：2095-2163（2016）02-

Novel K-medoids clustering algorithm based on dynamic search of Microparticlesunder optimizedgranular computing

SONG Honghai，YAN Hongwen

（ Institute of Computer and Communication Engineering， Changsha University of Sciences and Technology， Changsha Hunan 410114， China）

Abstract：The K-medoids algorithm has the disadvantage of sensitivity to cluster center initialization， low clustering accuracyand high the time complexity. So this paper proposes an optimized K-medoids algorithm； this algorithm has been initialized on the basis of granular computing which takes the similarity between objects as the basis to judge， and combined with the maximum and minimum cluster center initialization method the best or near-best cluster centercan be effectively accessed； Under the precondition of optimization of granular computing， the paper puts forward the dynamic search strategy based on the microparticles， the initial center as a base， all objects within the particles to an average distance of the center of the radius， form a microparticle； In microparticles inside， using the first after nearly far from the center of the principle of search， can effectively narrow the search， increase the clustering accuracy. Tested on a number of standard data sets in UCIand compared with other improved K-medoids algorithm， the experimental results show that this new algorithm reuduces the convergence time effectively and improves the accuracy of clustering.

Key word：clustering； K-medoids algorithm； granular computing；similarity； microparticles dynamic search

0 引言

聚類就是將擁有不同屬性的事物劃分成不同類的過程，不依賴于先驗信息，只需考慮數據本身的特征屬性以及數據間的相互關系[1]，同一類內的事物屬性具有高質的相似性，不同類之間的屬性則具有高度不相似性。作為一種重要的數據分析方法，聚類已經成為一種實用開發工具，廣泛地應用到數據挖掘、模式識別、信息檢索和圖像處理等領域。

在時下經典的聚類算法中，K-medoids算法具有了較為普遍應用性。算法優點是實現思想簡單，搜索能力強等，但也存在對初始化聚類中心敏感，時間復雜度較高，精確度不高等問題。針對這一特征狀況，有大量學者提出了許多改進的算法：文獻[2-4]提出了運用粒計算的思想來初始化 K-medoids 聚類中心，從而降低了時間復雜度，增強了局部搜索能力，但由于粒子多會表現出一定的隨機性，使得準確率未獲提高；文獻[5]提出了一種改進粒計算的K-medoids算法，在相當程度上改善了K-medoids算法對初始化聚類中心敏感的問題，但因其搜索能力不強，導致精確度也未見可觀增長；，進一步地，文獻[6]則提出一個基于最小支撐樹的初始化聚類中心方法，有效解決了初始化敏感的問題，但卻增加了時間復雜度；另外，文獻[7-8]又采用相異度矩陣來記錄樣本之間的距離，增強了局部搜索能力，同時降低了時間復雜度。

綜上可知，各研究文獻從不同方面對K-medoids算法實施了改進與優化，并已取得了一定的成果，但也存在明顯的局限性，具體就是時間復雜度和準確度不能兼顧：有些以增加時間復雜度為代價來提高準確度，有些是以犧牲準確度來降低時間復雜度；還有一些則只是針對某種特定的數據?；诖?，在現有粒計算的基礎上，本文提出了一種基于優化粒計算初始化，微粒子動態搜索的K-medoids算法。

1 傳統的K-medoids算法

K-medoids聚類算法根據K-means算法的思想改進而來[9]，是一種劃分的方法，能夠有效地處理異常數據和噪聲數據，且具良好的魯棒性。算法中采用歐氏距離來衡

基于粒計算初始化步驟如下：

3 算法的改進

3.1 粒計算的改進

基于粒計算初始化的步驟6改進如下：前2個初始化中心保持不變，仍然分別是粒子密度最大粒子的中心和距密度最大粒子最遠且密度最大的粒子的中心，記為 和 ；對于剩下的粒子不是以歐氏距離作為依據，而是以對象間的相似度為依據，結合最大最小法，分別計算出剩余粒子的中心與 的相似度，記為 ，取 ，例如取第三個初始化中心時，分別計算出 ，則 ，依次類推，得到 個初始化聚類中心。

4.2基于微粒子動態搜索

基于改進的粒計算初 始化后，同一粒子中的對象具有高密度和高相似度，即同一粒子中的對象很大程度上可能屬于同一簇，可以判定與初始化中心相近的對象是最優聚類中心的候選集。因此，提出一種基于微粒子動態搜索的策略。

3.2.1 新概念

粒子中對象到其中心的平均距離，對其數學定義可表述為：

其中， 是粒子 中對象 與中心 的歐氏距離， 是粒子 所包含對象的個數。

定義5 微粒子：以某一對象為基點，粒子中所有對象到粒子中心的平均距離為半徑r，這樣包含若干個對象的封閉區域。

3.2.2 微粒子搜索過程

以初始化中心 為基點，粒子 中所有對象 的平均距離 為半徑，這樣形成的圓區域內所包含的對象為一個微粒子；在微粒子內，以離初始化中心點 最近的對象作為新的聚類中心，根據準則函數可進行如下判斷：

若新的準則函數 小于原準則函數 ，即 ，則用新的聚類中心點代替原中心點；再以新的聚類中心點為基點， 為半徑，形成新的微粒子，在新的微粒子中應用上述搜索策略。

若新的準則函數 大于原準則函數 ，即 ，則中心點不變；采取先近后遠的原則，以離初始化中心點 次近的對象作為新的聚類中心點，計算準則函數。

依此類推，直至找到最佳聚類中心。在粒計算有效初始化的前提下，基于微粒子動態搜索，縮小了尋找最佳聚類中心的范圍，提高了搜索的效率。

改進算法的實現過程可具體描述如下：

綜上所述，實驗從改進算法的準確率和收斂時間兩個方面，與其他算法進行了對比。由實驗可知文中算法能夠收斂于最佳中心或最相似中心，提高了聚類的準確率和縮短了其運行的時間，尤其在相對較大的數據集上，文中算法的聚類效果明顯優于其他算法。

5 結束語

K-medoids算法具有對初始聚類中心敏感，聚類準確度不高及時間復雜度大的缺點。文中提出了一種新的K-medoids算法，該算法采用改進的粒計算來克服K-medoids算法對初始化敏感問題，使用基于微粒子動態搜索策略改善了K-medoids算法全局搜索的能力，提高了算法精確度，同時也縮短了其收斂的時間。文中算法與其他改進的K-medoids算法作了對比，通過對比驗證了文中算法的可行性與有效性。

參考文獻：

[1]馬儒寧，王秀麗，丁軍娣.多層核心集凝聚算法[J].軟件學報，2013，23（3）：490-506.

[2]王永貴，林琳，劉憲國.基于改進粒子群優化的文本聚類算法研究[J]計算機工程，2014，40（11）：172-177.

[3]馬箐，謝英娟.基于粒計算的K-medoids 聚類算法[J].計算機應用，2012，32（7）：1973-1977.

[4]姚麗娟，羅可，孟穎.一種基于粒子群的聚類算法[J].計算機工程與應用，2012，48（13）：150-153.

[5]潘楚，羅可.基于改進粒計算的 K-medoids 聚類算法[J].計算機應用，2014，34（7）：1997-2000.

[6]李春生，王耀南.聚類中心初始化的新方法[J].控制理論與應用，2010，27（10）：1436-1440.

[7]陶新民，徐晶，楊立標等.一種改進的粒子群和 K均值混合聚類算法[J].電子與信息學報，2010，32（1）：93-97.

[8]HAE-SANG，PARK，CHI-HYUCKJ.Asimpleand fastalgorithmforK-medoidsclustering[J].ExpertSystems with Applications，2008，36（2）：3336-3341.

[9]Han Jiawei，Kamber M.數據挖掘：概念與技術[M].范明，譯.北京：機械工業出版社，2012：293-297.

[10]張雪萍，龔康莉，趙廣才.基于 MapReduce的 K-medoids并行算法[J].計算機應用，2013，33（4）：1024-1035.

[11]王國胤，張清華，胡軍.粒計算研究綜述[J].智能系統學報，2007，2（6）：8-26.

[12]王倫文.聚類的粒度分析[J].計算機工程與應用，2006，42（5） ：29-31.

[13]徐麗，丁世飛.粒度聚類算法研究[J].計算機科學，2011，38（8）：25-28.

[14]顏宏文，周雅梅，潘楚.基于寬度優先搜索的K-medoids聚類算法[J].計算機應用，2015，35（5）：1302-1305.

[15]謝英娟，魯肖肖，屈亞楠等.粒計算優化初始聚類中心的K-medoids 聚類算法[J].計算機科學與探索，2015，9（5）：611-620.