多次元尺度法（MDS）：距離保持による次元削減
MDSの基本概念
Step 1: MDSの目的
対象間の距離（非類似度）情報を保持しながら、低次元空間で表現する手法
- 入力：距離行列$\mathbf{D} = (d_{ij})$
- 出力：低次元座標$\mathbf{X} = (x_{ik})$
- 制約：距離関係の保持
Step 2: 古典的MDS（主座標分析）
アルゴリズム：
- 中心化行列の計算：$\mathbf{H} = \mathbf{I} - \frac{1}{n}\mathbf{1}\mathbf{1}^T$
- 内積行列の導出：$\mathbf{B} = -\frac{1}{2}\mathbf{H}\mathbf{D}^{(2)}\mathbf{H}$
- 固有値分解：$\mathbf{B} = \mathbf{V}\mathbf{\Lambda}\mathbf{V}^T$
- 座標の構成：$\mathbf{X} = \mathbf{V}_k\mathbf{\Lambda}_k^{1/2}$
ここで、$\mathbf{D}^{(2)} = (d_{ij}^2)$は距離の2乗行列
Step 3: 内積行列の理論
距離と内積の関係（Young-Householder定理）：
$d_{ij}^2 = \|\mathbf{x}_i\|^2 + \|\mathbf{x}_j\|^2 - 2\mathbf{x}_i^T\mathbf{x}_j$
中心化された座標では：
$b_{ij} = \mathbf{x}_i^T\mathbf{x}_j = -\frac{1}{2}(d_{ij}^2 - d_{i\cdot}^2 - d_{\cdot j}^2 + d_{\cdot\cdot}^2)$
MDSの種類
| 種類 | 特徴 | 目的関数 |
|---|
| 古典的MDS | 距離の絶対値を保持 | 固有値分解 |
| 非計量MDS | 距離の順序のみ保持 | ストレス最小化 |
| 計量MDS | 距離の比例関係保持 | 重み付きストレス |
Step 4: 非計量MDSとストレス関数
Kruskalのストレス関数：