一種新的k-medoids聚類算法

姚麗娟，羅可，孟穎

長(zhǎng)沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，長(zhǎng)沙 410114

一種新的k-medoids聚類算法

姚麗娟，羅可，孟穎

長(zhǎng)沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，長(zhǎng)沙 410114

1 引言

聚類是一個(gè)將數(shù)據(jù)集劃分成若干組或類的過(guò)程，它使得同一個(gè)組內(nèi)的數(shù)據(jù)對(duì)象具有較高的相似度，而不同組中數(shù)據(jù)對(duì)象則不相似，相似或不相似通常可利用距離進(jìn)行度量。聚類已成為數(shù)據(jù)挖掘的一個(gè)重要研究領(lǐng)域[1]。

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

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

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

2 k-medoids算法介紹及分析

典型的k-中心點(diǎn)算法描述如下：

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

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

處理流程為：

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

步驟2指派每個(gè)剩余的對(duì)象給離它最近的中心點(diǎn)所代表的簇；

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

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

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

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

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

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

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

密度初始化流程為：

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

在S中取最大密度點(diǎn)作為第一個(gè)聚類中心Z1，并從S中刪除：

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

3 算法的改進(jìn)思想

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

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

在密度初始化流程中通過(guò)計(jì)算每個(gè)樣本之間的距離來(lái)確定每個(gè)樣本的密度，因此可以在此階段實(shí)行一種機(jī)制：

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

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

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

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

因?yàn)槊芏认嘟狞c(diǎn)很大程度上都屬于同一聚類，且離最優(yōu)中心點(diǎn)最近。這樣的迭代過(guò)程避免了盲目地在所有樣本中尋找最優(yōu)中心點(diǎn)，這種改進(jìn)策略很大程度上降低了時(shí)間復(fù)雜度。

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

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

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

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

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

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

3.3 新算法描述

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

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

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

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

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

（2）根據(jù)當(dāng)前的中心點(diǎn)對(duì)其他對(duì)象進(jìn)行初始聚類劃分。

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

步驟3輸出最終的k個(gè)中心點(diǎn)及聚類劃分。

3.4 算法分析

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

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

3.5 參數(shù)分析

聚類的一個(gè)難點(diǎn)是算法要適應(yīng)各種情況，聚類參數(shù)則是根據(jù)實(shí)驗(yàn)和經(jīng)驗(yàn)來(lái)進(jìn)行確定，參數(shù)θ的經(jīng)驗(yàn)值一般為0＜θ＜1。

MDensity參數(shù)體現(xiàn)了候選解范圍的大小，過(guò)大會(huì)因?yàn)榈螖?shù)較多導(dǎo)致時(shí)間復(fù)雜度高，而過(guò)小會(huì)因?yàn)槭諗枯^快導(dǎo)致聚類精度較低。因此，MDensity參數(shù)需要根據(jù)實(shí)際樣本的平均密度進(jìn)行計(jì)算得到。

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

4 算法仿真與性能分析

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

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

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

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

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

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

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

圖2 k=4時(shí)的樣本聚類圖

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

圖4 各算法聚類收斂圖

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

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

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

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

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

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

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

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

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

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

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

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

[1]Han Jiawei，Kamber M.數(shù)據(jù)挖掘：概念與技術(shù)[M].范明，譯.北京：機(jī)械工業(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聚類的自適應(yīng)話題追蹤技術(shù)[J].計(jì)算機(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].控制理論與應(yīng)用，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]孫勝，王元珍.基于核的自適應(yīng)k-medoid聚類[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（3）：674-677.

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

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

[15]夏寧霞，蘇一丹，譚希.一種高效的k-medoids聚類算法[J].計(jì)算機(jī)應(yīng)用研究，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

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

聚類；k-medoids算法；密度初始化；目標(biāo)函數(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.

國(guó)家自然科學(xué)基金（No.11171095，No.10871031）；湖南省自然科學(xué)衡陽(yáng)聯(lián)合基金（No.10JJ8008）；湖南省教育廳重點(diǎn)項(xiàng)目（No.10A015）；湖南省科技計(jì)劃項(xiàng)目（No.2011FJ3051）。

姚麗娟（1986—），女，碩士，主要研究方向?yàn)閿?shù)據(jù)挖掘，計(jì)算機(jī)應(yīng)用；羅可（1961—），男，博士，教授，研究方向?yàn)閿?shù)據(jù)挖掘，計(jì)算機(jī)應(yīng)用等；孟穎（1984—），女，碩士，主要研究方向?yàn)閿?shù)據(jù)挖掘，計(jì)算機(jī)應(yīng)用。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