[Dimensionality Reduction] Unsupervised Method (Linear embedding) 2: Multi-dimensional scaling (MDS)

본 포스트는 고려대학교 산업경영공학부 강필성 교수님의 Business Analytics 강의를 정리한 내용입니다.

 

MDS의 목적은 D차원 공간 상에 객체들이 존재할 때, 이 객체들의 distance가 저차원에서도 최대한 많이 보존되도록 하는 축을 찾는 것이다.

MDS에서 데이터들의 특징은 개별적인 객체들의 거리이고, 이 거리들을 보존하는 것이 최종 목표이다.

PCA vs MDS

1. Data

PCA는 다차원에 존재하는 $N$개의 object가 데이터이다. $(N \times D)$

MDS는 해당하는 객체들 사이의 유사도 또는 비 유사도를 측정할 수 있는 지표가 데이터이고, 이는 $N \times N$ metrix로 구성된다.

2. Purpose

PCA는 원 데이터의 분산을 최대한 보존하는 bases를 찾는 것에 목적을 둔다.

MDS는 실질적인 객체들의 좌표 시스템을 찾는다. 이 좌표 시스템은 객체들 사이의 거리 정보를 보존해야 한다.

3. Output

PCA는 $d$개의 bases, $d$개의 eigenvalue이다.

MDS는 $X \in R^{d}$ 인 각 object의 좌표가 output이다.

PCA에 비해 MDS는 cover 해야 하는 범위가 더 넓다. $D$ 차원에서 좌표로 표현된 $X$라는 데이터는 $X$를 통해 $d$ metrix를 만드는 것은 쉽지만, 반대로 $d$로부터 $X$를 만드는 것은 다차원 척도 법을 쓰지 않는 이상 만들 수 있는 방법은 없다.

이를 예로 설명하자면 사과, 포도, 바나나가 있을 때, 이들 간 유사도는 다음과 같이 정의된다고 가정하자.

사과 포도 바나나

사과	1	0.6	0.4
포도	0.6	1	0.5
바나나	0.4	0.5	1

위 테이블과 같이 행렬은 $N \times N$으로 정의가 되고, 같은 객체들끼리는 1인 것과, 대칭 행렬인 모습을 볼 수 있다.

만약 여기서 사과에 대한 데이터를 10차원으로 확장하라고 하면 그것은 불가능하다.

이를 통해 알 수 있는 사실은 MDS가 cover 할 수 있는 범위가 더 넓다는 것이고, 이는 PCA를 적용할 수 있는 데이터는 MDS를 적용할 수 있지만, MDS를 적용할 수 있는 모든 데이터는 PCA를 적용할 수 없다는 사실을 알 수 있다.

 

MDS Procedure

Step 1. Construct Proximity / Distance Matrix

만약 object에 대한 coordinate가 존재할 때, 그들의 거리 또는 유사도를 계산할 수 있다. 거리는 다음과 같은 조건을 따른다.

$$ \begin{align} &d_{ij} \geq 0 \\ &d_{ii} = 0 \\ &d_{ij} = d_{ji} \\ &d_{ij} \leq d_{ik}+d_{jk} \end{align} $$

1. distance는 0과 같거나 커야 한다.
2. 같은 객체들의 distance는 0이어야 한다.
3. 대칭 행렬을 만족해야 한다.
4. 삼각 부등식을 만족해야 한다. 여기서 $k$는 $i$와 $j$ 사이에 있어야 한다.

distance는 Euclidean, Manhattan 등 본인이 원하는 distance method를 사용해도 되고, Similarity는 correlation matrix, jaccard 등 많이 알려진 유사도 방법들을 사용하면 된다.

우리는 $d$ 차원에 $n$개의 $x$로 구성된 $d \times n$ shape을 같은 $X$를 각 object 별 유사도 / distance 지표를 갖는 $n \times n$ 크기의 행렬 $D$로 만드는 것이 목적이다.

이를 위해 $d_{rs}^{2}$로 부터 $x_{r}$과 $x_{s}$를 찾아야 한다.

Step 2. Extract the coordinates that preserve the distance information

Step 2는 distance information을 보존하는 coordinate system을 찾는 것이 목표이다.

Distance matrix $D$의 각 element는 다음 식과 같이 표현된다.

$$ d_{rs}^{2}= (\mathbf{x}{r}-\mathbf{x}{s})^{T}(\mathbf{x}{r}-\mathbf{x}{s}) $$

$\mathbf{x}$로 부터 스칼라 값인 $d_{rs}^{2}$를 구한다.

우리가 현재 가지고 있는 데이터의 구조는 $D$이다. $(n \times n)$ 이를 통해 $X$라는 $(d \times n)$ matrix를 찾고 싶은데, 이를 바로 찾기는 힘들어서 $B$라는 inner product matrix를 먼저 찾을 것이다. $(n \times n)$

$B$ matrix는 다음과 같이 정의 된다.

$$ [\mathbf{B}]{rs}= b{rs}= \mathbf{x}{r}^{T}\mathbf{x}{s} $$

이는 $\mathbf{x}{r}$ 과 $\mathbf{x}{s}$의 내적 값이다. (inner matrix)

계산에 앞서, 우리는 연산의 편의성을 위해 2가지 가정을 할 것이다.

$$ \begin{align} &\sum^{n}{r=1}x{ri}=0, \ (i=1,2,\dots,p) \\ &d_{rs}^{2}=\mathbf{x}{r}^{T}\mathbf{x}{r}+\mathbf{x}{s}^{T}\mathbf{x}{s}- 2\mathbf{x}{r}^{T}\mathbf{x}{s} \end{align} $$

(5)는 모든 변수는 centering을 진행하였기 때문에, 평균을 0으로 둔다.

(6)은 $d_{rs}^{2}= (\mathbf{x}{r}-\mathbf{x}{s})^{T}(\mathbf{x}{r}-\mathbf{x}{s})$를 풀어 쓴 식이다.

 

MDS의 수식을 설명하기 위해 몇 가지 정리가 필요하다.

$$ d_{rs}^{2}= (\mathbf{x}{r}-\mathbf{x}{s})^{T}(\mathbf{x}{r}-\mathbf{x}{s}) $$

위 distance 수식에 $r$에 대한 summataion을 진행하면 다음과 같이 된다.

$$ \frac{1}{n}\sum_{r=1}^{n}d^{2}{rs}=\frac{1}{n}\sum{r=1}^{n}\mathbf{x}^{T}{r}\mathbf{x}{r}+\frac{1}{n}\sum_{r=1}^{n}\mathbf{x}^{T}{s}\mathbf{x}{s}-\frac{2}{n}\sum_{r=1}^{n}\mathbf{x}^{T}{r}\mathbf{x}{s} = \frac{1}{n}\sum_{r=1}^{n}\mathbf{x}^{T}{r}\mathbf{x}{r}+\mathbf{x}^{T}{s}\mathbf{x}{s} $$

(6)을 통해 distance의 평균을 term 2와 같이 전개한 것을 확인할 수 있고, term 2에 $\mathbf{x}^{T}{s}\mathbf{x}{s}$는 $r$과는 상관이 없어 $n \times \mathbf{x}^{T}{r}\mathbf{x}{r}$가 된다. 그리고 term 2의 마지막 식은 (5)로 인해 0이 된다.

$$ \begin{align}\mathbf{x}^{T}{s}\mathbf{x}{s}=\frac{1}{n}\sum_{r=1}^{n}d^{2}{rs}+\frac{1}{n}\sum{r=1}^{n}\mathbf{x}^{T}{r}\mathbf{x}{r}\end{align} $$

수식을 다시 쓰면 위와 같이 정리할 수 있다.

distance 행렬을 $s$에 대해 summation을 진행하면 다음과 같이 쓸 수 있다.

$$ \frac{1}{n}\sum_{s=1}^{n}d^{2}{rs}=\frac{1}{n}\sum{s=1}^{n}\mathbf{x}^{T}{r}\mathbf{x}{r}+\frac{1}{n}\sum_{s=1}^{n}\mathbf{x}^{T}{s}\mathbf{x}{s}-\frac{2}{n}\sum_{s=1}^{n}\mathbf{x}^{T}{r}\mathbf{x}{s} =\mathbf{x}^{T}{r}\mathbf{x}{r}+ \frac{1}{n}\sum_{s=1}^{n}\mathbf{x}^{T}{s}\mathbf{x}{s} $$

(7)과 마찬가지로 정리하면 아래와 같은 식을 얻을 수 있다.

$$ \begin{align}\mathbf{x}^{T}{r}\mathbf{x}{r}=\frac{1}{n}\sum_{s=1}^{n}d^{2}{rs}-\frac{1}{n}\sum{s=1}^{n}\mathbf{x}^{T}{s}\mathbf{x}{s}\end{align} $$

이번에는 $r$과 $s$에 대해 summation을 진행해보자.

$$ \frac{1}{n^{2}}\sum_{r=1}^{n}\sum_{s=1}^{n}d^{2}{rs}=\frac{1}{n^{2}}\sum{r=1}^{n}\sum_{s=1}^{n}\mathbf{x}{r}^{T}\mathbf{x}{r}+ \frac{1}{n^{2}}\sum_{r=1}^{n}\sum_{s=1}^{n}\mathbf{x}{s}^{T}\mathbf{x}{s}-\frac{2}{n^{2}}\sum_{r=1}^{n}\sum_{s=1}^{n}\mathbf{x}{r}^{T}\mathbf{x}{s} \\ =\frac{1}{n}\sum_{r=1}^{n}\mathbf{x}{r}^{T}\mathbf{x}{r}+\frac{1}{n}\sum_{s=1}^{n}\mathbf{x}{s}^{T}\mathbf{x}{s}=\frac{2}{n}\sum_{r=1}^{n}\mathbf{x}{r}^{T}\mathbf{x}{r} $$

위 식을 정리하면 다음과 같다.

$$ \begin{align}\frac{2}{n}\sum_{r=1}^{n}\mathbf{x}{r}^{T}\mathbf{x}{r}=\frac{1}{n^{2}}\sum_{r=1}^{n}\sum_{s=1}^{n}d_{rs}^{2}\end{align} $$

위에서 정리한 식을 활용하여 distance matrix로부터 inner product matrix $\mathbf{B}$를 정의할 수 있다.

$$ \begin{align} b_{rs}&=\mathbf{x}{r}^{T}\mathbf{x}{s} \\ &=-\frac{1}{2}(d_{rs}^{2}-\mathbf{x}{r}^{T}\mathbf{x}{r}-\mathbf{x}{s}^{T}\mathbf{x}{s}) \\ &=-\frac{1}{2}(d_{rs}^{2}-\frac{1}{n}\sum_{s=1}^{n}d_{rs}^{2}+\frac{1}{n}\sum_{s=1}^{n}\mathbf{x}{s}^{T}\mathbf{x}{s}-\frac{1}{n}\sum^{n}{r=1}d^{2}{rs}+\frac{1}{n}\sum_{r=1}^{n}\mathbf{x}{r}^{T}\mathbf{x}{r}) \\ &= -\frac{1}{2}(d_{rs}^{2}-\frac{1}{n}\sum_{s=1}^{n}d_{rs}^{2}-\frac{1}{n}\sum_{r=1}^{n}d_{rs}^{2}+\frac{1}{n^{2}}\sum_{r=1}^{n}\sum_{s=1}^{n}d_{rs}^{2}) \\ &=a_{rs}-a_{r.}-a_{.s}+a_{..} \end{align} \\ \text{where} \ a_{rs}=-\frac{1}{2}d_{rs}^{2}, \ a_{r.}=\frac{1}{n}\sum_{s}a_{rs}, \ a_{.s}=\frac{1}{n}\sum_{r}a_{rs},\ a_{..}=\frac{1}{n^{2}}\sum_{r}\sum_{s}a_{rs}
$$

(10)에서 (11)은 (6)을 이용하여 변환한다.

(11)에서 (12)는 (7), (8)에서 구한 수식을 대입한다.

(12)에서 (13)은 (9)를 이용하여 구한다.

이를 통해 distance matrix로부터 inner product matrix인 $\mathbf{B}$를 distance의 선형 결합을 통해 만들 수 있다.

$$ [\mathbf{A}{rs}=a{rs}] \ \ \ \mathbf{B}=\mathbf{H}\mathbf{A}\mathbf{H} \ \ \ \mathbf{H}=\mathbf{I}-\frac{1}{n}11^{T} $$

앞 연산들을 통해 위 수식과 같이 $\mathbf{B}$ matrix에 대한 정의를 할 수 있다.

$\mathbf{B}$로부터 coordinate matrix인 $\mathbf{X}$를 구하기 위해 아래와 같은 연산을 진행한다.

$$ \mathbf{B} = \mathbf{X}\mathbf{X}^{T} \ \ \ rank(\mathbf{B})=rank(\mathbf{X}\mathbf{X}^{T})=rank(\mathbf{X})=p $$

$\mathbf{X}$가 $n \times p$ 행렬이고, $p <n$ 일 때, $\mathbf{B}$의 rank는 $p$가 된다.

또한 $\mathbf{B}$는 대칭 행렬이고, postive semi-definite를 만족하며, rank가 $p$이기 때문에, $p$개의 non-negative한 eigen value와 $n-p$개의 zero eigenvalue를 갖게 된다.

이를 표현하면 다음과 같다.

$$ \mathbf{B}=\mathbf{V}\mathbf{\Lambda}\mathbf{V}^{T}, \ \mathbf{\Lambda}=diag(\lambda_{1},\lambda_{2}, \dots, \lambda_{n}), \ \mathbf{V}=[\mathbf{v}{1}, \mathbf{v}{2}, \dots, \mathbf{v}_{n}] $$

$n-p$개의 zero eigenvalue를 제외하고 아래와 같이 다시 쓸 수 있다.

$$ \mathbf{B}{1}=\mathbf{V}{1}\mathbf{\Lambda}{1}\mathbf{V}^{T}{1}, \ \mathbf{\Lambda}{1}=diag(\lambda{1},\lambda_{2}, \dots, \lambda_{p}), \ \mathbf{V}{1}=[\mathbf{v}{1}, \mathbf{v}{2}, \dots, \mathbf{v}{p}] $$

$\mathbf{B}_{1}=\mathbf{X}\mathbf{X}^{T}$인 것을 활용하여 아래와 같이 $\mathbf{X}$를 구할 수 있다.

$$ \mathbf{X} = \mathbf{V}{1}\mathbf{\Lambda}{1}^{\frac{1}{2}} $$