[ㅍ] 유전자 알고리즘을 이용한 최적화

목 차

I. 서론
II. 관련 연구
III. 귀납 법칙의 생성
IV. 규칙 생성의 방법
1. H 값을 이용한 가지치기 방법
2. 목표 속성값의 결정
V. 규칙 집합의 선택
VI. 실험 결과
VII. 결론
--------------------------------------------------------------------------------
발행자명 동국대학교 산업기술연구원 
학술지명 산업기술논문집 
ISSN 1225-6188 
권 11 
호 2 
출판일 2000. . .  

유전자 알고리즘을 이용한 최적화 귀납법칙 집합의 생성방법

Generating Optimized Inductive Rule Sets Using Genetic Algorithms

이창환
신광현
4-537-0002-05

Abstract
귀납 법칙 생성 시스템은 데이터에서부터 법칙을 자동으로 발견하는 시스템으로서 현재 많은 연구가 진행되고 있다. 본 논문은 이러한 귀납법칙 시스템에 의하여 생성되는 귀납법칙 집합들의 최적화된 부분 집합을 탐색하기 위하여 유전자 알고리즘을 사용함으로써 성능을 향상시키는 방법에 대한 연구이다. 귀납 법칙 생성 시스템에 의하여 생성되는 규칙들 중에서 최적의 규칙 집합을 구하는 것은 귀납 법칙분야에서 고려해야 할 큰 문제중의 하나이다. 제안된 시스템의 성능을 평가하기 위하여 다수의 기계학습 데이터를 사용하여 기존의 다른 방법들과 비교하였으며, 제안된 시스템은 항상 좋은 정확도를 제공하였다.

The rule induction system generates a set of inductive rules, and the task of selecting an optimal rule subset is one of the important problem in the area of rule induction. This paper proposes a new method for improving the performance of the rule induction system using the paradigm of genetic algorithm. This paper shows that genetic algorithm can be effectively applied to optimal rule selection problem. The proposed system was evaluated using a set of different machine learning data sets and, showed better performance in all cases than other traditional methods.

--------------------------------------------------------------------------------

I. 서론
인간의 직관으로부터 직접적으로 얻어진 규칙은 정보 전달의 어려움 등으로 인하여 불합리하고 많은 비용이 든다. 그렇기 때문에 주어진 데이터베이스로부터 전문가 수준의 자동적으로 추론되어진 규칙을 사용할 수 있다면 대단히 유용할 것이다. 이런 이유로 인하여 최근에 여러 종류의 귀납법칙 생성 시스템들이 개발되어 사용되고 있다. 현재에 통용되는 규칙 귀납 시스템은 PRISM(Cendrowska, 1987) [1], CN2(Clark and Niblett, 1989) [2] 와 규칙 귀납 시스템의 AQ 시리즈 [3] 등이 있다. 그들의 규칙 귀납의 방법에는 차이가 있지만 기본적인 사고는 단일 최고 규칙(single-best-rule)의 방법을 사용하는 것인데 이 방법은 한번에 하나의 규칙을 만들어 확장하며, 다음에 나올 하나의 조건에다 규칙이 부정 데이터와 일치하기 이전까지의 조건을 더해 나간다.

본 논문은 현재 개발하여 사용하고있는 특정 귀납 법칙 생성 시스템에서 생성되는 규칙들에 대하여 유전자 알고리즘을 사용하여 최적의 규칙 집합을 결정하는 방법을 제시하고 궁극적으로 귀납법칙 시스템의 성능을 향상시킬 수 있는 방법에 대하여 소개하고자 한다. 본 논문이 참조하는 귀납법칙 생성 시스템은 본 저자가 정보 이론을 사용하여 개발한 귀납법칙 시스템으로서 ([4] 참조) 이는 주어진 데이터를 읽어서 n 개의 귀납법칙을 생성하며 각 법칙들은 그 중요도에 따라 미리 정렬이 되어 있다. 본 논문의 후반부 내용은 이와 같이 생성된 귀납법칙들에 대하여 데이터를 가장 잘 예측할 수 있는 규칙 집합을 구하는 것이다.

주어진 n 개의 귀납법칙에서 최적의 규칙 집합을 구하는 것은 NP 문제이며 귀납 법칙분야에서 고려해야 할 큰 문제중의 하나이다. 본 논문에서는 이 문제의 해결을 위하여 유전자 알고리즘을 사용하고자 한다. 유전자 알고리즘은 비교적 간단하면서도 최적치에 근사한 값을 제공할 수 있으며, 기계학습의 여러 분야에서 활용되고 있다. 따라서 본 논문에서는 유전자 알고리즘을 귀납법칙의 최적 집합 탐색의 문제의 분야에 적용하여 귀납법칙 시스템 전체의 성능을 향상시키고자 한다.

II. 관련 연구
유전자 알고리즘을 귀납법칙에 이용한 예로써 GABIL [5] 을 들 수 있다. 이는 명제 규칙들의 집합을 2 진수로 표현하고 이렇게 표현된 집합을 유전자 알고리즘으로 이용하여 규칙을 생성하는 시스템으로, 그 결과는 C4.5 [6] 나 AQ 시스템과 비슷한 성능을 보여주었다. 이렇게 유전자 알고리즘 자체를 학습 시스템이 응용하기도 하지만 다른 시스템과 결합하는 다중화 전략 시스템의 일부로 사용하기도 한다.

다중 전략의 방법을 사용한 예로서는 Vafaie 와 De Jong [7] 의 연구들이 있다. 이들은 시스템의 수행 시간을 단축시키고 주위 환경의 변화 또는 잡음 등으로 인한 외부적인 장애를 극복하고자 다중 전략 방법을 사용하였다. 그들은 유전자 알고리즘을 사용하여 주어진 데이터 집합을 조사하여 탐색 공간을 줄이고 줄여진 데이터의 집합들을 AQ 알고리즘으로 규칙들을 생성한 후 인식률을 계산하게끔 하는 방식을 취하였다. 우리는 여기서 제안하는 방법은 위에서 언급한 방법과는 차이가 있다. 위의 방법이 시스템의 수행 시간의 단축을 위해 유전자 알고리즘을 사용한 것과는 달리 우리가 제안하는 방법은 보다 합리적인 규칙 집합의 생성을 위해 유전자 알고리즘을 사용한다.

III. 귀납 법칙의 생성
본 절에서는 제안된 시스템이 사용하고 있는 귀납법칙 생성 방법에 대한 내용을 간략히 설명하고자한다. 이 절의 내용은 이미 독립적으로 발표되어 있으므로 좀더 자세한 내용은 [4] 를 참조하기 바란다. 제안한 귀납법칙 시스템에서 규칙 생성의 기본적인 가정은 각 규칙의 왼쪽 면에 할당된 값이 오른쪽 면의 확률 분포에 영향을 준다는 가정에서 출발한다. 직관적으로 말하자면, 특정 속성(attribute)의 값이 정해질 때 목표 속성(target attribute)의 확률 분포를 현저히 변화시킨다면 이는 특정 속성의 값을 결정하는 중요한 역할을 의미한다. 따라서 시스템은 우선 속성의 변수값(예를 들어서 B 속성이 b 의 값을 가짐)을 우선 선택하고, B=b이라는 사건이 목표 속성 A 의 분포값에 어떤 영향을 끼치는 가를 점검한다. 만약 그것이 목표 속성의 확률 분포에 상당한 영향을 끼친다면 시스템은 다음과 같은 규칙이 있음을 가정한다.

B = b → A = a with H

각 규칙은 각 규칙의 중요도를 표현하는 H 값을 포함하고 있다. 규칙의 왼쪽은 논리곱(conjunction)의 형태로 되어 있으며 논리합과 부정 논리의 형태는 고려하지 않는다.

따라서 목표 속성의 확률분포의 변화 정도를 측정하는 엔트로피 함수를 정의하기 위하여 본 논문의 귀납 법칙 시스템은 Hellinger 계산 [8] 이라 불리는 엔트로피 함수를 사용하였다. Hellinger 계산은 다음과 같이 정의된다.

 

이 식은 속성 A에 대해서 B=b 의 값 이전의 확률 분포와 B=b 값 이후의 확률분포에 대하여 얼마나 차이가 있는가에 대한 계산식이다.

규칙 생성 환경에서 목표 속성의 특별한 하나의 값은 규칙의 오른 편에서 나타나고 그래서 다른 값들의 확률들은 1-P(a)에 포함되어진다. 다시 말해 규칙의 정확도를 측정하는 데에 있어서 중요한 점은 개체가 규칙의 오른 편의 목표값(A=a)에 속하는가를 검사하는 것이다. 예를 들어서 목표 속성 A 가 k 개 (a1, a2, ... , ak) 의 값을 가지고 있고 규칙은 오른 편에서 A=a1 이라고 가정하자. 속성 A의 확률 분포가 (P(A=a1), P(A≠a1)) 와 같이 2진의 확률 분포로 변환된다. 그래서 공식 (2) 는 다음과 같이 변환될 수 있다.

 

이 식에서 P(a|b)는 B=b라는 조건 하에서 A=a의 조건 확률을 의미한다.

규칙 귀납에서 우리가 고려해야할 또 다른 문제는 규칙이 얼마나 일반적인(general) 규칙인가 하는 것을 결정하는 것이다. 규칙을 만족하는 데이터의 수가 많을수록 그 규칙은 더욱 일반성이 있다고 할 수 있다. 예를 들면 가상적인 병원 데이터 베이스에서 HIV 양성 환자의 2가지 경우가 있고, 2가지 환자들의 혈액형은 A형이 나왔다고 가정해보자. 이 경우에 다음과 같은 규칙이 생성된 규칙 귀납 시스템은 좋은 법칙이 아니다.

If HIV-test = positive,

then Blood-type = A

이런 규칙의 형태는 특수한 조건을 과만족(overfitting)시키고 그들의 일반성(generality)을 떨어뜨린다. 그래서 규칙의 중요도의 부분으로써 규칙의 보편성의 정도를 계산하여야 한다. 규칙의 일반성을 나타내기 위하여 귀납법칙 시스템에서는 다음 수식을 사용하였다.

 

결과적으로 H 계산은 규칙의 중요도를 주어진 규칙의 정확도와 일반성의 복합적인 계산으로 표현한다. 주어진 규칙에서 중요도의 마지막 형태는 다음과 같이 규칙의 일반성과 정확도 사이에서 생성된 식으로 정의된다.

정의 1 : 다음과 같은 규칙

 

의 H 값은 다음과 같이 정의된다

 

위의 식에서 Bi는 i 번째 속성을 나타내며 bij는 속성 Bi의 j 번째 값이다.

IV. 규칙 생성의 방법
귀납법칙 시스템은 이산 속성(discrete attribute)의 형태로 된 데이터들을 읽어서 H 값의 순서대로 정렬된 k 개의 규칙을 생성한다. 시스템에서 규칙을 생성하는 방법을 간략히 설명하면 아래와 같다. 먼저, 규칙의 왼편이 한 개의 속성조건만을 갖는 단일조건(single-condition)규칙들을 생성한다. 알고리즘은 이들 단일 조건 규칙들에서 출발하여 가능한 왼쪽 면을 통한 깊이우선(depth-first) 탐색을 수행한다. 단일 조건들 중에서 H 계산값이 가장 높은 k 개의 규칙들이 규칙 리스트의 형태로 저장된다. 이들의 H 값중 가장 작은 H 값은 H* 로 정의된다. 이 규칙 리스트의 각 원소에 대하여 알고리즘은 더욱 특수화된(specialized) 규칙들을 생성하려고 한다. 즉 알고리즘은 규칙 리스트에서 한 원소를 뽑고 추가적인 속성 조건을 왼편에 추가하여서 특수화시킨다. 알고리즘은 다음 절에서 설명하는 정리들 중에서 하나를 만족할 때까지 특수화를 계속한다.

1. H 값을 이용한 가지치기 방법
귀납법칙 시스템이 다루는 데이터는 속성들의 숫자가 증가함에 따라 계산해야할 규칙들의 총 숫자는 폭발적으로 증가한다. 예를 들어서 데이터가 r 개의 속성을 가지고 각 속성들은 υi(i=1, ..., r) 의 값들을 가진다고 가정하자. 그러면 최악의 경우 총 규칙의 개수는 다음과 같이 주어진다.

 

우리는 Hellinger 계산의 특성들을 분석한(pruning) 기술을 고안하고자 한다. 우선 다음과 같은 규칙을 가정하자.

B = b → A = a (6)

또한 C=c 라는 조건을 더해서 다음과 같이 특수화된 규칙을 가정하자.

B = b∧C = c → A = a (7)

공식 (6)과 (7)에서의 규칙들은 각각 Rg 와 Rs 로 표시한다. 규칙 Rg 와 Rs 의 H 값을 각각 Hg 와 Hs 라고 가정하면 이들은 다음과 같이 정의된다.

 

이 경우, 속성 C 의 값에 관계없이 우리는 다음과 같은 결과를 얻을 수 있다.

정리 1 : 목표 속성의 클래스 개수를 m 이라고할 때 Hs 값은 다음의 경계값을 초과할 수 없다.

 

-- (10)

정리 2 : 만약 조건 확률 Rs가 1이라면 Rs의 H 값은 Rg의 H 값을 초과할 수 없다.

IF P(a|b) = 1, Hs ≤ Hg

위 정리의 증명들은 지면 제약상 생략하기로 한다. 이 법칙들은 속성 C 에 관한 추가 정보없이 Hs 값의 경계를 예상하게 할 수 있게 하였다. 따라서 만약 Hs 값의 경계값이 현재의 최소 H 값(H*) 필요가 없으며 현재의 규칙에 대하여서는 더 이상 )보다 작다면 시스템은 더 이상 진행할 특수한 규칙들을 생성할 필요도 없다.

또한 추가로 사용되는 가지치기 방법은 현재 진행중인 규칙의 조건 확률이 1이라면, 정리 2 에 의하여 시스템은 더 이상 특수한 규칙을 생성할 필요가 없음을 알 수 있다.

2. 목표 속성값의 결정
생성된 규칙들은 귀납적인 성질에 기인하여 서로 모순된 몇 가지 규칙들이 존재할 확률이 있다. 새로운 개체의 목표 속성값을 결정하기 위하여 각 귀납 규칙들의 H 값은 규칙들의 가중치(weight)로써 간주될 수 있다. 새로운 개체가 주어지면 시스템은 생성된 전체 규칙들중에서 새로운 개체가 만족하는 개체를 선택하고 선택된 규칙들의 H 값과 목표속성의 값을 저장한다. 최종적으로 가장 큰 H 값을 모은 목표속성의 값의 최종 분류(classification)의 답으로써 선택된다.

V. 규칙 집합의 선택
지금까지 규칙 귀납 시스템이 주어진 데이터에 대하여 이들을 잘 설명할 수 있는 귀납 규칙들을 순서대로 생성하는 방법에 대하여 설명하였다. 하지만 규칙 귀납 시스템에 있어서 몇 개의 규칙들을 생성하는 것이 최선인가에 대한 답을 얻는 것은 대단히 어려운 문제이다. 많은 규칙들의 생성이 본래의 데이터를 바르게 설명해 준다고 할 수도 없으며 오히려 데이터에 대한 과적합(overfitting)을 초래할 수도 있기 때문이다. 다시 말해 규칙의 생성 순위가 낮은 규칙들로 인해 원래의 데이터가 잘못 설명되어질 수 있다는 것이다. 더우기 생성된 각 규칙들간에 발생할 수 있는 모순(contradiction) 현상은 최적의 규칙 집합을 얻기 위해 고려해야 할 또 다른 문제이다. 일반적인 데이터의 경우 많은 잡음과 누락치(missing value) 등을 포함하고 있으며 이런 불분명한 데이터의 집합은 시스템으로 하여금 서로 상이한 규칙들을 만들어 내게 하는 요인이 될 수 있다. 위와 같은 이유로 많은 규칙들 가운데 최적의 규칙 집합을 구하는 것은 중요한 문제이며, 이를 해결하기 위한 간단한 방법들로 맹목적 방법(Brute-force method)과 탐욕적 방법(Greedy method) 등을 고려해 볼 수 있다.

우선 쉽게 생각해 볼 수 있는 방법으로는 맹목적 방법을 들 수 있다. 그러나 이 방법은 생성된 규칙의 수를 n개라고 할 때 O(2n)의 복잡도를 갖기 때문에 현실적으로 시스템 상에 구현한다는 것은 사실상 의미가 없다. 이런 이유로 구현하기가 쉽고 복잡도 역시 O(n)으로 낮은 탐욕적 방법이 자주 시도되고 있다.

탐욕적 방법은 먼저 첫 번째의 순위를 가진 규칙과 원래의 데이터와의 비교하여 정확도를 구하고, 다음에는 첫 번째 규칙과 두 번째 규칙으로 이루어진 규칙 집합과 비교함으로써 정확도를 구하게 된다. 이렇게 순차적으로 다음 순위의 규칙들을 하나씩 더해나가며 각각의 정확도를 계산하게 되고 계산된 적합도들 중에서 가장 높은 값을 가지는 규칙 집합을 선택하게 된다. 이러한 원리 때문에 규칙 순위상 상위에 있는 규칙들이 대부분 선택되어지고 하위의 규칙들은 제외되므로 만약 최적의 규칙 집합이 {Rule 1, Rule 5, Rule 7, ...} 의 형태로 이루어져 있다고 가정하면 탐욕적 방법의 알고리즘으로는 최적의 규칙 집합을 구할 수 없게 된다. 이와 같이 맹목적 방법과 탐욕적 방법이 가진 문제점은 최적의 규칙 집합을 구하기 어렵게 하므로 본 논문에서는 규칙 선택의 방법으로 유전자 알고리즘을 사용하려 하는 것이다.

유전자 알고리즘은 재생산(reproduction), 교배(crossover) 그리고 돌연변이(mutation)의 3가지 기능을 가지고 어떤 주어진 문제에 관해 최적화 해를 구하다. 이 3가지 기능을 사용하기 위해서 먼저 모집단(population)을 생성해야 하는데 제안한 시스템에서 하나의 염색체(chromosome)는 규칙 귀납 시스템에서 생성된 규칙의 수로 결정한다. 다시 말해 규칙 귀납 시스템에서 생성된 규칙 하나가 염색체 하나의 비트(bit)가 되고 만약 생성된 규칙이 선택되어진다면 1로 그렇지 못하면 0으로 만든다. 이렇게 만들어진 모집단을 가지고 유전자 알고리즘을 시작하면, 처음에는 규칙 귀납 시스템에서 생성된 규칙들로부터 확률적으로 일부의 규칙들이 선택되고 선택된 규칙들의 집합들간에 교배(crossover)가 이루어진다. 그림 2는 제안한 시스템이 생성된 규칙들을 어떻게 선택하는지를 보여준다. 위의 그림 1 에서 설명한 방법으로 규칙들을 선택하게 되면 재생산을 위해 적합도(fitness)를 계산해야 한다. 재생산은 염색체가 가지는 적합도에 따라 그 염색체를 복제하는 과정이며 계산된 적합도가 높을수록 선택된 규칙들이 살아 남을 확률이 높다는 것을 의미하기 때문이다. 적합도를 계산하기 위해서 선택된 규칙들은 원래의 데이터와의 비교가 이루어지게 된다. 먼저 선택된 규칙들은 원래의 데이터를 포함하는가를 확인하는 작업이 이루어진다. 만약 선택된 규칙들 중 하나가 원래의 데이터를 포함한다면 선택된 규칙의 클래스(class) 속성에 규칙의 H 값을 누적시키고 이 작업은 선택된 다른 규칙들도 마찬가지로 적용된다. 이런 식으로 원래의 데이터에 대해 각각의 규칙 클래스에 대한 H 값들이 누적되어졌으면 그 중 가장 높은 H값을 가진 클래스의 목표 속성과 원래 데이터 클래스의 목표 속성을 비교한다. 만약 비교한 두 개의 값

 

그림 3) : 유전자 알고리즘을 이용한 규칙 선택의 방법

이 일치하는 경우의 개수를 c 라 하고 전체 데이터의 개수를 t 라 한다면 시스템의 적합도는 다음과 같다.

적합도 = c / t

그러나 위와 같은 방법으로 원래의 데이터와 선택된 규칙들을 비교할 경우 선택된 규칙들 중 어느 한가지 규칙에도 만족하지 않는 데이터들이 존재할 수 있다. 이렇게 만족하지 않은 데이터들은 원래 데이터가 갖는 클래스 속성 중에서 분포도가 가장 높은 클래스 속성으로 포함시키는 방법을 사용하였다. 이렇게 첫 번째 세대가 끝나게 되면 다음 세대에서는 확률적으로 두 개의 규칙 집합을 선택해서 교배 및 규칙 집합의 재생산에 들어가며 그 방법은 그림 3의 방법을 따른다.

위에서도 언급했듯이 시스템은 높은 적합도를 가진 염색체를 높은 확률로 선택한다. 즉, 높은 적합도를 가진 염색체는 다음 세대에도 살아 남을 확률이 높다는 것이고 이를 구현하기 위한 방법으로 룰렛 휠 선택 방법(roulette wheel selection method)을 사용한다. 이렇게 선택된 2개의 규칙 집합은 임의로 선택된 교배점(crossover point)에 의해 나뉘고 그림 2 에서 도식화된 것처럼 새로운 2 개의 규칙 집합을 생산하게 된다. 규칙 집합이 총 32 비트라는 것은 규칙 귀납 시스템에 의해 생성된 규칙 수가 32 개라는 것을 의미하며, 규칙 1은 32개 규칙 중 13 개의 규칙이 규칙 2 에서는 12 개의 규칙이 선택되었다는 것을 의미한다. 교배 위치(crossover point)는 17번째와 18번째 비트 사이에 존재하며 결국 다음 세대에서는 18번째 이후 15개의 비트가 서로 바뀌었음을 알 수 있다. 이와 같이 새로운 규칙 집합에 의한 모집단이 생성되면 그림 2의 방법으로 돌아가 다시 적합도를 계산하고 최적의 규칙 집합을 찾아나가게 된다.

 

그림 4) : 교배 방법

결국 전체 시스템이 수행되는 방법을 간단히 요약하면 규칙 귀납 시스템에 의해 생성된 규칙들은 임의적으로 선택되어지고 이렇게 선택된 규칙들은 본래 주어진 데이터와 다시 비교하여 적합도를 구한 후, 유전자 알고리즘으로 선택된 규칙들을 세대 교번 시키면 시스템은 자동적으로 적합도가 가장 높은 규칙 집합을 선택하게 되는 것이다. 최종적으로 선택된 규칙 집합들은 비록 시스템을 수행시킬 때마다 다른 규칙 집합을 제공하지만 규칙 귀납 시스템에서 생성된 상위의 규칙들과 하위의 규칙들을 적절히 선택하게 된다.

계속적인 세대 교번을 통해서 최적의 규칙 집합을 탐색해 나가지만 세대 교번을 얼마나 해야 하는가도 유전자 알고리즘을 사용하면서 고려해야할 문제 중에 하나이다. 세대 교번이 끝나는 시점을 적합도가 증가하다가 감소하는 시점에서 잡기도 하지만 제안된 시스템에서는 구해진 적합도가 국부적 최적값(local optimal value)이 나올 것을 고려하여 임의로 정한 횟수(예를 들면 500회, 1000회 등)만큼 실행시킨 후, 그 중에서 가장 높은 적합도를 가진 규칙들을 선택하게끔 했다. 위 내용을 알고리즘으로 정리하면 다음과 같다.

위에서 설명한 바와 같이 제안한 시스템은 맹목적 방법과 탐욕적 방법이 가진 단점을 유전자 알고리즘을 사용하여 해결하기는 하지만, 데이터로부터 규칙을 생성하고 생성한 규칙들로부터 다시 원래의 데이터와 비교하여 적합도를 구하기 때문에 수행의 복잡도가 높다. 만약 주어진 데이터의 수를 d, 염색체(chromosome)의 수를 c, 모집단의 크기(population size)를 p, 그리고 세대수(generation)를 N이라고 하면 유전자 알고리즘으로 규칙들을 선택하는데 소요되는 복잡도는 d * c * p * N = O(dcp)가 되며, 특히 데이터의 수는 시스템의 수행 시간에 상당한 영향을 끼친다. 왜냐 하면 일반적으로 염색체의 수나 모집단의 크기 등은 수백에서 수천 정도의 크기를 가지므로 비교적 제한되어 있다고 볼 수 있지만 데이터의 수는 이보다는 훨씬 크기 때문에 시스템의 수행 시간을 크게 좌우하게 되며 이 문제는 앞으로 계속 연구해야 할 문제다.

VI. 실험 결과
본 시스템의 실험을 위해서 Postoperative Patient Data와 Car Evaluation Database를 사용하였으며 이 데이터들은 University of California Irvine machine Learning database repository 에서 채택하였다. Postoperative Patient Data는 외과 수술 후 환자들의 회복의 정도를 기록해 놓은 것들이다. 수술 후 나타나는 환자의 저체온증 현상은 대단히 중요한 문제로 이 데이터 집합의 속성들은 환자의 체온과 혈압 등에 대한 것들로 구성되어 있다. Car Evaluation Database는 자동차의 각 요구 사양에 맞추어 자동차를 평가해 놓은 것들이다. 요구 사항은 속성들로 포함되어 있고 가격(사는 가격과 유지비)과 기술(편안함과 안정도 등)의 6가지 속성으로 구성되어 있다.

 

표 1 : 실험 데이터

 

그림 4 : Postoperative Patient Data에 대한 유전자 알고리즘의 정확도

 

그림 3 : Postoperative Patient Data 에서의 규칙 선택

 

그림 5 : Postoperative Patient Data에 대한 탐욕적 알고리즘의 정확도(GA의 경우 모집단의 크기=100, 세대수=500)

 

그림 7 : Car Evaluation Data 에 대한 유전자 알고리즘의 정확도

 

그림 6 : Car Evaluation Database에서의 규칙 선택

 

그림 8 : Car Evaluation Database에 대한 탐욕적 알고리즘의 정확도(GA의 경우 모집단의 크기=100, 세대수=500)

그림 3 은 규칙 귀납 시스템에 의해 생성된 규칙들 중에서 유전자 알고리즘으로 선택된 규칙들을 보여준다. Postoperative Patient Data 를 적용한 이 실험에서는 생성된 100개의 규칙들 중 규칙 1, 2, 3 등 최종 61개가 선택되었으며 규칙 8, 14 등은 상대적으로 누락되었음을 알 수 있다. 그림 4는 염색체(chromosome)의 수와 세대(generation)의 수의 변화에 따른 적합도의 변화를 보여주는 것으로 규칙 생성 시스템에 의해서 먼저 생성된 100개의 규칙을 가지고 실험한 것이다. 크기와 적합도의 변화가 크지 않으므로 시스템의 복잡도가 모집단의 크기나 세대수에는 대해서는 크게 영향을 주지 않음을 확인할 수 있다. 도표에서 세로축의 정확도(Accuracy)는 적합도(fitness)에 100을 곱한 백분율 값을 말한다. 그림 5은 유전자 알고리즘과 탐욕적 방법을 비교한 그래프이다. 그림 3의 실험에서 선택한 규칙의 수를 100개로 고정하고 염색체 수와 세대수를 변화해 가며 실험한 것이라면, 그림 6의 실험은 유전자 알고리즘을 사용한 경우 염색체 수와 세대수를 각각 100, 500으로 고정시키고 선택할 규칙의 수를 변화해 가며 실험한 것이다. Postoperative Patient Data의 경우 탐욕적 방법의 최고 정확도만을 비교했을 경우 평균 10%이상 높은 정확도를 얻을 수 있음을 볼 수 있다.

그림 6, 7, 8 은 위의 그림 3, 4, 5 의 경우와 같은 방법으로 실험하였으며 Car Evaluation Database를 적용한 결과들이다. 그림 6 의 경우 H 값이 높은 상위 2개의 규칙들은 선택된 반면에 이 후 값의 차이를 보이는 규칙들의 경우 드물게 선택되었음을 알 수 있다.

VII. 결론
귀납 법칙 시스템에 있어서 생성된 규칙들이 본래의 데이터를 얼마나 잘 설명해 줄 수 있는지에 대한 문제와 관련지어서 생성할 규칙의 수를 정하는 문제, 특히 최적의 규칙 집합을 찾는 문제는 규칙 귀납 시스템들에게 있어서 큰 쟁점 중에 하나이다. 이를 해결하기 위한 방편으로 일반적으로 사용하는 탐욕적 방법은 앞서 언급했듯이 최적의 규칙 집합이 만약 생성된 규칙들이 서로 인접하지 않은 규칙들을 집합으로 하는 것이라면 그 해를 찾기가 불가능해진다. 이 문제를 해결하기 위한 방법으로 제안한 시스템에서는 유전자 알고리즘을 사용하였고 유전자 알고리즘은 이런 문제 해결에 있어서 더 높은 효율을 얻을 수 있음을 확인할 수 있었다.

--------------------------------------------------------------------------------

참고문헌
[1] Cendrowska, J. "PRISM:An Algorithms for Inducing Modular Rules," Int. J. of Man-Machine Studies, Vol. 27 pp.349-379, 1987.
[2] Clark, P. and T. Niblett, "The CN2 Induction Algorithms," Machine Learning, Vol. 3, pp. 261-283, 1989.
[3] Bloedorn, E., and R. S. Michalski, "Data-driven Constructive Induction in AQ17-DCI: A Method and Experiments," Reports of Machine Learning and Inference Laboratory," Center for Artificial Intelligence, George Mason University, 1991.
[4] 이창환, "Learning Inductive Rules Using Hellinger Measure," 한국정보과학회 논문지, Vol. 24, pp 663-672, 1997.
[5] Quinlan, J. R. "C4.5: Programs for Machine Learning," San Mateo, CA:Morgan kaufmann, 1993.
[6] De Jong, K. A., Spears, W.H., and Golden, D. F. "Using Genetic Algorithms for Concept Learning," Machine Learning, 13, pp 161-188, 1993.
[7] Jerzy W. Bala and Kenneth A. De Jong and Peter W. Pachowicz. "Multistrategy Learning from Engineering Data by Integrating Inductive Generalization and Genetic Algorithms", Machine Learning, vol 4, pp. 417-487, 1994.
[8] Beran, R. J. "Minimum Hellinger Distance for Parametric Models," Ann. Statics, vol 5, pp 445-463, 1977.
[9] Ryszard S. Michalski, "Inferential Theory of Learning," Machine Learning, vol 4, pp 3-61, 1994.
[10] De Jong, K. "Learning with Genetic Algorithms: An Overview", in Machine Learning, vol 3, no 3, pp. 123-138, 1988.
[11] Haleh Vafaie and Kenneth De Jong "Improving a Rule Induction System using Genetic Algorithms", Machine Learning, vol 4, pp. 453-469, 1994.
[12] DeJong, K. A. Spears, W. M. and Gordon, D. F. "Using Genetic Algorithms for Concepts learning", Machine Learning, pp. 161-188, 1993.
[13] Booker, L. B., Goldberg, D. E., and Holland, J.H. "Classifier Systems and Genetic Algorithms", Artificial Intelligence, pp. 235-282, 1989.

--------------------------------------------------------------------------------

이력사항

이창환
동국대학교 정보통신 공학과

신광현
동국대학교 정보통신 공학과