基于局部密度的高效聚類算法研究

周　杰，劉立波，卜旭松

(寧夏大學(xué) 數(shù)學(xué)計算機學(xué)院，寧夏 銀川 750021)

基于局部密度的高效聚類算法研究

周杰，劉立波，卜旭松

(寧夏大學(xué) 數(shù)學(xué)計算機學(xué)院，寧夏 銀川 750021)

摘要：針對基于密度聚類算法對參數(shù)值過于敏感、參數(shù)值難以設(shè)置的不足，提出一種基于局部密度的高效聚類算法，以有效解決基于密度聚類算法對密度層級不同數(shù)據(jù)集聚類準確率低的問題。該算法將局部密度概念和k-means算法相結(jié)合，在算法迭代過程中動態(tài)計算局部密度參數(shù)和簇核心距。對于分布在簇核心距之內(nèi)的數(shù)據(jù)，采用基于劃分的方法直接聚類；對于分布在簇核心距之外的數(shù)據(jù)采用基于局部密度方法進行聚類。實驗結(jié)果表明，提出的算法在聚類精度和計算效率兩方面均具有較好的性能。

關(guān)鍵詞：k-means；局部密度；簇核心距；聚類

中圖分類號：TP391

文獻標志碼：碼：A

文章編號：號：2095-4824(2015)06-0021-05

收稿日期：2015-09-11

作者簡介：周杰(1990-)，女，寧夏銀川人，寧夏大學(xué)數(shù)學(xué)計算機學(xué)院碩士研究生。

Abstract：In view of the limitation of density-based clustering algorithm that is sensitive to parameter settings and difficult to set the parameters, this paper proposes an efficient local density-based clustering algorithm for the problem that the density-based clustering algorithm is not accurate to the data set with different density-levels. The proposed algorithm combines the local density concepts and K-means algorithms and dynamically calculates the local-density parameters and core-distance of the clusters in the process of the iteration. The data inside the core-distance is clustered into the clusters directly by the partition-based method and the data outside the core distance of the clusters is clustered by the local density method. Experimental results indicate that the proposed method exhibits better performance in both efficiency and accuracy.

聚類[1-2]作為一種有效的數(shù)據(jù)挖掘工具已經(jīng)成功應(yīng)用于許多領(lǐng)域，如網(wǎng)絡(luò)安全[3]、生物學(xué)、商務(wù)智能和Web搜索等多個方面。聚類是把一個數(shù)據(jù)集劃分成多個組或簇的過程，使得簇內(nèi)高度相似，而簇間相異。若待分類數(shù)據(jù)集中不含噪聲數(shù)據(jù)，采用基于劃分的聚類算法具有較好的聚類效果，但當數(shù)據(jù)集中存在較多噪聲數(shù)據(jù)時，基于劃分的聚類算法聚類質(zhì)量較低[4-5]。盡管基于密度的聚類算法能通過設(shè)置全局閾值方式消除噪聲數(shù)據(jù)對聚類準確率的影響[6-8]，但全局密度閾值不能很好地刻畫數(shù)據(jù)集的內(nèi)在聚類結(jié)構(gòu)，當數(shù)據(jù)集中簇的密度層級相差較大時，全局密度閾值選擇非常困難，使得聚類質(zhì)量難以保證。較大的密度閾值能較好地過濾噪聲，但容易導(dǎo)致稠密度較小簇中的大量數(shù)據(jù)被標記為噪聲，而較小的密度閾值又會降低算法噪聲過濾能力，導(dǎo)致簇中含有較多噪聲數(shù)據(jù)[9]。針對上述問題，本文提出一種基于局部密度聚類的新算法，該算法能有效地解決基于密度聚類算法參數(shù)設(shè)置難、聚類結(jié)果對參數(shù)敏感問題，在發(fā)現(xiàn)不同密度層級簇方面具有更高的聚類準確率和執(zhí)行效率。

1相關(guān)算法

1.1k-means聚類算法

k-means算法[10-12]首先隨機選取k個對象作為算法的初始聚類中心，然后按照某種距離度量公式計算每個對象到各簇聚類中心的距離，將對象劃分到離其最近的簇中。重新計算各簇均值，用計算后的簇均值作為新簇聚類中心，重新劃分所有對象。迭代繼續(xù)，直到劃分結(jié)果穩(wěn)定，即本次迭代形成的簇與前次迭代形成的簇高度相似。在算法每次迭代過程中，待聚類數(shù)據(jù)對象只需與k個聚類中心進行比較即可被分配到最相似的簇中，因而算法執(zhí)行速度快。k-means算法時間復(fù)雜度為O(nkt)，其中n表示樣本的總個數(shù)，t表示迭代次數(shù)。采用k-means算法能夠?qū)崿F(xiàn)快速聚類，算法具體過程如下：

Step1：從待聚類的數(shù)據(jù)集N中隨機選取k個對象{m1,m2,m3,…,mk}作為各簇的初始聚類中心；

Step2：repeat；

Step3：對于數(shù)據(jù)集N中每個對象xi，按照某種距離度量公式計算xi到各聚類中心的距離，將

劉立波(1974-)，女，寧夏銀川人，寧夏大學(xué)數(shù)學(xué)計算機學(xué)院，博士，教授。

卜旭松(1988-)，男，山東煙臺人，寧夏大學(xué)數(shù)學(xué)計算機學(xué)院碩士研究生。

xi劃分到離其最近的簇中；

Step5：until聚類中心不發(fā)生變化。

圖1　example數(shù)據(jù)集

圖1是example數(shù)據(jù)集中數(shù)據(jù)的分布情況，數(shù)據(jù)集包含簇A和簇B兩個密度層級相差較大的簇，n1、n2和n3是噪聲數(shù)據(jù)。

圖2　ε=0.2，Minpts=2聚類效果

圖3　ε=0.2，Minpts=4聚類效果

圖2是DBSCAN算法在ε=0.2，Minpts=2時的聚類結(jié)果，如圖可知算法能準確識別簇B，由于各簇的鄰域密度值Minpts均為2，使得局部噪聲數(shù)據(jù)n1、n2等被劃分到簇A中，導(dǎo)致簇A聚類不準確。圖3是DBSCAN算法在ε=0.2，Minpts=4時的聚類結(jié)果，可看出算法能夠較準確的識別簇A，由于各簇鄰域密度值Minpts均為4，簇B被誤標記成噪聲數(shù)據(jù)。

2基于局部密度的聚類算法

k-means算法本身并無過濾噪聲和基于局部密度聚類的能力[13-14]。本文將簇稠密度、簇相對稠密度、簇核心距概念和局部密度閾值方法引入到k-means算法中，使算法不僅能夠過濾噪聲，而且具有基于局部密度聚類方法的優(yōu)點。提出的聚類算法需要用戶設(shè)定3個參數(shù)：鄰域密度值、ε-鄰域值和聚類個數(shù)k。在算法初次迭代過程中獲取簇核心距、簇稠密度和簇相對稠密度等簇屬性，并通過這些屬性計算簇局部密度閾值,進而將用戶設(shè)置的全局密度閾值轉(zhuǎn)化為符合各簇密度層級的局部密度閾值。算法在后續(xù)迭代過程中通過如下方式過濾噪聲進行聚類：

對于待聚類對象xi，若xi離簇Ci距離最近且xi是Ci的核心對象，則直接把xi劃分到簇Ci；若xi不是Ci的核心對象，則查找xi的ε-鄰域內(nèi)是否包含RMinpts個對象。若包含RMinpts個對象，則將xi劃分到簇Ci，否則將xi標記為噪聲。算法每次迭代結(jié)束后，重新計算簇Ci的新聚類中心、簇稠密度和相對稠密度，更新簇局部密度閾值。算法繼續(xù)迭代，直到各簇不再發(fā)生變化。以下是本文涉及到的概念、局部密度閾值計算方法和算法具體描述。

2.1相關(guān)概念

2.1.1歐氏距離

設(shè)xi=(xi1,xi2,xi3,…,xip)和xj=(xj1,xj2,xj3,…,xjp)是兩個包含p個數(shù)值屬性描述的對象。對象xi和xj之間的歐氏距離定義為：

(1)

2.1.2簇核心距

設(shè)簇Ci中對象到簇心的歐式距離期望為μi，標準差σi，簇Ci的簇核心距定義為： R(Ci)=μi，若對象xi到簇Ci的歐式距離d(xi,oi)≤R(Ci),則稱xi為簇Ci的核心對象。

2.1.3ε-鄰域

設(shè)xi為數(shù)據(jù)集N中的對象，xi的ε-鄰域是以xi為中心，以ε為半徑的空間。

2.1.4鄰域密度

對象xi的ε-鄰域內(nèi)包含其他對象的數(shù)量。

2.1.5簇稠密度

設(shè)Ni是簇Ci當前對象總個數(shù)，簇Ci的簇稠密度定義為：

den(Ci)= Ni∕(μi+2σi)，i=1,2,…,k(2)

2.1.6相對稠密度

設(shè)簇Ci的稠密度denmax(Ci)=max{den(Ci)}，簇相對稠密度定義如下：

(3)

2.2局部密度閾值計算方法

按照2.1中簇稠密度的定義，首先計算各簇稠密度，再根據(jù)簇稠密度計算簇相對稠密度，以簇相對稠密度和用戶設(shè)定的鄰域密度參數(shù)的乘積作為簇的局部密度閾值，定義為RMinpts=「Minpst×rden(Ci)?。局部密度閾值RMinpts以簇相對密度作為權(quán)重計算得出，因而能夠較真實地反映各簇密度層級。

2.3算法描述

輸入：

k：預(yù)期分簇數(shù)量。

D：包含n個對象的待聚類數(shù)據(jù)集。

ε：半徑參數(shù)。

Minpts：鄰域密度閾值。

輸出：

基于局部密度的k個簇的集合。

步驟：

Step1：從待聚類的數(shù)據(jù)集N中隨機選取k個對象{m1,m2,m3,…,mk}作為各簇初始聚類中心；

Step2：repeat；

Step3：if (第一次迭代){對于數(shù)據(jù)集N中的每個對象xi，按照歐式距離度量公式計算xi到各聚類中心距離，將xi劃分到離它最近的簇中；}

else {對于數(shù)據(jù)集N中的每個對象xi，按照歐氏距離計算xi到各聚類中心距離，找出離xi最近的簇Ci。

if (dist(xi,oi)≤R(Ci)){直接將xi劃分到簇Ci}

else if (dist(xi,oi)>R(Ci) andxi的ε-鄰域包含對象數(shù)不小于RMinpts){將xi劃分到簇Ci}

else { 將xi標記為噪聲}

}

Step4：重新計算簇Ci的新聚類中心；計算簇Ci中對象xi到簇聚類中心oi的歐式距離期望μi和標準差σi；

Step5：until不發(fā)生變化。

3實驗與分析

通過和DBSCAN算法、文獻[6]中提出的IDBSCAN算法對比，驗證算法的執(zhí)行效率。以上三種算法均由JAVA語言編程實現(xiàn)。

3.1聚類準確率分析

實驗測試數(shù)據(jù)如圖4，數(shù)據(jù)集共包含3個簇A、B、C和噪聲數(shù)據(jù)，其中簇A和簇B的密度較大，C的密度較小。實驗中本文算法和DBSCAN算法ε-鄰域值均為0.4。

圖4　帶噪聲的數(shù)據(jù)集

圖5是DBSCAN算法在Minpts=10時的聚類效果，圖6是DBSCAN算法在Minpts=6時的聚類效果，圖7為本算法在Minpts=10時的聚類效果。

圖5　DBSCAN算法Minpts=10聚類效果

圖6　DBSCAN算法Minpts=6聚類效果

從圖5可看出，當DBSCAN算法的ε-鄰域參數(shù)設(shè)為0.4，鄰域密度參數(shù)設(shè)為10時，算法能夠過濾噪聲數(shù)據(jù)，較準確地對簇A和簇B進行聚類，由于簇C的密度相對較小，因此簇C的部分數(shù)據(jù)被當作噪聲數(shù)據(jù)過濾掉。從圖6可看，出當DBSCAN算法的ε-鄰域參數(shù)設(shè)為0.4，鄰域密度參數(shù)設(shè)為6時，由于鄰域密度參數(shù)閾值相對較小，簇C能夠被較準確地識別，簇A和簇B周圍的一些噪聲數(shù)據(jù)被劃歸到這兩個簇中，導(dǎo)致簇A和簇B聚類不準確。

圖7　本算法Minpts=10聚類效果圖

對比圖5和圖6，不難發(fā)現(xiàn)DBSCAN算法對此類數(shù)據(jù)聚類的缺點。從圖7可以看出，當本算法ε-鄰域參數(shù)設(shè)為0.4，鄰域密度參數(shù)設(shè)為10時，第一次迭代過程中算法計算得到簇A的局部密度閾值RMinptsA=10，簇B的局部密度參數(shù)RMinptsB=9，簇C的局部密度參數(shù)為RMinptsC=5。這3個簇鄰域密度參數(shù)能夠較好地反映各簇內(nèi)部結(jié)構(gòu)，聚類過程中算法按照各簇密度閾值過濾噪聲數(shù)據(jù)進行聚類，上述實驗結(jié)果表明本算法聚類效果比DBSCAN算法更準確。

3.2算法執(zhí)行效率分析

算法執(zhí)行效率驗證的實驗硬件環(huán)境為Intel(R) Core(TM) i3-3110M CPU @ 2.4 GHz，內(nèi)存4 GB。實驗選取5個數(shù)據(jù)集，每個數(shù)據(jù)集包含兩個簇和噪聲數(shù)據(jù)，數(shù)據(jù)集具體信息如表1所示，本文算法、DBSCAN算法和文獻[6]中的IDBSCAN算法的執(zhí)行效率如圖8所示。

表1　數(shù)據(jù)集信息

圖8　算法執(zhí)行效率對比

從圖8可以看出，由于DBSCAN算法對于每個點都要驗證其是否達到鄰域密度規(guī)定的Minpts個點，算法時間開銷較大；IDBSCAN算法避免了鄰域內(nèi)重疊對象的檢測，效率有所提升；本文算法只對到簇心距離大于簇核心距的對象進行驗證是否滿足最小鄰域密度要求，所需對象驗證數(shù)量少，因而算法耗時少，具有比DBSCAN算法和IDBSCAN算法更高的執(zhí)行效率。

4結(jié)語

針對基于密度聚類算法對簇密度層級相差較大的數(shù)據(jù)集聚類不準確問題，本文將局部密度閾值方法和k-means算法相結(jié)合，提出了基于局部密度聚類算法。該算法用局部閾值取代全局閾值進行聚類，更準確地反映數(shù)據(jù)集內(nèi)各簇的密度結(jié)構(gòu)。與傳統(tǒng)的基于密度的聚類算法相比，本文算法具有更高的聚類準確率和算法執(zhí)行效率。然而，提出的算法在發(fā)掘任意形狀簇方面仍存在不足，如何提高它在發(fā)掘任意形狀簇方面的能力，是本課題組今后的研究方向。

[參考文獻]

[1]公茂果，王 爽，馬 萌，等.復(fù)雜分布數(shù)據(jù)的二階段聚類算法[J].軟件學(xué)報, 2011,22(11):2760-2772.

[2]孫吉貴,劉杰,趙連宇.聚類算法研究[J].軟件學(xué)報,2008,19(1):48-61.

[3]丁彥，李永忠.基于PCA和半監(jiān)督聚類的入侵檢測算法研究[J].山東大學(xué)學(xué)報：工學(xué)版,2012，42(5):41-46.

[4]郝洪星，朱玉全，陳耿.基于劃分和層次的混合動態(tài)聚類算法[J].計算機應(yīng)用研究,2011,28(1):51-54.

[5]Parsons L,Haque E,Liu H.Subspace clustering for high dimensional data:a review[J].SIGKDD Explorations,2004,6(1):90-105.

[6]畢方明，王為奎，陳龍. 基于空間密度的群以噪聲發(fā)現(xiàn)聚類算法研究[J].南京大學(xué)學(xué)報：自然科學(xué)版，2012,48(4):491-498.

[7]許虎寅,王治和.一種改進的基于密度的聚類算法[J]. 微電子學(xué)與計算機,2012,29(2):44-47.

[8]黃德才,吳天虹.基于密度的混合屬性數(shù)據(jù)流聚類算法[J].控制與決策，2010,25(3):416-421.

[9]王晶,夏魯寧,荊繼武.一種基于密度最大值的聚類算法[J].中國科學(xué)院研究生院學(xué)報,2009,26(4):539-548.

[10]Redmond S J, Heneghan C.A method for initialising the k-means clustering algorithm using Kd-trees[J]. Pattern Recognition Letters,2007,28(8):965-973

[11]Cao F, Liang J, Jiang G.An initialization method for the k-means algorithm using neighborhood model[J].Computers and Mathematics with Applications,2009,58(3):474-483.

[12]楊福萍,王洪國,董樹霞,等.基于聚類劃分的兩階段離群點檢測算法[J].計算機應(yīng)用研究,2013,30(7):1942-1945.

[13]Miyahara S, Komazaki Y,Miyamoto S.An algorithm combining spectral clustering and DBSCAN for core points[J].Knowledge and Systems Engineering,2014,245(2):21-28.

[14]Tran T N, Klaudia D,Daszykowski M.Revised DBSCAN algorithm to cluster data with dense adjacent clusters[J]. Chemometrics and Intelligent Laboratory Systems,2013,120(2):92-96.

Research on Efficient Clustering Algorithm Based on Local Density

Zhou Jie，Liu Libo，Bu Xusong

(SchoolofMathematicsandComputerScience，NingxiaUniversity，Yinchuan，Ningxia750021，China)

Key Words：k-means; local density; core-distance; clustering

(責(zé)任編輯：張凱兵)