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

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

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

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

　　(2)給定閾值dthr，找出鄰域密度最大的數據點作為第一個初始類的中心c1，計算S中每行值大于dthr的個數，個數最多的行號即為第一個類的中心，將第一類中的數據點存放到矩陣S’(n×n+2)的第一行，每行中的第一個為類中心，計算類的平均半徑r，同時計算此類的平均距離d₂，放到最后兩位。
　　(3)對尚未加入的數據點，計算某一個數據點到類c1中的所有點的平均距離d₁，類的平均距離d₂；
若d₁<d₂，則判斷加入此數據后類的半徑是否變大；如果變小，將數據點加入此類，同時改變此類的平均半徑；否則尋找下一個聚類，計算同上。
　　如果不能加入到任何一個已有聚類，則創建一個新的類，將其存入S’中。直到沒有新數據到來，算法結束。
　　部分偽代碼：
　　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機上進行,配置P4，2.0 GHz CPU，512 MB內存，80 GB硬盤,算法用Matlab7.3實現。
　　測試數據集同時使用了真實數據和自行構造的模擬數據，真實數據采用SEQUOIA 2000數據庫，該數據庫也被參考文獻[4]用于對算法的性能測試。
　　首先用構造的模擬數據對聚類結果進行驗證。圖2為DBSCAN算法在閾值半徑為20時得到的結果，明顯地將不同的三類作為一類輸出，形成了錯誤的類劃分；而在取同樣的初始閾值半徑時，圖3可以看出M-DBSCAN算法得到更好的聚類結果。

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

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

　　本文討論了一種將DBSCAN聚類算法進行改進的M-DBSCAN聚類算法，它克服了DBSCAN聚類算法不能處理大數據集的問題，并實現可以對閾值進行實時更改。試驗結果顯示，M-DBSCAN算法的準確性比DBSCAN算法要好，處理大數據集的速度更快。但是對于聚類數目的確定仍然是判斷是否超過某閾值才可算作某一類的標準，聚類數目與閾值的選擇有很大關系。因此如何自動確定聚類數目將是下一步工作的方向。
參考文獻
[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] 朱蔚恒，印鑒，謝益煌．基于數據流的任意形狀聚類算法[J]．軟件學報，2006，17(3)：379-386．
[4] 忻凌，倪志偉，黃玲.基于數據流的BIRCH改進聚類算法[J].計算機工程與應用，2007，43（5）：121-123
[5]  田地，王世卿.數據挖掘中基于密度和距離聚類算法設計[J].計算機技術與發展，2006，16（10）：254-257.
[6]  陳燕，耿國華，鄭建國.一種改進的基于密度的聚類算法.微機發展，2005，15(3).
[7]  王翠茹，朵春紅.一種改進的基于密度的DBSCAN聚類算法.廣西師范大學學報：自然科學版，2007，25（4）.
[8]  周水庚，周傲英，曹晶． 基于數據分區的DBSCAN算法[J]．計算機研究與發展，2000，37(10)：1153-1159.