# クラスタ安定性 ## 定義 クラスタ安定性（cluster stability）とは、密度ベースクラスタリングにおいてクラスタの有意性を定量化する概念である。Hartigan のモデルに基づき、確率密度関数 $f(x)$ の密度等高線クラスタ（density-contour cluster）を密度レベル $\lambda$ に対するレベルセット $\{x \mid f(x) \ge \lambda\}$ の極大連結部分集合として定義する。密度レベルを上げるにつれてクラスタは縮小し、やがて分割または消滅する。より有意なクラスタは出現後により長く「生存」する。この生存の持続性を定量化したものがクラスタ安定性である。(Source: [[@2013__PAKDD__Density-Based Clustering Based on Hierarchical Density Estimates]]) **超過質量**（excess of mass）は Müller・Sawitzki（1991）に由来する概念で、密度等高線クラスタ $C_i$ が密度レベル $\lambda_{min}(C_i)$ で出現するとき、以下で定義される。 $E(C_i) = \int_{x \in C_i} \left( f(x) - \lambda_{min}(C_i) \right) dx$ 超過質量は階層の分岐に沿って単調に増加するため、入れ子クラスタ間の安定性比較には適さない。この限界を克服するため、Campello ら（2013）は**相対超過質量**（relative excess of mass）を導入した。 $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$ が分割または消滅する密度レベルである。相対超過質量はクラスタの「自身のレベル範囲」における質量のみを測るため、親クラスタと子クラスタの比較が可能となる。(Source: [[@2013__PAKDD__Density-Based Clustering Based on Hierarchical Density Estimates]]) ## HDBSCAN における定式化 有限データセット $X$ に対して、クラスタ $C_i$ の安定性 $S(C_i)$ は以下で定義される（Equation 3）。 $S(C_i) = \sum_{x_j \in C_i} \left( \frac{1}{\varepsilon_{min}(x_j, C_i)} - \frac{1}{\varepsilon_{max}(C_i)} \right)$ $\varepsilon_{max}(C_i)$ はクラスタ $C_i$ が出現する最大の $\varepsilon$ 値、$\varepsilon_{min}(x_j, C_i)$ はオブジェクト $x_j$ がクラスタ $C_i$ に属さなくなる $\varepsilon$ 値に対応する。 この安定性尺度に基づき、簡約化クラスタツリーから最適なフラット分割を抽出する問題が定式化される（Problem 4）。目的は、葉から根への各パスでちょうど 1 つのクラスタが選択されるという制約の下で、選択クラスタの安定性の総和 $J = \sum_{i=2}^{\kappa} \delta_i S(C_i)$ を最大化することである。 Algorithm 3 はこの問題をボトムアップ動的計画法で解く。各内部ノード $C_i$ について、$C_i$ 自身の安定性 $S(C_i)$ と子ノードの累積安定性 $\hat{S}(C_{i_l}) + \hat{S}(C_{i_r})$ を比較し、大きい方を採用する。計算量は $O(\kappa)$（$\kappa$ はクラスタ数）であり、大域最適解が保証される。(Source: [[@2013__PAKDD__Density-Based Clustering Based on Hierarchical Density Estimates]]) AUTO-HDS の安定性尺度との相違点として、HDBSCAN の安定性は各クラスタの分岐内で完結するのに対し、AUTO-HDS では他の分岐のクラスタの密度や基数が安定性値に影響するという望ましくない性質がある。(Source: [[@2013__PAKDD__Density-Based Clustering Based on Hierarchical Density Estimates]]) ## 横断的知見 - 1 ソース目のため、他のソースとの突き合わせによる知見は今後の蓄積に委ねる。 ## 未解決の問い - クラスタ安定性尺度は密度推定の精度にどの程度依存するか。$m_{pts}$ の変化に対する安定性値のロバスト性は実証されているが、理論的な保証は本論文では未提供である。 - 相対超過質量以外の安定性尺度（たとえば情報理論的尺度やパーシステントホモロジーに基づく尺度）との理論的・実験的比較は行われていない。 - 非球形や非凸なクラスタに対する安定性尺度の振る舞いについて、体系的な分析が不足している。 ## 関連 - [[@2013__PAKDD__Density-Based Clustering Based on Hierarchical Density Estimates]] — HDBSCAN 原論文 - [[密度ベースクラスタリング]] — 上位概念 - [[時系列クラスタリング]] — 関連概念 ## 出典 - [[@2013__PAKDD__Density-Based Clustering Based on Hierarchical Density Estimates]]