다차원 척도법(Multidimensional Scaling, MDS)
02 Oct 2020 | Machine-Learning
해당 게시물은 고려대학교 강필성 교수님의 강의를 바탕으로 작성한 것입니다.
Multidimensional Scaling
다차원 척도법(Multidimensional Scaling, MDS)의 목적은 $d$ 차원 공간 상에 있는 객체의 거리를 최대한 보존하는 저차원의 좌표계를 찾는 것입니다. 주성분분석(Principal Component Analysis, PCA)와 다차원 척도법을 비교하면서 다차원 척도법에 대해서 알아보겠습니다.
주성분분석(PCA)
다차원척도법(MDS)
데이터
$d$ 차원 공간상에 있는
$n$ 개의 인스턴스
따라서, $n \times d$ 행렬로부터 시작
$(\mathbf{X} \in \mathbb{R}^d)$
$n$ 개의 인스턴스 간의
근접도(Proximity) 행렬
따라서, $n \times n$ 행렬로부터 시작
$(\mathbf{D}_{n \times n})$
목적
원래 데이터의
분산을 보존하는
기저의 부분집합 찾기
인스턴스의
거리 정보를 보존하는
좌표계 찾기
출력값
1. $d$ 개의 고유벡터(eigenvectors)
2. $d$ 개의 고윳값(eigenvalues)
$d$ 차원에 있는
각 인스턴스의 좌표값
$(\mathbf{X} \in \mathbb{R}^d)$
Procedure
Step 1.
다차원 척도법을 수행하는 과정을 알아보겠습니다. 가장 첫 번째 스텝은 인스턴스 사이의 근접도(거리) 행렬을 만드는 것입니다. 객체의 좌표값이 존재한다면 근접도 행렬을 계산해낼 수 있습니다. 거리 행렬의 각 요소 $d_{ij}$는 다음과 같은 4개의 조건을 만족해야 합니다.
- $d_{ij} \geq 0$
- $d_{ii} = 0$
- $d_{ij} = d_{ji}$
- $d_{ij} \leq d_{ik} + d_{jk}$ (삼각부등식)
거리를 계산할 때에는 유클리드 거리(Euclidean)나 맨하탄 거리(Manhattan) 등을 사용하고, 유사도를 계산할 때에는 상관관계(Correlation)나 자카드 유사도(Jaccard)를 사용합니다. 주성분 분석에서 사용했던 $d \times n$ 크기의 Column-wise 행렬 $\mathbf{X}$로부터 $n \times n$ 크기의 근접도 행렬 $\mathbf{D}$를 계산한다면 아래의 식을 사용하여 각 요소의 값을 구할 수 있습니다.
\[d_{rs}^2 = (\mathbf{x}_r-\mathbf{x}_s)^T(\mathbf{x}_r-\mathbf{x}_s)\]
Step 2.
두 번째로 해야 하는 일은 거리 정보를 최대한 보존하는 좌표 시스템을 찾는 것입니다. 다차원 축소법의 주된 알고리즘이 개입되는 부분이기도 합니다. 근접도 행렬 $\mathbf{D}$로부터 이들의 거리를 최대한 보존하는 $d$ 차원의 좌표계 $\mathbf{X}$를 바로 찾는 것은 어렵습니다. 그렇기 때문에 각 인스턴스의 내적값을 요소로 갖는 $\mathbf{B}$라는 행렬을 매개체로써 한 번 거쳐가도록 합니다. 간단하게 나타내면 아래와 같습니다.
\[\mathbf{D} \text{ (Proximity matrix)} \Rightarrow \mathbf{B} \text{ (Inner product matrix)} \Rightarrow \mathbf{X} \text{ (Coordinate matrix)} \\
b_{rs} = \mathbf{x}_r^T\mathbf{x}_s\]
이제 $\mathbf{D}$로부터 $\mathbf{B}$를 만들겠습니다. 실질적인 계산을 하기 전에 가정해야 할 사항이 있습니다. 모든 변수의 평균이 $0$이 된다는 점입니다. 따라서, 아래의 식이 성립하게 됩니다.
\[\sum_{r=1}^n x_{ri} = 0, (i=1,2, \cdots, p)\]
이제 준비도 마쳤으니 $\mathbf{B}$의 요소인 $\mathbf{x}_r^T\mathbf{x}_s$를 본격적으로 찾아보도록 하겠습니다. 먼저 위에서 알아본 거리 행렬 요소에 관한 식을 전개해보겠습니다.
\[\begin{aligned}
d^2_{rs} &= (\mathbf{x}_r-\mathbf{x}_s)^T(\mathbf{x}_r-\mathbf{x}_s)\\
&= \mathbf{x}_r^T\mathbf{x}_r + \mathbf{x}_s^T\mathbf{x}_s - 2\mathbf{x}_r^T\mathbf{x}_s
\end{aligned}\]
우리의 목적은 우변의 마지막 항인 $\mathbf{x}_r^T\mathbf{x}_s$을 구하는 것이므로 나머지 항을 하나의 문자로 치환하기 위해서 수학적 트릭을 사용하겠습니다. 트릭의 첫 번째 과정으로 각 문자 $r,s$에 대해서 각 항의 평균값을 구해보겠습니다. 먼저 $r$에 대한 평균을 구할 때의 수식은 아래와 같이 변하게 됩니다.
\[\frac{1}{n}\sum^n_{r=1} d^2_{rs} = \frac{1}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_r + \frac{1}{n}\sum^n_{r=1}\mathbf{x}_s^T\mathbf{x}_s - \frac{2}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_s = \frac{1}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_r + \mathbf{x}_s^T\mathbf{x}_s \\
\color{blue}{\therefore \mathbf{x}_s^T\mathbf{x}_s = \frac{1}{n}\sum^n_{r=1} d^2_{rs} - \frac{1}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_r}\]
마찬가지로 $s$에 대한 평균을 구할 때의 수식은 아래와 같이 변하게 됩니다.
\[\frac{1}{n}\sum^n_{s=1} d^2_{rs} = \frac{1}{n}\sum^n_{s=1}\mathbf{x}_r^T\mathbf{x}_r + \frac{1}{n}\sum^n_{s=1}\mathbf{x}_s^T\mathbf{x}_s - \frac{2}{n}\sum^n_{s=1}\mathbf{x}_r^T\mathbf{x}_s = \mathbf{x}_r^T\mathbf{x}_r + \frac{1}{n}\sum^n_{s=1}\mathbf{x}_s^T\mathbf{x}_s \\
\color{red}{\therefore \mathbf{x}_r^T\mathbf{x}_r = \frac{1}{n}\sum^n_{s=1} d^2_{rs} - \frac{1}{n}\sum^n_{s=1}\mathbf{x}_s^T\mathbf{x}_s}\]
트릭을 통해서 두 항 $\mathbf{x}_s^T\mathbf{x}_s, \mathbf{x}_r^T\mathbf{x}_r$ 은 치환할 수 있게 되었지만 치환 과정에서 다른 항들이 나오게 됩니다. 이 항을 처리하기 위해서 또 다른 트릭을 한 번 더 사용합니다.
\[\begin{aligned}
\frac{1}{n^2}\sum^n_{r=1}\sum^n_{s=1} d^2_{rs} &=
\frac{1}{n^2}\sum^n_{r=1}\sum^n_{s=1}\mathbf{x}_r^T\mathbf{x}_r +
\frac{1}{n^2}\sum^n_{r=1}\sum^n_{s=1}\mathbf{x}_s^T\mathbf{x}_s -
\frac{2}{n^2}\sum^n_{r=1}\sum^n_{s=1}\mathbf{x}_r^T\mathbf{x}_s \\
&= \frac{1}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_r
+ \frac{1}{n}\sum^n_{s=1}\mathbf{x}_s^T\mathbf{x}_s = \frac{2}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_r
\end{aligned} \\
\color{olive}{\therefore \frac{2}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_r = \frac{1}{n^2}\sum^n_{r=1}\sum^n_{s=1} d^2_{rs}}\]
이제 모든 항을 처리할 수 있게 되었습니다. 이제 처음에 $d^2_{rs}$에 대해서 나타냈던 식을 활용하여 $b$ 를 나타내보도록 하겠습니다.
\[\begin{aligned}
b_{rs} &= \mathbf{x}_r^T\mathbf{x}_s \\
&= - \frac{1}{2}(d^2_{rs}-\mathbf{x}_r^T\mathbf{x}_r - \mathbf{x}_s^T\mathbf{x}_s) \qquad \because d^2_{rs} = \mathbf{x}_r^T\mathbf{x}_r + \mathbf{x}_s^T\mathbf{x}_s - 2\mathbf{x}_r^T\mathbf{x}_s \\
&= - \frac{1}{2}(d^2_{rs} - \frac{1}{n}\sum^n_{s=1} d^2_{rs} + \frac{1}{n}\sum^n_{s=1}\mathbf{x}_s^T\mathbf{x}_s - \frac{1}{n}\sum^n_{r=1} d^2_{rs} + \frac{1}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_r) \\
&= - \frac{1}{2}(d^2_{rs} - \frac{1}{n}\sum^n_{s=1} d^2_{rs} - \frac{1}{n}\sum^n_{r=1} d^2_{rs} + \frac{1}{n^2}\sum^n_{r=1}\sum^n_{s=1} d^2_{rs})
\end{aligned} \\\]
마지막 식을 다른 형태로 치환하여 나타낼 수 있습니다.
\[\begin{aligned}
b_{rs} &= - \frac{1}{2}(d^2_{rs} - \frac{1}{n}\sum^n_{s=1} d^2_{rs} - \frac{1}{n}\sum^n_{r=1} d^2_{rs} + \frac{1}{n^2}\sum^n_{r=1}\sum^n_{s=1} d^2_{rs}) \\
&= a_{rs} - a_{r\cdot} - a_{\cdot s} + a_{\cdot\cdot}
\end{aligned}\]
$a_{rs}$ 를 행렬 $\mathbf{A}$의 성분이라 하면 우리가 구하려던 행렬 $\mathbf{B}$는 아래와 같이 구할 수 있습니다.
\[\mathbf{B} = \mathbf{HAH} \qquad \mathbf{H} = \mathbf{I} - \frac{1}{n}\mathbf{11}^T\]
이렇게 구한 행렬 $\mathbf{B}$는 아래와 같이 나타낼 수 있습니다.
\[\mathbf{B} = \mathbf{XX}^T\]
행렬 $\mathbf{B}$는 대칭행렬이며 양의 준정부호 행렬(Positive semi-definite matrix)이기 때문에 행렬 $\mathbf{X}$ 의 랭크가 $p$ 라면 $\mathbf{B}$ 는 $p$ 개의 양수인 고윳값과 $n-p$ 개의 $0$인 고윳값을 가지고 있습니다. 따라서 고윳값 분해(Eigenvalue factorization)를 통해서 아래와 같이 분해할 수 있습니다.
\[\mathbf{B}_1 = \mathbf{V}_1\mathbf{\Lambda}_1\mathbf{V}_1^T\\
\mathbf{\Lambda}_1 = \text{diag}(\lambda_1, \lambda_2, \cdots ,\lambda_p)\]
고윳값 분해로 만들어 낸 식을 아래와 같이 나타낼 수 있으므로 우리가 구하고자 하는 좌표 행렬 $\mathbf{X}$를 구할 수 있게 됩니다.
\[\mathbf{B}_1 = \mathbf{V}_1\mathbf{\Lambda}_1\mathbf{V}_1^T = (\mathbf{V}_1\mathbf{\Lambda}_1^{1/2})(\mathbf{V}_1\mathbf{\Lambda}_1^{1/2})^T \\
\therefore \mathbf{X} = \mathbf{V}_1\mathbf{\Lambda}_1^{1/2}\]
해당 게시물은 고려대학교 강필성 교수님의 강의를 바탕으로 작성한 것입니다.
Multidimensional Scaling
다차원 척도법(Multidimensional Scaling, MDS)의 목적은 $d$ 차원 공간 상에 있는 객체의 거리를 최대한 보존하는 저차원의 좌표계를 찾는 것입니다. 주성분분석(Principal Component Analysis, PCA)와 다차원 척도법을 비교하면서 다차원 척도법에 대해서 알아보겠습니다.
| 주성분분석(PCA) | 다차원척도법(MDS) | |
|---|---|---|
| 데이터 | $d$ 차원 공간상에 있는 $n$ 개의 인스턴스 따라서, $n \times d$ 행렬로부터 시작 $(\mathbf{X} \in \mathbb{R}^d)$ |
$n$ 개의 인스턴스 간의 근접도(Proximity) 행렬 따라서, $n \times n$ 행렬로부터 시작 $(\mathbf{D}_{n \times n})$ |
| 목적 | 원래 데이터의 분산을 보존하는 기저의 부분집합 찾기 |
인스턴스의 거리 정보를 보존하는 좌표계 찾기 |
| 출력값 | 1. $d$ 개의 고유벡터(eigenvectors) 2. $d$ 개의 고윳값(eigenvalues) |
$d$ 차원에 있는 각 인스턴스의 좌표값 $(\mathbf{X} \in \mathbb{R}^d)$ |
Procedure
Step 1.
다차원 척도법을 수행하는 과정을 알아보겠습니다. 가장 첫 번째 스텝은 인스턴스 사이의 근접도(거리) 행렬을 만드는 것입니다. 객체의 좌표값이 존재한다면 근접도 행렬을 계산해낼 수 있습니다. 거리 행렬의 각 요소 $d_{ij}$는 다음과 같은 4개의 조건을 만족해야 합니다.
- $d_{ij} \geq 0$
- $d_{ii} = 0$
- $d_{ij} = d_{ji}$
- $d_{ij} \leq d_{ik} + d_{jk}$ (삼각부등식)
거리를 계산할 때에는 유클리드 거리(Euclidean)나 맨하탄 거리(Manhattan) 등을 사용하고, 유사도를 계산할 때에는 상관관계(Correlation)나 자카드 유사도(Jaccard)를 사용합니다. 주성분 분석에서 사용했던 $d \times n$ 크기의 Column-wise 행렬 $\mathbf{X}$로부터 $n \times n$ 크기의 근접도 행렬 $\mathbf{D}$를 계산한다면 아래의 식을 사용하여 각 요소의 값을 구할 수 있습니다.
\[d_{rs}^2 = (\mathbf{x}_r-\mathbf{x}_s)^T(\mathbf{x}_r-\mathbf{x}_s)\]Step 2.
두 번째로 해야 하는 일은 거리 정보를 최대한 보존하는 좌표 시스템을 찾는 것입니다. 다차원 축소법의 주된 알고리즘이 개입되는 부분이기도 합니다. 근접도 행렬 $\mathbf{D}$로부터 이들의 거리를 최대한 보존하는 $d$ 차원의 좌표계 $\mathbf{X}$를 바로 찾는 것은 어렵습니다. 그렇기 때문에 각 인스턴스의 내적값을 요소로 갖는 $\mathbf{B}$라는 행렬을 매개체로써 한 번 거쳐가도록 합니다. 간단하게 나타내면 아래와 같습니다.
\[\mathbf{D} \text{ (Proximity matrix)} \Rightarrow \mathbf{B} \text{ (Inner product matrix)} \Rightarrow \mathbf{X} \text{ (Coordinate matrix)} \\ b_{rs} = \mathbf{x}_r^T\mathbf{x}_s\]이제 $\mathbf{D}$로부터 $\mathbf{B}$를 만들겠습니다. 실질적인 계산을 하기 전에 가정해야 할 사항이 있습니다. 모든 변수의 평균이 $0$이 된다는 점입니다. 따라서, 아래의 식이 성립하게 됩니다.
\[\sum_{r=1}^n x_{ri} = 0, (i=1,2, \cdots, p)\]이제 준비도 마쳤으니 $\mathbf{B}$의 요소인 $\mathbf{x}_r^T\mathbf{x}_s$를 본격적으로 찾아보도록 하겠습니다. 먼저 위에서 알아본 거리 행렬 요소에 관한 식을 전개해보겠습니다.
\[\begin{aligned} d^2_{rs} &= (\mathbf{x}_r-\mathbf{x}_s)^T(\mathbf{x}_r-\mathbf{x}_s)\\ &= \mathbf{x}_r^T\mathbf{x}_r + \mathbf{x}_s^T\mathbf{x}_s - 2\mathbf{x}_r^T\mathbf{x}_s \end{aligned}\]우리의 목적은 우변의 마지막 항인 $\mathbf{x}_r^T\mathbf{x}_s$을 구하는 것이므로 나머지 항을 하나의 문자로 치환하기 위해서 수학적 트릭을 사용하겠습니다. 트릭의 첫 번째 과정으로 각 문자 $r,s$에 대해서 각 항의 평균값을 구해보겠습니다. 먼저 $r$에 대한 평균을 구할 때의 수식은 아래와 같이 변하게 됩니다.
\[\frac{1}{n}\sum^n_{r=1} d^2_{rs} = \frac{1}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_r + \frac{1}{n}\sum^n_{r=1}\mathbf{x}_s^T\mathbf{x}_s - \frac{2}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_s = \frac{1}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_r + \mathbf{x}_s^T\mathbf{x}_s \\ \color{blue}{\therefore \mathbf{x}_s^T\mathbf{x}_s = \frac{1}{n}\sum^n_{r=1} d^2_{rs} - \frac{1}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_r}\]마찬가지로 $s$에 대한 평균을 구할 때의 수식은 아래와 같이 변하게 됩니다.
\[\frac{1}{n}\sum^n_{s=1} d^2_{rs} = \frac{1}{n}\sum^n_{s=1}\mathbf{x}_r^T\mathbf{x}_r + \frac{1}{n}\sum^n_{s=1}\mathbf{x}_s^T\mathbf{x}_s - \frac{2}{n}\sum^n_{s=1}\mathbf{x}_r^T\mathbf{x}_s = \mathbf{x}_r^T\mathbf{x}_r + \frac{1}{n}\sum^n_{s=1}\mathbf{x}_s^T\mathbf{x}_s \\ \color{red}{\therefore \mathbf{x}_r^T\mathbf{x}_r = \frac{1}{n}\sum^n_{s=1} d^2_{rs} - \frac{1}{n}\sum^n_{s=1}\mathbf{x}_s^T\mathbf{x}_s}\]트릭을 통해서 두 항 $\mathbf{x}_s^T\mathbf{x}_s, \mathbf{x}_r^T\mathbf{x}_r$ 은 치환할 수 있게 되었지만 치환 과정에서 다른 항들이 나오게 됩니다. 이 항을 처리하기 위해서 또 다른 트릭을 한 번 더 사용합니다.
\[\begin{aligned} \frac{1}{n^2}\sum^n_{r=1}\sum^n_{s=1} d^2_{rs} &= \frac{1}{n^2}\sum^n_{r=1}\sum^n_{s=1}\mathbf{x}_r^T\mathbf{x}_r + \frac{1}{n^2}\sum^n_{r=1}\sum^n_{s=1}\mathbf{x}_s^T\mathbf{x}_s - \frac{2}{n^2}\sum^n_{r=1}\sum^n_{s=1}\mathbf{x}_r^T\mathbf{x}_s \\ &= \frac{1}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_r + \frac{1}{n}\sum^n_{s=1}\mathbf{x}_s^T\mathbf{x}_s = \frac{2}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_r \end{aligned} \\ \color{olive}{\therefore \frac{2}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_r = \frac{1}{n^2}\sum^n_{r=1}\sum^n_{s=1} d^2_{rs}}\]이제 모든 항을 처리할 수 있게 되었습니다. 이제 처음에 $d^2_{rs}$에 대해서 나타냈던 식을 활용하여 $b$ 를 나타내보도록 하겠습니다.
\[\begin{aligned} b_{rs} &= \mathbf{x}_r^T\mathbf{x}_s \\ &= - \frac{1}{2}(d^2_{rs}-\mathbf{x}_r^T\mathbf{x}_r - \mathbf{x}_s^T\mathbf{x}_s) \qquad \because d^2_{rs} = \mathbf{x}_r^T\mathbf{x}_r + \mathbf{x}_s^T\mathbf{x}_s - 2\mathbf{x}_r^T\mathbf{x}_s \\ &= - \frac{1}{2}(d^2_{rs} - \frac{1}{n}\sum^n_{s=1} d^2_{rs} + \frac{1}{n}\sum^n_{s=1}\mathbf{x}_s^T\mathbf{x}_s - \frac{1}{n}\sum^n_{r=1} d^2_{rs} + \frac{1}{n}\sum^n_{r=1}\mathbf{x}_r^T\mathbf{x}_r) \\ &= - \frac{1}{2}(d^2_{rs} - \frac{1}{n}\sum^n_{s=1} d^2_{rs} - \frac{1}{n}\sum^n_{r=1} d^2_{rs} + \frac{1}{n^2}\sum^n_{r=1}\sum^n_{s=1} d^2_{rs}) \end{aligned} \\\]마지막 식을 다른 형태로 치환하여 나타낼 수 있습니다.
\[\begin{aligned} b_{rs} &= - \frac{1}{2}(d^2_{rs} - \frac{1}{n}\sum^n_{s=1} d^2_{rs} - \frac{1}{n}\sum^n_{r=1} d^2_{rs} + \frac{1}{n^2}\sum^n_{r=1}\sum^n_{s=1} d^2_{rs}) \\ &= a_{rs} - a_{r\cdot} - a_{\cdot s} + a_{\cdot\cdot} \end{aligned}\]$a_{rs}$ 를 행렬 $\mathbf{A}$의 성분이라 하면 우리가 구하려던 행렬 $\mathbf{B}$는 아래와 같이 구할 수 있습니다.
\[\mathbf{B} = \mathbf{HAH} \qquad \mathbf{H} = \mathbf{I} - \frac{1}{n}\mathbf{11}^T\]이렇게 구한 행렬 $\mathbf{B}$는 아래와 같이 나타낼 수 있습니다.
\[\mathbf{B} = \mathbf{XX}^T\]행렬 $\mathbf{B}$는 대칭행렬이며 양의 준정부호 행렬(Positive semi-definite matrix)이기 때문에 행렬 $\mathbf{X}$ 의 랭크가 $p$ 라면 $\mathbf{B}$ 는 $p$ 개의 양수인 고윳값과 $n-p$ 개의 $0$인 고윳값을 가지고 있습니다. 따라서 고윳값 분해(Eigenvalue factorization)를 통해서 아래와 같이 분해할 수 있습니다.
\[\mathbf{B}_1 = \mathbf{V}_1\mathbf{\Lambda}_1\mathbf{V}_1^T\\ \mathbf{\Lambda}_1 = \text{diag}(\lambda_1, \lambda_2, \cdots ,\lambda_p)\]고윳값 분해로 만들어 낸 식을 아래와 같이 나타낼 수 있으므로 우리가 구하고자 하는 좌표 행렬 $\mathbf{X}$를 구할 수 있게 됩니다.
\[\mathbf{B}_1 = \mathbf{V}_1\mathbf{\Lambda}_1\mathbf{V}_1^T = (\mathbf{V}_1\mathbf{\Lambda}_1^{1/2})(\mathbf{V}_1\mathbf{\Lambda}_1^{1/2})^T \\ \therefore \mathbf{X} = \mathbf{V}_1\mathbf{\Lambda}_1^{1/2}\]
Comments