[기계학습 2강] Decision Tree & Information Gain

※이 내용들은 (KAIST Open Online Course)의 인공지능 및 기계학습 개론 1 Chap. 2강 내용을 기반으로 재구성하였음을 먼저 밝힙니다.※

 

 

지난시간 배운 것 :: Rule based machine learning

---

딸 아이가 밖에서 나가서 놀 것인지 아닌지를 판별하는 모델을 만들어보았었다. 하지만 이것은 퍼펙트 월드에서만 적용되므로 현실성이 없었다. 현실 문제는 항상 에러가 존재한다. 에러가 있는 것을 판별하는 방법 중 하나가 Decision Tree이다.

 

 

<이전 글 참조>

2021.03.31 - [Statistics/Machine_Learning] - [기계학습 2강] Rule Based Machine Learning

[기계학습 2강] Rule Based Machine Learning

 

Decision Tree의 표현

---

저번 주에 사용했던 <Sunny, ?, ?, ?, ?, ?> (?: don't care로 둘 중 어느 것도 상관없음)을 Decision Tree로 나타내보자.

 

여기서 몇 개의 Feature(Temp, Wind)의 ?가 구체적(Cold, Warm, Light, Strong)으로 주어진다면 다음과 같이도 나타낼 수 있다.

 

 

 

다른 예제 Credit Approval Dataset을 이용한 Decision Tree

---

이 데이터셋은 archive에서 자세한 Feature들에 대한 정보를 확인할 수 있다. 하지만 learning이라는 것은 도메인 지식과는 무관하게 하는 것이기 때문에 활용하지 않도록 하겠다.

 

 

Dataset 간단 분석

 

• 690개의 instance를 가지고 있는데 그 중 307개가 positive instance이다.
• instance들에 대해서 A1~A15개의 Feature들을 가지고 있다.
• A1은 value로 a ,b,?(정보가 없는 것) 3가지를 A9은 value로 t,f 2가지를 가지고 있으며 이때 Class의 label은 다음과 같다.

 

 

하나의 Feature를 이용하여 신용평가를 해보기

 

• A1를 사용하여 판별한다면 a, b, ?의 정보를 가지고 판별한다. 하지만 효율성이 떨어진다.

• A9를 사용한다면 t,f의 정보를 가지고 판별한다. A1를 사용한 것보다는 효율성이 높지만 좋지는 못하다.

하나의 Feature만을 가지고 판별한다면 결과가 좋지 못했다. 여러 가지 Feature를 엮어서 Decision Tree로 나타낸다면 더 효율적일 것이다. 그렇다면 어느 Feature를 루트에 놓는 것이 좋을까? 이를 해결하기 위해 Entropy라는 개념을 도입해야 한다.

 

 

Entropy

---

 

Entropy란 어떤 attribute를 더 잘 분류할 수 있을지 알려주는 지표로 확률변수(random variable)의 불확실성(Uncertainty)이 높냐 낮냐를 나타낸다.

 

간단한 예를 들어 보자. 동전을 던져 앞면만 나오는 동전이 있다면 이 동전의 결과의 확률분포에 대한 불확실성은 낮고 엔트로피도 낮다. 하지만 50%의 확률로 앞면이 나온다고하면 이 확률분포에 대한 불확실성은 높고 엔트로피도 높다.

 

즉, 다음과 같이 볼 수 있다.

 

- Featrure들을 확률변수로 본다.

- 엔트로피가 높으면 불확실성은 크다.

- $H(X) = -\sum_{X} P(X=x) log_{b} P(X=x)$(확률밀도함수를 이용하는데 확률밀도함수에 정의된 모든x에 대해서 그냥 확률밀도함수와 log를 씌운 확률밀도함수의 곱으로 나타낸다.  X가 연속적인 공간에 정의되어 있다면 sigma가 integral로 바뀔 것이다. )

 

 

 

conditional entropy

---

이제 conditonal entropy 즉, 어떤 특정 feature에 대한 기본 정보가 있을 때 entropy를 구해보자. (X라는 feature가 주어졌을 때 y라는 feature의 엔트로피를 구해보자.)

 

 $H(Y|X) = -\sum P(X=x) H(Y|X=x)$

 

먼저 이 식을 이해해보자. 이해를 위해 아래 그림과 같이 X(빨간색)와 Y(파란색)만으로 이루어진 결합분포를 가정해보자.

이미지 출처 : (https://zetawiki.com/wiki/%ED%8C%8C%EC%9D%BC:Multivariate_normal_sample.svg)

•  $H(Y|X)$에서 X가 주어졌을 때 Y의 엔트로피를 구해야 하는데 X는 특정 x들로 이루어져 있다.
• 특정 x들은 이에 해당하는 Y의 분포를 가지고 있다. (위의 그림을 참조해서 생각해보면 좋다.)
• 따라서, $H(Y|X)$는  $H(Y|X=x)$을 모든 x에 대해 구해준 후 합해준 것과 같을 것이다.

 

다음으로 한 줄 더 진행된 아래의 식을 이해해보자.

 

$H(Y|X) = -\sum_{X} P(X=x) H(Y|X=x)$

$= \sum_{X}$ { $ \sum_{Y} P(Y=y | X=x) log_{b} P(Y=y |X=x)$ }

 

• $H(Y|X=x)$식은 특정 x라는 값이 주어졌을때 Y의 분포였다.
• 위 부분의 Entropy를 구하는 식 $ H(X) = -\sum_{X}P(X=x)log_{b}P(X=x)$ 을 참조해보자.
• 이를 $H(Y|X=x)$에 적용할 것인데 X=x라는 조건이 주어졌을 때 Y의 분포이므로 Y에 대해서 적용해주고 X=x는 그냥 그대로 써주면 된다.
• 따라서, $H(Y|X=x)$는 $ P(Y=y | X=x)log_{b}P(Y=y | X=x)$로 나타낼 수 있다.

 

이제 다시 예시로 돌아와서 적용해보자. conditional entropy는 $ A_{1}$나 $A_{9}$와 같은 확률변수(random variable)가 아닌  positive와 negative라는 class에 대해서도 엔트로피를 구할수있다.

 

$H(Y=y) - \sum_{Y } P(Y=y)log_{2}P(Y=y)$, $Y \in${$+, - $}

이 케이스에서 $P(Y=y)$에 대한 하나의 값(t)를 구해보면 $P(Y=t) = \frac{307}{307+383}$이다. 이 방법은 MLE를 구하는 것을 적용한 것이다.

 

이제 Y에 대한 Conditional Entropy 를 구해보자.

$H(Y|A1) = \sum_{X} \sum_{Y} P(A1=x, Y=y) log_{2} \frac{P(A1=x)}{P(A1=x, Y=y)}$ 

$H(Y|A9) = \sum_{X} \sum_{Y} P(A9=x, Y=y) log_{2} \frac{P(A9=x)}{P(A9=x, Y=y)}$

 

이제 위의 식과 아래의 식의 차이를 나타내는 Information Gain이라는 측정방법에 대해 알아보자.

 

 

Information Gain

---

Information Gain은 Y라는 클래스의 엔트로피에서 $A_{i}$라는 특정 Attribute가 주어졌을때의 차이를 말한다. 

$G(Y, Ai) = H(Y) - H(Y|Ai)$

Information Gain이 필요한 이유는 Y라는 클래스의 엔트로피를 구했을 때보다 $A_{i}$라는 특정 Attribute가 주어졌을때 엔트로피가 얼마나 줄어드는가를 보기 위해서이다. 위에서 A1과 A9일 때의 Y의 conditional entropy는 A9일 때가 더 적다. 

 

 

우리는 엔트로피가 적은 Attribute를 찾기 원하기 때문에 이를 찾아 Decision Tree를 구성할 때 Root node로 선정해줄 수 있다. 이제 더 많은 Attribute에 대해서 Decision Tree를 그려보는 알고리즘을 고려해보자. 여러가지가 존재하지만 가장 기본적인 ID3 알고리즘을 알아보자.

 

 

Top-Down Induction Algorithm :: ID3 algorithm

---

방법은 다음과 같다.

• 처음 open 노드를 만든다. 이를 루트를 한다.
• 다음으로 이 루트에 모든 instance를 넣어준다. 
• 오픈 노드가 없을 때까지 반복을 할 것이다.
• 오픈 initial 노드를 선택한 다음 가장 최고의 변수를 선택해야 한다. (이를 위해 Information Gain을 구해야한다.)
• 선택된 변수(ex. A9)의 Value(t, f)에 대해서 instance를 정렬해서 케이스에 넣어준다.
• 정렬된 instance들이 가지를 따라 다음 노드에 들어가게 된다.
• 노드에 들어가게 된 instance들이 동일한 클래스 label(+나 -)를 가질 경우 멈춘다.

 

 

Overffiting

---

Decision Tree를 더욱 세부화시킨다면 주어진 데이터에 대해서만 잘 작동하게 된다. 하지만 현실은 에러가 존재하고 노이즈가 존재하기 때문에 다른 데이터에 대해서는 올바르게 판단하지 못하게 된다. 즉, overfitting이 발생한다. 따라서, 무조건 Decision Tree를 복잡하게 구성하는 것은 좋지 못하다. 

 

 

 

 

-히비스서커스-