부산대학교 도서관

As development of the techniques which can aggregate data, the size and the amount of data to be processed in data mining area has increased rapidly. Therefore, new techniques are proposed because the existed algorithms based on single machine consume too much time to process big data. Among the new techniques, algorithms based on MapReduce which is distributed parallel processing framework are proposed.In this paper, we proposed MCSK-Means (multi centroid set k-Means) algorithm using MapReduce. The naive k-Means algorithm create k initial centroids randomly. By this property, the accuracy of result clusters from k-Means depend on distribution of the initial centroids. This can be the shortage of k-Means.To alleviate this problem, the proposed algorithm, MCSK-Means, uses m initial centroid sets contain k centroids respectively to decrease the dependency of the initial centroids. The centroid sets are used in k-Means individually and makes the centroid sets to k centroids using agglomerative hierarchical clustering algorithm. The converged k centroids can make clustering result which has high accuracy in contrast with k initial centroids from the naive k-Means. Finally, we run k-Means algorithm using the converged k centroids to get a final result.In the experiments, we can demonstrate the efficiency of MCSK-Means and MCSK-Means can process big data in short time because the algorithm is implemented in MapReduce.
데이터 수집 기술이 발달함에 따라서 데이터마이닝 분야에서 처리하는 데이터의 크기와 양이 빠르게 증가하고 있는 추세이다. 기존에 제안된 단일기기 환경의 알고리즘은 이러한 빅 데이터를 처리하는데 너무 많은 시간을 소요하기 때문에 새로운 방안들이 제시되고 있다. 그 중에서 분산 병렬 처리 프레임워크인 맵리듀스를 이용한 알고리즘들이 제안되고 있다.본 논문에서는 맵리듀스를 이용한 k-Means 알고리즘 기반의 MCSK-Means (multi centroid set k-Means) 알고리즘을 제안한다. 기존의 k-Means 알고리즘은 클러스터의 개수 k만큼의 초기 중심점들을 무작 위로 생성한다. 이러한 특성 때문에 k-Means 알고리즘의 결과로 생성되는 클러스터들은 초기 중심점의 생성 위치에 따라서 크게 달라지며 클러 스터 정확도에 차이가 생기게 된다. 이는 곧 일정한 클러스터 정확도를 보장할 수 없는 단점이 된다.이를 해결하기 위해서 본 논문에서 제안하는 알고리즘은 k개의 중심점 들로 이루어진 m개의 초기 중심점 집합들을 이용하여 기존의 k개만큼만 생성되는 초기 중심점의 의존도를 줄이고자 하였다. 각 중심점 집합들에 대해서 서로 영향을 주지 않고 독립적으로 k-Means 알고리즘을 입력된 데이터 집합에 대해서 수행하고 직접 계층 클러스터링 알고리즘을 적용하여 k개의 클러스터 중심점으로 수렴할 수 있도록 하였다. 생성된 k개의 중심점들은 기존의 무작위로 생성된 k-Means 알고리즘의 초기 중심점에 비해서 비교적 정확도가 높은 결과를 얻을 수 있도록 설정되고, 마지막으로 수렴된 k개의 중심점들을 이용하여 다시 k-Means 알고리즘을 수행하여 최종 결과를 얻도록 하였다.제안 알고리즘의 효율성을 여러 환경의 실험을 통해서 입증할 수 있었고 맵리듀스 환경으로 개발하여 대용량 데이터에서도 비교적 빠른 시간에 수행이 가능함을 보였다.