密度自適應的數據競爭聚類算法*

蘇　輝，葛洪偉,2+，張　濤

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

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

密度自適應的數據競爭聚類算法*

蘇輝1，葛洪偉1,2+，張濤1

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

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

針對現(xiàn)有數據競爭聚類算法在處理密度不均勻數據集時聚類效果不理想的問題，提出了一種密度自適應的數據競爭聚類算法。首先，定義了一種局部密度自適應線段；然后，根據局部密度自適應線段計算出密度自適應相似度，密度自適應相似度不僅反映了數據的整體空間分布信息，還反映了數據點的局部信息，更加符合數據的實際分布；最后，將密度自適應相似度用于數據競爭聚類算法中。在人工和真實數據集上的仿真實驗結果表明，新算法比現(xiàn)有的數據競爭聚類算法在處理密度不均勻數據集時，具有更高的聚類性能。

聚類；數據競爭；聚合場；密度不均勻

1　引言

聚類分析是數據挖掘的一種重要方法，它將給定的數據集劃分到不同簇中，使得同一簇中的對象具有較大的相似性，而不同簇間的對象有較大的相異性[1]。很多時候，聚類分析是解決其他問題的起點，并在廣泛的領域中扮演著重要角色，例如生物學[2]、模式識別[3]、信息檢索[4]、數據挖掘[5]和機器學習[6]等領域。

目前已經有很多聚類方法被提出，例如k-means聚類、譜聚類和AP（affinity propagation）聚類[7-9]等。然而很多聚類算法在有其特色和優(yōu)點的同時，也有著自身的缺點。例如，有些聚類方法對初始聚類中心的選擇比較敏感，有些聚類方法容易受到噪聲和孤立點的干擾，造成算法的聚類效果不佳。有鑒于此，Lu等人最近提出了一種數據競爭（data competition，DC）聚類算法[10]。DC聚類通過數據集中各個數據點之間的相互競爭尋找聚類中心，然后將數據點分配給聚類中心完成聚類。該算法對于噪聲和孤立點不敏感，具有簡單高效的特點，在圖像分割等應用中表現(xiàn)良好[11]。

DC聚類算法是一種基于中心的聚類算法。它像許多其他的中心類聚類算法一樣，在緊湊的具有超球形分布的數據集上具有較好的聚類性能，難以處理任意空間形狀和具有多重尺度的數據，例如密度不均勻數據。這就對其進一步的應用帶來了限制。DC聚類算法是在數據形成的相似性矩陣基礎上進行聚類的，其相似度矩陣是基于歐氏距離測度來計算的。但是歐氏距離描述復雜結構數據集中數據點之間相互關系的能力不足，造成在處理結構復雜數據時聚類效果不佳。對此，一種密度敏感的DC聚類算法已被提出來[12]，雖然該方法對于具有密度流形的數據集的聚類效果較好，但是其仍然難以處理密度不均勻數據。Zelnik-Manor等人則提出了一種基于Self-Tuning相似度的自調節(jié)譜聚類算法[13]，該算法雖然能有效處理密度不均勻數據，但是需要利用譜聚類的拉普拉斯譜映射先將數據映射到低維空間，使得數據更加可分后再聚類。Self-Tuning相似度用于類似DC聚類算法這樣的沒有拉普拉斯譜映射過程的聚類算法效果不佳。針對以上算法存在的問題，本文提出了一種密度自適應的數據競爭（density adaptive data competition，DA-DC）聚類算法。本文算法首先定義了一種局部密度自適應線段，它不但反映了數據點之間的直接距離關系，還包含了數據點的領域內信息，即局部密度。在局部密度自適應線段的基礎上，通過求數據點之間的最短路徑計算出密度自適應相似度，以利用數據分布的全局信息。它能夠同時反映數據集分布的全局空間信息和局部空間信息，可以更好地描述數據點之間的相互關系。仿真實驗表明，DA-DC聚類算法比原有的DC聚類算法具有更好的聚類效果，特別是在處理密度不均勻數據集時，其聚類性能提升更為明顯。

2　數據競爭聚類算法

2.1聚合場模型

定義1數據集借助其內部數據點間一種類似引力場的相互作用而凝聚或分裂為若干個簇。這樣的作用稱為聚合場。

定義2聚合場模型是為了達到描述簇成員數據點與簇中心數據點之間關系的目的，按照聚合場的概念建立起來的模型。

在聚合場中，簇中心數據點跟屬于它的簇成員數據點之間能夠相互吸引，但是不同的簇中心點之間會相互排斥。另外，簇成員點和其他簇中的數據點之間不會發(fā)生作用，成員數據點只能在簇的內部與其簇中心點之間發(fā)生相互作用。在聚合場中，簇中心點集聚了整個簇的聚合能量，也就是說在一個簇的所有數據點之中簇中心點的聚合能量是最大的。

首先，定義xi和xj兩個數據點的相似度Sij為：

依此可計算出整個數據集的相似度矩陣S。

定義3找到和數據點xi距離最近的r個點，xi的聚合能量Ei就是它們與xi的相似度的總和。1< r

2.2基于聚合場模型的聚類

根據聚合場的概念，聚合能量較小的數據點相比于聚合能量較大的數據點，成為簇成員點的可能性會更高。在聚合場模型中，如果想要兩個數據點都有變成簇中心點的可能，那么它們之間的距離必須達到足夠遠。而對于相互之間距離很近的兩個數據點來講，第一種可能性是其中的一個點變?yōu)槌蓡T數據點，第二種可能性是它們兩者都變?yōu)槌蓡T數據點。因此，僅需在相互距離很近的兩個數據點間，通過相互之間的競爭，進而決出更有可能是簇成員點的那個點，就可以從數據集中識別出一個成員數據點。這種數據點之間的競爭叫作數據競爭。

假設數據集X={x1,x2,…,xn}，包含有K個簇，共有n個數據點，dij表示數據點xi、xj間的距離，D代表數據集X的距離矩陣。然后，采用局部最小距離（locally minimum distance，LMD）方法選取參與數據競爭的數據點對。首先對距離矩陣D按行升序排序得到D′，D′的首列是零向量，這是由于數據點和其自身的距離為0，如下所示：

其中，q表示競爭輪數，1

假設xp是X中唯一的一個孤立數據點，由于第1輪數據競爭的次數為n，那么第1輪第n次競爭肯定為xp和其他某一個非孤立點間的競爭，而且必然會將xp標記為簇成員點。這是采用局部最小距離策略的好處之一，即阻止孤立數據點成為簇中心點，從而讓聚類方法對孤立點不敏感。

當簇成員點的數量達到n-K時，結束數據競爭的過程。此時，剩下的K個沒有被標識為成員點的那些數據點就是聚類中心點。然后根據最近鄰法把每個成員點分配給各自的簇聚類中心點，完成聚類。

3　密度自適應相似度

聚類通常被看作是一種無監(jiān)督學習，使用一些數據集自身的先驗信息能夠有效提升聚類質量[14]。例如，先驗一致性假設就是數據集的一個重要信息，即相互距離較近的數據點之間可能有較高的相似度，分布在同一個聚類結構或密集區(qū)域上的數據點間也可能有較高的相似度；前一個假設是局部性的，后一個假設則是全局性的[15]。歐氏距離測度只能夠描述聚類結構的局部一致性特征，而難以描述其全局一致性特征[16]。因此，對于現(xiàn)實世界的復雜結構數據集，采用歐氏距離不能很好地描述數據點之間的相似度，從而不能產生理想的聚類效果。

原有DC聚類算法無法識別密度不均勻的簇結構。密度不均勻簇指的是簇和其周圍簇的數據分布密度具有明顯的差異。例如，圖1所示的toy人工數據集，在其中部有一個相對密集的區(qū)域，可以看作一個簇，它的周圍分布著相對稀疏的背景點則可以看作另一個簇。在歐式距離測度下，數據點a和b之間的相似度比a和c之間的相似度要高。但是a和b不在同一個類中，a實際上應該和同一類中的c相似度更高。導致采用基于歐氏距離相似度的DC聚類算法無法識別這些簇。圖2（a）展示了DC聚類算法在toy數據集上的聚類結果，和實際的聚類分布相差較大。

Fig.1　Artificial toy dataset圖1　toy人工數據集

為了解決上述問題，Zelnik-Manor等人提出了Self-Tuning譜聚類算法[13]。在對具有多重尺度的數據集進行聚類分析時，將數據點所處領域內的密度引入到譜聚類中來。該算法通過數據點領域內密度的大小來對數據點之間的相似度進行調整，定義了一個能夠自適應得到尺度參數σ的高斯相似函數：

其中，dist(xi,xj)表示數據點xi和xj間的歐氏距離；σ表示數據點的局部密度，其定義如下：

σi表示樣本點xi到其第KD個最近鄰居點的距離，根據文獻[13]的建議取KD=7。對于圖1的toy數據集，假設a到b、d兩點的距離相等，即dist(a,b)=dist(a,d)。根據圖1有σb<σd，進而σaσb<σaσd，可得Affinity(a,b)< Affinity(a,d)。這樣就使得a和b兩點的相似度小于a和d兩點的相似度，從而與數據實際分布相符合。

Fig.2　Results of DC using Euclidean distance and Self-Tuning similarity respectively on toy dataset圖2　DC算法分別使用歐氏距離和Self-Tuning相似度在數據集toy上的聚類結果

文獻[13]采用Self-Tuning相似函數來計算譜聚類的相似度矩陣，然后將原始數據映射到拉普拉斯矩陣的特征空間中，這相當于在譜空間中得到原數據集的一個低維嵌入。最后對譜空間中的數據進行聚類。因為得到的低維嵌入在結構分布上更為簡單可分，所以能夠得到良好的聚類結果。但是對于其他算法來說，采用Self-Tuning相似度依然難以處理密度不均勻數據集，例如k-means、AP等。它們沒有拉普拉斯映射這一譜聚類算法具有的步驟，不能在計算相似度矩陣之后，將數據映射到更可分的低維空間里。另外，雖然Self-Tuning相似度添加了數據點的領域內信息，但這僅是一種局部信息，缺乏對數據分布全局信息的挖掘和利用。圖2（b）顯示了DC算法基于Self-Tuning相似度的聚類結果，可見聚類出現(xiàn)明顯錯誤。

根據聚類先驗一致性假設，同一類的數據應分布在同一密度區(qū)域中，不同類的數據應被各密度區(qū)域的邊界線隔離開。對此，本文提出了一種新的密度自適應相似度。它利用了數據點的局部密度信息，并挖掘了數據分布的全局信息，能夠準確地描述數據的實際分布。

首先根據數據集X構造一個加權無向K-近鄰圖G=(V,E)，頂點集合V表示各數據點，邊集合E={Wij}表示每一對數據點間定義的相似度。若兩個數據點位于同一密度區(qū)域內，則它們間可以通過同一密度區(qū)域內的一組邊構成的路徑連接起來，無需穿過不同密度區(qū)域的密度交界線，則它們具有較高相似度。反之，若兩個數據點位于不同密度區(qū)域內，那么連接它們的路徑就需要穿過至少一條密度交界線，則它們具有較低相似度。為了縮短同一密度區(qū)域數據點間距離，并放大不同密度區(qū)域點間距離，在此先定義一種局部密度自適應線段。

定義4給定數據集X={x1,x2,…,xn}，任意兩個數據點xi和xj的局部密度自適應線段（local density adaptive line，LDAL）為：

其中，Affinity(xi,xj)表示數據點xi和xj之間的Self-Tuning相似度。ρ>1是調節(jié)因子，調整ρ的值可以改變局部密度自適應線段對Self-Tuning相似度變化的敏感度，進而改變局部密度自適應線段的長度。此處的K-近鄰是以Self-Tuning相似度為度量的近鄰。從指數 ρ(1-Affinity(xi,xj))可以看出，在 ρ已定的時候，Affinity(xi,xj)越小，則指數越大，則xi和xj之間的局部密度自適應線段就越長。

這樣就沿著數據分布的不同密度區(qū)域的交界線構建一個密度落差帶，由于上面的指數函數會放大密度落差帶兩側數據點之間的距離，使得密度落差帶兩側數據點間的距離遠小于同一密度區(qū)域中數據點間的距離，以達到隔離密度落差帶兩側數據點的目的。然后，通過尋找圖G中兩點間的最短路徑來度量兩點間的相似度。

定義5數據集X中任意兩個數據點xi、xj的密度自適應相似度（density adaptive similarity，DAS）SDAS(xi,xj)為：

其中，DDAS(xi,xj)表示兩點間的最短路徑長度；p∈Vl表示圖G上一個長度為的連接點p1和p||p的路徑，且邊(pk,pk+1)∈E，；DLDAL(pk,pk+1)是結點pk和pk+1之間局部密度自適應線段長度；Pij是連接結點xi和xj的所有路徑所組成的集合。采用Floyd算法[17]計算最短路徑。

根據定義5，位于同一密度區(qū)域內的數據點，它們之間的最短路徑無需穿過密度落差帶，可以通過同一密度區(qū)域內一組相對較短的邊組成，使得它們間的相似度較高。不同密度區(qū)域數據點間的最短路徑需要穿過至少一條密度落差帶，因密度落差帶兩側的數據點間距離被大幅放大，造成穿過密度落差帶的路徑的長度較大，故它們間的相似度較低。這樣就達到了增大同一密度區(qū)域數據點間相似度，同時縮小不同密度區(qū)域數據點間相似度的目的。密度自適應相似度能夠準確描述密度不均勻數據集的實際分布信息，有效提高聚類算法的聚類效果。

4　本文聚類算法

為了增強原有DC聚類算法處理密度不均勻數據集聚類問題的能力，提升其聚類效果，本文結合密度自適應相似度的思想，提出了一種密度自適應的數據競爭聚類算法。本文算法首先計算出數據點之間的局部密度自適應線段長度，然后根據數據集構造無向加權K-近鄰圖。在此基礎上基于兩個數據點之間的最短路徑長度來衡量它們的密度自適應相似度。用得到的密度自適應相似度取代原有DC聚類算法中基于歐氏距離的相似度進行聚類。

4.1算法步驟

輸入：數據集X={x1,x2,…,xn}，聚類個數K，能量調節(jié)參數r，近鄰參數Kn。

輸出：聚類劃分C={c1,c2,…,cK}。

步驟1計算出數據集的歐氏距離矩陣，進而求出數據集中任意兩點間的Self-Tuning相似度，得到Self-Tuning相似度矩陣。

步驟2計算出數據集中任意兩個數據點之間的局部密度自適應線段長度，然后構造無向加權K-近鄰圖。

步驟3根據式（8）計算出數據集的密度自適應相似度矩陣，然后計算出各數據點的聚合能量。

步驟4根據局部最小距離競爭法，依次選取兩個數據點進行競爭，標記聚合能量較小的那個點為簇成員點。

步驟5重復上述步驟4的過程，若簇成員點的數量達到n-K，則結束數據競爭過程。

步驟6根據最近鄰法把每個成員點分配給各自的簇中心點，完成聚類。

4.2算法時間復雜度分析

假設給定的數據集含有n個數據點，能量調節(jié)參數為r，數據競爭的回合數為q，要得到的聚類個數為K。根據上面的描述，計算歐氏距離矩陣D的時間是T1=0.5×n2+0.5×n。計算各數據點局部密度σ的時間是T2=n×nlbn。計算Self-Tuning相似度矩陣Affinity的時間是T3=0.5×n2+0.5×n。計算各點間的局部密度自適應線段并構造近鄰圖花費的時間為T4=n×n×nlbn。計算數據集每對數據點間最短距離矩陣DDAS的時間為T5=n3。因為SDAS=-DDAS，其花費時間忽略不計。然后計算D′的時間為T6=n×nlbn。計算各數據點的聚合能量的時間為T7=r×n，識別成員點的時間為T8

5　實驗與分析

5.1人工數據集

實驗中所使用的6個人工數據集有2pointback、 2pointcircle、flyback、2moon、2spiral和smile。其中前4個數據集均為類簇之間密度具有明顯差別的密度不均勻數據集，而2spiral和smile數據集的不同類簇之間密度較為均勻，以此來對DA-DC算法的性能進行全面的實驗驗證。各數據集的詳細信息如表1所述。

Table 1　Artificial datasets in experiments表1　實驗中使用的人工數據集

在上述6個數據集上面，分別運行DC和DA-DC聚類算法，聚類結果如圖3～圖8所示。

從圖3～圖8中可以看到，DC聚類算法在6個人工數據集上均沒有得到理想的結果，出現(xiàn)了較為嚴重的聚類錯誤，而DA-DC聚類算法在6個人工數據集上全部得到了理想的聚類結果。2pointback和flyback這兩個數據集都由密集分布區(qū)和稀疏的背景點構成。稀疏的背景點使得DC聚類算法難以分辨出密集區(qū)域簇，而DA-DC聚類算法順利識別出了密集類和背景類。2pointcircle數據集，它的兩個密集區(qū)域簇外圍分布著較為稀疏的環(huán)狀數據，而且環(huán)與密集區(qū)距離很近難以識別，而2moon數據集的兩個月牙形數據區(qū)密度分布差異很大。雖然2spiral和smile數據集的類簇間密度較為均勻，但2spiral數據集由兩條帶狀數據區(qū)螺旋纏繞而成，smile數據集由長條狀數據和點狀數據簇圍繞組成，這都加大了它們的聚類難度。DA-DC聚類算法能夠順利處理這6個數據集，表明其在處理密度不均勻數據時性能要優(yōu)于DC聚類算法。

5.2UCI數據集

為了進一步驗證DA-DC聚類算法的性能，采用UCI（University of California Irvine）數據庫中的常用數據集對DA-DC聚類算法進行仿真實驗。UCI數據庫是加州大學歐文分校提出的用于機器學習的數據庫，并且是一個常用的專門用于測試機器學習、數據挖掘算法的公共數據庫，庫中的數據集都有確定的分類。實驗中使用到的6個UCI數據集的詳細信息如表2所述。

Fig.3　Results of two algorithms on 2pointback dataset圖3　兩種算法在數據集2pointback上的聚類結果

Fig.4　Results of two algorithms on 2pointcircle dataset圖4　兩種算法在數據集2pointcircle上的聚類結果

Fig.5　Results of two algorithms on flyback dataset圖5　兩種算法在數據集flyback上的聚類結果

Fig.6　Results of two algorithms on 2moon dataset圖6　兩種算法在數據集2moon上的聚類結果

Fig.7　Results of two algorithms on 2spiral dataset圖7　兩種算法在數據集2spiral上的聚類結果

Fig.8　Results of two algorithms on smile dataset圖8　兩種算法在數據集smile上的聚類結果

Table 2　UCI datasets表2　UCI數據集

實驗采用常用的F-measure指標[18]和ARI（adjusted rand index）[19]指標對聚類結果進行評價。

F-measure指標通過算法的準確率和查全率計算得到。類t和聚類Ck的準確率和查全率分別為：

其中，Ntk代表類k中類別為t的樣本數；Nk代表聚類k中的樣本數；Nt代表類別t中的樣本數。則此類的F-measure計算公式為：

整個聚類劃分的F-measure值為：

其中，N表示數據集內數據點的總數；C表示算法運行得到的類的集合；T表示數據集的真實類別的集合；F-measure指標的取值范圍是[0,1]，其取值越大，則表示算法越準確。

ARI指標是常用的聚類評價標準。它通過聚類前后成對數據點之間的關系來評價聚類結果。將聚類結果和其真實的數據集對比，各成對數據點有4種可能：屬于同一簇的兩個點被分到同一簇中，此點對數量為a；屬于同一簇的兩個點被分到不同簇中，此點對數量為b；屬于不同簇的兩個點被分到同一簇中，此點對數量為c；屬于不同簇的兩個點被分到不同簇中，此點對數量為d。ARI指標計算公式為：

顯然，ARI指標值越大，表示聚類效果越好。

表3顯示了在6個UCI數據集上DC和DA-DC兩種聚類算法的F-measure指標對比情況。從中可以看出，DA-DC聚類算法在全部6個UCI數據集上的F-measure指標均優(yōu)于現(xiàn)有的DC聚類算法。尤其在ionosphere數據集上F-measure指標值提升了30%多。表4顯示了在6個UCI數據集上DC和DA-DA兩種聚類算法的ARI指標對比情況。從中可以看出，在glass數據集上，DA-DC聚類算法比DC聚類算法的ARI指標略低。但是，DA-DC聚類算法在其他5個UCI數據集上的ARI指標均高于DC聚類算法。特別是在ionosphere數據集上，DA-DC算法的ARI值比DC算法有很明顯的提高。

Table 3　F-measure index on UCI datasets表3　UCI數據集上的F-measure指標對比

Table 4　ARI index on UCI datasets表4　UCI數據集上的ARI指標對比

另外，為了直觀展示算法在真實數據上的執(zhí)行情況，給出了在user knowledge model數據集上的可視化聚類結果，如圖9所示。因為真實數據集一般維數較高，難以用2維或3維圖形顯示，這里使用可以保持原有數據集局部結構的局部線性嵌入（locally linear embedding）算法[20]將數據先進行維數約簡，然后再進行可視化顯示。

Fig.9　Results of two algorithms on user knowledge model dataset圖9　兩種算法在數據集user knowledge model上的聚類結果

綜上所述，DA-DC聚類算法整體上取得了更好的聚類效果。正因為局部密度自適應線段包含了數據集中數據點的領域內信息，即數據點的局部數據分布密度，它能夠描述數據的局部分布特征；通過計算數據點間最短路徑得到的密度自適應相似度能夠有效反映數據的全局結構信息。因此，相比于原DC聚類算法中基于歐氏距離的相似度，密度自適應相似度能夠更好地描述數據的實際分布信息。采用密度自適應相似度能夠更準確地計算出每個數據點的聚合能量，并設置更好的數據競爭次序，使得算法面對密度不均勻數據集時能夠正確產生聚類中心，并準確將數據點分配給聚類中心，有效提高聚類效果。因此，DA-DC聚類算法在處理密度不均勻數據集時比現(xiàn)有的DC算法具有更高的聚類性能。

5.3算法運行效率與參數分析

由4.2節(jié)算法時間復雜度分析可知，DA-DC算法的時間復雜度為O(n3)，由文獻[10]可知，DC算法的時間復雜度為O(n2lbn)。因此DA-DC算法在取得較好聚類結果的同時，由于使用了最短路徑算法，時間復雜度要高于原有DC算法。表5給出了兩種算法在不同數據集上的運行時間對比。各算法均在Matlab R2010b環(huán)境下編程實現(xiàn)，在同一PC機（Windows7 64位操作系統(tǒng)，Intel CPU 3.40 GHz，4 GB內存）上運行。

Table 5　Running time on UCI datasets表5　UCI數據集上的運行時間對比　s

由表5可以看出，DA-DC算法的運行時間約為DC算法的10倍。這對于DA-DC算法處理大規(guī)模數據集比較不利。下一步將研究如何在利用數據集固有先驗信息提高數據競爭聚類算法性能的同時降低時間復雜度。

另外，算法中共有5個參數：聚類個數K，能量調節(jié)參數r，計算局部密度的距離參數KD，調節(jié)因子ρ，近鄰參數Kn，其中后兩個參數是本文算法新引入的。聚類個數K由手動設定，決定可聚類結果中類簇的個數，對于一個數據集來說其屬于先驗信息，無需調整。能量調節(jié)參數r和距離參數KD分別采用文獻[10]和文獻[13]中的設置方法，兩個文獻中已對它們有所說明。因此，這里選擇了ecoli和ionosphere兩個UCI真實數據集進行仿真實驗，分析近鄰參數Kn和調節(jié)因子ρ這兩個參數對算法的影響。

圖10顯示了DA-DC聚類算法受近鄰參數和調節(jié)因子兩個參數影響的情況。從圖10（a）可以看出，在Kn大于5以后，算法對該參數不再敏感，結果趨于穩(wěn)定。從圖10（b）可以看出，算法結果在ρ大于7以后趨于穩(wěn)定。參數Kn可以在[5,10]范圍內取，參數ρ的值建議在[2,9]范圍內取。本文全部實驗中，Kn的值默認取8，ρ的值默認取5。圖10的結果表明，盡管DA-DC算法對Kn和ρ兩個參數有所依賴，但是它們均有相對穩(wěn)定的取值范圍。

Fig.10　Influence ofKnandρon DA-DC algorithm圖10　Kn和ρ兩種參數對DA-DC算法的影響

6　結束語

本文針對原有數據競爭（DC）聚類算法在處理密度不均勻數據集時聚類性能較差的問題，提出了一種密度自適應的數據競爭（DA-DC）聚類算法。本文算法定義了一種密度自適應相似度測度，能夠比原有DC聚類算法中的基于歐氏距離的相似度更加符合數據的實際聚類分布。將密度自適應相似度思想引入DC聚類算法中得到DA-DC聚類算法，從而能夠有效處理密度不均勻數據的聚類問題。在6個人工數據集和6個UCI數據集上的仿真實驗結果證明了本文算法的有效性。

[1]Jain A K,Murty M N,Flynn P J.Data clustering:a review[J]. ACM Computing Surveys,1999,31(3):264-323.

[2]Rebecca N,Marina M.An overview of clustering applied to molecular biology[J].Methods in Molecular Biology,2010, 620:369-404.

[3]Higgs B,Abbas M.Segmentation and clustering of carfollowing behavior:recognition of driving patterns[J].IEEE Transactions on Intelligent Transportation Systems,2015, 16(1):81-90.

[4]Ben-Gal I,Shavitt Y,Weinsberg E,et al.Peer-to-peer information retrieval using shared-content clustering[J].Knowledge and Information Systems,2014,39(2):383-408.

[5]De Angelis L,Dias J G.Mining categorical sequences from data using a hybrid clustering method[J].European Journal of Operational Research,2014,234(3):720-730.

[6]Saeed M,Javed K,Babri H A.Machine learning using Bernoulli mixture models:clustering,rule extraction and dimensionality reduction[J].Neurocomputing,2013,119:366-374.

[7]Macqueen J.Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley:University of California Press,1967:281-297.

[8]Filippone M,Camastra F,Masulli F,et al.A survey of kernel and spectral methods for clustering[J].Pattern Recognition,2008,41(1):176-190.

[9]Frey B J,Dueck D.Clustering by passing messages between data points[J].Science,2007,315(5814):972-976.

[10]Lu Zhimao,Zhang Qi.Clustering by data competition[J].Science China:Information Sciences,2013,56(1):1-13.

[11]Lu Zhimao,Fan Dongmei,Chen Bingcai,et al.A data competition based clustering algorithm for large image segmentation[J].Science China:Information Sciences,2012,42 (9):1147-1157.

[12]Su Hui,Ge Hongwei,Zhang Huanqing,et al.Density-sensitive clustering by data competition algorithm[J].Journal of ComputerApplications,2015,35(2):444-447.

[13]Zelnik-Manor L,Perona P.Self-tuning spectral clustering[J]. Advances in Neural Information Processing Systems,2004, 17:1601-1608.

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

[15]Wang Ling,Bo Liefeng,Jiao Licheng.A modified k-means clustering with a density-sensitive distance metric[C]//LNCS 4062:Proceedings of the 1st International Conference on Rough Sets and Knowledge Technology,Chongqing,Jul 24-26,2006.Berlin,Heidelberg:Springer,2006:544-551.

[16]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.

[17]Pradhan A,Mahinthakumar G.Finding all-pairs shortest path for a large-scale transportation network using parallel Floyd-Warshall and parallel Dijkstra algorithms[J].Journal of Computing in Civil Engineering,2012,27(3):263-273.

[18]Witten I H,Frank E,Hall M A.Data mining:practical machine learning tools and techniques[M].3rd ed.San Francisco: Morgan Kaufmann Publishers,2011.

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

[20]Roweis S T,Saul L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500): 2323-2326.

附中文參考文獻：

[11]盧志茂,范冬梅,陳炳才,等.一種基于數據競爭的高分辨率圖像的聚類分割算法[J].中國科學:信息科學,2012,42 (9):1147-1157.

[12]蘇輝,葛洪偉,張歡慶,等.密度敏感的數據競爭聚類算法[J].計算機應用,2015,35(2):444-447.

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

SU Hui was born in 1991.He is an M.S.candidate at School of Internet of Things Engineering,Jiangnan University, and the member of CCF.His research interests include pattern recognition and artificial intelligence.

蘇輝（1991—），男，安徽蚌埠人，江南大學物聯(lián)網工程學院碩士研究生，CCF會員，主要研究領域為模式識別，人工智能。

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 Jiangnan University.His research interests include artificial intelligence,pattern recognition and image processing.

葛洪偉（1967—），男，江蘇無錫人，1992年于南京航空航天大學計算機系獲得碩士學位，2008年于江南大學信息學院獲得博士學位，現(xiàn)為江南大學物聯(lián)網工程學院教授，主要研究領域為人工智能，模式識別，圖像處理。在國際權威期刊、國際會議和國內核心期刊上發(fā)表論文70多篇，主持和承擔了國家自然科學基金等國家級項目和省部級項目近20項，獲省部級科技進步獎多項。

ZHANG Tao was born in 1989.He is an M.S.candidate at School of Internet of Things Engineering,Jiangnan University.His research interests include pattern recognition and artificial intelligence.

張濤（1989—），男，江蘇徐州人，江南大學物聯(lián)網工程學院碩士研究生，主要研究領域為模式識別，人工智能。

DensityAdaptive Data Competition ClusteringAlgorithm*

SU Hui1,GE Hongwei1,2+,ZHANG Tao1
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

E-mail:ghw8601@163.com

Since the existing data competition clustering algorithm has poor performance on density inhomogeneous datasets,this paper proposes a density adaptive data competition clustering algorithm.Firstly,a local density adaptive line is defined.Nextly,the density adaptive similarity can be calculated based on local density adaptive line.The density adaptive similarity can reflect the global data space distribution information and local information of data points, which can describe the relationship between data points more effectively.Then,the density adaptive similarity is used in data competition clustering algorithm.The simulation results on synthetic and real life datasets show that the proposed algorithm can obtain better performance on density inhomogeneous datasets than existing data competition clustering algorithm.

clustering;data competition;aggregation field;density inhomogeneous

2015-08,Accepted 2015-11.

10.3778/j.issn.1673-9418.1508059

A

TP18

*The National Natural Science Foundation of China under Grant No.61402203(國家自然科學基金);the Postgraduates Research and Innovation Program of Jiangsu Province under Grant Nos.KYLX15_1169,KYLX_1122(江蘇省高校研究生科研創(chuàng)新計劃).

CNKI網絡優(yōu)先出版:2015-11-12,http://www.cnki.net/kcms/detail/11.5602.TP.20151112.1520.006.html

SU Hui,GE Hongwei,ZHANG Tao.Density adaptive data competition clustering algorithm.Journal of Frontiers of Computer Science and Technology,2016,10(10):1439-1450.