多次元尺度構成法(MDS; Multi-Dimensional Scaling)の導出まとめ

多次元尺度構成法(MDS; Multi-Dimensional Scaling)は個体間の類似度が与えられているときに、類似度に基づいてそれぞれの個体の位置を表現する手法の一つです。当記事では計量MDSの基本的な導出に関して取りまとめを行いました。
「統計学実践ワークブック」の$26$章の「その他の多変量解析手法」の内容を参考に作成を行いました。

 

理論的な導出

問題設定

多次元尺度構成法(MDS; Multi-Dimensional Scaling)は$n$個の個体間の類似度が与えられているときに、類似度に基づいてそれぞれの個体の位置を表現する手法の一つである。

下記の行列$D$を用いて$n$個の個体の類似度が得られている場合を考える。
$$
\large
\begin{align}
D = \left(\begin{array}{ccccc} 0 & d_{12}^2 & d_{13}^2 & \cdots & d_{1n}^2 \\ d_{21}^2 & 0 & d_{23}^2 & \cdots & d_{2n}^2 \\ d_{31}^2 & d_{32}^2 & 0 & \cdots & d_{3n}^2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ d_{n1}^2 & d_{n2}^2 & d_{n3}^2 & \cdots & 0 \end{array} \right)
\end{align}
$$

上記のように類似度の行列が与えられたとき、行列を元に個体$i$の位置を$x_{i} = (x_{i1},x_{i2},…,x_{ik})^{\mathrm{T}}$のように表すことを考える。

このとき、下記が成立すると考えても一般性を失わないので、下記が成立すると考える。
$$
\large
\begin{align}
\sum_{i=1}^{n} x_{i} &= \sum_{i=1}^{n} \left(\begin{array}{c} x_{i1} \\ \vdots \\ x_{ik} \end{array} \right) \\
&= \left(\begin{array}{c} 0 \\ \vdots \\ 0 \end{array} \right)
\end{align}
$$

また、表記の簡略化にあたって、$\displaystyle a = \sum_{i}^{n} ||x_i||^{2}$とおく。ここで$||x||^{2}$はフロベニウスノルムであると考える。

・参考
特異値分解 フロベニウスノルム(Frobenius norm)

 

二重中心化(double centering)

・二重中心化の概要
前項の問題設定に基づいて、$x_{i}$を並べた行列$X$に関して対称行列$X^{\mathrm{T}}X$は下記のように表すことができる。
$$
\large
\begin{align}
X X^{\mathrm{T}} &= – \frac{1}{2} \left( I_{n} – \frac{1}{n} J_{n} \right) D \left( I_{n} – \frac{1}{n} J_{n} \right) \quad (1) \\
I_{n} &= \left(\begin{array}{c} 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \end{array} \right) \\
J_{n} &= \left(\begin{array}{c} 1 & 1 & 1 & \cdots & 1 \\ 1 & 1 & 1 & \cdots & 1 \\ 1 & 1 & 1 & \cdots & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \cdots & 1 \end{array} \right)
\end{align}
$$

・二重中心化の導出
以下、$(1)$式の導出を行う。導出にあたって、$\displaystyle d_{ij}^{2}, \sum_{i=1}^{n} d_{ij}^{2}, \sum_{j=1}^{n} d_{ij}^{2}$を$x_i, x_j, a$を用いて表すことを考える。
$$
\large
\begin{align}
d_{ij}^{2} &= ||x_i-x_j||^2 = ||x_i||^2 + ||x_j||^2 – 2 x_i^{\mathrm{T}} x_j \\
\sum_{i=1}^{n} d_{ij}^{2} &= \sum_{i=1}^{n} (||x_i||^2 + ||x_j||^2 + – x_j^{\mathrm{T}} x_i) \\
&= \sum_{i=1}^{n} ||x_i||^2 + n||x_j||^2 + – x_j^{\mathrm{T}} \sum_{i=1}^{n} x_i = a + n||x_j||^2 \\
\sum_{j=1}^{n} d_{ij}^{2} &= \sum_{j=1}^{n} (||x_i||^2 + ||x_j||^2 + – x_i^{\mathrm{T}} x_j) \\
&= n||x_i||^2 + \sum_{j=1}^{n} ||x_j||^2 – x_i^{\mathrm{T}} \sum_{j=1}^{n} x_j = n||x_i||^2 + a
\end{align}
$$

上記の計算にあたっては$x_i^{\mathrm{T}} x_j = x_j^{\mathrm{T}} x_i$が成立することを用いた。また、$\displaystyle \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij}^{2}$は下記のように表すことができる。
$$
\large
\begin{align}
\sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij}^{2} &= \sum_{i=1}^{n} \sum_{j=1}^{n} (||x_i||^2 + ||x_j||^2 + – x_i^{\mathrm{T}} x_j) \\
&= 2na
\end{align}
$$

ここまでの内容を元に、$x_i^{\mathrm{T}} x_j$は下記のように表すことができる。
$$
\large
\begin{align}
d_{ij}^{2} &= ||x_i||^2 + ||x_j||^2 – 2 x_i^{\mathrm{T}} x_j \\
x_i^{\mathrm{T}} x_j &= – \frac{1}{2} (d_{ij}^2 – (||x_i||^2 + ||x_j||^2)) \\
&= – \frac{1}{2} \left( d_{ij}^2 – \frac{1}{n} \left( \sum_{i=1}^{n} d_{ij}^{2} – a \right) – \frac{1}{n} \left( \sum_{j=1}^{n} d_{ij}^{2} – a \right) \right) \\
&= – \frac{1}{2} \left( d_{ij}^2 – \frac{1}{n} \sum_{i=1}^{n} d_{ij}^{2} – \frac{1}{n} \sum_{j=1}^{n} d_{ij}^{2} – \frac{2a}{n} \right) \\
&= – \frac{1}{2} \left( d_{ij}^2 – \frac{1}{n} \sum_{i=1}^{n} d_{ij}^{2} – \frac{1}{n} \sum_{j=1}^{n} d_{ij}^{2} – \frac{2na}{n^2} \right) \\
&= – \frac{1}{2} \left( d_{ij}^2 – \frac{1}{n} \sum_{i=1}^{n} d_{ij}^{2} – \frac{1}{n} \sum_{j=1}^{n} d_{ij}^{2} – \frac{1}{n^2} \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij}^{2} \right)
\end{align}
$$

ここで「行列の成分表示」の表記に基づいて行列$A$の$(i,j)$成分を$(A)_{ij}$のように表すと考えるとき、$(1)$式に関して下記のような式がそれぞれ成立する。
$$
\large
\begin{align}
(D)_{ij} &= d_{ij}^2 \\
\left( \frac{1}{n} J_{n} D \right)_{ij} &= \frac{1}{n} \left(\begin{array}{cccc} 1 & 1 & \cdots & 1 \end{array} \right) \left(\begin{array}{c} d_{1j}^2 \\ d_{2j}^2 \\ \vdots \\ d_{nj}^2 \end{array} \right) \\
&= \frac{1}{n} \sum_{i=1}^{n} d_{ij}^2 \\
\left( \frac{1}{n} D J_{n} \right)_{ij} &= \frac{1}{n} \left(\begin{array}{cccc} d_{i1}^2 & d_{i2}^2 & \cdots & d_{in}^2 \end{array} \right) \left(\begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right) \\
&= \frac{1}{n} \sum_{j=1}^{n} d_{ij}^2 \\
\left( \frac{1}{n^2} J_{n} D J_{n} \right)_{ij} &= \frac{1}{n^2} \left(\begin{array}{cccc} 1 & 1 & \cdots & 1 \end{array} \right) \left(\begin{array}{cccc} d_{11}^2 & d_{12}^2 & \cdots & d_{1n}^2 \\ d_{21}^2 & d_{22}^2 & \cdots & d_{2n}^2 \\ \vdots & \vdots & \ddots & \vdots \\ d_{n1}^2 & d_{n2}^2 & \cdots & d_{nn}^2 \end{array} \right) \left(\begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right) \\
&= \frac{1}{n^2} \left(\begin{array}{cccc} 1 & 1 & \cdots & 1 \end{array} \right) \left(\begin{array}{c} \sum_{j=1}^{n} d_{1j}^2 \\ \sum_{j=1}^{n} d_{2j}^2 \\ \vdots \\ \sum_{j=1}^{n} d_{nj}^2 \end{array} \right) \\
&= \frac{1}{n^2} \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij}^{2}
\end{align}
$$

上記には$d_{ii}^2$が出てくるが$d_{ii}^2=0$と考えれば、$D$の行列の定義に反しない。上記を元に下記のように考えることができる。
$$
\large
\begin{align}
(X X^{\mathrm{T}})_{ij} &= x_i^{\mathrm{T}} x_j \\
&= – \frac{1}{2} \left( d_{ij}^2 – \frac{1}{n} \sum_{i=1}^{n} d_{ij}^{2} – \frac{1}{n} \sum_{j=1}^{n} d_{ij}^{2} – \frac{1}{n^2} \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij}^{2} \right) \\
&= – \frac{1}{2} \left( D_{ij} – \left( \frac{1}{n} J_{n} D \right)_{ij} – \left( \frac{1}{n} D J_{n} \right)_{ij} – \left( \frac{1}{n^2} J_{n} D J_{n} \right)_{ij} \right) \\
&= – \frac{1}{2} \left( I_{n} – \frac{1}{n} J_{n} \right) D \left( I_{n} – \frac{1}{n} J_{n} \right)_{ij} \\
&= \left( – \frac{1}{2} \left( I_{n} – \frac{1}{n} J_{n} \right) D \left( I_{n} – \frac{1}{n} J_{n} \right) \right)_{ij}
\end{align}
$$

上記より$(1)$式が成立することがわかる。

・参考
$\displaystyle \left( I_{n}-\frac{1}{n}J_{n} \right)A\left( I_{n}-\frac{1}{n}J_{n} \right)$の計算による二重中心化の計算の詳細の確認
https://www.hello-statisticians.com/explain-terms-cat/double_centering1.html

 

エッカート・ヤング分解と寄与度

$n \times n$の対称行列$B=X X^{\mathrm{T}}$の固有値$\lambda_1,…,\lambda_n$を元に下記のように対角行列$\Lambda$を考える。
$$
\large
\begin{align}
\Lambda = \left(\begin{array}{cccc} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n \end{array} \right)
\end{align}
$$

このとき$\Lambda^{1/2}$は下記のように表すことができる。
$$
\large
\begin{align}
\Lambda^{\frac{1}{2}} = \left(\begin{array}{cccc} \sqrt{\lambda_1} & 0 & \cdots & 0 \\ 0 & \sqrt{\lambda_2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \sqrt{\lambda_n} \end{array} \right)
\end{align}
$$

ここで$B=X X^{\mathrm{T}}$の固有ベクトルを元に直交行列$U$を考えると$B=U \Lambda U^{\mathrm{T}}$のように表すことができる。このとき$X=U \Lambda^{1/2}$のように考えると$X X^{\mathrm{T}} = (U \Lambda^{1/2})(U \Lambda^{1/2})^{\mathrm{T}} = U \Lambda^{1/2} (\Lambda^{1/2})^{\mathrm{T}} U^{\mathrm{T}} = U \Lambda U^{\mathrm{T}} = B$が成立する。これをエッカート・ヤング分解(Eckart-Young decomposition)という。

このように考えることで、$B$がわかっているときに$X$を計算することができる。ここで計算した$X$は$B$が非負定値行列であれば$D$と対応する位置を表す。

 

具体例