데이터 마이닝에서의 범주형데이터 군집분석을 위한 초기치 선정방법

Abstract

Data mining is the process of analyzing data from different perspectives and generates useful information. Technically, data mining finds correlations or patterns out of dozens of fields in large data. Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group, called a cluster, are more similar to each other than to those included in other groups. It is not only a main task of exploratory data mining, but also a common technique for statistical data analysis, used in many fields, including information retrieval. The k-means clustering method is usually based on vector quantization that is popular for cluster analysis in data mining. It also aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean, serving as a prototype of the cluster. As a segmentation method for cluster analysis schemes, the k-means algorithm is based on Euclidean distance, and is best suited for the analysis of numerical data set. However, in reality, there exist so many types of categorical data and more attention has been put on clustering such categorical data. After all, many researches need the cluster-based analysis mechanism especially for categorical data. A study of Huang Z. 1997 has presented the k-modes algorithm which is an expansion of the original k-means clustering algorithm. The k-modes algorithm extends the existing k-means paradigm to cluster catecorical dalta sing the similarity criteria through the comparison between attributes of the data by selecting representative data mode. However, the k-modes algorithm has a drawback in that it must decide the number of modes in advance of the iterative optimization process. If too many or less options are chosen, the accuracy of clustering will be severely deteriorated. In this paper, built on top of the well-known k-modes algorithm, how to select the number of modes and how to analyze the cluster set have been presented. The number of initial clusters decided by this way, makes it possible to efficiently estimate the final number of clusters. This step involves creating, merging and updating a great number of feasible initial modes of high similarity. Experimental results, discover that the accuracy of the proposed algorithm yields almost equal results, compared with the case beginning from the optimized initial points. After all, the suggested algorithm is more effective than existing ways in the analysis of unknown data. The rest of this thesis in organized as follows: Legacy segmentation strategies of cluster analysis techniques have been reviewed in Chapter II. Then, Chapter III describes our Chain k-modes algorithm in detail. This idea focuses on how to select the initial values for the case that they are not explicitly specified. In addition, how to analyze the clustered sets created by our scheme and the limited bound has been explained. Chapter IV has demonstrated the performance measurement results of the proposed algorithm, obtained from extensive simulation using R(3.0.1). Finally, Chapter V summarizes and concludes this thesis.

데이터에서 의미 있는 정보를 찾아내는 것은 매우 중요한 일이며, 이러한 과정을 데이터 마이닝(Data Mining)이라고 한다. "데이터 마이닝"이라는 용어는 1995년 지식발견 및 데이터 마이닝 국제학술대회를 개최한 이후 본격적으로 사용되어지고 있으며, 다양하게 정의되고 있다. [Berry and Linoff, 1997]는 "의미 있는 패턴과 규칙을 발견하기 위해서 자동화되거나 반자동화된 도구를 이용하여 대량의 데이터를 탐색하고 분석하는 과정"이라고 정의하였으며, [Hand et al, 2001]는"대량의 데이터로부터 유용한 정보를 추출하는 것"으로 정의하기도 한다. 즉, 데이터 마이닝은 미지의 데이터로부터 의미 있는 임의의 정보를 얻는 일련의 모든 방법이라고 할 수 있으며, 많은 기법들이 제시되고 있다. 최근 다양한 분야에서 빅데이터로 정의되는 정형, 비정형의 데이터에 대한 분석을 요구하고 있으며, 이러한 데이터를 수집, 분석하는 방법으로 데이터 마이닝 기법을 활용하여 실현시키고 있으며, 그 중요성은 날로 부각되고 있다. 데이터 마이닝 기법 중 군집분석기법은 다양한 분야의 수많은 데이터들로 부터 의미 있는 정보를 추출하기 위한 중요한 기법으로 인식되어 왔으며, 현재까지 군집분석기법에 대한 연구는 계속되고 있다. 군집분석기법 중에서 분할기법에 해당하는 k-means 알고리즘[Macqueen, 1967]은 유클리드 거리를 기반으로 하며, 수치형데이터의 분석에 매우 효율적이다. 하지만, 현실에서는 수치형데이터 뿐만 아니라 수많은 범주형데이터가 존재하며 중요시 되고 있다. 결국, 범주형데이터의 분석이 가능한 군집분석기법을 필요로 하였으며, [Huang Z. 1997a]의 연구에서는 기존 k-means 알고리즘을 수치형데이터에서 범주형데이터로 확장한 k-modes 알고리즘을 제안하였다. k-modes 알고리즘은 데이터의 속성간의 비교를 통한 유사도측정을 기반으로 하여 성질이 비슷한 데이터들에 대하여 대표 mode를 선정하는 방식이다. 하지만, k-modes 알고리즘은 mode의 개수를 미리 정해야 하는 문제점이 있으며, mode의 개수를 너무 많이 설정하거나 적게 설정하면 군집의 정확도가 낮아지는 문제점을 지니고 있다. 본 연구에서는 k-modes 알고리즘을 기반으로 mode의 개수를 선정하는 방법과 이를 기반으로 하는 군집분석기법을 제안하였다. 초기치 mode들은 임의로 선택된 표본으로부터 추정하였다. 이를 기반으로 유사도가 높은 다수의 초기치 mode를 생성, 병합, 갱신하는 과정을 통해 최종 군집의 개수를 추정할 수 있었다. 실험결과 제안 알고리즘의 정확도는 최적의 초기치를 기반으로 군집분석을 수행한 결과와 유사한 결과를 보였다. 이는 제안 알고리즘이 초기치의 정보를 알 수 없는 미지의 데이터에 대한 분석에서 기존의 다양한 방법들보다 매우 효과적 이라고 할 수 있다. 본 논문의 구성은 다음과 같다. II장에서는 분할기법 군집분석에 대한 설명을 하고 하였으며, III장에서는 제안 알고리즘에 대한 전반적인 과정을 설명하였다. 초기치가 주어지지 않았을 경우, 초기치를 선정하는 방법과 한계기준 및 제안 알고리즘을 이용한 군집분석 기법을 설명하였다. IV장에서는 제안 알고리즘의 실험결과이며, 실험은 R(3.0.1)을 활용하였다. V장에서는 논문에 대한 결론을 정리하였다.