DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN（ノイズを含むアプリケーションのための密度ベース空間クラスタリング）は、密集している点をクラスタにまとめ、疎な領域にある点をノイズとしてラベル付けする教師なし学習アルゴリズムです。Martin Ester、Hans-Peter Kriegel、Jörg Sander、Xiaowei Xuは、1996年のKDDカンファレンスでこのアルゴリズムを発表しました。クラスタ数を事前に指定する必要がなく、リング、三日月、曲がりくねった道路など、さまざまな形状のクラスタを扱えます。また、ノイズラベルは簡易的な異常検知としても機能します。アルゴリズム全体は、近傍の半径と、近傍が密であると見なすために必要な点の数という2つのパラメーターで制御します。

コア点、境界点、ノイズ点#

DBSCANは各点の近傍、つまり距離eps以内にある点の集合を調べ、その数を数えます。

• コア点: 近傍にmin_samples以上の点が含まれます。scikit-learnの実装では、その点自身も数に含めます。コア点はクラスタの密な内部を形成します。
• 境界点: コア点になるには近傍の数が足りませんが、コア点のeps以内にあります。境界点はクラスタの縁を形成します。
• ノイズ点: どちらにも該当せず、どのクラスタにも属さないため、ラベル-1が割り当てられます。

クラスタは、未訪問のコア点から成長します。DBSCANはその近傍にあるすべての点を追加し、新たに追加された各コア点から、到達可能な点がなくなるまで同じ処理を繰り返します。そのため、密な近傍が重なり合って連鎖すると、どのように曲がっていても1つのクラスタになります。境界点はクラスタに加わりますが、クラスタを拡張することはありません。入力順序が同じであれば結果は決定的ですが、2つのクラスタから到達可能な境界点は、先に到達したクラスタに加わります。そのため、データをシャッフルすると、境界点が別のクラスタに移ることがあります。

epsとmin_samplesの選び方#

半径epsが最も重要で、その値はデータのスケールに左右されるため、通常は事前に特徴を標準化します。半径が小さすぎると、ほとんどの点がノイズとして残ります。大きすぎると、隣接するクラスタが1つに統合されます。一般的なヒューリスティックでは、各点からk番目に近い近傍点までの距離を並べ替えます。kはmin_samplesとし、距離が急激に増加し始める曲線のひざの位置からepsを選びます。min_samplesを大きくすると、クラスタリングでノイズを許容しやすくなるため、大規模またはノイズの多いデータセットでよく使われます。画像の埋め込みのように高次元の空間では、点間の距離が互いに似た値になるため、DBSCANを実行する前に次元削減、たとえば主成分分析（PCA）を行うことがよくあります。

DBSCAN、K-Means、HDBSCANの違い#

k-meansクラスタリングでは、事前にクラスタ数を指定する必要があり、各点を最も近い重心に割り当てます。そのため、コンパクトで円形に近いクラスタが得られやすく、外れ値もいずれかのグループに取り込みます。DBSCANは密度からクラスタ数を見つけ、外れ値をどのクラスタにも含めません。弱点は、グローバルなepsを1つしか使わないことです。密度が大きく異なるクラスタがある場合、疎なクラスタとノイズ、または密なクラスタ同士を同時に分離できる半径が見つからないことがあります。HDBSCANはepsのすべての値でDBSCANを実質的に実行し、最も安定したクラスタを保持することでこの問題に対処します。どちらのアルゴリズムも、関連するOPTICSとともにscikit-learnのクラスタリングモジュールで利用できます。

この例では、互いに入り組んだ2つの三日月形クラスタにランダムな外れ値を20個追加し、調整済みランド指数を使って各結果を正解グループと比較します。1.0が完全一致を示します。

import numpy as np
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import adjusted_rand_score

# Two interleaving crescents plus 20 scattered outliers (true label -1)
X, y = make_moons(n_samples=300, noise=0.05, random_state=0)
rng = np.random.default_rng(0)
X = np.vstack([X, rng.uniform(-1.5, 2.5, size=(20, 2))])
y = np.concatenate([y, np.full(20, -1)])

# DBSCAN infers clusters from density; k-means is told there are 2
db_labels = DBSCAN(eps=0.2, min_samples=5).fit_predict(X)
km_labels = KMeans(n_clusters=2, random_state=0).fit_predict(X)

print(f"DBSCAN: {db_labels.max() + 1} clusters, {(db_labels == -1).sum()} noise points")
print(f"ARI: DBSCAN {adjusted_rand_score(y, db_labels):.2f}, k-means {adjusted_rand_score(y, km_labels):.2f}")

このスクリプトでは、DBSCANは2つのクラスタと15個のノイズ点を出力し、調整済みランド指数はDBSCANで0.97、k-meansで0.20となります。DBSCANは両方の三日月形クラスタをたどり、離れた場所にある外れ値を除外します。一方、k-meansはクラスタ数を正しく指定されているにもかかわらず、三日月形クラスタを直線で分割します。

実際のアプリケーション#

• LiDAR認識: 自動運転車やロボティクスのパイプラインでは、LiDARスキャンから地面の点を取り除き、残った3D点を個別の障害物にクラスタリングします。物体数が事前に分からないため、密度ベースのクラスタリングがよく使われます。
• 検出後処理: result.boxes.xywhとして取得できるYOLO26検出結果のボックス中心をDBSCANでクラスタリングすると、人混みの中の人物グループや、生産ライン上で繰り返し発生する欠陥の位置を特定できます。その際、孤立した検出結果はノイズとして除外されます。
• 不正検出とセンサー監視: -1とラベル付けされた取引や測定値は、正常な挙動の密集したグループから大きく離れており、レビュー対象の候補になります。
• 地理空間分析: 配送会社やライドシェア会社はGPSポイントをクラスタリングし、頻繁に停車する場所や乗車地点のホットスポットを特定します。Scikit-learnのDBSCANでは、緯度と経度をラジアンで表したmetric="haversine"を指定できます。この場合、epsは単位球面上の角度となるため、半径100メートルは地球の平均半径6,371 kmを使ってeps = 0.1 / 6371になります。