의사결정나무(Decision Tree)

Decision Tree가 무엇인지는 아래 그림보면 한 번에 이해가 됨(출처)

 

일반적으로 위의 Play, Don't Play예시처럼 classification에 적합하지만, 평균값을 취하는 등의 방법을 통해 실수값을 예측하는 regression문제에도 쓸 수 있다고 한다.

 

문제는 어떻게 위의 분기문을 만들것인지 인데,

 

엔트로피 개념

여기서 엔트로피개념이 등장함

엔트로피는 보통 무질서도 또는 불확실성의 개념으로 정의하며, 고전적으로는 열역학에서 정의되고 정보이론으로 확장되었다.

정보이론에서의 엔트로피는 한 메시지에 들어갈 수 있는 정보량의 크기(비트 수)를 의미하며..또는 메시지를 평균적으로 전송하기 위해 필요한 비트수라는 표현이 더 이해하기 쉬울 수도 있겠다., 희귀한 확률을 가진 정보일수록 정보량은 커진다.

여기서 헷갈릴 수 있는 점은 엔트로피는 커지는것만 가능한데 시간이 지날수록 정보량이 점점 커진다는 개념이 이해하기에 약간 어색하다는 점이다.(시간이 지날수록 자연적으로 정보가 풍부해진다니?..하지만 이것은 정보가 풍부해진다기 보다 무작위성이 늘어나, 정보를 전달하기 위해 필요한 비트수가 늘어난다는 관점에서 보면 이해하기 편해진다. 예를 들어 단색인 이미지를 전송할때는 rgb값 하나면 충분하지만, 랜덤한 이미지를 전송하려면 그만큼 필요한 정보가 늘어남이 당연할 것이다.)

이는 순도가 높은 정보일수록 정보량이 작아 전송이 쉽고 불순한 정보가 섞일수록 정보량이 커져서 전송이 어렵다는 관점에서 생각해보면 좋다.

 

엔트로피 계산

먼저 엔트로피의 식을 이해하기 위해 여기를 보고 오자.

예를 들어, 어떤 이벤트가 반드시 발생한다면(순도가 높다) 엔트로피는 0이 된다.$E[-\log p(x)] = - \sum_x {{\log_2 p(x)}p(x)} = -({log_2 1.0})(1.0) = 0$ 

그런데 해당이벤트가 절반확률로만 발생한다면 엔트로피는 1이 된다$E[-\log p(x)] = - \sum_x {{\log_2 p(x)}p(x)} = -(({log_2 1/2})(1/2) + ({log_2 1/2})(1/2)) = 1\times 0.5 + 1 \times 0.5 = 1$

즉 무질서해짐에 따라 정보의 순도가 떨어져서 항상 같은 확률로 무언가 일어나기 보다는 무질서한 확률로 발생하게 되며, 이는 엔트로피를 높인다고 할 수 있겠다.

(이 설명이 완벽하지는 않다. 순도가 높은 경우에 비해 무작위해진 경우에 엔트로피가 높은 것 만을 설명하며, 정말 희귀한 정보가 들어갔을때 시뮬레이션을 내가 다 해본건 아니다. 여전히 의문점들은 있는 상황..예를들어 무작위한 경우보다 더 높은 엔트로피를 가진 경우가 존재하는지 궁금하다..위의 이미지 전송의 경우에 말이지)

 

엔트로피를 decision tree에 적용하기

자 이제 엔트로피의 기본 개념은 익혔다고 한다면 decision tree와의 상관관계에 대해서 알아보자.

주황색 상자안에 빨간공 10개와 파란공 6개가 있다. 무작위하게 공하나를 꺼낸다면 10/16의 확률로 빨간공이 나올 것이고 6/16의 확률로 파란공이 나올 것이다.

이를 엔트로피로 계산하면 아래처럼 된다. $$entropy = E[-\log p(x)] = - \sum_x {{\log_2 p(x)}p(x)} = (10/16)\times 0.68 + (6/16) \times 1.42 \approx 0.95$$ 

이는 위에서 예를 든 1/2확률로 갈리는 경우에 나오는 1.0 엔트로피 값보다 약간 낮고, 완전히 한쪽으로 쏠린 경우에 나오는 0.0엔트로피보다는 큰 수치임을 알 수 있다.

 

이제 주황색 상자안에서 빨간색 점선을 잘 그어서 양쪽으로 classification을 잘 했을 경우에 엔트로피가 어떻게 변화하는지 살펴보자.

위에서 빨간점선을 기준으로 양쪽에 있는 공들을 살펴보면.. 완벽하지는 않지만 대략적으로 빨간공들은 위쪽에.. 파란공들은 아래쪽에 위치하여 나름 분류를 잘 했음을 볼 수 있다.

그리고 나눠진 두 상자 기준으로 각각 엔트로피를 구해보면 순도가 높아졌으므로 좀 더 0.0에 가까워질거라는 예측을 할 수 있다.

실제로 위쪽 부분의 엔트로피를 계산해보면 다음과 같다. $$entropy = E[-\log p(x)] = - \sum_x {{\log_2 p(x)}p(x)} = (7/8)\times 0.19 + (1/8) \times 3 \approx 0.54$$

재밌는점은 파란공이란 정보는 1/8로 뽑히게 된 만큼 희귀해져서 정보량이 3.0으로 크게 증가했지만.. 발생확률은 1/8로 더크게 감소하여 기대값인  엔트로피는 오히려 0.95에서 0.54로 큰폭으로 감소했음을 볼 수 있다. 정보의 개념과 엔트로피의 개념이 서로 달라지는 재밌는 포인트이다.

 

이제 아래쪽 부분의 엔트로피를 계산해보면 다음과 같다.$$entropy = E[-\log p(x)] = - \sum_x {{\log_2 p(x)}p(x)} = (3/8)\times 1.42 + (5/8) \times 0.68 \approx 0.95$$

아래쪽 엔트로피는 원래 엔트로피에서 변동이 없음을 볼 수 있다. 

 

양쪽을 합한 엔트로피는 비율합산을 하면 되는데 위아래 공의 개수가 동일하게 8개 이므로 단순평균을 취해주면 되고 계산해보면 약 0.75의 값이 나온다.

 

즉 처음 0.95와 비교했을때 빨간 점선으로 나눈 이후의 엔트로피가 0.75가 되었으므로, 엔트로피 감소분인 0.2가 information gain(정보이득)이 되고,

무작위성 감소, 불확실성 감소, 순도 증가가 되었으며,

직관적으로 보아도, 구획을 정리해서 각 구획별 순도를 높이는 과정이므로 classification에 좋은쪽으로 구획을 나누는 과정임을 알 수 있다.

즉, 위의 예로 살펴 볼때, decisiton tree에서 총 entropy를 낮추는 방향으로 구획을 나눠주게 되면 결국은 좋은 classification model이 됨을 알 수 있다.

 

따라서, 실제 decision tree에서 분기점을 찾는 방법은..

모든 feature에 대해서 구획을 brute-force로 나눠보고 이때 생기는 entropy의 변화를 보면서 결정한다고 보면 된다.

 

decision tree의 문제점

잘 생각해보면 결국 방을 지속적으로 계속해서 나누다보면 순도100%를 달성할 수 있으며 entropy를 0으로 만드는게 trivial하게 쉽다는점을 발견할 수 있다.

하지만 이는 오버피팅이며, 이를 해결하기 위해서 너무 많은 방을 생성할 수 없도록 패널티 항을 만들어서 cost function을 설계하게 된다.

이렇게, 너무 많은 분기를 생성하지 않도록 하는 작업을 가지치기(pruning)이라고 하며, 이를 통해 오버피팅을 피하고 일반화된 성능을 기대할 수 있다.

 

또한 변수단위 설명력은 우수하지만 선형으로 나눠지는 특징때문에 비선형 데이터 분류에 취약한 문제가 있다.

이를 극복하기위해 나온게 바로 랜덤포레스트(random forest)