유사쌍 분할과 엔트로피를 이용한 인스턴스 기반 학습을 위한 데이터 감소

Abstract

많은 응용 분야에서 데이터베이스의 크기가 빠른 속도로 증가하고 있다. 이러한 대용량의 데이터베이스에서 사용자에게 유용한 정보를 얻기 위하여 다양한 데이터 마이닝 기법이 적용될 수 있다. 하지만 이런 방대한 데이터를 직접 이용하는 것은 많은 분석 시간이 소요되며, 분석의 질을 떨어뜨릴 수 있다. 이러한 문제 해결을 위한 방법으로 전처리(preprocessing) 과정이 필요하며, 본 논문에서는 전처리 과정의 하나인 데이터 감소 방법들을 연구하였다. 본 연구에서는 이질성(heterogeneous)을 가진 파티션 간의 새로운 유사성 측정 방법을 제안하였다. 그리고 유사쌍 분할 방법을 이용한 데이터 감소 알고리듬과 엔트로피 기반 분할을 이용한 데이터 감소 알고리듬을 제안하였다. 제안하는 유사성 측정 방법은 파티션 간의 가장 거리가 가까운 인스턴스들을 하나의 쌍으로 구성하고, 그 유사쌍들의 거리 합을 파티션 간의 거리로 이용하는 방법이다. 유사쌍 분할을 이용한 데이터 감소 알고리듬은 거리가 가장 가까운 인스턴스들을 두 개의 파티션으로 이진 분할함으로써, 파티션 간의 거리를 최소로 하는 방법이다. 이 방법을 통해, 두 파티션은 유사한 특징을 가지게 되고 그 중 하나의 파티션이 대표 파티션으로 선택된다. 그리고 이러한 반복적인 이진 분할을 통하여 데이터 감소가 이루어진다. 엔트로피 기반 분할을 이용한 데이터 감소 알고리듬은 엔트로피의 특징을 이용하여 동질의 데이터들이 같은 파티션에 모이도록 구성하는 방법이다. 그리고 데이터 파티션에서 사용하지 않은 속성들은 불필요한 속성으로 간주하고 제거한다. 그리고 각 파티션의 중심 인스턴스들과 인접 인스턴스들로 이루어진 감소된 데이터 집합을 구하게 된다. 실험을 통해, 유사쌍 분할을 이용한 데이터 감소 알고리듬과 엔트로피 기반 분할을 이용한 데이터 감소 알고리듬 모두 평균 분류 정확도와 데이터 감소 시간이 기존 방법들보다 우수함을 알 수 있었다. 그리고 두 방법 모두 높은 데이터 감소 비율을 나타내었다. 특히, 유사쌍 분할을 이용한 방법이 엔트로피 기반 분할을 이용한 방법보다 높은 분류 정확도를 나타냈으며, 엔트로피 기반 분할을 이용한 방법이 유사쌍 분할을 이용한 방법보다 높은 데이터 감소 비율을 나타내었다.; The size of databases are explosively growing in many different applications. Various data mining techniques have been applied to extract meaning information from such large databases. Previous data mining techniques, however, use whole databases directly, hence may fail to provide high analytical quality. One way to address this problem is to preprocess the data, and data reduction is one approach. We propose a new similarity measure to compute the similarity between heterogeneous partitions. And two data reduction algorithms are proposed, one that uses a new similarity measure for partitioning and one that uses entropy. The proposed similarity measure finds the nearest instances between partitions, and composes instance pairs. Data reduction algorithm using similar-pair partitioning uses instance pairs to measure the distance between partitions. Then, these instance pairs are split into two partitions that have similar characteristics and the smallest possible distance between them. One of these partitions is selected as a representative set, and then the data are reduced via recursive binary artitioning. Data reduction algorithm using entropy-based partitioning groups homogeneous data into the same partition. Attributes that are not used at the partitioning stage are regarded as irrelevant, and are removed. In each partition, the representative instances comprise the center instance and its nearest neighboring instances. The reduced data set consists of the representative instances in each partition. Experimental results show that similar-pair partitioning and entropy-based partitioning both achieve high rates of data reduction, with greater classification accuracy and shorter calculation times than current methods. Data reduction using similar-pair partitioning results in greater classification accuracy than using entropy, while data reduction using entropy results in a better reduction rate than using similar-pair partitioning.