3. 머신러닝 알고리즘 : 의사결정 트리(Decision Tree) 알고리즘의 수학적 접근 - ID3 알고리즘

캡쳐 사진 및 글작성에 대한 도움 출저 : 유튜브 - 허민석님

Desicion Tree에서 하나의 속성을 잡고, 데이터를 split(나눌때)할 때, 가장 유명한 알고리즘은 ID3 알고리즘이다.

ID3알고리즘은 Entropy와 Information Gain이라는 2가지 컨셉을 가지고 있다.

1. 8개의 사진이 주어졌을 때, 첫번째 속성을 잡기전에 먼저, base entropy를 알아야한다.
   Entropy를 구하는 공식은 아래와 같다.
   E[+, -] =
   
   
   8개의 사진 중에서, 목적인 겨울가족사진에 해당하는 것은 1개, 아닌 것은 7개 이므로  p(+) = 1/8 , p(-) = 7/8 을 대입한다.
   
   계산 결과 base entropy는 0.543인 것이다.
   
   
2. 다음은, information Gain을 구해야한다.
   공식은, 임의의 1개의 속성을 잡았을 때, base entropy - new entropy이다.
   즉, E( 겨울가족사진 ) - E( 겨울가족사진, 카툰?) 의 계산값이다.
   
   new entropy인 E(겨울가족사진, 카툰?)을 계산하는 방법은
   1) 8개의 사진 중에 카툰사진은 4개이다. p(+) = 4/8
   2) 그 4개의 사진가운데, 겨울가족사진인 것 0개, 겨울가족사진이 아닌 것 4개 = E[0+, 4-]
   
   3) 8개의 사진 중 카툰이 아닌 사진은 4개이다. p(-) = 4/8
   4) 그 4개의 사진 가운데, 겨울가족사진인 것 1개, 겨울가족사진 아닌 것 3개 = E[1+, 4-]
   를 각각 곱해서 더한다.
   new entropy = 4/8 * E[0+,4-] + 4/8 * E[1+,4-]
   information Gain = base entropy(0.543) - new entropy( 4/8 * E[0+,4-] + 4/8 * E[1+,4-] )
   
   
   같은 방식으로, 겨울?  / 1명이상?  을 첫번째 속성(attribute)로 잡았을 때의 information Gain을 구할 수 있다.
   
   
   
   

결과적으로, Information Gain이 가장 높게 나온 카툰? 을 첫번째 속성으로 사용하게 되는 것이다.