基于優(yōu)化粒計(jì)算下微粒子動(dòng)態(tài)搜索的K—medoids聚類算法

宋紅海 顏宏文

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

關(guān)鍵字：聚類；K-medoids算法；粒計(jì)算；相似性；微粒子動(dòng)態(tài)搜索

文獻(xiàn)標(biāo)志碼： A 中圖分類號(hào)：TP301.6文章編號(hào)：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 引言

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

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

綜上可知，各研究文獻(xiàn)從不同方面對(duì)K-medoids算法實(shí)施了改進(jìn)與優(yōu)化，并已取得了一定的成果，但也存在明顯的局限性，具體就是時(shí)間復(fù)雜度和準(zhǔn)確度不能兼顧：有些以增加時(shí)間復(fù)雜度為代價(jià)來(lái)提高準(zhǔn)確度，有些是以犧牲準(zhǔn)確度來(lái)降低時(shí)間復(fù)雜度；還有一些則只是針對(duì)某種特定的數(shù)據(jù)。基于此，在現(xiàn)有粒計(jì)算的基礎(chǔ)上，本文提出了一種基于優(yōu)化粒計(jì)算初始化，微粒子動(dòng)態(tài)搜索的K-medoids算法。

1 傳統(tǒng)的K-medoids算法

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

基于粒計(jì)算初始化步驟如下：

3 算法的改進(jìn)

3.1 粒計(jì)算的改進(jìn)

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

4.2基于微粒子動(dòng)態(tài)搜索

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

3.2.1 新概念

粒子中對(duì)象到其中心的平均距離，對(duì)其數(shù)學(xué)定義可表述為：

其中， 是粒子 中對(duì)象 與中心 的歐氏距離， 是粒子 所包含對(duì)象的個(gè)數(shù)。

定義5 微粒子：以某一對(duì)象為基點(diǎn)，粒子中所有對(duì)象到粒子中心的平均距離為半徑r，這樣包含若干個(gè)對(duì)象的封閉區(qū)域。

3.2.2 微粒子搜索過程

以初始化中心 為基點(diǎn)，粒子 中所有對(duì)象 的平均距離 為半徑，這樣形成的圓區(qū)域內(nèi)所包含的對(duì)象為一個(gè)微粒子；在微粒子內(nèi)，以離初始化中心點(diǎn) 最近的對(duì)象作為新的聚類中心，根據(jù)準(zhǔn)則函數(shù)可進(jìn)行如下判斷：

若新的準(zhǔn)則函數(shù) 小于原準(zhǔn)則函數(shù) ，即 ，則用新的聚類中心點(diǎn)代替原中心點(diǎn)；再以新的聚類中心點(diǎn)為基點(diǎn)， 為半徑，形成新的微粒子，在新的微粒子中應(yīng)用上述搜索策略。

若新的準(zhǔn)則函數(shù) 大于原準(zhǔn)則函數(shù) ，即 ，則中心點(diǎn)不變；采取先近后遠(yuǎn)的原則，以離初始化中心點(diǎn) 次近的對(duì)象作為新的聚類中心點(diǎn)，計(jì)算準(zhǔn)則函數(shù)。

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

改進(jìn)算法的實(shí)現(xiàn)過程可具體描述如下：

綜上所述，實(shí)驗(yàn)從改進(jìn)算法的準(zhǔn)確率和收斂時(shí)間兩個(gè)方面，與其他算法進(jìn)行了對(duì)比。由實(shí)驗(yàn)可知文中算法能夠收斂于最佳中心或最相似中心，提高了聚類的準(zhǔn)確率和縮短了其運(yùn)行的時(shí)間，尤其在相對(duì)較大的數(shù)據(jù)集上，文中算法的聚類效果明顯優(yōu)于其他算法。

5 結(jié)束語(yǔ)

K-medoids算法具有對(duì)初始聚類中心敏感，聚類準(zhǔn)確度不高及時(shí)間復(fù)雜度大的缺點(diǎn)。文中提出了一種新的K-medoids算法，該算法采用改進(jìn)的粒計(jì)算來(lái)克服K-medoids算法對(duì)初始化敏感問題，使用基于微粒子動(dòng)態(tài)搜索策略改善了K-medoids算法全局搜索的能力，提高了算法精確度，同時(shí)也縮短了其收斂的時(shí)間。文中算法與其他改進(jìn)的K-medoids算法作了對(duì)比，通過對(duì)比驗(yàn)證了文中算法的可行性與有效性。

參考文獻(xiàn)：

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

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

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

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

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

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

[7]陶新民，徐晶，楊立標(biāo)等.一種改進(jìn)的粒子群和 K均值混合聚類算法[J].電子與信息學(xué)報(bào)，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.數(shù)據(jù)挖掘：概念與技術(shù)[M].范明，譯.北京：機(jī)械工業(yè)出版社，2012：293-297.

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

[11]王國(guó)胤，張清華，胡軍.粒計(jì)算研究綜述[J].智能系統(tǒng)學(xué)報(bào)，2007，2（6）：8-26.

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

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

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

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