自動(dòng)確定聚類中心的密度峰聚類*

李 濤，葛洪偉,2+，蘇樹智

1.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122

2.輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室（江南大學(xué)），江蘇 無錫 214122

自動(dòng)確定聚類中心的密度峰聚類*

李 濤1，葛洪偉1,2+，蘇樹智1

1.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122

2.輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室（江南大學(xué)），江蘇 無錫 214122

LI Tao,GE Hongwei,SU Shuzhi.Density peaks clustering by automatic determination of cluster centers. Journal of Frontiers of Computer Science and Technology,2016,10(11)：1614-1622.

密度峰聚類是一種新的基于密度的聚類算法，該算法不需要預(yù)先指定聚類數(shù)目，能夠發(fā)現(xiàn)非球形簇。針對(duì)密度峰聚類算法需要人工確定聚類中心的缺陷，提出了一種自動(dòng)確定聚類中心的密度峰聚類算法。首先，計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的局部密度和該點(diǎn)到具有更高密度數(shù)據(jù)點(diǎn)的最短距離；其次，根據(jù)排序圖自動(dòng)確定聚類中心；最后，將剩下的每個(gè)數(shù)據(jù)點(diǎn)分配到比其密度更高且距其最近的數(shù)據(jù)點(diǎn)所屬的類別，并根據(jù)邊界密度識(shí)別噪聲點(diǎn)，得到聚類結(jié)果。將新算法與原密度峰算法進(jìn)行對(duì)比，在人工數(shù)據(jù)集和UCI數(shù)據(jù)集上的實(shí)驗(yàn)表明，新算法不僅能夠自動(dòng)確定聚類中心，而且具有更高的準(zhǔn)確率。

聚類；密度峰；自動(dòng)聚類；密度聚類

1 引言

聚類是按照某個(gè)特定標(biāo)準(zhǔn)，根據(jù)數(shù)據(jù)自身的信息相似度，把沒有給定劃分類的數(shù)據(jù)集分割成不同的類或簇，使不同簇間的數(shù)據(jù)對(duì)象具有最小相似性，同一簇內(nèi)的數(shù)據(jù)對(duì)象具有最大相似性[1]。聚類作為一種無監(jiān)督的數(shù)據(jù)分析方法，在數(shù)據(jù)挖掘、模式識(shí)別、機(jī)器學(xué)習(xí)、信息檢索等領(lǐng)域[2]已經(jīng)得到了廣泛研究和應(yīng)用。

目前，已經(jīng)有許多聚類算法被提出。比較典型的有：基于劃分的K-means[3]、K-medoids[4]等聚類；基于層次的CURE（clustering using representatives）[5]、Chameleon[6]等聚類；基于網(wǎng)格的STING（statistical information grid）[7]、WaveCluster[8]等聚類；基于模型的統(tǒng)計(jì)學(xué)聚類和神經(jīng)網(wǎng)絡(luò)聚類；基于圖論的譜聚類[9-10]以及基于密度的DBSCAN（density-based spatial clustering of applications with noise）[11]、OPTICS（ordering points to identify the clustering structure）[12]等聚類。

2014年，Rodriguez等人在《Science》上提出了一種新的基于密度的密度峰聚類（density peaks clustering，DPC）算法[13]。DPC算法主要分兩步：首先，通過“決策圖”人工選取密度峰，也即聚類中心；其次，分配剩余數(shù)據(jù)點(diǎn)，得到聚類結(jié)果。

DPC算法雖然簡(jiǎn)單高效，但卻無法自動(dòng)確定聚類中心。特別是針對(duì)一些特殊數(shù)據(jù)集，通過決策圖人工選取聚類中心時(shí)容易出錯(cuò)。針對(duì)DPC算法這一缺陷，本文提出了一種自動(dòng)確定聚類中心的密度峰聚類算法（automatically density peaks clustering，ADPC）。ADPC算法能夠根據(jù)排序圖自動(dòng)確定聚類中心，具有更優(yōu)的聚類結(jié)果和更高的準(zhǔn)確率。

2 密度峰聚類及其缺陷

密度峰聚類[13]算法只有一個(gè)輸入?yún)?shù)，不需要預(yù)先指定聚類數(shù)目，能夠發(fā)現(xiàn)非球形的簇。算法基于數(shù)據(jù)點(diǎn)之間的距離測(cè)度，不需考慮概率分布或多維密度函數(shù)，性能不受數(shù)據(jù)空間維度影響，可以處理高維數(shù)據(jù)。

算法將具有如下特點(diǎn)的數(shù)據(jù)點(diǎn)視為聚類中心：該點(diǎn)被具有相對(duì)較低局部密度的鄰居點(diǎn)包圍，且與其他具有更高密度的數(shù)據(jù)點(diǎn)之間具有相對(duì)較大的距離。對(duì)于每個(gè)數(shù)據(jù)點(diǎn) j，只需計(jì)算兩個(gè)變量，即點(diǎn) j的局部密度ρj和該點(diǎn)到具有更高局部密度的點(diǎn)的最短距離δj。數(shù)據(jù)點(diǎn)j的局部密度ρj計(jì)算方式為：

其中，djk是數(shù)據(jù)點(diǎn)之間的距離；dc是截?cái)嗑嚯x。設(shè)數(shù)據(jù)點(diǎn)的鄰居點(diǎn)總數(shù)占數(shù)據(jù)集樣本點(diǎn)總數(shù)N的比例值為P∈(0,100)，將M=N(N-1)/2個(gè)距離dmn(m

δj為數(shù)據(jù)點(diǎn) j到具有更高局部密度的點(diǎn)k的最短距離，其計(jì)算方式為：

對(duì)于具有全局最高密度的數(shù)據(jù)點(diǎn)，令 δj= maxk(djk)。通常的，具有局部或全局最大密度的數(shù)據(jù)點(diǎn)的δj比其最近鄰距離要大。算法將同時(shí)具有相對(duì)較大ρ和δ的數(shù)據(jù)點(diǎn)視為聚類中心。

聚類中心找到后，下一步將剩下的每個(gè)數(shù)據(jù)點(diǎn)分配到比其密度更高且距其最近的數(shù)據(jù)點(diǎn)所屬的簇。不像K-means等算法[2,14]需要對(duì)目標(biāo)函數(shù)進(jìn)行多次迭代優(yōu)化，數(shù)據(jù)點(diǎn)分配只需上述一步即可完成。為了識(shí)別噪聲點(diǎn)，DPC算法為每個(gè)簇定義邊界區(qū)域密度：屬于這個(gè)簇并且與其他簇的數(shù)據(jù)點(diǎn)之間的距離小于dc的數(shù)據(jù)點(diǎn)總數(shù)。局部密度ρ高于邊界區(qū)域密度的點(diǎn)被視為簇的核心點(diǎn)，否則被視為噪聲點(diǎn)。

DPC算法雖然簡(jiǎn)單高效，但卻需要通過決策圖人工選取聚類中心。這種方法對(duì)每個(gè)簇內(nèi)都有唯一密度峰或者簇?cái)?shù)很少的數(shù)據(jù)集比較有效，因?yàn)榇藭r(shí)從決策圖中比較容易判斷出具有相對(duì)較大ρ和δ的數(shù)據(jù)點(diǎn)。但針對(duì)以下情況，決策圖則表現(xiàn)出明顯的局限性：

（1）如圖1所示，在決策圖上，除了明顯的密度峰點(diǎn)，一些具有相對(duì)較大ρ和較小δ，或者相對(duì)較小ρ和較大δ的數(shù)據(jù)點(diǎn)也可能是聚類中心，但這些點(diǎn)很容易被人為地忽略，使得少選了聚類中心，最終導(dǎo)致屬于不同簇的一些數(shù)據(jù)點(diǎn)被錯(cuò)誤地合并為同一個(gè)簇。

（2）如圖2所示，如果同一簇內(nèi)出現(xiàn)了多個(gè)密度峰，則這些點(diǎn)很容易被錯(cuò)選為多余的聚類中心，導(dǎo)致同一個(gè)簇被錯(cuò)誤地分割為多個(gè)子簇。

（3）在處理具有較多聚類中心的數(shù)據(jù)集時(shí)，同樣比較容易出現(xiàn)上述錯(cuò)選聚類中心的情況。

可見，DPC算法對(duì)聚類中心的選擇比較敏感，容易出現(xiàn)人為地少選、多選聚類中心的問題。這種缺陷在處理一些特殊數(shù)據(jù)集時(shí)表現(xiàn)得更為突出。

Fig.1 DPC gets less cluster centers by decision graph圖1 DPC算法通過決策圖少選聚類中心

Fig.2 DPC gets redundant cluster centers by decision graph圖2 DPC算法通過決策圖多選聚類中心

3 自動(dòng)確定聚類中心的密度峰聚類算法

3.1 自動(dòng)確定聚類中心

定義1γj為衡量點(diǎn)j是否為聚類中心的指標(biāo)：

顯然，當(dāng)點(diǎn) j為聚類中心時(shí)，ρj或δj具有較大值，則γj也具有較大值，因而γj較大的點(diǎn)很可能是聚類中心。對(duì)γ進(jìn)行降序排列，記排序后的點(diǎn)編號(hào)為i，繪制γ關(guān)于點(diǎn)i的前個(gè)點(diǎn)的函數(shù)圖，稱之為“γ排序圖”。

其中，

P=8時(shí)，圖2（b）中數(shù)據(jù)集的決策圖與γ排序圖如圖3所示。從圖3中可以看出，聚類中心都位于拐點(diǎn)之前。整體而言，大多數(shù)數(shù)據(jù)點(diǎn)的γ值較小且彼此接近，只有拐點(diǎn)之前的少數(shù)數(shù)據(jù)點(diǎn)γ值較大且彼此差異也較大，將這少數(shù)點(diǎn)稱為潛在聚類中心。

定義3潛在聚類中心定義為：

Fig.3 Decision graph andγsorting graph for data in Fig.2(b)whenP=8(top-30 points 2 clusters)圖3 P=8時(shí)圖2（b）數(shù)據(jù)集的決策圖與γ排序圖（前30個(gè)點(diǎn)2個(gè)簇）

準(zhǔn)確確定拐點(diǎn)是算法的關(guān)鍵。根據(jù)定義2，拐點(diǎn)為γi值前后差值大于閾值θ的所有點(diǎn)中γ值最小的點(diǎn)，因而一種有效查找拐點(diǎn)的方法為：從右往左依次判斷γ排序圖中的點(diǎn)，查找第一個(gè)滿足定義2中條件的點(diǎn)，該點(diǎn)即為拐點(diǎn)。這種方法確定的拐點(diǎn)能夠保證拐點(diǎn)之前具有盡可能多的潛在聚類中心，從而防止后續(xù)處理時(shí)漏選任何一個(gè)可能的實(shí)際聚類中心。

顯然，潛在聚類中心的個(gè)數(shù)一般多于實(shí)際聚類中心的個(gè)數(shù)。如果把所有潛在聚類中心都當(dāng)作實(shí)際聚類中心進(jìn)行聚類，則某些簇中可能會(huì)被指定多余的聚類中心，導(dǎo)致同一個(gè)簇被錯(cuò)誤地分割為多個(gè)子簇。在DPC算法中，實(shí)際聚類中心通常都位于數(shù)據(jù)點(diǎn)分布相對(duì)比較稠密的區(qū)域，而且彼此之間都具有相對(duì)較大的距離。因而在一個(gè)具有高密度區(qū)域的簇中，若存在多個(gè)潛在聚類中心（密度峰點(diǎn)），則這些潛在聚類中心彼此之間通常會(huì)比較接近。把查找到的屬于某個(gè)簇的第一個(gè)潛在聚類中心當(dāng)作該簇的唯一實(shí)際聚類中心；如果其他某個(gè)潛在聚類中心與該簇中已知實(shí)際聚類中心的最短距離小于dc，則將該潛在聚類中心視為被錯(cuò)選的多余的聚類中心，并將其當(dāng)作簇成員處理，否則將該潛在聚類中心當(dāng)作另一個(gè)簇的實(shí)際聚類中心。最終，實(shí)現(xiàn)從潛在聚類中心中準(zhǔn)確“篩選”出實(shí)際聚類中心的目的。

3.2 ADPC算法步驟描述

綜上所述，首先利用γ排序圖確定拐點(diǎn)及潛在聚類中心，然后從潛在聚類中心中自動(dòng)確定實(shí)際聚類中心，最后分配剩余數(shù)據(jù)點(diǎn)，得到聚類結(jié)果。算法主要步驟描述如下。

輸入：實(shí)驗(yàn)數(shù)據(jù)集X={x1,x2,…,xn}，數(shù)據(jù)點(diǎn)的鄰居點(diǎn)總數(shù)占數(shù)據(jù)集樣本總數(shù)的比例值P。

輸出：聚類結(jié)果C={C1,C2,…,Ck}，k為類數(shù)。

（1）根據(jù)P計(jì)算dc，計(jì)算每個(gè)數(shù)據(jù)點(diǎn)i的局部密度ρi和該點(diǎn)到具有更高局部密度數(shù)據(jù)點(diǎn)的最短距離δi。

（2）計(jì)算γi=ρiδi，將γ降序排列，繪制γ排序圖。根據(jù)γ排序圖自動(dòng)查找拐點(diǎn)ap，找到潛在聚類中心。

（3）默認(rèn)具有最大γ值的第一個(gè)點(diǎn)為一個(gè)實(shí)際聚類中心。從已經(jīng)被確定為實(shí)際聚類中心的所有點(diǎn)中，找到距離點(diǎn)i最近的點(diǎn) j，計(jì)算距離Dist(i,j)，記MinDist=Dist(i,j)。如果MinDist>dc，則點(diǎn)i被確定為一個(gè)新的實(shí)際聚類中心，否則點(diǎn)i被視為點(diǎn)j所屬的簇的成員。其中，i=2,3,…,ap，j=1,2,…,i-1。

（4）重復(fù)步驟（3），直到i=ap，自動(dòng)確定聚類中心的過程結(jié)束。

（5）將剩下的每個(gè)數(shù)據(jù)點(diǎn)分配到具有更大ρ的最近鄰點(diǎn)所屬的簇，計(jì)算邊界區(qū)域密度，根據(jù)邊界區(qū)域密度識(shí)別噪聲點(diǎn)。

使用DS7數(shù)據(jù)集自動(dòng)確定聚類中心的過程對(duì)算法原理做進(jìn)一步解釋。P=3.5（dc=2.52）時(shí)DS7數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果如圖4所示。圖4（a）中為拐點(diǎn)之前（包括拐點(diǎn)）的9個(gè)潛在聚類中心按γ值從大到小進(jìn)行了編號(hào)；圖4（b）為圖4（a）中9個(gè)潛在聚類中心的實(shí)際位置分布及錯(cuò)誤聚類結(jié)果；圖4（c）標(biāo)示出了算法最后自動(dòng)確定的7個(gè)實(shí)際聚類中心；圖4（d）為圖4（c）對(duì)應(yīng)的理想聚類結(jié)果。首先根據(jù)定義2，將γ值前后整體差異比較大的點(diǎn)9選作拐點(diǎn)，將點(diǎn)1至點(diǎn)9選作潛在聚類中心；然后依次判斷9個(gè)點(diǎn)能否作為實(shí)際聚類中心。默認(rèn)具有最大γ值的點(diǎn)1為一個(gè)實(shí)際聚類中心，點(diǎn)2找到已經(jīng)被確定為實(shí)際聚類中心且距其最近的點(diǎn)1，計(jì)算點(diǎn)1與點(diǎn)2之間的距離 Dist(1,2)= 21.68，因?yàn)镈ist(1,2)>dc，所以點(diǎn)2被確定為一個(gè)新的實(shí)際聚類中心；相似的，點(diǎn)3、4、5、6、7依次被確定為實(shí)際聚類中心；點(diǎn)8從已被確定為實(shí)際聚類中心的點(diǎn)中找到距其最近的點(diǎn)1，但Dist(1,8)

Fig.4 Procedure of determining cluster centers on DS7 byADPC圖4 ADPC算法在DS7數(shù)據(jù)集上自動(dòng)確定聚類中心的過程

Fig.5 Decision graph and ideal clustering result of DS15 by DPC whenP=2(15 clusters)圖5 P=2時(shí)DPC算法在DS15數(shù)據(jù)集上的決策圖與理想聚類結(jié)果（15個(gè)類）

3.3 ADPC算法時(shí)間復(fù)雜度分析

設(shè)實(shí)驗(yàn)數(shù)據(jù)集樣本總數(shù)為n，根據(jù)3.2節(jié)的描述，算法第（1）步根據(jù)P計(jì)算dc時(shí)，首先計(jì)算歐式距離矩陣的時(shí)間復(fù)雜度為O(n2)，對(duì)歐式距離矩陣上三角n(n-1)/2個(gè)距離進(jìn)行快速排序的時(shí)間復(fù)雜度為O(n2lbn)，計(jì)算 ρ和δ的時(shí)間復(fù)雜度為O(n2)；第（2）步中計(jì)算γ及自動(dòng)查找拐點(diǎn)的時(shí)間復(fù)雜度為O(n)，采用快速排序?qū)Ζ媒敌蚺帕械臅r(shí)間復(fù)雜度為O(n2lbn)；第（3）、（4）步中自動(dòng)確定聚類中心的時(shí)間復(fù)雜度綜合為O(n2)；第（5）步中分配數(shù)據(jù)點(diǎn)的時(shí)間復(fù)雜度為O(n)，識(shí)別噪聲點(diǎn)的時(shí)間復(fù)雜度為O(n2)。綜上所述，ADPC算法的時(shí)間復(fù)雜度為O(n2lbn)。

4 實(shí)驗(yàn)與分析

為了驗(yàn)證ADPC算法的性能，分別在人工數(shù)據(jù)集和UCI數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。

4.1 人工數(shù)據(jù)集

實(shí)驗(yàn)中用到的人工數(shù)據(jù)集有兩個(gè)，數(shù)據(jù)集的相關(guān)信息見表1。使用表1中數(shù)據(jù)集，分別運(yùn)行DPC與ADPC算法，實(shí)驗(yàn)結(jié)果如圖5～圖12所示。

Table 1 Synthetic data sets表1 人工數(shù)據(jù)集

Fig.6 γsorting graph and ideal clustering result of DS15 byADPC whenP=2(15 clusters)圖6 P=2時(shí)ADPC算法在DS15數(shù)據(jù)集上的γ排序圖與理想聚類結(jié)果（15個(gè)類）

Fig.7 Decision graph and wrong clustering result of DS15 by DPC whenP=3.5(11 clusters)圖7 P=3.5時(shí)DPC算法在DS15數(shù)據(jù)集上的決策圖與錯(cuò)誤聚類結(jié)果（11個(gè)類）

Fig.8 γsorting graph and ideal clustering result of DS15 byADPC whenP=3.5(15 clusters)圖8 P=3.5時(shí)ADPC算法在DS15數(shù)據(jù)集上的γ排序圖與理想聚類結(jié)果（15個(gè)類）

Fig.9 Decision graph and ideal clustering result of DS31 by DPC whenP=2(31 clusters)圖9 P=2時(shí)DPC算法在DS31數(shù)據(jù)集上的決策圖與理想聚類結(jié)果（31個(gè)類）

Fig.10 γsorting graph and ideal clustering result of DS31 byADPC whenP=2(31 clusters)圖10 P=2時(shí)ADPC算法在DS31數(shù)據(jù)集上的γ排序圖與理想聚類結(jié)果（31個(gè)類）

Fig.11 Decision graph and wrong clustering result of DS31 by DPC whenP=2.4(23 clusters)圖11 P=2.4時(shí)DPC算法在DS31數(shù)據(jù)集上的決策圖與錯(cuò)誤聚類結(jié)果（23個(gè)類）

Fig.12 γsorting graph and ideal clustering result of DS31 byADPC whenP=2.4(31 clusters)圖12 P=2.4時(shí)ADPC算法在DS31數(shù)據(jù)集上的γ排序圖與理想聚類結(jié)果（31個(gè)類）

針對(duì)DS15數(shù)據(jù)集，P∈[1.1,3.3]時(shí)，兩種算法雖然都能得到理想聚類結(jié)果，但DPC算法選取聚類中心時(shí)具有很大的不確定性；P∈[3.4,3.7]時(shí)，DPC算法已經(jīng)無法選取出準(zhǔn)確的聚類中心，而ADPC算法依然可以自動(dòng)確定全部15個(gè)聚類中心并得到理想聚類結(jié)果。其中P=2，P=3.5時(shí)，兩種算法在DS15數(shù)據(jù)集上的聚類結(jié)果分別如圖5～圖8所示。圖5表明，DPC算法雖然最終能夠得到15個(gè)類，但在圖5（a）中，因人工選擇具有主觀性，很可能會(huì)將聚類中心錯(cuò)選為2個(gè)、3個(gè)等；而在圖6、圖8中，ADPC算法不存在錯(cuò)選聚類中心的情況。相似的，針對(duì)DS31數(shù)據(jù)集，P∈[1.1,2.1]時(shí)，ADPC算法比DPC算法能夠更易且自動(dòng)得到理想聚類結(jié)果；而P∈[2.2,2.4]時(shí)，DPC算法經(jīng)過多次嘗試，最多也只能得到錯(cuò)誤的30個(gè)類，但ADPC算法依然可以自動(dòng)確定全部31個(gè)聚類中心并得到理想的聚類結(jié)果。其中P=2，P=2.4時(shí)，兩種算法在DS31數(shù)據(jù)集上的聚類結(jié)果分別如圖9～圖12所示。上述實(shí)驗(yàn)表明，ADPC算法避免了DPC算法通過決策圖人工選取聚類中心時(shí)出錯(cuò)的可能性，特別是當(dāng)DPC算法無法選取全部聚類中心時(shí)，ADPC算法不僅能夠基于γ排序圖自動(dòng)準(zhǔn)確地確定聚類中心，而且具有更優(yōu)的聚類結(jié)果。

4.2 UCI數(shù)據(jù)集

為了進(jìn)一步驗(yàn)證ADPC算法性能，使用表2中4個(gè)常用UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)采用F-measure[15]與NMI（normalized mutual information）[16]指標(biāo)評(píng)價(jià)聚類結(jié)果。

Table 2 UCI data sets表2 UCI數(shù)據(jù)集

在最佳P值下，DPC算法與ADPC算法在表2中數(shù)據(jù)集上聚類所得F-measure與NMI指標(biāo)值見表3。表3表明，除了在處理Seeds數(shù)據(jù)集時(shí)兩種算法具有相同的F-measure與NMI值，在其他3個(gè)數(shù)據(jù)集上，ADPC算法得到的兩個(gè)指標(biāo)值均比DPC算法更優(yōu)。整體而言，ADPC算法能夠得到更優(yōu)的聚類結(jié)果，具有更高的準(zhǔn)確度。

Table 3 Comparison of F-measure and NMI表3 兩種算法的F-measure與NMI指標(biāo)值對(duì)比

4.3 算法運(yùn)行效率分析對(duì)比

根據(jù)3.3節(jié)描述，ADPC算法的時(shí)間復(fù)雜度為O(n2lbn)。根據(jù)文獻(xiàn)[13]，DPC算法的時(shí)間復(fù)雜度為O(n2lbn)?？梢姡珹DPC算法雖然增加了自動(dòng)確定聚類中心的能力，但時(shí)間復(fù)雜度仍與DPC算法在同一個(gè)數(shù)量級(jí)。表4為兩種算法在表1、表2中6個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比，表中時(shí)間為算法在同一數(shù)據(jù)集上運(yùn)行10次所用的平均時(shí)間，DPC算法忽略在決策圖上人工選取聚類中心環(huán)節(jié)所用時(shí)間。兩種算法均在Matlab R2013a上編程實(shí)現(xiàn)，在同一PC機(jī)（Windows10 64位操作系統(tǒng)，Intel Core i7 2.5 GHz CPU，4 GB內(nèi)存）上運(yùn)行，時(shí)間單位為秒。

Table 4 Comparison of running time on different data sets表4 兩種算法在不同數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比 s

在表4中，ADPC算法只比DPC算法的運(yùn)行時(shí)間多了約0.1 s，差值在0.067 3～0.102 3之間。整體而言，ADPC算法沒有顯著增加運(yùn)行時(shí)間，這也驗(yàn)證了兩種算法具有相同時(shí)間復(fù)雜度的結(jié)論。

5 結(jié)束語

針對(duì)密度峰聚類（DPC）算法人工難以準(zhǔn)確選取聚類中心的缺陷，提出了一種自動(dòng)確定聚類中心的密度峰聚類算法（ADPC）。與DPC算法相比，ADPC算法在人工數(shù)據(jù)集上具有更優(yōu)的結(jié)果，在UCI真實(shí)數(shù)據(jù)集上具有更高的準(zhǔn)確度。由于ADPC算法主要是在選取聚類中心環(huán)節(jié)對(duì)DPC算法進(jìn)行了改進(jìn)，并沒有改變DPC算法的數(shù)據(jù)點(diǎn)分配機(jī)制，因而ADPC算法不僅增加了自動(dòng)確定聚類中心的能力，而且保留了DPC算法的一些優(yōu)勢(shì)：即同樣只需一個(gè)輸入?yún)?shù)，不需要預(yù)先指定聚類數(shù)目，可以識(shí)別非球形簇，并且沒有增加時(shí)間復(fù)雜度。

然而，ADPC算法在面對(duì)一些簇內(nèi)沒有密度峰或同時(shí)具有多個(gè)密度峰的復(fù)雜流形結(jié)構(gòu)數(shù)據(jù)集時(shí)，會(huì)出現(xiàn)能夠自動(dòng)確定聚類中心卻無法得到理想聚類結(jié)果的問題。這是因?yàn)閷?duì)于流形結(jié)構(gòu)中的某個(gè)點(diǎn)a而言，密度更高且距其最近的點(diǎn)b很可能在另一個(gè)簇中，這就導(dǎo)致點(diǎn)a被錯(cuò)誤地分配到點(diǎn)b所屬的簇，最終導(dǎo)致實(shí)際屬于不同簇的一些點(diǎn)被錯(cuò)誤地合并為同一簇。針對(duì)這一問題，首先可以考慮使用能夠更好地反映數(shù)據(jù)分布結(jié)構(gòu)特點(diǎn)、簇內(nèi)與簇間蘊(yùn)含結(jié)構(gòu)信息的新的距離測(cè)度，代替僅能反映聚類結(jié)構(gòu)局部一致性卻無法很好地反映全局一致性的歐氏距離；其次，改進(jìn)算法的分配機(jī)制，使得算法能夠沿著流形結(jié)構(gòu)尋找密度更高的近鄰點(diǎn)，從而使得數(shù)據(jù)點(diǎn)分配更佳合理?？傊绾问沟肁DPC算法能夠有效處理復(fù)雜流形結(jié)構(gòu)數(shù)據(jù)集，將是下一步的研究?jī)?nèi)容。

[1]Xu Rui,Wunsch D.Survey of clustering algorithms[J].IEEE Transactions on Neural Networks,2005,16(3):645-678.

[2]Aggarwal C C,Reddy C K.Data clustering:algorithms and applications[M].Boca Raton,USA:CRC Press,2013.

[3]Jain A K.Data clustering:50 years beyond K-means[J].Pattern Recognition Letters,2010,31(8):651-666.

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

[5]Zhou Yajian,Xu Chen,Li Jiguo.Unsupervised anomaly detection method based on improved CURE clustering algorithm[J].Journal on Communications,2010,31(7):18-23.

[6]Karypis G,Han E H,Kumar V.Chameleon:hierarchical clustering using dynamic modeling[J].Computer,1999,32 (8):68-75.

[7]Ansari S,Chetlur S,Prabhu S,et al.An overview of clustering analysis techniques used in data mining[J].International Journal of Emerging Technology and Advanced Engineering, 2013,3(12):284-286.

[8]Amini A,Wah T Y,Saybani M R,et al.A study of densitygrid based clustering algorithms on data streams[C]//Proceedings of the 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery,Shanghai,Jul 26-28, 2011.Piscataway,USA:IEEE,2011,3:1652-1656.

[9]Yang Peng,Zhu Qingsheng,Huang Biao.Spectral clustering with density sensitive similarity function[J].Knowledge-Based Systems,2011,24(5):621-628.

[10]Guang Junye,Liu Mingxia,Zhang Daoqiang.Spectral clustering algorithm based on effective distance[J].Journal of Frontiers of Computer Science and Technology,2014,8 (11):1365-1372.

[11]Yang Jing,Gao Jiawei,Liang Jiye,et al.An improved DBSCAN clustering algorithm based on data field[J].Journal of Frontiers of Computer Science and Technology,2012,6 (10):903-911.

[12]Kalita H K,Bhattacharyya D K,Kar A.A new algorithm for ordering of points to identify clustering structure based on perimeter of triangle:OPTICS(BOPT)[C]//Proceedings of the 2007 International Conference on Advanced Computing and Communications,Guwahati,India,Dec 18-21,2007.Piscataway,USA:IEEE,2007:523-528.

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

[14]McLachlan G,Krishnan T.The EM algorithm and extensions[M].Hoboken,USA:John Wiley&Sons,2007.

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

[16]Cai Deng,He Xiaofei,Han Jiawei.Document clustering using locality preserving indexing[J].IEEE Transactions on Knowledge &Data Engineering,2005,17(12):1624-1637.

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

[5]周亞建,徐晨,李繼國(guó).基于改進(jìn)CURE聚類算法的無監(jiān)督異常檢測(cè)方法[J].通信學(xué)報(bào),2010,31(7):18-23.

[10]光俊葉,劉明霞,張道強(qiáng).基于有效距離的譜聚類算法[J].計(jì)算機(jī)科學(xué)與探索,2014,8(11):1365-1372.

[11]楊靜,高嘉偉,梁吉業(yè),等.基于數(shù)據(jù)場(chǎng)的改進(jìn)DBSCAN聚類算法[J].計(jì)算機(jī)科學(xué)與探索,2012,6(10):903-911.

[15]楊燕,靳蕃,Mohamed K.聚類有效性評(píng)價(jià)綜述[J].計(jì)算機(jī)應(yīng)用研究,2008,25(6):1630-1632.

LI Tao was born in 1991.He is an M.S.candidate at Jiangnan University,and the member of CCF.His research interests include artificial intelligence and data mining.

李濤（1991—），男，河南商丘人，江南大學(xué)碩士研究生，CCF學(xué)生會(huì)員，主要研究領(lǐng)域?yàn)槿斯ぶ悄?，?shù)據(jù)挖掘。

GE Hongwei was born in 1967.He received the M.S.degree in computer science from Nanjing University of Aeronautics and Astronautics in 1992,and the Ph.D.degree in control engineering from Jiangnan University in 2008. Now he is a professor and Ph.D.supervisor at School of Internet of Things Engineering,Jiangnan University.His research interests include artificial intelligence,machine learning,pattern recognition and their applications.

葛洪偉（1967—），男，江蘇無錫人，1992年于南京航空航天大學(xué)計(jì)算機(jī)系獲得碩士學(xué)位，2008年于江南大學(xué)信息學(xué)院獲得博士學(xué)位，現(xiàn)為江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)槿斯ぶ悄?，模式識(shí)別，機(jī)器學(xué)習(xí)，圖像處理與分析。在國(guó)際權(quán)威期刊、國(guó)際會(huì)議和國(guó)內(nèi)核心期刊上發(fā)表論文70多篇，主持和承擔(dān)了國(guó)家自然科學(xué)基金等國(guó)家級(jí)項(xiàng)目和省部級(jí)項(xiàng)目近20項(xiàng)，獲省部級(jí)科技進(jìn)步獎(jiǎng)多項(xiàng)。

SU Shuzhi was born in 1987.He is a Ph.D.candidate at Jiangnan University.His research interests include pattern recognition and machine learning.

蘇樹智（1987—），男，山東泰安人，江南大學(xué)博士研究生，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別，機(jī)器學(xué)習(xí)。

Density Peaks Clustering byAutomatic Determination of Cluster Centers?

LI Tao1,GE Hongwei1,2+,SU Shuzhi1
1.School of Internet of Things Engineering,Jiangnan University,Wuxi,Jiangsu 214122,China
2.Ministry of Education Key Laboratory of Advanced Process Control for Light Industry(Jiangnan University), Wuxi,Jiangsu 214122,China
+Corresponding author:E-mail:ghw8601@163.com

Density peaks clustering is a new density-based clustering algorithm.It can find nonspherical clusters without specifying the cluster number.Aiming at the defect that the density peaks clustering algorithm can only manually determine cluster centers,this paper proposes a density peaks clustering by automatic determination of cluster centers. Firstly,for each data point,two quantities are calculated:the local density and the distance from points of higher density. Then the algorithm automatically searches the clustering centers according to the sorting graph.Finally,each remaining data point is assigned to the same cluster as its nearest neighbor of higher density,and then the noises are recognized according to the border density.Comparing the new algorithm with the density peaks clustering algorithm,the experimental results on synthetic data sets and UCI data sets show that the new algorithm can not only automatically determine cluster centers,but also get better results with higher accuracy.

clustering;density peaks;automatically clustering;density clustering

10.3778/j.issn.1673-9418.1510049

A

TP181

*The National Natural Science Foundation of China under Grant No.61402203(國(guó)家自然科學(xué)基金);the Research Innovation Program for College Graduates of Jiangsu Province under Grant No.KYLX15_1169(江蘇省普通高校研究生科研創(chuàng)新計(jì)劃項(xiàng)目).

Received 2015-10,Accepted 2016-03.

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