一種基于密度的聚類的算法
2.2 改進(jìn)的算法
DBSCAN算法在對類的劃分時(shí)采用的方法是:比較此數(shù)據(jù)點(diǎn)到各類中心的距離,若小于某閾值,則屬于此類??梢婇撝档倪x擇直接影響類的劃分及類的數(shù)目。但是如圖1所產(chǎn)生的聚類模塊[3]所示,這種方法帶來的問題就是:距離近的不一定屬于同一類,在閾值半徑內(nèi)的不一定屬于同一類。
針對此問題,本文提出一種改進(jìn)的算法M-DBSCAN。首先實(shí)現(xiàn)在線聚類,可以動態(tài)調(diào)整聚類的數(shù)目;之后,通過將數(shù)據(jù)點(diǎn)到類的平均距離與類內(nèi)平均距離以及新半徑與原半徑作比較進(jìn)行雙重判決,確定數(shù)據(jù)點(diǎn)是否可以加入此類中,以實(shí)時(shí)調(diào)整閾值半徑,解決了類劃分錯誤的問題。
改進(jìn)后整個算法描述如下:
?。?)積累一小段時(shí)間內(nèi)的數(shù)據(jù),得到相似度矩陣
?。?)給定閾值dthr,找出鄰域密度最大的數(shù)據(jù)點(diǎn)作為第一個初始類的中心c1,計(jì)算S中每行值大于dthr的個數(shù),個數(shù)最多的行號即為第一個類的中心,將第一類中的數(shù)據(jù)點(diǎn)存放到矩陣S’(n×n+2)的第一行,每行中的第一個為類中心,計(jì)算類的平均半徑r,同時(shí)計(jì)算此類的平均距離d2,放到最后兩位。
?。?)對尚未加入的數(shù)據(jù)點(diǎn),計(jì)算某一個數(shù)據(jù)點(diǎn)到類c1中的所有點(diǎn)的平均距離d1,類的平均距離d2;
若d1d2,則判斷加入此數(shù)據(jù)后類的半徑是否變大;如果變小,將數(shù)據(jù)點(diǎn)加入此類,同時(shí)改變此類的平均半徑;否則尋找下一個聚類,計(jì)算同上。
如果不能加入到任何一個已有聚類,則創(chuàng)建一個新的類,將其存入S’中。
評論