楊亞軍，張坤龍，楊曉科

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

1 概述

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

DBSCAN (Density Based Spatial Clustering of Applications with Noise)［2］是基于密度聚類的基礎(chǔ)。它認(rèn)為簇是由稀疏部分隔開的稠密區(qū)域，因此可以通過擴(kuò)展密度大的點(diǎn)即核點(diǎn)來發(fā)現(xiàn)簇。DBSCAN 能夠聚類任意形狀和大小的簇，并且不受孤立點(diǎn)的影響。但是當(dāng)數(shù)據(jù)集的各個(gè)簇的密度不同，并且簇之間沒有被稀疏部分隔開時(shí)DBSCAN 就會(huì)遇到困難，無法產(chǎn)生正確的聚類結(jié)果。許多算法針對(duì)變化密度進(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ù)是十分困難的。

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

2 相關(guān)研究

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

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

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

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

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

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

3 DBSCAN 算法

3.1 算法基本思想

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

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

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

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

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

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

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

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

3.2 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

cdensity(p)的值在每次從corequeue 中彈出一個(gè)核點(diǎn)的時(shí)候按式(3)更新:

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

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

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

3.4 算法分析

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

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

3.5 參數(shù)選擇

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

4 實(shí)驗(yàn)分析

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

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

圖3 dataset1 散點(diǎn)圖

圖4 dataset2 散點(diǎn)圖

4.2 結(jié)果分析

CHAMELEON 數(shù)據(jù)集的聚類結(jié)果如圖5(a)和圖5(b)所示。不同的形狀代表不同的簇，孤立點(diǎn)已經(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é)果相似，不同之處在于對(duì)邊界和孤立點(diǎn)的處理存在微小差異，SNN 和CHAMELEON 的結(jié)果可參照相關(guān)文獻(xiàn)。算法可以準(zhǔn)確地發(fā)現(xiàn)自然簇，并且識(shí)別出孤立點(diǎn)，而且參數(shù)設(shè)置更簡(jiǎn)單，相同的結(jié)果可以有多種參數(shù)選擇，具體如表1 所示。

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

圖5 聚類結(jié)果

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

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

5 結(jié)束語(yǔ)

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

［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］馬 帥，王騰蛟，唐世渭，等.一種基于參考點(diǎn)和密度的快速聚類算法［J］.軟件學(xué)報(bào)，2003，14(6):1089-1095.

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

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

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

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

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