HDBSCAN入門と実践：アルゴリズム・パラメータ・応用の深堀り
エバープレイ編集部概要
HDBSCAN（Hierarchical Density-Based Spatial Clustering of Applications with Noise）は、ノイズに強く、クラスタ数を事前指定する必要がない密度ベースのクラスタリング手法です。DBSCANの考えを階層化して安定性（persistence）に基づくクラスタ抽出を導入したもので、特に複雑な形状や異なる密度を持つクラスタを扱う際に有力です。本コラムでは、アルゴリズムの核心、主要パラメータ、出力の解釈、実装上の注意点、チューニング方法、利点と限界、実世界での応用例までを詳しく解説します。
基本概念と直感
HDBSCANは「密度に基づくクラスタの階層」を構築し、そこから最も“安定”なクラスタを抽出します。キーワードは次のとおりです。
- コア距離（core distance）: データ点の周りで指定した近傍サイズ（min_samples）に到達する距離。点の局所的密度の逆数に相当する尺度です。
- 相互到達距離（mutual reachability distance）: 2点間の距離と両点のコア距離の最大値。これを用いることで低密度領域の影響を緩和し、密度の低い領域でクラスタが分断されるのを防ぎます。
- 単一連結の木（single-linkage tree）: 相互到達距離を距離として最小全域木（MST）を構築し、これに基づく階層（樹）を得ます。
- 濃縮ツリー（condensed tree）と安定性（stability）: 階層を最小クラスタサイズ（min_cluster_size）で濃縮し、各クラスタの存続期間（どの密度域で現れてどの密度域で消えたか）に基づき安定性を計算。安定なクラスタを選択して確定ラベルを与えます。
アルゴリズムの流れ（ステップごと）
主要な処理は以下の順です。
- 各点のコア距離を計算（min_samplesにより第k最近傍距離を採る）
- 相互到達距離を定義して点間の距離を再評価
- 相互到達距離を重みとするグラフの最小全域木（MST）を構築
- MSTを基に単一連結の階層クラスタリング木を得る
- 階層をmin_cluster_sizeで濃縮してcondensed treeを作る
- 各クラスタの安定性（persistence）を計算し、高い安定性を示すクラスタを抽出
主なパラメータと意味
パラメータ設計は結果に大きく影響します。よく使われるものは：
- min_cluster_size：最小クラスタサイズ。これより小さい集合はクラスタとして認められず、ノイズ扱いされやすい。データの最小の有意味なクラスタサイズに合わせて設定します。
- min_samples：コア距離の計算に使う近傍数。大きくするとノイズをより広く検出し、クラスタはより保守的（大きくまとまる）になります。指定しない場合はmin_cluster_sizeが使われる実装が多いです。
- metric：距離の定義（Euclidean, manhattan, cosineなど）。高次元や疎なデータでは適切な距離を選ぶことが重要です。
- cluster_selection_method：クラスタ抽出の戦略。一般に"eom"（excess of mass：安定性に基づく）と"leaf"（葉ノードを採る）があります。デフォルトは"eom"で、より意味的に安定なクラスタを与えます。
出力とその解釈
実装（Pythonのhdbscanライブラリ等）では、主に次の情報が得られます。
- labels_: 各点のクラスタID（-1はノイズ）
- probabilities_: ソフトメンバシップ確率（クラスタに属する信頼度）
- outlier_scores_: 外れ値スコア（大きいほど外れの可能性が高い）
- cluster_persistence_: 各クラスタの安定性指標
- condensed_tree_: 濃縮ツリーの構造（可視化や詳細解析に有用）
重要なのは、HDBSCANはハードラベルだけでなく、点ごとの所属確率や外れ値スコアを返せる点です。これにより、境界点の取り扱いやノイズ判定に柔軟性が生まれます。
実装例（Python, 概略）
典型的にはpipでhdbscanを入れて用います（NumPy/Scikit-learnと組み合わせ）。簡単な流れは以下のとおりです。
from hdbscan import HDBSCAN
clusterer = HDBSCAN(min_cluster_size=10, min_samples=5, metric='euclidean')
clusterer.fit(X)
labels = clusterer.labels_
probs = clusterer.probabilities_
outliers = clusterer.outlier_scores_
また、condensed_tree_.plot()などで階層・クラスタの可視化が可能です。
チューニングとベストプラクティス
- min_cluster_sizeの決め方：ドメイン知識があればそれを優先。無ければデータ量の割合（全体の1%や5%）や、探索的に試す。
- min_samplesの調整：ノイズ検出を厳格にしたい場合は大きくする。外れ値を許容しづらい環境なら増やすと良い。
- 距離指標の選択：高次元データではEuclideanが効かないことがある。コサイン類似度や学習した距離を試す。
- 前処理：スケーリング（標準化や正規化）や次元削減（PCA, UMAP）との組合せが有効。特にUMAPとHDBSCANの組合せは表現学習分野で一般的です。
- 可視化：2次元に埋め込んでからcondensed treeと色付けで結果を確認。クラスタ境界やノイズ分布を視覚的に検証することが重要。
計算量とスケーラビリティ
理論的には全点間距離を直接扱うとO(n^2)になりますが、実装（hdbscanライブラリ）は空間索引（kd-tree/ball-tree）や近似近傍探索を活用し、低〜中次元では実用的な速度を出します。ただし高次元では近傍探索が効きにくくなり、計算負荷が増大するので注意が必要です。大規模データではサンプリングや次元削減、近似アルゴリズムの併用を検討してください。
長所（メリット）
- クラスタ形状に柔軟：非線形・凹凸の形状を自然に扱える。
- クラスタ数を事前指定不要：自動的に安定なクラスタを抽出。
- 異なる密度を持つクラスタに強い：DBSCANより密度差に対処しやすい。
- ソフトメンバシップと外れ値スコアを提供：境界や外れの扱いが柔軟。
短所（デメリット）と注意点
- スケールの選択に敏感：距離尺度や前処理が結果に大きく影響する。
- 高次元での計算負荷：近傍探索が効かない場合、計算量が問題になる。
- パラメータ調整は必要：全自動ではないため、min_cluster_size等の試行が必要。
- 解釈の難しさ：クラスタの“安定性”という概念は有益だが、結果の解釈に慣れが必要。
実世界での応用例
- 異常検知：ネットワークログやIoTデータの外れ値検出に利用。
- 顧客セグメンテーション：購買行動の多様な密度を持つ群の抽出。
- 画像特徴のクラスタリング：特徴ベクトルにUMAPを併用してHDBSCANで群分け。
- 地理空間データ解析：密度の異なる集積地の検出。
他手法との比較（DBSCAN・OPTICS等）
DBSCANは単純で高速だが、異なる密度を持つクラスタ分離が苦手で、epsの設定に敏感です。OPTICSは密度の変化を表現できるが抽出ルールが必要です。HDBSCANはこれらの欠点を補うべく階層化と安定性に基づく抽出を行うため、より柔軟で実世界データに強い傾向があります。ただし計算コストやパラメータ設計の面で注意が必要です。
まとめ（実践的チェックリスト）
- データをスケーリング／標準化する
- 低次元化（必要に応じてPCAやUMAP）を検討する
- min_cluster_sizeはドメイン知識か全体比率から初期値を決定
- min_samplesでノイズ検出の厳しさを調整
- 結果はlabels_だけでなくprobabilities_やoutlier_scores_で検証
- condensed_treeや可視化でクラスタの妥当性を確認する
参考文献
- HDBSCAN documentation — 公式ドキュメント（実装とAPI解説）
- hdbscan GitHub repository — ソースコードと実装詳細
- DBSCAN (Wikipedia) — 密度ベースクラスタリングの古典的手法の解説
- OPTICS (Wikipedia) — 密度変化を扱うアルゴリズムの解説
- Campello, Moulavi, Sander: Density-Based Clustering Based on Hierarchical Density Estimates (論文) — HDBSCANの理論的背景（原論文）
投稿者プロフィール
