다차원 척도법(multidimensional scaling)은 고차원의 데이터를 낮은 차원의 공간에 매핑(mapping)하여 데이터 간의 유사성을 표현하는 방법이다. 이는 주로 자질 선정 및 데이터를 시각화하는 데 이용된다. 그러한 다차원 척도법 중, 전통 다차원 척도법(classical multidimensional scaling)은 긴 수행 시간과 큰 공간을 필요로 하기 때문에 객체의 수가 많은 경우에 대해 적용하기 어렵다. 이는 유클리드 거리(Euclidean distance)에 기반한 $n{\times}n$ 상이도 행렬(dissimilarity matrix)에 대해 고유쌍 문제(eigenpair problem)를 풀어야 하기 때문이다(단, n은 객체의 개수). 따라서, n이 커질수록 수행 시간이 길어지며, 메모리 사용량 증가로 인해 적용할 수 있는 데이터 크기에 한계가 있다. 본 논문에서는 이러한 문제를 완화하기 위해 GPGPU 기술 중 하나인 CUDA와 분할-정복(divide-and-conquer)기법을 활용한 효율적인 다차원 척도법을 제안하며, 다양한 실험을 통해 제안하는 기법이 객체의 개수가 많은 경우에 매우 효율적일 수 있음을 보인다.
다차원 척도법(multidimensional scaling)은 고차원의 데이터를 낮은 차원의 공간에 매핑(mapping)하여 데이터 간의 유사성을 표현하는 방법이다. 이는 주로 자질 선정 및 데이터를 시각화하는 데 이용된다. 그러한 다차원 척도법 중, 전통 다차원 척도법(classical multidimensional scaling)은 긴 수행 시간과 큰 공간을 필요로 하기 때문에 객체의 수가 많은 경우에 대해 적용하기 어렵다. 이는 유클리드 거리(Euclidean distance)에 기반한 $n{\times}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...
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.
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.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 객체의 개수가 수 천 이상인 데이터에 전통 다차원 척도법을 효율적으로 적용하기 위해 CUDA와 분할-정복 기법을 제안하였다. 다수의 데이터에 대한 실험 결과에서 정확도는 약 75%~90%를 보였으며, 평균 수행 시간은 약 100배 정도 단축되었다.
를 계산하여 어파인 매핑을 적용한다. 이것은 edMDSi와 mMDSi 간의 동일한 객체의 결과 좌표를 서로 일치시키고, 이를 기준으로 D, 의 표본 추출하지 않은 나머지 객체들을 표본 추출된 객체들과 동일한 좌표공간에 매핑하기 위해서이다.
제안 방법
4. 初 행렬과 부분 행렬 EH 각각 전통 다차원 척도법을 적용하여 dMDSie mMDS를 생성한다. (dMDSi: 부분 행렬 2의 전통 다차원 척도법 결과, mMDS- Malisn 행렬의 전통 다차원 척도법 결과)
구체적으로 설명하자면, 두 기법을 통해 나온 다차원 척도법 결과(저차원 상의 좌표 데이터에 대해 각각 가능한 객체 사이의 모든 순서쌍에 대한 유클리드 거리를 계산하여 벡터를 생성하였다. 그리고 모든 순서쌍 사이의 거리로 구성된 두 개의 벡터(CPU에서의 결과 및 CUDA 에서의 결과) 사이의 상관 계수를 계산하였다. 상관 계수의 값이 1에 가까우면, 두 결과가 객체들 사이의 거리를 선형적으로 유사하게 표현하고 있다는 의미가 된다.
또한, CUDA와 분할-정복 기반의 근사기법을 적용할 때, 전체 데이터의 분할 개수 p와 표본 추출개수 S에 따른 수행 시간 및 정확도 변화를 관측하기 위해 설정을 변경하며, 각각의 설정에 대해 100번씩 실험을 반복하였다. 위의 표 2는 이를 정리하고 있다.
본 논문에서는 각 D, 와 Mm倒 행렬에 전통 다차원 척도법을 적용하는 과정과 어파인 매핑을 적용하기 위해 A, 를 계산하는 최소 선형 자승법 부분을 CUDA로 구현하여 적용하였다. 또한 계산한 A, .
하락 정도를 기술한다. 실험 결과는 저차원의 차원 개수에 따라서 큰 차이를 보이지 않았으므로, 논문에서는 2차원에 대한 경우만을 제시한다. 또한, 표본 크기에 있어서는 표본의 크기가 커질수록 속도는 늦어지고, 정확도는 높아졌기 때문에 가장 큰 표본 크기 s = 150에 대한 결과만을 기술한다.
우선, 전체 상이도 행렬을 여러 개의 부분 행렬로 분할하며 각 부분 행렬에서 임의로 표본을 추출한다. 표본 추출된 객체들을 이용하여 새로운 상이도 행렬을 생성하며, 분할된 부분 행렬들과 함께 각각 전통 다차원 척도법을 적용하고 이를 다시 결합하여 전체 데이터의 결과를 근사한다. 그 과정은 아래의 그림 2와 같다.
대상 데이터
CUDA를 이용한 실험에 사용된 시스템은 Intel Quad Core Q6600과 4GB 메모리, 지포스 8600GT, CUDA 2.3, CULA Basic 1.0 및 윈도우 XP 프로페셔널 32-bit 환경이다. 그리고 CUDA가 아닌 CPU를 활용하는 경우에도 위와 동일한 환경에서 C#을 이용하여 실험을 하였으며, 위의 환경에 적용하기 어려운 매우 큰 크기의 데이터는 리눅스 기반의 32GB 메모리를 가지는 64~bit 서버에서 Matlab을 사용하여 실험하였다.
마이크로어레이4)1, 2는 GEO(Gene Expression Omnibus, http://www.ncbi.nlm.nih.gov/geo/)에서 제공하는 데이터를 가공한 것으로 각각 생쥐(Mus musculus) 와 효모(Saccharomyces cerevisiae)^\ 유전자 정보를 다루고 있으며, 클래스 정보가 주어지지 않은 데이터이다. MNIST는 사람들이 손으로 직접 쓴 0~9 사이의 숫자를 스캔해서 생성한 28 X 28 크기의 이미지 데이터이 다 (http://yann.
본 논문에서 제안하는 방법의 검증을 위하여 3종류의 데이터를 사용하였으며, 표 1은 이를 설명하고 있다.
데이터처리
0 및 윈도우 XP 프로페셔널 32-bit 환경이다. 그리고 CUDA가 아닌 CPU를 활용하는 경우에도 위와 동일한 환경에서 C#을 이용하여 실험을 하였으며, 위의 환경에 적용하기 어려운 매우 큰 크기의 데이터는 리눅스 기반의 32GB 메모리를 가지는 64~bit 서버에서 Matlab을 사용하여 실험하였다.
본 논문에서 제안하는 방법에 대한 성능 평가를 위해 결과의 정확도와 프로그램의 수행 시간을 비교하였다. 비교 대상으로는 C# 및 Matlab으로 구현한 일반적인 전통 다차원 척도법을 경우에 따라 각각 활용하였다.
표 2 데이터에 따른 실험 설정
정확도 평가 기준으로는 피어슨 상관 계수(Pearson's correlation coefficient)를 계산하여 성능을 측정하였다
. 구체적으로 설명하자면, 두 기법을 통해 나온 다차원 척도법 결과(저차원 상의 좌표 데이터에 대해 각각 가능한 객체 사이의 모든 순서쌍에 대한 유클리드 거리를 계산하여 벡터를 생성하였다.
이론/모형
일반적으로 GPU의 메모리 크기에는 한계가 있으며, 따라서 CUDA를 적용할 수 있는 최대 행렬 크기에도 제한이 있다.D 이의 해결을 위해 본 논문에서는 분할-정복(divide-and-conquer) 기법을 적용하였다.
나뉜다[4]. GPU 에서 수행되는 함수를 커널 (kem야)이라고 부르며, 여러 개의 스레드에 대해 동일한 커널을 적용하는 siMD(Single Instruction Multiple Data) 방식을 사용한다.
본 논문에서는 다차원 척도법 중 전통 다차원 척도법을 다루며, GPU를 활용한 병렬처리 기법 중 CUDA를이용한다. 일반적으로 GPU의 메모리 크기에는 한계가 있으며, 따라서 CUDA를 적용할 수 있는 최대 행렬 크기에도 제한이 있다.
본 논문에서는 이러한 문제를 처리하기 위해 아래와 같이 분할-정복 기법을 이용한다.
왔다[3, 9, 10]. 본 논문에서는 이러한 방법들 중기 본적이지만 정확도가 일반적인 경우에 평균적으로는 가장 높다고 알려진 임의 표본 추출 기반의 분할 정복기법을 GPU의 메모리 한계를 극복하기 위해 적용하고 있다 [11].
비교하였다. 비교 대상으로는 C# 및 Matlab으로 구현한 일반적인 전통 다차원 척도법을 경우에 따라 각각 활용하였다.
성능/효과
분할-정복 기법을 제안하였다. 다수의 데이터에 대한 실험 결과에서 정확도는 약 75%~90%를 보였으며, 평균 수행 시간은 약 100배 정도 단축되었다. 이는 기존의 PC에서 수 시간 걸리던 작업을 동일한 PC에서 그래픽 카드를 이용하여 수 분 이내에 할 수 있음을 의미한다.
후속연구
이는 기존의 PC에서 수 시간 걸리던 작업을 동일한 PC에서 그래픽 카드를 이용하여 수 분 이내에 할 수 있음을 의미한다. 물론, 정확도가 많이 훼손될 수도 있으나, 많은 경우 그 정도가 그리 크지 않을 수 있으며, 객체의 개수가 수 천 이상인 다양한 데이터를 신속하게 저차원공간 상에서 시각화하려 할 때에 본 논문에서 제안하는 기법을 활용할 수 있다. 한편, 정확도가 많이 저하되거나 임의 표본 추출 결과에 따라 큰 편차를 보이는 경우는 데이터의 분포 모양과 관련이 있다고 추정되며, 이에 대한 보다 상세한 분석 및 해결은 향후 연구 과제이다.
물론, 정확도가 많이 훼손될 수도 있으나, 많은 경우 그 정도가 그리 크지 않을 수 있으며, 객체의 개수가 수 천 이상인 다양한 데이터를 신속하게 저차원공간 상에서 시각화하려 할 때에 본 논문에서 제안하는 기법을 활용할 수 있다. 한편, 정확도가 많이 저하되거나 임의 표본 추출 결과에 따라 큰 편차를 보이는 경우는 데이터의 분포 모양과 관련이 있다고 추정되며, 이에 대한 보다 상세한 분석 및 해결은 향후 연구 과제이다.
참고문헌 (11)
Borg, I. and Groenen, P. J. F., Modern Multidimensional Scaling: Theory and Applications, Second Edition, Springer Science+Business Media, New York, NY, USA, 2005.
Shashua, A. and Wolf, L., Kernel feature selection with side data using a spectral approach, Proc. of ECCV 2004, pp.39-53, 2004.
Yang, T., Liu, J., McMillan, L., and Wang, W., A fast approximation to multidimensional scaling, Proc. of the ECCV 2006 Workshop on Computation Intensive Methods for Computer Vision, 2006.
Kirk, D. and Hwu, W.-M., CUDA Textbook, Draft Version, 2009.
CUDA CUBLAS Library Ver.2.3, NVIDIA Corporation, Santa Clara, CA, USA, 2009.
CULA tools, EM Photonics, http://www.culatools.com.
de Silva, V. and Tenenbaum, J.B., Sparse multidimensional scaling using landmark points, Technical Report, Stanford University, 2004.
Faloutsos, C. and Lin, K.-I., FastMap: a fast algorithm for indexing, data-mining and visualization, Proc. of ACM SIGMOD 1995, pp.163-174, 1995.
Pechenizkiy, M., Puuronen, S., and Tsymbal, A., The impact of sample reduction on PCA-based feature extraction for supervised learning, Proc. of ACM SAC 2006 Data Mining Track, pp.553-558, 2006.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.