關(guān)曉惠，錢亞冠，孫欣欣

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

一種改進(jìn)的基于局部密度的聚類算法

關(guān)曉惠1，錢亞冠2，孫欣欣1

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

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

局部密度;類簇中心;評價指標(biāo)

1 引言

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

迄今為止，國內(nèi)外研究人員相繼提出很多聚類算法，主要分為基于層次的聚類、基于劃分的聚類、基于密度的聚類、基于網(wǎng)格的聚類、基于模型的聚類等［1］。基于層次的聚類是指對樣本集合進(jìn)行合并或者分裂，直到滿足某一個終止條件，代 表算法有 BIRCH 算法、CURE 算法［2，3］。優(yōu) 點(diǎn) 是 能得到不同粒度的聚類結(jié)構(gòu)，缺點(diǎn)是很難確定合并和分裂的準(zhǔn)則?；趧澐值木垲愂侵甘紫葘⑺袛?shù)據(jù)粗略地劃分為K個類，然后通過迭代算法使某個準(zhǔn)則達(dá)到最優(yōu)來對劃分進(jìn)行修正。代表算法有k-means算法、k中心點(diǎn)方法及其改進(jìn)［4-7］。優(yōu)點(diǎn)是算法簡單、速度快，缺點(diǎn)是K值需要事先指定，而且只能發(fā)現(xiàn)圓形類簇。基于密度的聚類算法是指根據(jù)數(shù)據(jù)對象的分布密度，將密度足夠大的數(shù)據(jù)對象聚類在一起，樣本空間被低密度區(qū)間劃分開，代表算法有DBSCAN 算法、OPTICS 算法、DENCLUE 算法［7-9］。優(yōu)點(diǎn)是可以發(fā)現(xiàn)任意形狀的類簇，缺點(diǎn)是參數(shù)的設(shè)置對聚類結(jié)果影響較大?；诰W(wǎng)格的聚類是指將數(shù)據(jù)空間量化為有限單元，構(gòu)成一個可以聚類的網(wǎng)格結(jié)構(gòu)，代表算法有STING算法、CLIQUE 算法［10，11］。優(yōu)點(diǎn)是運(yùn)算速度快，缺 點(diǎn)是存在量 化尺度問題?；谀Ｐ偷木垲愂侵笇ふ医o定數(shù)據(jù)與某種數(shù)據(jù)模型的最佳擬合，代表方法有COBWEB算法、AutoClass算法、SOM 算 法［12-14］。

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

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

2 聚類過程

2.1 算法思想

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

(1)局部密度 ρi

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

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

表示所有局部密度大于xi的點(diǎn)中，與xi距離最近的點(diǎn)xj與xi之間的距離。對于密度最大的點(diǎn)表示與xi距離最大的數(shù)據(jù)點(diǎn)與xi之間的距離。

2.2 確定類簇中心

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

算法1DCC(determing-clustering-center)

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

輸出:類簇中心點(diǎn)｛xm1，xm2，…，xmK｝。

對 ｛γ1，γ2，… ，γN｝從 大 到 小 進(jìn) 行 排 序 ，得 到 降 序 下 標(biāo) 序｛q1，q2，…，qN｝;

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

任意候選類簇中心xqi，xqj

if(在dc鄰域內(nèi)如果存在一條直接密度可達(dá)數(shù)據(jù)點(diǎn)鏈｛p1，p2，…，pi｝，滿足 xqi=p1，xqj=pi)

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

2.3 聚類

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

算法2LDC(local-density-clustering)

輸 入 :X=｛x1，x2，… ，xN｝是 需 要 聚 類 的 數(shù) 據(jù) 點(diǎn) ;N 是 數(shù) 據(jù)點(diǎn)個數(shù)。

輸出:每個數(shù)據(jù)點(diǎn)的類別 C=｛c1，c2，…，cN｝。

3 評價指標(biāo)

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

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

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

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

(3)F-measure:由準(zhǔn)確率和召回率兩個指標(biāo)組合而成。

4 實(shí)驗與結(jié)果分析

4.1 實(shí)驗數(shù)據(jù)

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

4.2 類簇中心選擇

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

4.3 dc對算法結(jié)果的影響

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

從圖2中可以看出，不同數(shù)據(jù)集下，dc對聚類結(jié)果的影響是不一樣的。Iris和Wine數(shù)據(jù)集都有最優(yōu)的dc。對于Iris數(shù)據(jù)集，當(dāng)t＞2%時，只能聚出2類，當(dāng)t＜1%時，雖然能聚出3類，但聚類的準(zhǔn)確率在降低。Leuk72-3k和Glass數(shù)據(jù)集的聚類結(jié)果基本不受dc的影響。通過分析發(fā)現(xiàn)，Leuk72-3k數(shù)據(jù)集的類內(nèi)樣本點(diǎn)的距離遠(yuǎn)小于類間的距離。因此在不同的應(yīng)用背景下，應(yīng)該根據(jù)具體的問題選擇合適的dc參數(shù)。

4.4 聚類結(jié)果對比

為了驗證算法的有效性，將本文中算法與經(jīng)典的K-means算法和DBSCAN算法進(jìn)行實(shí)驗對比，并用purity、R指數(shù)、F-measure來衡量算法的優(yōu)劣性。表1為幾種聚類算法在不同數(shù)據(jù)集上的實(shí)驗結(jié)果比較。

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

圖1 聚類中心選擇

圖2 不同數(shù)據(jù)集下dc對聚類結(jié)果的影響

表1 不同聚類算法實(shí)驗結(jié)果比較

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

5 結(jié)束語

圖3 不同數(shù)據(jù)集下類簇個數(shù)與各聚類指標(biāo)的關(guān)系

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

［1］周濤，陸惠玲 .數(shù)據(jù)挖掘中聚類算法研究進(jìn)展 ［J］.計算機(jī)工程與應(yīng)用，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］.軟件學(xué)報，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］.自動化學(xué)報，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］陳黎飛，郭躬德，姜青山.自適應(yīng)的軟子空間聚類算法［J］.軟件學(xué)報，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

關(guān)曉惠(1977-)，女，浙江水利水電學(xué)院副教授，主要研究方向為機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘。

錢亞冠(1976-)，男，博士，浙江科技學(xué)院理學(xué)院副教授，主要研究方向為互聯(lián)網(wǎng)流量分類、下一代互聯(lián)網(wǎng)、機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘。

孫欣欣(1973-)，女，浙江水利水電學(xué)院副教授，主要研究方向為計算機(jī)網(wǎng)絡(luò)。