DBSCANとは？密度ベースクラスタリングの基本概念と仕組みを解説

DBSCANとは

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）は、「ノイズを含むアプリケーション向けの密度ベース空間クラスタリング」と呼ばれるクラスタリング手法です。k-meansのような距離に基づく手法と異なり、データの「密度」に着目することで、十分に高い密度を持つ領域をクラスタとして成長させながら、ノイズを含む空間データベースから任意の形状のクラスタを検出できます。クラスタは「密度連結な点の最大集合」として表現されます。

DBSCANの基本概念

密度ベースクラスタリングでは、以下の定義が中心的な役割を果たします。

ε近傍（イプシロン近傍）

あるオブジェクトを中心とする半径 ε 以内の領域を、そのオブジェクトのε近傍と呼びます。

コアオブジェクト

あるオブジェクトのε近傍に、最低限必要な数 MinPts 以上のオブジェクトが含まれている場合、そのオブジェクトはコアオブジェクト（中核点）とみなされます。

直接密度到達可能

オブジェクトの集合 D において、p が q のε近傍内に存在し、かつ q がコアオブジェクトであるとき、「p は q から直接密度到達可能」といいます。

密度到達可能

D において、p₁ = q、p_n = p となるオブジェクト列 p₁, ..., p_n が存在し、各 i（1 ≤ i ≤ n）について p_i+1 が p_i から直接密度到達可能であるとき、「p は q から密度到達可能」と定義されます。

密度連結

p と q の双方が、あるオブジェクト o ∈ D から密度到達可能であるとき、「p と q は密度連結」といいます。

密度到達可能性と密度連結性の性質

• 密度到達可能性は直接密度到達可能性の推移閉包であり、非対称な関係です。互いに密度到達可能なのはコアオブジェクト同士だけです。
• 密度連結性は対称な関係です。

そして、密度ベースクラスタとは「密度到達可能性に関して極大となる、密度連結なオブジェクトの集合」を指します。どのクラスタにも所属しないオブジェクトは、すべてノイズとして扱われます。

DBSCANのアルゴリズムの流れ

1. データベース内のすべての点について、そのε近傍を調べます。
2. 点 p のε近傍に MinPts 以上の点が含まれる場合、p をコアオブジェクトとする新しいクラスタを作成します。
3. コアオブジェクトから直接密度到達可能なオブジェクトを繰り返し収集していきます。この過程で、複数の密度到達可能なクラスタが統合されることもあります。
4. どのクラスタにも新たな点を追加できなくなった時点で、処理を終了します。

計算量と実用上のポイント

空間インデックスを使用した場合、DBSCANの計算量は O(n log n) となります（n はデータベース内のオブジェクト数）。空間インデックスを使用しない場合は O(n²) です。ユーザーが指定するパラメータ ε と MinPts を適切に設定すれば、本アルゴリズムは任意形状のクラスタを効率的に発見できる強力な手法となります。

DBSCANの主なメリット

• クラスタ数を事前に指定する必要がありません。
• 球状に限らない、複雑な形状のクラスタも検出できます。
• 外れ値（ノイズ）を自動的に識別・分離できます。