Unifying Information-Theoretic and Pair-Counting Clustering Similarity

技術要約：情報理論的クラスタリング類似度とペア計数クラスタリングの統一

問題提起
クラスタリングの比較は、教師なしモデルを評価する上で不可欠であるが、実務家はしばしば異なる類似度指標間の重大な不一致に直面する。現在、この分野は2つの支配的な家族に分かれている。一つは、順序のない要素のペアに関する一致を評価するペア計数尺度（例：ランド指数、調整ランド指数、ジャカード指数）であり、もう一つは、共起の分割表全体にわたる依存性を集計する情報理論的尺度（例：相互情報量、情報の変分）である。これらの家族は、同一の分割に対して異なる結論を導き出すことが多く、解釈を不明瞭にしている。先行研究では、公理的な差異や幾何学的な局所的等価性が特定されてきたが、なぜこれらの尺度が乖離するのか――具体的には、その重み付けの原理とサンプリング空間に関して――を説明する統一的な解析的枠組みが欠けていた。

手法
本論文は、共通の独立性ベースラインと、それらの基礎となる数学的構造の拡張を通じて、これら2つの家族を統一する解析的枠組みを開発する。

1. 独立性付近における残差展開：
   著者らは、2つのクラスタリングが独立であるという中立的な参照モデルを定義し、それは期待確率 $p_{ij}^{ind} = p_{i\cdot}p_{\cdot j}$ によって特徴付けられる。このベースラインからの偏差を、残差 $\delta_{ij} = p_{ij} - p_{i\cdot}p_{\cdot j}$ を用いて分析する。

• 相互情報量 (MI): 本論文は、独立性ベースラインの周囲におけるMIの厳密なテイラー展開を導出する。その主要項は、周辺的に重み付けされた二次形式 ($\sum \delta_{ij}^2 / (p_{i\cdot}p_{\cdot j})$) であり、これはピアソンの $\chi^2$ 統計量に対応する。この重み付けは、期待質量が小さいセル（稀な交差）における偏差を強調する。
• ペア計数指標 (例：ランド指数): ランド指数は、周辺的なベースライン（偶然の一致）と残差項に分解される。残差成分は、重み付けのない二次形式 ($\sum \delta_{ij}^2$) と線形整列項の和であることが示される。MIとは異なり、ペア計数尺度は期待質量で除算しないため、大きなクラスターに支配され、マイノリティ・クラスターにおける一貫した整列を過小評価する。

2. 高次タプルへの拡張：
   著者らは、ペア計数の枠組みを、順序のないペアから$k$-タプルへと拡張する。彼らは、**衝突確率（collision probabilities）**の階層を導入する。これは、$k$ 個の独立にサンプリングされた要素が同じクラスター（または同じ分割セル）に入る確率として定義される。

• $k=2$ の場合、これらは標準的なペア計数量を回収する。
• $k > 3$ の場合、彼らはレニー・エントロピー対比 $I^{(k)}$ の一族を定義し、これは$k$要素の共割当ての一致に基づいた一致を測定する。
  これによって、ペア計数が、レニー・エントロピーへとつながるより広範な階層における「次数2」のケースであることが示され、グループレベルの一貫性をテストするための、より厳格なテストを提供する。

3. 要素中心の接続：
   本論文は、このタプル計数の階層を、アフィニティグラフ上のランダムウォークに基づく要素中心の類似性と結びつける。彼らは、厳密な分割において、$k$-タプルの衝突確率が、$k$ ステップの間クラスター内に留まるランダムウォークの確率に対応することを示し、サンプリング階層の幾何学的解釈を提示する。

主な貢献

• 解析的架け橋: 本論文は、両方の情報理論的尺度とペア計数尺度が、同じ分割表の残差の関数であり、主にその重み付けスキーム（確率重み付き vs 重みなし）とサンプリング空間（単一要素 vs 順序のないペア）において異なっていることを示す厳密な導出を提供する。
• 一致の階層: ペア計数が、レニー・エントロピーに関連する、より広範な衝突計数階層（$k$-タプル）の次数2のメンバーであるという事実を確立する。
• 乖離の解釈可能性: 指標を分解することで、指標間の不一致（例：RI vs MI）が恣意的なものではなく、明示的な数学的選択、すなわち、大きなクラスターの広範な重複を強調するか、あるいは小さなクラスターにおける鋭く体系的な整列を強調するか、という点に由来することを説明する。

結果
制御された合成例を通じて、本論文はこれらの理論的な違いがもたらす実用的な影響を実証する。

• 均衡なクラスター: クラスターサイズが均衡しており、ノイズが対称的である場合、各尺度は一致する傾向がある。これは、重み付けの違いが微々たるものになるためである。
• 不均衡なクラスター: 強力なクラス不均衡の下では、各尺度は著しく乖離する。
  • 小・小の不一致: 2つの小さなマイノリティ・クラスター間で要素が入れ替わった場合、情報理論的尺度（MI）は急激に低下する。これは、MIが期待質度の逆数によって偏差を重み付けするためである。ペア計数尺度（ARI）は、大きなクラスターに支配されているため、比較的安定している。
  • 大・小の不一致: 大きなクラスターと小さなクラスターの間で要素が入れ替わった場合、すべての尺度が低下するが、残差分析によれば、ペア計数尺度は大きなクラスターの破壊に伴う重みなしの二次項によって駆動される。
• 高次感度: $k$-タプル対比 ($I^{(k)}$) は、ペア計数尺度 ($I^{(2)}$) が（ペア数が同一であれば）拡散した重なりと集中した重なりの区別ができない一方で、高次のタプル ($I^{(3)}$ など) は、ペアの一致がコヒーレントなグループレベルの構造によって支持されているかどうかを検出できることを示している。

意義と主張
本論文は、この統一が、指標間の不一致を「厄介なもの」から、各尺度が強調するクラスタリング構造に関する解釈可能な証拠へと変貌させると主張している。

• 著者らは、「唯一の最良の尺度」は存在しないと論じている。むしろ、タスクに応じて指標を選択すべきである。ペア計数は、大きく均質なグループ間の粗い一致を要約するのに適している。情報理論的尺度は、小さくとも体系的な整列やマイノリティのサブタイプを検出するのに優れている。高次のタプル要約は、ペアの一致がコヒーレントなグループへと拡張されているかをテストするための、中間的な領域を提供する。
• 本フレームワークは、正規化、チャンス補正、およびサンプリングの変動性を、共通の理論的構造内の調整可能なレジームとして再構成し、実務家が経験的な試行錯誤ではなく、第一原理に基づいて指標を選択できるようにする。
• 著者らは、残差展開は独立性ベースラインの付近で最も透明性が高いこと、および高次のタプル計数は有限サンプルにおける疎性に苦しむ可能性があることを控えめに述べており、有限サンプル補正や、オーバーラップまたはソフトクラスタリングへの拡張といった将来の研究を示唆している。