고차원 클러스터링을 위한 분산 알고리즘

Abstract

클러스터링이란 각 개체간의 유사도를 기반으로 하여 주어진 전체 자료 집합을 서로 유사한 개체들로 구성된 군집들로 분할하는 문제이다. 클러스터링 알고리즘은 자료의 전체적인 분포 상태를 파악하는 방법으로서 뿐만 아니라 추천이나 분류 등 다른 알고리즘 수행을 위한 전처리 단계로서도 활용도가 높다. 하지만 전통적인 클러스터링 알고리즘들이 최근 범람하는 고차원 자료를 다루는 데 있어 한계를 노출하게 되면서, 고차원 자료를 클러스터링하는 알고리즘들이 관심을 모으게 되었다. 부분 공간 클러스터링 알고리즘은 고차원 클러스터링 문제를 해결하기 위한 방안 중 하나로 제안된 것으로, 지금까지 많은 연구가 이루어져 왔다. 하지만 지금까지 발표된 부분 공간 클러스터링 알고리즘들은 대부분이 단일 하드웨어에서 동작하는 것으로, 규모 확장성이 제한된다는 문제점을 가진다. 본 논문에서는 부분 공간 클러스터링 문제가 가지는 수학적 속성들을 검토하고, 이 문제를 분산 환경에서 해결하는 방안을 제시하였다. 실제 자료 집합에 대한 실험 결과는 MapReduce와 Bulk Synchronous Parallel 을 혼합한 접근 방식이 부분 공간 클러스터링 문제의 해결에 효과적임을 보여 주며, 제시된 방법이 차원 수와 자료 크기의 측면 모두에서 충분한 규모 확장성을 갖는다는 사실을 확인시켜 준다.