개선된 Binary Discernibility Matrix 방법을 사용한 분류 알고리듬 = A Classification Algorithm using improved Binary Discernibility Matrix

다국어 초록 (Multilingual Abstract)

Data mining as the tool to extract useful information from a large amount of data is being an important issue nowadays. Particularly, classification is an important theme in data mining. In classification, rough sets theory has provided mathematical tools to deal with uncertainty and vagueness in large data set.
The problem to find minimal subsets (called "reduct") of attributes that can describe all of the concepts in the given data set is known as NP-hard problem. However, algorithms to reduce the computation intensity have been proposed. A Binary Discernibility Matrix(BDM) method is one of these algorithms.
The original BDM method doesn't consider the correlation and association between attributes and classes. The execution order of attributes is decided only by the discernibility degree. However, in cases in which attributes have bised values, the discernibility degree value becomes low. As a result, they are excluded in the reduct. These are not also included in the set of classification rules.
This paper proposes a classification algorithm using an improved Binary Discernibility Matrix(BDM) method. In this proposed method, we consider the confidence and lift to find attributes having the highest association, which are then executed first. Therefore, these attributes are included in the reduct because they are indispensable attributes. We make up for the shortcomings of the original BDM method.
Classification rules should be explicit and understandable. The experiment comparing the original BDM with the improved BDM shows that the proposed method has better performance in accuracy and it creates simple and clear classification rules.

국문 초록 (Abstract)

오늘날 많은 응용 분야에서 다양한 형태의 데이터가 빠른 속도로 기하급수적으로 증가하고 있다. 이러한 대용량의 데이터에서 유용한 정보를 찾는 것은 어렵지만 상당히 중요하여, 유용한 정보를 찾아내기 위해서는 다양한 데이터 마이닝 기법이 적용 될 수 있다.
본 논문은 데이터 마이닝의 분류(classification)기법으로 방대하고 불확실하고 부정확한 데이터에서 여러 속성을 이용한 분류화 및 근사화를 효과적으로 제공하는 러프집합이론(rough sets theory)을 사용하고 있다.
러프집합에서 속성의 최소의 부분집합을 구하는 문제, 즉 리덕트(reduct)를 구하는 문제는 NP-hard 문제에 속한다. 그러나 이것을 구하는 계산의 양을 감소시키는 휴리스틱 알고리듬 방법중에 하나인 binary discernibility matrix(BDM) 방법이라는 것이 있다. 본 논문에서는 이 방법을 기반으로 사용하여 리덕트를 구하는 방법을 제안하고자 한다. 하지만, 기존의 BDM 방법에서는 속성과 클래스간의 상관관계와 신뢰도를 고려하지 않고, 다만 discernibility degree만을 고려하기 때문에 클래스와의 연관성이 높은 속성임에도 불구하고 속성값이 한쪽으로 치우칠 경우 discernibility degree가 낮게 나오기 때문에 리덕트에 포함되지 못하고 삭제가 되어 분류규칙에서 빠지게 되는 단점이 발견되었다. 그러므로 이 단점을 개선시키기 위해 향상도(lift)와 신뢰도(confidence)를 고려하여 연관성이 가장 높은 속성을 찾아서 BDM 방법으로 실행할 때 우선적으로 실행하게 함으로써 이 속성을 필수적으로 리덕트에 포함을 시켜 분류규칙에서 빠지게 되는 단점을 보완하고자 하였다.
실험을 통하여 기존의 BDM 방법과 개선된 BDM 방법으로 각각 ID3, C4.5의 의사결정나무 생성 알고리듬을 사용하여 모델을 구축하여 분류규칙을 생성하였다. 그 결과 개선된 BDM 방법이 기존의 BDM 방법보다 대체로 분류규칙의 개수가 적게 생성되어 결과가 명쾌하고, 정확도는 더 높게 나옴으로써 더 성능이 좋음을 알 수 있었다. 또한 불일치한 데이터가 포함된 데이터에서도 적용이 가능하였고 불일치한 데이터의 삭제 전후를 비교한 실험에서 하한근사(lower approximatiom)의 근사화 방법의 사용으로 경계영역(boundary region)에 속하는 데이터들을 삭제함으로써 분류규칙의 개수가 더 적게 생성이 되었고 정확도는 더 높은 결과를 나타내었다.

목차 (Table of Contents)

• 제 1 장 서론 = 1
• 1.1 연구 배경 = 1
• 1.2 연구 목적 = 2
• 1.3 본 연구의 구성 = 3
• 제 2 장 기존 연구 고찰 = 4
• 2.1 분류(Classification) 문제 = 4
• 2.1.1 의사결정나무(Decision Tree) = 5
• 2.2 Rough Set Theory의 기본개념 = 6
• 2.2.1 정보시스템(Information System, IS) = 7
• 2.2.2 식별불가능성관계(Indiscernibility relation) = 8
• 2.2.3 근사화(Approximation) = 9
• 2.2.3 리덕트(Reduct) = 11
• 2.3 기존의 Binary Discernibility Matrix 방법 = 13
• 제 3 장 개선된 Binary Discernibility Matrix 알고리듬 = 20
• 3.1 기존의 Binary Discernibility Matrix 방법의 문제점 = 20
• 3.2 개선된 Binary Discernibility Matrix 방법 = 21
• 3.2.1 신뢰도(confidence) = 21
• 3.2.1 향상도(lift) = 22
• 3.3 개선된 Binary Discernibility Matrix 방법 진행과정 = 23
• 3.4 개선된 Binary Discernibility Matrix 방법 실행 예제 = 25
• 제 4 장 실험 및 결과 = 32
• 4.1 실험 과정 및 예제 = 32
• 4.2 실험 결과 및 분석 = 39
• 제 5 장 결론 = 43
• 참고문헌 = 45
• ABSTRACT = 48