[ML] ID3 알고리즘, 엔트로피(Entropy)

이전에 업로드하였던 의사 결정 나무(Decision Tree)에서 조금더 세부적인 내용에 대해 정리하기 위해 글을 써본다.

-목차-

1. ID3 알고리즘이란?

    1.1 엔트로피(Entropy)

    1.2 정보 획득량(Information Gain)

1. ID3 알고리즘이란?

ID3 알고리즘은 의사 결정 나무 알고리즘의 한 종류로 Iterative Dichotomiser 3의 약자이다. Dichotomiser는 “이분하다”라는 뜻의 프랑스어로, 반복적으로 이분하는 알고리즘이라고 말할 수 있다.

ID3 알고리즘은 불순도 지표로 엔트로피를 사용하며 독립변수가 모두 범주형 변수일 경우에 사용 가능한 알고리즘이다.

 

1.1 엔트로피(Entropy)

ID3 에서 불순도의 지표로 엔트로피를 사용한다고 하였다. 그렇다면 엔트로피는 무엇일까?

엔트로피의 수식은 아래와 같이 계산할 수 있다.

\[Entropy = H(S) = \sum_{i=1}^{c}p_i \log_{2}\frac{1}{p_i} = -\sum_{i=1}^{c}p_i \log_{2}{p_i}\]

 

이진 분류 (Binary classification) 문제에서 한 사건의 확률이 \(p(x)\)라고 할 때, 엔트로피는 아래 그림과 같다.

이진 분류에서 어떤 범주형 피처가 5:5 로 섞여있다면 엔트로피가 최대가 된다. 불순도가 가장 큰 상태인 것이다.

 

이때 정보량이란 어떤 사건이 가지고 있는 정보의 양을 의미하며, 이는 식으로 다음과 같다.

 

\[information = I(x) = \log_2\frac{1}{p(x)}\]

 

사건 x가 발생할 확률을 x축, 정보량을 y축으로 그래프를 그리면 아래와 같다.

사건 x가 발생할 확률이 증가할수록, 정보량은 0에 수렴한다. 즉 , "흔하게 많이 발생하는 사건일수록 그다지 많은 정보를 가지고 있지 않다."라고 해석할 수 있다. 엔트로피는 정보량의 합이라고 이해한다면 분류 문제를 푸는 트리 모델은 leaf node는 정보량이 작을수록 좋은 모델이 된다고 생각할 수 있다.

이에 따라, Entropy를 작게 하는 방향으로 가지를 뻗어나가며 의사결정 나무를 키워나가는 것이 ID3 알고리즘의 핵심이라고 할 수 있다. 

 

1.2 정보 획득량(Information Gain)

ID3 알고리즘에서는 Entropy 값의 변화량을 나타내기 위해 Information Gain이라는 개념을 사용한다.

정보획득량(information gain)는 \(X\)라는 조건에 의해 확률 변수 \(Y\)의 엔트로피가 얼마나 감소하였는가를 나타내는 값이다. 다음처럼 \(Y\)의 엔트로피에서 \(X\)에 대한 \(Y\)의 조건부 엔트로피를 뺀 값으로 정의된다.

 

\[IG(Y, X) = H(Y) - H(Y|X)\]

 

Information Gain은 아래 수식과 같이 분기 전후 엔트로피의 차이 값으로 계산됩니다. 이때 분기 후 엔트로피는 양쪽 가지로 나뉘는 확률 \(p(t_i)\)를 가중치로 곱해 합쳐진다.

 

\[Information\,Gain = IG(Y, X) = H(Y) - H(Y|X)\\=H(Y) - \sum p(t)H(t)\]

 

최적의 Decision Tree를 만들기 위해, 여러 지표 중 분기 후 엔트로피 \(\sum p(t)H(t)\)가 작아지는 지표를 선택해야 한다. 즉, Information Gain이 가장 큰 지표를 선택하라는 말과 동일하다.

 

---

참고 자료

https://leedakyeong.tistory.com/entry/Decision-Tree

https://tyami.github.io/machine%20learning/decision-tree-2-ID3/