錢(qián)雪忠+韓利釗+羅靖

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

關(guān)鍵詞：動(dòng)態(tài)初始單元；多密度聚類(lèi)；網(wǎng)格相對(duì)密度差；模糊函數(shù)

DOIDOI：10.11907/rjdk.171164

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2017）006-0032-05

0 引言

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

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

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

1 擴(kuò)展聚類(lèi)算法

1.1 算法簡(jiǎn)介

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

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

1.2 ECRGDD算法存在的問(wèn)題

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

3.2 實(shí)驗(yàn)結(jié)果及分析

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

說(shuō)明：所有實(shí)驗(yàn)結(jié)果中的‘×為噪聲點(diǎn)。

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

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

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

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

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

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

下面對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行定量分析，DS1、DS2實(shí)驗(yàn)結(jié)果見(jiàn)表1、表2。

由于DS3的邊界點(diǎn)無(wú)確定分類(lèi)，第3組實(shí)驗(yàn)采用有10 000個(gè)數(shù)據(jù)的DS4[18]，DS4圖形如圖6所示，實(shí)驗(yàn)結(jié)果見(jiàn)表3。

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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]何童.不確定性目標(biāo)的CLARANS聚類(lèi)算法[J].計(jì)算機(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]周水庚，周傲英，曹晶，等.一種基于密度的快速聚類(lèi)算法[J].計(jì)算機(jī)研究與發(fā)展，2000，37（11）：1287-1292.

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

[14]馮振華，錢(qián)雪忠，趙娜娜.Greedy DBSCAN：一種針對(duì)多密度聚類(lèi)的DBSCAN改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用研究，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.

（責(zé)任編輯：杜能鋼）