다차원 척도법

1. 개요[편집]

다차원 척도법 Multidimensional Scaling (MDS)
입력	좌표가 아니라 비유사도 행렬 $\Delta = (\delta_{ij})$
출력	$k$ 차원 좌표 $X \in \mathbb R^{n\times k}$
고전 MDS	이중 중심화 → 그람행렬 고유분해 (Torgerson 1952)
PCA와의 관계	유클리드 거리에서 완전히 동치
비계량 MDS	순위만 보존 · 응력 최소화 (Shepard 1962 · Kruskal 1964)
표준 알고리즘	SMACOF — 다수화 반복 (de Leeuw 1977)
불변	평행이동 · 회전 · 반사 — 축에는 의미가 없다

도시 사이의 도로 거리표만 주고 지도를 그려 보라고 하면, 사람은 못 한다. 행렬 하나 고유분해하면 나온다.

다차원 척도법(Multidimensional Scaling, MDS)은 $n$ 개 대상 사이의 비유사도(거리·차이·불일치도) 행렬만 주어졌을 때, 그 값들을 최대한 잘 재현하는 저차원 좌표 $x_1,\dots,x_n$ 을 복원하는 기법이다. 주성분 분석이 “좌표가 있는데 차원을 줄이고 싶다”는 문제라면, MDS는 애초에 좌표라는 것이 없고 쌍별 관계만 있는 문제를 다룬다.

이 차이가 응용 범위를 결정한다. 두 단백질 구조 사이의 RMSD, 두 유전자 서열의 정렬 점수, 설문 응답자가 매긴 “이 둘은 얼마나 비슷한가”, NMR로 잰 원자쌍 사이의 거리 구속, 무선 노드 사이의 전파 도달 시간 — 전부 쌍별 숫자는 있는데 그 대상이 사는 공간이 없는 데이터다. MDS는 그런 데이터에 좌표계를 사후적으로 붙여 준다. 그 좌표계는 진짜일 수도 있고(원자는 실제로 3차원에 있다), 순전히 시각화용 허구일 수도 있다(브랜드 이미지 지도).

2. 고전 MDS — 거리에서 내적으로[편집]

핵심 관찰 하나로 전부 풀린다. 거리는 내적으로 되돌릴 수 있다. 좌표들이 중심화되어 있다고 하면($\sum_i x_i = 0$),

$$d_{ij}^2 = \|x_i\|^2 + \|x_j\|^2 - 2\,x_i^{\mathsf T}x_j$$

에서 $x_i^{\mathsf T}x_j$ 를 뽑아낼 수 있다. 행·열·전체 평균을 빼는 이중 중심화가 그 절차다.

$$b_{ij} = -\tfrac12\Bigl( d_{ij}^2 - \tfrac1n\textstyle\sum_k d_{ik}^2 - \tfrac1n\sum_k d_{kj}^2 + \tfrac1{n^2}\sum_{k,l} d_{kl}^2 \Bigr)$$

행렬로 쓰면 훨씬 짧다. $J = I - \tfrac1n\mathbf 1\mathbf 1^{\mathsf T}$ 를 중심화 사영행렬, $D^{(2)}$ 를 거리 제곱 행렬이라 할 때

$$B = -\tfrac12\, J\, D^{(2)}\, J$$

그리고 $B = XX^{\mathsf T}$ 는 바로 그람행렬이다. 남은 것은 대칭 고유값 문제뿐이다.

$$B = V\Lambda V^{\mathsf T}, \qquad X = V_k\,\Lambda_k^{1/2}$$

상위 $k$ 개 고유쌍만 쓰면 $k$ 차원 배치가 나온다. 이 절단이 최선이라는 것도 공짜로 따라온다 — $\|B - XX^{\mathsf T}\|_F$ 를 최소화하는 랭크 $k$ 행렬이 상위 고유쌍이라는 에카르트-영 정리 그대로다.¹

3. PCA와 같은 것이었다[편집]

$D$ 가 진짜 유클리드 거리(어떤 좌표 $Y\in\mathbb R^{n\times p}$ 에서 나온 것)라면, 고전 MDS의 결과는 $Y$ 에 주성분 분석을 건 것과 회전을 빼고 같다. 증명은 두 줄이다. 중심화된 $Y_c$ 에 대해

$$B = Y_cY_c^{\mathsf T} \ (n\times n), \qquad (n-1)\,C = Y_c^{\mathsf T}Y_c \ (p\times p)$$

인데, $Y_cY_c^{\mathsf T}$ 와 $Y_c^{\mathsf T}Y_c$ 는 0이 아닌 고유값이 같고 고유벡터는 특이값 분해 $Y_c = U\Sigma V^{\mathsf T}$ 로 서로 옮겨간다. MDS는 $U\Sigma$ 를 좌표로 쓰고 PCA는 $Y_cV = U\Sigma$ 를 점수로 쓴다. 같은 물건이다.

실무적 함의가 재밌다. 둘 중 작은 쪽 행렬을 분해하면 된다. 관측이 적고 변수가 많으면($n \ll p$) $n\times n$ 을 푸는 것이 이득이고, 이것이 유동 POD에서 “스냅숏 기법”이라 부르는 바로 그 요령이다. 다시 말해 적합직교분해의 스냅숏 방법은 고전 MDS와 같은 대각화를 하고 있다.

4. 이 거리가 유클리드이긴 한가[편집]

주어진 $\Delta$ 가 어떤 유클리드 공간에도 들어가지 않을 수 있다. 판정 기준은 놀랄 만큼 깔끔하다 — $B$ 가 양반정치이면 유클리드 삽입이 가능하고, 아니면 불가능하다. 쇤베르크와 영·하우스홀더가 1930년대에 정리한 결과다. 그리고 $B$ 의 랭크가 필요한 최소 차원이다.

$B$ 에 음의 고유값이 나오면 그것이 비유클리드성의 크기를 재는 눈금이 된다. 실무 대처는 셋이다.

1. 음의 고유값을 그냥 버린다(대부분의 구현 기본값). 크기가 양의 고유값에 비해 작으면 합리적이다.
2. 모든 비대각 거리에 상수 $c$ 를 더해 유클리드로 만든다(가법 상수 문제). 순위는 보존되지만 거리의 물리적 의미는 사라진다.
3. 애초에 거리 보존을 포기하고 아래의 응력 최소화로 간다.

무엇을 택하든 버려진 음의 고유값의 크기를 확인하는 것이 진단의 시작이다. 상관 기반 비유사도, 그래프 최단경로, 순위 데이터는 삼각부등식조차 깨지는 경우가 흔하고, 그때 나온 예쁜 2차원 그림은 거리를 재현한 것이 아니라 억지로 눌러 담은 것이다.

5. 응력 — 다른 목적함수로 갈아타기[편집]

고전 MDS는 내적을 맞추지 거리를 직접 맞추지 않는다. 거리를 직접 맞추고 싶으면 목적함수를 바꾼다. 크러스컬의 응력(stress)이 표준이다.

$$\sigma(X) \;=\; \sum_{i<j} w_{ij}\bigl(d_{ij}(X) - \hat\delta_{ij}\bigr)^2, \qquad \sigma_1 = \sqrt{\frac{\sigma(X)}{\sum_{i<j} w_{ij}\,d_{ij}(X)^2}}$$

$\sigma_1$ 이 정규화된 stress-1이다. 얻는 것이 셋이다. 가중치 $w_{ij}$ 로 신뢰도가 다른 관측을 다르게 대우할 수 있고(관측되지 않은 쌍은 $w_{ij}=0$ 으로 그냥 빼면 된다), 큰 거리보다 작은 거리를 잘 맞추도록 저울을 기울일 수 있으며, 아래의 비계량 확장이 자연스럽게 붙는다.

비계량 MDS는 $\delta_{ij}$ 의 순위만 믿는다. “A와 B가 A와 C보다 가깝다”는 정보는 있지만 그 차이가 두 배인지 세 배인지는 믿을 수 없는 데이터 — 설문의 리커트 척도, 전문가의 유사도 판단 — 가 대상이다. 그래서 $\hat\delta$ 를 고정된 값이 아니라 $\delta$ 의 순서를 지키는 임의의 단조 변환으로 두고 좌표와 함께 최적화한다. 매 반복에서 현재 거리 $d_{ij}(X)$ 에 대해 단조 회귀(인접 위반 병합, PAV)를 걸어 $\hat\delta$ 를 갱신하고, 그 $\hat\delta$ 로 좌표를 갱신하는 교대 최적화다. 결과 진단으로는 $\delta_{ij}$ 대 $d_{ij}$ 를 찍은 셰퍼드 도표를 보는데, 점들이 단조 곡선 주위에 좁게 모여 있으면 잘 맞은 것이다.²

6. SMACOF — 다수화라는 트릭[편집]

응력은 제곱근과 분모 때문에 다루기 고약하고, 경사법을 쓰면 보폭을 정해야 한다. SMACOF(Scaling by MAjorizing A COmplicated Function)는 다수화(majorization)로 이 둘을 동시에 없앤다.

다수화의 아이디어는 일반적이다. 어려운 함수 $\sigma(X)$ 위에 얹히면서 현재 점 $Z$ 에서만 닿는 쉬운 함수 $\tau(X,Z)$ 를 만든다.

$$\sigma(X) \le \tau(X,Z)\ \ \forall X, \qquad \sigma(Z) = \tau(Z,Z)$$

그러면 $\tau$ 를 최소화한 점 $X^{+}$ 에 대해 $\sigma(X^{+}) \le \tau(X^{+},Z) \le \tau(Z,Z) = \sigma(Z)$ 가 자동으로 성립한다. 목적함수가 절대 증가하지 않는다 — 보폭도, 선탐색도 필요 없다. EM 알고리즘이 우도에 대해 하는 일과 정확히 같은 구조다.

MDS에서는 응력을 세 조각으로 갈라 놓는 데서 출발한다.

$$\sigma(X) = \underbrace{\textstyle\sum w_{ij}\hat\delta_{ij}^2}_{\text{상수}} + \operatorname{tr}\bigl(X^{\mathsf T}VX\bigr) - 2\operatorname{tr}\bigl(X^{\mathsf T}B(X)X\bigr)$$

가운데 항은 $X$ 에 대해 이차식이라 다루기 쉽고, 문제는 마지막 항이다. 여기에 코시-슈바르츠 부등식을 걸면 $\operatorname{tr}(X^{\mathsf T}B(X)X) \ge \operatorname{tr}(X^{\mathsf T}B(Z)Z)$ 가 나오고, 부호가 음수이므로 그대로 다수화 함수가 완성된다. $\tau$ 는 $X$ 에 대한 이차식이니 미분해서 0으로 놓으면 닫힌 해가 나온다. 이것이 구트만 변환이다.

$$X^{+} = V^{+}B(Z)\,Z \qquad\xrightarrow{\ w_{ij}\equiv1\ }\qquad X^{+} = \frac1n\,B(Z)\,Z$$

$B(Z)$ 의 원소는 비대각에 $b_{ij} = -w_{ij}\hat\delta_{ij}/d_{ij}(Z)$($d_{ij}(Z)=0$ 이면 0), 대각에 $b_{ii} = -\sum_{j\ne i} b_{ij}$ 다. 읽어 보면 의미가 선명하다 — 각 점을, 이웃들이 “나한테서 $\hat\delta$ 만큼 떨어져 있어 달라”고 잡아당기는 방향들의 가중 평균 자리로 옮긴다. 스프링 이완의 이산판이고, 실제로 그래프 그리기의 힘-방향 배치 알고리즘과 사촌이다.

성질을 정리하면 이렇다. 응력이 단조 감소하는 것이 보장되고, 반복 하나가 행렬-행렬 곱 한 번($O(n^2k)$)이라 구현이 짧다. 대신 수렴은 선형이라 느리고, 응력은 볼록이 아니므로 국소최소에 빠진다. 표준 처방은 고전 MDS 해를 초기값으로 쓰고, 무작위 초기값으로도 몇 번 돌려 응력이 가장 낮은 것을 고르는 것이다. 결과가 초기값마다 다르면 그 자체가 “이 데이터는 $k$ 차원에 안 들어간다”는 신호일 때가 많다.

7. 축을 읽지 마라 — 불변성[편집]

MDS 해는 평행이동·회전·반사에 대해 불변이다. 거리는 강체운동으로 변하지 않으므로 원리적으로 그 이상 결정될 수 없다. 여기서 두 가지 실무 규칙이 따라온다.

• 좌표축에 해석을 붙이면 안 된다. “가로축은 가격, 세로축은 품질”이라는 문장은 MDS 결과 자체가 뒷받침해 주지 않는다. 고전 MDS는 관례적으로 주축 방향으로 정렬해 주므로 축이 의미 있어 보이지만, 그것은 분산 순서일 뿐이고 비계량 MDS에서는 그마저 없다. 해석은 점들의 상대 배치에 대해서만 하는 것이 안전하다.³
• 두 MDS 결과를 비교하려면 먼저 정렬해야 한다. 조건이 다른 두 실험의 배치를 겹쳐 보려면 회전·반사·크기를 맞추는 직교 프로크루스테스 문제를 한 번 풀고 시작한다. 이 절차를 빼먹고 “두 그림이 다르다”고 결론 내리는 사고가 잦다.

8. 차원은 몇으로 — 응력 스크리[편집]

차원 $k$ 를 키우면 응력은 반드시 감소한다(자유도가 늘어나니까). 그래서 응력이 낮다는 사실 자체는 아무 근거가 되지 못하고, $k$ 에 대한 응력 곡선을 그려 팔꿈치를 찾는 스크리 방식이 표준이다. 주성분 분석의 스크리 도표와 같은 논리이며, 고전 MDS라면 고유값 스크리를 그대로 봐도 된다.

크러스컬이 제시한 stress-1의 눈대중 기준(0.20 나쁨 / 0.10 보통 / 0.05 좋음 / 0.025 매우 좋음)이 지금도 인용되는데, 이 숫자들은 $n$ 과 $k$ 에 의존하므로 절대 기준이 아니다. 점이 적으면 아무 데이터나 응력이 낮게 나온다. 정직한 진단은 같은 $n,k$ 에서 무작위로 만든 비유사도의 응력 분포와 비교하는 것이고, 여기에 셰퍼드 도표와 여러 초기값에서의 재현성을 얹으면 대체로 충분하다.

9. 계보 — MDS에서 갈라져 나온 것들[편집]

MDS는 비선형 차원축소 계보의 뿌리 쪽에 있다.

방법	MDS와의 관계
고전 MDS	유클리드 거리 → PCA와 동치
Isomap	유클리드 거리를 그래프 최단경로(측지거리) 로 바꾸고 고전 MDS를 그대로 적용
커널 PCA	고전 MDS의 그람행렬을 임의의 커널행렬로 일반화
t-SNE · UMAP	거리 보존을 포기하고 이웃 확률분포의 일치로 목적을 갈아탐

Isomap이 특히 명확하다 — “거리를 어떻게 정의할 것인가”만 바꾸고 뒤쪽 기계는 고전 MDS를 그대로 재사용한다. 반면 t-SNE·UMAP은 목적함수를 갈아탄 것이라 성질이 근본적으로 달라진다. 이들의 그림에서 덩어리 사이의 거리를 읽으면 안 되는 이유가 바로 여기 있다. MDS는 (잘 맞았다면) 거리를 재현하려고 노력한 결과이지만, t-SNE는 애초에 그것을 목표로 삼지 않았다. 이 계보 전체의 통일된 서술은 다양체 학습 문서에 있다.

10. 규모와 계산[편집]

• 메모리가 $O(n^2)$, 고유분해가 $O(n^3)$ 이라 $n$ 이 수만이면 그대로는 안 돌아간다. 표준 우회는 랜드마크 MDS — 대표점 $m \ll n$ 개에만 고전 MDS를 걸고, 나머지는 랜드마크까지의 거리로 삼변측량하듯 배치한다. 나이스트룀 근사의 MDS판이다.
• 상위 고유쌍 몇 개만 필요하므로 전체 분해를 할 이유가 없다. 란초스 알고리즘이나 랜덤화 SVD 같은 저랭크 근사 도구가 그대로 쓰인다.
• SMACOF는 반복당 $O(n^2k)$ 이고 $B(Z)$ 가 가중치의 희소성을 그대로 물려받는다. 그래서 관측되지 않은 쌍이 많을수록 오히려 싸진다 — 결측이 결함이 아니라 이득이 되는 드문 상황이다. 여기까지 가면 문제는 사실상 거리행렬 행렬 완성과 붙는다.

11. 시뮬레이션 쪽에서의 쓸모[편집]

• 거리기하와 분자 구조. NMR의 NOE 측정은 원자쌍 사이의 대략적 거리 구속을 준다. 이 불완전한 거리행렬에서 3차원 좌표를 복원하는 것이 고전적인 거리기하 문제이며, MDS(특히 가중 SMACOF)가 초기 구조 생성에 쓰이고 그다음을 분자동역학 정련이 이어받는다.
• 형태공간 지도. 궤적에서 뽑은 구조들끼리 직교 프로크루스테스 문제로 정렬한 뒤 RMSD를 재면 비유사도 행렬이 하나 나온다. 여기에 MDS를 걸면 형태공간의 2~3차원 지도가 되고, 그 위에서 군집을 보거나 자유에너지를 재구성한다. 좌표가 없는 대상에 좌표를 붙이는 MDS의 본령이다.
• 거리 관측만으로 하는 위치추정. 무선 노드 사이의 거리만 알고 절대 좌표를 모르는 센서망에서 배치를 복원하는 문제가 그대로 MDS다. 결과가 회전·반사까지만 정해진다는 점도 SLAM의 게이지 자유도와 정확히 같은 이야기다.
• 설계공간·해공간의 조망. 파라미터를 바꿔 가며 돌린 해석 결과들 사이에 물리적으로 의미 있는 거리(장의 $L^2$ 차이, 스펙트럼 거리 등)를 정의하면, MDS가 “이 설계들은 서로 얼마나 다른 해를 낳는가”의 지도를 그려 준다. 실험계획법으로 뽑은 표본이나 대리 모델 구축 전 탐색 단계에서 쓸모가 있다.

12. 관련 문서[편집]

• 주성분 분석 · 특이값 분해 · 고유값 문제 · 저랭크 근사
• 다양체 학습 · Isomap · t-SNE · UMAP · 차원의 저주
• 직교 프로크루스테스 문제 · 행렬 완성 · 란초스 알고리즘 · 랜덤화 SVD
• 적합직교분해 · k-평균 군집화 · 스펙트럴 군집화
• 분자동역학 · 실험계획법 · 대리 모델 · SLAM

13. Footnotes[편집]

1. 이 기준을 응력(stress)과 구별해 긴장도(strain)라 부른다. 응력이 거리 자체의 오차를 재는 데 반해 긴장도는 이중 중심화된 내적의 오차를 재므로, 둘의 최적해는 일반적으로 다르다. 고전 MDS가 닫힌 해를 갖는 것은 순전히 이 기준을 골랐기 때문이고, 공짜 점심이 아니라 목적함수를 계산하기 편한 쪽으로 바꾼 대가다. ↩

2. 비계량 MDS의 고전적 사고는 퇴화 해다. 순위만 맞추면 되므로, 점들을 두세 덩어리로 완전히 뭉쳐 놓으면 응력이 거의 0으로 떨어지는 배치가 존재한다. 아름답게 분리된 군집 그림이 나왔는데 응력이 수상하게 낮다면, 데이터가 군집을 이룬 것이 아니라 알고리즘이 목적함수를 해킹한 것일 수 있다. 셰퍼드 도표가 계단 몇 개로 보이면 확정이다. ↩

3. 미국 도시 간 도로 거리표에 고전 MDS를 걸면 실제 지도와 거의 같은 배치가 나오는데, 남북이 뒤집혀 나오는 경우가 절반이다. 반사 불변성 때문이라 알고리즘 잘못이 아니지만, 슬라이드에 그대로 올렸다가 청중의 첫 질문을 “왜 플로리다가 위에 있죠”로 받게 된다. ↩