基于動態(tài)的網(wǎng)格相對密度差聚類算法研究

錢雪忠+韓利釗+羅靖

摘要：現(xiàn)有大多數(shù)多密度聚類算法存在參數(shù)依賴性較高、精確度較低的問題。提出一種基于網(wǎng)格相對密度差的擴展聚類算法（ECRGDD）的改進算法，即基于動態(tài)的網(wǎng)格相對密度差聚類算法（CDGRDD）。CDGRDD針對ECRGDD對于中心密度大、邊緣密度稀疏的類聚類效果差的問題，把初始單元網(wǎng)格密度定義為動態(tài)，在密度相似相鄰的網(wǎng)格合并時加入一個距離判斷條件，由此減少盲目合并的可能性。實驗表明，CDGRDD能有效對多密度、任意形狀的數(shù)據(jù)進行聚類。

關鍵詞：動態(tài)初始單元；多密度聚類；網(wǎng)格相對密度差；模糊函數(shù)

DOIDOI：10.11907/rjdk.171164

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2017）006-0032-05

0 引言

聚類分析是數(shù)據(jù)挖掘的重要研究內(nèi)容之一。聚類是把數(shù)據(jù)分成類或簇的過程，使同一類中的數(shù)據(jù)盡量相似，不同類之間的數(shù)據(jù)盡量相異[1]。傳統(tǒng)聚類算法大致分為劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法，在這5類方法中，學者對基于密度和基于網(wǎng)格的聚類算法進行了大量研究，兩者各有優(yōu)點與不足[2-6]。

目前已有很多經(jīng)典聚類算法，如K-MEANS、CLARANS、DBSCAN、CURE、CLIQUE和SNN等算法[7-11]，以及在這些經(jīng)典算法基礎上改進的算法，如周水庚等[12]提出的基于密度的快速聚類算法 （FDBSCAN）、黃紅偉等[13]提出的基于網(wǎng)格相對密度差的擴展聚類算法 （ECRGDD）、馮振華[14]針對多密度提出的貪婪聚類算法 （GDBSCAN）等。

基于網(wǎng)格的聚類算法將數(shù)據(jù)空間劃分成有限個單元網(wǎng)格，所有處理都在網(wǎng)格單元上進行。這種方法的優(yōu)點是聚類結果與數(shù)據(jù)點的輸入順序無關，算法復雜度僅依賴于空間網(wǎng)格的數(shù)量（遠小于數(shù)據(jù)點總數(shù)），具有較高的運算效率，且能識別任意形狀的簇。但是，現(xiàn)有的基于網(wǎng)格的聚類算法，通常只有在數(shù)據(jù)集分布較為均勻的情況下才能得到較好的聚類效果，對于多密度數(shù)據(jù)集并不能達到令人滿意的聚類結果。

1 擴展聚類算法

1.1 算法簡介

針對基于網(wǎng)格的聚類算法對于多密度數(shù)據(jù)集聚類效果不理想的問題，黃紅偉等提出了基于網(wǎng)格相對密度差的擴展聚類算法（ECRGDD），該算法結合基于密度和基于網(wǎng)格思想的優(yōu)點，采用數(shù)據(jù)空間網(wǎng)格化方法節(jié)省運算時間，根據(jù)網(wǎng)格間的密度關系展開聚類，并給出邊界提取方法，以便提高聚類質(zhì)量。

ECRGDD算法思想簡單表述為：首先根據(jù)統(tǒng)計的網(wǎng)格密度選取密度最大值g0作為初始單元；然后按照廣度優(yōu)先遍歷原則，采用相對密度差公式，逐層計算初始單元g0與其相鄰網(wǎng)格之間的相對密度差。若兩者密度相近，則將相鄰網(wǎng)格單元與初始單元歸為一類，繼續(xù)向外擴展，直到當前聚類的網(wǎng)格密度與初始單元網(wǎng)格密度相差較大，不滿足相對密度差公式時聚類結束；然后在剩余未被聚類的網(wǎng)格單元里找到密度最大者，重復上述步驟，直到剩下的數(shù)據(jù)點集不能再聚類時為止。

1.2 ECRGDD算法存在的問題

由于ECRGDD算法初始單元網(wǎng)格g0一直是本類中密度最大的網(wǎng)格，所以對于中心密、邊緣稀疏的類，如果相對密度差參數(shù)設置較小，類邊緣的網(wǎng)格就不滿足密度差公式。把這種類分成多個類，如果相對密度差參數(shù)設置比較大，噪聲點就會吸收到本類中；另一方面，ECRGDD算法只要滿足相對密度差公式就合并網(wǎng)格，合并存在盲目性。如果兩個類距離較近，不同類中的兩個網(wǎng)格正好是相鄰網(wǎng)格，密度又相近，這兩個類就會合并成一個類。如圖1所示，網(wǎng)格g1與網(wǎng)格g2是相鄰網(wǎng)格，且密度相近；g3與g4相鄰且密度相似，圖中的3個類就合并成一個類。

3.2 實驗結果及分析

本文通過Matlab工具實現(xiàn)CDGRDD算法并處理實驗結果，試驗環(huán)境：CPU為Intel i3 3.7GHz；內(nèi)存為4G；OS為Windows7。通過3個不同類型和規(guī)模的多密度數(shù)據(jù)分別與ECRGDD算法、DBSCAN算法、GDBSCAN算法進行比較。

說明：所有實驗結果中的‘×為噪聲點。

實驗1：數(shù)據(jù)Jain[16]是圖形比較規(guī)則，密度有較大差異的兩個類，共有408個數(shù)據(jù)對象，CDGRDD和ECRGDD中的兩個參數(shù)分別為з=0.53，uλ=0.1；DBSCAN算法中的兩個參數(shù)分別為Eps=2.5，Minpts=10；GDBSCAN算法中Mintps=10；聚類結果如圖3所示。

由上述實驗結果可知，ECRGDD聚類算法由于采用固定的初始單元密度，使得左上部分與右上部分分離，且聚類不精確；DBSCAN算法由于采用全局變量Eps、Mintps，對于多密度聚類，容易顧此失彼，密度高的聚類效果好，密度低的聚類效果差；GDBSCAN聚類算法整體聚類效果較好，但仔細觀察，此算法對個別數(shù)據(jù)存在瑕疵點；CDGRDD聚類成功識別了兩個不同密度的簇，且噪聲點識別較為準確。

實驗2：數(shù)據(jù)Compound[16]圖形比較復雜且具有多個類，共有418個數(shù)據(jù)對象，CDGRDD和ECRGDD中的兩個參數(shù)分別為з=0.55，uλ=0.1；DBSCAN算法中的兩個參數(shù)分別為Eps=1.5，Minpts=10；GDBSCAN算法中Mintps=5。聚類結果如圖4所示。

從圖4（a）可以看出，ECRGDD聚類算法在一個簇結束之前，都用固定的初始網(wǎng)格單元，使得公式（2）中的den（g0）是固定的，因此對于左上角這種中心密邊緣稀疏聚類效果不理想，噪聲偏多；另一方面在聚類過程中網(wǎng)格的合并沒有距離限制，使得左下角環(huán)形類中的一些網(wǎng)格是環(huán)形中心網(wǎng)格的相鄰網(wǎng)格且滿足密度差公式，所以被合并成了一個類，邊界點處理不理想；GDBSCAN算法出于數(shù)據(jù)輸入順序的原因，使得左上角兩個分類模糊，且分類個數(shù)不正確；CDGRDD算法成功識別了不同形狀、不同密度的5個簇，噪聲點檢測十分準確。

實驗3：數(shù)據(jù)Sizes5[17]高密度簇與低密度簇相鄰，有臨界點干擾情況且中心邊緣稀疏更為明顯，數(shù)據(jù)量也相對較大，共有1026個數(shù)據(jù)對象，CDGRDD和ECRGDD中的兩個參數(shù)分別為з=0.53，uλ=0.1；DBSCAN算法中的兩個參數(shù)分別為Eps=1，Minpts=5；GDBSCAN算法中Mintps=9。聚類結果如圖4所示。

ECRGDD聚類算法由于采用固定的初始單元密度，使得類邊緣的數(shù)據(jù)滿足不了公式（2），右上角的類被分成多個類。從圖4（b）中可以看出，雖然DBSCAN可以識別任意形狀的簇，但對于多密度聚類效果并不理想，密度大的類，吸收了較多的噪聲點，密度低的類丟失了較多的本該屬于本類的數(shù)據(jù)，且靠近密度大的稀疏類容易被吸收到密度大的類中；圖4（c）中顯示出GDBSCAN算法對中心密邊緣稀疏的類聚類效果也不理想，且存在瑕疵點（明顯屬于該類，卻被當成噪聲點）；CDGRDD算法準確識別出了4個相鄰、密度不同的類，且吸收了少量的噪聲點到簇中。

下面對實驗結果進行定量分析，DS1、DS2實驗結果見表1、表2。

由于DS3的邊界點無確定分類，第3組實驗采用有10 000個數(shù)據(jù)的DS4[18]，DS4圖形如圖6所示，實驗結果見表3。

由以上實驗可以看出，在處理多密度數(shù)據(jù)中，本文提出的CDGRDD聚類效果優(yōu)于其它算法。對于密度相對均勻的DS4，其它聚類算法效果也不錯。

4 結語

實驗證明，本文提出的CDGRDD聚類算法，針對中心邊緣稀疏的數(shù)據(jù)，利用動態(tài)的網(wǎng)格單元密度den（g0）計算相對密度差，對網(wǎng)格合并加入距離限制，在不增加時間復雜度的基礎上有效提高了算法對各種數(shù)據(jù)的適應性和準確性，對于不規(guī)則的多密度數(shù)據(jù)集有較為準確的聚類效果。但當維數(shù)d增加時，劃分的網(wǎng)格數(shù)將以指數(shù)級增長，因此下一步的研究重點是如何減少網(wǎng)格數(shù)量的處理。

參考文獻：

[1]JACOB M，HELLSTRM T.Policy understanding of science，public

trust and the BSE-CJD crisis[J].Journal of Hazardous Materials，2000，78（1）：303-317.

[2]HUANG J，ZHANG J.Fuzzy C-means clustering algorithm with spatial constraints for distributed WSN data stream[EB/OL].http：//med.wanfangdata.com.cn/Paper/Detail？id=PeriodicalPaper_JJ025372934 2011.

[3]GUHA S，RASTOGI R，SHIM K.Cure： an efficient clustering algorithm for large databases[J].Information Systems，1998，26（1）：35-58.

[4]ESTER M，KRIEGEL H P，SANDER J，et al.A density-based algorithm for discovering clusters in large spatial databases with noise[J].Kdd，1996，96（34）： 226-231.

[5]AGRAWAL R，GEHRKE J，GUNOPULOS D，et al.Automatic subspace clustering of high dimensional data for data mining applications[M].ACM，1998.

[6]YOUSRI N A，KAMEL M S，ISMAIL M A.A distance-relatedness dynamic model for clustering high dimensional data of arbitrary shapes and densities[J].Pattern Recognition，2009，42（7）： 1193-1209.

[7]WU J，LIU H，XIONG H，et al.A theoretic framework of K-means-based consensus clustering[C].IJCAI，2013.

[8]何童.不確定性目標的CLARANS聚類算法[J].計算機工程，2012，38（11）：56-58.

[9]HU BO-LEI，TAN JIAN-HAO.Clustering algorithm based on cumulative average density[J].Computer Engineering & Science，2013，35（1）：155-159.

[10]XU HONG-BO，HAO ZHONG-XIAO.Grid-partition Clustering Algorithm Based on Hilbert Curve[J].Journal of Chinese Computer Systems，2010，31（10）：1979-1983.

[11]ERTOZ L，STEINBACH M，KUMAR V.A new shared nearest neighbor clustering algorithm and its applications[C].Workshop on Clustering High Dimensional Data and its Applications at 2nd SIAM International Conference on Data Mining.2002： 105-115.

[12]周水庚，周傲英，曹晶，等.一種基于密度的快速聚類算法[J].計算機研究與發(fā)展，2000，37（11）：1287-1292.

[13]黃紅偉，黃天民.基于網(wǎng)格相對密度差的擴展聚類算法[J].計算機應用研究，2014，31（6）：1702-1705.

[14]馮振華，錢雪忠，趙娜娜.Greedy DBSCAN：一種針對多密度聚類的DBSCAN改進算法[J].計算機應用研究，2016，33（9）：1522-1529.

[15]PIEGL L A，TILLER W.Algorithm for finding all k，nearest neighbors[J].Computer-Aided Design，2002，34（2）：167-172.

[16]Clustering datasets[EB/OL].http：//cs.joensuu.fi/sipu/datasets/.

[17]Read pudn[EB/OL].http：//www.pudn.com/downloads219/sou rcecode/math/detail1 030717.html.

[18]KHALID S，RAZZAQ S.TOBAE：a density-based agglomerative clustering algorithm[J].Journal of Classification，2015，32（2）：241-267.

（責任編輯：杜能鋼）