검색 상세

대용량 데이터 분석을 위한 트리 기반의 범위질의 활용 군집화 기법

Tree-based Clustering Methods by Using Range Queries for Very Large Data Analysis

  • 유형철 (Ryu, Hyeong Cheol , 서강대학교 일반대학원)

초록/요약

기술의 진보는 거대한 데이터 집합을 생성하고 있다. 건강, 마케팅 및 의료 데이터 집합처럼 이러한 데이터 집합은 수치 및 범주 속성 등 다양한 형태로 이루어진 다차원 데이터 객체로 구성된다. 이와 같은 대용량 데이터 집합에 대한 군집화 분석 기법은 사용자에게 강력하고 새로운 부가가치를 창출할 통찰력을 주는 의미 있는 정보를 사용자에게 제공하는 데 유용한 기법으로 널리 활용되고 있는 중요한 연구 분야의 하나이다. 대용량 데이터 분석을 위하여 tree 구조를 활용한 요약기반 군집화 기법들이 제안되었으나, 데이터 집합의 요약을 위해 구축된 tree의 구조를 전역 군집화 기법에서 사용하지 않는 한계가 있었고, 이는 군집화 기법의 속도 저하로 이어졌다. 데이터 요약 시 구축된 tree의 구조는 전체 데이터 집합의 분포 정보를 가지고 있으므로, 이를 활용할 수 있는 군집화 기법을 연구하였다. 따라서 우리는 tree 구조를 활용할 수 있는 트리 구조 기반 질의처리를 제시하였고, 이를 활용하여 대용량 데이터 분석에 적합한 트리 구조 기반 군집화 기법을 연구하였다. 우리는 첫째로 tree 구조 기반 수치 속성 데이터 군집화를 연구하였다. 기존 군집화 기법인 BIRCH의 CF tree의 구조를 활용한 군집화 기법을 제시하여 군집화 정확도를 향상하고, 군집화 시간을 감소시켰다. 이후 혼합 속성 데이터의 군집화에 tree 구조를 사용하는 연구를 진행하여 수치 속성 및 범주 속성으로 구성된 혼합 속성 데이터에 대한 요약기반 군집화에 관한 연구를 수행한다. 마지막으로, 단일기기에서만 처리 가능한 기존 기법의 한계를 확장하여 MapReduce 기반의 수치 속성 데이터 군집화 기법을 연구하였다. Tree 구조 기반 수치 속성 데이터 군집화를 위해 BIRCH의 CF tree의 구조를 활용한 범위질의를 제안하고, 이를 활용한 군집화 기법 ERC(Effective multiple Range queries-based Clustering)를 제안한다. 또한, CF tree의 노드 분할 기법을 향상한 CF+ tree를 제시하고, CF+ tree에 기반한 ERC를 연구하였다. Tree 구조 기반 혼합 속성 데이터 군집화를 위해 BIRCH의 CF vector를 혼합 속성 데이터 군집의 요약이 가능하도록 MCF vector로 확장하였으며, 이를 활용하여 구축한 MCF tree를 제안하였다. MCF tree를 통해 구해진 요약 데이터는 기존 군집화 기법을 사용하여 최종 군집으로 나누어 진다. MapReduce 기반 수치 속성 데이터 군집화 기법은 단일기기 기반의 기존 기법을 분산처리 환경으로 확장한 기법이다. MapReduce를 활용한 분산 군집화 기법은 단일기기에서 처리할 수 없을 정도로 거대한 데이터를 다중기기를 사용하여 군집화하거나 군집화에 필요한 계산을 분산 병렬 처리함으로써 더 빠르게 군집화를 수행할 수 있게 한다. 우리의 연구는 데이터 집합을 요약하기 위해 설계된 tree의 구조를 활용한 질의처리를 제안하고 이를 군집화 기법에서 활용할 수 있음을 보여 주었다. 우리가 아는 한, 이는 트리를 활용한 질의처리와 군집화 간의 새로운 접근 방식에 관한 첫 번째 연구이다. 따라서 우리의 연구는 tree 구조와 군집화 기법 사이에 접근 방식의 폭을 넓힌 연구이며, 이를 통해 다양한 연구 및 응용 분야에 크게 기여할 것으로 기대된다.

more

초록/요약

Advance in technology has generated huge data sets. Like health, marketing, and medical data sets, these data sets are organized in multi-dimensional data objects consisting of numeric and categorical attributes. The clustering data analysis is a useful method used widely as providing users with information to create powerful new value-added insights. Clustering analysis of such a large volume of multi-dimensional data set is also an important research field. For large-scale multi-dimensional data analysis, the summary-based clustering methods using a tree structure had been proposed, but there was a limitation that the tree structure used for summarizing data set was not used for the global clustering method, which led to a slowing down of the clustering methods. Since the structure of the tree constructed when summarizing the data set has the distribution information of the entire data set, we studied the clustering method that utilizes the structure of the tree. Therefore, we proposed the query processing based on the tree structure and studied the clustering method using the tree structure. We first studied tree structure-based numerical data clustering. The clustering method using the structure of the CF tree of BIRCH, which is the existing clustering method, was proposed to improve the clustering accuracy and reduce the clustering time. After that, we used tree structure for clustering mixed-type data set and performed summary-based clustering on data set composed of numeric and categorical attributes. Finally, the MapReduce-based numerical data clustering method was studied by extending the limitation of existing methods that can be handled only in a single device. We proposed a range query using the CF tree structure of BIRCH for clustering numerical data based on tree structure, and we proposed an ERC(Effective multiple Range queries-based Clustering) using this range query. In addition, we proposed a CF+ tree that improves the node split scheme of the CF tree and studied the CF+ tree-based on ERC. For clustering mixed-type data based on the tree structure, the CF vector of BIRCH was extended to the MCF vector to enable us to summarize the mixed-type data set, and the MCF tree using the MCF vector was proposed. It was shown that the summary data obtained through the MCF tree can be applied to existing clustering methods. MapReduce-based numerical data clustering method is an extension of the existing single-device based method to the distributed processing environment. The distributed clustering method using MapReduce makes clustering faster by multiplying large amounts of data that cannot be processed on a single device, or by performing distributed parallel processing of clustering computations. Our study suggests query processing using a tree structure designed to summarize data sets and shows that it can be used in clustering methods. To the best of our knowledge, this is the first suggestion of a new approach between a tree-based query process and clustering, Thus, our study is an extension of the approach between tree structure and clustering methods, which is expected to continue greatly to various research and application areas.

more
반출 Meta View 목록