邱保志，唐雅敏

(鄭州大學 信息工程學院，鄭州450001)

快速識別密度骨架的聚類算法

邱保志，唐雅敏*

(鄭州大學 信息工程學院，鄭州450001)

針對如何快速尋找密度骨架、提高高維數(shù)據(jù)聚類準確性的問題，提出一種快速識別高密度骨架的聚類(ECLUB)算法。首先，在定義了對象局部密度的基礎(chǔ)上，根據(jù)互k近鄰一致性及近鄰點局部密度關(guān)系，快速識別出高密度骨架；然后,對未分配的低密度點依據(jù)鄰近關(guān)系進行劃分，得到最終聚類。人工合成數(shù)據(jù)集及真實數(shù)據(jù)集上的實驗驗證了所提算法的有效性，在Olivetti Face數(shù)據(jù)集上的聚類結(jié)果顯示，ECLUB算法的調(diào)整蘭德系數(shù)(ARI)和歸一化互信息(NMI)分別為0.877 9和0.962 2。與經(jīng)典的基于密度的聚類算法(DBSCAN)、密度中心聚類算法(CFDP)以及密度骨架聚類算法(CLUB)相比，所提ECLUB算法效率更高，且對于高維數(shù)據(jù)聚類準確率更高。

聚類算法；高維數(shù)據(jù)；k近鄰；密度骨架；局部密度

0 引言

聚類是數(shù)據(jù)挖掘中研究最活躍的領(lǐng)域之一，它依據(jù)相似性將相似的對象聚集在一起形成一個簇，不同簇中的對象具有高度不相似性。聚類是無監(jiān)督學習，在分析數(shù)據(jù)的內(nèi)部結(jié)構(gòu)、屬性之間的關(guān)系等方面有重要的作用，并已經(jīng)廣泛應用于模式識別、圖像處理、市場分析等領(lǐng)域[1-4]。目前，學者們對聚類技術(shù)進行了深入的研究，提出了大量算法，如K-means[5]、經(jīng)典的基于密度聚類(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)算法[6]等，如何提高算法的效率和對高維空間聚類的準確性依然是值得研究的問題[7-8]。

K-means是基于劃分的聚類算法，適用于對含有球形簇的數(shù)據(jù)集進行聚類，由于算法中使用歐氏距離，故對高維數(shù)據(jù)集的聚類結(jié)果精度不高。

基于密度的聚類由于其能發(fā)現(xiàn)任意形狀、大小的聚類而備受關(guān)注[9]。DBSCAN是基于密度聚類的經(jīng)典算法，它認為一個聚類由核心點和非核心點組成，密度可達的核心點集合構(gòu)成聚類的骨架，由骨架中的核心點可達的非核心點組成聚類肌肉。但基于密度的聚類算法不適合于多密度數(shù)據(jù)集和含有橋接聚類的數(shù)據(jù)集，聚類精度與鄰域半徑、密度閾值兩個參數(shù)高度相關(guān)，時間復雜度為O(n2)，由于DBSCAN使用歐幾里得度量距離，致使在處理高維數(shù)據(jù)集時陷入維數(shù)災難。

為提高聚類質(zhì)量，Rodriguez等[10]將基于中心劃分和基于密度劃分的方法相結(jié)合提出密度中心聚類(Clustering by Fast search and find of Density Peaks, CFDP)算法，該算法認為聚類中心具有較大局部密度且彼此相距較遠，剩余點就近分配給比其密度高的點所在聚類。從骨架的角度分析，聚類中心及其周圍擁有大于平均局部密度上界的核心點集合構(gòu)成聚類的骨架，與已分類數(shù)據(jù)點距離小于截斷距離(cutoff distance)的非核心點集合形成聚類肌肉。CFDP算法可自動識別出含噪聲和任意形狀、密度的簇；但是當一個簇中包含多個核心點時，算法會將一個完整的簇劃分為多個簇，且該算法的整體時間復雜度較高。

針對DBSCAN和CFDP均不適用于多密度數(shù)據(jù)集且時間復雜度較高的問題，Chen等提出密度骨架聚類(CLUstering based on Backbone, CLUB)算法[11]，依據(jù)互k近鄰一致性，將互為k近鄰的點劃為同一簇[12]，形成初始簇，并在每個初始簇中分別使用k近鄰識別出密度骨架，未分配的低密度點尋找距離其最近的高密度點，形成聚類肌肉。該算法使用密度骨架獲得簇結(jié)構(gòu)，有效解決了橋接簇和同一個簇中出現(xiàn)多個聚類中心而導致錯誤劃分的問題；使用空間索引查找k近鄰點，將時間復雜度降低為O(n·logn)。但該算法在識別密度骨架的過程中，兩次建立索引查找k近鄰點，形成初始聚類之后，要計算每個簇中數(shù)據(jù)點的局部密度并進行排序，故實際的運行時間開銷依舊很大。能否通過一次查找k近鄰得到高密度骨架是值得研究的問題。

為提高聚類算法的效率和在高維數(shù)據(jù)集上的聚類準確性，本文提出一種快速識別高密度骨架的聚類(Efficient CLUstering based on density Backbone, ECLUB)算法。本文的主要工作如下：

1)定義一種基于k近鄰的對象局部密度計算方法，可用于高維空間數(shù)據(jù)密度的計算；

2)提出一種識別密度骨架的簡單方法，能快速識別出任意形狀、任意密度的聚類骨架。

1 ECLUB算法

1.1 符號與定義

設(shè)數(shù)據(jù)集D={x1,x2,…,xn}，其中xi=(xi1,xi2,…,xim)(i=1,2,…,n)。

定義1k近鄰集。給定x∈D，距離點x最近的前k個點x構(gòu)成的k近鄰集，記作NNk(x):

NNk(x)={y∈D|d(x,y)≤kdist(x)}

其中：d(x,y)表示點x和y的歐氏距離；kdist(x)表示點x到其第k個最近鄰點的歐氏距離。

定義2 互k近鄰。給定x,y∈D，如果x∈NNk(y)且y∈NNk(x)，稱x和y互為k近鄰。

互為k近鄰的兩個點，極有可能在同一個簇[11]。

定義3 共享k近鄰集。給定x,y∈D，如果x和y互為k近鄰，?z∈D既屬于NNk(x)，又屬于NNk(y)，稱z為x和y的共享k近鄰點，這樣的點構(gòu)成集合稱為x和y的共享k近鄰集，記作SNN(x,y)：

SNN(x,y)=NNk(x)∩NNk(y)

若點x和y互為k近鄰且同屬一個簇，則x和y的共享k近鄰點也極有可能同屬這一類[11]。

定義4 對象的局部密度。點x的局部密度定義為σ(x)：

(1)

定義5 簇密度。簇密度是指簇中所有對象的局部密度的平均值，簇C的簇密度記為den(C)：

(2)

其中：|C|表示簇C中數(shù)據(jù)點總個數(shù)。簇密度作為判斷是否將數(shù)據(jù)對象劃分為同一簇和是否能合并兩個簇的依據(jù)。

定義6 點簇密度相似度。給定x,y∈D，x與簇C的點簇密度相似度記作SDC(x,C)：

SDC(x,C)=|1-σ(x)/den(C)|

(3)

點簇密度相似度表征點與簇在密度上的相似程度，越接近0，說明點x的局部密度與簇C中包含點的局部密度越接近。

定義7 簇密度相似度。給定兩個簇Cp、Cq，Cp∩Cq=?，簇密度相似度記作SCC(Cp,Cq)

(4)

在CLUB算法中，若點xi和xj互為k近鄰，則xi、xj以及它們的SNN(xi,xj)極有可能在同一個簇。若增加CLUB算法在識別密度骨架時對密度的限制條件，則更有把握將滿足以下條件的數(shù)據(jù)對象分為一類，ε值的取值范圍為[0,1)。

條件1 若xi和xj互為k近鄰，xi∈Cq,xj未標記，且滿足SDC(xj,Cq)≤ε，則將點xi和xj劃為同一簇，即xj∈Cq。

條件2 若xi,xj∈Cq,xk∈SNN(xi,xj)，xk未標記，且滿足SDC(xk,Cq)≤ε，則將點xk、xi和xj劃分為同一簇，即xk∈Cq。

條件3 若xi和xj互為k近鄰，xi∈Cp,xj∈Cq，且滿足SCC(Cp,Cq)≤ε，則合并簇Cp和簇Cq。

1.2 ECLUB算法步驟

ECLUB算法基于以下思想：互為k近鄰的高密度點及其SNN在滿足密度相近的條件下可分為一類，形成高密度骨架，未分配的低密度點尋找距離其最近的高密度點形成聚類肌肉或標記為離群點。ECLUB算法描述如算法1所示。

算法1 ECLUB。

輸入 數(shù)據(jù)集D、近鄰點個數(shù)k；

輸出 聚類結(jié)果C。

b)將滿足條件1、2和3的數(shù)據(jù)對象分為一類，更新簇密度。

步驟3 低密度點的分配。未標記的低密度點與其互為k近鄰的點分為一類，若其不存在互為k近鄰的點，則標記為離群點。

ECLUB算法定義了對象的局部密度，在識別密度骨架的過程中，同時考慮近鄰關(guān)系以及點、簇的密度關(guān)系，通過一次查找k近鄰點，一次遍歷數(shù)據(jù)對象，得到高密度骨架，提高了算法效率。

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

本文所有實驗環(huán)境均為Windows 7 64位操作系統(tǒng)，Matlab R2015a軟件，CPU為AMD 3.4 GHz，內(nèi)存為4 GB。

2.1 實驗數(shù)據(jù)集

實驗選用8個數(shù)據(jù)集，其中3個人工合成數(shù)據(jù)集來自同類研究的相關(guān)文獻[10-11]，分別用于驗證ECLUB算法在處理橋接簇、多密度簇和非球形簇的能力；5個真實數(shù)據(jù)集來源于UCI機器學習數(shù)據(jù)庫[13]和Olivetti Face數(shù)據(jù)庫[14]的100張頭像，用于驗證ECLUB算法對真實的高維數(shù)據(jù)處理的有效性。Olivetti Face數(shù)據(jù)集中包含10個人物，每個人物擁有不同表情、側(cè)臉、是否佩戴眼鏡等特征的10張頭像圖片。表1詳細描述了實驗中使用到的數(shù)據(jù)集。

表1 實驗中用到的人工合成數(shù)據(jù)集和真實數(shù)據(jù)集Tab. 1 Synthetic datasets and real datasets used in the experiment

2.2 評價指標

實驗的評價指標采用調(diào)整蘭德系數(shù)(Adjusted Rand Index, ARI)和歸一化互信息(Normalized Mutual Information, NMI)，這兩個指標用于度量聚類結(jié)果的準確性，取值越接近1，表明聚類結(jié)果越準確。

2.3 算法有效性分析

圖1是ECLUB算法在不同數(shù)據(jù)集上的聚類結(jié)果，不同灰度點代表不同簇。圖1(a)是k∈[16,18]時的聚類結(jié)果，表明ECLUB算法可以準確識別出aggregation數(shù)據(jù)集中橋接聚類的簇；圖1(b)是k∈[6,9]時的聚類結(jié)果，表明ECLUB算法能夠準確識別出compound數(shù)據(jù)集中相互嵌套的多密度簇；圖1(c)是k∈[45,60]時的聚類結(jié)果，表明ECLUB算法能夠有效識別T4數(shù)據(jù)集中帶有干擾線的非球形聚類。上述三個二維數(shù)據(jù)集上的聚類結(jié)果驗證了ECLUB算法的有效性。

圖2顯示ECLUB算法對Olivetti Face數(shù)據(jù)集的聚類結(jié)果，同一簇用相同灰度值的圖片表示，右下最后一個頭像圖片灰度值最低，用于表示不屬于任何簇。ECLUB算法能準確識別出8個簇，分別為前兩個和后六個人物，中間(第3、4個)人物誤分為一類，ARI和NMI分別為0.877 9和0.962 2；文獻[11]給出了CLUB算法對Olivetti Face數(shù)據(jù)集的聚類結(jié)果，CLUB算法能夠識別出8個簇，其中：3個頭像未分類，14個頭像誤分類，ARI和NMI分別為0.775 8和0.884 3。可以看出，ECLUB算法對于Olivetti Face數(shù)據(jù)集的聚類結(jié)果準確性要高于CLUB算法。

圖1 ECLUB算法在人工數(shù)據(jù)集上的聚類結(jié)果Fig. 1 Clustering results of ECLUB algorithm on artificial datasets

圖2 ECLUB算法在Olivetti Face數(shù)據(jù)集的聚類結(jié)果Fig. 2 Clustering results of ECLUB algorithm on Olivetti Face dataset

表2采用ARI和NMI對4種算法在人工數(shù)據(jù)集和真實數(shù)據(jù)集的實驗結(jié)果進行評價(T4數(shù)據(jù)集缺少真實類標號，不包含其評價)。ECLUB與CLUB算法相比，ECLUB算法的ARI值有6項為最高，NMI值有5項為最高；CLUB算法的ARI值有4項為最高，NMI值有5項為最高。ECLUB算法對Segmentation和compound數(shù)據(jù)集的聚類準確性低于CLUB算法，但偏差極??；對Glass和Olivetti Face數(shù)據(jù)集的聚類準確性比CLUB算法平均提高了25.02%。同樣，ECLUB算法的ARI和NMI評價指標在絕大多數(shù)的數(shù)據(jù)集上均高于CFDP和DBSCAN算法。整體來看，上述結(jié)果驗證了ECLUB算法在人工數(shù)據(jù)集和高維真實數(shù)據(jù)集聚類結(jié)果的有效性和準確性。

2.4 算法時間復雜度及運行效率分析

本文算法使用局部敏感哈希函數(shù)[7]查找k近鄰，時間復雜度為O(nlogn)，其中n為數(shù)據(jù)集總個數(shù)。在ECLUB算法步驟步驟1中使用快速排序算法對點局部密度降序排列，時間復雜度為O(nlogn)；識別密度骨架時僅考慮前2/3的數(shù)據(jù)量，時間復雜度為O(2kn/3)，其中，k為近鄰個數(shù)，通常k?n，故可記為O(n)；對低密度點進行分配時，時間復雜度為O(kn/3)，通常剩余點數(shù)遠小于n/3，甚至接近于0，故可忽略不計。因此ECLUB算法的整體時間復雜度為O(nlogn)。

CFDP算法和DBSCAN算法的時間復雜度為O(n2)，隨著數(shù)據(jù)量的增加，算法運行時間呈指數(shù)型增長；ECLUB算法和CLUB算法的時間復雜度為O(nlogn)，接下來主要對比ECLUB和CLUB算法在不同數(shù)據(jù)量上的運行時間。在人工合成數(shù)據(jù)集上分別執(zhí)行ECLUB和CLUB算法，針對不同數(shù)據(jù)量，每種算法均獨立運行10次，選取10次實驗的平均值作為算法在該數(shù)據(jù)量上的運行時間。如圖3所示，隨著數(shù)據(jù)量的增加，ECLUB算法較CLUB的高效性逐步凸顯。當數(shù)據(jù)量為20 000時，CLUB算法的運行時間為777.060 s，ECLUB算法的運行時間為486.008 s。

表2 不同算法在不同數(shù)據(jù)集上的聚類結(jié)果Tab. 2 Clustering results of different algorithms on different datasets

圖3 不同數(shù)據(jù)量上ECLUB和CLUB的運行時間對比Fig.3 Running time comparison of ECLUB and CLUB on different data volumes

雖然ECLUB算法與CLUB算法時間復雜度相同，但后者在識別密度骨架時，首先通過互k近鄰和共享k近鄰集識別初始簇，然后要對每個初始簇中的數(shù)據(jù)點重新查找k近鄰，并計算局部密度。在實際運行情況下，ECLUB算法僅需一步識別密度骨架，故與CLUB算法相比，運行效率更高。

2.5 高密度點所占比例與相似度閾值的分析

圖4展示了經(jīng)降序排列后的點局部密度的斜率變化情況，從a點之后，點局部密度值開始呈現(xiàn)快速降低，由高密度點逐步轉(zhuǎn)化為低密度點。根據(jù)a點所處位置，判斷出高密度點所占比例。在人工數(shù)據(jù)集和真實數(shù)據(jù)集上的實驗顯示，高密度點所占比例的選取具有魯棒性，圖4中兩種數(shù)據(jù)的高密度點所占比例可選范圍分別為[40%,80%]、[32%,82%]。本文中統(tǒng)一將2/3作為高密度點所占比例。

相似度閾值ε的大小約束著局部密度差異對數(shù)據(jù)點劃分和簇合并的影響程度。根據(jù)點簇密度相似度和簇密度相似度的定義，SDC(x,C)≤ε,即|1-σ(x)/den(C)|≤ε，可轉(zhuǎn)化為den(C)·(1-ε)≤σ(x)≤den(C)·(1+ε)，故0≤ε<1；同理，SCC(Cp,Cq)≤ε，即|1-2den(Cq)/(den(Cp)+den(Cq))|≤ε，可轉(zhuǎn)化為|den(Cp)-den(Cq)|/(den(Cp)+den(Cq))≤ε，故0≤ε<1。ε值過大，容易將密度差異大的數(shù)據(jù)點分為一類;相反，ε值過小，導致局部密度相近的點或簇不能準確地進行合并。從圖5可以看出，隨著ε值的增大，ARI呈現(xiàn)先增大后減小的趨勢。在人工數(shù)據(jù)集和真實數(shù)據(jù)集上的實驗結(jié)果表明，ε值在[0.01,0.8]的范圍內(nèi)，ARI均能取得較高值，當ε值為0.01時，ARI均為最高。本文實驗中統(tǒng)一將ε取值為0.01。

圖4 經(jīng)降序排列后的局部密度斜率變化Fig.4 Slope changes of local density after listing in descending order

圖5 不同數(shù)據(jù)集上ε值變化對ARI的影響Fig.5 Effect of ε value on ARI for different datasets

3 結(jié)語

本文提出一種快速識別密度骨架的聚類算法ECLUB，該算法在識別密度骨架的過程中，同時考慮近鄰關(guān)系以及點和簇的密度關(guān)系，避免了CLUB算法必須通過兩步識別高密度骨架的缺陷。ECLUB算法可以有效發(fā)現(xiàn)任意形狀、不同密度的簇，可適用于任意維度，在保證算法聚類結(jié)果準確性有所提高的同時，提高算法聚類速度。如何在密度骨架的基礎(chǔ)上，進一步提高聚類準確性是下一步的研究工作。

References)

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

[2] 伍育紅.聚類算法綜述[J].計算機科學,2015,42(z1):491-499,524.(WU Y H. General overview on clustering algorithms [J]. Computer Science, 2015, 42(z1): 491-499,524.)

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

[4] 陳治平,胡宇舟,顧學道.聚類算法在電信客戶細分中的應用研究[J].計算機應用,2007,27(10):2566-2569,2577.(CHEN Z P, HU Y Z, GU X D. Applied research of clustering algorithm in telecom consumer segments [J]. Journal of Computer Applications, 2007, 27(10): 2566-2569, 2577.)

[5] BRODER A, GARCIA-PUETO L, JOSIFOVSKI V, et al. ScalableK-means by ranked retrieval [C]// WSDM 2014: Proceedings of the 7th ACM International Conference on Web Search and Data Mining. New York: ACM, 2014: 233-242.

[6] MIYAHAR S, MIYANOTO S. A family of algorithms using spectral clustering and DBSCAN [C]// Proceedings of the 2014 IEEE International Conference on Granular Computing. Piscataway, NJ: IEEE, 2014: 196-200.

[7] 邱保志,賀艷芳,申向東.熵加權(quán)多視角核K-means算法[J].計算機應用,2016,36(6):1619-1623.(QIU B Z, HE Y F, SHEN X D. Multi-view kernelK-means algorithm based on entropy weighting [J]. Journal of Computer Applications. 2016,36(6):1619-1623.)

[8] PARSONS L, HAQUE E, LIU H. Subspace clustering for high dimensional data: a review [J]. ACM SIGKDD Explorations Newsletter, 2004, 6(1): 90-105.

[9] LYU Y H, MA T H, TANG M L, et al. An efficient and scalable density-based clustering algorithm for datasets with complex structures [J]. Neurocomputing, 2016, 171(C): 9-22.

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

[11] CHEN M, LI L J, WANG B, et al. Effectively clustering by finding density backbone based-onkNN [J]. Pattern Recognition, 2016, 60: 486-498.

[12] ALTMAN N S. An introduction to kernel and nearest-neighbor nonparametric regression [J]. American Statistician, 1992, 46(3): 175-185.

[13] ASUNCION A, NEWMAN D. UCI machine learning repository [EB/OL]. [2017- 03- 27]. http://archive.ics.uci.edu/ml/.

[14] AT&T Laboratories Cambridge. The database of faces at a glance [EB/OL]. [2017- 03- 27]. http://www.cl.cam.ac.uk/research/dtg/attarchive/facesataglance.html.

This work is partially supported by the Basic and Advanced Technology Research Project of Henan Province (152300410191).

QIUBaozhi, born in 1964, Ph. D., professor. His research interests include data mining, artificial intelligence.

TANGYamin, born in 1991, M. S. candidate. Her research interests include data mining.

Efficientclusteringalgorithmforfastrecognitionofdensitybackbone

QIU Baozhi, TANG Yamin*

(SchoolofInformationEngineering,ZhengzhouUniversity,ZhengzhouHenan450001,China)

In order to find density backbone quickly and improve the accuracy of high-dimensional data clustering results, a new algorithm for fast recognition of high-density backbone was put forward, which was named Efficient CLUstering based on density Backbone (ECLUB) algorithm. Firstly, on the basis of defining the local density of object, the high-density backbone was identified quickly according to the mutual consistency ofk-nearest neighbors and the local density relation of neighbor points. Then, the unassigned low-density points were divided according to the neighborhood relations to obtain the final clustering. The experimental results on synthetic datasets and real datasets show that the proposed algorithm is effective. The clustering results of Olivetti Face dataset show that, the Adjusted Rand Index (ARI) and Normalized Mutual Information (NMI) of the proposed ECLUB algorithm is 0.877 9 and 0.962 2 respectively. Compared with the Density-Based Spatial Clustering of Applications with Noise (DBSCAN) algorithm, Clustering by Fast search and find of Density Peaks (CFDP) algorithm and CLUstering based on Backbone (CLUB) algorithm, the proposed ECLUB algorithm is more efficient and has higher clustering accuracy for high-dimensional data.

clustering algorithm; high-dimensional data;k-nearest neighbor; density backbone; local density

2017- 06- 01;

2017- 08- 17。

河南省基礎(chǔ)與前沿基金資助項目(152300410191)。

邱保志(1964—)，男，河南駐馬店人，教授，博士，CCF會員，主要研究方向：數(shù)據(jù)挖掘、人工智能； 唐雅敏(1991—)，女，河南鄭州人，碩士研究生，主要研究方向：數(shù)據(jù)挖掘。

1001- 9081(2017)12- 3482- 05

10.11772/j.issn.1001- 9081.2017.12.3482

(*通信作者電子郵箱yamin_tang@163.com)

TP391.4

A