[1-6] ISOMAP & LLE

ISOMAP : Isometric Feature Mapping

Isomap은 다차원 스케일링(MDS) 또는 주성분 분석(PCA)의 확장이자 두 방법론을 결합한 방법론으로 볼 수 있습니다. 앞서 다루었던 PCA와 MDS의 특징을 결합하여 모든 점 사이의 측지선 거리를 유지하는 더 낮은 차원의 임베딩을 추구합니다. 여기서 측지거리란, 두 측점사이의 타원체면을 따라 이루어진 거리를 말합니다.

위 그림 에 따르면 두 점은 유클리디안 거리로는 가깝지만 실제 측지거리를 구할 경우 색깔이 나타내는 의미만큼 멀리 떨어져 위치함을 알 수 있습니다. 즉, Isomap 알고리즘은 두 데이터간의 실제 특징을 반영하는 거리 정보를 사용하는 효과적인 차원 축소를 추구합니다.

ISOMAP 기법은 MDS 이다. 단, 거리의 정의만 다른 MDS 이다. MDS 에서 정의한 데이터 객체 사이의 거리가 실제 Manifold 상에서 도달가능한 거리가 아니기 때문이다. 따라서 ISOMAP 은 $d\ (distance\ matrix)$ 를 재정의한다. ISOMAP 프로세스는 3가지 단계로 구성됩니다.

ISOMAP 프로세스

1) 인접한 이웃 그래프 구축

첫번째 단계에서는 어떤 점들이 매니폴드 상에서 서로 가까이 위치하는지를 측정합니다. 두가지 방식이 사용되는데 첫번째는 고정된 기준값인 앱실론을 기준으로 그보다 거리가 가까운 경우의 모든 두 점을 서로 연결합니다. 두번째는 자기 자신과 가장 가까운 K개의 점을 연결하는 KNN방식으로 모든 점들을 서로 연결합니다. 첫번째 단계가 진행된 후의 모습은 아래 그림과 같습니다.

$\epsilon - Isomap$ : $\epsilon$ 반경 이내의 모든 점을 잇는다.
$k - Isomap$ : 특정 개체에서 k 개의 이웃들을 연결해준다.

이렇게 점끼리 연결되었을때 엣지의 가중치는 두 연결된 점 사이의 유클리디안 거리가 됩니다.

2) 두 점 간의 최단 경로 그래프 계산

두 점사이가 연결되어 있으면, inf 로 초기화 하고, 그래프 상에서 최단 거리 알고리즘을 사용하여 거리 행렬을 구한다.

두 점 i와 j에 대하여 두 점이 서로 연결되어 있다면 $d_G$ ( i , j ) = d X ( i , j ) 서로 연결되어 있지 않으면 $d_G$ ( i , j ) 를 무한으로 초기화합니다. 그 후 1부터 N개 까지의 k에 있어서 점 i와 j간의 최단 거리를 의미하는 d G ( i , j ) 를 m i n ( d G ( i , j ) , d g ( i , k ) + d G ( k , i ) ) 로 변환합니다. 이 과정에서는 대표적으로 Dijkstra 알고리즘, Floyd’s 알고리즘 등이 사용됩니다.

min\{d_G(i, j), d_G(i, k)+d_G(k, i)\}

3) MDS 방법론을 사용하여 d차원 임베딩 구축

위에서 구한 거리 행렬을 기반으로 MDS 를 수행함.

위 그림은 손글씨 2에 해당하는 MNIST데이터를 Isomap을 활용하여 2차원으로 축소한 결과입니다. 아래로 내려갈수록 숫자 2의 윗부분에 동그랗게 그려지고 오른쪽으로 갈수록 숫자 2의 아랫부분이 동그랗게 그려지는 특징을 정확히 잡아냈음을 확인할 수 있습니다.

LLE : Locally Linear Embedding

LLE 의 핵심목적은 특정 개체를 잘 표현하는 이웃들의 가중치를 찾는 것이 목적입니다. 로컬 선형 임베딩(Local Linear Embedding)은 고차원의 공간에서 인접해 있는 데이터들 사이의 선형적 구조를 보존하면서 저차원으로 임베딩하는 방법론입니다. 즉 좁은 범위에서 구축한 선형모델을 연결하면 다양체, 매니폴드를 잘 표현할 수 있다는 알고리즘입니다. LLE는 다음과 같은 장점을 갖습니다.