의사결정나무

의사결정나무

의사결정나무(Decision Tree)란 나무 구조를 사용하여 의사결정 구조를 나타냅니다. 스무고개 놀이를 떠올린다면 의사결정나무의 구조를 쉽게 이해할 수 있습니다.

 

이런식으로 의사결정나무는 몇가지 질문을 통해 결과를 나누는 구조로 이루어져 있습니다.

 

엔트로피

의사결정나무는 여러 질문을 통해 결과를 나누기 때문에 어떤 질문을 어떤 순서로, 어느정도로 물을 것인지 정하는 것이 중요합니다. 가장 이상적인 질문은 예측하려는 값에 대하여 가장 많은 정보를 담고 있는 질문입니다.

 

예를 들어 Input으로 들어온 어떤 동물을 곰,고양이,뱀으로  분류하려고 할 때, '다리가 있나요?' 라는 질문의 결과를 통해 뱀을 한번에 분류할 수 있습니다. 이런 식으로 그 대상에 대해 가장 확정적인 정보로 가장 먼저 질문해야합니다.   

 

이렇게 효율적인 질문을 고르기 위해 그 질문이 얼마만큼의 정보를 담고 있는지를 나타낸 것이 엔트로피(entropy)입니다. 불확실성을 나타내기도 하는데, 모든 데이터가 한 클래스에만 속한다면, 그 데이터셋의 엔트로피는 낮다고 할 수 있습니다. 반대로 데이터셋의 모든 데이터들이 각각 다른 클래스를 가진다면 그 데이터셋의 엔트로피는 높다고 할 수 있습니다.

 

이 개념을 수학식으로 나타내어 보겠습니다.

데이터셋 내의 한 데이터가 클래스 c1에 속할 확률을 p1이라고 한다면 그 데이터셋의 엔트로피는 다음과 같이 구할 수 있습니다.

 

$H(S) = -p_{1}\log_{2}p_{1} -p_{2}\log_{2}p_{2} ... -p_{n}\log_{2}p_{n}$

 

만약 모든 데이터들이 한 클래스에만 속한다면 어떤 데이터든간에 해당 클래스에 속할 확률이 1이고 나머지 클래스에 속할 확률은 0이 됩니다. 따라서 엔트로피는 H(S) = -1log1 - 0log0 - 0log0 ... 0log0 이 되므로 H(S) = 0, 즉 매우 낮은 수치가 됩니다.

반면 클래스에 고르게 분포되어있다면 계산식의 각 항의 값이 커지므로 엔트로피는 커지게 됩니다.