姚麗娟，羅可，孟穎

長沙理工大學計算機與通信工程學院，長沙 410114

一種新的k-medoids聚類算法

姚麗娟，羅可，孟穎

長沙理工大學計算機與通信工程學院，長沙 410114

1 引言

聚類是一個將數(shù)據(jù)集劃分成若干組或類的過程，它使得同一個組內(nèi)的數(shù)據(jù)對象具有較高的相似度，而不同組中數(shù)據(jù)對象則不相似，相似或不相似通?？衫镁嚯x進行度量。聚類已成為數(shù)據(jù)挖掘的一個重要研究領域[1]。

k-medoids算法[2-3]由于算法簡單，收斂速度快及局部搜索能力強的優(yōu)點被應用到了很多方面[4]。但是該算法依然存在對初值敏感，時間復雜度高，不適應大數(shù)據(jù)集和形狀不規(guī)則的數(shù)據(jù)集等問題。而且該算法是基于梯度下降的[5-6]，因此，常常不可避免地使目標函數(shù)陷入局部極值，甚至會出現(xiàn)退化解和無解的情況。鑒于此，最近許多學者提出了很多改進的算法：文獻[7-8]提出一個基于最小支撐樹的聚類中心初始化方法，克服了Stephen J.Redmond給出的方法在估計密度方面的缺陷，但是增加了時間復雜度；文獻[9]提出基于“metric access method”的方法，提高了聚類的正確率但也增加了額外的開銷；文獻[10]通過計算各個對象之間的距離選擇初始中心點，并將中心點替換的范圍局限于簇類，提高了算法的效率，但降低了聚類的正確率；文獻[11]通過密度信息來產(chǎn)生初始中心，但它是以犧牲時間復雜度來換取較好的搜索性能，從而提高聚類效果；文獻[12]采用基于核的自適應聚類，克服了k-medoids對初始值的敏感性問題，但是沒有降低時間復雜度；文獻[13]提出了將局部搜索過程嵌入到迭代局部搜索過程中的方法，顯著減少了計算時間，但提高聚類效果沒有得到提高。

上述文獻中有些改進算法解決了初值敏感問題但時間復雜度卻較高，有些能降低時間復雜度卻對初值較較敏感，且都沒有從實質(zhì)上解決k-medoids算法聚類精度的問題，同時也沒有解決高維數(shù)據(jù)集及形狀不規(guī)則數(shù)據(jù)的聚類問題。

因此，本文提出一種能提高聚類精度的改進算法：（1）采用密度初始化，以克服k-medoids中存在的初值敏感問題；（2）基于密度的迭代搜索策略降低時間復雜度；（3）采用加權優(yōu)化的準則函數(shù)進一步提高聚類精度。

2 k-medoids算法介紹及分析

典型的k-中心點算法描述如下：

輸入：簇的數(shù)目k，包含n個對象的數(shù)據(jù)集。

輸出：滿足平方差最小的k個聚類中心及劃分的k個聚類。

處理流程為：

步驟1從n個對象的數(shù)據(jù)集中隨機選擇k個對象作為初始的中心點；

步驟2指派每個剩余的對象給離它最近的中心點所代表的簇；

步驟3按照平方差函數(shù)值減少的原則，更新每個簇的中心點；

步驟4重復執(zhí)行步驟2和步驟3，直到每個聚類不再發(fā)生變化為止。

平方差函數(shù)可以定義為：

其中，p為類Ci中的樣本，Oj為聚類中心（p和Oj均是多維的）。

由于k-medoids聚類算法具有對初值敏感的缺點，不少學者提出基于密度思想的聚類[14]，具體表述如下。

取相隔距離較遠的k個處于高密度區(qū)域的點作為中心點，則樣本x的密度為：

Density(x)={p∈C|dist(x，p)≤r}（2）dist為某種距離度量，r為半徑，C為樣本集，公式（2）表示為以x為中心點，r為半徑組成的球體所包含的樣本數(shù)；其中r設定為r=u×θ，θ為用戶給定常數(shù)，u為兩兩數(shù)據(jù)對象距離的均值，可以表述為：

密度初始化流程為：

（1）每個樣本的密度計算出后，將密度大于平均密度的樣本放于集合S，S表述為：

在S中取最大密度點作為第一個聚類中心Z1，并從S中刪除：

公式（5）～（9）中變量i的取值均為1，2，…，n。

3 算法的改進思想

3.1 基于密度的迭代搜索策略

k-medoids算法因步驟3中心點的替代策略導致時間復雜度較高，計算代價也較大，因此很難適應到大數(shù)據(jù)和高維數(shù)據(jù)，為了解決這一問題，引入了一種基于密度的迭代搜索策略。該策略是在高密度區(qū)域內(nèi)進行中心點的更新，即中心點的候選范圍為最初的高密度區(qū)域。

在密度初始化流程中通過計算每個樣本之間的距離來確定每個樣本的密度，因此可以在此階段實行一種機制：

（1）記錄所有樣本的歐氏距離矩陣（相似度矩陣），記為D；

（2）記錄和初始中心點密度相近的k個矩陣，分別為M1，M2，…，Mk：

Mi={p∈S|dist(ki，p)≤MDensity}（10）公式（10）表示以ki為中心，MDensity為半徑的點集，分別記為M1，M2，…，Mk，其中ki表示第i個中心點，S表示高密度點集。

每次迭代過程都在M1，M2，…，Mk個矩陣內(nèi)進行，即每簇候選中心點優(yōu)先在M1，M2，…，Mk個矩陣中選擇，直到滿足搜索條件為止；若都不滿足，則考慮其他候選中心點。

因為密度相近的點很大程度上都屬于同一聚類，且離最優(yōu)中心點最近。這樣的迭代過程避免了盲目地在所有樣本中尋找最優(yōu)中心點，這種改進策略很大程度上降低了時間復雜度。

相似度矩陣D的記錄，也減少了k-medoids算法在劃分簇時計算樣本到簇中心距離的時間，而只需從D中查找相應樣本的距離，從而減少計算時間。

3.2 準則函數(shù)優(yōu)化

大多數(shù)聚類主要表現(xiàn)在：每類的內(nèi)部距離應該盡量近，而各類之間的距離應該盡量遠。但是一般算法都是將類內(nèi)距離和最小作為準則函數(shù)，沒有考慮到聚類總體質(zhì)量是類內(nèi)距離和類間距離共同決定的?；谶@一思想，本文提出一種基于加權的準則函數(shù)作為k-medoids算法的目標函數(shù)，能有效地均衡類間距離和類內(nèi)距離的不協(xié)調(diào)性。當基于加權的均衡化函數(shù)達到最小時，將得到最優(yōu)的空間聚類結果。

類間距離b(c)定義為不同聚類中心點間的距離，可以表述為：

基于加權優(yōu)化的準則函數(shù)采用類內(nèi)距離和類間距離共同決定，則準則函數(shù)可以表示為：

其中，w1、w2為加權系數(shù)，且w1+w2=1；w1、w2加權系數(shù)設定的目的是：對于那些聚類效果不明顯、數(shù)據(jù)形狀不規(guī)則的數(shù)據(jù)集，必須在w1、w2達到某種關系的情況下，聚類效果才達到最好。

3.3 新算法描述

下面給出新算法的主要步驟：

輸入：包含n個數(shù)據(jù)對象的樣本數(shù)據(jù)庫，參數(shù)k，θ，w1，w2值；

輸出：k個聚類中心及最優(yōu)聚類。

步驟1選擇、優(yōu)化初始中心并做初步聚類劃分：

（1）根據(jù)相似度矩陣D和密度初始化方法找出k個初始中心點，并記錄M1，M2，…，Mk；

（2）根據(jù)當前的中心點對其他對象進行初始聚類劃分。

步驟2執(zhí)行基于密度的迭代過程：

步驟3輸出最終的k個中心點及聚類劃分。

3.4 算法分析

本文算法采用密度初始化方法找到接近最終聚類中心的初始中心點，之后的迭代過程就可以簡化；同樣考慮每個聚類中心往往都是處于高密度區(qū)域，在迭代過程中中心點的替換范圍可以限制在與初始中心點密度相近的高密度區(qū)域之內(nèi)，則迭代次數(shù)明顯降低，在大數(shù)據(jù)集上尤為明顯。采用加權優(yōu)化的準則函數(shù)判斷聚類是否達到收斂，進一步提高聚類的準確率。

在時間復雜度方面，起決定作用的是步驟2，在這個階段，新算法進行k次搜索的范圍是不同的。對于在數(shù)據(jù)分布均勻的情況下，可以確定每個中心點候選范圍在[2，(n-k)/k]內(nèi)，再根據(jù)公式（4）的計算，可以縮小范圍，則表示為[2，d1/k](d1?n-k)。根據(jù)算法流程，在進行第i(i=1，2，…，k)輪替換時，此時中心點候選范圍Mi中數(shù)據(jù)點的數(shù)量最大為d1/k個。在中心點替換過程中，對其余n-k個數(shù)據(jù)對象進行劃分，需進行k次，所以時間復雜度為O(d1×(n-k))。而根據(jù)步驟2，整個替換過程需要進行k次，則總的時間復雜度可以為O(k×d1×(n-k))，由于d1?n-k，所以時間復雜度可以表述為O(k(n-k))，與傳統(tǒng)k-medoids算法的時間復雜度O(k(n-k)2)相比，小一個數(shù)量級，明顯降低了時間復雜度。

3.5 參數(shù)分析

聚類的一個難點是算法要適應各種情況，聚類參數(shù)則是根據(jù)實驗和經(jīng)驗來進行確定，參數(shù)θ的經(jīng)驗值一般為0＜θ＜1。

MDensity參數(shù)體現(xiàn)了候選解范圍的大小，過大會因為迭代次數(shù)較多導致時間復雜度高，而過小會因為收斂較快導致聚類精度較低。因此，MDensity參數(shù)需要根據(jù)實際樣本的平均密度進行計算得到。

w1、w2對于數(shù)據(jù)形狀規(guī)則的數(shù)據(jù)集一般相差不大，幾乎都接近0.5。但是對于形狀不規(guī)則的數(shù)據(jù)，w1、w2體現(xiàn)了數(shù)據(jù)集的不規(guī)則程度，且影響準則函數(shù)E的大小，最終決定了聚類的準確率。因此，根據(jù)不同的數(shù)據(jù)集需要設置不同的w1、w2，但w1、w2必須滿足w1+w2=1的關系，使聚類效果達到最好并能提高算法的適應性。

4 算法仿真與性能分析

為了檢驗該算法的有效性，采用傳統(tǒng)的k-medoids算法及部分改進算法與本文算法進行實驗對比，且在聚類效果和算法收斂時間兩方面進行比較。

仿真環(huán)境：操作系統(tǒng)Windows 7，編譯軟件Matlab7.0.1；Pentium?Dual-Core CPU T4200@2.00 GHz，內(nèi)存為2 GB。

（1）樣本數(shù)據(jù)：下面給出一個樣本數(shù)據(jù)庫（如表1），并對它實施本文改進的k-medoids算法。

表1中有24個樣本對象，為了表現(xiàn)樣本數(shù)據(jù)庫的空間效果，把表中的屬性對應到坐標軸上，如圖1所示。為了驗證加權準則函數(shù)的高效性，圖3給出了各個準則函數(shù)的趨勢圖說明w(c)、b(c)與加權準則函數(shù)之間的關系。按照改進的算法，當k=4時，加權準則函數(shù)值最小E=28.23，且w(c)=18.12，b(c)=34.17。圖2給出當k=4時聚類的結果，m0、m1、m2、m3分別為各類的中心點，與樣本數(shù)據(jù)庫的最優(yōu)結果相吻合。

分析：當k=4時，加權準則函數(shù)值最小，其中準則函數(shù)由類內(nèi)距離和類間距離兩部分組成，且與類間距離和類內(nèi)距離保持一定關系。圖3給出加權準則函數(shù)和類間距離、類內(nèi)距離的趨勢圖。加權準則函數(shù)最小值對應的k值為4，即樣本數(shù)據(jù)庫的最優(yōu)聚類數(shù)目，其中類內(nèi)距離隨著k值的增大呈下降趨勢。在該實驗中k越大，類的數(shù)目就越多，類所含的樣本對象數(shù)目就越少，影響也隨之減小，因此類間距離是呈下降趨勢的，并且在k值比較小的情況下，其變化速度比較快。而類間距離隨著k值的增大呈上升趨勢，并且當k等于樣本個數(shù)時，類間距離達到最大，因為這時每個對象都是一個類，類內(nèi)距離已經(jīng)為零。而加權準則函數(shù)均衡了類內(nèi)距離和類間距離對樣本對象造成的影響，符合最優(yōu)聚類的結果。

表1 樣本數(shù)據(jù)庫

圖1 樣本數(shù)據(jù)

圖2 k=4時的樣本聚類圖

圖4表示樣本數(shù)據(jù)庫中，在k=4的情況下不同算法準則函數(shù)的收斂時間圖。從圖中可以看出，在開始的時候，本文算法的加權準則函數(shù)E值均比其他算法采用的準則函數(shù)都要小，說明采用密度初始化中心點效果明顯，此時的中心點離最終的中心點較近。隨著聚類迭代的推進，E加權準則函數(shù)在0.4 s就已經(jīng)收斂，達到最終的聚類，說明采用基于密度迭代的搜索策略能減少聚類時間和迭代次數(shù)并有效聚類。而其余三種算法均采用隨機初始中心，因此最初準則函數(shù)值較大，IKMD算法采用在各簇內(nèi)選擇候選中心點，一定程度上也減少了算法收斂時間。算法2[15]采用增量式的思想擴大搜索范圍，效果比IKMD算法好，但是相比于本文算法，收斂時間還是較長。

圖4 各算法聚類收斂圖

（2）標準數(shù)據(jù)集：Iris、Wine及Breast Cancer數(shù)據(jù)集，每類數(shù)據(jù)集介紹如表2所示。

表2 各數(shù)據(jù)集的參數(shù)比較

在上述三個數(shù)據(jù)集中，Iris、Wine及Breast Cancer（BC）的數(shù)據(jù)類型為區(qū)間標度變量，用歐氏距離度量數(shù)據(jù)庫中對象之間的相異度。

通過30實驗，本文提到的用戶自定義參數(shù)設置如下則效果最好：

本文算法和原始k-medoids、部分改進算法及k-means的改進算法進行比較，結果如表3～表5。

表3 各算法在Iris數(shù)據(jù)集的正確率和收斂時間比較

表4 各算法在Wine數(shù)據(jù)集的正確率和收斂時間比較

表5 各算法在Breast Cancer數(shù)據(jù)集的正確率和收斂時間比較

從表3、表4和表5可以看出，三種不同類型的數(shù)據(jù)集，聚類正確率及收斂時間都有所提高。Iris和Wine數(shù)據(jù)集最好正確率都達到97%以上，且多次實驗的結果都比較平穩(wěn)，波動范圍幾乎都控制在5%以內(nèi)，聚類效果較好。在BC數(shù)據(jù)集中收斂時間大幅度減少，遠遠小于IKMD算法和算法2的收斂時間，并提高了正確率。

綜上所述，在同樣的實驗條件下，針對不同的數(shù)據(jù)集，本文算法既能保證聚類性能又能大幅度提高算法效率；對于不同形狀的數(shù)據(jù)集具有較好的適應性；對數(shù)據(jù)集中的噪音數(shù)據(jù)具有較好的抗干擾能力，聚類效果較穩(wěn)定。上述實驗結果驗證了本文算法的可行性和有效性，并能適應多維大數(shù)據(jù)集。

5 結束語

提出一種新k-medoids聚類算法，在分析聚類特性的基礎上給出基于加權的準則函數(shù)，與傳統(tǒng)評價函數(shù)不同，該函數(shù)對類內(nèi)和類間差異進行有效權衡，使得算法的有效性得到充分的發(fā)揮；同時在中心點替換過程中采用基于密度迭代的搜索策略，很大程度上降低了算法的計算量。本文算法輸入的參數(shù)較少，時間復雜度低，能對任何形狀、不同分布特性、不同密度、不同大小的數(shù)據(jù)進行聚類。與k-medoids算法及其相關改進算法相比，本文算法具有較強的適應性，適合大規(guī)模的數(shù)據(jù)集，且執(zhí)行效率較高，聚類結果穩(wěn)定。但是本文算法還存在以下問題：（1）w1、w2參數(shù)能否自適應給出；（2）算法能實現(xiàn)k值自動確定，但是在大數(shù)據(jù)集的情況下本文算法沒有討論。這將是下一步的研究重點。

[1]Han Jiawei，Kamber M.數(shù)據(jù)挖掘：概念與技術[M].范明，譯.北京：機械工業(yè)出版社，2007-03.

[2]Chen Xinquan，Peng Hong，Hu Jingsong.K-medoids subatitution clustering method and a new clustering validity index method[C]// Proc of 6th World Congress on Intelligent Control and Automation，2006：5896-5900.

[3]任曉東，張永奎，薛曉飛.基于K-Mode聚類的自適應話題追蹤技術[J].計算機工程，2009，35（9）：222-224.

[4]Mishra N，Motwani R.Optimal time bounds for approximata clustering[J].Machine Learning，2004，56：35-60.

[5]Ben-David S.A k-median algorithm with running time independent of data size[J].Machine Learning，2004，56：61-87.

[6]Har-Peled S，Kushal A.Smaller coresets for k-median and k-means clustering[J].Discrete Comput Geom，2007，37：3-19.

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

[8]Gao Danyang，Yang Bingru.An impronved K-medoids clustering algorithm[C]//Proc of the 2nd International Conference on Computer and Autonmation Engineering（ICCAE），2010：132-135.

[9]Barioni C N M，Razente H L，Traina A J M，et al.Acceleration K-medoids-based algorithms through metric access method[J]. Jourmal of Systerm and Software，2008，81（3）：343-355.

[10]Park H S，Jun C H.A simple and fast algorithm for k-medoids clusting[J].Expert Systerm with Applications，2009，36（2）：3336-3341.

[11]Pardeshi B，Toshniwal D.Improved K-medoids clustering based on cluster validity index and object density[C]//Proc of the 2ndIEEEInternational AdvanceComputingConference，2010：379-384.

[12]孫勝，王元珍.基于核的自適應k-medoid聚類[J].計算機工程與設計，2009，30（3）：674-677.

[13]吳景嵐，朱文興.基于k中心點的迭代局部搜索聚類算法[J].計算機研究與發(fā)展，2004，41：246-252.

[14]孫秀娟，劉希玉.基于初始中心優(yōu)化的遺傳k-means聚類新算法[J].計算機工程與應用，2008，44（23）：166-168.

[15]夏寧霞，蘇一丹，譚希.一種高效的k-medoids聚類算法[J].計算機應用研究，2010，27（12）：4517-4519.

YAO Lijuan,LUO Ke,MENG Ying

Institute of Computer and Communication Engineering,Changsha University of Sciences and Technology,Changsha 410114,China

For the disadvantages that sensitivity to centers initialization,lower clustering accuracy and slow convergent speed ofk-medoids algorithm,a novelk-medoids algorithm based on density initialization,density of iterative search strategy and optimization criterion function is proposed.The Initialization of the algorithm is that,it chooses k cluster centers in the high-density area which are far apart,effectively positioning of the final cluster center.To replace the centers are in the ranges which are proximity to thek-initial centers,to reduce the scope of the search candidate point.Criterion function of equalization based on class density and within-class density weighted is adopted to improve the clustering precision.Experimental results show that this algorithm can improve the clustering quality,shorten the clustering time compared with traditionalk-medoids algorithms or other improved algorithms.

clustering;k-medoids algorithm;density initialization;criterion function

針對k-medoids算法對初始聚類中心敏感，聚類精度較低及收斂速度緩慢的缺點，提出一種基于密度初始化、密度迭代的搜索策略和準則函數(shù)優(yōu)化的方法。該算法初始化是在高密度區(qū)域內(nèi)選擇k個相對距離較遠的樣本作為聚類初始中心，有效定位聚類的最終中心點；在k個與初始中心點密度相近的區(qū)域內(nèi)進行中心點替換，以減少候選點的搜索范圍；采用類間距和類內(nèi)距加權的均衡化準則函數(shù)，提高聚類精度。實驗結果表明，相對于傳統(tǒng)的k-mediods算法及某些改進算法，該算法可以提高聚類質(zhì)量，有效縮短聚類時間。

聚類；k-medoids算法；密度初始化；目標函數(shù)

A

TP391.4

10.3778/j.issn.1002-8331.1112-0644

YAO Lijuan,LUO Ke,MENG Ying.New k-medoids clustering algorithm.Computer Engineering and Applications, 2013,49（19）：153-157.

國家自然科學基金（No.11171095，No.10871031）；湖南省自然科學衡陽聯(lián)合基金（No.10JJ8008）；湖南省教育廳重點項目（No.10A015）；湖南省科技計劃項目（No.2011FJ3051）。

姚麗娟（1986—），女，碩士，主要研究方向為數(shù)據(jù)挖掘，計算機應用；羅可（1961—），男，博士，教授，研究方向為數(shù)據(jù)挖掘，計算機應用等；孟穎（1984—），女，碩士，主要研究方向為數(shù)據(jù)挖掘，計算機應用。E-mail：yaolijuan1986@163.com

2012-01-11

2012-03-26

1002-8331（2013）19-0153-05

CNKI出版日期：2012-05-22http://www.cnki.net/kcms/detail/11.2127.TP.20120522.1316.012.html