基于網(wǎng)格梯度的多密度聚類算法

（重慶郵電大學(xué) 中韓合作空間信息系統(tǒng)研究所， 重慶 400065）



摘要：大多數(shù)現(xiàn)有的聚類算法都致力于發(fā)現(xiàn)任意形狀、任意大小的類，但很難有效處理多密度的數(shù)據(jù)集。提出的算法利用網(wǎng)格聚類速度快的特點(diǎn)，先通過(guò)高斯平滑去除噪聲，再采用網(wǎng)格梯度的思想找出隱藏在多密度數(shù)據(jù)集中的簇。算法在人工數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，結(jié)果表明該算法能有效地去除噪聲，發(fā)現(xiàn)多密度的簇，具有較好的聚類效果。

關(guān)鍵詞：聚類算法； 梯度； 網(wǎng)格； 密度； 相似性

中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)11-3278-03



Grid gradient-based multi-density clustering algorithm



XIA Ying， LI Ke-fei， FENG Jiang-fan



(SIKO-GIS Research Center， Chongqing University of Posts Telecommunications， Chongqing 400065， China)



Abstract:At present， most clustering algorithms devote to find the arbitrary shape and different size clusters， but it is difficult to deal with the multi-density data set effectively. This paper proposed the algorithm which used the grid-based character of rapidity. Firstly， it wiped off the noise using the Gaussian smoothing， then found the cluster which hid in multi-density data set. In the experiment， used the artificial data on the algorithm. The result indicates the algorithm can wipe off the noise effectively and find out the multi-density cluster. The clustering result is good.

Key words：clustering algorithm; gradient; grid; density; similarity



0引言

聚類是將數(shù)據(jù)對(duì)象分成類或簇的過(guò)程，使同一個(gè)簇中的對(duì)象之間具有很高的相似度，而不同簇中的對(duì)象高度相異^[1]。聚類源于許多研究領(lǐng)域，包括數(shù)據(jù)挖掘、統(tǒng)計(jì)學(xué)、生物學(xué)和機(jī)器學(xué)習(xí)等。聚類分析是數(shù)據(jù)挖掘中一種非常重要的技術(shù)和方法，是自發(fā)、無(wú)監(jiān)督的學(xué)習(xí)過(guò)程。通過(guò)聚類能夠識(shí)別對(duì)象空間中稠密和稀疏區(qū)域，從而發(fā)現(xiàn)全局分布模式和數(shù)據(jù)屬性之間有趣的相關(guān)。近幾年來(lái)，聚類分析已經(jīng)廣泛地成功應(yīng)用于許多領(lǐng)域，包括市場(chǎng)研究、模式識(shí)別、數(shù)據(jù)分析和圖像處理等。

針對(duì)聚類分析，專家們提出了許多算法。這些算法大致可分為劃分方法^[2]、層次方法^[3]、基于密度的方法^[4]、基于網(wǎng)格的方法^[5]和基于模型的方法^[6]。聚類在很多實(shí)際應(yīng)用中都發(fā)揮著很重要的作用，不同的應(yīng)用對(duì)聚類處理有不同的要求，一些典型的要求如輸入?yún)?shù)的個(gè)數(shù)及所需的先驗(yàn)知識(shí)最小化；能夠發(fā)現(xiàn)任意形狀的簇；能夠處理帶有噪聲的數(shù)據(jù)；能夠發(fā)現(xiàn)多密度的簇；能夠增量聚類；對(duì)輸入記錄的次序不敏感；能夠處理海量數(shù)據(jù)等。

在聚類所使用的數(shù)據(jù)集中，各個(gè)類的密集程度往往不盡相同，甚至差別很大。大多數(shù)現(xiàn)有的聚類算法都致力于發(fā)現(xiàn)任意形狀、任意大小的類，但很難有效地處理多密度的數(shù)據(jù)集。已有能夠處理多密度數(shù)據(jù)集聚類算法有Chameleon^[3]、GDCIC^[7]、多階段等密度線算法^[8]、SNN^[9]等。Chameleon算法可以用來(lái)處理多密度的數(shù)據(jù)集，但當(dāng)數(shù)據(jù)集較大時(shí)其算法的時(shí)間復(fù)雜度較高；GDCIC算法采用了局部網(wǎng)格密度置信區(qū)間的方法，能夠自動(dòng)識(shí)別稠密區(qū)域，但是不能很好地處理某些高噪點(diǎn)區(qū)域；多階段等密度線算法采用多階段的方式，利用等密度線的思想對(duì)數(shù)據(jù)集進(jìn)行聚類，它的缺點(diǎn)是不能有效地分離出多個(gè)類；SNN算法采用了一種共享近鄰的思想來(lái)定義相似度（對(duì)于數(shù)據(jù)集中每個(gè)點(diǎn)，找出距離其最近的k個(gè)鄰近點(diǎn)，形成一個(gè)集合，然后考慮數(shù)據(jù)集中的任意兩個(gè)點(diǎn)的k個(gè)鄰近點(diǎn)集合交集部分的點(diǎn)數(shù)超過(guò)一個(gè)閾值，則將這兩個(gè)點(diǎn)歸于一類），但是它在處理孤立點(diǎn)或噪聲方面精度不高，而且其時(shí)間復(fù)雜度為O（N2）。本文提出了一種基于網(wǎng)格梯度的多密度聚類算法，先通過(guò)高斯平滑去除噪點(diǎn)；然后計(jì)算出所有的網(wǎng)格梯度，再比較相鄰網(wǎng)格的梯度找出梯度極大網(wǎng)格，相鄰的非極大梯度網(wǎng)格則形成簇。

1相關(guān)概念

傳統(tǒng)的基于網(wǎng)格和密度的聚類算法首先將數(shù)據(jù)空間分成不相交的網(wǎng)格單元，同一單元中的點(diǎn)是相似的，相鄰的高密度單元連接在一起組成聚類，而那些低密度單元作為孤立點(diǎn)、噪點(diǎn)則被舍棄。傳統(tǒng)的基于網(wǎng)格和密度的聚類算法最大的缺點(diǎn)在于采用了絕對(duì)密度作為算法的全局參數(shù)，導(dǎo)致部分網(wǎng)格密度相對(duì)較低的簇被作為噪點(diǎn)而丟棄。聚類的本質(zhì)是使得同一個(gè)簇中的對(duì)象之間具有較高的相似度，而不同簇中的對(duì)象差別較大，即簇與簇（或非簇）區(qū)域之間的界線是相比較而劃分的，簇與簇（或非簇）之間的密度差異是相對(duì)的^[10]。

在劃分了網(wǎng)格的數(shù)據(jù)集中，屬于同一個(gè)簇的網(wǎng)格是相連通的并且密度具有一定的相似性。可以根據(jù)這種相似性（而不是根據(jù)網(wǎng)格密度閾值來(lái)判斷）通過(guò)查找與該單元相似的所有鄰近網(wǎng)格，然后以這些網(wǎng)格來(lái)進(jìn)行擴(kuò)展，從而找到整個(gè)簇。按照這種思想生成的聚類，效果應(yīng)該是最佳的，可以發(fā)現(xiàn)數(shù)據(jù)分布情況不同密度不同的簇。基于網(wǎng)格梯度的多密度聚類算法正是基于這種思想而提出的。

為了便于討論，對(duì)以下概念進(jìn)行說(shuō)明：

概念1網(wǎng)格單元密度是指一個(gè)網(wǎng)格單元中數(shù)據(jù)對(duì)象的個(gè)數(shù)^[11]。現(xiàn)有的基于網(wǎng)格聚類方法區(qū)分高密度單元和低密度單元，只對(duì)高密度單元進(jìn)行聚類。為了識(shí)別不同密度的簇，本文不作此區(qū)分。

概念2網(wǎng)格單元的鄰居是指那些與該網(wǎng)格單元有相鄰邊界或者相鄰點(diǎn)的那些網(wǎng)格。在二維空間中每一個(gè)網(wǎng)格單元有八個(gè)鄰居，如圖2所示，被斜線覆蓋的網(wǎng)格就是灰色網(wǎng)格單元的鄰居。

概念3相似性強(qiáng)區(qū)域是指該區(qū)域的網(wǎng)格單元密度相差較小；反之，相似性弱區(qū)域是指該區(qū)域的網(wǎng)格單元密度相差較大。實(shí)際上簇的內(nèi)部區(qū)域相似性較強(qiáng)，而在簇的邊界區(qū)域相似性較弱。若某個(gè)網(wǎng)格單元能與其相鄰的網(wǎng)格單元?dú)w為一個(gè)簇，表明這個(gè)網(wǎng)格單元與其周圍的網(wǎng)格能夠很好地融合，網(wǎng)格密度與其周圍的網(wǎng)格密度相差較小；而在簇的邊界，相鄰的屬于不同簇（或簇與非簇）的網(wǎng)格單元密度相差較大。如圖3所示，右側(cè)數(shù)據(jù)是左側(cè)局部區(qū)域的網(wǎng)格密度統(tǒng)計(jì)，斜線上下兩側(cè)區(qū)域相似性較強(qiáng)，而斜線區(qū)域的相似性較弱。

概念4高斯平滑是一種應(yīng)用在圖像處理中的信號(hào)處理技術(shù)^[12]。使用高斯函數(shù)作為低通濾波器，濾掉圖像中灰度突變的高頻分量，從而達(dá)到減少噪聲的目的。高斯濾波器是平滑的而且在頻域中大致上是有上限帶寬的，能夠增強(qiáng)原數(shù)據(jù)間的連續(xù)性，對(duì)噪聲進(jìn)行有效的抑制，同時(shí)還保留原數(shù)據(jù)特征。對(duì)于含有噪聲的數(shù)據(jù)集，同樣可以使用這種技術(shù)去除噪點(diǎn)網(wǎng)格。

概念5網(wǎng)格梯度是指網(wǎng)格密度在某處的梯度。在微積分學(xué)中連續(xù)函數(shù)在某點(diǎn)的梯度是這樣一個(gè)矢量，它的方向與取得最大方向?qū)?shù)的方向一致，而它的模為方向?qū)?shù)的最大值。簡(jiǎn)單地講，梯度是反映函數(shù)變化最快的一個(gè)矢量。梯度幅值是指其大小，梯度方向是指其方向。由于網(wǎng)格密度在本質(zhì)上是離散的，網(wǎng)格梯度使用差分來(lái)近似計(jì)算^[12]。把網(wǎng)格梯度方向大致分為四種（水平、豎直、45°方向、135°方向），也就是把0~180°分為四個(gè)部分：0~22.5°以及157.5°~180°算做水平方向；22.5°~67.5°算做45°方向；67.5°~112.5°算做豎直方向；112.5°~157.5°算做135°方向。如圖4所示，如果當(dāng)前網(wǎng)格（灰色）梯度方向如箭頭所示，那么它就是45°方向。

2基于網(wǎng)格梯度的多密度聚類算法

本聚類算法引入了圖像處理邊緣檢測(cè)的思想^[13]，結(jié)合基于網(wǎng)格和密度的聚類算法，針對(duì)多密度數(shù)據(jù)集提出。圖像邊緣檢測(cè)使用高斯平滑減少圖像中的噪聲，根據(jù)邊緣像素灰度突變的特點(diǎn)尋找圖像的邊緣。在聚類中，對(duì)于劃分網(wǎng)格的數(shù)據(jù)集，屬于同一簇的網(wǎng)格相似性較強(qiáng)，其網(wǎng)格梯度幅值較小；而在簇的邊界區(qū)域，網(wǎng)格的相似性較弱，其網(wǎng)格梯度幅值較大。通過(guò)查找局部網(wǎng)格梯度的極大值，找出潛在的邊界網(wǎng)格，如果這些潛在的邊界網(wǎng)格梯度值大于某個(gè)給定閾值（用戶指定），則認(rèn)為該網(wǎng)格為邊界網(wǎng)格，剩下的相鄰網(wǎng)格單元可歸為一個(gè)簇。

算法的思路與處理過(guò)程如下：

a)網(wǎng)格劃分。網(wǎng)格的劃分對(duì)最終聚類結(jié)果有很大的影響。如果網(wǎng)格太大會(huì)將多個(gè)簇合并成一個(gè)簇，最后的聚類結(jié)果不精確；網(wǎng)格太小又會(huì)使網(wǎng)格的數(shù)量接近數(shù)據(jù)對(duì)象的個(gè)數(shù)，時(shí)間復(fù)雜度增加。本文使用文獻(xiàn)[7]中公式來(lái)計(jì)算每一維上的區(qū)間數(shù)目：

m=n/coef M（1）

其中:n是數(shù)據(jù)對(duì)象的總數(shù)；coef M是一個(gè)正整數(shù)的調(diào)節(jié)系數(shù)，用戶可以根據(jù)具體情況進(jìn)行調(diào)整。

b)數(shù)據(jù)分箱。讀取數(shù)據(jù)集中的每個(gè)對(duì)象，根據(jù)其屬性分別劃入相對(duì)應(yīng)的網(wǎng)格單元，并且統(tǒng)計(jì)最終劃入網(wǎng)格單元對(duì)象數(shù)目作為網(wǎng)格密度。

c)去噪。噪點(diǎn)/離群點(diǎn)對(duì)最終的聚類結(jié)果有很大的影響，甚至?xí)?dǎo)致聚類失敗。因此，在計(jì)算網(wǎng)格梯度前要對(duì)所有的網(wǎng)格使用高斯平滑作預(yù)處理，去除大量的噪點(diǎn)/離群點(diǎn)網(wǎng)格。

d)梯度計(jì)算。在平滑處理后的網(wǎng)格單元上計(jì)算每個(gè)網(wǎng)格單元的梯度，最終得到全部網(wǎng)格的梯度。

e)查找梯度極大值網(wǎng)格。梯度幅值越大的網(wǎng)格，表明其網(wǎng)格密度變化越快，最有可能是簇（或非簇）的邊界。將網(wǎng)格單元的梯度幅值與梯度方向上的兩個(gè)相鄰網(wǎng)格的梯度幅值作比較。如果該網(wǎng)格單元的梯度幅值大于另兩個(gè)網(wǎng)格梯度幅值，則將其作為邊界網(wǎng)格的候選單元；否則不作為候選單元。如圖5所示，如果當(dāng)前網(wǎng)格5的梯度方向如箭頭所示，那么它就與網(wǎng)格3、7作比較。 

f)閾值化處理。根據(jù)設(shè)定的閾值，將候選網(wǎng)格單元中梯度幅值大于給定閾值的網(wǎng)格作為邊界網(wǎng)格。使用雙閾值算法：首先對(duì)所有的網(wǎng)格梯度進(jìn)行統(tǒng)計(jì)；然后根據(jù)用戶設(shè)定的兩個(gè)閾值T1和T2（T2約為T(mén)1的兩倍，且0＜T1 ，T2＜1）計(jì)算出低閾值和高閾值。如果候選網(wǎng)格單元的梯度幅值超過(guò)高閾值時(shí)，這些網(wǎng)格構(gòu)成了某個(gè)尺度下確定的邊界網(wǎng)格單元輸出。還有其他一些與某些邊界網(wǎng)格單元連接的候選網(wǎng)格單元，如果它們的梯度幅值超過(guò)低閾值時(shí)，也被當(dāng)做邊界網(wǎng)格單元。

g)標(biāo)志簇。屬于同一個(gè)簇的網(wǎng)格單元是連通的，不同的簇則被邊界網(wǎng)格分隔，根據(jù)這種特點(diǎn)查找所有相鄰接的非邊界網(wǎng)格，將其標(biāo)志為同一個(gè)簇。

h)邊界網(wǎng)格處理。邊界網(wǎng)格包含數(shù)據(jù)集中有著特殊意義的數(shù)據(jù)對(duì)象。它們位于一個(gè)簇的邊沿區(qū)域，其一側(cè)是高密度區(qū)域，另一側(cè)是密度相對(duì)較低的區(qū)域。對(duì)于它們的劃分比較困難。在本文算法中使用硬劃分，即將邊界網(wǎng)格劃分給網(wǎng)格密度較大的簇。

下面給出算法主要步驟的偽碼描述：

輸入：劃分網(wǎng)格的調(diào)節(jié)系數(shù)coef M；估算高閾值的參數(shù)

輸出：clusters(結(jié)構(gòu)體數(shù)組data存儲(chǔ)數(shù)據(jù)對(duì)象和所屬的網(wǎng)格ID；結(jié)構(gòu)體數(shù)組cell存儲(chǔ)網(wǎng)格的相關(guān)信息)

步驟：

根據(jù)用戶輸入的參數(shù)coef M將整個(gè)二維數(shù)據(jù)空間劃分成m2個(gè)網(wǎng)格單元；

for(數(shù)據(jù)對(duì)象D)

映射到網(wǎng)格單元，所屬網(wǎng)格單元標(biāo)號(hào)記入

Data[i].CellID；

++Cell[Data[i].CellID].Density；//計(jì)算網(wǎng)格單元密度

end for

for(網(wǎng)格單元 C)

使用卷積操作進(jìn)行高斯平滑，平滑后網(wǎng)格單元密度記入Cell[i].GausSmo；

end for

for(網(wǎng)格單元 C)

根據(jù)平滑后的網(wǎng)格單元密度計(jì)算梯度幅值

Cell[i].GradMag；

end for

for(網(wǎng)格單元 C)

if(該網(wǎng)格梯度幅值是梯度方向上的極大值)Cell[i].Flag 標(biāo)記為候選邊界網(wǎng)格；

++GradMagList[Cell[i].GradMag]；//統(tǒng)計(jì)梯度極大值

end if

end for

根據(jù)用戶輸入的參數(shù)T和梯度統(tǒng)計(jì)數(shù)組GradMagList計(jì)算出梯度高閾值ThdHigh和低閾值ThdLow；

for(網(wǎng)格單元 C)

if(Cell[i].Flag 是候選邊界網(wǎng)格，并且Cell[i].GradMag大于ThdHigh)

Cell[i].Flag 標(biāo)志為邊界網(wǎng)格；

查找相鄰的候選邊界網(wǎng)格，如果梯度大于ThdLow將其也標(biāo)志為邊界網(wǎng)格；

end if

end for

for(網(wǎng)格單元 C)

if(Cell[i].Flag 非邊界網(wǎng)格)

查找相鄰的非邊界網(wǎng)格，將它們標(biāo)志為同一個(gè)簇；

end if

endfor

for(網(wǎng)格單元 C)

if(Cell[i].Flag 是邊界網(wǎng)格)

將它劃入網(wǎng)格密度最大的鄰居所屬的簇；

end if

end for

3算法分析與測(cè)試

實(shí)驗(yàn)使用的環(huán)境為P4 2.39 GHz的CPU，內(nèi)存為512 MB，操作系統(tǒng)為Windows XP Professional，算法的編寫(xiě)使用Visual C++ 6.0。其中使用的綜合測(cè)試數(shù)據(jù)集為根據(jù)一定規(guī)則隨機(jī)生成，噪點(diǎn)隨機(jī)分布。

31算法的時(shí)間復(fù)雜度

對(duì)于二維空間中的數(shù)據(jù)集，在算法最初需要對(duì)數(shù)據(jù)集進(jìn)行一次掃描，其時(shí)間復(fù)雜度為O(N)，其他步驟所需時(shí)間復(fù)雜度為O(6m2)，因此算法總的時(shí)間復(fù)雜度為O(N+6m2)。其中：N是數(shù)據(jù)對(duì)象的總數(shù)；m是在每一維上劃分區(qū)間的數(shù)目。

32實(shí)驗(yàn)結(jié)果

圖6(a)所示數(shù)據(jù)集由兩部分組成，右側(cè)大圓區(qū)域分布了50 000個(gè)數(shù)據(jù)點(diǎn)，左側(cè)在小圓區(qū)域分布了1 000個(gè)數(shù)據(jù)點(diǎn)，小圓中的數(shù)據(jù)密度約為大圓中的兩倍。圖6(b)表明算法能夠正確識(shí)別出兩個(gè)不同密度的簇。

圖7(a)所示76 000個(gè)數(shù)據(jù)對(duì)象分布在多種幾何圖形區(qū)域，隨機(jī)分布噪點(diǎn)3 000個(gè)。圖7(b)表明算法能夠識(shí)別多種形狀的簇。

圖8(a)是一個(gè)多密度數(shù)據(jù)集；(b)是GDCIC的聚類結(jié)果；(c)是本算法的聚類結(jié)果。與GDCIC算法相比，本算法能夠更好地處理某些高噪點(diǎn)區(qū)域。

4結(jié)束語(yǔ)

本文提出了基于網(wǎng)格梯度的多密度聚類算法。該算法考慮到簇的內(nèi)部區(qū)域相似性較強(qiáng)，而在簇的邊界區(qū)域相似性較弱的特點(diǎn)，通過(guò)計(jì)算網(wǎng)格梯度來(lái)尋找簇，并且使用了高斯平滑處理有效地去除包含孤立點(diǎn)的網(wǎng)格，從而得到較好的聚類效果。算法采用了網(wǎng)格劃分的方法，聚類速度快；對(duì)于網(wǎng)格不作高、低密度的區(qū)分，減輕了用戶參數(shù)選擇的負(fù)擔(dān)。實(shí)驗(yàn)結(jié)果表明，在二維空間下算法能夠?qū)г肼暤亩嗝芏葦?shù)據(jù)集聚類和均勻密度的數(shù)據(jù)集正確聚類。

算法的不足之處是，聚類結(jié)果對(duì)用戶輸入的參數(shù)較為敏感，要根據(jù)數(shù)據(jù)實(shí)際情況進(jìn)行選擇，這對(duì)于算法的穩(wěn)定性有一定影響。因此，如何選取參數(shù)使算法所需的先驗(yàn)知識(shí)最小化是筆者下一步的研究工作。

參考文獻(xiàn)：

［1］HAN Jia-wei， KAMBER M. 數(shù)據(jù)挖掘概念與技術(shù)[M]. 范明， 孟小峰，譯. 北京：機(jī)械工業(yè)出版社，2007.

[2]MacQUEEN J B.Some methods for classification and analysis of multivariate observations[C]//Proc ofthe 5th Berkeley Symp on Mathematical Statistics and Probability. Berkeley: University of California Press， 1967:281-297.

[3]KARYPIS G， HAN E H S， KUMAR V. Chameleon: hierarchical clustering using dynamic modeling [J].IEEE Computer，1999，32(8):68-75.

[4]ESTER M， KRIEGEL H P， SANDER J，et al. A density-based algorithm for discovering clusters in large spatial databases[C]//Proc ofInt Conf on Knowledge Discovery and Data Mining(KDD’96). 1996: 226-331.

[5]WANG W， YANG J， MUNTZ R. STING: a statistical information grid approach to spatial data mining[C]//Proc ofInt Conf on Very Large Data Bases (VLDB’97). Athens， Greece:[s.n.]， 1997:186-195.

[6]FISHER D. Improving inference through conceptual clustering[C]//Proc of the 6th National Conference on Artificial Intelligence. 1987:461-465.

[7]GAO Song， XIA Ying. GDCIC:a grid-based density-confidence-interval clustering algorithm for multi-density dataset in large spatial database[C]//Proc of the 6th International Conference on Intelligent Systems Design and Applications.Washington DC:IEEE Computer Society， 2006:713-717.

[8]趙艷廠， 宋梅， 宋俊德，等. 用于不同密度聚類的多階段等密度線算法[J]. 北京郵電大學(xué)學(xué)報(bào)，2003，26(2):42-47.

[9]ERTZ L， STEINBACH M， KUMAR V. Finding clusters of different sizes， shapes， and densities in noisy， high dimensional data[C]//Proc of the 3rd SIAM International Conference on Data Mining.San Francisco: SIAM Press， 2003:1-12.

[10]劉青寶，鄧蘇，張維明. 基于相對(duì)密度的聚類算法[J]. 計(jì)算機(jī)科學(xué)，2007，34(2):192-195.

[11]HSU C M， CHEN M S．Subspace clustering of high dimensional spatial data with noises[C]//Proc ofthe 8th Pacific-Asia Conf on Knowledge Discovery and Data Mining. Heidlberg: Springer， 2004:31-40.

[12]鄭南寧. 計(jì)算機(jī)視覺(jué)與模式識(shí)別[M]. 北京：國(guó)防工業(yè)出版社， 1998.

[13]CANNY J. A computational approach to edge detection[J].IEEE Trans on PAMI，1986，8(6):679-698.