HDBSCAN

直感 #

DBSCAN は半径 eps の円をつないでクラスタを作りますが、密な街と疎な村が同じ地図に混ざっていると、村をつなげる大きさの円では街が 1 つに融合し、街を分けられる小さい円では村が全部ノイズになります。HDBSCAN はこのジレンマを「半径を 1 つ選ばない」ことで解きます。水位を 1 m ずつ下げていく洪水の地図を想像してください。水が引くにつれて高い島（密な領域）から順に顔を出し、さらに引くと島が 2 つに割れたり、小さな岩（min_cluster_size 未満の点）が離れたりします。HDBSCAN はこの「島がどの水位で生まれ、どの水位で割れたか」を全部記録した木（凝縮木）を作り、幅広い水位にわたって形を保った島を最終クラスタとして採用します。

何が起きているか（ステップで見る） #

コードを読む前に、この手法が図の上で何をしているかを追ってみましょう。「再生」を押すか、スライダーを動かすと 1 手順ずつ進みます。

見るポイント：クラスターは「円がつながる範囲」。丸くない形でも追いかけられ、どの円にも入らない点はノイズになる。HDBSCAN はこの円の半径をあらゆる値で試し、長く形を保ったクラスタを選ぶ。

数式で見る 4 つの段階 #

HDBSCAN のアルゴリズムは、コア距離の計算、相互到達距離の定義、最小全域木の構築、凝縮木からの安定クラスター抽出の 4 段階で構成されます。4 つの段階を順に、図の上で何を計算しているかを添えて追います。

1. コア距離（Core Distance） #

点 $x_i$ から見て $k$ 番目に近い点を $x_i^{(k)}$ とすると、コア距離はその点までの距離です。

$k$ は引数 min_samples に対応します。コア距離は「この点の周りに min_samples 個の仲間を集めるのに必要な円の半径」で、小さいほど密な領域にいることを意味します。DBSCAN では全点に同じ半径 $\varepsilon$ を使いましたが、HDBSCAN は点ごとに違う半径を持たせます。

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

2 点 $x_i, x_j$ の相互到達距離は、両方のコア距離と実際の距離のうち最大の値です。

両方の点が密な領域にあればコア距離は小さく、ユークリッド距離 $d(x_i, x_j)$ がそのまま採用されます。どちらかが疎な領域にあると、その点のコア距離が勝って距離が引き伸ばされます。この引き伸ばしのおかげで、疎な領域の点は密な領域に吸い寄せられにくくなり、ノイズ耐性が上がります。全点間の相互到達距離から**最小全域木（MST）**を作るのが次の準備です。

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

最小全域木の辺を長いものから順に切ると、全点が 1 つの木から徐々に分かれていく階層分割が得られます。半径 $\varepsilon$ の逆数を密度パラメーター $\lambda$ と定義します。

$\lambda$ が大きいほど、小さい円でもつながる高密度の水準を指します。凝縮木（condensed tree）は、この階層木で分裂後の片方が min_cluster_size 未満になった場合を「クラスタの分裂」ではなく「点の脱落」と見なして枝を省いたものです。min_cluster_size=20 なら、19 点以下の塊が離れても親クラスタは続いていると扱います。

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

凝縮木の各クラスター $C$ について、安定度は「点が所属していた $\lambda$ の幅」の合計です。

$\lambda_{\min}(C)$ はクラスター $C$ が親から分裂して誕生したときの $\lambda$ 値で、$\lambda_{\max}(x_i, C)$ は点 $x_i$ が $C$ から脱落するか、$C$ がさらに分裂するときの $\lambda$ 値です。安定度が高いクラスターは広い密度範囲にわたって形を保っており、信頼できる構造と見なします。最後に凝縮木を葉から根へたどり、親の安定度 $S(C)$ と子の安定度の合計を比べ、子の合計が上回れば子を、そうでなければ親を採用します（cluster_selection_method="eom"、Excess of Mass）。

HDBSCANの処理フロー #

Pythonを用いた実験や説明 #

次のコードは make_moons で三日月 2 つの 400 点を作り、hdbscan.HDBSCAN(min_cluster_size=20, min_samples=10) でクラスタリングします。eps は一切指定していないのに 2 つの月が分かれ、最後に各クラスタの安定度とノイズ点数が表示されます。

 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))

実行結果の読み方 #

図では上下 2 つの三日月が別の色で塗られ、月の先端や外側の数点がノイズ色になります。「クラスタ安定度」は長さ 2 の配列で、どちらの月も密度の広い範囲で形を保つので 1.0 に近い値が並びます。noise=0.08 のデータならノイズ点数は数点から十数点で、min_samples を 10 から 20 に上げると月の縁の点が削られてノイズ点数が増えます。

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

スライダーで min_cluster_size を 3 から 50 まで動かすと、180 点の結果が変わります。3 では 25 個の細かい塊に砕け、5 で 8 個、10〜30 では 2 つの三日月に落ち着きます。ただし 20 以上ではノイズ点数が 76、114 と増えていき、50 ではクラスタと認められる塊がなくなり全 180 点がノイズです。

使いどころと落とし穴 #

HDBSCAN が向いているのは、クラスタごとに密度が違うデータと、eps を試行錯誤する時間を省きたい場面です。UMAP で 2〜10 次元に落とした埋め込みの上で使うと、高次元で距離が均一化する問題も避けられます。落とし穴は min_cluster_size です。小さすぎると上のスライダーの 3 のように 25 個に砕け、大きすぎると 50 のように本物のクラスタまでノイズになります。データ数の 1〜5 % から始めて cluster_persistence_ の値を見ながら調整してください。計算量は最小全域木の構築を含めておおむね $O(n \log n)$ で、DBSCAN より重い代わりに数十万点でも実用的です。クラスタが同じ密度の球状なら、k-means や GMM の方が少ない計算で同じ答えに届きます。

まとめ #

HDBSCAN は半径 eps を固定せず、コア距離と相互到達距離から最小全域木を作り、辺を長い順に切ってできる階層木を min_cluster_size で凝縮します。各クラスタが存続した $\lambda$ の幅を安定度 $S(C)$ として合計し、親と子のどちらが安定かで最終クラスタを選ぶのが DBSCAN との決定的な違いです。指定するのは min_cluster_size と min_samples の 2 つで、密度の異なるクラスタを同時に拾えます。上のスライダーの通り min_cluster_size が結果を左右するので、データ数の 1〜5 % を起点に cluster_persistence_ を見て調整します。

参考文献 #