謝娟英，屈亞楠

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

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

謝娟英+，屈亞楠

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

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

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

1　引言

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

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

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

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

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

2　基本概念

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

3　本文K-medoids算法

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

3.1DP_K-medoids算法思想

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

步驟1初始化。

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

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

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

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

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

（2）計(jì)算聚類(lèi)誤差平方和。

步驟3更新類(lèi)簇中心并重新分配樣本。

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

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

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

3.2DPNM_K-medoids算法思想

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

3.3本文K-medoids算法分析

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

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

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

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

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

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

4　實(shí)驗(yàn)結(jié)果與分析

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

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

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

本部分實(shí)驗(yàn)采用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)[18]的iris等13個(gè)聚類(lèi)算法常用數(shù)據(jù)集對(duì)本文算法進(jìn)行測(cè)試。所用數(shù)據(jù)集描述見(jiàn)表1，pid是pima indians diabetes數(shù)據(jù)集的簡(jiǎn)寫(xiě),waveform40是waveform21增加19個(gè)噪音屬性得到的數(shù)據(jù)集。本文DP_K-medoids和DPNM_ K-medoids算法分別與快速K-medoids算法[5]、方差優(yōu)化初始中心的MD_K-medoids和SD_K-medoids算法[10]，以及密度峰值聚類(lèi)算法[11]進(jìn)行比較，以檢驗(yàn)本文提出的密度峰值優(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個(gè)UCI數(shù)據(jù)集的樣本最近鄰數(shù)t=8。密度峰值聚類(lèi)算法的結(jié)果隨截?cái)嗑嚯x參數(shù)值的改變而不同，實(shí)驗(yàn)展示的是在各數(shù)據(jù)集多次實(shí)驗(yàn)得到的最好聚類(lèi)結(jié)果值。本文K-medoids算法在UCI數(shù)據(jù)集上的決策圖及其初始聚類(lèi)中心如圖1所示，圖中矩形框內(nèi)的加粗黑圓點(diǎn)為所選初始聚類(lèi)中心。表2是6種聚類(lèi)算法對(duì)表1 UCI數(shù)據(jù)集選擇的初始聚類(lèi)中心樣本。表3是6種聚類(lèi)算法對(duì)表1 UCI數(shù)據(jù)集10次運(yùn)行的平均迭代次數(shù)和平均聚類(lèi)時(shí)間。其中，加粗字體表示相應(yīng)的最好實(shí)驗(yàn)結(jié)果。密度峰值聚類(lèi)算法不存在聚類(lèi)中心更迭的過(guò)程，因而比較算法平均迭代次數(shù)時(shí)不將密度峰值聚類(lèi)算法作為對(duì)比算法。圖2展示了6種聚類(lèi)算法的Rand指數(shù)、Jaccard系數(shù)、AdjustedRandindex參數(shù)和聚類(lèi)準(zhǔn)確率的平均值比較。

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

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

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

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

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

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

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ù)和聚類(lèi)準(zhǔn)確率

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

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

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

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

4.2.1本文K-medoids算法魯棒性測(cè)試實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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ù)和聚類(lèi)準(zhǔn)確率

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Fig.11　Clustering results of four algorithms on D31圖11　4種算法在D31數(shù)據(jù)集上的聚類(lèi)結(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ù)和聚類(lèi)準(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.

附中文參考文獻(xiàn)：

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

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

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

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

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

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

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

[15]楊燕,靳蕃,Kamel M.聚類(lèi)有效性評(píng)價(jià)綜述[J].計(jì)算機(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é)計(jì)算機(jī)科學(xué)學(xué)院副教授，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)闄C(jī)器學(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é)計(jì)算機(jī)科學(xué)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?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(國(guó)家自然科學(xué)基金);the Key Science and Technology Program of Shaanxi Province under Grant No.2013K12-03-24(陜西省科技攻關(guān)項(xiàng)目);the Fundamental Research Funds for the Central Universities of China under Grant No.GK201503067(中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金).

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