Decision Tree

결정 트리는 분류, 회귀 문제에 사용되는 non-parametric supervised learning method 이다. Non-parametric 은 미리 정해진 갯수의 파라미터를 가지지 않고, 학습 시 유동적으로 변한다는 것을 말한다.

결정 트리 알고리즘은 데이터를 분할하면서 규칙을 학습하는 방식으로 작동한다. 데이터의 어떤 기준을 바탕으로 규칙을 만들어야 가장 효율적인 분류인지 찾는 것이다. 결정 트리의 구조를 살펴보자.

• Internal Node (Rule Node): 분류를 위한 규칙을 만들어서 특정한 feature 에 대해 테스트 진행. Feature 이 연속값을 가진다면, threshold 를 통해 분류할 수도 있다.
• Leaf Node: label 에 대한 prediction 결과. 더 이상 분할할 수 없는 상태

Building a Decision Tree

결정 트리의 궁극적인 목표는 각 노드의 데이터를 점점 균일하게 만드는 것이다. 그리고 이를 이루는 데 최대한 간단한 모델을 사용해야 한다. 오른쪽 트리처럼 더 정확하고 간결한 트리가 좋은 모델이다. 이를 위해서 어떤 feature 에 대한 분류 규칙을 어떻게 배치해야 할까?

Information Gain

정보 이득 (Information Gain) 은 어떤 속성이 데이터를 얼마나 잘 분류하는지에 대한 지표다. 둘 중 attribute A 가 데이터를 더 잘 분류했고, IG 가 더 높다. 그러므로 IG 가 높은 속성을 트리의 상단에 배치하면 더 효율적인 구조가 될 것이다. 비슷한 지표로 Gini Coefficient 가 있다.

Entropy

IG 는 엔트로피 개념을 기반으로 한다. 엔트로피는 평균적인 정보량을 나타내는 지표로, 데이터의 불확실성을 측정한다. 이는 어떤 정보를 나타내는 데 필요한 bit 수의 기댓값으로 설명할 수 있다. 정보 표현에 필요한 bit 수가 많을수록, 그 정보를 정확하게 알기 어려워지기 때문이다. 어떤 랜덤값 x 에 대한 엔트로피는 다음과 같이 나타낼 수 있다.

$$ H(x)=-\sum^n_{i=1}p(x=i)log_2p(x=i) $$

여기서 $log_2p(x=i)$ 는 $x=i$ 일 확률을 나타내는 데 필요한 bit 수의 기대값이다.

한 마디로 정리하자면, 엔트로피가 높을수록 정보가 impure 하다는 것이다.

By choosing an attribute with the highest IG, 
the entropy of the whole tree can be minimized

Conditional Entropy

IG 는 어떤 속성으로 분류하기 전과 후의 엔트로피 차이로 계산할 수 있다. 이를 계산하기 위해서는 분류 기준 a 를 선택했을 때 데이터의 엔트로피인 Conditional Entropy 를 알아야 한다.