胡博磊，譚建豪

（湖南大學(xué)電氣與信息工程學(xué)院，湖南 長(zhǎng)沙 410082）

1 引言

聚類分析［1］是根據(jù)事物本身的特性研究個(gè)體的一種方法，它將數(shù)據(jù)分類到不同的類或組，并使得同一個(gè)組內(nèi)的數(shù)據(jù)具有較大的相似性，而不同組中的數(shù)據(jù)則具有較大的相異性。作為數(shù)據(jù)挖掘中的一個(gè)重要研究課題，聚類分析被廣泛應(yīng)用于社會(huì)的各個(gè)領(lǐng)域，如圖像分割、網(wǎng)絡(luò)安全、統(tǒng)計(jì)分析和市場(chǎng)研究等。有關(guān)的聚類方法主要有：劃分的方法、分層的方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法。DBSCAN［2］是一種典型的基于密度的空間聚類方法，它通過(guò)不斷生長(zhǎng)足夠高密度區(qū)域來(lái)進(jìn)行聚類，能夠從含有噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類。但是，它需要用戶輸入?yún)?shù)，聚類結(jié)果嚴(yán)重依賴于用戶參數(shù)的合理選擇；并且它使用了一個(gè)全局密度閾值Minpts，對(duì)于存在多個(gè)不同密度的簇相連的數(shù)據(jù)集，聚類效果不佳。Minpts過(guò)高，會(huì)導(dǎo)致低密度簇被遺漏；Minpts過(guò)低，會(huì)導(dǎo)致高密度的簇被相鄰的低密度的簇包含。國(guó)內(nèi)外許多學(xué)者針對(duì)DBSCAN算法做了改進(jìn)研究。馮少榮［3］等把智能計(jì)算理論引入到聚類研究中，提出了一種基于遺傳算法的DBSCAN改進(jìn)方案，提高了聚類效果。周董［4］等針對(duì)密度不均勻數(shù)據(jù)集，提出了一種改進(jìn)算法，能夠發(fā)現(xiàn)不同密度的簇。李光強(qiáng)［5］等根據(jù)鄰近目標(biāo)間空間局部密度變化情況來(lái)進(jìn)行聚類，使算法能夠自動(dòng)適應(yīng)空間位置的局部密度變化。武佳薇［6］等通過(guò)考察核心對(duì)象的鄰域平衡性來(lái)有效地排除邊界稀疏噪聲對(duì)象，從而提高聚類精度。儲(chǔ)岳中［7］等利用貝葉斯信息測(cè)度來(lái)優(yōu)化聚類結(jié)果，從而很好地解決了合適的聚類半徑選取問(wèn)題。黎韶光［8］等對(duì)擴(kuò)展空間對(duì)象的聚類進(jìn)行了研究，并提出了相應(yīng)的算法。

綜上所述，對(duì)于簇相連的變密度數(shù)據(jù)集，現(xiàn)有大部分聚類算法要么不支持，要么聚類效果不理想。本文在現(xiàn)有的基于密度的聚類方法的基礎(chǔ)上，引入累積平均密度的概念，設(shè)計(jì)算法時(shí)考量對(duì)象的區(qū)域相似性，使其能夠?qū)Υ叵噙B的變密度數(shù)據(jù)集進(jìn)行有效的聚類分析。

2 DBSCAN算法

DBSCAN算法是基于中心的密度聚類方法，需要兩個(gè)用戶輸入?yún)?shù)：半徑ε和密度閾值Minpts。算法把密度定義為數(shù)據(jù)集中以某個(gè)給定對(duì)象為圓心、以給定ε為半徑的空間區(qū)域中的對(duì)象的個(gè)數(shù)。并通過(guò)給定密度閾值Minpts把對(duì)象劃分為核心對(duì)象、邊界對(duì)象和噪聲對(duì)象。密度不小于Minpts的對(duì)象稱為核心對(duì)象，在至少一個(gè)核心對(duì)象的ε半徑范圍內(nèi)且自身不是核心對(duì)象的對(duì)象稱為邊界對(duì)象，其余的對(duì)象稱為噪聲對(duì)象。算法將一個(gè)聚類定義為一組“密度互連”的對(duì)象的集合。其中密度互連相關(guān)的定義如下：

（1）給定對(duì)象集D，p，q∈D，若p屬于q的ε－鄰域，且q為核心對(duì)象，那么就說(shuō)p從q直接密度可達(dá)。

（2）給定對(duì)象集D，若存在對(duì)象鏈p1，p2，…，pn∈D，p1＝p，pn＝q，對(duì)于pi，若pi＋1從pi直接密度可達(dá)，則稱q從p關(guān)于ε和Minpts密度可達(dá)，其中1≤i≤n。

（3）給定對(duì)象集D，p，q∈D，若存在對(duì)象o，使得對(duì)象p和q都從o關(guān)于ε和Minpts密度可達(dá)，則稱p和q是密度互連的。

DBSCAN算法的主要步驟為：首先從數(shù)據(jù)集中找到一個(gè)未被處理的核心對(duì)象，創(chuàng)建一個(gè)包含該對(duì)象的新類；然后根據(jù)這個(gè)核心對(duì)象，找到從其直接密度可達(dá)的對(duì)象，對(duì)它們?cè)O(shè)置類標(biāo)記，并把它們加入到種子列表；接著，算法對(duì)種子列表中的核心對(duì)象進(jìn)行擴(kuò)展查詢，找到核心對(duì)象的直接密度可達(dá)對(duì)象，將其設(shè)置類標(biāo)記后加入到種子列表，并從種子列表中移除該核心對(duì)象，重復(fù)這個(gè)過(guò)程，直到?jīng)]有新的對(duì)象加入到種子列表，則這個(gè)類的聚類過(guò)程完成。重復(fù)上述步驟，直到?jīng)]有新的對(duì)象加入各個(gè)類時(shí)，整個(gè)聚類過(guò)程結(jié)束。

那些不屬于任何類的對(duì)象被標(biāo)記為噪聲。DBSCAN可以從含有噪聲的數(shù)據(jù)集中發(fā)現(xiàn)任意形狀的聚類。

3 基于累積平均密度的聚類方法

針對(duì)DBSCAN算法的參數(shù)敏感性和不能區(qū)分相連的不同密度的簇等情況，本文提出了一種對(duì)DBSCAN的改進(jìn)算法。算法先按照密度對(duì)數(shù)據(jù)集排序，然后用累積平均密度作為依據(jù)進(jìn)行聚類，提升聚類質(zhì)量。

3.1 累積平均密度有關(guān)概念

假設(shè)數(shù)據(jù)集為D，使用歐氏距離作為距離度量，這里，我們引入一些有關(guān)定義。

定義1 對(duì)象p的ε－鄰域［1］：以p為圓心、ε為半徑的空間區(qū)域，記作Nε（p）。

定義2 對(duì)象p的密度［1］：對(duì)象p的ε－鄰域包含的對(duì)象的個(gè)數(shù)，記作d（p）。

定義3 中心對(duì)象：當(dāng)前未被標(biāo)識(shí)類標(biāo)記的對(duì)象中密度最大的對(duì)象。

在整個(gè)聚類過(guò)程中，中心對(duì)象是階段取值的。取一個(gè)中心對(duì)象，然后進(jìn)行聚類，這個(gè)類的聚類過(guò)程完成后，取下一個(gè)中心對(duì)象，再進(jìn)行聚類，依次進(jìn)行，直至整個(gè)聚類過(guò)程結(jié)束。

定義4 對(duì)象p的累積平均密度：若p未被標(biāo)識(shí)類標(biāo)記，則p的累積平均密度為p的密度；若p已被標(biāo)識(shí)了類標(biāo)記，則p的累積平均密度為該類當(dāng)前所包含的所有對(duì)象密度的算術(shù)平均值。記作c（p），其公式如下：

其中，p1，p2，…，pk是當(dāng)前已被標(biāo)識(shí)了p所在類標(biāo)記的對(duì)象。

由定義可知，累積平均密度在聚類過(guò)程中是不斷變化的，起始時(shí)，它等于中心對(duì)象的密度，然后每加入一個(gè)數(shù)據(jù)對(duì)象到中心對(duì)象所在的類，需要重新計(jì)算一次。

定義5 對(duì)象p對(duì)于對(duì)象q的容納因子：假設(shè)q∈Nε（p），對(duì)象p對(duì)于對(duì)象q的容納因子記作fp（q），公式如下：

表示的是q的密度和對(duì)象p的累積平均密度的相似度，fp（q）值越小，表示兩者越相似，則q可以被容納進(jìn)p所在的類；fp（q）值越大，表示兩者差距越大，則q不能被容納進(jìn)p所在的類。

定義6 核心對(duì)象：給定容納閾值δ＞0，p∈D且p為中心對(duì)象或核心對(duì)象，q∈Nε（p），若fp（q）≤δ且d（p）≥Minpts，則稱q為核心對(duì)象。

顯然，這個(gè)概念的定義是遞歸的，初始時(shí)，只有中心對(duì)象，可以根據(jù)中心對(duì)象找出其鄰域的核心對(duì)象，然后再根據(jù)這些核心對(duì)象尋找到其它核心對(duì)象。

直接密度可達(dá)、密度可達(dá)和密度互連以及聚類的定義與DBSCAN算法中的定義相同。

3.2 算法原理及描述

DBSCAN算法中只設(shè)置了一個(gè)密度下限，然后根據(jù)這個(gè)密度下限來(lái)收集直接密度可達(dá)對(duì)象進(jìn)行聚類。而本文首次提出了累積平均密度的概念，并用它來(lái)考量密度的相似度（通過(guò)容納因子來(lái)反映）。聚類過(guò)程中不但要考慮密度下限，還要考慮密度的相似性，只有密度相似度達(dá)到一定程度的對(duì)象才能聚為一類，降低了聚類的籠統(tǒng)性和隨機(jī)性，增加了聚類的適應(yīng)性和穩(wěn)定性。首先找出密度最大的對(duì)象，然后收集和其密度相似的對(duì)象形成一個(gè)聚類，然后再找出剩下數(shù)據(jù)中密度最大的對(duì)象，重復(fù)上述過(guò)程直到所有數(shù)據(jù)都被歸類，則得到聚類的最終結(jié)果。顯然，對(duì)于相連的不同密度的簇，可以通過(guò)密度相似性把高密度的簇和低密度的簇區(qū)分開(kāi)來(lái)。

算法需要三個(gè)輸入?yún)?shù)：半徑ε、密度閾值Minpts和容納閾值δ。基本步驟如下：

Step 1 計(jì)算數(shù)據(jù)集中各個(gè)數(shù)據(jù)對(duì)象的密度并對(duì)其進(jìn)行排序。

Step 2 確定中心對(duì)象。選取當(dāng)前未被標(biāo)識(shí)類標(biāo)記對(duì)象中密度最大的對(duì)象作為中心對(duì)象p，若p的密度不小于Minpts，則對(duì)其設(shè)置類標(biāo)記并創(chuàng)建一個(gè)包含對(duì)象p的新類；否則聚類結(jié)束。

Step 3 構(gòu)建種子列表。把中心對(duì)象p的直接密度可達(dá)對(duì)象加入種子列表。

Step 4 類擴(kuò)展。對(duì)于種子列表中的對(duì)象q，若滿足條件fp（q）≤δ且d（q）≥Minpts，說(shuō)明對(duì)象q是核心對(duì)象，則應(yīng)對(duì)對(duì)象q設(shè)置類標(biāo)記，把對(duì)象q的直接密度可達(dá)對(duì)象加入種子列表，并從種子列表中移除對(duì)象q；否則，說(shuō)明對(duì)象q不是核心對(duì)象，則應(yīng)把對(duì)象q從種子列表中移除。

Step 5 重復(fù)Step 4直至種子列表為空。表示完成了一個(gè)類的聚類過(guò)程。

Step 6 重復(fù)Step 2～Step 5直至整個(gè)聚類過(guò)程結(jié)束。

需要指出的是，在Step 4中弱化了密度閾值Minpts在合并簇的過(guò)程中的作用，Minpts主要被用來(lái)抑制噪聲，簇的合并更多地依賴于容納因子。在半徑ε相同時(shí)，改進(jìn)算法的密度閾值要比DBSCAN算法中的密度閾值小很多。因此，在某種意義上降低了算法對(duì)輸入?yún)?shù)的敏感性。

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

通過(guò)實(shí)驗(yàn)分析改進(jìn)算法的性能，并與DBSCAN算法進(jìn)行比較。實(shí)驗(yàn)環(huán)境為Windows XP SP2操作系統(tǒng)，Intel（R）Pentium（R）Dual處理器，1GB內(nèi)存，Eclipse 3.7和MATLAB 7.0開(kāi)發(fā)環(huán)境。

4.1 處理時(shí)間

算法運(yùn)行時(shí)間主要集中在以下兩個(gè)步驟：Step 1的初始密度計(jì)算和Step 4的類擴(kuò)展。Step 1的時(shí)間主要由鄰域搜索時(shí)間和密度排序時(shí)間組成，Step 4的時(shí)間主要為鄰域搜索時(shí)間。另外，可以在運(yùn)行Step 1的時(shí)候記錄下相關(guān)數(shù)據(jù)供Step 4使用，做到一次計(jì)算多次查詢，從而省去Step 4中鄰域搜索的時(shí)間消耗。程序中，密度排序采用歸并排序算法實(shí)現(xiàn)，時(shí)間復(fù)雜度為O（nlogn）；鄰域搜索的時(shí)間復(fù)雜度為O（n2）。在不使用空間索引的情況下，DBSCAN算法的時(shí)間復(fù)雜度為O（n2）［9］。因此，改進(jìn)算法和DBSCAN算法相比，在時(shí)間復(fù)雜度上屬于同階，沒(méi)有明顯的差異。

4.2 實(shí)驗(yàn)

為了方便說(shuō)明，我們使用兩個(gè)二維數(shù)據(jù)集來(lái)對(duì)算法進(jìn)行聚類實(shí)驗(yàn)。實(shí)驗(yàn)分為兩步：（1）對(duì)簇不相連的數(shù)據(jù)集進(jìn)行聚類實(shí)驗(yàn)，驗(yàn)證該情況下改進(jìn)算法的正確性；（2）對(duì)簇相連的數(shù)據(jù)集進(jìn)行聚類實(shí)驗(yàn)，驗(yàn)證該情況下改進(jìn)算法對(duì)聚類質(zhì)量的提升。

4.2.1 簇不相連的數(shù)據(jù)集聚類實(shí)驗(yàn)

實(shí)驗(yàn)使用的數(shù)據(jù)集A有1 600條記錄，分為四類，大小和形狀各不相同，并包含有噪聲數(shù)據(jù)。

用改進(jìn)算法對(duì)數(shù)據(jù)集A進(jìn)行聚類，參數(shù)設(shè)置為ε＝0.47，Minpts＝5，δ＝0.17時(shí)，聚類結(jié)果如圖1所示。圖1中，不同的類用不同的灰度顏色表示，散亂的黑色點(diǎn)表示噪聲，可以看出，數(shù)據(jù)集被標(biāo)記為四個(gè)不同形狀和大小的類，噪聲數(shù)據(jù)被有效地識(shí)別，類的數(shù)目和形狀都和數(shù)據(jù)集的先驗(yàn)知識(shí)相吻合，驗(yàn)證了在簇不相連的數(shù)據(jù)集下改進(jìn)算法的正確性。

Figure 1 Clustering result1of dataset A by improved algorithm圖1 改進(jìn)算法對(duì)數(shù)據(jù)集A的聚類結(jié)果1

另外，實(shí)驗(yàn)過(guò)程發(fā)現(xiàn)，在參數(shù)取值為δ＝0.17，Minpts∈［5，9］，ε∈［0.47，0.50］時(shí)，聚類效果都很不錯(cuò)。圖2顯示的是參數(shù)設(shè)置為ε＝0.5，Minpts＝9，δ＝0.17時(shí)的聚類結(jié)果?？梢钥闯?，數(shù)據(jù)集被聚為四類，與圖1中基本一致，表明在一定范圍內(nèi)，參數(shù)的變化對(duì)聚類的結(jié)果影響不大，說(shuō)明改進(jìn)算法在一定程度上降低了參數(shù)敏感性。

Figure 2 Clustering result2of dataset A by improved algorithm圖2 改進(jìn)算法對(duì)數(shù)據(jù)集A的聚類結(jié)果2

4.2.2 簇相連的數(shù)據(jù)集聚類實(shí)驗(yàn)

實(shí)驗(yàn)使用的數(shù)據(jù)集B有5 000條記錄，分為四類，包含有噪聲數(shù)據(jù)，且密度分布不均勻，左邊部分密度最大，右邊部分次之，然后是上邊部分，下邊部分密度最小，并且類之間緊密相連。

用DBSCAN算法對(duì)該數(shù)據(jù)集進(jìn)行聚類，參數(shù)設(shè)置為ε＝0.15，Minpts＝9時(shí)，聚類結(jié)果如圖3所示。從結(jié)果可以看出，數(shù)據(jù)集被聚為一個(gè)類，與先驗(yàn)知識(shí)不符，說(shuō)明對(duì)于簇相連的數(shù)據(jù)集，DBSCAN算法不能達(dá)到很好的聚類效果。

Figure 3 Clustering result of dataset B by DBSCAN algorithm圖3 DBSCAN算法對(duì)數(shù)據(jù)集B的聚類結(jié)果

用改進(jìn)算法對(duì)該數(shù)據(jù)集進(jìn)行聚類，參數(shù)設(shè)置為ε＝0.2，Minpts＝5，δ＝0.2時(shí)，聚類結(jié)果如圖4所示。由結(jié)果可以看出，改進(jìn)算法把數(shù)據(jù)集標(biāo)記為四類，如實(shí)地反映了數(shù)據(jù)集的真實(shí)分布情況，很好地達(dá)到了預(yù)期效果，說(shuō)明對(duì)于簇相連的數(shù)據(jù)集，改進(jìn)算法能夠把相連的簇區(qū)分開(kāi)來(lái)，能提升該情況下聚類的質(zhì)量。

Figure 4 Clustering result of dataset B by improved algorithm圖4 改進(jìn)算法對(duì)數(shù)據(jù)集B聚類結(jié)果

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

本文提出了累積平均密度的概念，并在此基礎(chǔ)上提出了一種基于DBSCAN算法的改進(jìn)算法。實(shí)驗(yàn)表明，改進(jìn)算法具有以下特點(diǎn)：能夠提升對(duì)簇相連數(shù)據(jù)集的聚類質(zhì)量；弱化了密度閾值的作用，在一定程度上降低了參數(shù)敏感性；能夠發(fā)現(xiàn)任意形狀的聚類；能夠有效地處理噪聲數(shù)據(jù)；能夠向高維擴(kuò)展。

本文中的累積平均密度是用算術(shù)平均值來(lái)計(jì)算的，對(duì)簇合并的控制可能不夠精細(xì)，未來(lái)考慮使用方根的算術(shù)平均值等其它方式來(lái)計(jì)算。另外，為了提高對(duì)高維大數(shù)據(jù)集的聚類效率，算法的并行實(shí)施和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)也是下一步的研究方向。

［1］ Zhu Ming.Data mining［M］.Hefei：University of Science and Technology of China Press，2008.（in Chinese）

［2］ Ester M，Kriegel H P，Sander J.A density－based algorithm for discovering clusters in large spatial databases with noise［C］∥Proc of the 2nd International Conference on Knowledge Discovery and Data Mining，1996：226－231.

［3］ Feng Shao－rong，Xiao Wen－jun.A new method to improve the clustering quality of DBSCAN algorithm［J］.Journal of Xi’an Electronic and Science University：Natural Science Edition，2008，35（3）：523－529.（in Chinese）

［4］ Zhou Dong，Liu Peng.VDBSCAN：Variable density based clustering algorithm［J］.Computer engineering and Applications，2009，45（11）：137－141.（in Chinese）

［5］ Li Guang－qiang，Deng Min，Liu Qi－liang，et al.A spatial clustering method adaptive for local density changes［J］.Journal of Surveying and Mapping，2009，38（3）：255－263.（in Chinese）

［6］ Wu Jia－wei，Li Xiong－fei，Sun Tao，et al.A clustering algorithm based on neighborhood density balanced［J］.Journal of Computer Research and Development，2010，47（6）：1044－1052.（in Chinese）

［7］ Chu Yue－zhong，Xu Bo.Research on the optimization of clustering algorithm based on dynamic nearest neighbor［J］.Computer Engineering and Design，2011，32（5）：1687－1690.（in Chinese）

［8］ Li Shao－guang，Zhou Ju－suo，Xie Yu－bo，et al.An extended object oriented spatial density clustering algorithm［J］.Computer Engineering and Applications，2011，47（13）：166－168.（in Chinese）

［9］ Han Jia－wei，Kamber M.Data mining：Concepts and techniques［M］.Translated by Fan Ming，Meng Xiao－feng.Beijing：China Machine Press，2007.（in Chinese）

［10］ Hinneburg A，Keim D A.An efficient approach to clustering in large multimedia databases with noise［C］∥Proc of the 4th International Conference on Knowledge Discovery and Data mining，1998：58－65.

［11］ Liu Qing－bao，Deng Su，Zhang Wei－ming.Relative density based clustering algorithm［J］.Computer Science，2007，34（2）：192－195.（in Chinese）

［12］ Chen Zhi－ping，Wang Lei，Li Zhi－cheng.Research of clustering algorithm based on density gradient［J］.Computer Application，2006（10）：2389－2392.（in Chinese）

［13］ Qiu Bao－zhi，Xu Min.Research of non parameter clustering boundary detection algorithm［J］.Computer Engineering，2011，37（15）：23－26.（in Chinese）

附中文參考文獻(xiàn)：

［1］ 朱明.數(shù)據(jù)挖掘［M］.合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2008.

［3］ 馮少榮，肖文俊.一種提高DBSCAN聚類算法質(zhì)量的新方法［J］.西安電子科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，35（3）：523－529.

［4］ 周董，劉鵬.VDBSCAN：變密度聚類算法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（11）：137－141.

［5］ 李光強(qiáng)，鄧敏，劉啟亮，等.一種適應(yīng)局部密度變化的空間聚類方法［J］.測(cè)繪學(xué)報(bào)，2009，38（3）：255－263.

［6］ 武佳薇，李雄飛，孫濤，等.鄰域平衡密度聚類算法［J］.計(jì)算機(jī)研究與發(fā)展，2010，47（6）：1044－1052.

［7］ 儲(chǔ)岳中，徐波.動(dòng)態(tài)最近鄰聚類算法的優(yōu)化研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2011，32（5）：1687－1690.

［8］ 黎韶光，周巨鎖，謝玉波，等.一種面向擴(kuò)展空間對(duì)象的密度聚類算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（13）：166－168.

［9］ 韓家煒，坎伯.數(shù)據(jù)挖掘概念與技術(shù)［M］.范明，孟小峰，譯.北京：機(jī)械工業(yè)出版社，2007.

［11］ 劉青寶，鄧蘇，張維明.基于相對(duì)密度的聚類算法［J］.計(jì)算機(jī)科學(xué)，2007，34（2）：192－195.

［12］ 陳治平，王雷，李志成.基于密度梯度的聚類算法研究［J］.計(jì)算機(jī)應(yīng)用，2006（10）：2389－2392.

［13］ 邱保志，許敏.無(wú)參數(shù)聚類邊界檢測(cè)算法的研究［J］.計(jì)算機(jī)工程，2011，37（15）：23－26.