HDBSCAN

中級

2.5.6

HDBSCAN

最終更新 2020-04-08 読了時間 2 分
まとめ
  • HDBSCAN（Hierarchical DBSCAN）は DBSCAN を階層化し、密度の異なる領域を自動的にクラスタ化するアルゴリズム。
  • min_cluster_size と min_samples の 2 つで密度基準を制御し、ノイズ点（ラベル -1）を自然に切り離す。
  • クラスタごとの「安定度」（persistence）を計算でき、信頼度の高いクラスタのみ採用する運用が可能。
  • UMAP などの次元削減と組み合わせると、高次元データでも柔軟に利用できる。
  • DBSCAN — HDBSCAN は DBSCAN を階層化した手法です。先に DBSCAN を理解しましょう

直感 #

DBSCAN は 1 つの eps（半径）を用いて密度の高い領域を探しますが、データによっては適切な半径がクラスタごとに異なります。 HDBSCAN は eps を徐々に広げながら密度が高い領域を追跡し、クラスタの階層構造を構築します。その後、クラスタの安定度を評価し、もっとも安定した部分クラスタを最終的な出力とします。

数式による定式化 #

HDBSCANのアルゴリズムは、大きく分けてコア距離の計算、相互到達距離の定義、最小全域木の構築、凝縮木からの安定クラスター抽出の4段階で構成されます。

1. コア距離（Core Distance） #

データ点$x_i$に対し、$k$番目に近い近傍点を$x_i^{(k)}$とします。コア距離は次のように定義されます。

$$ d_{\text{core}}(x_i) = d(x_i,\; x_i^{(k)}) $$

ここで$k$はパラメーターmin_samplesに対応します。コア距離が小さい点ほど高密度な領域に位置しています。DBSCANの固定半径$\varepsilon$に代わり、HDBSCANは各点に適応的な密度スケールを持たせます。

2. 相互到達距離（Mutual Reachability Distance） #

2点$x_i, x_j$間の相互到達距離は、両方のコア距離と実際の距離の最大値として定義されます。

$$ d_{\text{mreach}}(x_i, x_j) = \max\!\bigl(d_{\text{core}}(x_i),\; d_{\text{core}}(x_j),\; d(x_i, x_j)\bigr) $$

この距離は以下の性質を持ちます。

  • 両点が十分に高密度な領域にある場合は、実際のユークリッド距離$d(x_i, x_j)$が支配的になる
  • 一方でも疎な領域にある点がある場合は、コア距離が支配的になり距離が引き伸ばされる
  • これにより、疎な領域の点は密な領域に吸い寄せられにくくなり、ノイズ耐性が高まる

相互到達距離を用いた全点間の距離行列から**最小全域木（MST）**を構築します。

3. 階層クラスタリングと凝縮木 #

最小全域木の辺を距離の大きい順に切断すると、階層的なクラスター分割が得られます。ここで距離閾値$\varepsilon$の逆数を密度パラメーター$\lambda$として定義します。

$$ \lambda = \frac{1}{\varepsilon} $$

$\lambda$が大きいほど高い密度水準に対応します。凝縮木（condensed tree）は、分裂後のクラスターサイズがmin_cluster_size未満のものを「点の脱落」として扱い、ツリーを簡潔化したものです。

4. クラスター安定度（Cluster Stability） #

凝縮木上の各クラスター$C$について、安定度は以下のように計算されます。

$$ S(C) = \sum_{x_i \in C} \bigl(\lambda_{\max}(x_i, C) - \lambda_{\min}(C)\bigr) $$

各記号の意味は次のとおりです。

  • $\lambda_{\min}(C)$: クラスター$C$が誕生した（親から分裂した）ときの$\lambda$値
  • $\lambda_{\max}(x_i, C)$: 点$x_i$がクラスター$C$から脱落するか、$C$がさらに分裂するときの$\lambda$値

安定度が高いクラスターは広い密度範囲にわたって存在し続けており、信頼性の高い構造と見なされます。親クラスターの安定度と子クラスターの安定度の合計を比較し、子の合計が上回る場合は子クラスターを採用します。

HDBSCANの処理フロー #

flowchart TD A["各点のコア距離\nd_coreを計算"] --> B["相互到達距離\nd_mreachを計算"] B --> C["最小全域木\n（MST）を構築"] C --> D["辺を距離順に\n切断して階層木を作成"] D --> E["min_cluster_size\n未満を脱落とみなし\n凝縮木を構築"] E --> F["各クラスターの\n安定度S(C)を計算"] F --> G{"親の安定度 ≥\n子の安定度の合計？"} G -->|Yes| H["親クラスターを採用"] G -->|No| I["子クラスターを採用"] H --> J["最終クラスター\nを出力"] I --> J style A fill:#2563eb,color:#fff style C fill:#1e40af,color:#fff style E fill:#1e40af,color:#fff style F fill:#7c3aed,color:#fff style J fill:#10b981,color:#fff

Pythonを用いた実験や説明 #

hdbscan ライブラリで月型データをクラスタリングし、ノイズ点とクラスタ安定度を確認します。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import numpy as np
import matplotlib.pyplot as plt
import hdbscan
from sklearn.datasets import make_moons

X, _ = make_moons(n_samples=400, noise=0.08, random_state=42)

clusterer = hdbscan.HDBSCAN(
    min_cluster_size=20,
    min_samples=10,
    cluster_selection_method="eom",
)
labels = clusterer.fit_predict(X)

plt.figure(figsize=(6, 5))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap="tab10", s=20)
plt.title("HDBSCAN によるクラスタリング")
plt.show()

print("クラスタ安定度:", clusterer.cluster_persistence_)
print("ノイズ点数:", np.sum(labels == -1))

最小クラスタサイズと結果 #

最小クラスタサイズを変えるとクラスタ数とノイズ点がどう変わるか確認できます。

参考文献 #

  • Campello, R. J. G. B., Moulavi, D., Zimek, A., & Sander, J. (2013). Density-Based Clustering Based on Hierarchical Density Estimates. Pacific-Asia Conference on Knowledge Discovery and Data Mining.
  • McInnes, L., Healy, J., & Astels, S. (2017). hdbscan: Hierarchical Density Based Clustering. Journal of Open Source Software.
  • scikit-learn developers. (2024). Clustering. https://scikit-learn.org/stable/modules/clustering.html