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

　　3 算法性能及分析

　　對(duì)M-DBSCAN算法的性能作了測(cè)試，并與DBSCAN作了比較。所有的測(cè)試都在1臺(tái)PC機(jī)上進(jìn)行，配置P4，2.0 GHz CPU，512 MB內(nèi)存，80 GB硬盤，算法用Matlab7.3實(shí)現(xiàn)。

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

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

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

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