Decision Tree란? :: ID3 알고리즘, 엔트로피란?

의사결정나무란? 

 

Decision Tree란? 의사결정 규칙을 나무구조로 나타내에 전체 데이터를 소집단으로 분류하거나 예측하는 분석기법

 

전체 데이터에서 마치 스무고개하듯이 질문하며 분류해나간다.

그 모양이 마치 나무와 같아서 의사결정 나무라 부른다.

 

예)

 

 

 

나무에서 분할되는 부분을 노드(node) 라 하고, 가장 처음 노드를 root node, 가장 마지막 노드들을 terminal node라 한다.

 

그렇다면, 위의 예시에서 모양 or 색 중에서 무엇을 먼저, 어떤 기준으로 나눠야 할까?

 

그 답은 불순도가 낮아지는 방향으로 나눠야 하며, 그 방법으로 ID3, CART, C4.5 등 여러 알고리즘이 있다.

본 포스팅에서는 ID3에 대해 알아보고자 한다.

 

---

 

ID3 알고리즘에 대해 알아보기에 앞서, 불순도란 무엇이며 어떻게 측정하는지 알아보겠다.

 

불순도란?

 

불순도란 순도의 반대말로, 영어로는 Impurity 이다.

 

예를 들어, 다음과 같이 항아리 세개가 있다.

1번과 3번항아리를 오롯이 파란공, 빨간공으로만 채워져 있으며, 2번 항아리는 빨간공과 파란공이 정확히 반반 섞여있다.

1번과 3번 항아리는 순도 100%라 할 수 있으며, 2번 항아리는 불순도가 높은 상태라 할 수 있다.

 

 

이 불순도를 수치화한 지표로 엔트로피(Entropy), 지니계수(Gini Index) 등이 있는데, 

불순도를 엔트로피로 계산한 알고리즘이 바로 ID3이며, 지니계수로 계산한 알고리즘이 CART 알고리즘이다.

 

---

 

엔트로피란?

 

Entropy란? 불순도를 측정하는 지표로서, 정보량의 기댓값

 

엔트로피를 수식으로 표현하면 다음과 같다.

 

$$ Entropy(S) = \sum_{i=1}^c p_i*I(x_i) $$

S : 이미 발생한 사건의 모음, c : 사건의 갯수

 

* 정보량

 

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

$$ I(x) = log_2\frac{1}{p(x)} $$

p(x) : 사건 x가 발생할 확률

 

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

 

사건 x가 발생할 확률이 증가할 수록, 정보량은 0에 수렴한다. 즉, "흔하게, 자주 발생하는 사건일수록 그닥 많은 정보를 가지고 있지 않다." 라고 해석할 수 있다.

 

위의 항아리 예시에서 빨간구슬의 비율을 x축, 그에 따른 엔트로피 값을 y축으로 그래프를 그리면 다음과 같다.

 

 

항아리에 순도가 100% (한 종류의 공만 있는 상태 = 분류하기 좋은 상태) 일 때 Entropy는 0이며, 두 공이 정확히 반반 섞여 있을 때 (불순한 상태 = 분류하기 어려운 상태) Entropy가 최대값을 갖는다.

즉, 불순한 상태일 수록 Entropy는 큰 값을 가지며, 불순도가 클 수록 분류하기 어렵다.

 

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

 

---

 

ID3 알고리즘

 

ID3 알고리즘은 엔트로피로 불순도를 계산하며, 독립변수가 모두 범주형일때만 가능하다는 단점이 있다. 

(연속형 변수도 가능하도록 발전한 것이 C4.5 알고리즘이다.)

 

---

 

ID3 알고리즘엔 정보획득량(Information Gain) 이라는 개념이 나온다.

 

정보획득량이란? 분할전 Entropy와 분할 후 Entropy의 차이

 

이를 수식으로 표현하면 다음과 같다.

 

$$ IG(S,A) = E(S) - E(S|A) $$

A : 속성(Feature), E : Entropy

 

여기서, 엔트로피는 불순도를 나타낸다 했다. 즉, 정보획득량이 크다는 것은 어떠한 속성으로 분할 했을 때 불순도가 줄어든다는 것을 의미한다. 

 

가지고 있는 모든 속성(= X, Features) 에 대해 분할 후 정보획득량을 계산하고, 이 값이 가장 큰 속성부터 분할의 기준으로 삼는다. 

 

---

 

기상조건에 따른 테니스경기 참가여부를 ID3 알고리즘으로 분류해보고자 한다.

 

 

Approach 1) 분할 전, 목표 속성인 참가여부에 대한 엔트로피 계산

 

$$ E(경기)=-\frac{9}{14}log_2(\frac{9}{14}) -\frac{5}{14}log_2(\frac{5}{14}) = 0.940 $$

 

Approach 2) 각 속성에 대해 분할 후 엔트로피 계산

 

2-1) 날씨

$$ E(경기|날씨)= p(맑음)*E(경기|맑음) + p(흐림)*E(경기|흐림) +p(비)*E(경기|비) $$

 

 

2-2) 온도

 

 

2-3) 습도

 

 

2-4) 바람

 

 

Approach 3) 각 속성에 대한 Information Gain 계산

 

 

Approach 4) 각 terminal node에 대해 Approach 1, 2, 3 반복

 

예를 들어, "맑음"으로 분류된 노드는 "날씨 = 맑음" 인 데이터만 가지고 와서 다시 분할 전 엔트로피를 계산한다.

 

 

* Approach 4)

 

 

 

Information Gain이 가장 큰 "습도"를 기준으로 분할

 

 

 

위 예시의 최종 결과는 다음과 같다.

 

 

 

---

 

다음 포스팅에서는 Gini Index로 불순도를 계산하는 CART 알고리즘에 대해 소개하겠다.

 

---

 

 

참고 및 출처

 

https://smalldataguru.com/%EA%B2%B0%EC%A0%95-%ED%8A%B8%EB%A6%ACdecision-tree%EC%9D%98-%EC%A7%80%EB%8B%88-%EB%B6%88%EC%88%9C%EB%8F%84gini-impurity%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%BC%EA%B9%8C/

 

https://ratsgo.github.io/machine%20learning/2017/03/26/tree/

 

https://bskyvision.com/598