의사결정나무(Decision Tree)
26 Mar 2017 | decision tree
이번 포스팅에선 한번에 하나씩의 설명변수를 사용하여 예측 가능한 규칙들의 집합을 생성하는 알고리즘인 의사결정나무(Decision Tree)에 대해 다뤄보도록 하겠습니다. 이번 글은 고려대 강필성 교수님 강의와 김성범 교수님 강의를 참고했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
모델 소개
의사결정나무는 데이터를 분석하여 이들 사이에 존재하는 패턴을 예측 가능한 규칙들의 조합으로 나타내며, 그 모양이 ‘나무’와 같다고 해서 의사결정나무라 불립니다. 질문을 던져서 대상을 좁혀나가는 ‘스무고개’ 놀이와 비슷한 개념입니다. 한번 예를 들어볼까요?
위 예시는 운동경기가 열렸다면 PLAY=1, 그렇지 않으면 PLAY=0으로 하는 이진분류(binary classification) 문제입니다. 모든 사례를 조사해 그림으로 도시하면 위와 같은 그림이 되는 것입니다. 그림을 한번 해석해볼까요? 날씨가 맑고(sunny), 습도(humidity)가 70 이하인 날엔 경기가 열렸습니다. 해당 조건에 맞는 데이터들이 ‘경기가 열렸다(play 2건)’고 말하고 있기 때문입니다. 반대로 비가 오고(rain) 바람이 부는(windy) 날엔 경기가 열리지 않았습니다. 의사결정나무를 일반화한 그림은 아래와 같습니다.
전체적으로 보면 나무를 뒤집어놓은 것과 같은 모양입니다. 아시다시피 초기지점은 root node이고 분기가 거듭될 수록 그에 해당하는 데이터의 개수는 줄어듭니다. 각 terminal node에 속하는 데이터의 개수를 합하면 root node의 데이터수와 일치합니다. 바꿔 말하면 terminal node 간 교집합이 없다는 뜻입니다. 한편 terminal node의 개수가 분리된 집합의 개수입니다. 예컨대 위 그림처럼 terminal node가 3개라면 전체 데이터가 3개의 부분집합으로 나눠진 셈입니다.
의사결정나무는 분류(classification)와 회귀(regression) 모두 가능합니다. 범주나 연속형 수치 모두 예측할 수 있다는 말입니다. 의사결정나무의 범주예측, 즉 분류 과정은 이렇습니다. 새로운 데이터가 특정 terminal node에 속한다는 정보를 확인한 뒤 해당 terminal node에서 가장 빈도가 높은 범주에 새로운 데이터를 분류하게 됩니다. 운동경기 예시를 기준으로 말씀드리면 날씨는 맑은데 습도가 70을 넘는 날은 경기가 열리지 않을 거라고 예측합니다.
회귀의 경우 해당 terminal node의 종속변수(y)의 평균을 예측값으로 반환하게 되는데요, 이 때 예측값의 종류는 terminal node 개수와 일치합니다. 만약 terminal node 수가 3개뿐이라면 새로운 데이터가 100개, 아니 1000개가 주어진다고 해도 의사결정나무는 딱 3종류의 답만을 출력하게 될 겁니다.
그렇다면 데이터를 분할한다는 건 정확히 어떤 의미를 지니는걸까요? 설명변수(X)가 3개짜리인 다변량 데이터에 의사결정나무를 적용한다고 가정하고 아래 그림을 보시면 좋을 것 같습니다.
아무런 분기가 일어나지 않은 상태의 root node는 A입니다. 변수가 3개짜리이니 왼쪽 그래프처럼 3차원 공간에 있는 직육면체를 A라고 상정해도 좋을 것 같네요. A가 어떤 기준에 의해 B와 C로 분할됐다고 생각해 봅시다. 그렇다면 두번째 그림처럼 A가 두 개의 부분집합으로 나뉘었다고 상상해 볼 수 있겠습니다. 마지막으로 B가 D와 C로 분할됐다면, 3번째 줄의 그림처럼 될 겁니다. 이 예시에서 terminal node는 C, D, E 세 개 인데요, 이를 데이터 공간과 연관지어 생각해보면 전체 데이터 A가 세 개의 부분집합으로 분할된 것 또한 알 수 있습니다. D 특성을 갖고 있는 새로운 데이터가 주어졌을 때 의사결정나무는 D 집합을 대표할 수 있는 값(분류=최빈값, 회귀=평균)을 반환하는 방식으로 예측합니다.
불순도/불확실성
의사결정나무는 한번 분기 때마다 변수 영역을 두 개로 구분하는 모델이라고 설명을 드렸는데요, 그렇다면 대체 어떤 기준으로 영역을 나누는 걸까요? 이 글에서는 타겟변수(Y)가 범주형 변수인 분류나무를 기준으로 설명하겠습니다.
결론부터 말씀드리면 분류나무는 구분 뒤 각 영역의 순도(homogeneity)가 증가, 불순도(impurity) 혹은 불확실성(uncertainty)이 최대한 감소하도록 하는 방향으로 학습을 진행합니다. 순도가 증가/불확실성이 감소하는 걸 두고 정보이론에서는 정보획득(information gain)이라고 합니다. 이번 챕터에서는 어떤 데이터가 균일한 정도를 나타내는 지표, 즉 순도를 계산하는 3가지 방식에 대해 살펴보겠습니다. 우선 그림을 보시죠.
먼저 설명드릴 지표는 엔트로피(entropy)입니다. m개의 레코드가 속하는 A영역에 대한 엔트로피는 아래와 같은 식으로 정의됩니다. (Pk=A영역에 속하는 레코드 가운데 k 범주에 속하는 레코드의 비율)
\[Entropy(A)=-\sum _{ k=1 }^{ m }{ { p }_{ k }\log _{ 2 }{ { (p }_{ k }) } }\]
이 식을 바탕으로 오렌지색 박스로 둘러쌓인 A 영역의 엔트로피를 구해보겠습니다. 전체 16개(m=16) 가운데 빨간색 동그라미(범주=1)는 10개, 파란색(범주=2)은 6개이군요. 그럼 A 영역의 엔트로피는 다음과 같습니다.
\[Entropy(A)=-\frac { 10 }{ 16 } \log _{ 2 }{ (\frac { 10 }{ 16 } ) } -\frac { 6 }{ 16 } \log _{ 2 }{ (\frac { 6 }{ 16 } ) } \approx 0.95\]
여기서 A 영역에 빨간색 점선을 그어 두 개 부분집합(R1, R2)으로 분할한다고 가정해 봅시다. 두 개 이상 영역에 대한 엔트로피 공식은 아래 식과 같습니다. 이 공식에 의해 분할 수 A 영역의 엔트로피를 아래와 같이 각각 구할 수 있습니다. (Ri=분할 전 레코드 가운데 분할 후 i 영역에 속하는 레코드의 비율)
\[Entropy(A)=\sum _{ i=1 }^{ d }{ { R }_{ i } } \left( -\sum _{ k=1 }^{ m }{ { p }_{ k }\log _{ 2 }{ { (p }_{ k }) } } \right)\]
\[Entropy(A)=0.5\times \left( -\frac { 7 }{ 8 } \log _{ 2 }{ (\frac { 7 }{ 8 } ) } -\frac { 1 }{ 8 } \log _{ 2 }{ (\frac { 1 }{ 8 } ) } \right) +0.5\times \left( -\frac { 3 }{ 8 } \log _{ 2 }{ (\frac { 3 }{ 8 } ) } -\frac { 5 }{ 8 } \log _{ 2 }{ (\frac { 5 }{ 8 } ) } \right) \approx 0.75\]
그럼 분기 전과 분기 후의 엔트로피가 어떻게 변화했는지 볼까요? 분기 전 엔트로피가 0.95였는데 분할한 뒤에 0.75가 됐군요. 0.2만큼 엔트로피 감소(=불확실성 감소=순도 증가=정보획득)한 걸로 봐서 의사결정나무 모델은 분할한 것이 분할 전보다 낫다는 판단 하에 데이터를 두 개의 부분집합으로 나누게 됩니다. 다시 한번 말씀드리지만 의사결정나무는 구분 뒤 각 영역의 순도(homogeneity)가 증가/불확실성(엔트로피)가 최대한 감소하도록 하는 방향으로 학습을 진행합니다.
순도와 관련해 부연설명을 드리면 A 영역에 속한 모든 레코드가 동일한 범주에 속할 경우(=불확실성 최소=순도 최대) 엔트로피는 0입니다. 반대로 범주가 둘뿐이고 해당 개체의 수가 동일하게 반반씩 섞여 있을 경우(=불확실성 최대=순도 최소) 엔트로피는 1의 값을 갖습니다. 엔트로피 외에 불순도 지표로 많이 쓰이는 지니계수(Gini Index) 공식은 아래와 같습니다.
\[G.I(A)=\sum _{ i=1 }^{ d }{ { \left( { R }_{ i }\left( 1-\sum _{ k=1 }^{ m }{ { p }_{ ik }^{ 2 } } \right) \right) } }\]
아래는 범주가 두 개일 때 한쪽 범주에 속한 비율(p)에 따른 불순도의 변화량을 그래프로 나타낸 것입니다. 보시다시피 그 비율이 0.5(두 범주가 각각 반반씩 섞여 있는 경우)일 때 불순도가 최대임을 알 수가 있습니다. 오분류오차(misclassification error)는 따로 설명드리지 않은 지표인데요, 오분류오차는 엔트로피나 지니계수와 더불어 불순도를 측정할 수 있긴 하나 나머지 두 지표와 달리 미분이 불가능한 점 때문에 자주 쓰이지는 않는다고 합니다.
모델 학습
의사결정나무의 학습 과정은 입력 변수 영역을 두 개로 구분하는 재귀적 분기(recursive partitioning)와 너무 자세하게 구분된 영역을 통합하는 가지치기(pruning) 두 가지 과정으로 나뉩니다. 우선 재귀적 분기 먼저 살펴보겠습니다.
재귀적 분기
아래와 같이 24개 가정을 대상으로 소득(income), 주택크기(Lot size), 잔디깎기 기계 구입 여부(Ownership)를 조사한 데이터가 있습니다. 이를 토대로 소득과 주택크기를 설명변수(X), 기계 구입 여부를 종속변수(Y)로 하는 분류나무 모델을 학습시켜 보겠습니다.
우선 이를 한 변수 기준(예컨대 주택 크기)으로 정렬합니다. 이후 가능한 모든 분기점에 대해 엔트로피/지니계수를 구해 분기 전과 비교해 정보획득을 조사합니다. 예컨대 아래 표 기준으로 보시면 분기지점을 첫 레코드와 나머지 23개 레코드로 두고, 1번 레코드와 2~24번 레코드 간의 엔트로피를 구한 뒤 이를 분기 전 엔트로피와 비교해 정보획득을 조사합니다. 그 결과는 아래와 같습니다.
\[\begin {align*}
분기\quad전\quad 엔트로피&=-\frac { 1 }{ 2 } \log _{ 2 }{ (\frac { 1 }{ 2 } ) } -\frac { 1 }{ 2 } \log _{ 2 }{ (\frac { 1 }{ 2 } ) } =1\\분기\quad후\quad엔트로피 &=\frac { 1 }{ 24 } \left( -\log _{ 2 }{ 1 } \right) +\frac { 23 }{ 24 } \left( -\frac { 12 }{ 23 } \log _{ 2 }{ (\frac { 12 }{ 23 } ) } -\frac { 11 }{ 23 } \log _{ 2 }{ (\frac { 11 }{ 23 } ) } \right) \approx 0.96\\ 정보획득&=1-0.96=0.04
\end{align*}\]
이후 분기 지점을 두번째 레코드로 두고 처음 두 개 레코드와 나머지 22개 레코드 간의 엔트로피를 계산한 뒤 정보획득을 알아봅니다. 이렇게 순차적으로 계산한 뒤, 이번엔 다른 변수인 소득을 기준으로 정렬하고 다시 같은 작업을 반복합니다. 모든 경우의 수 가운데 정보획득이 가장 큰 변수와 그 지점을 택해 첫번째 분기를 하게 됩니다. 이후 또 같은 작업을 반복해 두번째, 세번째… 이렇게 분기를 계속 해 나가는 과정이 바로 의사결정나무의 학습입니다.
그렇다면 1회 분기를 위해 계산해야 하는 경우의 수는 총 몇 번일까요? 개체가 $n$개, 변수가 $d$개라고 할 때 경우의 수는 $d(n-1)$개가 됩니다. 분기를 하지 않는 경우를 제외하고 모든 개체와 변수를 고려해 보는 것입니다.
가지치기
의사결정나무 모델 학습의 또다른 축은 가지치기(pruning)입니다. 모든 terminal node의 순도가 100%인 상태를 Full tree라고 하는데요. 이렇게 Full tree를 생성한 뒤 적절한 수준에서 terminal node를 결합해주어야 합니다. 왜냐하면 분기가 너무 많아서 학습데이터에 과적합(overfitting)할 염려가 생기기 때문입니다.
의사결정나무의 분기 수가 증가할 때 처음에는 새로운 데이터에 대한 오분류율이 감소하나 일정 수준 이상이 되면 오분류율이 되레 증가하는 현상이 발생한다고 합니다. 이러한 문제를 해결하기 위해서는 검증데이터에 대한 오분류율이 증가하는 시점에서 적절히 가지치기를 수행해줘야 합니다.
마치 나뭇가지를 잘라내는 것과 같다는 의미에서 이러한 용어가 붙었습니다. 매우 직관적이죠. 가지치기 개념도는 아래와 같습니다. 다만 가지치기는 데이터를 버리는 개념이 아니고 분기를 합치는(merge) 개념으로 이해해야 합니다.
재귀적 분기를 설명해 드릴 때 들었던 잔디깎기 기계 구입 여부 데이터를 의사결정나무로 학습한 결과물입니다. 왼쪽이 Full tree, 오른쪽이 가지치기를 한 결과를 시각화한 것입니다. 왼쪽 그림을 보시면 모든 terminal node의 불순도는 0임을 확인할 수 있습니다.
하지만 terminal node가 너무 많으면 새로운 데이터에 대한 예측 성능인 일반화(generalization) 능력이 매우 떨어질 염려가 있습니다. terminal node를 적절하게 합쳐주면 오른쪽 그림과 같은 결과가 나오는 걸 확인할 수 있습니다.
마지막으로 가지치기의 비용함수(cost function)를 살펴보겠습니다. 의사결정나무는 이 비용함수를 최소로 하는 분기를 찾아내도록 학습됩니다. 아래와 같이 정의됩니다.
\[CC(T)=Err(T)+\alpha \times L(T)\]
CC(T)=의사결정나무의 비용 복잡도(=오류가 적으면서 terminal node 수가 적은 단순한 모델일 수록 작은 값)
ERR(T)=검증데이터에 대한 오분류율
L(T)=terminal node의 수(구조의 복잡도)
Alpha=ERR(T)와 L(T)를 결합하는 가중치(사용자에 의해 부여됨, 보통 0.01~0.1의 값을 씀)
마치며
이상으로 의사결정나무에 대해 살펴보았습니다. 의사결정나무는 계산복잡성 대비 높은 예측 성능을 내는 것으로 정평이 나 있습니다. 아울러 변수 단위로 설명력을 지닌다는 강점을 가지고 있습니다. 다만 의사결정나무는 결정경계(decision boundary)가 데이터 축에 수직이어서 특정 데이터에만 잘 작동할 가능성이 높습니다.
이같은 문제를 극복하기 위해 등장한 모델이 바로 랜덤포레스트인데요, 같은 데이터에 대해 의사결정나무를 여러 개 만들어 그 결과를 종합해 예측 성능을 높이는 기법입니다.
의사결정나무든 랜덤포레스트는 R이나 Python 등 주요 언어에서 모두 패키지 형태로 쉽고 간편하게 사용을 할 수가 있으니 한번쯤은 실험을 해보시면 좋을 것 같습니다. 질문이나 의견 있으시면 이메일이나 댓글로 부탁드립니다. 여기까지 읽어주셔서 감사드립니다.
이번 포스팅에선 한번에 하나씩의 설명변수를 사용하여 예측 가능한 규칙들의 집합을 생성하는 알고리즘인 의사결정나무(Decision Tree)에 대해 다뤄보도록 하겠습니다. 이번 글은 고려대 강필성 교수님 강의와 김성범 교수님 강의를 참고했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
모델 소개
의사결정나무는 데이터를 분석하여 이들 사이에 존재하는 패턴을 예측 가능한 규칙들의 조합으로 나타내며, 그 모양이 ‘나무’와 같다고 해서 의사결정나무라 불립니다. 질문을 던져서 대상을 좁혀나가는 ‘스무고개’ 놀이와 비슷한 개념입니다. 한번 예를 들어볼까요?
위 예시는 운동경기가 열렸다면 PLAY=1, 그렇지 않으면 PLAY=0으로 하는 이진분류(binary classification) 문제입니다. 모든 사례를 조사해 그림으로 도시하면 위와 같은 그림이 되는 것입니다. 그림을 한번 해석해볼까요? 날씨가 맑고(sunny), 습도(humidity)가 70 이하인 날엔 경기가 열렸습니다. 해당 조건에 맞는 데이터들이 ‘경기가 열렸다(play 2건)’고 말하고 있기 때문입니다. 반대로 비가 오고(rain) 바람이 부는(windy) 날엔 경기가 열리지 않았습니다. 의사결정나무를 일반화한 그림은 아래와 같습니다.
전체적으로 보면 나무를 뒤집어놓은 것과 같은 모양입니다. 아시다시피 초기지점은 root node이고 분기가 거듭될 수록 그에 해당하는 데이터의 개수는 줄어듭니다. 각 terminal node에 속하는 데이터의 개수를 합하면 root node의 데이터수와 일치합니다. 바꿔 말하면 terminal node 간 교집합이 없다는 뜻입니다. 한편 terminal node의 개수가 분리된 집합의 개수입니다. 예컨대 위 그림처럼 terminal node가 3개라면 전체 데이터가 3개의 부분집합으로 나눠진 셈입니다.
의사결정나무는 분류(classification)와 회귀(regression) 모두 가능합니다. 범주나 연속형 수치 모두 예측할 수 있다는 말입니다. 의사결정나무의 범주예측, 즉 분류 과정은 이렇습니다. 새로운 데이터가 특정 terminal node에 속한다는 정보를 확인한 뒤 해당 terminal node에서 가장 빈도가 높은 범주에 새로운 데이터를 분류하게 됩니다. 운동경기 예시를 기준으로 말씀드리면 날씨는 맑은데 습도가 70을 넘는 날은 경기가 열리지 않을 거라고 예측합니다.
회귀의 경우 해당 terminal node의 종속변수(y)의 평균을 예측값으로 반환하게 되는데요, 이 때 예측값의 종류는 terminal node 개수와 일치합니다. 만약 terminal node 수가 3개뿐이라면 새로운 데이터가 100개, 아니 1000개가 주어진다고 해도 의사결정나무는 딱 3종류의 답만을 출력하게 될 겁니다.
그렇다면 데이터를 분할한다는 건 정확히 어떤 의미를 지니는걸까요? 설명변수(X)가 3개짜리인 다변량 데이터에 의사결정나무를 적용한다고 가정하고 아래 그림을 보시면 좋을 것 같습니다.
아무런 분기가 일어나지 않은 상태의 root node는 A입니다. 변수가 3개짜리이니 왼쪽 그래프처럼 3차원 공간에 있는 직육면체를 A라고 상정해도 좋을 것 같네요. A가 어떤 기준에 의해 B와 C로 분할됐다고 생각해 봅시다. 그렇다면 두번째 그림처럼 A가 두 개의 부분집합으로 나뉘었다고 상상해 볼 수 있겠습니다. 마지막으로 B가 D와 C로 분할됐다면, 3번째 줄의 그림처럼 될 겁니다. 이 예시에서 terminal node는 C, D, E 세 개 인데요, 이를 데이터 공간과 연관지어 생각해보면 전체 데이터 A가 세 개의 부분집합으로 분할된 것 또한 알 수 있습니다. D 특성을 갖고 있는 새로운 데이터가 주어졌을 때 의사결정나무는 D 집합을 대표할 수 있는 값(분류=최빈값, 회귀=평균)을 반환하는 방식으로 예측합니다.
불순도/불확실성
의사결정나무는 한번 분기 때마다 변수 영역을 두 개로 구분하는 모델이라고 설명을 드렸는데요, 그렇다면 대체 어떤 기준으로 영역을 나누는 걸까요? 이 글에서는 타겟변수(Y)가 범주형 변수인 분류나무를 기준으로 설명하겠습니다.
결론부터 말씀드리면 분류나무는 구분 뒤 각 영역의 순도(homogeneity)가 증가, 불순도(impurity) 혹은 불확실성(uncertainty)이 최대한 감소하도록 하는 방향으로 학습을 진행합니다. 순도가 증가/불확실성이 감소하는 걸 두고 정보이론에서는 정보획득(information gain)이라고 합니다. 이번 챕터에서는 어떤 데이터가 균일한 정도를 나타내는 지표, 즉 순도를 계산하는 3가지 방식에 대해 살펴보겠습니다. 우선 그림을 보시죠.
먼저 설명드릴 지표는 엔트로피(entropy)입니다. m개의 레코드가 속하는 A영역에 대한 엔트로피는 아래와 같은 식으로 정의됩니다. (Pk=A영역에 속하는 레코드 가운데 k 범주에 속하는 레코드의 비율)
\[Entropy(A)=-\sum _{ k=1 }^{ m }{ { p }_{ k }\log _{ 2 }{ { (p }_{ k }) } }\]이 식을 바탕으로 오렌지색 박스로 둘러쌓인 A 영역의 엔트로피를 구해보겠습니다. 전체 16개(m=16) 가운데 빨간색 동그라미(범주=1)는 10개, 파란색(범주=2)은 6개이군요. 그럼 A 영역의 엔트로피는 다음과 같습니다.
\[Entropy(A)=-\frac { 10 }{ 16 } \log _{ 2 }{ (\frac { 10 }{ 16 } ) } -\frac { 6 }{ 16 } \log _{ 2 }{ (\frac { 6 }{ 16 } ) } \approx 0.95\]여기서 A 영역에 빨간색 점선을 그어 두 개 부분집합(R1, R2)으로 분할한다고 가정해 봅시다. 두 개 이상 영역에 대한 엔트로피 공식은 아래 식과 같습니다. 이 공식에 의해 분할 수 A 영역의 엔트로피를 아래와 같이 각각 구할 수 있습니다. (Ri=분할 전 레코드 가운데 분할 후 i 영역에 속하는 레코드의 비율)
\[Entropy(A)=\sum _{ i=1 }^{ d }{ { R }_{ i } } \left( -\sum _{ k=1 }^{ m }{ { p }_{ k }\log _{ 2 }{ { (p }_{ k }) } } \right)\] \[Entropy(A)=0.5\times \left( -\frac { 7 }{ 8 } \log _{ 2 }{ (\frac { 7 }{ 8 } ) } -\frac { 1 }{ 8 } \log _{ 2 }{ (\frac { 1 }{ 8 } ) } \right) +0.5\times \left( -\frac { 3 }{ 8 } \log _{ 2 }{ (\frac { 3 }{ 8 } ) } -\frac { 5 }{ 8 } \log _{ 2 }{ (\frac { 5 }{ 8 } ) } \right) \approx 0.75\]그럼 분기 전과 분기 후의 엔트로피가 어떻게 변화했는지 볼까요? 분기 전 엔트로피가 0.95였는데 분할한 뒤에 0.75가 됐군요. 0.2만큼 엔트로피 감소(=불확실성 감소=순도 증가=정보획득)한 걸로 봐서 의사결정나무 모델은 분할한 것이 분할 전보다 낫다는 판단 하에 데이터를 두 개의 부분집합으로 나누게 됩니다. 다시 한번 말씀드리지만 의사결정나무는 구분 뒤 각 영역의 순도(homogeneity)가 증가/불확실성(엔트로피)가 최대한 감소하도록 하는 방향으로 학습을 진행합니다.
순도와 관련해 부연설명을 드리면 A 영역에 속한 모든 레코드가 동일한 범주에 속할 경우(=불확실성 최소=순도 최대) 엔트로피는 0입니다. 반대로 범주가 둘뿐이고 해당 개체의 수가 동일하게 반반씩 섞여 있을 경우(=불확실성 최대=순도 최소) 엔트로피는 1의 값을 갖습니다. 엔트로피 외에 불순도 지표로 많이 쓰이는 지니계수(Gini Index) 공식은 아래와 같습니다.
\[G.I(A)=\sum _{ i=1 }^{ d }{ { \left( { R }_{ i }\left( 1-\sum _{ k=1 }^{ m }{ { p }_{ ik }^{ 2 } } \right) \right) } }\]아래는 범주가 두 개일 때 한쪽 범주에 속한 비율(p)에 따른 불순도의 변화량을 그래프로 나타낸 것입니다. 보시다시피 그 비율이 0.5(두 범주가 각각 반반씩 섞여 있는 경우)일 때 불순도가 최대임을 알 수가 있습니다. 오분류오차(misclassification error)는 따로 설명드리지 않은 지표인데요, 오분류오차는 엔트로피나 지니계수와 더불어 불순도를 측정할 수 있긴 하나 나머지 두 지표와 달리 미분이 불가능한 점 때문에 자주 쓰이지는 않는다고 합니다.
모델 학습
의사결정나무의 학습 과정은 입력 변수 영역을 두 개로 구분하는 재귀적 분기(recursive partitioning)와 너무 자세하게 구분된 영역을 통합하는 가지치기(pruning) 두 가지 과정으로 나뉩니다. 우선 재귀적 분기 먼저 살펴보겠습니다.
재귀적 분기
아래와 같이 24개 가정을 대상으로 소득(income), 주택크기(Lot size), 잔디깎기 기계 구입 여부(Ownership)를 조사한 데이터가 있습니다. 이를 토대로 소득과 주택크기를 설명변수(X), 기계 구입 여부를 종속변수(Y)로 하는 분류나무 모델을 학습시켜 보겠습니다.
우선 이를 한 변수 기준(예컨대 주택 크기)으로 정렬합니다. 이후 가능한 모든 분기점에 대해 엔트로피/지니계수를 구해 분기 전과 비교해 정보획득을 조사합니다. 예컨대 아래 표 기준으로 보시면 분기지점을 첫 레코드와 나머지 23개 레코드로 두고, 1번 레코드와 2~24번 레코드 간의 엔트로피를 구한 뒤 이를 분기 전 엔트로피와 비교해 정보획득을 조사합니다. 그 결과는 아래와 같습니다.
이후 분기 지점을 두번째 레코드로 두고 처음 두 개 레코드와 나머지 22개 레코드 간의 엔트로피를 계산한 뒤 정보획득을 알아봅니다. 이렇게 순차적으로 계산한 뒤, 이번엔 다른 변수인 소득을 기준으로 정렬하고 다시 같은 작업을 반복합니다. 모든 경우의 수 가운데 정보획득이 가장 큰 변수와 그 지점을 택해 첫번째 분기를 하게 됩니다. 이후 또 같은 작업을 반복해 두번째, 세번째… 이렇게 분기를 계속 해 나가는 과정이 바로 의사결정나무의 학습입니다.
그렇다면 1회 분기를 위해 계산해야 하는 경우의 수는 총 몇 번일까요? 개체가 $n$개, 변수가 $d$개라고 할 때 경우의 수는 $d(n-1)$개가 됩니다. 분기를 하지 않는 경우를 제외하고 모든 개체와 변수를 고려해 보는 것입니다.
가지치기
의사결정나무 모델 학습의 또다른 축은 가지치기(pruning)입니다. 모든 terminal node의 순도가 100%인 상태를 Full tree라고 하는데요. 이렇게 Full tree를 생성한 뒤 적절한 수준에서 terminal node를 결합해주어야 합니다. 왜냐하면 분기가 너무 많아서 학습데이터에 과적합(overfitting)할 염려가 생기기 때문입니다.
의사결정나무의 분기 수가 증가할 때 처음에는 새로운 데이터에 대한 오분류율이 감소하나 일정 수준 이상이 되면 오분류율이 되레 증가하는 현상이 발생한다고 합니다. 이러한 문제를 해결하기 위해서는 검증데이터에 대한 오분류율이 증가하는 시점에서 적절히 가지치기를 수행해줘야 합니다.
마치 나뭇가지를 잘라내는 것과 같다는 의미에서 이러한 용어가 붙었습니다. 매우 직관적이죠. 가지치기 개념도는 아래와 같습니다. 다만 가지치기는 데이터를 버리는 개념이 아니고 분기를 합치는(merge) 개념으로 이해해야 합니다.
재귀적 분기를 설명해 드릴 때 들었던 잔디깎기 기계 구입 여부 데이터를 의사결정나무로 학습한 결과물입니다. 왼쪽이 Full tree, 오른쪽이 가지치기를 한 결과를 시각화한 것입니다. 왼쪽 그림을 보시면 모든 terminal node의 불순도는 0임을 확인할 수 있습니다.
하지만 terminal node가 너무 많으면 새로운 데이터에 대한 예측 성능인 일반화(generalization) 능력이 매우 떨어질 염려가 있습니다. terminal node를 적절하게 합쳐주면 오른쪽 그림과 같은 결과가 나오는 걸 확인할 수 있습니다.
마지막으로 가지치기의 비용함수(cost function)를 살펴보겠습니다. 의사결정나무는 이 비용함수를 최소로 하는 분기를 찾아내도록 학습됩니다. 아래와 같이 정의됩니다.
\[CC(T)=Err(T)+\alpha \times L(T)\]CC(T)=의사결정나무의 비용 복잡도(=오류가 적으면서 terminal node 수가 적은 단순한 모델일 수록 작은 값)
ERR(T)=검증데이터에 대한 오분류율
L(T)=terminal node의 수(구조의 복잡도)
Alpha=ERR(T)와 L(T)를 결합하는 가중치(사용자에 의해 부여됨, 보통 0.01~0.1의 값을 씀)
마치며
이상으로 의사결정나무에 대해 살펴보았습니다. 의사결정나무는 계산복잡성 대비 높은 예측 성능을 내는 것으로 정평이 나 있습니다. 아울러 변수 단위로 설명력을 지닌다는 강점을 가지고 있습니다. 다만 의사결정나무는 결정경계(decision boundary)가 데이터 축에 수직이어서 특정 데이터에만 잘 작동할 가능성이 높습니다.
이같은 문제를 극복하기 위해 등장한 모델이 바로 랜덤포레스트인데요, 같은 데이터에 대해 의사결정나무를 여러 개 만들어 그 결과를 종합해 예측 성능을 높이는 기법입니다.
의사결정나무든 랜덤포레스트는 R이나 Python 등 주요 언어에서 모두 패키지 형태로 쉽고 간편하게 사용을 할 수가 있으니 한번쯤은 실험을 해보시면 좋을 것 같습니다. 질문이나 의견 있으시면 이메일이나 댓글로 부탁드립니다. 여기까지 읽어주셔서 감사드립니다.
Comments