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

　　2.2 改進的算法

　　DBSCAN算法在對類的劃分時采用的方法是：比較此數(shù)據(jù)點到各類中心的距離，若小于某閾值，則屬于此類?？梢婇撝档倪x擇直接影響類的劃分及類的數(shù)目。但是如圖1所產(chǎn)生的聚類模塊[3]所示，這種方法帶來的問題就是：距離近的不一定屬于同一類，在閾值半徑內(nèi)的不一定屬于同一類。

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

　　改進后整個算法描述如下：

　?。?）積累一小段時間內(nèi)的數(shù)據(jù)，得到相似度矩陣

　?。?）給定閾值dthr，找出鄰域密度最大的數(shù)據(jù)點作為第一個初始類的中心c1，計算S中每行值大于dthr的個數(shù)，個數(shù)最多的行號即為第一個類的中心，將第一類中的數(shù)據(jù)點存放到矩陣S’（n×n+2）的第一行，每行中的第一個為類中心，計算類的平均半徑r，同時計算此類的平均距離d2，放到最后兩位。

　?。?）對尚未加入的數(shù)據(jù)點，計算某一個數(shù)據(jù)點到類c1中的所有點的平均距離d1，類的平均距離d2；

　　若d1d2，則判斷加入此數(shù)據(jù)后類的半徑是否變大；如果變小，將數(shù)據(jù)點加入此類，同時改變此類的平均半徑；否則尋找下一個聚類，計算同上。

　　如果不能加入到任何一個已有聚類，則創(chuàng)建一個新的類，將其存入S’中。