Dimensionality Reduction - MDS (Multi-Dimensional Scaling)

July 09, 2022

2022   ·   machine-learning  

Contents

  • Multi-Dimensional Scaling (MDS)

    • Step 1: Proximity Matrix
    • Step 2: Extracting Coordinates

Multi-Dimensional Scaling (MDS)

Multi-Dimensional Scaling (MDS), 혹은 다차원척도법은 주성분분석(PCA) 과 함께 대표적인 선형변환 차원축소 방법론/변수추출기법이다. PCA 가 데이터의 분산을 최대한 보존하며 낮은 차원으로 데이터를 사영했다면, MDS 는 객체들간 거리를 최대한 보존하며 낮은 차원으로 데이터를 투영시킨다. 그렇기에 MDS 의 최종 목표는 객체들간의 거리를 최대한 보존하는 좌표계를 찾는 것이다.

  Principal Component Analysis Multi-Dimensional Scaling
Data \(n\) objects in a \(d\) dimensional space Proximity matrix between \(n\) objects
Purpose Find a set of bases to preserve the original variance Find a set of coordinates that preserve the distance information between objects
Output \(d\) bases (eigenvectors) and eigenvalues Coordinate of each object in \(d\) dimensional space

Coverage, 혹은 범용성은 PCA 보다 MDS 가 높다.

MDS 가 기본적으로 사용하는 것은 데이터의 Proximity Matrix \(\mathbf{D}\) 이고, 이는 기존 데이터에서 쉽게 구축 할 수 있기 때문이다. 그렇기에 MDS 로 \(\mathbf{D \Rightarrow X}\) 는 가능하지만 다른 방법론으론 어렵다.

MDS: \(\mathbf{D \Rightarrow X \Rightarrow \lambda}\)

PCA: \(\mathbf{X \Rightarrow \lambda}\)

Step 1: Proximity Matrix

기존 데이터셋인 \(\mathbf{X} \ (d\times n)\) 이 있다면, 객체간의 거리를 정의하여 대칭행렬 \(\mathbf{D} \ (n\times n)\) 을 만들 수 있다. 이때 객체간의 거리는 Euclidean, Manhattan Distance 같은 기본적인 거리로 정의할 수 있으며, 거리 대신 Correlation, Jaccard 같은 유사도로도 정의 할 수 있다. 이때 \(\mathbf{D}\) 에 대한 제약은 다음과 같다.

\[d_{ij} \geq 0, \ d_{ii} = 0, \ d_{ij} = d_{ji} \\ d_{ij} \leq d_{ik}+d_{kj}\]

\(\mathbf{D}\) 는 모든 객체들이 0보다 크거나 같은 값을 갖고 대각성분이 0 인 대칭행렬임을 첫째줄에서 표현하고, 삼각부등식의 제약 또한 만족해야 한다.

\(\mathbf{D}\) 에서 임의의 두 객체들간의 거리는 다음과 같은 공식으로 계산할 수 있다. 이때 객체라 함은 데이터셋 \(\mathbf{X}\) 의 각 샘플이다.

\[d^2_{rs} = (\mathbf{x_r - x_s})^T(\mathbf{x_r - x_s})\]

즉, 샘플 \(r,s\) 간의 거리의 제곱은 위와 같은 행렬식으로 계산되는 스칼라값이다.

Step 2: Extracting Coordinates

각 샘플이 \(d^2_{rs} = (\mathbf{x_r - x_s})^T(\mathbf{x_r - x_s})\) 인 객체들간의 거리정보를 담고 있는 행렬 \(\mathbf{D}\) 를 구축했다. \(\mathbf{D}\) 로부터 바로 \(\mathbf{X}\) 를 구할 수 없기 때문에 임의의 행렬 \(\mathbf{B}\) 를 만든다. 이때 \(\mathbf{B}\) 는 \(\mathbf{D}\) 의 모든 샘플에 대한 내적값으로 채워진다.

\[\mathbf{[B]}_{rs} = b_{rs} = \mathbf{x^T_r x_s}\]

이때 모든 변수 \(p\) 의 평균은 0이라고 가정한다.

\[\sum_{r=1}^{n} x_{r i}=0,(i=1,2, \ldots, p) \quad d_{r s}^{2}=\mathbf{x}_{r}^{T} \mathbf{x}_{r}+\mathbf{x}_{s}^{T} \mathbf{x}_{s}-2 \mathbf{x}_{r}^{T} \mathbf{x}_{s}\]

샘플 \(r, s\) 간의 거리의 제곱식을 전개하면 우측과 같은 식으로 표현할 수 있다.

\[\begin{gathered} b_{r s}=\mathbf{x}_{r}^{T} \mathbf{x}_{s}=-\frac{1}{2}\left(d_{r s}^{2}-\frac{1}{n} \sum_{s=1}^{n} d_{r s}^{2}-\frac{1}{n} \sum_{r=1}^{n} d_{r s}^{2}+\frac{1}{n^{2}} \sum_{r=1}^{n} \sum_{s=1}^{n} d_{r s}^{2}\right) \\ =a_{r s}-a_{r .}-a_{\cdot s}+a_{. .} \\ \left(\text {where } a_{r s}=-\frac{1}{2} d_{r s}^{2}, a_{r .}=\frac{1}{n} \sum_{s} a_{r s}, a_{\cdot s}=\frac{1}{n} \sum_{r} a_{r s}, a_{. .}=\frac{1}{n^{2}} \sum_{r} \sum_{s} a_{r s}\right) \\ {[\mathbf{A}]_{r s}=a_{r s} \quad \mathbf{B}=\mathbf{H A H} \quad \mathbf{H}=\mathbf{I}-\frac{1}{n} \mathbf{1 1} ^{T}} \end{gathered}\]

수학적인 트릭을 이용해 임의의 행렬 \(\mathbf{B}\) 를 위와 같이 전개할 수 있으며, 최종적인 좌표계 행렬 \(\mathbf{X}\) 는 \(\mathbf{X = V_1\Lambda_1^{1 \over 2}}\) 가 된다.

사실 MDS 에서 좌표계 행렬 \(\mathbf{X}\) 을 구하는 과정은 이보다 훨씬 복잡하다. 요즘 MDS 는 그저 단일 차원축소 방법론으로 사용하지 않지만, ISOMAP 의 기본 연산이 되기 때문에 Proximity/Distance Matrix \(\mathbf{D}\) 에서 저차원의 좌표계 \(\mathbf{X}\) 로 투영되는 개념을 알아가면 좋다.

해당 포스트는 강필성 교수님의 Business Analytics 를 참고하여 작성되었습니다.