ID3나 CART 등의 의사결정트리를 상세히 알기 위해서는 정보, 불순도, 엔트로피, 지니지수 등의 개념을 이해하여야 한다. 예제를 통해 찬찬히 알아보도록 하자.
정보와 불순도
정보($H$)란 쉽게 표현하여 어떤 내용을 표현하기 위해 물어야하는 기대 질문 수를 의미하며, 불순도(Impurity)는 자료 중 동일 범주의 비율을 의미하는 순도(purity)의 반댓말로 여러 범주가 서로 섞여있는 정도를 의미한다. 이 개념을 기억하고 아래의 예제와 설명을 파악해보도록 하자.
불확실성의 정도를 나타내는 지표
Entropy 설명
예를들어 5개의 동전의 앞/뒷면을 최소 질문 수로 맞추는 게임을 한다고 하자(질문의 답변은 Yes/No로 할 수 있다). 이 질문의 답은 동전의 앞/뒷면을 물으면 바로 답을 알 수 있으므로, 이를 수식으로 나타내면 $2^5=32$와 같다.
이번엔 5자리 알파벳 맞추는 최소 질문 수로 맞추는 게임을 한다고 하자. 이 때 우리는 알파벳이 앞쪽 절반에 해당하는지를 묻는다면 가장 효율적일 것이다. 이로써 알파벳 하나를 최대 5번의 질문으로 분류할 수 있다.
알파벳 하나를 맞추는 최소 질문수를 먼저 풀어보자. 이를 수식으로 나타내면 $2^{질문 수} = 26$이라 나타낼 수 있다. 따라서 $질문수=log_2 26$으로 표현할 수 있다. $log_2 26\approx 4.7$이다.
5자리 알파벳을 맞추는 최소질문수는 $2^{질문수}=26^5$이므로 $질문수=log_2 26^5=5 log_2 26 \approx 5 \times 4.7 = 23.5$이다.
여기서 계산한 질문수를 정보라고 하며 정보($H$)는 아래와 같이 나타낼 수 있다.
$$ 질문 수 = 반복시행수 \times log_2 {가능한 결과 수} \\ H=n log_2(s)$$
앞선 문제에서는 발생확률이 동일하였다. 이제 발생확률이 동일하지 않은 경우를 생각해보자. 이 경우 가장 효율적인 질문 방법은 발생 확률이 높은 순으로 질문을 하는 것일 것이다.
이번엔 A, B, C, D를 맞추는 문제에서 A는 50% B와 C는 12.5% D는 25% 확률로 나타난다고 하자. A의 확률이 50%이므로 A가 맞는지에 대해 질문하는 것이 가장 효율적일 것이다. 또한 그 다음으로 D인지 아닌지를 질문하고, B(혹은 C)가 맞는지 질문하는 것이 효율적일 것이다.
$$0.5 \times 1 + 0.125 \times 3 + 0.125 \times 3 + 0.25 = \\ \sum 발생확률 * 질문수=1.75=평균적인 질문 수$$
$$ H = \sum 사건발생확률 \log_2 {1 \over {사건발생확률}} $$
$$H = \sum\limits_i p_i log_2 {1\over {p_i}} $$
$$ H= - \sum\limits_i p_i log_2 p_i$$
정보량은 어떤 내용을 표현하기 위해 물어야하는 기대 질문 수이므로 정보량이 낮다는 것은(적은 정보량을 생산한다는 것은) 불확실성이 적다는 것을 의미한다. 적은 정보량으로 문제를 해결 할 수 있다는 것은 불확실성이 낮다는 것이라 할 수 있다.
엔트로피의 log의 밑이 2인경우 bit의 단위를 사용하며 샤넌앤트로피라 부른다.
gini 설명
엔트로피와 마찬가지로 불순도를 측정하는 지표로 분산전도를 정량화하여 표현한 값을 의미한다. 이를 수식으로 나타내면 다음과 같다.
$$ G(S)=1- \sum\limits_{i=1}^{c} p_i ^2 $$
참고문헌
Blog Logo
원문 [C.E. Shannon, A Mathematical Theory of Communication, 1948]
