다차원 척도법(multidimensional scaling)은 고차원의 데이터를 낮은 차원의 공간에 매핑(mapping)하여 데이터 간의 유사성을 표현하는 방법이다. 이는 주로 자질 선정 및 데이터를 시각화하는 데 이용된다. 그러한 다차원 척도법 중, 전통 다차원 척도법(classical multidimensional scaling)은 긴 수행 시간과 큰 공간을 필요로 하기 때문에 객체의 수가 많은 경우에 대해 적용하기 어렵다. 이는 유클리드 거리(Euclidean distance)에 기반한 $n{ imes}n$ 상이도 행렬(dissimilarity matrix)에 대해 고유쌍 문제(eigenpair problem)를 풀어야 하기 때문이다(단, n은 객체의 개수). 따라서, n이 커질수록 수행 시간이 길어지며, 메모리 사용량 증가로 인해 적용할 수 있는 데이터 크기에 한계가 있다. 본 논문에서는 이러한 문제를 완화하기 위해 GPGPU 기술 중 하나인 CUDA와 분할-정복(divide-and-conquer)기법을 활용한 효율적인 다차원 척도법을 제안하며, 다양한 실험을 통해 제안하는 기법이 객체의 개수가 많은 경우에 매우 효율적일 수 있음을 보인다.
Multidimensional scaling (MDS) is a widely used method for dimensionality reduction, of which purpose is to represent high-dimensional data in a low-dimensional space while preserving distances among objects as much as possible. MDS has mainly been applied to data visualization and feature selection. Among various MDS methods, the classical MDS is not readily applicable to data which has large numbers of objects, on normal desktop computers due to its computational complexity. More precisely, it needs to solve eigenpair problems on dissimilarity matrices based on Euclidean distance. Thus, running time and required memory of the classical MDS highly increase as n (the number of objects) grows up, restricting its use in large-scale domains. In this paper, we propose an efficient approximation algorithm for the classical MDS based on divide-and-conquer and CUDA. Through a set of experiments, we show that our approach is highly efficient and effective for analysis and visualization of data consisting of several thousands of objects.
