[머신러닝] 의사결정 나무 (Decision Tree)

안녕하세요, 이번 포스팅에서는 의사결정 나무에 대해서 배워보도록 하겠습니다.

의사결정나무는 초등학생 때 수학시간에 배웠었던거 기억하시나요?

https://ko.wikipedia.org/wiki/%EA%B2%B0%EC%A0%95_%ED%8A%B8%EB%A6%AC_%ED%95%99%EC%8A%B5%EB%B2%95

 

의사결정나무는 위와 같은 형태를 가지고 있는데, 마치 나무에 가지가 계속해서 연결되고, 가지에서 잎들이 나오는 형태와 비슷해서 이와 같은 이름으로 불려졌다고 합니다.

​

의사결정나무는 머신러닝에 대한 지식이 아무것도 없는 사람 조차도 결과를 이해하기 쉽기 때문에, 굉장히 많이 사용되는 모델입니다.

하지만 실제로, 수리적으로 어떻게 분류가 되는것인지를 파고들어가면 마냥 쉽지는 않습니다.

​

의사결정나무는 기본적으로 분류 문제에서 사용되지만, 회귀 문제에도 사용 될 수 있도록 한 CART (Classification and Regression Tree)로도 발전이 되어 있습니다.

이번 포스팅에서는 분류에서 사용 되는 분류 의사결정나무에 대해 배워보도록 하겠습니다.

​

가장 먼저 분류 의사결정나무가 학습되는 과정의 핵심을 말씀드리면, 분류에 있어서, 불순도 (불확실성)을 최소화 시키는 방향으로 학습이 진행됩니다. 불순도란 분류가 되었을 때, 실제로 오답률이 어느정도인가에 대한 지표라고 이해하시면 됩니다.

가장 많이 쓰이는 불순도의 측도로 엔트로피 (Entropy)가 있습니다.

Y에 대한 Level이 w개가 있다고 할 때, 엔트로피는 다음과 같이 계산됩니다.

이 때, pk 는 분류된 공간의 전체 대비 k의 level을 가지는 관측치의 비율입니다.

이해를 돕기 위해, 간단한 예시를 들어보도록 하겠습니다.

위과 같은 공간에서 빨간공과 파란공은 분류 할 때, 점선을 통해 분류를 한다면 Entropy의 변화가 어떻게 발생할까요?

우선, 점선으로 분류되기 전의 엔트로피를 계산해보면 다음과 같습니다. (빨간공 10개, 파란공 6개)

그리고 다음으로, 점선을 통해 2개의 공간으로 분류가 되었을 때의, 엔트로피를 구해보도록 하겠습니다.

여기서, 주의하실 점은 2개 이상의 공간에서의 엔트로피를 구하는 공식은 살짝 달라집니다.

d개의 공간이 있을 때, 엔트로피를 구하는 공식은 위와 같습니다.

이 때 Ri 는 전체 관측치 중에서 그 공간에 포함된 관측치의 비율입니다. 즉, 위의 빨간공과 파란공의 분류에서는 점선에 따른 분류로써 8개씩 포함이 되므로, 각각 R1 과 Ri 는 각각 0.5의 값을 가지게 되겠네요.

이제 다시 본격적으로 엔트로피를 구해보면 다음과 같습니다.

최종적으로, 점선에 따른 분류를 통해 엔트로피가 0.95에서 0.75로 줄어드는 것을 확인할 수 있습니다. 이를 0.2만큼의 정보 획득이 발생했다고 말하기도 합니다.

​

분류 의사결정나무는 정보 획득량 (분류하기 전의 엔트로피 - 분류 후의 엔트로피)가 최대로 하는 방향으로 학습이 진행됩니다.

​

그리고 엔트로피 말고도 많이 쓰이는 불순도 지표로 지니계수 (Gini Index)가 있습니다.

지니계수 계산법은 다음과 같습니다.

지니계수의 예제는 다루어 보지는 않겠지만, 위의 예시에 한 번 직접 계산해보시는 것을 권장하는 바입니다.

​

​

의사결정 나무에는 한 가지 문제점이 있습니다. 그것은 바로 overfitting 되기 쉽다는 것입니다.

극단적인 예시를 보여드리도록 하겠습니다.

위와 같은 상황에서 파란색 공과 노란색 공은 분류하고자 할 때, 의사 결정나무를 너무 깊게 만들면, 다음과 같이 학습이 됩니다.

물론, 정확도는 100%이지만, 과연 분류가 잘됬다고 볼 수 있을까요??

물론 아닙니다. 위와 같은 분류는 아주 심하게 학습 데이터에 과적합 되었다고 할 수 있습니다.

비록, 정확도가 100%는 아니지만 위와 같은 분류가 더 좋은 분류라고 할 수 있습니다.

이처럼 완벽하게 분류가 되는 Full Tree가 아닌 중간에 그만두는 과정을 가지치기 (Prunning)이라고 합니다.

​

일반적인 가지치기의 과정을 설명해드리자면, 우선 의사결정나무를 최대까지 성장시킵니다.

그리고 가장 아래의 가지부터 시작하여, 분류하기전과 분류후의 예측 오차를 비교합니다.

만약 분류를 한 후의 예측 오차가 더 크다면, 가지치기를 진행합니다.

​

​