README.md

• Decision Tree가 Greedy Algorithm인 이유
  • 가 주어졌을때 Speed를 예측하는 Decision Tree를 만든다고 가정한다.
  • Base Entropy
  • Grade is Steep
  • Grade is Flat

Decision Tree가 Greedy Algorithm인 이유

Grade	Bumpiness	Speed limit	Speed
Steep	Bumpy	Yes	Slow
Steep	Smooth	Yes	Slow
Flat	Bumpy	No	Fast
Steep	Smooth	No	Fast

가 주어졌을때 Speed를 예측하는 Decision Tree를 만든다고 가정한다.

Base Entropy

이때 엔트로피는

• entropy = - sum(p_i * log₂ p_i)

위 공식을 사용하여 계산하며

• p_slow = 2 / 4 = 0.5
• p_fast = 2 / 4 = 0.5
• entropy = - 0.5 * log(0.5) - 0.5 * log(0.5) = - log₂(0.5) = 1

이때 Decision Tree는 Information Gain이 최대가 되도록 가지(branch)를 생성하는데

• Information Gain = base entropy - weighted average of children entropy

여기서 base entropy는 위에서 구한 값으로 1이다.

children entropy를 구하기 위해 feature Grade 를 선택하여 Speed 를 예측한다고 가정한다.

Grade is Steep

만약 Grade 가 Steep 인 가지라면 2 slow, 1 fast 가 속하게 될 것이며,

이는

• p_slow = 2 / 3

• p_fast = 1 / 3

• entropy = - p_slow * log₂ p_slow - p_fast * log₂ p_fast = 0.9184

Grade is Flat

Grade 가 Flat 인 경우, 1 Fast만 속하게 됨

• p_slow = 0

• p_fast = 1 / 1

• entropy = 0

즉,

• weighted average entropy = 3 / 4 * 0.9184 + 1 / 4 * 0

• Information gain = 1 - 3 / 4 * 0.9184 = 0.3112

다른 피쳐에 대해서 똑갈이 반복하면

• IG_grade = 0.3112
• IG_bump = 0
• IG_limit = 1

따라서 speed limit이 가장 큰 Information Gain을 가지기 때문에 speed limit으로 가지를 나눔.

이제 IG_limit 을 베이스로 그 다음 가지를 나누어 간다.