# Density-Based Clustering Based on Hierarchical Density Estimates > [!abstract] 概要 > 理論・実用の両面で改良された密度ベース階層クラスタリング手法を提案する。提案手法はクラスタリング階層を生成し、その中から有意なクラスタのみからなる簡約化ツリーを構築できる。最も有意なクラスタ（異なる密度閾値に対応しうる）のみからなる「フラットな」分割を得るため、新しいクラスタ安定性尺度を提案し、選択クラスタの全体安定性を最大化する問題を定式化して、最適解を求めるアルゴリズムを与える。多様な実世界データにおいて、現行の最先端密度ベースクラスタリング手法を上回ることを実証する。 ## 論文情報 - **著者**: [[Ricardo J.G.B. Campello]]、[[Davoud Moulavi]]、[[Jörg Sander]] - **所属**: Department of Computing Science, University of Alberta, Edmonton, AB, Canada - **会議**: PAKDD 2013（Pacific-Asia Conference on Knowledge Discovery and Data Mining） - **掲載**: LNAI 7819, pp. 160–172, Springer-Verlag Berlin Heidelberg, 2013 - **備考**: Campello は University of São Paulo（USP）からのサバティカル中。FAPESP・CNPq の支援を謝辞に記載。研究の一部は NSERC の支援を受けている。 ## 概要 本論文は、密度ベースクラスタリングの階層的拡張である HDBSCAN を提案する。HDBSCAN は DBSCAN の全解を単一パラメータ $m_{pts}$ のみで階層的に列挙し、有意なクラスタだけからなる簡約化ツリーを生成する。さらに、相対超過質量（relative excess of mass）に基づくクラスタ安定性尺度を導入し、異なる密度レベルにまたがる最適なフラット分割を動的計画法で抽出する。 ## 問題設定 既存の密度ベースクラスタリング手法には以下の限界がある。 1. **単一閾値**: DBSCAN や DENCLUE はグローバルな密度閾値に基づくフラットなラベル付けしか提供できない。密度が大きく異なるクラスタや入れ子構造を持つデータには不適切である。 2. **簡約化の欠如**: gSkeletonClu のように階層を提供する手法でも、有意なクラスタのみへの自動的な簡約化ができない。 3. **グローバルカットのみ**: OPTICS や gSkeletonClu はグローバルなカット（密度閾値）によるフラット分割の抽出しか提案しておらず、異なる密度レベルに特徴づけられるクラスタを適切に抽出できない。 4. **特定問題への限定**: gSkeletonClu はネットワーク、DECODE や汎化単リンケージ法は実座標空間上の点集合に限定されている。 5. **多パラメータ依存**: 多くの手法が複数の、しばしば結果に大きく影響する入力パラメータを必要とする。 ## 提案手法 ### DBSCAN* の再定義 本論文はまず DBSCAN を再定義した DBSCAN* を提示する。 - **Definition 1（核オブジェクト）**: オブジェクト $x_p$ の $\varepsilon$-近傍が $m_{pts}$ 個以上のオブジェクトを含むとき、$x_p$ を核オブジェクトと呼ぶ。核オブジェクトでないものはノイズである。 - **Definition 2（$\varepsilon$-到達可能）**: 2 つの核オブジェクト $x_p$, $x_q$ が互いの $\varepsilon$-近傍に含まれるとき、$\varepsilon$-到達可能と呼ぶ。 - **Definition 3（密度接続）**: 2 つの核オブジェクトが直接的または推移的に $\varepsilon$-到達可能であるとき、密度接続と呼ぶ。 - **Definition 4（クラスタ）**: クラスタ $C$ は、全ての対が密度接続であるような $X$ の極大部分集合である。 DBSCAN* は DBSCAN と異なり、境界オブジェクト（border object）の概念を排除する。境界オブジェクトは技術的にはレベルセットに属さない（推定密度が閾値を下回る）ため、密度等高線クラスタの統計的解釈との整合性が向上する。この再定義により、DBSCAN* とその階層版（HDBSCAN）の間に正確な関係が成立する。元の DBSCAN と OPTICS の間では近似的な関係しか成り立たなかった。 ### HDBSCAN HDBSCAN は OPTICS の概念的・アルゴリズム的改良と位置づけられ、唯一の入力パラメータは $m_{pts}$（密度推定の古典的平滑化因子）である。 - **Definition 5（コア距離）**: オブジェクト $x_p$ のコア距離 $d_{core}(x_p)$ は、$x_p$ からその $m_{pts}$-最近傍（$x_p$ 自身を含む）までの距離である。 - **Definition 6（$\varepsilon$-核オブジェクト）**: $d_{core}(x_p) \le \varepsilon$ を満たす全ての $\varepsilon$ に対して $x_p$ は $\varepsilon$-核オブジェクトとなる。 - **Definition 7（相互到達可能距離）**: $d_{mreach}(x_p, x_q) = \max\{d_{core}(x_p), d_{core}(x_q), d(x_p, x_q)\}$。 - **Definition 8（相互到達可能グラフ）**: $X$ のオブジェクトを頂点とし、辺の重みが相互到達可能距離である完全グラフ $G_{m_{pts}}$。 **Proposition 1**: DBSCAN* による分割は、相互到達可能距離空間上で単リンケージ法を適用し、得られたデンドログラムをレベル $\varepsilon$ でカットしたものと一致する（$d_{core}(x_p) > \varepsilon$ のシングルトンはノイズクラスとして扱う）。 **Algorithm 1**（HDBSCAN の主要ステップ）: 1. 全データオブジェクトの $m_{pts}$ に関するコア距離を計算する。 2. 相互到達可能グラフ $G_{m_{pts}}$ の最小全域木（MST）を計算する。 3. 各頂点にコア距離を重みとする自己辺（self edge）を追加して拡張 MST（$MST_{ext}$）を得る。 4. $MST_{ext}$ から辺を重みの降順に除去してデンドログラムとして HDBSCAN 階層を抽出する。 計算量は Prim のアルゴリズム（リストベース）を用いて $O(dn^2)$、空間計算量は $O(dn)$（距離行列が与えられる場合は時間 $O(n^2)$、空間 $O(n^2)$）。 ### 階層の簡約化 HDBSCAN 階層は大規模データでは解釈困難となるため、**Algorithm 2** で有意なクラスタのみからなる簡約化ツリーを抽出する。Hartigan の剛体クラスタ（rigid cluster）の概念に基づき、密度レベルの連続的な増加に対して連結成分は (i) 縮小して連結を維持、(ii) 複数の小さな成分に分割、(iii) 消滅の三通りしかないことを利用する。 パラメータ $m_{clSize} \ge 1$ を導入し、$m_{clSize}$ 未満のオブジェクトからなる成分を偽の分割（spurious）として扱いノイズとラベル付けする。実用上は $m_{clSize} = m_{pts}$ と設定し、$m_{pts}$ を平滑化因子とクラスタサイズの閾値の双方として機能させることで、単一パラメータの簡潔さを維持する。 ### 最適非階層クラスタリング 異なる局所密度を持つ目立つクラスタを抽出するため、クラスタ安定性の最大化を最適化問題として定式化する。 **超過質量**（excess of mass）: Hartigan のモデルに従い、密度等高線クラスタ $C_i$ が密度レベル $\lambda_{min}(C_i)$ で出現するとき、超過質量は以下で定義される。 $E(C_i) = \int_{x \in C_i} \left( f(x) - \lambda_{min}(C_i) \right) dx$ ![[Campello-et-al-2013-HDBSCAN/fig01-density-clusters-excess-of-mass.png|図1. 密度関数、クラスタ、超過質量の図解]] 超過質量は階層のどの分岐に沿っても単調であるため、入れ子クラスタ間の安定性比較には使えない。そこで**相対超過質量**（relative excess of mass）を導入する（Equation 2）。 $E_R(C_i) = \int_{x \in C_i} \left( \lambda_{max}(x, C_i) - \lambda_{min}(C_i) \right) dx$ ここで $\lambda_{max}(x, C_i) = \min\{f(x), \lambda_{max}(C_i)\}$、$\lambda_{max}(C_i)$ は $C_i$ が分割または消滅する密度レベルである。 有限データセットに対して、クラスタ $C_i$ の**安定性**（Equation 3）を以下で定義する。 $S(C_i) = \sum_{x_j \in C_i} \left( \lambda_{max}(x_j, C_i) - \lambda_{min}(C_i) \right) = \sum_{x_j \in C_i} \left( \frac{1}{\varepsilon_{min}(x_j, C_i)} - \frac{1}{\varepsilon_{max}(C_i)} \right)$ **Problem 4**（最適化問題）: 簡約化クラスタツリーの葉から根までの各パスで正確に一つのクラスタが選択されるという制約の下で、選択クラスタの安定性の総和 $J = \sum_{i=2}^{\kappa} \delta_i S(C_i)$ を最大化する。 **Algorithm 3**（ボトムアップ動的計画法）: 1. 全ての葉ノード $C_h$ に対し $\hat{S}(C_h) = S(C_h)$ と初期化し、全 $\delta_i = 1$ とする。 2. 最深レベルからボトムアップで処理する（根を除く）: - $S(C_i) < \hat{S}(C_{i_l}) + \hat{S}(C_{i_r})$ ならば $\hat{S}(C_i) = \hat{S}(C_{i_l}) + \hat{S}(C_{i_r})$ とし $\delta_i = 0$。 - そうでなければ $\hat{S}(C_i) = S(C_i)$ とし、$C_i$ の部分木の全クラスタを $\delta = 0$ に設定する。 ![[Campello-et-al-2013-HDBSCAN/fig02-optimal-cluster-selection.png|図2. クラスタツリーからの最適選択の図解]] 図2 の例では、$C_{10}$ と $C_{11}$ の組み合わせが $C_8$ より良いため $C_8$ は棄却されるが、$\{C_{10}, C_{11}, C_9\}$ は $C_5$ と比較して棄却され $C_5$ が残る。$\{C_4\}$ と $\{C_5\}$ は $C_2$ より良く、$C_3$ は $\{C_6, C_7\}$ より良い。最終的に $C_3$, $C_4$, $C_5$ のみが残り、最適解 $J = 17$ を与える。 計算量は $O(\kappa)$（$\kappa$ は簡約化ツリーのクラスタ数で、通常データオブジェクト数よりはるかに小さい）。 ## 新規性 HDBSCAN は以下の点で先行手法と明確に区別される。 - **OPTICS との違い**: OPTICS は到達可能性プロットの事後処理でクラスタツリーを抽出する手法を提案したが、臨界パラメータの選択に敏感で広く普及しなかった。Sander ら（2003）による改良版も、結果に大きく影響するヒューリスティクスと埋め込み閾値に依拠しており、局所カットによるフラット解の抽出は実質的に未解決であった（リーフクラスタを取る場当たり的手法のみ）。HDBSCAN は DBSCAN* を再定義し相互到達可能距離を通じて正確な階層を得る。 - **AUTO-HDS との違い**: AUTO-HDS のクラスタリング階層は HDBSCAN の階層の部分集合であり、幾何的比率 $r_{shave}$ で階層レベルをサンプリングする。このサンプリングにより、クラスタの安定性が過小評価されたりクラスタが見落とされたりする副作用がある。$r_{shave} \to 0$ とすればこの問題は防げるが、漸近計算量が $O(n^3)$ に増大する（HDBSCAN は $O(n^2 \log n)$）。AUTO-HDS の安定性尺度は、あるクラスタの安定性値が他の分岐のクラスタの密度や基数に影響される望ましくない性質を持つ。また、フラット解の抽出にも貪欲ヒューリスティクスを用い、全体安定性の観点から準最適な結果を返しうる。 ## 実験設定 - **データセット**: 9 個の個別データセットと 2 つのデータセットコレクション。 - 遺伝子発現データ: CellCycle-237（237 オブジェクト、4 クラス、17 次元）、CellCycle-384（384 オブジェクト、5 クラス、17 次元）、YeastGalactose（205 オブジェクト、4 クラス、20 次元）。ユークリッド距離（z スコア正規化、ピアソン相関と等価）。 - UCI データ: Wine（178 オブジェクト、3 クラス、13 次元）、Glass（214 オブジェクト、7 クラス、9 次元）、Iris（150 オブジェクト、3 クラス、4 次元）。ユークリッド距離。 - テキスト文書データ: Articles-1442-5（253 文書、5 クラス、388 次元）、Articles-1442-80（253 文書、5 クラス、4636 次元）、Cbrilpirivson（945 文書、5 クラス、1431 次元）。コサイン非類似度。 - ALOI コレクション: Amsterdam Library of Object Images に基づく。$k = 2, 3, 4, 5$ カテゴリを 100 回ランダム選択し各カテゴリから 25 画像をサンプリング（計 400 セット）。ALOI-TS88（テクスチャ統計量、88 次元）と ALOI-PCA（6 記述子から PCA 第1主成分の 6 次元結合）。ユークリッド距離。 - **比較対象**: OPTICS(AutoCl)、AUTO-HDS。全手法で $m_{pts} = 4$（AUTO-HDS では $n_{\varepsilon}$、OPTICS では MinPts に相当）。AUTO-HDS は $r_{shave} = 0.03$、$n_{part} = m_{pts} - 1$。HDBSCAN は $m_{clSize} = m_{pts}$。 - **評価指標**: 全体 F 値（FScore）、調整ランド指数（ARI）、クラスタに割り当てられたオブジェクトの割合（%covered）。 ## 実験結果 ![[Campello-et-al-2013-HDBSCAN/table01-results.png|表1. 全データセットの結果]] 主要な結果は以下のとおりである。 - HDBSCAN(EOM) は大多数のデータセットで他の 2 手法を上回り、多くの場合に大差をつけた。ほぼ全ての場合で、高い FScore・ARI を維持しながらより大きな%covered を達成した。 - Wine では ARI 0.29（対 OPTICS 0.16、AUTO-HDS 0.12）、Iris では ARI 0.57（対 0.33、0.11）と大幅に優位であった。 - Cbrilpirivson では ARI 0.19 / FScore 0.47 と、OPTICS(AutoCl) の ARI 0.01 / FScore 0.07 および AUTO-HDS の ARI 0.04 / FScore 0.21 を大きく上回った。 - HDBSCAN(EOM) が最良でなかった唯一のケースは YeastGalactose で、ARI 0.94（OPTICS の 0.96）であったが、FScore は 0.97 で OPTICS と同等であった。 - CellCycle-384 では OPTICS(AutoCl) が%covered 100%を達成したが ARI は 0 であり、意味のないクラスタリングであった。HDBSCAN の ARI 0.35 / FScore 0.50 / %covered 47%が実質的に最良であった。 - ALOI-TS88 および ALOI-PCA コレクションでは対応 t 検定（$\alpha = 0.01$）により、全ての手法ペア間の性能差が統計的に有意であることが確認された。HDBSCAN(EOM) は ALOI-TS88 で ARI 0.63 / FScore 0.79、ALOI-PCA で ARI 0.72 / FScore 0.85 と、他の手法を有意に上回った。 ## 考察 HDBSCAN は密度ベースクラスタリングの 5 つの根本的限界（単一閾値、簡約化なし、グローバルカットのみ、特定問題限定、多パラメータ）を全て同時に解消する手法として独自の位置を占める。実験結果は、クラスタ安定性に基づく最適抽出が、ヒューリスティクスベースの手法よりもロバストかつ高品質な結果を返すことを示している。$m_{pts}$ への頑健性も確認されており（異なる $m_{pts}$ 値での追加実験でも類似の結果が得られた）、この単一パラメータが密度推定の古典的平滑化因子として挙動が十分に理解されている点も実用上の利点である。 ## 強み / 弱点・課題 **強み**: - 単一パラメータ $m_{pts}$ のみで動作し、このパラメータは密度推定の平滑化因子として挙動が理解されている。 - DBSCAN* の再定義により密度レベルセットとの理論的整合性を確保し、HDBSCAN 階層との正確な関係を確立した。 - クラスタ安定性の最適化問題を定式化し、大域最適解を $O(\kappa)$ の動的計画法で効率的に求める。 - 任意の距離関数を持つ一般的なデータ空間に適用可能であり、実座標空間やネットワークに限定されない。 - 広範な実世界データにおける実証的優位性が統計的に有意に示された。 **弱点・課題**: - 全体の計算量は $O(dn^2)$ であり、大規模データセットへの直接適用にはスケーラビリティの課題がある（MST 構築がボトルネック）。 - 論文中の実験は比較的小規模なデータ（最大 945 オブジェクト）に限られており、大規模データでの検証が不足している。 - 半教師あり学習との統合やサブスペースの考慮が今後の課題として挙げられているが、本論文では未対応である。 - 境界オブジェクトの排除（DBSCAN*）は理論的には正当だが、実応用では境界領域のオブジェクトに対するラベル情報が失われるトレードオフがある。 ## 出典 - (Source: [[@2013__PAKDD__Density-Based Clustering Based on Hierarchical Density Estimates]])