Measuring Distortion in the Empty Regions of Dimensionality Reduction Scatterplots with the Gap Index

技術要約：ギャップ指数（Gap Index）による次元削減散布図の空領域における歪みの測定

問題提起
次元削減（DR）は高次元データの可視化に不可欠であるが、データが2次元多様体上に存在しない限り、あらゆる投影には歪みが伴う。品質指標は存在するものの、既存の一般的な指標（例：ストレス、信頼性、連続性）は、主に点同士の関係（ペアワイズ距離や近傍関係など）の保存に焦点を当てている。これらの指標は、「空領域」や点と点の間の「隙間（ギャップ）」における歪みを捉えることができないことが多い。しかし、これらの空白領域は視覚的に極めて重要であり、クラスター間の分離やユーザーが知覚する全体的な構造を定義するものである。その結果、指標が「高品質（低歪み）」と報告していても、投影が偽のパターンや誤解を招く分離を生み出している可能性があり、これが視覚的分析における過信につながる。

手法：ギャップ指数（Gap Index, GI）
著者らは、2次元投影内の空領域における歪みを定量化するために設計された品質指標である、ギャップ指数（GI）を提案する。GIは、空間を三角形に分解し、その変形を高次元空間と比較することで機能する。計算プロセスは以下のモジュール化されたパイプラインに従う：

1. 三角形分割（Triangulation）： 2次元投影を、ドロネー三角形分割を用いて重なりのない三角形の集合に分割する。この手法は、計算効率（$O(N \log N)$）、データの凸包をカバーする能力、および細長く数値的に不安定な三角形を回避するという特性から採用されている。
2. 三角形の変形（Triangle Deformation）： 2次元投影における各三角形 $t_i$ に対して、同じ3つの頂点を用いることで、高次元空間における対応する三角形 $\hat{t}_i$ を特定する。変形は、これら三角形の相対面積を比較することによって計算される。
   • 相対面積は、各空間における全三角形の面積の合計に対する当該三角形の面積の比として定義される。この正規化により、指標はスケール不変性を確保する。
   • 変形値 $D(t_i, \hat{t}_i)$ は、2つの面積の最大値で正規化された相対面積の差として算出される。これにより、値は $[-1, 1]$ の範囲となり、正の値は引き伸ばし（2次元の方が高次元よりもギャップが大きい）を、負の値は圧縮を示す。
   • 重要な点として、高次元の三角形の面積は、ペアワイズ距離のみ（ヘロンの公式）を用いて計算できるため、GIは高次元の座標を明示的に必要とせず、距離行列のみで計算可能である。
3. 集計（Aggregation）： 単一のスカラー指標を生成するために、GIはすべての三角形の絶対変形値を、重み付き平均を用いて集計する。各三角形の重み $w_i$ は、2次元空間または高次元空間における相対面積の大きい方を選択する。これにより、視覚的に顕著な大きなギャップ（投影側または元のデータ側のいずれか）が最終的なスコアに大きな影響を与えるようになる。
4. 可視化（Visualization）： GIは、変形値に応じて三角形を色分けすることで、散布図上にオーバーレイできる。発散型のカラーマップ（青は圧縮、赤は引き伸ばし、黄色は歪みなし）を用いることで、領域的な歪みを可視化する。三角形の境界による視覚的なノイズを軽減するため、著者らは背景にガウスぼかしを適用することを提案している。

主な貢献

1. 限界の特定： 本論文は、標準的な品質指標が、視覚的に大きな影響を与える空領域の構造的変形に対して鈍感であることを指摘し、それがアナリストを誤導する可能性があることを強調している。
2. 新しい指標の提案： 著者らは、点と点の関係から、点と点の間の空の空間（ギャップ）の歪みへと焦alsを移した指標であるギャップ指数を導入した。
3. ベンチマークと実装： 論文では、GIを一般的な指標（ストレス、信頼性、連続性、定常性、凝集性）と比較するための、人工および実データのコレクションを提供している。結果を再現するために、オープンソースのPython実装が提供されている。

結果
評価の結果、GIは他の指標が見逃す歪みを検出できることが示された：

• 視覚的アーティファクトへの感度： 「平面データセット」の実験（3D内に埋め込まれた2D平面上にランダムに分布する点）において、PCAは完全な投影（GI = 0）を行うが、t-SNEは偽のクラスター状のギャップを作成する。ストレスや信頼性はt-SNEの歪みが最小であると報告する一方で、GIは人工的なギャップによって引き起こされる重大な視覚的歪みを正しく特定した。
• 解釈性： 合成データセット（例：面が欠落した3Dキューブ）において、GIの可視化は、空の空間がどこで引き伸ばされたか、あるいは圧縮されたかを明確に示し、ユーザーが元の高次元構造（例：投影内の大きな赤い領域が3Dオブジェクトの欠落した面に対応していること）を推論することを可能にする。
• パフォーマンス： GIは、ドロネー三角形分割の $O(N \log N)$ の複雑さが支配的であり、計算効率が高いため、大規模なデータセットにも適している。

意義と主張
本論文は、GIが視覚的分析における盲点である「空領域の信頼性」に対処することで、既存の品質指標を補完する不可欠な要素を提供すると主張している。クラスターやパターンを定義するギャップに焦点を当てることで、GIは人間の知覚により適合した、投影品質のより包括的な視点を提供する。著者らは、GIが計算速度が速く、解釈可能であり、点中心の指標では見落とされがちな、視覚的に大きな影響を与える小さな構造的変形を検出できると断言している。本研究は、投影の三角形分割に関する従来の概念を再検討・拡張し、スカラー評価と領域的可視化の両方に適した、正規化された集計品質指標として定式化したものである。