摘 要： 基于密度的聚類是聚類算法中的一種，其主要優(yōu)點(diǎn)是可以發(fā)現(xiàn)任意形狀的簇，但處理大數(shù)據(jù)集時效果不佳，為此提出了一種改進(jìn)的算法M-DBSCAN，保留了基于密度聚類算法的優(yōu)點(diǎn)，同時克服了以往算法不能處理大數(shù)據(jù)集的缺點(diǎn)。實驗結(jié)果證明，M-DBSCAN聚類算法在聚類質(zhì)量及速度上都比原DBSCAN有較大提高。
關(guān)鍵詞： 聚類； DBSCAN算法； 在線聚類

　　聚類就是把相似的東西歸為一類，有明顯區(qū)別的事物分屬在不同的類別中，方便處理的一種數(shù)據(jù)挖掘的方法。目前，它已成為數(shù)據(jù)挖掘研究領(lǐng)域中一個非?；钴S的研究方向。聚類分析技術(shù)在模式識別、數(shù)據(jù)分析、圖像處理和市場研究等許多領(lǐng)域得到了廣泛的應(yīng)用。
　　迄今為止，人們提出了許多聚類分析的算法，其中基于密度的聚類算法能夠發(fā)現(xiàn)任意形狀的簇，應(yīng)用較為廣泛。其主要思想是:只要臨近區(qū)域的密度(對象或數(shù)據(jù)點(diǎn)的數(shù)目)超過某個閾值就繼續(xù)聚類。也就是說，對給定類中的每個數(shù)據(jù)點(diǎn)，在一個給定范圍的區(qū)域中必須至少包含某個數(shù)目的點(diǎn)。這樣的方法可以用來過濾噪聲和孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的類。
　　基于密度的聚類算法主要有：DBSCAN（Density Based Spatial Clustering of Applications with Noise），OPTICS（Ordering Points to Identify the Clustering Structure）等。DBSCAN算法利用類的高密度連通性可以快速發(fā)現(xiàn)任意形狀的類，但是當(dāng)處理的數(shù)據(jù)量較大時，一般的聚類算法不能滿足在線聚類這一特點(diǎn)，計算復(fù)雜度高，速度慢。針對此問題本文提出了一種改進(jìn)的M-DBSCAN（Modified-DBSCAN）算法，改善了DBSCAN存在的不足，而且對處理大量數(shù)據(jù)有較好的效果。
1 DBSCAN算法
　　MARTIN E等人提出的DBSCAN算法將具有足夠高密度的區(qū)域劃分為一類，并可以在帶有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類[1]。
　　DBSCAN算法提出了一些新的定義：

　　DBSCAN算法是基于密度的聚類算法，它將類看作是數(shù)據(jù)空間中被低密度區(qū)域分割開的高密度對象區(qū)域。在該算法中，發(fā)現(xiàn)一個聚類的過程是基于這樣的事實：一個聚類能夠被其中的任意一個核心對象所確定。其基本思想是：考察數(shù)據(jù)庫D中的某一個點(diǎn)P，若P是核心點(diǎn)，則通過區(qū)域查詢得到該點(diǎn)的鄰域，鄰域中的點(diǎn)和P同屬于一個類，這些點(diǎn)將作為下一輪的考察對象(即種子點(diǎn))，并通過不斷地對種子點(diǎn)進(jìn)行區(qū)域查詢來擴(kuò)展它們所在的類，直至找到一個完整的類。然后，依此過程尋找其他的類。最后剩下的不屬于任何類的點(diǎn)即為噪聲。DBSCAN算法可以挖掘任意形狀的聚類，對數(shù)據(jù)輸入順序不敏感，并且具有處理異常數(shù)據(jù)(噪音)的能力。對具有N個樣本的數(shù)據(jù)庫，該算法的時間復(fù)雜性為O(NlogN)。
2 M-DBSCAN算法
2.1 在線聚類
　　由于處理數(shù)據(jù)量較大，一次性處理完畢不但運(yùn)算量大，復(fù)雜度高，而且對存儲空間的需求量大，因此本文提出一種在線式聚類算法，可以動態(tài)增加聚類數(shù)目。
　　算法的原理是：隨著輸入樣本數(shù)據(jù)的不斷增加，實時動態(tài)地增加聚類個數(shù)或調(diào)整聚類中心及聚類半徑，在形成的任意一個聚類中，聚類中心與屬于此聚類的樣本點(diǎn)的相似度都不小于一個閾值dthr，dthr的選取將直接影響到聚類數(shù)目。
　　將在線式聚類算法引入后，算法的描述如下：
　　(1)積累一小段時間內(nèi)的數(shù)據(jù)，進(jìn)行歸一化壓縮，進(jìn)行相似度計算，得到相似度矩陣；
　　(2)通過對相似度矩陣進(jìn)行比較分析，找出鄰域密度最大的數(shù)據(jù)點(diǎn)作為第一個初始類的中心c₁；
　　(3)對尚未加入此類的數(shù)據(jù)點(diǎn)x_i，比較與類中心的距離是否大于給定閾值dthr，若是，則加入此類，否則創(chuàng)建一個新類c_j；
　　(4)處理完這一小段數(shù)據(jù)后，對新到來的一個數(shù)據(jù)點(diǎn)進(jìn)行與(3)相同的做法，確定其類別；
　　(5)直到?jīng)]有數(shù)據(jù)到來為止，輸出聚類結(jié)果。
2.2 改進(jìn)的算法
　　DBSCAN算法在對類的劃分時采用的方法是：比較此數(shù)據(jù)點(diǎn)到各類中心的距離，若小于某閾值，則屬于此類?？梢婇撝档倪x擇直接影響類的劃分及類的數(shù)目。但是如圖1所產(chǎn)生的聚類模塊[3]所示，這種方法帶來的問題就是：距離近的不一定屬于同一類，在閾值半徑內(nèi)的不一定屬于同一類。

　　針對此問題,本文提出一種改進(jìn)的算法M-DBSCAN。首先實現(xiàn)在線聚類，可以動態(tài)調(diào)整聚類的數(shù)目；之后，通過將數(shù)據(jù)點(diǎn)到類的平均距離與類內(nèi)平均距離以及新半徑與原半徑作比較進(jìn)行雙重判決，確定數(shù)據(jù)點(diǎn)是否可以加入此類中，以實時調(diào)整閾值半徑，解決了類劃分錯誤的問題。
　　改進(jìn)后整個算法描述如下：
　　(1)積累一小段時間內(nèi)的數(shù)據(jù)，得到相似度矩陣
　　　

　　(2)給定閾值dthr，找出鄰域密度最大的數(shù)據(jù)點(diǎn)作為第一個初始類的中心c1，計算S中每行值大于dthr的個數(shù)，個數(shù)最多的行號即為第一個類的中心，將第一類中的數(shù)據(jù)點(diǎn)存放到矩陣S’(n×n+2)的第一行，每行中的第一個為類中心，計算類的平均半徑r，同時計算此類的平均距離d₂，放到最后兩位。
　　(3)對尚未加入的數(shù)據(jù)點(diǎn)，計算某一個數(shù)據(jù)點(diǎn)到類c1中的所有點(diǎn)的平均距離d₁，類的平均距離d₂；
若d₁<d₂，則判斷加入此數(shù)據(jù)后類的半徑是否變大；如果變小，將數(shù)據(jù)點(diǎn)加入此類，同時改變此類的平均半徑；否則尋找下一個聚類，計算同上。
　　如果不能加入到任何一個已有聚類，則創(chuàng)建一個新的類，將其存入S’中。直到?jīng)]有新數(shù)據(jù)到來，算法結(jié)束。
　　部分偽代碼：
　　Cluster M-DBSCAN()
　　{
  　　　Initialize S(n×n),dthr;
  　　　For i=1:n
   　　　　　If S(i,j)>=dthr
    　　　　　　　sum(i)++;
    　　　　　　　count(i,j)=j;
    　　　　　　　j++;
　　　 end
　　end
　　sort(sum(:));
　　S’(1,:)=count(,:);
　　S’(1,n+1)=meanradius;
　　S’(1,n+2)=meandistance2;
　　If meandistance1<meandistance2
　　　　  If meanradiusnew<meanradius
　　　　　   Add xj to S’(1);
　　　　　   S’(1,n+1)=new meanradius;
　　Else
  　　　　Next class;
　　End
　　If no class
　　　　　  Create a new class S’(2);
　　End
　　…
　　Until no data come
　　　　　It’s over
　　Output S’
　　}
3 算法性能及分析
　　對M-DBSCAN算法的性能作了測試，并與DBSCAN作了比較。所有的測試都在1臺PC機(jī)上進(jìn)行,配置P4，2.0 GHz CPU，512 MB內(nèi)存，80 GB硬盤,算法用Matlab7.3實現(xiàn)。
　　測試數(shù)據(jù)集同時使用了真實數(shù)據(jù)和自行構(gòu)造的模擬數(shù)據(jù)，真實數(shù)據(jù)采用SEQUOIA 2000數(shù)據(jù)庫，該數(shù)據(jù)庫也被參考文獻(xiàn)[4]用于對算法的性能測試。
　　首先用構(gòu)造的模擬數(shù)據(jù)對聚類結(jié)果進(jìn)行驗證。圖2為DBSCAN算法在閾值半徑為20時得到的結(jié)果，明顯地將不同的三類作為一類輸出，形成了錯誤的類劃分；而在取同樣的初始閾值半徑時，圖3可以看出M-DBSCAN算法得到更好的聚類結(jié)果。

　　從圖4中可以看到兩種算法在SEQUOIA 2000數(shù)據(jù)庫上對不同數(shù)據(jù)量樣本的執(zhí)行時間的比較。算法M-DBSCAN比算法DBSCAN快得多，且隨著數(shù)據(jù)量的不斷增大，這種速度上的差別越來越大。表1為兩種算法的錯誤率比較圖，錯誤率為，N₁為算法所得聚類數(shù)目，N₂為實際聚類數(shù)目。表1中可看出,改進(jìn)的M-DBSCAN算法錯誤概率普遍要小于DBSCAN的，表明改進(jìn)后的算法減小了錯誤率,對處理大樣本集有較好的性能。

　　表2中的測試數(shù)據(jù)集來自Dr．JSrg Sander提供的仿照DBSCAN 中DataBase2生成的數(shù)據(jù)集DB2[8]。由表中可以看出，當(dāng)數(shù)據(jù)規(guī)模為50 000時，雖然SGDO[7]處理噪音點(diǎn)的能力比M-DBSCAN強(qiáng)，但是從錯誤率和運(yùn)行時間上M-DBSCAN比前兩者都有較大的改善。CURD[6]雖然有較短的運(yùn)行時間，但是存在大量的噪音點(diǎn)，所以從綜合性能上比較M-DBSCAN更加完善，聚類質(zhì)量更高。

　　本文討論了一種將DBSCAN聚類算法進(jìn)行改進(jìn)的M-DBSCAN聚類算法，它克服了DBSCAN聚類算法不能處理大數(shù)據(jù)集的問題，并實現(xiàn)可以對閾值進(jìn)行實時更改。試驗結(jié)果顯示，M-DBSCAN算法的準(zhǔn)確性比DBSCAN算法要好，處理大數(shù)據(jù)集的速度更快。但是對于聚類數(shù)目的確定仍然是判斷是否超過某閾值才可算作某一類的標(biāo)準(zhǔn)，聚類數(shù)目與閾值的選擇有很大關(guān)系。因此如何自動確定聚類數(shù)目將是下一步工作的方向。
參考文獻(xiàn)
[1] ESTER M，KRIEGEL H P，SANDER J，et a1． A densitybased algorithm for discovering cluster in large spatial databases  with noise[A]． In：SIMOUDIS E，HAN J， FAYYAD U． Proeeedins of the 2nd  International Conference Knowledge Discovering in Databases and Data Mining  (KDD-96)[C]．Massachusetts：AAAI Press．1996:226-232．
[2] HAN Jia Wei，KAMBER M． Data mining，ovncepts and Techniques[M]．CA：Morgan Kaufmann Publishers，2000．
[3] 朱蔚恒，印鑒，謝益煌．基于數(shù)據(jù)流的任意形狀聚類算法[J]．軟件學(xué)報，2006，17(3)：379-386．
[4] 忻凌，倪志偉，黃玲.基于數(shù)據(jù)流的BIRCH改進(jìn)聚類算法[J].計算機(jī)工程與應(yīng)用，2007，43（5）：121-123
[5]  田地，王世卿.數(shù)據(jù)挖掘中基于密度和距離聚類算法設(shè)計[J].計算機(jī)技術(shù)與發(fā)展，2006，16（10）：254-257.
[6]  陳燕，耿國華，鄭建國.一種改進(jìn)的基于密度的聚類算法.微機(jī)發(fā)展，2005，15(3).
[7]  王翠茹，朵春紅.一種改進(jìn)的基于密度的DBSCAN聚類算法.廣西師范大學(xué)學(xué)報：自然科學(xué)版，2007，25（4）.
[8]  周水庚，周傲英，曹晶． 基于數(shù)據(jù)分區(qū)的DBSCAN算法[J]．計算機(jī)研究與發(fā)展，2000，37(10)：1153-1159.