A Deterministic Information Bottleneck Method for Clustering Mixed-Type Data

技術要約：混合型データのための決定論的情報ボトルネック法

問題提起
連続変数とカテゴリ変数（名義変数および順序変数）の両方で構成されるデータセットである混合型データのクラスタリングは、変数の型の異質性により、重大な課題を提示する。K-Prototypes、KAMILA、および距離ベースのアプローチ（Gowerの非類似度を用いたPAMなど）といった既存の手法は解決策を提供しているものの、これらは多くの場合、セントロイドに基づく仮定や特定の距離指標に依存しており、不均質なデータの潜在的な情報構造を十分に捉えきれない可能性がある。さらに、多くの既存のアプローチは、クラスター構造を不明瞭にし次元を増大させる可能性があるワンホットエンコーディングのような広範な前処理を必要とせずに、連続、名義、および順序変数を自然に扱う統一された理論的枠組みを欠いている。

手法：DIBmix
本論文は、混合型データを扱うために拡張された決定論的情報ボトルネック（DIB）フレームワークに基づくクラスタリングアルゴリズムであるDIBmixを提案している。核心となる目的は、圧縮制約の下で、混合属性空間におけるデータの位置 $Y$ との相互情報量を最大化するような、入力データ $X$ の圧縮表現 $T$（クラスター）を見つけることである。

主な手法構成要素は以下の通りである：

1. 一般化積カーネル： 混合データに対する結合密度 $p(x, y)$ を推定するために、著者らは一般化積カーネルを採用している。これは以下を統合したものである：

   • 連続変数のためのガウスカーネル
   • 名義変数（順序のないカテゴリ変数）のためのAitchison & Aitkenカーネル
   • 順序変数（順序のあるカテゴリ変数）のためのLi & Racineカーネル
     このアプローチは、変数の独立性を仮定することを避け、カーネル積をロバストな密度推定のための重み付けメカニズムとして使用する。

2. 最適化フレームワーク： アルゴリズムは、目的関数 $H(T) - \beta I(Y; T)$ を最小化することを目指す。ここで、$H(T)$ はクラスター割り当てのエントロピー（クラスターサイズの正則化として機能する）であり、$I(Y; T)$ はクラスターとデータの位置との間の相互情報量である。パラメータ $\beta$ は、圧縮と関連性の間のトレードオフを制御する。

3. 適応的ハイパーパラメータ選択：

   • バンド幅選択： 連続変数とカテゴリ変数の寄与を等しくするための体系的な戦略が提案されている。これには、連続変数のための平均最遠近傍カーネル比率や、カテゴリ変数のための不一致比率を定義し、単一の変数タイプが類似度行列を支配しないようにバンド幅を調整するプロセスが含まれる。
   • 適応的 $\beta$： 標準的なDIBの実装では $\beta$ が固定されているのに対し、DIBmixは各反復において正則化パラメータ $\beta$ の適応的更新スキームを採用している。これにより、データに不均衡なクラスターサイズが含まれている場合でも、最小のクラスターが消失するのを防ぎ、正確に $C$ 個の空でないクラスターを持つ解への収束を保証する。

4. スケーラビリティ： 大規模なデータセットに対して、本手法はNyström近似を利用して、完全な類似度行列を構築する計算複雑度を $O(n^2)$ から $O(n\sqrt{n})$ に削減し、大規模なアプリケーションへの適用を可能にしている。

主な貢献
本論文は、主に3つの貢献を述べている：

1. フレームワークの拡張： 次元削減やワンホットエンコーディングを必要とせずに、混合型データ（連続、名義、順序）をネイティブに扱うためにDIBフレームワークを適応させた。
2. 体系的なハイパーパラメータ戦略： 変数の寄与をバランスさせ、あらかじめ定められた数のクラスターへの有効な分割を保証するために、バンド幅と正則化パラメータ $\beta$ を選択する方法を提案し、不均衡なクラスターサイズの問題に対処した。
3. 包括的な評価： 広範なシミュレーションと実世界のデータセットを用いて、DIBmixを4つの確立された手法（KAMILA、K-Prototypes、FAMDを用いたK-Means、およびGowerの非類似度を用いたPAM）と比較検証した。

結果
DIBmixの性能は以下を通じて評価された：

• シミュレーション： サンプルサイズ、クラスター数、変数の割合、重なりレベル、およびクラスターの形状を変化させた28,800個の合成データセットが生成された。
  • DIBmixは、競合手法と比較して、最も高い中央値の調整ランド指数（ARI）および調整相互情報量（AMI）を達成した。
  • 特に不均衡なクラスターサイズおよび低〜中程度のクラスターの重なりがあるシナリオにおいて、高い堅牢性を示した。
  • 効果量（偏 $\eta^2$）は、DIBmixが競合他社を一貫して上回っていることを示しており、その値は0.32から0.99の範囲であった。
• 実世界ベンチマーク： 本手法は、公開されている10個のUCIデータセットに対してテストされた。
  • DIBmixは、10個のデータセットのうち4つで最高のARIを達成した。
  • 変数のタイプがバランスよく混在しているデータセットにおいて、最高の性能を発揮した。
  • どちらか一方の変数タイプが圧倒的に支配的なデータセットにおいては、FAMDやK-Prototypesよりもわずかに低いものの、競争力のある性能を示した。
  • 10個のデータセットに対するフリードマン検定の結果、DIBmixは最高の平均ランク（2.45）を示したが、データセットの少なさとクリティカル・ディファレンス（臨界差）の閾値により、統計的有意性には達しなかった。

意義および主張
著者らは、DIBmixが混合型データのための理論的根拠に基づいた代替案を確立すると主張している。その意義は以下の点にある：

• 不均衡への対処： 同等のサイズのクラスターを好む傾向がある従来のセントロイドベースのアルゴリズムとは異なり、DIBmixのエントロピーベースの目的関数は、高度に不均衡なクラスターサイズを許容し、効果的に扱うことができる。
• 理論的厳密性： 情報ボトルネック原理を利用することで、本手法はデータを圧縮しながら関連する情報を抽出するための原理的な方法を提供し、距離ベースまたはモデルベースのアプローチとは異なる視点を提供する。
• 解釈可能性： このフレームワークは、相互情報量を通じて変数の重要性を定量化することを可能にし、どの特徴量がクラスタリング構造を駆動しているかを特定するのに役立つ（例：前立腺癌データセットにおける臨床的に関連のあるバイオマーカーの特定）。

本論文は、DIBmixは極めて競争力があり、特に真に混合されたデータに対して堅牢であるものの、一方の変数タイプが圧倒的に支配的なデータセットにおいては最適ではない可能性があると結論付けている。著者らは、極端なシナリオにおけるバンド幅選択やクラスターの均質性の仮定に関する限界を認め、今後の研究としてローカルバンド幅や外れ値への堅牢性の探索を提案している。