Decision tree

의사결정나무는 데이터패턴을 파악하는 과정에서 하나의 질문(노드)에서 여러 결정가지가 생성된 모습이 나무와 같다고 해서 붙여진 이름입니다.  가지를 내리는 과정이 마치 스무고개를 하는 것 같은데 예시는 이렇습니다. 

 

decision tree 예시

 

가장 위에 있는 질문은 root node, 중간에 있는 것들은 intermediate node, 마지막은 terminate node라고 합니다. 

decision tree는 linear classification에서도 사용될수 있지만 그렇지 않은 경우에서도 사용될 수 있습니다. 

 

decision tree는 변수가 numerical이던, categorical이던 상관하지 않고 normalization을 따로 해주지 않아도 학습을 하고 

학습과정이 보이지 않는 모델이 아닌 open box model입니다. 

decision tree 모델은 순도(homogeneity)가 높은 방향으로 혹은 불순도(impurity)나 불확실도(uncertainty)가 낮은 방향으로 학습하는데 이때 쓰이는 개념이 entropy입니다.

 

Entropy는 0~1사이의 값을 갖는데 0.5일 경우 가장 entropy가 높고 0에 가까울수록 불순도가 낮고 1에 가까울수록 불순도가 높습니다. 

아래 예시에서 A의 경우 파란공이 2개뿐이라 불순도가 낮다고 할 수 있으며 B는 모두 파란색이라 굳이 구분하지 않아도 되는 불순도가 0이라고 말할 수 있습니다. 마지막으로 1:1비율로 빨강과 파랑을 가진 C는 A에 비해서 불순도가 높다고 할 수 있습니다. 

 

불순한 상태가 높아 분류하기 어려운 상황에서 entropy는 높아지고 불순한 상태가 낮을수록 entropy가 낮습니다.

불순도와 entropy는 비례관계입니다. 

 

정보획득량(information gain)은 분활전 entropy - 분활후 entropy입니다. 따라서, 정보획득량이 클수록 불순도가 줄어드는 것을 의미하며 information gain이 큰 속성을 기준을 삼아 의사결정나무가 분활하게 됩니다.

노드들의 entropy 합을 최소화하고 정보획득량을 최대화하는 속성순서대로 배치하는것이 좋습니다.