DBSCAN

DBSCAN 可以話係最多人用嘅基於密度聚類法之一，係Density-based spatial clustering of applications with noise嘅縮寫，喺1996年由Martin Ester、Hans-Peter Kriegel、Jörg Sander 同 Xiaowei Xu 提出。

步驟

步驟如下：

• 想像有一點 $\mathbf {x} _{i}$，如果佢周圍半徑 $r$ 嘅範圍內超過咗 ${\text{minPts}}$ 咁多點，噉佢就算係核心點（core）；
• 想像有兩點 $\mathbf {x} _{1}$ 同 $\mathbf {x} _{2}$，如果 $\left\|\mathbf {x} _{2}-\mathbf {x} _{1}\right\|$（兩點之間嘅距離） $\leq r$，噉 $\mathbf {x} _{2}$ 算係可以由 $\mathbf {x} _{1}$ 直接去到（directly reachable from $\mathbf {x} _{1}$）；順帶一提，$\mathbf {x} _{1}$ 一定要係核心點。
• 想像有兩點 $\mathbf {x} _{1}$ 同 $\mathbf {x} _{3}$，如果有條路徑 $\mathbf {x} _{j_{1}},\mathbf {x} _{j_{2}}\ldots \mathbf {x} _{j_{f}}$，當中 $\mathbf {x} _{j_{1}}=\mathbf {x} _{1}$ 而且 $\mathbf {x} _{j_{f}}=\mathbf {x} _{3}$，期間每點（$\mathbf {x} _{j_{2}}$ 等）都可以由打前嗰點直接去到嘅，噉 $\mathbf {x} _{3}$ 算係可以由 $\mathbf {x} _{1}$ 去到（reachable from $\mathbf {x} _{1}$）；
• 所有「唔能夠由第啲點度去到」嘅點，冚唪唥當係雜訊。

如果 $\mathbf {x} _{n}$ 係核心點，噉佢同所有由佢度去到嘅點成一個聚類。

用圖像表示嘅話，可以想像下圖：下圖 ${\text{minPts}}=4$，A 等嘅紅色點全部都係核心點，因為佢哋全部都有「周圍 $r$ 咁遠嘅範圍（啲圓圈）內有超過 ${\text{minPts}}$ 咁多點」呢種特性，黃色點 B 同 C 唔係核心點，但可以由 A 去到，於是啲紅色點加埋 B 同 C，就成一個聚類；藍色點 N 唔能夠由任何一點度去到，所以當係雜訊忽視。

睇埋

• 聚類分析