📂機械学習

DBSCAN: 密度に基づくクラスタリング

アルゴリズム ¹

DBSCAN^{Density-Based Spatial Clustering of Applications with Noise}は 距離空間 $\left( X , d \right)$ における点の密度に基づいて クラスタリング を行うアルゴリズムだ。二つの ハイパーパラメータ である半径^radius $\varepsilon > 0$ と密度の基準となる最小点数^{minimal number of points} $m$ が与えられる。

1. 有限集合 $D \subset X$ を データベース^databaseと呼ぶ。
2. $p \in D$ に対して $N_{\varepsilon} \left( p \right) = \left\{ q \in X \mid d \left( p , q \right) \le \varepsilon \right\}$ を $p$ の 近傍^neighborhoodと呼ぶ。
3. $p \in D$ が $| N_{\varepsilon} \left( p \right) | \ge m$ を満たすなら $p$ を コア点^{core point}と呼ぶ。
4. $p \in D$ がコア点でないが、$N_{\varepsilon} \left( p \right)$ が他のコア点を含むなら $p$ を 境界点^{border point}と呼ぶ。
5. コア点 $q$ に対して $p \in N_{\varepsilon} \left( q \right)$ であれば $q$ は $p$ に 直接到達可能^{directly reachable}であるという。 $$ p = p_{1} , \cdots , p_{n} = q $$ 上のように $p_{k}$ が $p_{k+1}$ に直接到達可能であり $p = p_{1}$ かつ $q = p_{n}$ な シーケンス が存在すれば $p$ は $q$ に 到達可能^reachableであるという。
6. 二つの $p , q \in D$ に到達可能なコア点 $o \in D$ が存在すれば $p$ と $q$ は 連結^connectedしているという。
7. 空集合 でない $C \subseteq D$ の全ての $\forall p, q \in C$ が次の二条件を満たすなら クラスタ^clusterと呼ぶ。
   • (i) 最大性: もし $p$ から $q$ へ到達可能なら、$q \in C$ である。
   • (ii) 連結性: $p$ と $q$ は連結している。
8. どのクラスタにも属さない点を ノイズ^noiseと呼ぶ。

説明 ²

到達可能性と連結性の違いはコア点に限られるかどうかだ。連結性は 対称的 な関係であるのに対し、到達可能である主体になるためにはコア点である条件が必要なので、$p$ が $q$ に到達可能でもその逆が成り立たないことがある。

人気

2025年時点でクラスタリングと言えば、通常DBSCANは終着のアルゴリズムといってよいほど非常に優れた性能を示し、長年広く使われてきた手法だ。 $k$-平均クラスタリング が単純さを武器にし、階層的クラスタリング が直感性を武器にするなら、DBSCANは比較的複雑なデータセットでも高い一貫性を持つ。

DBSCAN以降、クラスタリングアルゴリズムの発展が全くなかったわけではないが、$k$-平均クラスタリングや階層的クラスタリングがそうであったように細かな変形が試みられただけで、その堅固な地位を揺るがすには至らなかった。こうして三つのアルゴリズムはクラスタリング界の三神器と見なされ、EMアルゴリズムなどの手法は教科書で少し触れられる程度にとどまる。

特に 人工知能 の時代が到来してからは 教師あり学習 が圧倒的に優勢となり、クラスタリング手法の革新はほとんど止まったように見える。逆に言えば、クラスタリング自体を研究するつもりがないならDBSCANを最後に学習を終えてもよい、ということでもある。