楊亞軍，張坤龍，楊曉科

(天津大學計算機科學與技術學院，天津 300072)

1 概述

聚類是一種十分重要的數(shù)據挖掘方法。它的目標是將數(shù)據對象進行分組，使得組內對象之間的相似性比組間對象之間的相似性大。聚類具有廣泛的用途，它既可以用于理解客觀世界，同時也可以作為其他數(shù)據挖掘方法的預處理，例如可以用于孤立點檢測等［1］。許多學者對聚類進行了研究，他們提出了大量聚類算法，包括分層聚類、劃分聚類、基于密度的聚類、基于格的聚類、基于模型的方法和一些比較新的方法，例如核聚類、譜聚類、蟻群聚類等。其中基于密度的聚類比較優(yōu)秀，它可以聚類任意形狀和大小的簇。

DBSCAN (Density Based Spatial Clustering of Applications with Noise)［2］是基于密度聚類的基礎。它認為簇是由稀疏部分隔開的稠密區(qū)域，因此可以通過擴展密度大的點即核點來發(fā)現(xiàn)簇。DBSCAN 能夠聚類任意形狀和大小的簇，并且不受孤立點的影響。但是當數(shù)據集的各個簇的密度不同，并且簇之間沒有被稀疏部分隔開時DBSCAN 就會遇到困難，無法產生正確的聚類結果。許多算法針對變化密度進行 改 進，如SNN(Shared Nearest Neighbor)［3］和VDBSCAN(Varied Density Based Spatial Clustering of Application with Noise)［4］等，它們雖然可以發(fā)現(xiàn)不同密度的簇，但在某些情況下無法產生正確的結果，并且選擇合適的參數(shù)是十分困難的。

針對參數(shù)不易選擇和無法處理變化密度的問題，本文對DBSCAN 算法進行了改進，并提出了一種自適應的基于變化密度的空間聚類方法(SAVDBSCAN)。算法以點到其第k 個最鄰近鄰居的距離作為密度，若一個點的密度與其k 個最鄰近鄰居中的每個點的密度相似，則將該點作為核點進行擴展。對于相似性判斷，首先由用戶給定一個閾值，然后算法在每次加入一個核點后進行自適應，得到一個更合適的值。

2 相關研究

DBSCAN［2］是基于密度聚類的奠基，它認為簇是由稀疏或者空白區(qū)域隔開的稠密區(qū)域。DBSCAN 引入了密度的概念，定義一個點的密度為以該點為圓心用戶指定大小Eps 為半徑的圓內的數(shù)據點的個數(shù)，并將密度大于用戶給定閾值MinPts 的點定義為核點。算法通過擴展相通的核點來發(fā)現(xiàn)簇。DBSCAN 可以發(fā)現(xiàn)任意形狀和大小的簇，并且不受孤立點的影響。DBSCAN 的算法復雜性為O(N2)，如果存在空間索引，其算法復雜性為O(NlogN)。但是當簇的密度有顯著的變化并且簇之間沒有被空白或稀疏區(qū)域隔開，DBSCAN 無法產生正確的結果，并且選擇合適的參數(shù)Eps 和MinPts 是很困難的。

OPTICS［5］針對DBSCAN 無法處理變化密度的問題進行了改進。OPTICS 并不顯式的進行簇標記，而是分析生成一個有序對象列表。從這個排序的列表中可以得到任意參數(shù)Eps 和MinPts 的DBSCAN 的聚類結果。

SNN(Shared Nearest Neighbour)［3］使用2 個節(jié)點共享鄰居的個數(shù)來度量相似性。算法利用稀疏化的相似矩陣來構建共享鄰居圖，并利用共享鄰居圖計算出每個點的SNN 密度。然后利用DBSCAN 的方法進行聚類。SNN 算法可以有效地聚類不同大小、形狀和密度的簇，但是算法復雜性高，并且參數(shù)的選擇也比較麻煩。

VDBSCAN［4］是另外一個對DBSCAN 進行改進的算法。VDBSCAN 利用k 鄰居距離圖得到一系列局部Eps 值，并從最小的局部Eps 開始依次對未標記的數(shù)據對象應用DBSCAN，直到所有的局部Eps值都已處理完，則算法結束。VDBSCAN 可以處理不同密度的聚類，但是算法比較復雜，需要先繪制k 鄰居距離圖，并且有的時候k 鄰居距離圖無法明顯的反映出局部Eps 值，k 的選擇也是比較困難的。

此外，文獻［6-11］對DBSCAN 不能處理變化密度的問題提出了改進，其中，文獻［7-8］提出了參數(shù)自適應的思想，試圖在算法運行的過程中自動對參數(shù)進行選擇。

以上提到的各種聚類算法都嘗試解決不同形狀、大小和密度的聚類問題。盡管有的算法可以取得相當好的聚類效果，例如SNN，但它們都存在一個相同的問題，即算法對參數(shù)十分敏感，并且選擇合適的參數(shù)是十分困難的。

3 DBSCAN 算法

3.1 算法基本思想

DBSCAN 之所以不能聚類變化密度的簇，是因為它有2 個全局的參數(shù)Eps 和MinPts，在算法開始時給定參數(shù)的值，并且運行時不會改變。當簇的密度發(fā)生變化時，一個全局的參數(shù)無法對所有的簇都適用，因此必須能夠針對不同的簇合理的給出密度，并且這個密度在不同的簇之間是可以變化的。

對空間數(shù)據的特征進行研究，發(fā)現(xiàn)同一個簇內的點到其第k 個最鄰近鄰居的距離大致是相同的，而來自不同密度的簇中的點到其第k 個最鄰近鄰居的距離有顯著的差異［4］。這個結論可以通過繪制k鄰居距離圖來證明。k 鄰居距離圖是將所有點按照到第k 個最鄰近鄰居的距離升序排列，然后以點在排序中的位置為橫坐標，以該點到第k 個最近鄰居的距離為縱坐標繪制而成。因此，以點到其第k 個最鄰近鄰居的距離作為密度就可以滿足同一簇中的密度相似，而不同密度簇中的點密度存在差異。

有了密度的定義之后，需要對數(shù)據點進行遍歷，將那些相通的密度相似的點聚類到同一個簇中，并且要識別出簇邊界，停止當前簇的擴展。根據密度的定義，簇的邊界就是點的密度發(fā)生顯著變化的地方。因此，只有當一個點的k 個最鄰近鄰居的密度與該點相似時，該點才作為核點進行擴展，并且依次擴展它的k 個鄰居。

例如圖1 為一個包含18 個點的數(shù)據集A 的散點圖，這個數(shù)據集包括2 個簇，每個簇分別有9 個點，該數(shù)據集的2 鄰居距離圖如圖2 所示。其中，9 個點到第2 個最鄰近鄰居的距離為1，它們都屬于簇1。有7 個點到第2 個最鄰近鄰居的距離為2，它們屬于簇2。還有2 個點a 和b 到第2 個最鄰近鄰居的距離為1.41，它們屬于簇2，但是位于簇2 和簇1 的交界處。若算法首先處理d 點，其最鄰近2 鄰居為c 和f，由于c 和f 的密度與d 相似，則d 為核點，標記為簇1，然后依次處理c 和f。先將c 標記為簇1，然后判斷c 的二鄰居為a 和g。由于a 的密度與c有顯著差異，則c 不作為核點，接下來用同樣的方法處理其余的點。這樣可以識別出簇邊界，并且停止當前簇的擴展。

圖1 數(shù)據集A 散點圖

圖2 數(shù)據集A 的2 鄰居距離示意圖

當多個點之間的距離相同的時候，會出現(xiàn)一個問題，稱之為封閉集團。一個封閉集團是一個點的集合，并且該集合內的所有點的k 個最鄰近鄰居也在該集合內。例如圖1 中的{d，f，e，g}即為一個封閉集團，其中，d 的鄰居為e 和f，f 的鄰居為d 和g，g的鄰居為e 和f，e 的鄰居為d 和g。這樣在擴展簇1的時候一旦進入這個封閉集團就無法出來，不能產生正確的結果。為了克服這個問題，計算一個點的最鄰近鄰居的時候，首先計算k 個最鄰近鄰居，然后將到該點的距離與第k 個最鄰近鄰居到該點距離相同的點也加入到鄰近鄰居集合中，并且進行核點判斷的時候，只要最鄰近鄰居中有不少于k 個鄰居的密度與當前擴展點的密度相似，就將該點作為核點擴展。

此外，算法可以在運行的時候根據已經處理的點的性質，動態(tài)更新參數(shù)的值，使之趨向于真實的值。

3.2 算法描述

在介紹改進算法之前，需要對DBSCAN 中的一些定義進行修改，并且增加一些新的定義，其中，2 個點p 和q 的歐幾里德距離用dist(p，q)表示，D 表示聚類數(shù)據集，它是d 維空間Rd中點的集合。

定義1(density(p)) 一個點p 的密度為p 到其第k 個最鄰近鄰居的距離。其中，k 為用戶給定的參數(shù)。

定義2(N(p)) 一個點p 的N(p)表示點p 的最鄰近鄰居的集合，首先是將p 的k 個最鄰近鄰居加入到N(p)中，然后將那些到p 的距離與p 的第k 個最鄰近鄰居到p 的距離相似的點也加入到N(p)。即當所有的鄰居到p 的距離不同時，N(p)的勢為k，否則N(p)的勢可能大于k。

定義3(cdensity(p)) 一個點p 的cdensity (p)表示p 所屬的簇中當前已經擴展的核點的density 的平均值。

定義4(similar-neighbor(p，q)) 如果p 的鄰居q 是p 的相似鄰居，當且僅當式(1)成立，α 為用戶指定的參數(shù)。

定義5(核點) 一個點p 稱之為核點，當且僅當它的最鄰近鄰居中至少有k 個是p 的相似鄰居。

定義6(邊界點) 一個點p 為邊界點，當且僅當它是一個核點的相似鄰居，但是它不是核點。

定義7(孤立點) 一個點p 為孤立點，當且僅當p 既不是核點也不是邊界點。

用包含4 個字段的結構體表示空間中的每個點，4 個字段為:該點的坐標，簇標號字段Cp，最鄰近鄰居數(shù)組(用來保存最鄰近鄰居)和密度density。初始時，Cp=-1，density=-1。一個點有3 種狀態(tài):已處理，候選處理和未處理。

定義8(已處理) 若一個點p 的狀態(tài)為已處理，則該點的density(p)已經計算得出，它的最鄰近鄰居中的任意一點q 的density(q)也已計算出，并且簇標記Cp 不等于-1。

定義9(候選處理) 若一個點p 的狀態(tài)為候選處理，則該點的density(q)已經計算得出，Cp 不等于-1，但是它的最鄰近鄰居中至少存在一點q 的density(q)未計算出。

定義10(未處理) 若一個點p 的狀態(tài)為未處理，則該點的Cp 值為-1，該點的density (q)也為-1。

此外，算法還需要一個隊列corequeue 和一個全局變量current-cluster-id。其中corequeue 用來保存候選擴展的核點，current-cluster-id 保存當前簇的簇標號，初始值為0。

算法從未處理的點中選擇一個點p，計算它的密度density(p)，并且計算它的最鄰近鄰居中所有點q的密度density(q)，同時判斷q 是否為p 的相似鄰居。若p 的最鄰近鄰居中至少有k 個是它的相似鄰居，那么p 就是一個核點，即說明發(fā)現(xiàn)了一個新的簇，此時應該將current-cluster-id 的值加1，并且將點p 加入到corequeue 中。若corequeue 非空，則從中彈出一個核點curcore，將其簇標號Cp 設置為current_cluster_id 的值，并且依次處理它的最鄰近鄰居。對于每一個鄰居q，首先將q 的Cp 值設置為currentcluster-id 的值，然后計算q 的密度變化率是否小于α，并且判斷q 的最鄰近鄰居中是否至少有k 個是q的相似鄰居，若是則q 為核點，將q 加入到隊列corequeue 中，然后再從corequeue 彈出一個點，按上述方式處理，直到corequeue 為空，則表示一個簇已經擴展完成，算法再從剩下的未處理的點中找一個點重復上述過程，直到所有的點都已經處理完畢。算法的偽代碼如下:

函數(shù)isCore 用來判斷一個點是否為核點。傳入參數(shù)p 為要判斷的點，c 為當前簇的平均密度，α為密度變化閾值，D 為數(shù)據集。若一個點的最鄰近鄰居中至少有k 個是它的相似鄰居，那么該點就是核點。對于簇的起始核點和擴展核點的處理存在差異。簇的起始核點的最鄰近鄰居必須是沒有簇標號的，即它的最鄰近鄰居中至少有k 個沒有簇標號的鄰居是它的相似鄰居，那么該點才作為簇起始點。

update cdensity 是對當前簇的簇密度進行更新，update α 是對密度的變化閾值進行更新，這2 個方法將在3.3 節(jié)詳細介紹。

3.3 自適應機制

空間數(shù)據中同一個簇中的點的密度大致相同，它們近似服從高斯分布［7］，算法用已擴展核點的密度的平均值作為均值。基于這個思想，在對p 的鄰居q 進行相似鄰居判斷的時候，用當前簇中已處理過的核點(包含點p)的密度的平均值cdensity(p)來代替density(p)，則相似鄰居的判定公式就變?yōu)槭?2):

cdensity(p)的值在每次從corequeue 中彈出一個核點的時候按式(3)更新:

其中，n 為包括p 在內的當前簇中已擴展的核點個數(shù);cdensity(p)'是不包含點p 的簇密度平均值。這樣用均值代替某個點可以避免個別特殊點引起的聚類錯誤。

密度的波動為方差，方差在［0，α)區(qū)間內，其中，α 為波動范圍的上界。對于α，首先由用戶指定一個閾值，然后算法在運行的過程中，根據每次彈出核點密度偏離中心的程度對α 的值進行動態(tài)更新。具體的，當從corequeue 中彈出一個核點p 時，根據式(4)計算它偏離中心的程度d。

然后根據式(5)對α 進行自適應。當d 的值小于α/2 時，需要對α 進行縮減。當d 的值大于α/2時，需要增加α 的值。縮減的比例小于增加的比例。這是因為α 是偏離中心程度的上限，根據高斯分布的特征，大部分數(shù)據集中在中心值周圍，若縮減的過快，就會因為這些值的影響，而將α 減小到一個比較小的值，從而不能發(fā)現(xiàn)那些d 較大但是滿足相似鄰居的點。這個縮減比例是經過大量實驗之后確定的一個相對比較優(yōu)的值。

3.4 算法分析

算法需要處理所有的數(shù)據點，即需要在所有點上執(zhí)行一次迭代，時間復雜度為O(N)，對于迭代中的每一個點，首先需要計算它的k 個最鄰近鄰居，如果沒有空間索引，計算k 個最鄰近鄰居需要掃描一遍數(shù)據集中的所有點，需要的時間為O(N)，若存在空間索引R 樹，根據R 樹查找最鄰近鄰居的時間復雜度是O(logN)。然后是在核隊列上進行循環(huán)，循環(huán)與N 無關，所以時間復雜度為O(1)，對于核隊列中的每個點，需要處理它的k 個鄰居，這個與N 無關，所以時間復雜度也為O(1)。因此，若沒有空間索引，算法的時間復雜度為O(N2)。若存在空間索引，聚類的時間復雜度為O(NlogN)，建樹的時間復雜度也為O(NlogN)，并且兩者不相關，所以算法的時間復雜度也為O(NlogN)。

綜上所述，若不存在空間索引，算法的時間復雜度為O(N2)，若存在空間索引R 樹，算法的時間復雜度為O(NlogN)。由此可見，本文提出的算法的時間復雜度和DBSCAN 相同。

3.5 參數(shù)選擇

算法有3 個輸入參數(shù):dataset，k 和α。其中，dataset 是聚類的輸入數(shù)據集，這個參數(shù)對于所有聚類算法都一樣，在這里不做討論。第2 個參數(shù)k 是要計算的最鄰近鄰居的個數(shù)，類型為整數(shù)。k 的選擇偏小會將一個自然簇分裂成若干個，k 的選擇偏大，可能會合并自然簇。根據大量的實驗，k 一般選擇8～16之間的整數(shù)可以取得比較好的聚類效果。α是度量相似鄰居的閾值，即允許密度變化率的最大值。若α 選擇過大，則會合并自然簇，若α 的選擇偏小，則會將一個自然簇分裂。因為算法有自適應功能，所以α 一般選擇0～1 之間的一位小數(shù)即可，算法運行過程中可以自適應到合適的值。由此可見，本文提出的算法的參數(shù)空間是比較小的，因此較容易選擇合適的參數(shù)。

4 實驗分析

這一部分評估了SAVDBSCAN 算法，并且與CHAMELEON［12］和SNN 的結果進行了比較。用Java 實現(xiàn)了SAVDBSCAN 算法，在一個雙核，主頻為2.6 GHz，內存2 GB，安裝有Linux 操作系統(tǒng)的機器上進行了實驗。

4.1 實驗數(shù)據

本文在4 個數(shù)據集上測試了算法的聚類效果。其中前2 個數(shù)據集是來自CHAMELEON 算法的實驗數(shù)據，分別是t7.10k.dat 和t8.8k.dat。另外2 個是自己產生的數(shù)據集，包括dataset1 和dataset2。其中，dataset1 是一個由6 000 個點組成的3 個嵌套的同心圓，每個圓環(huán)里有2 000 個點，最里邊的圓的密度最大，向外密度依次降低，如圖3 所示。dataset2 是一條由5 400 個點組成的“魚”，眼睛的密度最高，尾巴的密度最低，如圖4 所示。

圖3 dataset1 散點圖

圖4 dataset2 散點圖

4.2 結果分析

CHAMELEON 數(shù)據集的聚類結果如圖5(a)和圖5(b)所示。不同的形狀代表不同的簇，孤立點已經被消除。具體地，圖5(a)為t7.10.dat 的結果，其中，k 為11，α 為0.7。圖5(b)為t8.8k.dat 的聚類結果，k 為14，α 為0.6。算法的聚類結果與SNN 算法和CHAMELEON 算法的聚類結果相似，不同之處在于對邊界和孤立點的處理存在微小差異，SNN 和CHAMELEON 的結果可參照相關文獻。算法可以準確地發(fā)現(xiàn)自然簇，并且識別出孤立點，而且參數(shù)設置更簡單，相同的結果可以有多種參數(shù)選擇，具體如表1 所示。

dataset1 的聚類結果如圖5(c)所示，k 取16，α為0.9，算法準確地發(fā)現(xiàn)了3 個簇，分別用3 種不同的顏色標記。而且在邊界上的聚類也很準確，比較光滑，沒有出現(xiàn)鋸齒。圖5(d)為dataset2 的聚類結果，k 為16，α 為0.4。從圖上可以看出算法能夠準確地識別出“魚”的各個部分。

圖5 聚類結果

表1 參數(shù)設置

實驗結果表明，算法可以準確地聚類任意形狀、大小和密度的簇，并且識別出孤立點，可以取得與CHAMELEON 和SNN 相同的聚類結果。此外，通過自適應，參數(shù)的設置也變得十分容易，同樣的結果可以有多種參數(shù)設置。

5 結束語

本文針對DBSCAN 不能處理變化密度的缺點，提出一個改進的算法SAVDBSCAN。算法基于同一個簇中的點到其第k 個鄰居的距離比不同簇中的點相似的思想，將一個點到其第k 個最鄰近鄰居的距離作為密度的度量，并且引入了相似鄰居的概念，若一個點p 的鄰居q 的密度與p 的密度變化率小于用戶給定的閾值，則q 為p 的相似鄰居。然后重新定義核點，一個點的最鄰近鄰居中至少有k 個相似鄰居，則該點為核點。在修改后運用DBSCAN 算法進行聚類。為了取得更好的聚類效果，算法進行了參數(shù)的自適應，主要有2 個方面:(1)在計算一個點的相似鄰居時，以該點所在的簇當前已擴展核點的密度的平均值代替該點的密度;(2)在進行相似鄰居判斷時，自適應變化閾值α。通過自適應機制，本文算法可以在運行時根據數(shù)據的分布情況，自動調整參數(shù)的值，從而更好地發(fā)現(xiàn)自然簇。實驗結果表明，SAVDBSCAN 可以發(fā)現(xiàn)任意形狀、大小和密度的簇，并且有效地檢測出孤立點。此外，可以取得和SNN 以及CHAMELEON相似的聚類效果，并且參數(shù)空間更小，取得合適的參數(shù)比較容易。下一步工作將根據數(shù)據的特性，自動選擇合適的k 值，使得不同密度簇中的點到第k 個最鄰近鄰居的距離有明顯的差異。

［1］Xu R，Wunsch D.Survey of Clustering Algorithms［J］.IEEE Transactions on Neural Networks，2005，16(3):645-678.

［2］Ester M，Kriegel H P，Sander J，et al.A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise［C］//Proc.of Conference on Knowledge Discovery and Data Mining.Portland，USA:AAAI Press，1996:216-224.

［3］Ertoz L，Steinbach M，Kumar V.Finding Clusters of Different Sizes，Shapes，and Densities in Noisy，High Dimensional Data［C］//Proc.of SIAM International Conference on Data Mining.Chicago，USA:［s.n.］，2003:333-341.

［4］Liu P，Zhou D，Wu N.Varied Density Based Spatial Clustering of Application with Noise［C］//Proc.of International Conference on Service Systems and Service Management.Chengdu，China:［s.n.］，2007:123-129.

［5］Ankerst M，Breunig M M，Kriegel H P，et al.OPTICS:Ordering Points to Identify the Clustering Structure［J］.ACM SIGMOD Record，1999，28(2):49-60.

［6］馬 帥，王騰蛟，唐世渭，等.一種基于參考點和密度的快速聚類算法［J］.軟件學報，2003，14(6):1089-1095.

［7］陳 剛，劉秉權，吳 巖.一種基于高斯分布的自適應DBSCAN 算法［J］.微電子學與計算機，2013，30(3):27-30.

［8］夏魯寧，荊繼武.SA-DBSCAN:一種自適應基于密度聚類算法［J］.中國科學院研究生院學報，2009，26(4):530-538.

［9］于亞飛，周愛武.一種改進的DBSCAN 密度算法［J］.計算機技術與發(fā)展，2011，21(2):30-33.

［10］歐陽佳，林丕源.基于DBSCAN 算法的網頁正文提取［J］.計算機工程，2011，37(3):64-66.

［11］蔡 岳，袁津生.基于改進DBSCAN 算法的文本聚類［J］.計算機工程，2011，37(12):50-52.

［12］Karypis G，Han E H，Kumar V.Chameleon:Hierarchical Clustering Using Dynamic Modeling［J］.Computer，1999，32(8):68-75.