대용량 데이터에서 데이터 군집화 기반의 효율적인 이상치 탐지 기법 = An Efficient Outlier Detection Algorithms based on Data Clustering over Massive Data

다국어 초록 (Multilingual Abstract)

An outlier means that a data is distant from other data or a data has a contradictory relation with other data in a data set. As these features, since the outlier is used to an unnecessary data or a significant event, the outlier detection is very important. However, since the advent of the devices that capable of communication with others and environments measurement has come an explosion of data, the existing outlier detection algorithms are not suitable to the massive data. Thus, in this paper, we propose an efficient outlier detection algorithms based on data clustering over the massive data. In proposed algorithms, we utilize the MapReduce framework which comprises a number of machines in order to construct the local clusters in parallel and merge the local clusters to the global clusters. To fully utilize every machine in MapReduce, we divide the domain of the data set into a number of grids, and then each machine collects every data in each grid and constructs the local clusters. In our experiments, we created the various size of the data sets and form the diverse experiment environments in order to evaluate proposed algorithms in various fields.

국문 초록 (Abstract)

이상치란 데이터 집합에서 다른 데이터들과 분명한 차이를 보이거나 모순 관계를 갖는 데이터를 의미한다. 이러한 특징으로 이상치는 데이터 집합에서 불필요한 데이터 또는 중요한 사건을 의미하는 정보로 사용되기 때문에, 이상치를 탐지하는 일은 매우 중요하다. 그러나 환경 정보 측정과 외부와의 통신이 가능한 기기들의 등장으로 데이터가 기하급수적으로 수집됨에 따라 기존 이상치 탐지 기법들은 이러한 대용량 데이터에 적합하지 않다. 따라서 본 논문에서는 대용량 데이터에서 데이터 군집화 기반의 효율적인 이상치 탐지 기법을 제안한다. 제안 기법에서는 복수 개의 기기들이 참여하는 맵리듀스를 이용하여 지역 군집들을 병렬로 생성하고, 지역 군집들을 병합하여 전역 군집들로 생성한다. 제안 기법에서는 데이터 영역을 격자들로 분할하여 각 격자에 속한 데이터들을 어떤 한 기기에서 모두 수집하여 지역 군집을 생성함에 따라 맵리듀스에 참여하는 모든 기기들을 완전히 사용한다. 실험에서는 제안 기법의 성능을 다방면에 걸쳐 평가하기 위해, 여러 크기의 실험 데이터 집합들을 생성하고 다양한 실험 환경을 구성하였다.

참고문헌 (Reference)

1 윤들녁, "맵리듀스를 이용한 그리드 기반 k-NN 조인 질의처리 알고리즘" 한국정보과학회 30 (30): 103-115, 2014

2 Kejia Zhang, "Unsupervised outlier detection in sensor networks using aggregation tree" 158-169, 2007

3 Konstantin Shvachko, "The hadoop distributed file system" 1-10, 2010

4 Frank E. Grubbs, "Procedures for detecting outlying observations in samples" 11 (11): 1-21, 1969

5 Qing He, "Parallel outlier detection using kd-tree based on MapReduce" 75-80, 2011

6 Jeffrey Dean, "MapReduce: simplified data pprocessing on large clusters" 51 (51): 107-113, 2008

7 Weili Wu, "Localized outlying and boundary data detection in sensor networks" 19 (19): 1145-1157, 2007

8 Anna Koufakou, "Fast paralle outlier detection for categorical datasets using MapReduce" 3298-3304, 2008

9 Sridhar Ramaswamy, "Efficient algorithms for mining outliers from large data sets" 29 (29): 427-438, 2000

10 Hans-Peter Kriegel, "Angle-Based outlier detection in high-dimensional data" 444-452, 2008

11 Alexander Hinneburg, "An efficient approach to clustering in large multimedia databases with noise" 5 (5): 387-415, 2003