다차원 빅데이터를 위한 맵리듀스 기반의 병렬 K-Means 군집화 기법 (Parallel K-Means Clustering based on MapReduce for Multi-Dimensional BigData)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 데이타베이스연구 / 35권 / 1호 / 20 ~ 34페이지
· 저자명 : 최성준, 김홍연, 민준기

초록

군집화는 주어진 데이터 집합에 속한 점들을 여러 개의 군집들로 분류하는 알고리즘으로써 각 군집에 속한 점들은 유사한 특성을 가지도록 하고 유사하지 않은 점들은 서로 다른 군집에 속하도록 하는 것을 목적으로 한다. 다양한 군집화 알고리즘들 중에서 가장 널리 쓰이는 기법은 중심 기반 군집화 기법인 K-Means 알고리즘이다. 본 연구에서는 대용량 데이터 처리를 위한 맵리듀스 프레임워크를 활용한 효과적인 병렬 K-Means 알고리즘인 SMRKMeans을 제안한다. SMRKMeans 알고리즘에서는 각 중심점에 대하여 가장 가까운 중심점까지의 거리를 유지하며, 이를 이용하여 각 데이터에 대한 모든 중심점들까지의 거리를 계산할 필요가 있는지 여부를 효율적으로 판단하도록 하였다. 또한, 기존 병렬 알고리즘과는 달리 SMRKMeans 를 맵 단계로만 구성되도록 설계하여 셔플 및 리듀스 단계 수행을 위한 부담을 제거하였다. 더욱이, 데이터 조각 (data sharding) 기법을 적용하여 맵 단계에서 데이터 집합을 네트워크를 통하여 여러 머신에 배분하는 부담을 줄였다.

영어초록

Clustering is the algorithm for partitioning the points in a given data set into several groups. The goal of clustering is that the points in a group are similar while the dissimilar points are in the different groups. Among the diverse clustering algorithms, K-Means as a center based clustering algorithm is one of the most widely used algorithms. In this paper, we propose an efficient parallel K-Mean algorithm, called SMRKMeans, which utilizes the MapReduce framework for processing large volume data sets. In SMRKMeans, for each center, we maintain the distance to the closest center of it and we check whether each point is needed to compute the distances to all center points by using the maintained minimal distances. Additionally, in contrast to the existing parallel algorithm, since we design SMRKMeans composed of map phases only, we eliminate the overhead for conducting shuffle and reduce phases. Furthermore, by the adapting data sharding technique, we alleviate the network overhead for distributing data set to several machines at the map phase.

참고자료

· 없음