2.4. Entropy and Information Gain

Etropy:

Decision tree를 만들기 위해 entropy를 이해해야 한다.

entropy : 어떤 attribute를 더 잘 check 할 수 있는지 알려주는 하나의 지표

 

불확실성을 줄여야하는데, 그렇기 위해선 이 불확실성을 판단할 수 있어야 한다.

>> 불확실성을 판단하는 것이 entropy

모든 케이스에 대해서 비슷한 확률분포가 존재하면 불확실성이 큰 것이고, 케이스에 대해서 dominant한 확률을 가지고 있다면 그 불확실성은 매우 적다.

 

높은 엔트로피 = 높은 불확실성

 

엔트로피 H(x)는 확률 밀도함수를 활용하고 있다. x는 T or F 또는 a or b or ? 등이 나올 수 있다.

만약 x가 normal distribution에서 정의되고 있다면 sigma는 integral로 변환된다.

 

이 때 특정 정보에 대한 엔트로피는(in given x, entropy of y is)(conditional entropy)

Y의 불확실성을 측정하는데 있어 X의 특성을 반영하는 것이다.(weigh x)

 

Information Gain:

아무것도 적용하지 않았을 때 307개의 positive, 383개의 negative가 있다면 이 때의 엔트로피는 다음과 같다.

A1을 condition으로 할 때의 Y의 엔트로피는(conditional entropy)는 다음과 같다.

이 때, Y에 대해서 어떤 attribute를 줬을 때 얼만큼의 레벨이 변경되는가는 다음과 같다.

이를 Information Gain이라 한다.

 

Top-Down Induction Algorithm:

모든 attribute에 대해서 IG를 구하면 어떤 attribute를 썼을 때 가장 효과적인지 구할 수 있다.

IG가 가장 높은 것을 기준으로 트리의 루트를 만든다. 분리된 케이스에 대해서 entropy를 구해서 A1 또는 A3를 쓸지 결정할 수 있다.

 

decision tree를 더 크게 만들면 우리가 파악가능한 케이스에 대해서 neagative한 케이스를 제거할 수 있다.

 

Problem of Desicion Tree:

하지만 현실은 다르다. 

현실은 항상 error와 inconstistency가 존재하기 때문에 지금 있는 데이터는 100% 정확하더라도 앞으로의 데이터가 100%이라고 볼 수 없다.

 

트리가 커질수록 error가 많아지고 accuracy가 떨어진다.

>> 어느정도 작동하는 decision tree에서, decision tree를 늘리면 앞으로의 데이터에서 정확도가 떨어진다.