統計検定準一級実践ワークブック26章まとめ
第一段階#
個体$ i $の座標ベクトルを$ x_i\in\mathbb R^p $とし、$ \sum_{i=1}^n x_i=0 $と中心化する。行に$ x_i^\top $を並べた行列を$ X $として、 $$ a=\sum_{i=1}^n|x_i|^2=|X|_F^2 $$ とおく。$ a $はフロベニウスノルムの二乗である。
ユークリッド距離について、 $$ d_{ij}^2=|x_i-x_j|^2=|x_i|^2+|x_j|^2-2x_i^\top x_j $$ なので、 $$ x_i^\top x_j=-\frac12\left(d_{ij}^2-|x_i|^2-|x_j|^2\right) $$ となる。中心化の条件から、 $$ \sum_{k=1}^n d_{kj}^2=a+n|x_j|^2,\qquad\sum_{\ell=1}^n d_{i\ell}^2=n|x_i|^2+a $$ であり、さらに全ての$ i,j $で足すと、 $$ \sum_{k=1}^n\sum_{\ell=1}^n d_{k\ell}^2=2na $$ となる。これらを代入すると、 $$ x_i^\top x_j=-\frac12\left(d_{ij}^2-\frac1n\sum_{k=1}^n d_{kj}^2-\frac1n\sum_{\ell=1}^n d_{i\ell}^2+\frac1{n^2}\sum_{k=1}^n\sum_{\ell=1}^n d_{k\ell}^2\right) $$ を得る。固定した$ i,j $と、和をとる添字$ k,\ell $を区別すると読みやすい。
下ごしらえ#
$ D=(d_{ij}^2) $を距離の二乗を並べた行列、$ J_n $を全成分1の行列とする。例えば、 $$ J_3D=\begin{pmatrix}\sum_{k=1}^3d_{k1}^2&\sum_{k=1}^3d_{k2}^2&\sum_{k=1}^3d_{k3}^2\\sum_{k=1}^3d_{k1}^2&\sum_{k=1}^3d_{k2}^2&\sum_{k=1}^3d_{k3}^2\\sum_{k=1}^3d_{k1}^2&\sum_{k=1}^3d_{k2}^2&\sum_{k=1}^3d_{k3}^2\end{pmatrix} $$ となる。つまり$ (J_nD)_{ij}=\sum_kd_{kj}^2 $は列$ j $だけに依存し、行$ i $によらない。同様に$ (DJ_n)_{ij}=\sum_\ell d_{i\ell}^2 $は行$ i $だけに依存する。$ J_nDJ_n $の各成分は全成分の総和となる。
第二段階#
$ B=XX^\top $を内積行列とすると、$ B_{ij}=x_i^\top x_j $なので、先ほどの成分の式は、 $$ B=-\frac12\left(D-\frac1nJ_nD-\frac1nDJ_n+\frac1{n^2}J_nDJ_n\right) $$ と書ける。中心化行列$ H=I_n-J_n/n $を用いれば、 $$ B=-\frac12HDH $$ となる。これが古典的多次元尺度法の二重中心化である。
ユークリッド距離から作った$ B $は半正定値である。固有値分解$ B=U\Lambda U^\top $から、正の固有値に対応する列を使って$ X=U_+\Lambda_+^{1/2} $と座標を復元できる。低次元に近似するときは大きい正の固有値から選ぶ。一般の非類似度では負の固有値が出ることもあり、同じ次元での厳密なユークリッド距離表現があるとは限らない。