基于動態的網格相對密度差聚類算法研究

錢雪忠+韓利釗+羅靖

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

關鍵詞：動態初始單元；多密度聚類；網格相對密度差；模糊函數

DOIDOI：10.11907/rjdk.171164

中圖分類號：TP312

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

0 引言

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

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

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

1 擴展聚類算法

1.1 算法簡介

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

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

1.2 ECRGDD算法存在的問題

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

3.2 實驗結果及分析

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

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

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

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

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

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

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

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

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

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

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

4 結語

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

參考文獻：

[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].計算機研究與發展，2000，37（11）：1287-1292.

[13]黃紅偉，黃天民.基于網格相對密度差的擴展聚類算法[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.

（責任編輯：杜能鋼）