의사결정트리 분석 기법

1장. 의사결정트리 분석 소개
2장. ID3 알고리즘
   (1) ID3 알고리즘 소개
   (2) Entropy 계산
   (3) Information 계산
   (4) 알고리즘 구현 소스코드
3장. C4.5 알고리즘
4장. 참고자료 <발췌>

ID3 알고리즘

1. ID3 알고리즘 소개

    ID3 알고리즘은 대표적인 의사결정트리 기반 분류 알고리즘이다. ID3 알고리즘은 1970년대 후반 J. Ross Quinlan 박사에 의해 제안되었다. (대청. CRM위한 데이터마이닝, p.157) 그 이후에 개발된 다양한 의사결정트리 기반의 분류 알고리즘(C4.5, CART, CHAID 등)들도 기본적으로 ID3 알고리즘의 아이디어에 기초하고 있다. 따라서 현재 데이터마이닝 툴에서 지원하고 있는 C4.5(C5.0), CART, CHAID 등의 알고리즘을 이해하기 위해서는 ID3를 먼저 정확해게 이해할 필요가 있다. (ID3 알고리즘은 오래된 방법이므로 배울 필요가 없다고 생각하고, 처음부터 진보된 알고리즘인 C4.5를 공부하는 경우가 있는데, ID3를 이해하지 못한 상태에서 C4.5등의 최근 사용되는 알고리즘을 이해하기는 쉽지않다. 즉, ID3 알고리즘을 알지 못하고서는 C4.5를 이해할 수가 없다.)

   ID3 알고리즘에 관계된 키워드들은 아래와 같다. 알고리즘 과목 또는 인공지능 과목을 수강한 경험이 있다면 익숙한 단어들을 찾을 수 있을 것이다. 본 2장을 자세히 학습하면 ID3 알고리즘이 왜 아래의 키워드들과 관계가 있는지 이해하게 될 것이다.

  ▪ 탐욕 알고리즘 (Greedy Algorithm)
  ▪ Divide & Conquer 방식
  ▪ 귀납적 추론
  ▪ 휴리스틱 (Heuristic) 기법
  ▪ 엔트로피 (Entropy)
  ▪ 정보 이득 (Information Gain)
 
   먼저 간단한 데이터를 가지고 ID3 알고리즘이 어떤 일을 하는 지 살펴보도록 하자. 설명에서 사용할 데이터는 데이터마이닝 및 기계학습 등의 교재에서 예제로 많이 사용되고 있는 유명하고 간단한 데이터이다. 데이터이름은 weather 이다. 간단히 설명하면 어떤 날씨 조건(조망, 온도, 습도 등)에서 경기를 했는지, 안했는지에 대한 정보를 기록한 데이터이다.

   데이터 파일의 형식은 csv 형식의 텍스트 파일이다. 아래의 <그림1>과 같이 메모장으로 열수도 있고, <그림2>와 같이 엑셀 프로그램을 사용해서 열수도 있다. 엑셀 프로그램을 사용한 경우 데이터를 더 잘 이해하며 볼 수 있다. 맨 위의 한줄은 데이터의 각 속성(필드)의 이름이고, 그 아래 14개의 레코드(Record or Instance)가 존재함을 볼 수 있다.

 

 그림1

 

   그림2

   위 데이터를 ID 알고리즘에 적용하면 어떤 결과가 나올까? 우리는 이 데이터를 통해 어떤 날씨가 경기하기에 좋고, 또 어떤 날씨가 경기하기에 안 좋은 날씨인가에 대한 지식을 얻고 싶다. ID3 알고리즘을 지원하는 다양한 데이터마이닝 프로그램들이 있지만, 무료로 공개되어 있는 weka 프로그램을 작성하여 수행한 결과는 아래와 같다.

   그림3

   위 그림이 갖는 의미를 해석해보자. 왼쪽부터 순서로 해석하면 아래와 같은 규칙으로 된 지식들을 얻을 수 있다. 해석하는 방법은 단순하므로 3개 정보만 기록하였다. 물론, 해석결과가 일반적이지 않을 수 있지만 주어진 데이터에서는 적합한 규칙들이다. (아마도 실내 경기장이 아닐까?)
 
 ▪ 날씨가 맑고(outlook=sunny) 습도가 낮으면(humidity=low) 운동을 한다. (play=yes)
 ▪ 날씨가 맑고(outlook=sunny) 습도가 낮으면(humidity=high) 운동을 한다. (play=no)
 ▪ 날씨가 흐리면(outlook=overcast) 운동을 한다. (play=yes)

2. Entropy 계산 방법  

참고 : (1) Data Mining (IAN.H) p.93-94. (2) Concept & Tech(한글판) p.356.

   ID3 알고리즘의 자세한 동작 방법, 절차는 본 장의 마지막에서 설명하기로 하고, 먼저 필요한 수식들을 학습하도록 하자. 본 절에서는 Entropy 개념 및 계산 방법을 학습한다.

   엔트로피(entropy)는 주어진 데이터 집합의 혼잡도를 의미한다. 즉, 주어진 데이터 집합에 레코드들이 서로 다른 종류(클래스)들이 많이 섞여있으면 엔트로피가 높고, 같은 종류(클래스)의 레코드들이 많이 있으면 엔트로피가 낮다. 곧 소개할 엔트로피 계산식에서는 엔트로피 값은 0에서 1사이의 값을 갖는다. 가장 혼잡도가 높은 상태의 값이 1이며, 하나의 클래스로만 구성된 상태의 값이 0이다. 의사결정트리 분류 알고리즘에서는 엔트로피가 높은 상태에서 낮은 상태가 되도록 데이터를 특정 조건을 찾아 나무 모양으로 구분해 나간다.

   그림4

   바로 전 절에서 소개한 그림을 예로 들어 설명해보자. 매 위의 노드(outlook이라고 써있는 노드)의 엔트로피 값이 가장 크며 그 하위의 3개의 노드(outook에 의해 구분된 하위 노드)들의 엔트로피가 더 낮을 것이다. 또 그 하위에 있는 노드들은 부모노드 보다 엔트로피 값이 작을 것이다.

   엔트로피 값은 아래의 식에 의하여 계산된다. 이 식은 주어진 데이터셋 S에 대한 엔트로피 값을 구하는 계산식이다. 엔트로피 값은  즉 각 클래스 값의 포함 비율에 로그를 적용하고 다시 값을 가중치로 곱한 값을 모두 더하는 식이다. log2 함수 적용을 통해 마이너스(-) 값이 나타나므로 전체 수식 값에 - 를 붙여주어 0 에서 1 사이의 값을 갖도록 한다.

 

  위 식에서 는 i번째 클래스 값이 대하여 해당 데이터집합 중에서 차지하는 비율(Probability)을 의미한다. 각 변수들이 갖는 의미는 아래와 같다.

  S : 주어진 데이터들의 집합
 C = {C1, C2, ... , Ck} : 클래스 값들의 집합
 freq(Ci,S) : S에서 class Ci에 속하는 레코드의 수
 |S| : 주어진 데이터들의 집합의 데이터 개수

 
    그러면, 간단한 예를 가지고 엔트로피 값을 계산해보자. 10명의 회원이 있는데 5명이 우수회원, 5명이 일반회원이라고 하자. 그러면, 데이터가 완전히 혼합되어 있으므로 엔트로피 값은 1이 된다. 반면, 10명 모두 일반회원이라면 전혀 혼합되어 있지 않으므로 엔트로피 값은 0 이 된다.

  10명의 회원이 있는데 5명이 우수회원, 5명이 일반회원인 경우 엔트로피 계산식에 적용하면 아래와 같다.

   식?

  
   10명의 회원이 있는데 10명이 우수회원, 0명이 일반회원인 경우 엔트로피 계산식에 적용하면 아래와 같다.

 식?


  이해를 위하여 다른 예를 들어보자. 노드에 데이터가 총 14개 있는데 클래스가 Yes인 레코드가 9개, No인 클래스가 5개 있다고 가정하자. 그러면 아래와 같이 계산할 수 있다.

 

 식?

   물론, 클래스가 2개 이상일 경우에도 같은 방식으로 적용하면 된다. 클래스의 값이 a 또는 b 또는 c의 3가지인 경우는 아래와 같이 계산될 수 있다.

  

 식?

잠깐! 실습문제  

 실습문제 :  데이터셋의 클래스값들을 입력받아 엔트로피 값을 구하는 프로그램을 작성하시오.
 ( 여러 개의 정수들을 입력하고 엔터를 치면 해당 노드의 엔트로피 값을 계산합니다. )

 결과예시 :     Input # of Classes :  5 5
                          Entropy Value :  1.0

                     Input # of Classes :  10 0
                          Entropy Value :   0.0

                     Input # of Classes :  2 3 5
                          Entropy Value :  ??? 

3. Information Gain 계산 방법  

  “정보 이득(information gain)”이란 어떤 속성을 선택함으로 인해서 데이터를 더 잘 구분하게 되는 것을 의미한다. 예를 들어, 학생 데이터에서 수능등급을 구분하는데에 있어 수학 점수가 체육 점수보다 변별력이 더 높다고 하자. 그러면 수학점수 속성이 체육 점수 속성보도 정보이득이 높다라고 말할 수 있다. 정보이득을 계산하기 위해서는 먼저 엔트로피 개념과 계산방법을 이해해야 한다. 따라서, 정보이득 계산방법을 설명하기 전에 엔트로피 계산식을 살펴보기로 하자.

정보 이득의 계산식은 아래와 같다.

   식 ?

   여기서,       , I(s1,s2,...,sm) 은 원래 상위 노드의 엔트로피를 의미한다. 즉, 상위노드의 엔트로피에서 하위노드의 엔트로피를 뺀 것이다. 그리고 E(A)는 A라는 속성을 선택했을 때 하위로 작은 m개의 노드를 나누어진다고 하면 하위 각 노드의 엔트로피를 계산한 후 노드의 속한 레코드의 개수를 가중치로 하여 엔트로피를 평균한 값이다.

  식 Gain(A) 의 의미는 ... 속성 A를 선택했을 때의 정보이득 양을 계산하는 수식으로써 ... 원래 노드의 엔트로피를 구하고 A라고 하고, 속성 A를 선택한 후의 m개의 하위 노드로 나누어진 것에 대한 전체적인 엔트로피를 구한 후 그것을 B라고 하면, A-B를 의미한다. 이 값이 클수록 정보 이득이 큰 것이고 해당 속성 A가 변별력이 좋다는 것을 의미한다.



 그림?

각 노드의 Entropy를 구해보자.

   

 각 노드의 엔트로피를 계산하였으면, 속성 A에 의한 Information 값을 구할 수 있다.

 

잠깐! 실습문제  

 실습문제 :  Weather 데이터에서 [Outlook] 속성을 사용하는 경우 Information Gain을 구하는 프로그램을
 작성하시오.

 결과예시 :     Weahter 데이터에서 Outlook 속성에 대한 Information Gain 값을 계산합니다.

 - 부모노드의 Entropy : 0.940

 - 하위노드( sunny ) Entropy : 0.971    가중치 : 5/14
 - 하위노드(overcast) Entropy : 0        가중치 : 4/14
 - 하위토드( rainy )  Entropy : 0.971    가중치 : 5/14

 - Information Gain :  0.246

4. ID3 알고리즘 정리

 * ID3 알고리즘
1. 전체 데이터를 포함하는 루트 노드를 생성한다.
2. 만약 샘플들이 모두 같은 클래스라면, 노드는 잎이 되고, 해당 클래스로 레이블을 부여한다.
3. 그렇지 않으면 정보이득이 높은(즉, 데이터를 가장 잘 구분할 수 있는) 속성을 선택한다.
   (이때 정보이득은 엔트로피의 변화를 가지고 계산한다.)
4. 선택된 속성으로 가지(Branch)를 뻗어 하위 노드들을 생성한다.
   (각 하위 노드들은 가지의 조건을 만족하는 레코드들이다.)
5. 각 노드에 대해여 2단계로 이동한다.

* 정지조건  
- 해당 노드에 속하는 레코드들이 모두 같은 클래스를 같는다.
- 상위 노드에서 이미 모든 속성들을 다 사용하였다. 더 이상 사용할 속성이 없다.

* ID3의 특징
- 범주형 속성에 대해서만 사용이 가능하다.
  (엔트로피 기반 척도 수식이 범주형 속성에 대해서만 적용이 가능하기 때문에 그렇다.) 
- 상위 노드에서 사용된 속성은 다시 사용하지 않는다.  

5. ID3 알고리즘의 한계 (단점)

- 연속형 (수치형) 속성을 사용할 수 없다.
- 범주형 속성을 전체에 대해서 하위 노드를 생성하기 때문에
  선택된 속성의 범주값이 매우 많을 경우 하위 노드의 가지(branch)의 수가 매우 많아진다.
  예를 들어, 주소가 선택된 경우 매우 잘게 구분되고 해석이 어려워진다.

* 참고자료 (References)

[1] 인공지능의 이해, 생능출판사, 양기철 저, p.204 - 207
[2] MACHINE LEARNING, Tom M. Mitchell, Carnegie Mellong University. (p.52-80, 3장 전체)

* 참고자료 [1]에 발췌

Quinlan이 1986년 제안한 ID3 알고리즘은 학습결과(개념)를 의사결정 트리(Tree) 형태로 표현하며 예를 통한 귀납적 학습을 수행한다. 의사결정 트리는 하향식(Top-Down)으로 생성하며 필요한 정보는 미래 준비되어 있어야 한다. ID3는 루트 노드(Root Node)에서 평가할 특성(Property)을 선택하여 평가 후 자신의 자노드(Child Node)를 생성한다. 각자의 자노드에서 같은 작업이 반복되고 더 이상의 자노드가 생성되지 않을 때까지 반복하여 의사결정 트리를 완성한다.

 ( 위 자료에서 1986년 이라는 연도는 잘못된 듯하다. ID3는 1970년대 발표된 것으로 알려져있다.)

관련파일들


by 에이아이 2009. 7. 29. 19:22