Decision Tree 에서의 ID3 알고리즘

Decision Tree 란 ??? 

A decision treeis a decision support tool that uses a tree-like model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an 
algorithm that only contains conditional control statements.
- Decision tree - Wikipedia -

- Decision Tree의 정의를 살펴보면, 트리모양으로 모델링 된, 비용과 결과등을 종합하여, 결정을 내리는 도구라 할 수 있겠다. Decision Tree 모델은 분류(Classification) 과 회귀(Regression) 등 모두 사용되는데, 이는 나중에 포스팅올리겠습니다... ㅎㅎ . 우선 여기서 집고 넘어갈 점은 Decision Tree 모델이 무엇을 기준으로 결정을 내리는데 도움을 주겠냐 이말이다.

 

[ Decision Tree 모델의 간단한 모델링]

이 처럼 Decision Tree 에서 Node 들을 나눠 나갈때, 무엇을 기준으로 하는지는 ID3, CART(Sk learn에서 주로 쓰인다.), C4.5 등 여러가지가 존재하지만, ID3에 대해서 알아보자.

---

 

 

불순도(Impurity) 란??

흔히 불순도를 정의 하기 전에 다음 그림을 살펴보자.

항아리 1 번 과 같은 경우 파랑 100으로 이루어져 순도 100%라 할 수 있지만,

항아리 2와 같은 경우 파랑 4개 주황 4개로 순도 50%로 이루어져 있다 할 수 있고,

항아리 3과 같은 경우에 주황 8개로 주황구슬 순도 100%로 이루어져 있다 할 수 있다.

 

여기서 중요한 점은 Decision Tree  model 에서 이러한 순도를 기준으로 Node를 분할해 나가는데. ID3 기반의 Decision Tree model 은 Impurity 값으로 엔트로피를 사용한다는 것이다.

 

 

 

---

그럼 엔트로피란???

Entropy 란 불순도를 뜻하는 지표로써,

로 표현이 된다. 좀 더 일반화 시켜보자면,

 

가 되게 되고, 

(Pk=A영역에 속하는 attribute값 가운데 k 범주에 속하는 속성값의 비율)

(Ri=분할 전 attribute값 가운데 분할 후 i 영역에 속하는 속성값의 비율)

위의 항아리 예제에서 주황구슬의 비율을 x 축, 엔트로피 값을 y축으로 그래프로 그린다면 다음과 같다.

이를 수식으로 보자면, 

주황 과 파랑이 반반씩 섞여 있을때, 파랑과 주황이 반반씩 섞여 있을때, 가장큰 엔트로피 값을 가지게 된다.

 

 

---

그럼 여기서 엔트로피가 최대가 되는 지점은 알겠지만, 그러면 어떻게 다시 분류해야 하는가에서 

분류 전의 엔트로피 값과 분류 후의 엔트로피값 이 2가지를 비교하여, 제일 큰 차이를 나타내는 값을 기준으로 Decision Tree 를 분할 하겠다는 것이다.

이 차트를 보게 되었을때, 테니스 참가자들의 참가여부는 OX로 예측이 가능하고, Decision Tree 모델로 예측을 진행 할 것이다.

 

분할 전 엔트로피 계산

첫번째로 분할 전에. 참가여부에 대한 엔트로피 계산 값은.

14명 중 9명이 참가하고, 5명이 참가를 하지 않으므로, P1 = 9/14 , P2 = 5/14 로 엔트로피가 계산 가능하다.

대략 0.940 정도의 엔트로피가 나오는 수치이다.

 

분할 후 엔트로피 계산

두번째. 자 그러면 이제 분할 후 엔트로피를 계산 할 것인데,

-여기서 날씨를 기준으로 엔트로피를 분석해보자.

날씨가 흐림(Overcast), 맑음(Sunny), 비(Rain) 기준으로 나뉘므로, 여기서 S(전체 엔트로피)에서 S_sunny,S_overcast,S_rain 이 세값들을 뺴줘 전체 엔트로피 차이를 구해보자.

날씨(Outlook) 에 대한 엔트로피 계산 예시

날씨를 기준으로 엔트로피 차이를 설명했을 때,  엔트로피 차이는 0.247 만큼의 차이가 발생하였다.

 

- 그럼 이제 Temp(온도) 를 기준으로 엔트로피를 나누어 보자. S_hot ,S_mild, S_cold 세 분류로 나뉘었으므로, 세분류로 나뉘어 준다.

마찬가지로 습도, 바람에 대해서 엔트로피 차이를 구해보자.

자 그러면, 최종적으로 엔트로피의 차이는

• 날씨 기준 : 0.247
• 온도 기준 : 0.029
• 습도 기준 : 0.152
• 바람 기준 : 0.048  의 데이터 값의 차가 존재한다.

따라서 엔트로피의 차이는 날씨(Outlook) 데이터를 기준으로 분류 했을시, 가장 엔트로피의 차이가 크므로, 날씨 데이터 기준으로 , Decision Tree 모델 가지치기가 진행 되는 것이다.

 

 

 

 

 

 

 

 

 

 

출처

---

Decision Tree란? :: ID3 알고리즘, 엔트로피란? (tistory.com)

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

의사결정 나무 (Decision Tree) ID3 알고리즘 설명 - tyami’s study blog

의사결정 나무 (Decision Tree) ID3 알고리즘 설명