유전자 알고리즘을 사용한 분류 규칙 유도 방법
Discovering Classification Rules using Genetic Algorithm
- 주제(키워드) 분류기 , 규칙 유도 , 유전자 알고리즘
- 발행기관 서강대학교 컴퓨터공학과
- 지도교수 양지훈
- 발행년도 2009
- 학위수여년월 2009. 2
- 학위명 석사
- 실제URI http://www.dcollection.net/handler/sogang/000000045119
- 본문언어 한국어
초록/요약
분류(Classification)는 데이터 마이닝(Data Mining)의 한 분야로써, 데이터베이스에서 여러 속성을 가진 데이터의 여러 속성 중 한 속성에 대해 그 값이나 범주(Class)를 다른 속성들을 사용해서 예측하는 방법이다. 분류기를 만들기 위해 여러 효율적인 방법이 개발되었고, 분류 규칙 유도 방법 또한 이 중 하나이다. 이 방법의 목표는 사람이 쉽게 이해 가능한 규칙들의 집합을 발견해 내는 것이다. 규칙 유도(Rule Induction)를 통해 데이터를 규칙 기반으로 표현 가능하게 됨으로써 시스템 관리자들은 이를 시스템의 결정을 지원하기 위한 지식 기초로 활용할 수 있고, 시스템의 행동 양식에 대한 이해가 쉬운 명세 체계를 구축할 수 있다. 규칙 유도를 위해서는 데이터에서 나타나는 모든 가능한 패턴에 대해 검색하고 가장 좋은 성능을 보이는 규칙을 찾아내야 하기 때문에 이를 위해 다양한 검색 방법이 활용될 수 있다. 생물학적인 진화 과정에 착안하여 만들어진 유전자 알고리즘(Genetic Algorithm)을 사용하면 좀 더 효율적인 규칙 탐사를 수행할 수 있다. 본 연구에서는 여러 다른 규칙 유도 방법의 소개와 함께, 다양한 형태의 데이터를 처리할 수 있는 효율적인 규칙 유도 방법을 제안한다. 이를 위해 먼저 유전자 알고리즘을 문제에 적용하는 방법에 대해서 설명하고, 구현된 분류기의 성능을 개선하는 여러 방법에 대해서 논의한다. 그리고 제안한 방법을 사용하여 다양한 형태의 여러 데이터에 대해 다른 분류기와 그 정확도를 비교한다. 마지막으로 결과를 통해 제안한 방법이 타 방법과 비슷하거나 우수한 성능을 보임을 확인하였다.
more초록/요약
Classification, one of the data mining tasks which has an object is to predict the value(the class) of a user-specified goal attribute based on the values of other attributes called the predicting attributes. There are many efficient methods, and rule induction is one of the techniques. The goal of this method is to discover a set of rules easily understandable for human. Rule induction is able to convert the data into a rule-based representation that can be used either as a knowledge base for decision support or as a description of the system behavior. Basically rule induction features the capability to search for all possible interesting patterns from data sets to discover the rules with a good performance, and thus a variety of search techniques are applicable for this purpose. It is efficient to use the genetic algorithm for the such task, which have been inspired by the process of biological evolution. In this study we propose a rule induction method which is able to process the various forms of data and introduce the issues related to this work. First, we explain the ways of applying the genetic algorithm to find rules. And we discuss several features for elaborating the result. And then we compare the performance of our classifier with others. We found that the proposed classifier is comparable or superior to other methods in diverse data sets.
more목차
제1장 서론 = 1
1.1 연구 배경 = 1
1.2 논문의 구성 = 3
제2장 관련연구 = 4
2.1 규칙 기반 분류 = 4
2.2 규칙 기반 분류기의 종류 = 5
2.2.1 연관 규칙 기반 방법 = 5
2.2.2 의사 결정 나무 기반 방법 = 6
2.2.3 순차적 분류 방법 = 7
2.3 유전자 알고리즘을 사용한 규칙 기반 분류기 = 10
2.3.1 개체 표현 방법 = 12
2.3.2 유전자 알고리즘을 사용한 순차적 분류 = 14
제3장 유전자 알고리즘을 사용한 분류 규칙 유도 방법 = 18
3.1 개체 부호화 = 19
3.2 유전 연산 정의 = 21
3.2.1 교차 연산자 = 21
3.2.2 돌연변이 연산자 = 23
3.2.3 선택 연산자 = 25
3.2.4 대치 연산 = 26
3.3 적합도 함수 = 27
3.3.1 정확도 측정 = 28
3.3.2 정확도 및 적용 범위 측정 = 29
3.3.3 규칙 집합의 단순성을 고려한 측정 = 30
3.3.4 선호도 고려 = 32
3.3.5 적합도 함수 = 32
3.4 순차적 분류에 적용 = 33
3.5 분류기 성능 향상을 위한 추가적 방법 = 38
3.5.1 정보 획득을 사용한 가지치기 = 39
3.5.2 조건의 연속형 값 조정 및 가지치기 = 40
3.5.3 성능 향상을 위한 기타 시도 = 42
제4장 실험 및 결과 = 44
4.1 실험 데이터 = 44
4.2 실험 방법 = 46
4.3 결과 및 분석 = 48
4.3.1 제안한 방법과 기존 분류기와의 분류 정확도 비교 = 48
4.3.2 제안한 방법과 기존 규칙 기반 분류기와의 규칙 수 비교 = 51
제5장 결론 및 향후 과제 = 53
5.1 결론 = 53
5.2 향후 과제 = 54
참고문헌 = 57
그림목차
[그림 1] 데이터베이스 내 지식 탐사 과정 = 1
[그림 2] 순차적 분류 방법을 사용한 규칙 학습의 예 = 8
[그림 3] 순차적 분류 규칙 유도 방법의 의사 코드 = 9
[그림 4] 유전자 알고리즘의 순서도 = 11
[그림 5] 특수화된 분류 규칙 집합, 일반화된 분류 규칙 집합의 예 = 15
[그림 6] 규칙 개체 표현 = 19
[그림 7] 이점 교차 연산 = 23
[그림 8] 돌연변이 연산의 예 = 24
[그림 9] 혼동 행렬 = 28
[그림 10] 유전자 알고리즘을 사용한 순차적 분류 알고리즘의 의사 코드 = 34
[그림 11] 유전자 알고리즘을 사용한 순차적 분류 알고리즘에 사용되는 함수들 = 35
[그림 12] 같은 분류 성능을 갖는 다른 결정 경계 = 40
[그림 13] 결정 경계의 변경 = 41
표목차
[표 1] 실험 데이터 설명 = 45
[표 2] 유전자 알고리즘의 매개 변수 설정 = 48
[표 3] 분류 정확도 비교 = 49
[표 4] 규칙의 수 비교 (정확도와 같이 표시) = 52
