密度ベースクラスタリング入門：DBSCAN・OPTICS・HDBSCAN の基本と実務活用
エバープレイ編集部はじめに — 密度ベースクラスタリングとは何か
密度ベースクラスタリング（density-based clustering）は、データの「密度」に着目してクラスター（群）を検出する一連の手法の総称です。代表的なアルゴリズムとしてDBSCAN（Density-Based Spatial Clustering of Applications with Noise）、OPTICS、HDBSCANなどがあり、ノイズ（外れ値）を自然に扱え、非線形で複雑な形状のクラスタを発見できる点が大きな強みです。特に地理空間データや異常検知、画像処理、バイオインフォマティクスなどで広く利用されています。
基本概念（DBSCAN を例に）
DBSCAN の基本は「ε（イプシロン、近傍半径）」と「minPts（最小点数）」の2つのパラメータに基づく定義です。以下の用語が重要です。
- ε-近傍（ε-neighborhood）：ある点 p の周りの半径 ε の範囲に入る点の集合。
- コア点（core point）：その ε-近傍内に自身を含めて minPts 以上の点がある点。コア点は密度の中心となる。
- ボーダー点（border point）：自分自身はコア点でないが、あるコア点の ε-近傍に含まれる点。
- ノイズ（noise / outlier）：どのコア点の ε-近傍にも含まれない点。
DBSCAN はコア点を起点に、ε-近傍内を再帰的に拡張してクラスターを作ります。結果として、形状が自由で密度が一定以上の領域をクラスターとして検出できます。
パラメータ選びの実務的ヒント
- minPts の目安：次元数 D に対して minPts ≥ D+1 を最低線として、実務では 4〜2×D の範囲で調整することが多いです。2D の地理データでは minPts = 4 や 5 がよく使われます。
- ε の決定（k-distance プロット）：各点について k = minPts に対応する最近傍距離（k-distance）を計算し、それらを降順プロットします。距離が急増する「エルボー」点が ε の候補になります。
- 標準化と距離尺度：特徴量はスケールに敏感なため、標準化（z-score）やスケーリングが重要です。また、ユーザの問題に応じてユークリッド距離、マンハッタン距離、コサイン類似度など適切な距離を選びます。カテゴリ変数が混在する場合はガワー距離（Gower）などの手法を検討します。
アルゴリズムの計算量と高速化
DBSCAN の基本的な実装は各点の近傍探索を行うため O(n^2)（n はデータ数）になり得ますが、空間データ構造を用いることで大幅に高速化できます。具体的には KD-tree、Ball-tree、R-tree、あるいはグリッドベースのインデックスを用いると、低次元では平均的に O(n log n) に近づきます。ただし高次元データでは空間分割の効果が薄れる（次元の呪い）ため、近傍探索のコストは依然高くなります。
大規模データに対しては次のような対策があります：
- 近似近傍探索（LSH、FAISS など）で近傍検索を近似的に高速化
- サンプリングやストリーミング手法で事前に代表点を抽出
- 並列化・GPU 実装（近年のライブラリや商用ツール）
変種と拡張
密度ベースの考え方を拡張した主な手法：
- OPTICS（Ordering Points To Identify the Clustering Structure）：DBSCAN の欠点である単一の ε を前提とする制約を克服するために、点の「並び（ordering）」と「reachability distance（到達可能距離）」を出力します。ε を大きくとった上で得られるリーチャビリティプロットを解析することで、異なる密度をもつクラスタを可視化・抽出できます。
- HDBSCAN（Hierarchical DBSCAN）：密度に基づく階層的クラスタリングを行い、クラスタの「安定度（stability）」に基づいて最終的なクラスタを抽出します。OPTICS と同様に異なる密度を自然に扱え、クラスタ数や ε に敏感になりにくいという利点があります。確率的なクラスタ所属度（soft clustering）を返す実装もあります。
- DENCLUE、Mean-Shift など：確率密度関数（kde）や核密度推定に基づくアプローチで、密度のモード（局所最大）をクラスタとして検出します。特徴的には数学的基盤が異なるが、密度に基づく思想は共通です。
長所と短所（ユースケース別の考慮点）
長所：
- クラスタの形状に柔軟（非球状・非凸形状の検出が可能）
- ノイズ点の自動検出（ラベリングしない）
- クラスタ数を事前に指定する必要がない（自動決定）
短所：
- パラメータ（ε, minPts）に敏感。特にデータ内で密度差が大きい場合、単一の ε では対応できないことがある
- 高次元データでは距離が均一化しやすく、密度判定が難しくなる（次元の呪い）
- スケーリングや異常値に注意が必要。前処理が結果に与える影響が大きい
実務での適用上の注意点とワークフロー
- 前処理：欠損値処理、スケーリング、カテゴリの数値化（必要ならガワー距離）を行う。
- パラメータ探索：k-distance プロットで ε を候補選定し、minPts は次元数を参照して調整する。複数のパラメータを試す場合は、評価指標（シルエットは密度クラスタには最適とは限らない）やドメイン知識で妥当性を判断する。
- 可視化：2D/3D に投影（t-SNE, UMAP）してクラスタ分布を確認する。OPTICS のリーチャビリティプロットは非常に有用。
- スケール時の工夫：大規模データでは近似近傍、インクリメンタルな手法、バッチ処理、分散化などを活用する。
代表的な実装とツール
- scikit-learn の DBSCAN 実装（Python）：使いやすく、多くの距離／空間インデックスが利用可能。OPTICS も実装されています。
- hdbscan（Python パッケージ）：HDBSCAN の高性能実装。階層的クラスタ抽出や確率的クラスタメンバーシップを提供します。
- 地理空間ライブラリ（PostGIS, GeoPandas 等）とも相性が良く、緯度経度データのホットスポット解析に応用されます。
代表的な応用例
- 地理空間解析：犯罪ホットスポット、交通渋滞地点、店舗集積の検出
- 異常検知：機器の異常ログやネットワークトラフィックの外れ値検出
- 画像処理：セグメンテーションや前景抽出における領域検出
- バイオインフォマティクス：シングルセル解析などでの細胞群の発見（HDBSCAN が使われることが多い）
まとめ
密度ベースクラスタリングは、ノイズを含むデータや非凸形状のクラスタを扱う際に非常に有効な手法群です。DBSCAN はシンプルかつ説明性が高く、OPTICS や HDBSCAN は密度差があるデータや自動化に強みを持ちます。実務ではパラメータの選定、スケール、距離尺度の選択、そして可視化による確認が重要です。大規模・高次元データに対しては近似手法や次元削減、並列化などの工夫が必要になります。
参考文献
- M. Ester, H.-P. Kriegel, J. Sander, X. Xu, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", KDD 1996 (DBSCAN)
- OPTICS — Wikipedia
- F. M. J. A. Campello, D. Moulavi, J. Sander, "Density-Based Clustering Based on Hierarchical Density Estimates", arXiv:1305.7223 (HDBSCAN)
- scikit-learn: DBSCAN/OPTICS ドキュメンテーション
- hdbscan パッケージ ドキュメント
- DBSCAN — Wikipedia
