密度峰值優(yōu)化初始中心的K-medoids聚類算法*

謝娟英，屈亞楠

陜西師范大學(xué) 計算機科學(xué)學(xué)院，西安 710062

密度峰值優(yōu)化初始中心的K-medoids聚類算法*

謝娟英+，屈亞楠

陜西師范大學(xué) 計算機科學(xué)學(xué)院，西安 710062

針對快速K-medoids聚類算法和方差優(yōu)化初始中心的K-medoids聚類算法存在需要人為給定類簇數(shù)，初始聚類中心可能位于同一類簇，或無法完全確定數(shù)據(jù)集初始類簇中心等缺陷，受密度峰值聚類算法啟發(fā)，提出了兩種自適應(yīng)確定類簇數(shù)的K-medoids算法。算法采用樣本xi的t最近鄰距離之和倒數(shù)度量其局部密度ρi，并定義樣本xi的新距離δi，構(gòu)造樣本距離相對于樣本密度的決策圖。局部密度較高且相距較遠的樣本位于決策圖的右上角區(qū)域，且遠離數(shù)據(jù)集的大部分樣本。選擇這些樣本作為初始聚類中心，使得初始聚類中心位于不同類簇，并自動得到數(shù)據(jù)集類簇數(shù)。為進一步優(yōu)化聚類結(jié)果，提出采用類內(nèi)距離與類間距離之比作為聚類準(zhǔn)則函數(shù)。在UCI數(shù)據(jù)集和人工模擬數(shù)據(jù)集上進行了實驗測試，并對初始聚類中心、迭代次數(shù)、聚類時間、Rand指數(shù)、Jaccard系數(shù)、Adjusted Rand index和聚類準(zhǔn)確率等經(jīng)典聚類有效性評價指標(biāo)進行了比較，結(jié)果表明提出的K-medoids算法能有效識別數(shù)據(jù)集的真實類簇數(shù)和合理初始類簇中心，減少聚類迭代次數(shù)，縮短聚類時間，提高聚類準(zhǔn)確率，并對噪音數(shù)據(jù)具有很好的魯棒性。

聚類；K-medoids算法；初始聚類中心；密度峰值；準(zhǔn)則函數(shù)

1　引言

聚類基于“物以類聚”原理將一組樣本按照相似性歸成若干類簇，使得屬于同一類簇的樣本之間差別盡可能小，而不同類簇的樣本間差別盡可能大。聚類算法包括基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法[1]。經(jīng)典的劃分式聚類算法包括K-means算法[2]和K-medoids算法[3]。K-medoids算法克服了K-means算法對孤立點敏感的缺陷，PAM（partitioningaroundmedoids）算法[3-4]是最經(jīng)典的K-medoids算法。然而，K-medoids算法同K-means算法一樣，存在著聚類結(jié)果隨初始聚類中心改變而變化的問題。

快速K-medoids算法[5]從初始聚類中心選擇和聚類中心更迭兩方面對PAM算法進行改進，取得了遠優(yōu)于PAM算法的聚類效果。然而快速K-medoids算法選擇的初始聚類中心可能位于同一類簇。鄰域K-medoids聚類算法[6]提出鄰域概念，使選擇的初始聚類中心盡可能位于不同樣本分布密集區(qū)，得到了優(yōu)于快速K-medoids算法的聚類效果，但該算法的鄰域半徑需要人為設(shè)定。引入粒度概念，定義粒子密度，選擇密度較大的前K個粒子的中心樣本作為K-medoids算法的初始聚類中心，得到了更好的初始聚類中心和聚類結(jié)果，且避免了文獻[6]主觀選擇鄰域半徑的缺陷[7-8]。但是基于粒計算的K-medoids算法[7]構(gòu)造樣本去模糊相似矩陣時需要人為給定閾值。粒計算優(yōu)化初始聚類中心的K-medoids算法將粒計算與最大最小距離法結(jié)合[9]，且使用所有樣本的相似度均值作為其構(gòu)造去模糊相似度矩陣的閾值，改進了文獻[7]需要人為設(shè)定閾值進行模糊相似矩陣去模糊操作的缺陷。文獻[10]中算法完全依賴數(shù)據(jù)集自身的分布信息，以方差作為樣本分布密集程度度量，分別以樣本間距離均值和相應(yīng)樣本標(biāo)準(zhǔn)差為鄰域半徑，選取方差值最小且其間距離不低于鄰域半徑的樣本為初始聚類中心，使K-medoids算法的初始聚類中心盡可能完全反應(yīng)數(shù)據(jù)集樣本原始分布信息，得到優(yōu)于快速K-medoids和鄰域K-medoids算法的聚類結(jié)果，且不需要任何主觀參數(shù)選擇。但是該算法當(dāng)鄰域半徑過大時，不能得到數(shù)據(jù)集真實類簇數(shù)。Rodriguez等人[11]基于聚類中心比其近鄰樣本密度高且與其他密度較高樣本的距離相對較遠的特點，提出快速搜索密度峰值聚類算法（clustering by fast search and find of density peaks，DPC），以密度峰值點樣本為類簇中心，自動確定類簇個數(shù)，并分配樣本到距離最近的密度較高樣本所在類簇實現(xiàn)聚類。但是該算法需要人為給定截斷距離參數(shù)，聚類結(jié)果隨截斷距離參數(shù)改變而波動。

本文針對快速K-medoids算法[5]和方差優(yōu)化初始中心K-medoids算法[10]的潛在缺陷，受文獻[11]啟發(fā)，提出了密度峰值優(yōu)化初始中心的K-medoids聚類算法DP_K-medoids（density peak optimized K-medoids）。DP_K-medoids算法使用樣本xi的t近鄰距離之和的倒數(shù)度量樣本xi的局部密度ρi，并定義樣本xi的距離δi為樣本xi到密度大于它的最近樣本xj的距離的指數(shù)函數(shù)，構(gòu)造樣本距離相對于樣本密度的決策圖，選擇決策圖中樣本密度ρ和樣本距離δ都較高，且明顯遠離數(shù)據(jù)集大部分樣本點的決策圖右上角的密度峰值點作為初始聚類中心，使得初始聚類中心位于不同類簇，同時自適應(yīng)地確定類簇個數(shù)。

劃分式聚類算法的思想是使類內(nèi)距離盡可能小，而類間距離盡可能大，因此本文提出以類內(nèi)距離與類間距離之比作為新聚類準(zhǔn)則函數(shù)，得到了改進DP_K-medoids算法DPNM_K-medoids（density peak optimized K-medoids with new measure）。其中類內(nèi)距離度量定義為聚類誤差平方和，類間距離定義為各類簇中心樣本距離之和。

通過UCI數(shù)據(jù)集和人工模擬數(shù)據(jù)集實驗測試，以及對不同聚類有效性指標(biāo)進行比較，結(jié)果表明本文提出的DP_K-medoids算法和DPNM_K-medoids算法均能識別數(shù)據(jù)集的類簇數(shù)，并選擇到數(shù)據(jù)集的合理初始聚類中心，有效減少了聚類迭代次數(shù)，縮短了聚類時間，提高了聚類準(zhǔn)確率。

2　基本概念

設(shè)給定含n個樣本的數(shù)據(jù)集X={x1,x2,…,xn}，每個樣本有p維特征，欲將其劃分為k個類簇Cj,j= 1,2,…,k,k＜n，第i個樣本的第 j個屬性值為xij。

3　本文K-medoids算法

本文提出密度峰值優(yōu)化初始中心的K-medoids聚類算法，主要針對快速K-medoids算法和方差優(yōu)化初始中心的K-medoids算法的缺陷展開，其主要貢獻是樣本xi的局部密度ρi采用其t最近鄰距離之和的倒數(shù)度量，樣本xi的距離δi定義為樣本xi到密度大于它的最近樣本xj的距離的指數(shù)函數(shù)，利用樣本距離相對于樣本密度的決策圖，自適應(yīng)地確定數(shù)據(jù)集類簇數(shù)和K-medoids算法的合理初始類簇中心。

3.1DP_K-medoids算法思想

針對快速K-medoids算法和方差優(yōu)化初始中心K-medoids算法需要人為設(shè)定類簇數(shù)k，以及前者初始聚類中心可能位于同一類簇，后者初始聚類中心受到鄰域半徑影響，可能不能得到數(shù)據(jù)集真實類簇數(shù)的缺陷，本文DP_K-medoids算法使用樣本的t最近鄰距離之和的倒數(shù)度量樣本xi的局部密度ρi，采用式（6）定義度量樣本xi的距離δi。以ρ為橫軸，δ為縱軸構(gòu)造樣本距離相對于樣本密度的決策圖，選擇決策圖中樣本密度ρ和樣本距離δ都較高，且明顯遠離大部分樣本點的決策圖右上角區(qū)域的密度峰值點為初始類簇中心，密度峰值點個數(shù)即為類簇數(shù)，使選擇的初始聚類中心位于不同類簇。

步驟1初始化。

（1）根據(jù)式（7）對樣本進行標(biāo)準(zhǔn)化；

（2）根據(jù)式（5）計算樣本xi的局部密度ρi，根據(jù)式（6）計算樣本xi的距離δi；

（3）構(gòu)造以ρ為橫軸，δ為縱軸的決策圖，選擇決策圖中樣本密度ρ和樣本距離δ都較高，且明顯遠離大部分樣本的右上角區(qū)域的密度峰值點為初始聚類中心，密度峰值點個數(shù)為類簇數(shù)k。

步驟2構(gòu)造初始類簇。

（1）根據(jù)距離最近原則，將其余樣本點分配到最近初始類簇中心，形成初始劃分；

（2）計算聚類誤差平方和。

步驟3更新類簇中心并重新分配樣本。

（1）為每個類簇找一個新中心，使得簇內(nèi)其余樣本到新中心距離之和最小，用新中心替換原中心；

（2）重新分配每個樣本到最近類簇中心，獲得新聚類結(jié)果，計算聚類誤差平方和；

（3）若當(dāng)前聚類誤差平方和與前次迭代聚類誤差平方和相同，則算法停止，否則轉(zhuǎn)步驟3。

3.2DPNM_K-medoids算法思想

DPNM_K-medoids使用類內(nèi)距離與類間距離之比作為聚類準(zhǔn)則函數(shù)，求聚類表達式（4）的最小優(yōu)化。當(dāng)準(zhǔn)則函數(shù)達到最小值時，得到最優(yōu)聚類結(jié)果。DPNM_K-medoids算法的初始聚類中心選擇與DP_K-medoids的初始聚類中心選擇方法相同，二者的區(qū)別在于聚類準(zhǔn)則函數(shù)不同，也就是聚類的停止條件不同。將DP_K-medoids算法的步驟2和步驟3計算聚類誤差平方和修改為計算聚類結(jié)果的新聚類準(zhǔn)則函數(shù)值，同時將步驟3中的第3小步修改為，若當(dāng)前新聚類準(zhǔn)則函數(shù)值不小于前次迭代的新聚類準(zhǔn)則函數(shù)值，則算法停止，否則轉(zhuǎn)步驟3繼續(xù)執(zhí)行，便得到DPNM_K-medoids算法。

3.3本文K-medoids算法分析

K-medoids算法的時間復(fù)雜度由初始聚類中心選擇和聚類中心更迭兩部分組成。密度峰值聚類算法的時間復(fù)雜度由初始聚類中心選擇和樣本分配兩部分組成。

本文DP_K-medoids和DPNM_K-medoids算法，以及密度峰值聚類算法[11]通過計算樣本局部密度和樣本距離選取初始聚類中心。由式（5）樣本局部密度計算和式（6）樣本距離計算以及密度峰值聚類算法描述[11]可見，該3種算法計算一個樣本局部密度與距離的時間復(fù)雜度均為Ο(n)，因此本文DP_K-medoids和DPNM_K-medoids算法，以及密度峰值聚類算法[11]計算所有樣本密度的時間復(fù)雜度為Ο(n2)。

快速K-medoids算法[5]通過計算樣本全局密度選取初始聚類中心。方差優(yōu)化初始中心的MD_K-medoids和SD_K-medoids算法[10]通過計算樣本方差選取初始聚類中心?？焖貹-medoids算法[5]和方差優(yōu)化初始中心的K-medoids算法[10]計算一個樣本密度的時間復(fù)雜度分別為Ο(n2)和Ο(n)，因此快速K-medoids算法計算所有樣本密度的時間復(fù)雜度為Ο(n3)，方差優(yōu)化初始中心的K-medoids算法計算所有樣本方差的時間復(fù)雜度為Ο(n2)。

本文兩種K-medoids算法、快速K-medoids算法[5]、方差優(yōu)化初始中心的MD_K-medoids和SD_K-medoids算法[10]聚類中心更迭的時間復(fù)雜度均為Ο(nk×iter)，其中iter為算法迭代次數(shù)，n為樣本數(shù)，k為類簇數(shù)。密度峰值聚類算法[11]在獲得初始聚類中心后，將其余樣本分配給密度比它大的最近鄰樣本所在類簇，因此樣本分配時間復(fù)雜度為Ο(n)。

因此，本文DP_K-medoids和DPNM_K-medoids算法，以及方差優(yōu)化初始中心的MD_K-medoids和SD_K-medoids算法的時間復(fù)雜度為Ο(n2+nk×iter)。快速K-medoids算法的時間復(fù)雜度為Ο(n3+nk× iter)。密度峰值聚類算法的時間復(fù)雜度為Ο(n2+n)。由此可見，盡管上述6種聚類算法的時間復(fù)雜度可統(tǒng)一表達為O(n2)數(shù)量級，但密度峰值聚類算法是該6種聚類算法中速度最快的聚類算法。

5種K-medoids算法均先獲得k個初始聚類中心，然后根據(jù)距離最近原則將其余樣本分配到最近初始聚類中心，得到初始類簇劃分。初始劃分通常不是最優(yōu)聚類結(jié)果，當(dāng)前聚類準(zhǔn)則函數(shù)值通常不是最小的。此時，進行聚類中心更迭，當(dāng)一次聚類中心更替發(fā)生，并重新分配樣本得到新類簇分布時，計算當(dāng)前分布的聚類準(zhǔn)則函數(shù)值，若比上次迭代的聚類準(zhǔn)則函數(shù)值小，則繼續(xù)迭代。經(jīng)過若干次迭代后，聚類準(zhǔn)則函數(shù)值達到最小，即聚類結(jié)果不再發(fā)生改變，聚類算法收斂到最優(yōu)解。

4　實驗結(jié)果與分析

為了測試本文K-medoids算法的性能，分別在UCI數(shù)據(jù)集和兩種人工模擬數(shù)據(jù)集上進行實驗。實驗環(huán)境是Inter?CoreTMi5-3230M CPU@2.60 GHz，4GB內(nèi)存，400GB硬盤，Matlab應(yīng)用軟件。

算法聚類結(jié)果采用迭代次數(shù)、聚類時間、聚類準(zhǔn)確率，以及外部有效性評價指標(biāo)Rand指數(shù)[12]、Jaccard系數(shù)[13-15]和Adjusted Rand index[16-17]參數(shù)進行評價。

4.1UCI數(shù)據(jù)集實驗結(jié)果與分析

本部分實驗采用UCI機器學(xué)習(xí)數(shù)據(jù)庫[18]的iris等13個聚類算法常用數(shù)據(jù)集對本文算法進行測試。所用數(shù)據(jù)集描述見表1，pid是pima indians diabetes數(shù)據(jù)集的簡寫,waveform40是waveform21增加19個噪音屬性得到的數(shù)據(jù)集。本文DP_K-medoids和DPNM_ K-medoids算法分別與快速K-medoids算法[5]、方差優(yōu)化初始中心的MD_K-medoids和SD_K-medoids算法[10]，以及密度峰值聚類算法[11]進行比較，以檢驗本文提出的密度峰值優(yōu)化初始中心的K-medoids算法的有效性。

Table 1　Datasets from UCI machine learning repository表1　UCI數(shù)據(jù)集描述

由于各數(shù)據(jù)集樣本空間分布不同，本文K-medoids算法選取的樣本最近鄰數(shù)t值也不盡相同，數(shù)據(jù)集haberman、hayes-roth、sonar、waveform21和 waveform40的樣本最近鄰數(shù)t=6，數(shù)據(jù)集pid的樣本最近鄰數(shù)t=7，其余7個UCI數(shù)據(jù)集的樣本最近鄰數(shù)t=8。密度峰值聚類算法的結(jié)果隨截斷距離參數(shù)值的改變而不同，實驗展示的是在各數(shù)據(jù)集多次實驗得到的最好聚類結(jié)果值。本文K-medoids算法在UCI數(shù)據(jù)集上的決策圖及其初始聚類中心如圖1所示，圖中矩形框內(nèi)的加粗黑圓點為所選初始聚類中心。表2是6種聚類算法對表1 UCI數(shù)據(jù)集選擇的初始聚類中心樣本。表3是6種聚類算法對表1 UCI數(shù)據(jù)集10次運行的平均迭代次數(shù)和平均聚類時間。其中，加粗字體表示相應(yīng)的最好實驗結(jié)果。密度峰值聚類算法不存在聚類中心更迭的過程，因而比較算法平均迭代次數(shù)時不將密度峰值聚類算法作為對比算法。圖2展示了6種聚類算法的Rand指數(shù)、Jaccard系數(shù)、AdjustedRandindex參數(shù)和聚類準(zhǔn)確率的平均值比較。

圖1所示實驗結(jié)果對比表1的數(shù)據(jù)集描述可以看出，本文兩種K-medoids算法能發(fā)現(xiàn)數(shù)據(jù)集的真實類簇數(shù)和相應(yīng)的初始聚類中心。因此，本文兩種K-medoids算法克服了快速K-medoids算法、MD_K-medoids算法和SD_K-medoids算法需要人為給定類簇數(shù)，及其選擇初始類簇中心時的缺陷。

Fig.1　Decision graphs and initial seeds of the proposed K-medoids algorithms on UCI datasets圖1　本文K-medoids算法對各UCI數(shù)據(jù)集的決策圖及其初始聚類中心

Table 2　Initial seeds selected by six algorithms on UCI datasets表2　6種算法在UCI數(shù)據(jù)集上選擇的初始聚類中心

Table 3　Iterations and clustering time of six algorithms on UCI datasets表3　UCI數(shù)據(jù)集上6種算法的迭代次數(shù)和聚類時間

分析表2實驗結(jié)果與各數(shù)據(jù)集真實分布可知，本文DP_K-medoids和DPNM_K-medoids算法除了在haberman、banknote、hayes-roth和sonar數(shù)據(jù)集選擇的初始聚類中心存在位于同一類簇的現(xiàn)象，在其余9個UCI數(shù)據(jù)集上選擇的初始聚類中心均位于不同類簇。快速K-medoids算法在iris、wine、pid和bupa這4個數(shù)據(jù)集選擇的初始聚類中心位于不同類簇，在其余9個數(shù)據(jù)集的初始聚類中心均存在位于同一類簇的現(xiàn)象。MD_K-medoids算法在7個數(shù)據(jù)集選擇的初始聚類中心位于不同類簇，在haberman、pid、banknote、hayes-roth、bupa和heart數(shù)據(jù)集選擇的初始聚類中心位于同一類簇。SD_K-medoids算法在haberman、banknote、hayes-roth、heart和waveform21數(shù)據(jù)集選擇的初始聚類中心位于同一類簇，在其余8個數(shù)據(jù)集選擇的初始聚類中心均位于不同類簇。密度峰值聚類算法在7個數(shù)據(jù)集選擇的初始聚類中心位于不同類簇，在haberman、pid、hayes-roth、bupa、waveform21和waveform40數(shù)據(jù)集選擇的初始聚類中心均存在位于同一類簇的現(xiàn)象。由此可見，本文提出的DP_K-medoids和DPNM_K-medoids算法選擇的初始聚類中心更好，從而可以得到較好的初始類簇劃分，加快算法收斂速度，并增加算法收斂到全局最優(yōu)解的概率。

從表3所示實驗結(jié)果可以看出，本文提出的兩種K-medoids算法在除數(shù)據(jù)集pid之外的其他12個UCI數(shù)據(jù)集上的迭代次數(shù)和運行時間都優(yōu)于其他3種K-medoids算法?？焖貹-medoids算法在pid數(shù)據(jù)集的迭代次數(shù)和聚類時間都最優(yōu)。表3實驗結(jié)果揭示，本文DPNM_K-medoids算法的迭代次數(shù)優(yōu)于DP_K-medoids算法，在迭代次數(shù)相同的情況下，本文DP_K-medoids算法的運行時間更快。分析原因是，本文DPNM_K-medoids算法采用新聚類準(zhǔn)則作為收斂性判斷依據(jù)，而DP_K-medoids算法采用聚類誤差平方和作為聚類準(zhǔn)則判斷算法是否收斂。新聚類準(zhǔn)則函數(shù)值需要更多計算時間，因此當(dāng)?shù)螖?shù)相同時，DP_K-medoids算法的運行時間更快。密度峰值聚類算法在13個UCI數(shù)據(jù)集上的聚類時間是6種聚類算法中最短的，與3.3節(jié)的算法分析結(jié)果一致。密度峰值聚類算法聚類時間最短的原因是：密度峰值聚類算法的樣本分配策略是一步分配，使其時間消耗最少。

Fig.2　Rand index,Jaccard coefficient,Adjusted Rand index and clustering accuracy of six algorithms on UCI datasets圖2　6種算法在UCI數(shù)據(jù)集上的Rand指數(shù)、Jaccard系數(shù)、Adjusted Rand index參數(shù)和聚類準(zhǔn)確率

從圖2可以看出，本文DP_K-medoids和DPNM_K-medoids聚類算法在soybean-small數(shù)據(jù)集的4個聚類有效性指標(biāo)Rand指數(shù)、Jaccard系數(shù)、Adjusted Rand index參數(shù)和聚類準(zhǔn)確率均不如方差優(yōu)化初始聚類中心的K-medoids算法和密度峰值聚類算法，但是優(yōu)于快速K-medoids算法。圖2顯示，密度峰值聚類算法在banknote數(shù)據(jù)集的4個聚類有效性指標(biāo)均值高于其余5種K-medoids算法，原因是，5種K-medoids算法對該數(shù)據(jù)集初始聚類中心確定后，均根據(jù)距離最近原則，將數(shù)據(jù)劃分為上下分布的兩個類簇；而密度峰值聚類算法根據(jù)密度較大最近鄰樣本所在類簇將數(shù)據(jù)劃分為左右分布的兩個類簇，符合banknote數(shù)據(jù)集的真實類簇分布。從圖2還可以看出，密度峰值聚類算法在數(shù)據(jù)集haberman的Rand指數(shù)、Jaccard系數(shù)和聚類準(zhǔn)確率高于其余5種K-medoids算法，Adjusted Rand index稍低于其余算法。圖2還顯示，SD_K-medoids在waveform40數(shù)據(jù)集的4個聚類有效性指標(biāo)均優(yōu)于其余算法，而密度峰值聚類算法在該數(shù)據(jù)集的各項指標(biāo)值最差。從圖2（a）可見，本文提出的兩種K-medoids算法在其他10個數(shù)據(jù)集的聚類有效性指標(biāo)都優(yōu)于其他3種K-medoids算法。圖2（b）顯示，本文K-medoids算法在8個UCI數(shù)據(jù)集的聚類有效性指標(biāo)Jaccard系數(shù)值優(yōu)于其他3種K-medoids算法；快速K-medoids算法在banknote數(shù)據(jù)集的聚類有效性指標(biāo)Jaccard系數(shù)最好，方差優(yōu)化初始聚類中心的MD_K-medoids算法在hayes-roth和bupa數(shù)據(jù)集的Jaccard系數(shù)聚類指標(biāo)最優(yōu)。圖2（c）關(guān)于各算法聚類結(jié)果的Adjusted Rand index參數(shù)比較揭示，本文算法在10/13個數(shù)據(jù)集的聚類性能最好，方差優(yōu)化初始聚類中心的MD_K-medoids算法在hayes-roth數(shù)據(jù)集的聚類效果最好。圖2（d）的聚類準(zhǔn)確率比較揭示，本文算法在8/13個數(shù)據(jù)集的聚類準(zhǔn)確率高于其他3種K-medoids算法，快速K-medoids算法在hayes-roth數(shù)據(jù)集聚類準(zhǔn)確率最高，方差優(yōu)化初始聚類中心的K-medoids算法在bupa和soybean-small數(shù)據(jù)集聚類準(zhǔn)確率最高。

綜合以上分析可知，本文提出的DP_K-medoids和DPNM_K-medoids算法能在較短時間內(nèi)實現(xiàn)對數(shù)據(jù)集的有效聚類，各項聚類有效性指標(biāo)比較揭示本文兩種K-medoids算法整體性能更優(yōu)。

4.2人工數(shù)據(jù)集實驗結(jié)果與分析

本實驗分為兩部分，分別測試本文提出的兩種K-medoids算法的魯棒性，以及其對經(jīng)典人工數(shù)據(jù)集的聚類性能。

4.2.1本文K-medoids算法魯棒性測試實驗

為測試本文算法的魯棒性，隨機生成分別含有0%、5%、10%、15%、20%、25%、30%、35%、40%、45%不同比例噪音的人工模擬數(shù)據(jù)集。每一組數(shù)據(jù)集含有4個類簇，每一類簇有100個二維樣本，這些樣本符合正態(tài)分布。其中第i類簇的均值為 μi，協(xié)方差矩陣為σi，在第一類簇加入噪音數(shù)據(jù)，噪音數(shù)據(jù)的協(xié)方差矩陣為σn，數(shù)據(jù)集的生成參數(shù)如表4所示。第一類簇分布在數(shù)據(jù)集的中間，在中間類簇加入噪音數(shù)據(jù)，使其與周圍3個類簇的樣本都有部分交疊，以更好地測試本文算法的魯棒性。

Table 4　Parameters to generate synthetic datasets表4　人工模擬數(shù)據(jù)集的生成參數(shù)

在10組含有不同比例噪音的人工模擬數(shù)據(jù)集上分別運行本文DP_K-medoids和DPNM_K-medoids算法、快速K-medoids算法、MD_K-medoids算法和SD_K-medoids算法以及密度峰值聚類算法。每個算法各運行10次，實驗結(jié)果為10次運行的平均值。表5為6種算法在各數(shù)據(jù)集選擇的初始聚類中心，表6為6種算法的迭代次數(shù)和聚類時間，圖3為6種算法對各數(shù)據(jù)集聚類結(jié)果的Rand指數(shù)、Jaccard系數(shù)、Adjusted Rand index參數(shù)和聚類準(zhǔn)確率比較。

從表5中可以看出，本文算法對該10組含噪人工模擬數(shù)據(jù)集確定的類簇數(shù)與數(shù)據(jù)集真實類簇數(shù)一致，且針對各數(shù)據(jù)集選擇的初始聚類中心分布在不同類簇。對該10組含不同比例噪音的人工模擬數(shù)據(jù)集，MD_K-medoids算法選擇的初始聚類中心均位于不同類簇，快速K-medoids算法選擇的初始聚類中心存在位于同一類簇的現(xiàn)象，SD_K-medoids算法在噪音比例為20%和25%的人工模擬數(shù)據(jù)集上選擇的初始聚類中心存在兩個中心位于同一類簇的現(xiàn)象，密度峰值聚類算法在噪音比例為30%時存在兩個類簇中心位于同一類簇的現(xiàn)象。因此，快速K-medoids算法在該10組含噪音人工模擬數(shù)據(jù)集上選擇的初始聚類中心是5種K-medoids算法中最差的，本文K-medoids算法選擇的初始聚類中心最優(yōu)，MD_K-medoids算法和SD_K-medoids算法以及密度峰值聚類算法居中。

Table 5　Initial seeds selected by six algorithms on synthetic datasets with noises表5　6種算法在帶噪音人工模擬數(shù)據(jù)集上選擇的初始聚類中心

Table 6　Iterations and clustering time of six algorithms on synthetic datasets with noises表6　帶噪音人工模擬數(shù)據(jù)集上6種算法的迭代次數(shù)和聚類時間

從表6中可以看出，本文DPNM_K-medoids算法在各噪音數(shù)據(jù)集的迭代次數(shù)最少。從聚類時間來看，本文兩種K-medoids算法優(yōu)于其他3種K-medoids算法。本文兩種K-medoids算法相比，在迭代次數(shù)相同的情況下，DP_K-medoids算法聚類時間更短，因為DPNM_K-medoids算法的聚類準(zhǔn)則函數(shù)計算更費時間。密度峰值聚類算法在帶噪音人工模擬數(shù)據(jù)集上的聚類時間是6種算法中最短的，因為密度峰值聚類算法的一步分配策略使其時間消耗最低。

從圖3的實驗結(jié)果可以看出，本文K-medoids算法在含噪音的數(shù)據(jù)集上明顯優(yōu)于其他4種聚類算法。本文DPNM_K-medoids算法在含有40%噪音的人工模擬數(shù)據(jù)集上的Rand指數(shù)、Jaccard系數(shù)、Adjusted Rand index參數(shù)和聚類準(zhǔn)確率均優(yōu)于其他5種聚類算法。密度峰值聚類算法在不帶噪音的人工模擬數(shù)據(jù)集的各項聚類指標(biāo)最優(yōu)，在噪音比例為20%、25%、35%和45%的人工模擬數(shù)據(jù)集的各項指標(biāo)值最差。由此可見，本文新提出的聚類準(zhǔn)則使得基于密度峰值點優(yōu)化初始聚類中心的K-medoids算法的聚類性能更優(yōu)，具有更強的魯棒性。

綜合表5、表6和圖3的實驗結(jié)果分析可知，本文采用密度峰值點優(yōu)化初始聚類中心的K-medoids算法對噪音具有很好的魯棒性，能發(fā)現(xiàn)數(shù)據(jù)集的真實類簇數(shù)和合理初始類簇中心，實現(xiàn)有效聚類。

Fig.3　Rand index,Jaccard coefficient,Adjusted Rand index and clustering accuracy of six algorithms on synthetic datasets with different ratio noises圖3　6種算法在不同比例噪音人工模擬數(shù)據(jù)集上的Rand指數(shù)、Jaccard系數(shù)、Adjusted Rand index參數(shù)和聚類準(zhǔn)確率

4.2.2經(jīng)典人工模擬數(shù)據(jù)集實驗結(jié)果分析

本小節(jié)采用測試聚類算法性能的經(jīng)典人工模擬數(shù)據(jù)集對本文提出的密度峰值優(yōu)化初始聚類中心的K-medoids算法的聚類性能進行測試。實驗使用的經(jīng)典人工模擬數(shù)據(jù)集原始分布如圖4所示。該經(jīng)典人工模擬數(shù)據(jù)集的共同點是：類簇個數(shù)較多，類簇形狀任意。其中S1、S2、S3和S4數(shù)據(jù)集均各含有5 000個樣本，15個類簇，數(shù)據(jù)集樣本重疊程度依次增加[19]。R15數(shù)據(jù)集也含有15個類簇，樣本數(shù)為600[20]，D31數(shù)據(jù)集含有31個類簇，樣本數(shù)為3 100[20]。

Fig.4　Original distribution of classic synthetic datasets圖4　經(jīng)典人工模擬數(shù)據(jù)集的原始分布

Fig.5　Decision graphs and initial seeds of two K-medoids algorithms on classic synthetic datasets圖5　兩種K-medoids算法對經(jīng)典人工模擬數(shù)據(jù)集的決策圖和初始聚類中心

在這些經(jīng)典人工模擬數(shù)據(jù)集上分別運行5種K-medoids聚類算法和密度峰值聚類算法，其中本文兩種K-medoids算法的最近鄰樣本數(shù)t取8。本文K-medoids算法確定初始聚類中心的決策圖如圖5所示，其中矩形框內(nèi)的加粗黑圓點為初始類簇中心。MD_K-medoids算法在S1和R15數(shù)據(jù)集僅能確定出4個初始聚類中心，在S2、S3、S4和D31數(shù)據(jù)集僅能確定出5個初始聚類中心。SD_K-medoids算法在R15數(shù)據(jù)集僅能確定出4個初始聚類中心，在S1、S2、S3和D31數(shù)據(jù)集僅能確定出5個初始聚類中心，在S4數(shù)據(jù)集能確定出6個初始聚類中心。原因是：當(dāng)被選為初始聚類中心的樣本鄰域半徑過大時，使得該樣本鄰域內(nèi)包含的樣本數(shù)過多，導(dǎo)致剩余樣本集合為空，因而無法確定足夠的初始聚類中心。因此，下面將僅比較本文DP_K-medoids、DPNM_K-medoids算法、快速K-medoids算法和密度峰值聚類算法在經(jīng)典人工模擬數(shù)據(jù)集上的聚類結(jié)果。4種聚類算法在S1、S2、S3、S4數(shù)據(jù)集的聚類結(jié)果分別如圖6、圖7、圖8和圖9所示。4種聚類算法在R15、D31數(shù)據(jù)集上的聚類結(jié)果分別如圖10和圖11所示。4種聚類算法在經(jīng)典人工模擬數(shù)據(jù)集聚類結(jié)果的Rand指數(shù)、Jaccard系數(shù)、Adjusted Rand index參數(shù)和聚類準(zhǔn)確率比較如圖12所示。

從圖5的實驗結(jié)果可以看出，本文兩種K-medoids算法在經(jīng)典人工模擬數(shù)據(jù)集上識別的類簇個數(shù)與對應(yīng)數(shù)據(jù)集的真實類簇數(shù)完全一致，而且決策圖中的密度峰值點和非密度峰值點可以清晰分離，因此當(dāng)類簇個數(shù)較多時，采用本文新定義的樣本局部密度ρ和樣本距離δ能準(zhǔn)確選擇密度峰值點，從而準(zhǔn)確地確定初始聚類中心。因此，本文兩種K-medoids算法在經(jīng)典人工模擬數(shù)據(jù)集上能克服快速K-medoids、MD_K-medoids和SD_K-medoids算法需要人為給定初始類簇數(shù)，以及MD_K-medoids和SD_K-medoids算法當(dāng)類簇個數(shù)較多時不能完全確定初始聚類中心的缺陷。

從圖6至圖9的實驗結(jié)果可以看出，本文兩種K-medoids算法和密度峰值聚類算法在S1和S2數(shù)據(jù)集的聚類結(jié)果和原始分布幾乎一樣，只將個別邊界樣本錯分。本文兩種K-medoids算法和密度峰值聚類算法會將S3和S4數(shù)據(jù)集中重疊區(qū)域的樣本誤分，非重疊區(qū)域樣本能夠?qū)崿F(xiàn)正確分類?？焖貹-medoids算法對S1、S2、S3和S4數(shù)據(jù)集不僅將重疊區(qū)域樣本分錯，而且將原本屬于兩個類簇但是距離較近的樣本聚為一類，同時還將一個類簇誤分為兩個類簇。由此可見，本文兩種K-medoids算法和密度峰值聚類算法對S1、S2、S3和S4數(shù)據(jù)集的聚類效果優(yōu)于快速K-medoids算法。

從圖10和圖11實驗結(jié)果可知，本文K-medoids算法和密度峰值聚類算法能將R15數(shù)據(jù)集完全正確分類，將D31數(shù)據(jù)集個別重疊樣本誤分?？焖貹-medoids算法將R15數(shù)據(jù)集最中間一個類簇分為兩類；將D31數(shù)據(jù)集最中間那個類簇分為3類，同時快速K-medoids算法將D31數(shù)據(jù)集原本屬于多個類簇，但是距離較近的樣本聚為一個類簇。因此，本文DP_K-medoids和DPNM_K-medoids算法與密度峰值聚類算法對經(jīng)典人工數(shù)據(jù)集R15和D31的聚類效果遠優(yōu)于快速K-medoids算法對該兩數(shù)據(jù)集的聚類效果。

從圖12實驗結(jié)果可以看出，本文DP_K-meoids和DPNM_K-medoids算法以及密度峰值聚類算法對S1、S2、S3、R15和D31數(shù)據(jù)集聚類結(jié)果的各項聚類有效性指標(biāo)值均比快速K-medoids算法的相應(yīng)指標(biāo)值高很多，說明本文新提出的密度峰值選取初始聚類中心的K-medoids聚類方法能獲得非常好的聚類結(jié)果。本文兩種K-medoids算法、快速K-medoids算法和密度峰值聚類算法在S4數(shù)據(jù)集的各項聚類有效性指標(biāo)值幾乎相等，原因是S4數(shù)據(jù)集各類簇間樣本重疊度非常高，各類簇間樣本不易區(qū)分，這也是本文DP_K-meoids、DPNM_K-medoids算法和密度峰值聚類算法在S4數(shù)據(jù)集各項聚類有效性指標(biāo)值偏低的原因。

綜合圖5～圖12的實驗結(jié)果分析可知，本文提出的密度峰值優(yōu)化初始聚類中心的DP_K-medoids和DPNM_K-medoids算法以及密度峰值聚類算法能準(zhǔn)確識別S1～S4、R15和D31這些經(jīng)典人工模擬數(shù)據(jù)集的類簇數(shù)和合理初始聚類中心，并對這些數(shù)據(jù)集實現(xiàn)有效聚類。

5　結(jié)束語

本文提出了采用密度峰值優(yōu)化初始聚類中心的K-medoids算法，采用樣本t近鄰距離之和的倒數(shù)度量樣本局部密度，并定義了新的樣本距離，構(gòu)造樣本距離相對于樣本密度的決策圖，選擇決策圖中局部密度較高且距離相對較遠的樣本作為初始聚類中心，自適應(yīng)地識別數(shù)據(jù)集的類簇數(shù)和合理初始類簇中心，并提出新的聚類準(zhǔn)則函數(shù)。UCI數(shù)據(jù)集實驗結(jié)果揭示，本文提出的兩種K-medoids聚類算法DP_K-medoids和DPNM_K-medoids在UCI真實數(shù)據(jù)集的各項聚類有效性指標(biāo)優(yōu)于快速K-medoids算法、MD_K-medoids算法、SD_K-medoids算法以及密度峰值聚類算法。人工模擬數(shù)據(jù)集實驗結(jié)果揭示，本文兩種K-medoids算法能準(zhǔn)確發(fā)現(xiàn)數(shù)據(jù)集的真實類簇數(shù)和合理初始類簇中心，實現(xiàn)有效聚類，有效減少聚類迭代次數(shù)，縮短聚類時間，加快算法收斂速度，并對噪音有很好的魯棒性。

Fig.6　Clustering results of four algorithms on S1圖6　4種算法在S1數(shù)據(jù)集上的聚類結(jié)果

Fig.7　Clustering results of four algorithms on S2圖7　4種算法在S2數(shù)據(jù)集上的聚類結(jié)果

Fig.8　Clustering results of four algorithms on S3圖8　4種算法在S3數(shù)據(jù)集上的聚類結(jié)果

Fig.9　Clustering results of four algorithms on S4圖9　4種算法在S4數(shù)據(jù)集上的聚類結(jié)果

Fig.10　Clustering results of four algorithms on R15圖10　4種算法在R15數(shù)據(jù)集上的聚類結(jié)果

Fig.11　Clustering results of four algorithms on D31圖11　4種算法在D31數(shù)據(jù)集上的聚類結(jié)果

Fig.12　Rand index,Jaccard coefficient,Adjusted Rand index and clustering accuracy of four algorithms on classic synthetic datasets圖12　4種算法在經(jīng)典人工模擬數(shù)據(jù)集上的Rand指數(shù)、Jaccard系數(shù)、Adjusted Rand index參數(shù)和聚類準(zhǔn)確率

References:

[1]Han Jiawei,Kamber M,Pei Jian.Data mining concepts and techniques[M].Beijing:China Machine Press,2012:398-400.

[2]MacQueen J.Some methods for classification and analysis of multivariate observation[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley,Jun 21-Jul 18,1965.Berkeley,USA:University of California Press,1967:281-297.

[3]Kaufman L,Rousseeuw P J.Finding groups in data:an introduction to cluster analysis[M].New York,USA:John Wiley&Sons,1990:126-163.

[4]Theodoridis S,Koutroumbas K.Pattern recognition[M].Boston,USA:Academic Press,2009:745-748.

[5]Park H S,Jun C H.A simple and fast algorithm for k-medoids clustering[J].Expert Systems with Applications,2009,36 (2):3336-3341.

[6]Xie Juanying,Guo Wenjuan,Xie Weixin,et al.Aneighborhoodbased K-medoids clustering algorithm[J].Journal of Shaanxi Normal University:Natural Science Edition,2012,40(4): 1672-4291.

[7]Ma Qing,Xie Juanying.New K-medoids clustering algorithm based on granular computing[J].Journal of Computer Applications,2012,32(7):1973-1977.

[8]Pan Chu,Luo Ke.Improved K-medoids clustering algorithm based on improved granular computing[J].Journal of Com-puterApplications,2014,34(7):1997-2000.

[9]Xie Juanying,Lu Xiaoxiao,Qu Yanan,et al.K-medoids clustering algorithms with optimized initial seeds by granular computing[J].Journal of Frontiers of Computer Science and Technology,2015,9(5):611-620.

[10]Xie Juanying,Gao Rui.K-medoids clustering algorithms with optimized initial seeds by variance[J].Journal of Frontiers of Computer Science and Technology,2015,9(8):973-984.

[11]Rodriguez A,Laio A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.

[12]Rand W M.Objective criteria for the evaluation of clustering methods[J].Journal of the American Statistical Association, 1971,66(336):846-850.

[13]Zhang Weijiao,Liu Chunhuang,Li Fangyu.Method of quality evaluation for clustering[J].Computer Engineering,2005, 31(20):10-12.

[14]Yu Jian,Cheng Qiansheng.The search scope of optimal cluster number in the fuzzy clustering method[J].Science in China:Series E,2002,32(2):274-280.

[15]Yang Yan,Jin Fan,Kamel M.Survey of clustering validity evaluation[J].Application Research of Computers,2008,25 (6):1631-1632.

[16]Hubert L,Arabie P.Comparing partitions[J].Journal of Classification,1985,2(1):193-218.

[17]Vinh N X,Epps J,Bailey J.Information theoretic measures for clustering comparison:is a correction for chance necessary?[C]//Proceedings of the 26thAnnual International Conference on Machine Learning,Montreal,Canada,Jun 14-18,2009.New York,USA:ACM,2009:1073-1080.

[18]Frank A,Asuncion A.UCI machine learning repository[EB/ OL].Irvine,USA:University of California,School of Information and Computer Science(2010)[2015-03-19].http:// archive.ics.uci.edu/ml.

[19]Franti P,Virmajoki O.Iterative shrinking method for clustering problems[J].The Journal of the Pattern Recognition Society,2006,39(5):761-765.

[20]Veenman C J,Reinders M J T,Backer E.A maximum variance cluster algorithm[J].IEEE Transactions on PatternAnalysis and Machine Intelligence,2002,24(9):1273-1280.

附中文參考文獻：

[6]謝娟英,郭文娟,謝維信.基于鄰域的K中心點聚類算法[J].陜西師范大學(xué)學(xué)報:自然科學(xué)版,2012,40(4):1672-4291.

[7]馬箐,謝娟英.基于粒計算的K-medoids聚類算法[J].計算機應(yīng)用,2012,32(7):1973-1977.

[8]潘楚,羅可.基于改進粒計算的K-medoids聚類算法[J].計算機應(yīng)用,2014,34(7):1997-2000.

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

[10]謝娟英,高瑞.方差優(yōu)化初始中心的K-medoids聚類算法[J].計算機科學(xué)與探索,2015,9(8):973-984.

[13]張惟皎,劉春煌,李芳玉.聚類質(zhì)量的評價方法[J].計算機工程,2005,31(20):10-12.

[14]于劍,程乾生.模糊聚類方法中的最佳聚類數(shù)的搜索范圍[J].中國科學(xué):E輯,2002,32(2):274-280.

[15]楊燕,靳蕃,Kamel M.聚類有效性評價綜述[J].計算機應(yīng)用研究,2008,25(6):1631-1632.

XIE Juanying was born in 1971.She is an associate professor at School of Computer Science,Shaanxi Normal University,and the senior member of CCF.Her research interests include machine learning and data mining.

謝娟英（1971—），女，陜西西安人，博士，陜西師范大學(xué)計算機科學(xué)學(xué)院副教授，CCF高級會員，主要研究領(lǐng)域為機器學(xué)習(xí)，數(shù)據(jù)挖掘。

QU Yanan was born in 1991.She is an M.S.candidate at School of Computer Science,Shaanxi Normal University. Her research interest is data mining.

屈亞楠（1991—），女，陜西渭南人，陜西師范大學(xué)計算機科學(xué)學(xué)院碩士研究生，主要研究領(lǐng)域為數(shù)據(jù)挖掘。

K-medoids ClusteringAlgorithms with Optimized Initial Seeds by Density Peaks*

XIE Juanying+,QU Yanan
School of Computer Science,Shaanxi Normal University,Xi’an 710062,China
+Corresponding author:E-mail:xiejuany@snnu.edu.cn

XIE Juanying,QU Yanan.K-medoids clustering algorithms with optimized initial seeds by density peaks. Journal of Frontiers of Computer Science and Technology,2016,10(2):230-247.

To overcome the deficiencies of the fast K-medoids and the variance based K-medoids clustering algorithms whose number of clusters of a dataset must be provided manually and their initial seeds may locate in a same cluster or cannot be totally found etc.Stimulated by the density peak clustering algorithm,this paper proposes two new K-medoids clustering algorithms.The new algorithms define the local densityρiof pointxias the reciprocal of the sum of the distance betweenxiand itstnearest neighbors,and new distanceδiof pointxiis defined as well,then the decision graph of a point distance relative to its local density is plotted.The points with higher local density and apart from each other located at the upper right corner of the decision graph,which are far away from the rest points in the same dataset,are chosen as the initial seeds for K-medoids,so that the seeds will be in different clusters and the number of clusters of the dataset is automatically determined as the number of initial seeds.In order to get a better clustering,a new measure function is proposed as the ratio of the intra-distance of clusters to the interdistance between clusters.The proposed two new K-medoids algorithms are tested on the real datasets from UCI machine learning repository and on the synthetic datasets.The clustering results of the proposed algorithms are evaluated in terms of the initial seeds selected,iterations,clustering time,Rand index,Jaccard coefficient,Adjusted Randindex and the clustering accuracy.The experimental results demonstrate that the proposed new K-medoids clustering algorithms can recognize the number of clusters of a dataset,find its proper initial seeds,reduce the clustering iterations and the clustering time,improve the clustering accuracy,and are robust to noises as well.

2015-05,Accepted 2015-07.

clustering;K-medoids algorithm;initial seeds;density peak;measure function

10.3778/j.issn.1673-9418.1506072

*The National Natural Science Foundation of China under Grant No.31372250(國家自然科學(xué)基金);the Key Science and Technology Program of Shaanxi Province under Grant No.2013K12-03-24(陜西省科技攻關(guān)項目);the Fundamental Research Funds for the Central Universities of China under Grant No.GK201503067(中央高校基本科研業(yè)務(wù)費專項資金).

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-07-14,http://www.cnki.net/kcms/detail/11.5602.TP.20150714.1609.002.html

A

TP181.1