什麼是DBSCAN？

DBSCAN代表基於密度的應用空間聚類演算法(Density-Based Spatial Clustering of Applications with Noise)。它是一種基於密度的聚類演算法。該演算法將具有足夠高密度的區域增長為簇，並在包含噪聲的空間資料庫中找到任意結構的簇。它將簇表示為密度連線點的最大組。

基於密度的聚類概念包括以下一些新的定義：

• 給定物件的半徑為ε的鄰域稱為該物件的ε鄰域。

• 如果物件的ε鄰域包含至少最小數量MinPts的物件，則該物件被稱為核心物件。

• 給定一組物件D，如果p在q的ε鄰域內，且q是核心物件，則可以說物件p可由物件q直接密度可達。

• 在一組物件D中，如果存在物件鏈p₁,..., p_n，其中p₁ = q且p_n = p，並且p_i+1關於ε和MinPts可由p_i直接密度可達（1 ≤ i ≤ n），p_i ε D，則物件p關於ε和MinPts可由物件q密度可達。

• 在一組物件D中，如果存在物件o ε D，使得p和q都關於ε和MinPts可由o密度可達，則物件p與物件q關於ε和MinPts密度連線。

密度可達性是直接密度可達性的傳遞閉包，這種連線是不對稱的。只有核心物件是相互密度可達的。密度連線是對稱關係。

基於密度的簇是一組關於密度可達性是最大的密度連線的物件。每個不包含在任何簇中的物件都被視為噪聲。

DBSCAN透過測試資料庫中每個點的ε鄰域來搜尋簇。如果一個點p的ε鄰域包含超過MinPts個點，則建立一個以p為核心物件的新簇。DBSCAN重複地從這些核心物件中收集直接密度可達的物件，這可能包含幾個密度可達簇的合併。當沒有新的點可以插入到任何簇中時，該過程結束。

如果使用空間索引，DBSCAN的計算複雜度為O(nlogn)，其中n是資料庫物件的個數。否則，為O(n²)。透過適當設定使用者指定的引數ε和MinPts，該演算法能夠有效地發現任意形狀的簇。

Ginni

更新於：2022年2月16日

5K+ 瀏覽量

開啟你的職業生涯

完成課程獲得認證

開始學習