Class Angular Distortion Index for Dimensionality Reduction

以下は、Gunaratne、Kobourov、および Miller による論文「Class Angular Distortion Index for Dimensionality Reduction」の詳細な技術的サマリーです。

1. 問題提起

次元削減（DR）手法（t-SNE、UMAP、PCA など）は、高次元データの可視化に不可欠です。しかし、現在の DR 評価における重大な限界は、クラスター間の関係性の誤った表現にあります。

• 核心的な課題: 多くの DR 手法はクラスターを分離し（明確な「塊」にする）、成功していますが、これらのクラスター間の大域的な幾何学的関係を歪める傾向があります。例えば、ネストされた構造、曲がった多様体、または絡み合ったクラスターが、射影において平坦化されたり、恣意的に再配置されたりします。
• 既存の指標の限界: 現在の品質指標は、これらの歪みを捉えられていません。これは、誤った仮定に依存しているためです。
  • 分離性の仮定: シルエットスコアや Davies-Bouldin 指数などの指標は、クラスターがコンパクトで球状、かつ明確に分離されていると仮定しています。これらは、真のトポロジカル構造を破壊する場合（例：ネストされた球を別々の円に変える場合）でも、密で孤立した「塊」を作成する射影を評価してしまいます。
  • 重心バイアス: ラベル信頼性と連続性（Label-T&C）などの指標はクラスター重心に依存しています。クラスターが重なり合っているか、ネストされている場合（重心が一致する）、これらの指標は忠実な射影とランダムな射影を区別できません。
  • 点対点 vs クラスターレベル: ほとんどの指標は点対点またはペアごとの距離を評価しており、点のグループ間の高次幾何学的関係を見落としています。

2. 手法：クラス角歪み指数（CADI）

著者らは、内部角度を用いてクラスター間の幾何学的関係の保存を評価するために設計された新しい指標、CADIを提案します。

中核的概念

重心や個々の点間の距離を測定する代わりに、CADI は、参照点が 1 つのクラスに属し、他の 2 つの点が異なるクラスに属する 3 点の組によって形成される内部角度を測定します。

• 直感: クラス $C_a$ のある点からクラス $C_b$ がどのように「見えるか」（角度 $\angle jik$ を通じて）を観察することで、この指標はクラスターの形状と相対的な向きを捉えます。
• 微分可能性: 角度の余弦類似度に依存するため、CADI は微分可能であり、最適化のための損失関数として使用できます。

数学的定義

クラス分割 $C$ を持つデータセット $X$ と射影 $Y$ が与えられたとき：
$$\text{CADI}(X, Y, C) = \frac{1}{T} \sum_{i \in C_a, j,k \in C_b, j \neq k} \left( \cos(\theta_X(j,i,k)) - \cos(\theta_Y(j,i,k)) \right)^2$$
ここで：

• $i$ はクラス $C_a$ に属する参照点です。
• $j, k$ は異なるクラス $C_b$ に属する点です。
• $\theta$ は、$j$ と $k$ へのベクトルによって形成される、$i$ における内部角度を表します。
• $T$ はサンプリングされた 3 点の組の総数です。
• 目的: CADI を最小化する（0 に近いほど良い）。

実用的な実装

• サンプリング: 完全な和を計算すると $O(n^3)$ となります。著者らは、$k = O(n)$ の 3 点の組（具体的には $40n$）をサンプリングすることで、無視できる分散で安定した結果が得られ、指標がスケーラブルになることを示しています。
• 不変性: CADI は角度のみに依存するため、並進、回転、および一様スケーリングに対して不変です。
• AngleEmbedding: 著者らは、CADI を損失関数として使用する新しい DR アルゴリズム、AngleEmbeddingを導入しました。これは、パラメトリックなニューラルネットワーク（フィードフォワードネットワーク）を通じて最適化され、クラスター間の角関係特に保存する射影を生成します。

3. 主要な貢献

1. 新しい指標（CADI）: 既存の指標の「球状性」や「分離性」の仮定を超えた、クラスターレベルの品質指標です。これは特に、ネストされた、曲がった、または絡み合ったクラスターのような複雑な構造の保存を標的としています。
2. 失敗モードの証明: 既存の指標（シルエット、Label-T&C など）が、複雑なトポロジを忠実に保存する射影よりも、ランダムな射影や「塊」の射影を高く評価する傾向があることを示す広範な証拠を提供しています。
3. AngleEmbedding アルゴリズム: CADI を最適化する新しい教師あり DR 手法であり、この指標が高忠実度な射影の生成を効果的に駆動できることを実証しています。
4. 包括的なベンチマーク評価: ネストされた球体、リング、遺伝子発現、テキストデータなどを含む 20 以上の合成データおよび実世界データセットにおいて、CADI を他の 8 つの指標および 8 つの DR アルゴリズムと比較して評価を行いました。

4. 結果

評価は、CADI と既存の指標の間に大きな不一致があることを浮き彫りにしました。

• 合成データ（ネストされた球体とリング）:
  • シナリオ: データは 5 つのネストされた球体、または連鎖した相互に絡み合ったリングで構成されています。
  • 既存の指標: シルエットスコアや Label-T&C は、リングを別々の塊に分解したり球体を散らしたりするt-SNEやUMAPを最良と評価するか、あるいは重心が重なるためランダム射影を高く評価することが多いです。
  • CADI: トポロジを破壊する手法に最悪のスコアを割り当てる一方で、線形またはネストされた順序を保存するAngleEmbeddingやPCAを最良と正しく識別します。
• 実世界データ（肝臓、USPS、TREC）:
  • 肝臓データ: がん細胞（HCC）は健康な細胞よりも分散が大きいです。t-SNE は等しいサイズの分離した塊を作成し、この分散を隠蔽します。CADI は、HCC クラスターがより広がっていることを正しく示すAngleEmbeddingとPCAを評価します。
  • USPS（数字）: クラスターのサイズは数字によって大きく異なります。t-SNE は等しいサイズのクラスターを強制します。CADI は、クラスターサイズが真のデータ分布を反映している射影（AngleEmbedding によって保存される）を評価します。
  • 相関: CADI は他の指標との相関が低く（例：シルエットとのスピアマン相関は約 0.24）、射影の品質の異なる側面を測定していることを確認しています。
• ハイパーパラメータ調整: CADI は UMAP のハイパーパラメータ選択を導くために成功裏に使用され、視覚的な検査が曖昧であっても大域的構造をよりよく保存する構成を特定しました。

5. 意義と結論

• パラダイムシフト: 本論文は、クラスター関係の分析（階層、ネスト、または大域的トポロジの理解など）を伴うタスクにおいては、現在の「分離性重視」の指標が誤解を招くものであると主張しています。CADI は構造的忠実度を評価するための必要な代替手段を提供します。
• ツールの選択: 著者らは適切な使用ケースを明確にしています。
  • クラスターの数を特定すること、または初期探索が目的であれば、t-SNE/UMAPを使用してください。
  • クラスターがどのように互いに関連しているか、それらの相対的な位置、および幾何学的形状を理解することが目的であれば、CADI/AngleEmbeddingを使用してください。
• 将来の課題: 著者らは、AngleEmbedding を非ユークリッド空間（球面、双曲面など）に拡張し、角度誤差の集約に関するさらなる理論的検討を行うことを提案しています。

要約すると、CADIは、クラスター間幾何学の歪みを定量化することで、次元削減評価における重要な盲点を解消し、複雑で非球状のデータ構造を扱う分析家にとってより信頼性の高い指針を提供します。