본문

Decision Tree에서의 Entropy와 Information Gain

* Information Gain: 지정된 속성이 얼마나 잘 training example들간을 구분하는가에 대한 수치.

* Entropy: example들의 집합에서의 혼합성(impurity)을 나타냄 


S는 example의 collection, p+란 긍정적 examples, p-는 부정적 example의 확률을 가리킨다. 예를 들어, 14개의 example이 있고, 여기에 9개의 긍정적 example, 5개의 부정적 example이 있다면, 이를 Entropy([9+, 5-])으로 표기하고 계산하자면 다음과 같다. Entropy([9+, 5-])=-(9/14)log(9/14) - (5/14)log(5/14)=0.940. 만약 Entropy가 0인경우, S에 속하는 모든 example은 동일한 class에 속함을 의미하고, 만약 1인 경우에는 동일한 개수의 긍정적/부정적 example을 가진다는것을 의미한다. 


Information gain이란, 특정 속성을 기준으로 example들을 구분하게될 때, '감소되는 entropy의 양'을 의미한다. 즉, example의 collection인 S상의 속성 A의 information gain인 Gain(S,A)는 다음과 같이 정의딘다.


여기서 Values(A)는 속성 A의 모든 가능한 값의 집합을 의미하고, Sv 는 속성 A가 v값을 가질떄의 S의 부분집합을 의미한다

이때 첫번째 식은 기존의 S에서의 entropy값을 나타내는 것이고, 두번째 식은 속성 A를 사용하여 구분된 S의 entropy에 대한 기대값을 나타낸다. 두번째 식은 Sv에 속하는 example들로 표현되는 |Sv|/|S|의 가중치를 가지는 각 부분집합 Sv에 대한 entropy의 총 합이다. 따라서 Gain(S,A)는 속성 A의 값을 사용하여 나눌 생기는 entropy 감소량에 대한 기대치를 의미하는 것이다. 


예를 들어, 14일동안 운동(example)한 날짜와 각 날마다 바람의 세기(강/약)와 습도(고/저)를 측정하는(attribute, 속성) 경우를 생각해 보자. 만약 14일동안 9일은 운동을 하고 5일은 운동을 하지 않았다 한다면 [9+, 5-] 로 표기할 수 있다. 바람의 세기에 대한 측면에서, 바람이 강할경우에 6일은 운동을 하였고, 2일은 운동을 하지 않았다고 가정해보자. 바람이 약할 경우는 그 이외의 경우이므로 3일은 운동을 하고 3일은 운동을 하지 않았다고 할 수 있겠다. 이때 바람의 세기(속성)를 기준으로 information gain을 계산해본다면 다음과 같다. [수식 1]


   

[수식 1] 바람기준 Information Gain

[수식 2] 습도기준 Information Gain 


습도의 측면에서 생각해보자, 습도가 높은 경우에 3번 운동을 하고 4번 운동을 하지 않았다고 가정해보자. 그렇다면 습도가 낮은 경우에는 당연히 6번 운동을 하고 1번 운동을 하지 않았을 것이다. 이전에서 바람의 세기를 기준으로 했듯, 이번에는 습도의 고저를 기준으로 information gain을 계산한다면 다음과 같다. [수식 2] 그리고 이를 그림으로 표현하면 다음과 같다.





앞에서 Information gain이란 특정 속성을 기준으로 example들을 구분하게될 때 감소되는 entropy의 양을 의미한다고 하였다. 그리고 entropy는 example들의 집합에서의 혼합성(impurity)을 나타낸다고 하였으므로, entropy가 작아질수록 혼합성이 줄어든다. example을 구분할때 혼합성이 작을 수록 서로간의 구분이 더욱 용이해 지므로, Information gain이 커질수록 좋은것이다. 따라서 Information gain이 더 큰, '습도' 속성을 기준으로 운동여부를 구분하는 것이 더욱 효율적이다.


원문출처 : Tom Mitchell - Machine Learning : Chapter 3. Decision Tree Learning

댓글

Holic Spirit :: Tistory Edition

design by tokiidesu. powerd by kakao.