自動確定聚類中心的密度峰聚類*

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

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

2.輕工過程先進控制教育部重點實驗室（江南大學(xué)），江蘇 無錫 214122

自動確定聚類中心的密度峰聚類*

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

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

2.輕工過程先進控制教育部重點實驗室（江南大學(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)非球形簇。針對密度峰聚類算法需要人工確定聚類中心的缺陷，提出了一種自動確定聚類中心的密度峰聚類算法。首先，計算每個數(shù)據(jù)點的局部密度和該點到具有更高密度數(shù)據(jù)點的最短距離；其次，根據(jù)排序圖自動確定聚類中心；最后，將剩下的每個數(shù)據(jù)點分配到比其密度更高且距其最近的數(shù)據(jù)點所屬的類別，并根據(jù)邊界密度識別噪聲點，得到聚類結(jié)果。將新算法與原密度峰算法進行對比，在人工數(shù)據(jù)集和UCI數(shù)據(jù)集上的實驗表明，新算法不僅能夠自動確定聚類中心，而且具有更高的準(zhǔn)確率。

聚類；密度峰；自動聚類；密度聚類

1 引言

聚類是按照某個特定標(biāo)準(zhǔn)，根據(jù)數(shù)據(jù)自身的信息相似度，把沒有給定劃分類的數(shù)據(jù)集分割成不同的類或簇，使不同簇間的數(shù)據(jù)對象具有最小相似性，同一簇內(nèi)的數(shù)據(jù)對象具有最大相似性[1]。聚類作為一種無監(jiān)督的數(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)計學(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ù)點，得到聚類結(jié)果。

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

2 密度峰聚類及其缺陷

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

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

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

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

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

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

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

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

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

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

可見，DPC算法對聚類中心的選擇比較敏感，容易出現(xiàn)人為地少選、多選聚類中心的問題。這種缺陷在處理一些特殊數(shù)據(jù)集時表現(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 自動確定聚類中心的密度峰聚類算法

3.1 自動確定聚類中心

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

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

其中，

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

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

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

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

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

3.2 ADPC算法步驟描述

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗與分析

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

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

實驗中用到的人工數(shù)據(jù)集有兩個，數(shù)據(jù)集的相關(guān)信息見表1。使用表1中數(shù)據(jù)集，分別運行DPC與ADPC算法，實驗結(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時ADPC算法在DS15數(shù)據(jù)集上的γ排序圖與理想聚類結(jié)果（15個類）

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

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

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

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

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

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

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

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

為了進一步驗證ADPC算法性能，使用表2中4個常用UCI數(shù)據(jù)集進行實驗。實驗采用F-measure[15]與NMI（normalized mutual information）[16]指標(biāo)評價聚類結(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ù)集時兩種算法具有相同的F-measure與NMI值，在其他3個數(shù)據(jù)集上，ADPC算法得到的兩個指標(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)值對比

4.3 算法運行效率分析對比

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

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

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

5 結(jié)束語

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

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

附中文參考文獻：

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

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

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

[15]楊燕,靳蕃,Mohamed K.聚類有效性評價綜述[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é)生會員，主要研究領(lǐng)域為人工智能，數(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é)計算機系獲得碩士學(xué)位，2008年于江南大學(xué)信息學(xué)院獲得博士學(xué)位，現(xiàn)為江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院教授、博士生導(dǎo)師，主要研究領(lǐng)域為人工智能，模式識別，機器學(xué)習(xí)，圖像處理與分析。在國際權(quán)威期刊、國際會議和國內(nèi)核心期刊上發(fā)表論文70多篇，主持和承擔(dān)了國家自然科學(xué)基金等國家級項目和省部級項目近20項，獲省部級科技進步獎多項。

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)域為模式識別，機器學(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(國家自然科學(xué)基金);the Research Innovation Program for College Graduates of Jiangsu Province under Grant No.KYLX15_1169(江蘇省普通高校研究生科研創(chuà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