密度型空間分群演算法 是什麼？

DBSCAN：密度型空間分群演算法 的完整解釋

密度型空間分群演算法（Density-Based Spatial Clustering of Applications with Noise, DBSCAN）是一種基於資料點鄰域密度進行分群的演算法，

核心概念

DBSCAN 基於一個直觀的假設：真實世界的群組是由高密度區域組成，群組之間以低密度區域分隔。演算法使用兩個超參數定義「密集」：

• ε（epsilon）：鄰域半徑，決定多近才算「鄰居」
• minPts：最小樣本數，決定多少鄰居才能形成核心

資料點依此分為三類：

1. 核心點（Core Point）：以 ε 為半徑的圓內包含至少 minPts 個點（含自身）
2. 邊界點（Border Point）：在某核心點的鄰域內，但自身鄰域內點數不足 minPts
3. 雜訊點（Noise Point）：不在任何核心點的鄰域內的孤立點

運作原理

演算法步驟

1. 對每個未被標記的點，計算其 ε 鄰域內的點數
2. 若點數 ≥ minPts，標記為核心點，建立一個新群組
3. 遞迴地將所有從核心點「密度可達（Density-Reachable）」的點加入同一群組
4. 重複直到所有點都被標記為某個群組的成員或雜訊點

密度可達性

DBSCAN 定義了一個重要的傳遞性概念：點 A 從點 B 密度可達，若 B 是核心點且 A 在 B 的 ε 鄰域內。密度連通性則要求兩點都從同一個核心點密度可達，確保群組內部的連通性。

時間複雜度

若使用空間索引結構（如 KD-Tree 或 Ball Tree），DBSCAN 的時間複雜度為 O(n log n)；若使用暴力搜尋，則為 O(n²)。在高維空間中，由於維度詛咒（Curse of Dimensionality），距離計算變得不再可靠，DBSCAN 的效能會顯著下降。

實際應用

地理空間分析

DBSCAN 非常適合分析 GPS 軌跡資料，例如識別城市中的熱門聚集地點（商圈、交通樞紐），或偵測交通事故高發區域。地理資料天然存在不規則形狀的群組和雜訊點（錯誤 GPS 信號），恰好符合 DBSCAN 的假設。

異常偵測

DBSCAN 將不屬於任何密集群組的點標記為雜訊，這些雜訊點在異常偵測場景中即代表潛在的異常事件。例如，在網路安全中偵測異常流量模式，或在製造業中識別感測器數據中的異常讀值。

影像處理

DBSCAN 可用於影像中的物件偵測前處理，將影像像素依顏色或紋理特徵分群，識別出具有相似特性的連續區域。

使用者行為分析

電商平台可用 DBSCAN 對使用者行為序列進行分群，發現自然形成的用戶群體，而無需預先假設用戶分成幾群。

常見誤區

誤區一：ε 和 minPts 容易設定

DBSCAN 的效能對參數選擇高度敏感。ε 過大會合併多個真實群組，ε 過小則會破壞密集群組。實務上常用 k-Distance Graph（計算每個點到第 k 近鄰的距離並排序）來尋找合適的 ε：圖形中的「肘部（Elbow）」通常是 ε 的好選擇。

誤區二：DBSCAN 不受資料縮放影響

ε 是基於歐氏距離的絕對值，因此特徵縮放直接影響分群結果。在運行 DBSCAN 前，MUST 對特徵進行標準化（Standardization）或正規化（Normalization），否則量綱差異大的特徵會主導距離計算。

誤區三：DBSCAN 適用於所有維度的資料

在高維空間（特徵數 > 20）中，所有點之間的距離趨於相似，ε 鄰域的概念失去意義。此時應先進行降維（PCA、UMAP 等），再套用 DBSCAN。

與相關技術的比較

常見問題