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

胡博磊，譚建豪

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

1 引言

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

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

2 DBSCAN算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 算法原理及描述

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

算法需要三個輸入?yún)?shù)：半徑ε、密度閾值Minpts和容納閾值δ?；静襟E如下：

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

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

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

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

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

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

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

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

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

4.1 處理時間

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

4.2 實(shí)驗

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

［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］.合肥：中國科學(xué)技術(shù)大學(xué)出版社，2008.

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

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

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

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

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

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

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

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

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

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