[ML_Basic] Decision Tree (의사 결정 나무)

 

강의 참고

https://kooc.kaist.ac.kr/machinelearning1_17/

인공지능 및 기계학습 개론Ⅰ 강좌소개 : edwith

 

Rule based learning (규칙 기반 학습)에는 큰 단점이 있다.

https://thought-process-ing.tistory.com/72

바로 Rule based learning의 가정 Perfect world라는 것이다. 우리의 세상에는 예측하지 못하는 noise들이 많다.

따라서 우리는 noises에 강한 방법들(robust methods)이 필요하고 가정이 조금 더 간결해야 한다.

그 중 하나의 방법이 의사결정나무(decision tree)이다.

 

다음과 같은 경우를 의사결정 나무로 나타내보자

Sky	Temp	Humid	Wind	Water	Forecst	EnjoySpt
Sunny	Warm	Normal	Strong	Warm	Same	Yes
Sunny	Warm	High	Strong	Warm	Same	Yes
Rainy	Cold	High	Strong	Warm	Change	No
Sunny	Warm	High	Strong	Cool	Change	Yes

이 인스턴스들을 이용해서 가설을 다음과 같이 세운다고 가정하자.

$$h_{0} : <Sunny,?,?,?,?,?> → Yes$$

 

$$ h_{1} : <Sunny, Warm, ?, Strong, ?, ? > → Yes$$

의사 결정 나무(decision tree)도 결국 가설을 잘 세우기 위해서 feature set을 잘 설정하는 것이 중요하다.

그러면 feature set을 잘 세우고 잘 못세우고의 기준은 어떻게 정할 수 있을까?

feature set을 잘 세운다는 것은 불확실성을 크게 줄이는 것(Reducing the most uncertainty)일 것이다.

그러면 불확실성을 측정할 수 있는 기준이 될 만한 것은 무엇이 있을까?

 

엔트로피(Entropy)

 고등학교 다닐 때 화학에서 많이 들어봤던 단어이다. 엔트로피는 널리 퍼져 있는 정도, 즉 불확실한 상태를 나타낸다고 할 수 있다. 즉 엔트로피가 높다는 것은 더 불확실하다는 것을 나타낸다.

그러면 확률적으로 엔트로피는 어떻게 나타낼까?

X가 이산분포이면 $$H(X) = - \sum_X P(X=x)log_{b} P(X=x)$$

X가 연속분포이면 $$H(X) = -  \int_X P(X=x)log_{b} P(X=x)dx$$

 

조건부 엔트로피(Conditional Entropy)

$$H(Y|X) =  \sum_X P(X=x)H(Y|X=x) =\sum_X P(X=x) \big\{- \sum_Y P(Y=y|X=x)log_{b} P(Y=y|X=x)\big\} $$

 

이 엔트로피를 이용한 것이 우리가 흔히 분류(classification)할 때 쓰이는 손실함수로 교차 엔트로피(CrossEntropy)이다.

다음은 이진분류(binary classification)에서 흔히 사용되는 간단한 교차 엔트로피 함수이다.

import math
def cross_entropy(label, prediction):
    if label == 1:
        return -math.log(prediction)
    else: # label ==0
        return -math.log(1-prediction)

 

의사결정나무(Decision Tree)의 문제

의사결정나무(Decision Tree)는 과적합(overfitting)이 잘 일어날 수 있는 환경이다.

우리가 가설을 좀 더 파고들고 해서 training data를 완전히 쪼개서(?) 훈련해서 정확도를 높였을 때 실제로 다른 test data를 넣었을 때는 성능이 훨씬 떨어질 수 있다.

따라서 적절할 때 조기종료(early stopping)을 해야한다.