考慮一種情況, 點的分佈不均勻, 形狀不規則時, Kmeans 演算法及層次聚類演算法將面臨失效的風險。
如下坐標系:
圖 5. DBSCAN 演算法舉例
我們可以看到上面的點密度不均勻,
設定掃描半徑 Eps, 並規定掃描半徑內的密度值。 若當前點的半徑範圍內密度大於等於設定密度值, 則設置當前點為核心點;若某點剛好在某核心點的半徑邊緣上, 則設定此點為邊界點;若某點既不是核心點又不是邊界點, 則此點為雜訊點。
刪除雜訊點。
將距離在掃描半徑內的所有核心點賦予邊進行連通。
每組連通的核心點標記為一個簇。
將所有邊界點指定到與之對應的核心點的簇總。
演算法過程舉例如上圖坐標系所示, 我們設定掃描半徑 Eps 為 1.5, 密度閾值 threshold 為 3, 則通過上述演算法過程, 我們可以得到下圖:
圖 6. DBSCAN 演算法舉例結果示例
通過計算各個點之間的歐式距離及其所在掃描半徑內的密度值來判斷這些點屬於核心點, 邊界點或是雜訊點。 因為我們設定了掃描半徑為 1.5, 密度閾值為 3, 所以:
P0 點為邊界點, 因為在以其為中心的掃描半徑內只有兩個點 P0 和 P1;
P1 點為核心點, 因為在以其為中心的掃描半徑內有四個點 P0,P1,P2,P4 ;
P8 為雜訊點, 因為其既非核心點, 也非邊界點;
其他點依次類推。