수치형 속성을 이산화 하기 위한 밀도 기반의 접근 방법 = (A) density-based approach to discretizing numeric attributes

국문 초록 (Abstract)

데이터로부터 의미 있는 형태의 정보를 얻기 위한 여러 가지 기법들이 개발되어왔지만, 그 중 최근 들어 가장 각광 받는 분야 중 하나는 기계학습 방법이다. 기존의 기계학습 알고리즘은 대부분 범주 형 속성에 기반해서 규칙 또는 의사 결정 모델을 생성한다. 그런데, 실 세계의 데이터는 보통 범주 형 속성 외에도 수치 값을 갖는 속성을 포함하고, 또 많은 경우에 있어 수치 형 속성으로만 구성되기도 한다. 따라서 이러한 경우, 데이터를 기계학습에 사용하기 위해서는 수치형 속성에 대한 적절한 처리 과정이 필요하다.
본 논문에서는, 수치형 속성의 도메인을 여러 개의 분절된 부분으로 나누어 기계학습 알고리즘에 사용하는 방법인 이산화 기법에 대해 연구하였다. 기계학습 알고리즘의 발전과 함께 많은 이산화 방법이 개발되었지만, 각각은 문제의 특성에 따라 일관되지 못한 성능을 보이는 것으로 나타났다. 따라서 현실적인 이산화 방법의 선택 기준은 문제의 특성에 따라 여러 가지 방법을 실험적으로 검증하는 것이다. 본 논문에서는, 기존의 이산화 방법과 다른 배경을 갖는, 밀도 기반의 새로운 이산화 방법을 제안하였고, 도메인의 특성에 따라 기존의 이산화 방법과 상호보완적으로 사용될 수 있는지를 검증하였다.
제안한 밀도 기반의 이산화 방법은 표본 데이터의 모집단 분포를 추정한 후, 새로운 평가함수인 확률밀도순도 함수에 따라 최적의 분할을 결정한다. 이 때 제안한 평가함수의 수학적인 특성을 통해 재귀적인 최적화 과정이 없이 최적의 분할을 결정하는 것이 가능하다. 제안한 방법의 성능을 검증하기 위해, 평가 함수와 탐색 전략의 관점에서 이론적 분석을 하였고, 기존의 대표적인 이산화 방법과 실험적으로 비교 분석하였다. UC Irvine Machine Learning Repository 의 실 세계 데이터를 사용한 실험 결과를 통해 제안한 방법이 노이즈의 처리와 이진 분류 문제에 있어 우수한 성능을 보임을 확인할 수 있었다.

다국어 초록 (Multilingual Abstract)

So far, various kinds of methods have been developed to gain useful information from large data. The most popularly used one is the machine learning method. The existing machine learning algorithm usually generates rules or decision making models based on the nominal attribute data. But real-world data usually contains not only nominal attributes but also numeric attributes. Therefore, in order to use these data, there should be a process that converts the attributes of the data into an appropriate attribute types.
In this paper, we will show a discretization method that partitions the domain of a numeric attribute into discrete parts and uses it as a data for the machine learning algorithm. Along with the development of machine learning algorithms many discretization methods have been introduced and developed. But however, most of them turned out that they do not show consistent performance. Therefore, the criterion for selecting a realistic discretization method is all about verifying the methods experimentally according to the type of data we are using. In this paper, we have introduced a novel discretization algorithm which differs with the ordinary methods. Also, we have verified that according to the characteristics of the problem domain, the new discretization method can be used with the existing ones.
The proposed density-based discretization method estimates the distribution of the population of the sample data and then finds the optimized partitions using the probability-density-purity function which is an evaluation function. The mathematical characteristics of the evaluation function enables optimized partitioning without using the recursive optimization process. To verify the performance of the proposed method, we gave a theoretical analysis of the method in terms of evaluation function and search strategy. Also, we have compared and analyzed, experimentally, the method with the existing ones. Using the real world data from UC Irvine Machine Learning Repository, we have shown that the proposed well in noise handling and binary classifications.

목차 (Table of Contents)

• 차례 = 1
• 1 서론 = 4
• 2 문제 설정 = 7
• 2.1 용어 및 개념 = 8
• 2.1.1 Bin = 8
• 2.1.2 Boundary Point = 9
• 2.1.3 Split-point 또는 Cut-point, Interval boundary = 11
• 2.1.4 Arity = 11
• 2.2 이산화의 정의 = 12
• 2.3 Split-point 탐색의 문제점 = 14
• 3 평가 함수와 탐색 전략 = 16
• 3.1 평가 함수 = 16
• 3.2 탐색 전략 = 24
• 3.2.1 결정적 방법 = 27
• 3.2.2 Greedy search 방법 = 28
• 3.2.3 동적 프로그래밍 = 31
• 4 확률 밀도 기반의 이산화 = 33
• 4.1 배경 = 33
• 4.2 정규 분포를 이용한 밀도 함수의 추정 = 35
• 4.2.1 정규 분포 = 36
• 4.2.2 밀도 함수의 추정 = 37
• 4.3 밀도 기반의 평가 함수 = 40
• 4.3.1 밀도 기반의 불순도 지표 = 40
• 4.3.2 평가 함수 = 43
• 4.3.3 평가 함수의 최적화 = 44
• 4.4 DENDIS: 밀도 기반의 이산화 알고리즘 = 46
• 5 기존의 이산화 알고리즘 = 50
• 5.1 Equal-Width Binning, Equal-Frequency Binning = 50
• 5.2 1R = 51
• 5.3 D2 = 52
• 5.4 MDLP = 53
• 5.5 ID3, C4.5 = 57
• 5.6 ChiMerge = 58
• 5.7 Chi2 = 59
• 5.8 그 밖의 이산화 방법 = 60
• 6 실험 = 62
• 6.1 실험 환경 설정 = 62
• 6.2 생성된 분할의 개수 비교 = 65
• 6.3 C4.5 알고리즘을 사용한 10-fold Cross-Validation = 68
• 6.3.1 10-fold Cross-Validation 정확도 = 69
• 6.3.2 통계적 검증 = 72
• 6.3.3 Tree의 크기 = 75
• 6.4 수행 시간 비교 = 77
• 7 결론 및 향후 연구 과제 = 80
• 참고 문헌 = 83