基于變化密度的自適應(yīng)空間聚類方法研究

楊亞軍，張坤龍，楊曉科

(天津大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300072)

1 概述

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

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

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

2 相關(guān)研究

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

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

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

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

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

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

3 DBSCAN 算法

3.1 算法基本思想

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

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

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

例如圖1 為一個包含18 個點的數(shù)據(jù)集A 的散點圖，這個數(shù)據(jù)集包括2 個簇，每個簇分別有9 個點，該數(shù)據(jù)集的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 為核點，標(biāo)記為簇1，然后依次處理c 和f。先將c 標(biāo)記為簇1，然后判斷c 的二鄰居為a 和g。由于a 的密度與c有顯著差異，則c 不作為核點，接下來用同樣的方法處理其余的點。這樣可以識別出簇邊界，并且停止當(dāng)前簇的擴(kuò)展。

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

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

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

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

3.2 算法描述

在介紹改進(jìn)算法之前，需要對DBSCAN 中的一些定義進(jìn)行修改，并且增加一些新的定義，其中，2 個點p 和q 的歐幾里德距離用dist(p，q)表示，D 表示聚類數(shù)據(jù)集，它是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)。即當(dāng)所有的鄰居到p 的距離不同時，N(p)的勢為k，否則N(p)的勢可能大于k。

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 自適應(yīng)機(jī)制

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

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

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

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

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

3.4 算法分析

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

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

3.5 參數(shù)選擇

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

4 實驗分析

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

4.1 實驗數(shù)據(jù)

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

圖3 dataset1 散點圖

圖4 dataset2 散點圖

4.2 結(jié)果分析

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

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

圖5 聚類結(jié)果

表1 參數(shù)設(shè)置

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

5 結(jié)束語

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

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

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

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

［10］歐陽佳，林丕源.基于DBSCAN 算法的網(wǎng)頁正文提?。跩］.計算機(jī)工程，2011，37(3):64-66.

［11］蔡 岳，袁津生.基于改進(jìn)DBSCAN 算法的文本聚類［J］.計算機(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.