一種改進的基于局部密度的聚類算法

關曉惠，錢亞冠，孫欣欣

(1.浙江水利水電學院，浙江 杭州 310018;2.浙江科技學院理學院，浙江 杭州 310023)

一種改進的基于局部密度的聚類算法

關曉惠1，錢亞冠2，孫欣欣1

(1.浙江水利水電學院，浙江 杭州 310018;2.浙江科技學院理學院，浙江 杭州 310023)

聚類分析一直是機器學習和數據挖掘領域一個比較活躍而且極具挑戰性的研究方向。Alex提出的基于局部密度的聚類算法是一種快速、有效的聚類方法，但該方法通過手工選取確定聚類個數和聚類中心。為此，對原算法進行改進，在初步選取候選聚類中心的基礎上，使用基于密度連通的算法優化選取聚類中心，然后使用大密度最近鄰方法確定樣本類別。實驗證明，該方法能有效解決聚類個數和聚類中心無法確定的問題，同時在聚類評價指標上顯示出較好的聚類效果和性能。

局部密度;類簇中心;評價指標

1 引言

聚類是指在沒有任何先驗知識的情況下，根據數據特征的相似性將同類數據聚集在一起的過程，屬于無監督分類的范疇。聚類的目標是使得同一類簇內對象的相似性盡可能大，不同類簇之間對象的相似性盡可能小。聚類作為一種重要的數據分析和挖掘手段，已被廣泛應用于語音識別、字符識別、圖像處理、信息安全、金融等領域。

迄今為止，國內外研究人員相繼提出很多聚類算法，主要分為基于層次的聚類、基于劃分的聚類、基于密度的聚類、基于網格的聚類、基于模型的聚類等［1］。基于層次的聚類是指對樣本集合進行合并或者分裂，直到滿足某一個終止條件，代 表算法有 BIRCH 算法、CURE 算法［2，3］。優 點 是 能得到不同粒度的聚類結構，缺點是很難確定合并和分裂的準則。基于劃分的聚類是指首先將所有數據粗略地劃分為K個類，然后通過迭代算法使某個準則達到最優來對劃分進行修正。代表算法有k-means算法、k中心點方法及其改進［4-7］。優點是算法簡單、速度快，缺點是K值需要事先指定，而且只能發現圓形類簇。基于密度的聚類算法是指根據數據對象的分布密度，將密度足夠大的數據對象聚類在一起，樣本空間被低密度區間劃分開，代表算法有DBSCAN 算法、OPTICS 算法、DENCLUE 算法［7-9］。優點是可以發現任意形狀的類簇，缺點是參數的設置對聚類結果影響較大。基于網格的聚類是指將數據空間量化為有限單元，構成一個可以聚類的網格結構，代表算法有STING算法、CLIQUE 算法［10，11］。優點是運算速度快，缺 點是存在量 化尺度問題。基于模型的聚類是指尋找給定數據與某種數據模型的最佳擬合，代表方法有COBWEB算法、AutoClass算法、SOM 算 法［12-14］。

近年來隨著人工智能、機器學習、模式識別、數據挖掘等領域的不斷發展，又提出了許多新的聚類算法。為了解決樣本點不僅僅只屬于某一個類的問題，提出了模糊聚類［15-17］，用模糊理論的方法對數據進行軟劃分。譜聚類是一種基于圖論的聚類方法［18］，通過計算數據之間相似矩陣的特征值和特征向量進行聚類。子空間聚類是針對高維數據空間出現的一種有效聚類方法［19］，通過特征選擇在不同的子空間上進行聚類。然而，在很多聚類方法中都需要提供聚類個數作為參數，目前還沒有一個很好的辦法可以保證獲得準確的聚類數目，這一直是聚類分析中的一個難點［20］。Frey提出一種利用親密度傳播進行聚類的方法［21］。該方法無需事先指定聚類數目，能夠快速、有效地處理大規模數據集，但對于比較松散的聚類結構就會得到較多的聚類數目。

2014年Alex Rodriguez和Alessandro Laio在Science上提出一種簡潔的聚類算法［22］。與以往的聚類算法相比，該方法能夠處理任意形狀的類簇，而且對數據變換有很好的頑健性。但該方法中聚類個數和聚類中心無法自動確定，需要手工選取，這無疑限制了算法的應用范圍和領域。本文提出的基于局部密度的聚類算法，是對該算法的一種改進。在初步選取候選聚類中心的基礎上，增加一個優化選取聚類中心的過程，使用基于密度連通的算法合并或剔除不正確的聚類中心，使用大密度最近鄰方法確定樣本類別。實驗證明，該方法具有較好的聚類效果和性能，有效解決了聚類個數不確定的問題。

2 聚類過程

2.1 算法思想

本文算法的核心思想是基于局部密度的概念，它表示與該點的距離在一定范圍的點的個數，也就是說一個點附近點的個數越多，其局部密度越大。該算法認為聚類中心是由一些局部密度比較低的點圍繞，并且這些點距離其他高局部密度的點的距離都比較大。為此定義兩個量。

(1)局部密度 ρi

其中，dc＞0為截斷距離，需要用戶確定。推薦做法是選擇dc，使得每個點的平均鄰居數為總點數的1%～2%(假設為t)。為了將聚類算法擴展到異形類簇，本文使用高斯核函數來定義局部密度，既避免了不同的點具有相同局部密度的問題，又能識別異形類簇。

(2)到較高局部密度點的最近距離δi

表示所有局部密度大于xi的點中，與xi距離最近的點xj與xi之間的距離。對于密度最大的點表示與xi距離最大的數據點與xi之間的距離。

2.2 確定類簇中心

類簇中心是指局部密度比較大，且距離其他較大局部密度的點的距離比較遠的點。首先計算所有點的ρi和δi，以ρ為橫坐標，以δ為縱坐標形成決策圖，選擇ρi和 δi都比較大的點作為類簇的中心。為了定量確定類簇的中心點，定義 γi=ρiδi，然后對｛γi｜i=1，…，N｝進行降序排序，選擇 γi大于某個閾值λ的點為中心點。此時可能會存在兩種特殊情況:第一種情況是一些ρ很大但δ值很小的點會被選為中心點，這樣可能會造成同一個類簇中有兩個中心點存在，將本來屬于同一個類簇的數據點分成兩個不同的類簇;第二種情況是ρ很小，但δ很大，這樣會把部分異常點視為聚類的中心，本文的做法是對ρ和δ都設置各自的閾值，將大于閾值的點視為候選中心點。然后使用基于密度的連通性算法將候選中心點合并或剔除，具體算法如下。

算法1DCC(determing-clustering-center)

輸入:X=｛x1，x2，…，xN｝是需要聚類的數據點;N 是數 據點個數;｛ρ1，ρ2，…，ρN｝為每個數據的局部密度;｛δ1，δ2，…，δN｝為每個樣本點到高局部密度的最小距離。

輸出:類簇中心點｛xm1，xm2，…，xmK｝。

對 ｛γ1，γ2，… ，γN｝從 大 到 小 進 行 排 序 ，得 到 降 序 下 標 序｛q1，q2，…，qN｝;

選取 γi＞ε并且 ρi＞σ 的點為候選類簇中心點｛xq1，xq2，…，xqW｝;

任意候選類簇中心xqi，xqj

if(在dc鄰域內如果存在一條直接密度可達數據點鏈｛p1，p2，…，pi｝，滿足 xqi=p1，xqj=pi)

xqi，xqj屬于同一個類簇，并選擇ρ值比較大的點為合并后的類簇中心;

2.3 聚類

類簇中心確定以后，需要確定每個點劃分給某個類簇的可靠性。本文使用大密度最近鄰方法將每個點歸類到局部密度比自己大的最近鄰的簇。聚類算法如下。

算法2LDC(local-density-clustering)

輸 入 :X=｛x1，x2，… ，xN｝是 需 要 聚 類 的 數 據 點 ;N 是 數 據點個數。

輸出:每個數據點的類別 C=｛c1，c2，…，cN｝。

3 評價指標

評價一個聚類算法的好壞一般基于這樣的原則:簇中的成員盡可能地互相靠近，簇與簇之間的距離盡可能遠。假 設 P=｛P1，P2，… ，PS｝為 人 工 標 注 的 分 類 結 果 ，C=｛C1，C2，…，Cm｝為聚類算法的劃分。本文采用以下評價指標。

(1)purity:正確聚類的樣本數占總樣本數的比例

(2)R指數:表示C和P之間的相似程度

假設a表示兩個點在C和P中均屬于同一個簇的個數;b表示兩個點在C中屬于相同的簇，在P中屬于不同簇的個數;c表示兩個點在C中屬于不同的簇，在P中屬于相同簇的個數;d表示兩個點在C、P中均屬于不同簇的個數。R值越大說明C和P的吻合度越高，說明C的聚類效果越好。

(3)F-measure:由準確率和召回率兩個指標組合而成。

4 實驗與結果分析

4.1 實驗數據

UCI數據庫是一個專門用于測試分類、聚類算法的國際通用標準測試數據庫，包含Wine、Iris、Glass等數據集。其中Iris數據集包含3類，每一類代表一種類型的鳶尾花，每類有50個數據，共150個樣本，在3個類簇中分布均勻，其中一類與另外兩類線性可分，另外兩類有部分重疊。Wine數據集包含178個樣本，13個數值型屬性，共分成3類，每類中樣本數量不同。Glass數據集共有69個樣本，包含3類，每類占總數據量的1/3。另外，Leuk72-3k也是比較常用的聚類測試數據集。

4.2 類簇中心選擇

算法首先根據局部密度和到高密度樣本的距離來確定類簇中心，然后計算其他非中心樣本與類簇中心的距離，從而決定樣本歸屬。因此，算法中類簇中心點的選擇不但決定著聚類的個數，還影響其他樣本的類別歸屬。圖1(a)為Iris數據樣本經過多維尺度變換后樣本的分布情況，圖1(b)為｛γi｜i=1，…，N｝從大到小排序后的結果。如果選擇 γi最大的2個樣本作為類簇中心，則整個數據被分成2個類簇，如果選擇γi值最大的前5個樣本作為類簇中心，則樣本被分成5個類簇。為了更合理地確定類簇中心，首先給γi設置一個相對較小的閾值(本實驗的閾值為6)，使較多的樣本點成為候選類簇中心，然后使用算法1對候選類簇中心進行合并，得到最優的類簇中心，圖1(c)中菱形的點為候選類簇中心。圖1(d)中菱形的點為合并后的類簇中心，樣本的不同形狀標示根據最優類簇中心聚類后的結果。

4.3 dc對算法結果的影響

dc的選擇決定局部密度的大小，如果取得太大，ρi的區分度不大，類簇中心不準確，如果取得太小，類簇中心的個數過多，會導致同一類簇的數據被劃分為不同的類簇。為了證明dc的大小對實驗結果的影響，本文針對不同的數據集，分別采用不同大小的dc做實驗，得出的實驗結果如圖2所示(t為dc的值使得每個點的平均鄰居數占所有點的比例)。

從圖2中可以看出，不同數據集下，dc對聚類結果的影響是不一樣的。Iris和Wine數據集都有最優的dc。對于Iris數據集，當t＞2%時，只能聚出2類，當t＜1%時，雖然能聚出3類，但聚類的準確率在降低。Leuk72-3k和Glass數據集的聚類結果基本不受dc的影響。通過分析發現，Leuk72-3k數據集的類內樣本點的距離遠小于類間的距離。因此在不同的應用背景下，應該根據具體的問題選擇合適的dc參數。

4.4 聚類結果對比

為了驗證算法的有效性，將本文中算法與經典的K-means算法和DBSCAN算法進行實驗對比，并用purity、R指數、F-measure來衡量算法的優劣性。表1為幾種聚類算法在不同數據集上的實驗結果比較。

從表1可以看出，本文算法相對于K-means、DBSCAN算法在各指標上均有較大的提升，說明該算法有較好的聚類效果和性能。

圖1 聚類中心選擇

圖2 不同數據集下dc對聚類結果的影響

表1 不同聚類算法實驗結果比較

Alex提出的算法中，聚類個數以及類簇中心都通過人工方式選定，為了確定最優的聚簇類數，本文采用最優評價指標方法來確定聚類個數。在給定的數據集上，通過選擇不同的類簇中心個數，對數據集進行不同的劃分，并計算不同劃分的評價指標，如圖3所示。選擇評價指標最好的聚類個數為最佳聚類個數。從圖3中可以看出，4k2-far數據集的最優類簇個數為4，Iris數據集的最優類簇個數為3。

5 結束語

圖3 不同數據集下類簇個數與各聚類指標的關系

針對基于局部密度的聚類算法無法自動選擇類簇個數和類簇中心的問題，本文在該算法的基礎上增加了一個優化選取聚類中心的過程，使用基于密度連通的算法合并或剔除不正確的聚類中心。與其他聚類算法相比，該方法具有較好的聚類效果和性能，并有效地解決了聚類個數不確定的問題。本文還驗證了不同的截斷距離對聚類結果的影響，實驗證明在實際應用中應該根據具體的聚類問題選擇合適的參數。

［1］周濤，陸惠玲 .數據挖掘中聚類算法研究進展 ［J］.計算機工程與應用，2012，48(12):100-109.ZHOU T，LU H L.Clustering algorithm research advances on data mining ［J］.Computer Engineering and Applications，2012，48(12):100-109.

［2］ZHANGT，RAMAKRISHNANR，LIVNYM.BIRCH:an efficient data clustering method for very large databases ［C］//Proceedings of 1996 ACM-SIGMOD International Conference ManagementofData，June4-6，1996，Montreal，Quebec，Canada.New York:ACM Press，1996:103-114.

［3］GUHA S，RASTOGI R，SHIM K.CURE:an efficient clustering algorithm for large database［J］.Information Systems，2001，26(1):35-58.

［4］MACQUEEN J.Some methods for classification and analysis of multivariate observations ［C］//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability，June 21-18，1965，Berkeley，California，USA.California:University of California Press，1967:281-297.

［5］KAUFMAN L，ROUSSEEUW P J.Finding Groups in Data:An Introduction to Cluster Analysis ［M］.New York:John Wiley&Sons，1990.

［6］HUANG Z.Extensions to the k-means algorithm for clustering large data sets with categorical values ［J］.Data Mining and Knowledge，Discovery II，1998(2):283-304.

［7］倪巍偉，陳耿，吳英杰.一種基于局部密度的分布式聚類挖掘算法［J］.軟件學報，2008，19(9):2339-2348.NI W W，CHEN G，WU Y J.Local density based distributed clustering algorithm ［J］.Journal of Software，2008，19(9):2339-2348.

［8］ANKERST M，BREUNIG M，KRIEGEL H P，et al.OPTICS:ordering points to identify the clustering structure ［C］//Proceedings of 1999 ACM-SIGMOD International Conference Management of Data(SIGMOD'99)，June 1-3，1999，Philadelphia，Pennsylvania，USA.New York:ACM Press，1999:49-60.

［9］HINNEBURG A，KEIM D A.Anefficientapproachto clustering in large multimedia databases with noise ［C］//Proceedings of 1998 International Conference Knowledge Discovery and Data Mining，August 27-31，1998，New York，USA.New York:ACM Press，1998:58-65.

［10］WANG W，YANG J，MUNTZ R.STING:a statistical information grid approach to spatial data mining ［C］//Proceedings of 1997 International Conference Very Large Data Bases，August 2-29，1997，Athens，Greece.New York:ACM Press，1997:186-195.

［11］AGRAWAL R，GEHRKE J，GUNOPULOS D，et al.Automatic subspace clustering of high dimensional data for data mining applications［C］//Proceedings of 1998 ACM-SIGMOD International Conference Management of Data， June 2-4，1998，Seattle，Washington，USA.New York:ACM Press，1998:94-105.

［12］FISHER D.Improving inherence through conceptual clustering［C］//Proceedings of 1987 AAAI Conference，July 13-17，1987， Seattle，Washington，USA.［S.l.］:AAAI Press，1987:461-465.

［13］FAYYAD V M，PIATETSKY S G，SMYTH P，et al.Bayesian Classification (AutoClass):Theory and Result.Advances in Knowledge Discovery and Data Mining［M］.Bridge City:The MIT Press，1996:153-180.

［14］TEUVO K.The self-organizing map ［J］.Neurocomputing，1998，21(13):1-6.

［15］CAI W L，CHEN S C，ZHANG D Q.Fast and robust fuzzy c-means clustering algorithms incorporating local information for image segmentation［J］.Pattern Recognition，2007，40(3):825-833.

［16］BASU B，SRINIVAS V V.Regional flood frequency analysis using kernel-based fuzzy clustering approach ［J］.Water Resources Research，2014，50(4):3295-3316.

［17］LI X，WONG H S，WU S.A fuzzy minimax clustering model and its applications［J］.Information Sciences，2012，186:114-125.

［18］周林，平西建，徐森，等.基于譜聚類的聚類集成算法 ［J］.自動化學報，2012，38(8):1335-1342.ZHOU L，PING X J，XU S，et al.Cluster ensemble based on spectral clustering［J］.Acta Automatica Sinica，2012，38(8):1335-1342.

［19］陳黎飛，郭躬德，姜青山.自適應的軟子空間聚類算法［J］.軟件學報，2010(10):2513-2523.CHEN L F，HUO G D，JIANG Q S.Adaptive algorithm for soft subspace clustering［J］.Journal of Software，2010(10):2513-2523.

［20］SUN H，WANG S，JIANG Q.FCM-based model selection algorithms for determining the number of cluster ［J］.Pattern Recognition，2004，37(10):2027-2037.

［21］FREY B J，DUECK D.Clustering by passing messages between data points［J］.Science，2007，315(5814):972-976.

［22］ALEX R，ALESSANDRO L.Clustering by fast search and find of density peaks［J］.Science，2014，344(6191):1492-1496.

An improved clustering algorithm based on local density

GUAN Xiaohui1，QIAN Yaguan2，SUN Xinxin2
1.College of Information Engineering and Art Design，Zhejiang University of Water Resources and Electric Power，Hangzhou 310018，China 2.College of Science，Zhejiang University of Science and Technology，Hangzhou 310023，China

Clustering analysis is an important and challenging research field in machine learning and data mining.A fast and effective clustering algorithm based on the idea of local density was proposed by Alex.But the number of clusters and cluster centers in the algorithm were determined by hand.Therefore，the candidates of cluster centers based on local density were firstly selected and then density connectivity method was used to optimize the candidates.The classes of samples are the same as the nearest center with bigger local density.Experiments show that the proposed method has a better cluster efficiency and can handle the problems of uncertain cluster number and cluster centers.

local density，cluster center，evaluation criterion

TN929.5

A

10.11959/j.issn.1000-0801.2016008

2015-06-08;

2015-11-02

關曉惠(1977-)，女，浙江水利水電學院副教授，主要研究方向為機器學習與數據挖掘。

錢亞冠(1976-)，男，博士，浙江科技學院理學院副教授，主要研究方向為互聯網流量分類、下一代互聯網、機器學習與數據挖掘。

孫欣欣(1973-)，女，浙江水利水電學院副教授，主要研究方向為計算機網絡。