\(n\)個の点 \(x_1,\ldots,x_n\) の間の距離(非類似度)が与えられている場合に,点の位置を求める方法.結果の可視化などに利用される.
点 \(x_i\) と \(x_j\) の間の距離 \(d_{ij}\) の2乗を要素とする\(n\times n\)行列を \(D\) とする. \(X\) は,\(k\)次元空間の点 \(x_i\) を行ベクトルで表し,それを\(n\)行集めた\(n\times k\)行列. \(J\) は,単位行列から,全要素が \(1/n\) の行列を引いた \(n\times n\)行列.\(P=(-1/2)JDJ^\top\)とする.
この \(P\) を最小二乗の意味で近似する \(XX^\top\) は次式を最小化: \[\phi=\mathrm{trace}[(P-XX^\top)^2]\] \(P\) の大きい方から \(k\)個の固有値を求め,これらの固有値を対角要素とする行列を\(\Lambda_k\),対応する固有ベクトルを集めた行列を \(Q_k\) とする.点の推定位置 \(\hat{X}\) は次式: \[\hat{X}=Q_r{\Lambda_k}^{1/2}\] ただし,\(P\) は最低 \(k\)個の正の固有値が存在する必要がある. この方法を特に主座標分析 (principal coordinate analysis)という.
上記の方法は \(D\) が比率尺度や間隔尺度である場合を想定しているので計量MDS (metric MDS)と呼ばれる. 他に,順序尺度などを想定した非計量MDS (non-metric MDS)がある. これは,\(k\)次元空間中での点 \(x_i\) と \(x_j\) との間の距離を \(\delta_{ij}\) としたとき次のストレス (stress)を最小化するように\(x_i\)を定める: \[\bigg[\frac{\sum_{i,j,i\ne j}(\delta_{ij}-d_{ij})^2}{\sum_{i,j,i\ne j}{d_{ij}}^2}\bigg]^{1/2}\]
-- しましま