Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance

技術要約：階層的クラスタリングは、豊饒性、一貫性、およびスケール不変性を同時に満たすことができる

問題提起
クラスタリングには、普遍的に受け入れられた「クラスター」の定義が欠如しており、この困難さはクラインバーグの不可能性定理（Kleinberg, 2002）によって定式化されている。この定理は、フラットなクラスタリング手法（非類似度を単一の分割へと写像するもの）が、スケール不変性（測定単位に依存しない）、豊饒性（適切な入力があればあらゆる可能な分割を生成できる能力）、および一貫性（クラスター内の類似性を強め、クラスター間の非類似性を弱めても出力される分割が変わらないという性質）という3つの自然な公理を同時に満たすことはできないことを示している。この緊張関係は、一貫性がクラスター内に新たな部分構造の作成を許容する一方で、フラットな分割ではその公理を破ることなくその表現ができないことから生じる。

本論文では、出力がフラットな分割ではなく、階層（入れ子状のクラスター集合）である場合に、この不可能性が持続するかどうかを調査している。著者らは、階層的なクラインバーグの公理の類似体（analog）を、同時に満たすことができるかを問うている。

方法論と定義
著者らは、階層的クラスタリング手法を、非類似関数の集合 $D(X)$ から階層の集合 $T(X)$ への写像 $T$ として定義する。ここで、階層とは、$X$ 全体とすべてのシングルトン（単一要素集合）を含む、ラミナー（層状）なクラスターの族である。著者らは、階層的クラスタリングのための4つの公理を定式化している：

1. スケール不変性： 任意のスケール因子 $\beta > 0$ に対して、$T(\beta d) = T(d)$ である。
2. 分割の豊饒性： すべての分割 $\mathcal{C}$ に対して、$\mathcal{C} \subseteq T(d)$ となるような非類似度 $d$ が存在する。（注：階層は、その分割をクラスターのサブセットとして含んでいなければならない。）
3. 分割の一貫性： もし分割 $\mathcal{C}$ が $T(d)$ に含まれており、$d'$ が $d$ の $\mathcal{C}$-強化（クラスター内の距離が減少し、クラスター間の距離が増加すること）であるならば、$\mathcal{C} \subseteq T(d')$ である。
4. 置換不変性： 出力は、点のラベル付けではなく、非類似の構造にのみ依存する。

これら4つすべてを満たす手法を**適格（admissible）**と呼ぶ。また、**超距離度における厳密性（exactness on ultrametrics）**という、より強い条件についても検討している。これは、入力が超距離度である場合、その手法がそれに関連付けられた標準的な階層を復元することを要求するものである。

主要な貢献と結果

1. 適格性の達成可能性
フラットなクラスタリングの設定とは対照的に、著者らは適格な階層的手法が存在することを証明している。実際、これらには無数に存在する。

• 明示的な構成： 本論文は、いくつかの適格な手法を構築している：
  • 非バイナリ・シングル・リンケージ ($T_{SL}$)：標準的なバイナリ・シングル・リンケージとは異なり、タイ（同値）となったクラスターを同時に結合する非バイナリ版は適格である。
  • 分離手法（Separation Methods）：グローバルおよびローカルな分離マージンに基づく、2つの手法のファミリー $T_{glob}^\eta$ および $T_{loc}^\eta$。これらは、内部の非類似度が外部の非類似度に対して十分に小さいクラスターを定義する。
  • ブライアント＝ベリー安定クラスター ($T_{stable}$)：組合せ論的な安定性基準に基づく手法、およびその冪乗変換のバリアント $T_{stable}^{(p)}$。
• 他のリンケージにおける不可能性：完全（complete）、平均（average）、ウォード（Ward）、セントロイド（centroid）、およびメディアン（median）リンケージの非バイナリ版は、少なくとも一つの公理に違反することが示されている。

2. 適格な手法の構造的分析
適格な手法の集合 $H_{\alpha_{adm}}(X)$ は、洗練順序（refinement order）（$T_1 \sq \sq T_2$ とは、すべての $d$ に対して $T_1(d) \subseteq T_2(d)$ であること）の下で分析されている。

• 多様性： この集合は、**非可算な高さ、幅、および細胞性（cellularity）**を持つ半順序集合（poset）を形成する。
• 最大要素の不在： すべての手法を精緻化する単一の「最も精緻な」適格な手法は存在しない。
• 不適合性： 互いに**不適合（incompatible）**な（他の適格な手法によって共同で精緻化されることのない）最大要素が、非可算に存在する。具体的には、ファミリー $\{T_{stable}^{(p)} : p > 0\}$ は強力な上方反鎖（upward antichain）を形成する。
• 共通のバックボーン： この多様性にもかかわらず、公理は非自明な共通構造を強制する。すべての適格な手法は、十分に分離されたクラスターの階層（あるマージン列 $\eta$ に対する $T_{glob}^\eta$）を精緻化する。さらに、任意の有限個の適格な手法は、共通のバックボーンを共有する。
• 最小要素の不在： 自明な手法（シングルトンとルートのみを返すもの）は、全階層的手法の下限（infimum）であるが、分割の豊饒性を満たさないため適格ではない。したがって、適格なクラスには最小要素が存在しない。

3. 強適格性と超距離度
超距離度における厳密性の公理が追加されると、クラスは**強適格（strongly admissible）**となる（$H_{\alpha_{adm}^+}(X)$）。

• このクラスは依然として非可算であり、最大要素の多様性を保持している。
• 決定的なことに、通常の適格なクラスとは異なり、強適格なクラスには最小要素が存在する：$T_{glob}$（マージン列 $\eta = \mathbf{1}$ を持つ手法）。これにより、最も粗い強適格な手法が得られる。

4. 前処理と合成
本論文では、クラスタリングの前に適用される前処理変換 $\mu: D(X) \to D(X)$ について研究している。

• 保存条件： 変換が公理を保存するための一般的な条件（例：スケーリングが $\mu$ と可換であること、強化が強化へと写されること）を導出している。
• 例：
  • ミニマックスパス（劣ドミナント超距離度）：非類似度をその劣ドミナント超距離度へと写す変換 $B^*$ は、スケール不変性、置換不変性、および超距離度厳密性を保持する。これにより、分解 $T_{SL} = T_{glob} \circ B^*$ が導かれ、シングル・リンケージが超距離度変換と分離手法の合成であることを示している。
  • PCAおよびHDBSCAN：PCAおよび相互到達性（mutual-reachability）の前処理を分析し、それらがスケール不変性と置換不変性を保持するものの、一般に豊饒性や一貫性を保持することはないことを示している。

意義
本論文は、クラインバーグの公理を満たすことが不可能であるという根本的な問題は、出力をフラットな分割に限定したことによるアーティファクト（副産物）であることを示している。出力を階層的なものに変えることで、これらの公理は共同で充足可能となり、広大な適格な手法のランドスケープへの道が開かれる。

この研究は、適格な手法の空間が極めて多様である（唯一の最適解が存在しない）一方で、全く無構造ではないことを明らかにしている。公理は、すべての適格な手法が尊重しなければならない「保守的」なバックボーン（十分に分離されたクラスター）を強制する一方で、より微細な構造をどのように解決するかについては自由を与えている。これは、階層的クラスタリングにおけるトレードオフを理解するための原理的な枠組みを提供し、特定のメソッドの選択が、基本的な公理の違反ではなく、ノイズに対する感度と出力の粒度の間のバランスの設計に依存していることを示唆している。

著者らは、この枠組みがCarlssonおよびMémoli (2010) や AckermanおよびBen-David (2016) の先行研究と関連していると述べているが、本研究は重みなしの階層に焦点を当て、クラインバーグの一貫性公理の全強度を保持することで、単一のアルゴリズムの特性化ではなく、より広範で多様なメソッドのクラスを実現している点で異なっている。