확산 지도(Diffusion map)는 2006년 Ronald R. Coifman과 Stéphane Lafon이 소개한 비선형 차원 축소 기법이다. 이 기법은 데이터 포인트에 대한 무작위 보행 또는 확산 과정을 모델링하여 고차원 데이터의 저차원 표현을 구성한다. 이 방법은 데이터 다양체의 고유 기하 구조를 포착하며, 전역적 거리를 무시하고 국소적 연결을 강조하여 노이즈와 이상치에 강건하다. 확산 지도는 Machine learning , 데이터 분석, 과학 컴퓨팅 분야에서 시각화, 군집화, 노이즈 제거 등의 작업에 널리 적용된다.
핵심 아이디어는 데이터 포인트에 대한 마르코프 체인을 정의하고, 전이 확률이 포인트 간 유사성을 반영하도록 하는 것이다. 전이 행렬의 고유벡터를 분석함으로써, 이 방법은 유클리드 거리가 확산 거리(다양체를 따른 연결성의 척도)에 근사하는 유클리드 공간에 데이터를 임베딩한다. 이 임베딩은 국소 구조를 유지하면서 전역 패턴을 드러내며, 비선형 데이터에서 주성분 분석과 같은 선형 방법보다 종종 우수한 성능을 보인다.
수학적 기초
확산 지도 알고리즘은 일반적으로 가우시안 커널인 \( k(x_i, x_j) = \exp(-\|x_i - x_j\|^2 / \epsilon) \)로 시작한다. 여기서 \( \epsilon \)은 이웃 크기를 제어하는 스케일 매개변수이다. 이 커널로부터 커널 행렬을 정규화하여 행-확률적 행렬 \( P \)를 구성한다. 행렬 \( P \)는 데이터 그래프에서 무작위 보행의 전이 확률을 나타내며, \(P_{ij}\)는 점 \( i \)에서 점 \( j \)로 한 단계 이동할 확률이다.
확산 과정은 \( P \)의 거듭제곱을 통해 연구되며, \( P^t \)는 \( t \)-단계 전이 확률을 제공한다. 시간 \( t \)에서 두 점 사이의 확산 거리는 t 단계 후 확률 분포 사이의 가중 \( L^2 \) 거리로 정의된다. 핵심 결과는 이 거리가 \( P \)의 고유벡터와 고유값을 사용하여 계산될 수 있다는 것이다. 구체적으로 확산 지도는 각 점 \( x_i \)를 스케일된 고유벡터의 구성 요소로 벡터로 임베딩한다: \( \Psi_t(x_i) = (\lambda_1^t \psi_1(i), \lambda_2^t \psi_2(i), \ldots) \lambda_k \)와 \( \psi_k \)는 고유값과 고유벡터이다. 첫 번째 \( d \) 고유벡터로 절단하면 확산 거리를 근사하는 차원 임베딩이 얻어진다.
스펙트럼 클러스터링 및 다양체 학습과의 관계
확산 지도는 Laplacian eigenmaps 와 spectral clustering를 포함하는 스펙트럼 방법 계열에 속한다.최단 경로 거리에 의존하는 방법과 달리 확산 지도는 전체 확산 과정을 사용하므로 노이즈로 인한 단락 연결에 더 강건한다. 매개변터 \( t \)는 분석 스케일을 제어한다: 작은 \( t \)는 국소 구조를 강조하고, 큰 \( t \)는 전역 연결을 강조한다. 이 유연성은 실무자가 여러 해상도에서 데이터를 탐색할 수 있게 한다.
이 방법은 확산 과정이 열 방정식을 근사하기 때문에 다양체에 대한 열 커널과 밀접한 관련이 있다. 이 연결은 데이터 포인트 수가 증가하고 \( \epsilon \)이 감소함에 따라 고유벡터가 기저 다양체의 Laplace-Beltrami 연산자의 고유 션으로 수렴한다는 이론적 보장을 제공한다. 이 속성은 확산 지도를 Coifman과 Shahpin의 연구에서 입증된 다양한 학습을 위한 원칙적인 도구로 만든다.
기계 학습 및 과학에서의 응용
Machine learning에서 확산 지도는 군집화 또는 분류를 위한 사전 처리 단계로 비선형 특징 추출에 사용된다. 예를 들어, 이미지 분석에서 모양이나 질감에 따라 명시적 라벨 없이 다양한 객체 클래스를 분리할 있다. Artificial intelligence 연구에서 확산 지도를 Neural network 해석력에 적용고차원 활성화를 저차원 공간에서 시각화했다.
과학 분야에서 확산 지도는 단세포 RNA 시는 모든 시퀀스 데이터 분석하는 데 사용하여 세포 유형과 궤적을 식별하는 데 도움을 준다. 또한 단백질 경계를 기술하는 집단 변수를 발견하기 위해 분자 역학 적용한다. 이 방법은 scikit-learn 등 다양한 소프트웨어 라이브코딩에서 구현되어 Python 사용자에게 DiffusionMap 클래스를 제공한다.
확장 및 변형
원래 알고리즘의 한계를 해결하기 위해 여러 확장이 개발되었다. 등방성 확산 지도는 비표준적인데 포인트 샘플을 처리하기 위해 밀도 정규화 매개변수 \( \alpha \)를 도입한다. 다중 스케일 확산 지도는 여러 시간 스케일 \( t \)를 조합하여 국소 및 전역 구조가 포착한다. 또한, 아웃오브스표준 외부 표본 확장 기법은 Nyström 방법 또는 기하 고조음을 사용해 전체 지도를 다시 계산하지 않고 새 데이터 포인트를 임베딩할 수 있게 한다.
최근 연구에서는 확산 지도를 Deep learning 구조와 통합하고 있다. 예를 들어, 확산 지도 좌표는 residual networks에서 보조 대상으로 사용되며 표현 학습을 개선할 수 있다. 또한, 확산 과정이 생성적 확산 모델을 고무하는 확산 지도를 Generative AI 모델에 적용하는 작업도 있지만, 이는 차원 축소 기법과는 별개다.
계산 고려 사항
확산 지도의 주요 계산 비용은 커널 행렬을 구성고 고유벡터를 계산하는 것이다. 실제 데이터 세트에 대해서는 점 \( n \)에 따라 행렬이 \( n \times n \)이므로 이를 방해할 수 있다. \( k \)-최근접 이웃을 사용하여 작은 커널 값을 0으로 설정하는 스파 스승 근사는 메모리와 시간을 줄인다. AWS 및 Google Cloud 같은 라이브러리에서 구현된 확률적 고유 분해 알고리즘은 계산을 가속화할 수 있다. 실제로 확산 종은 최대 수만 포인트의 데이터 세트 자체에 일반적으로 적용지만, 대규모 데이터에 대한 확장 가능한 변형도 존재한다.
스케일 매개변수 \( \epsilon \)의 선택이 두드러진다. 너무 작으면 그래프가 분리되고, 너무 크면 임베딩이 로컬 세부 사항을 잃을 수 있다. 휴리스틱에는 \( \epsilon \)을 살아있는 거리의 중간값으로 설정하거나 엔트로피 기반 기준을 사용하는 것이 포함된다. 시간 매개변수 \( t \)는 단순화을 위해 종종 1으로 설정하지만, 더 큰 값은 글로벌 구조를 개선할 수 있는 반면 미세한 세부 사항을 잃을 수 있다.
함께 보기
참고 문헌
- Coifman, R. R., & Lafon, S. (2006). Diffusion maps. Applied and Computational Harmonic Analysis, 21(1), 5-30.
- Lafon, S., & Lee, A. B. (2006). Diffusion maps and coarse에 기반한: A unified framework for dimensionality reduction, graph partitioning, and data set parameterization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(9), 1393-1403.
- Nadler, B., Lafon, S., Coifman, R. R., & Kevrekidis, I. G. (2006). Diffusion maps, spectral clustering and reaction coordinates of dynamical systems. Applied and Computational Harmonic Analysis, 21(1), 113-127. (주에서 언급: 표준 참고 문헌이며, 이 문서는 원본 산문이다.)