邱保志，唐雅敏

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

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

邱保志，唐雅敏*

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

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

聚類算法；高維數據；k近鄰；密度骨架；局部密度

0 引言

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

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

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

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

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

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

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

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

1 ECLUB算法

1.1 符號與定義

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

定義1k近鄰集。給定x∈D，距離點x最近的前k個點x構成的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近鄰點，這樣的點構成集合稱為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中數據點總個數。簇密度作為判斷是否將數據對象劃分為同一簇和是否能合并兩個簇的依據。

定義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算法在識別密度骨架時對密度的限制條件，則更有把握將滿足以下條件的數據對象分為一類，ε值的取值范圍為[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。

輸入 數據集D、近鄰點個數k；

輸出 聚類結果C。

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

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

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

2 實驗結果與分析

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

2.1 實驗數據集

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

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

2.2 評價指標

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

2.3 算法有效性分析

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

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

圖1 ECLUB算法在人工數據集上的聚類結果Fig. 1 Clustering results of ECLUB algorithm on artificial datasets

圖2 ECLUB算法在Olivetti Face數據集的聚類結果Fig. 2 Clustering results of ECLUB algorithm on Olivetti Face dataset

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

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

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

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

表2 不同算法在不同數據集上的聚類結果Tab. 2 Clustering results of different algorithms on different datasets

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

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

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

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

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

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

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

3 結語

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

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] 邱保志,賀艷芳,申向東.熵加權多視角核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。

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

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

1001- 9081(2017)12- 3482- 05

10.11772/j.issn.1001- 9081.2017.12.3482

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

TP391.4

A