一種基于密度的聚類的算法

　　3 算法性能及分析

　　對M-DBSCAN算法的性能作了測試，并與DBSCAN作了比較。所有的測試都在1臺PC機上進行，配置P4，2.0 GHz CPU，512 MB內存，80 GB硬盤，算法用Matlab7.3實現。

　　首先用構造的模擬數據對聚類結果進行驗證。圖2為DBSCAN算法在閾值半徑為20時得到的結果，明顯地將不同的三類作為一類輸出，形成了錯誤的類劃分；而在取同樣的初始閾值半徑時，圖3可以看出M-DBSCAN算法得到更好的聚類結果。

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

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

　　本文討論了一種將DBSCAN聚類算法進行改進的M-DBSCAN聚類算法，它克服了DBSCAN聚類算法不能處理大數據集的問題，并實現可以對閾值進行實時更改。試驗結果顯示，M-DBSCAN算法的準確性比DBSCAN算法要好，處理大數據集的速度更快。但是對于聚類數目的確定仍然是判斷是否超過某閾值才可算作某一類的標準，聚類數目與閾值的選擇有很大關系。因此如何自動確定聚類數目將是下一步工作的方向。