의사결정나무는 스무고개 놀이와 비슷한 알고리즘이라 할 수 있다. 내가 생각한 인물을 맞춰내는 아키네이터 게임과 유사한 방식으로 알고리즘이 작동한다. 아래 그림은 유명한 타이타닉 데이터의 Y값인 생존여부를 맞추는 과정이며, 의사결정나무는 위와 같이 Y/N 형식의 대답이 나올 수 밖에 없는 알고리즘을 학습을 진행하게 된다. 그 결과 우리는 개인이 타이타닉호에서 생존했는지 사망했는지를 예측하는 값을 결정지을 수 있게 된다. 의사결정나무는 그림과 같이 간단하고 직관적인 결과 표현이 가능하고 인간의 의사결정 과정과도 유사하다.

DT

따라서 의사결정나무를 학습한다는 것은 정답에 가장 빨리 도달하는 Y/N질문을 학습하는 것이라 말할 수 있을 것이며, 궁극적으로 우리는 데이터를 가장 잘 분류하는 의사결정나무 모형을 만들고자 한다.

타깃변수(Y)의 형태에 따라 의사결정나무는 2가지 종류로 나뉜다. 위처럼 Y가 범주형일 때, 의사결정나무는 분류를 위한 Classification Tree로 불린다. 그러나 Y가 연속형일 때, 의사결정나무는 Regression Tree로 불린다. 그런데 보통 의사결정나무는 Y가 범주형인 상황에서 자주 사용되므로 Classification Tree의 경우에 포커스를 맞추고자 한다.

용어 정의

의사결정나무를 이해하기 위해 의사결정나무에서 빈번히 사용되는 용어들에 대해 먼저 정리하도록 하자.

위의 그림에서 각각의 질문은 노드(node)라고 불린다. 그 중에서도 첫번째 노드는 뿌리 노드(Root Node)라고 불린다. 데이터를 분류하는 과정에서 가장 먼저 사용되는 질문인 것으로 가장 효율적인 Y/N 질문이 여기 배치될 것이다. 그 다음 나무의 가지가 쳐지는 과정을 분기(Splitting)이라 한다. 분기를 통해 생성된 하위 노드를 자식 노드(Child Node)라고 부르며, 분기가 이루어진 상위 노드를 부모 노드(Parent Node)라 한다.

분기라는 것은 즉, 노드 1개를 2개 혹은 그 이상의 서브 노드(Sub Node)로 나누는 과정이다. (이후의 과정에서는 분기할 때는 2개의 서브 노드로 나뉘는 것만 생각하자) 따라서 분기를 진행하면 각 노드에 속한 데이터의 수는 줄어들 것이다.

분기를 여러번 거치면, 최종 단계의 노드가 발생하게 된다. 이 노드를 Leaf Node나 Terminal Node라고 부른다. Terminal Node의 모든 데이터를 합치면 그 갯수는 Root Node에 있는 데이터의 갯수와 동일할 것이다. 만약 Terminal Node가 단 1개의 타깃변수(Y)로만 존재한다면, 이를 Pure Node라고 부른다.

자 이제 본격적으로 의사결정나무를 만드는 과정을 살펴보도록 하자. 의사결정나무는 데이터를 분류하는 과정이기 때문에 어떤 기준을 세워야 데이터가 잘 분리되는지 고민해야 한다.

이는 타깃 변수(Y)의 분류를 위해 어떤 X변수(Attribute)를 선택해야 하는가? 어떤 X변수가 데이터에 대한 확실한 정보를 제공하고 있는가? 라는 질문으로 환원될 수 있을 것이다. 앞서 확인했던 타이타닉호 예시를 생각해보자. 배가 침몰하는 과정에서 아이와 여성을 먼저 구출했을 것이므로 희생자의 다수는 남성이다. 따라서 개인의 생존/사망 여부를 분류하는 과정의 첫번째 질문은 ‘이 사람의 성별이 남성인가?’ 이다. 이처럼 의사결정나무는 각 단계에서 데이터를 가장 잘 분리해낼 수 있는 기준을 찾아 그에 대한 질문을 던진다.

CART Algorithm

Y가 범주형 변수(0,1)일 때, 활용할 수 있는 대표적인 분기 기준은 지니 계수(Gini Index)이다. 지니 계수를 이용하는 알고리즘은 CART 알고리즘이다. CART 알고리즘은 1번의 분기에 1개의 X변수만을 사용하며 해당 분기에서는 데이터를 2개의 Sub Node로 분리한다.

만약 분기에 사용하는 X변수가 숫자형(Numerical)일 때, 특정값보다 큰지(또는 작은지) 여부를 따지게 된다. 앞선 그림에서 나이가 9.5세보다 많은가 여부를 따지는 것과 같은 케이스를 생각하면 된다. 만약 명목형(Nominal) 변수일 때는 특정 집합 안에 속하는가 여부를 따지게 된다. 마찬가지로 앞선 그림을 통해 예시를 들자면, 남성인지 아닌지를 따지는 것과 같은 케이스를 생각하면 된다.

CART Algorithm은 노드를 분기할 때, 불순도(impurity)를 고려한 Greedy Search를 진행한다. 분기 이전 부모 노드(Parent Node)의 불순도를 계산하고 분기 후 자식 노드(Child Node)의 불순도를 계산하여 불순도가 낮아지는 분기, 또 여러가지 X변수들 중에서도 불순도 개선이 가장 뛰어난 X를 선택하여 분기를 진행한다.

Greedy Search라는 것은 시행가능한 모든 경우의 수를 따져본다는 것을 의미한다. 만약 분기 기준이 되는 X변수가 연속형 변수라면, 우선 연속형 변수의 유일한(unique) 관찰값을 먼저 구한다. 만약 유일한 관찰값이 M개라면, 이 유일한 값들을 순서대로 정렬한 이후, M-1번의 Greedy Search를 진행한다. 여기서 주목할만한 의사결정나무의 특징은 바로 데이터의 순서가 중요하기 때문에 Outlier에 강건한(robust) 성격을 갖는다는 것이다.

만약 분기 기준이 되는 X변수가 범주형 변수라면, 몇개의 범주로 구성되는지를 따져본다. Q개의 범주로 구성된다면 \(2^{(Q-1)}-1\) 가지 경우의 수가 존재하게 된다. Greedy Search에서 시행하는 횟수는 이와 같고 이렇게 여러가지 시행을 모두 진행한 이후, 불순도 개선이 가장 뛰어난 것을 분기 기준으로 선택하게 된다. 즉 의사결정나무는 변수의 종류에 영향을 받지 않는다고 할 수 있다. 특히 질적변수의 경우 더미(dummy)변수를 생성하지 않고도 해당 변수를 활용할 수 있다는 장점이 있다.

우선 불순도(Impurity)를 어떻게 따져볼 수 있는가를 생각해보아야 한다. 앞서 언급한 지니 계수(Gini Index)를 불순도 측정에 사용한다. 지니 계수의 식은 다음과 같으며 값이 가장 작은 경우를 선택한다.

\[\text{Gini Index} = \sum_{i=1}^{m}p_{i}(1-p_{i}) = 1-\sum_{i=1}^{m}p_{i}^{2}\]

지니 계수를 계산하는 예시를 살펴보도록 하자. 다음과 같이 총 8명이 존재하며 이들이 사기행위를 벌였는지 여부를 알아내보고자 한다. 4명의 무고한 사람과 4명의 사기꾼이 존재한다. 이들을 구분하기 위해 어떤 X변수를 기준으로 나누는 것이 옳은 것일까?

우선 부모 노드의 지니 계수를 계산해보자. 위의 식을 적용하면 다음의 그림과 같이 계산해낼 수 있다. 지금은 1개의 노드만 존재하니까 1개의 집합에서만 지니 계수를 계산하면 되지만, 이후의 과정에서는 집합이 2개씩 존재하게 된다. 이 때 각 집합의 지니 계수를 가중평균하여 분기 이후 노드들의 지니 계수를 구할 수 있다.

DT

2가지 X변수가 있다고 하자. 첫번째 변수는 성별이고 두번째 변수는 대출 여부다. 성별로 나눈 경우는 다음과 같다고 하자.

DT

대출 여부로 나눈 경우는 다음과 같다고 하자. 불순도 개선은 그림에서의 Goodness of split의 값이다. 대출 여부로 나눈 것이 불순도를 더 많이 개선시켰고 따라서 분기의 기준이 되어아햘 X변수는 대출 여부이다.

DT

가지치기(Pruning)

앞서 언급한 알고리즘을 활용하면 궁극적으로 우리는 모든 Terminal Node가 순도 100%인 결과를 만들어낼 수 있다. 그러나 항상 통계학에서는 Training Data에 과적합시키는 것을 지양한다. 이러한 문제를 해결하기 위해 가지치기(Pruning) 개념이 등장한다. 의사결정나무는 뿌리 노드에서 시작해서 top-down 방식으로 나무를 만들어가지만, Pruning은 밑에서부터 불필요한 가지를 쳐낸다.

DT

가지치기에는 사전 가지치기(Pre-Pruning)와 사후 가지치기(Post-Pruning)의 두가지 종류가 존재한다.

사전 가지치기는 트리의 성장 작업 중 실시하는 가지치기이며, 어느 정도 불순한 Terminal Node가 존재해도 성장을 조기에 종료시키는 방법이다. 보통 R이나 Python에서 hyperparameter 지정을 통해 사전 가지치기를 진행하게 되는데 옵션으로 설정해주는 나무의 최대 깊이(max depth), Terminal Node의 데이터 최대 개수 같은 것들을 설정하여 사전 가지치기를 프로그래밍 과정에서 진행할 수 있다. Python은 사전 가지치기만 실행할 수 있고 보통 프로그래밍 과정에서는 사전 가지치기를 주로 사용한다.

사후 가지치기는 트리 성장을 완료한 후 실시하는데 완성된 트리에서 일부 Terminal Node를 제거하여 가지치기를 진행한다.

가지치기의 기준은 어떻게 설정하는가? 우리가 회귀분석에서 MSE를 작게만드는 것을 최선의 것으로 선택하듯이 가지치기에도 기준이 있다. 여러 분기 중에서 비용함수를 최소화시키는 분기를 찾아내서 가지치기 수준을 결정 짓는다. 프로그램에서 알아서 계산해주니 큰 그림으로 아래와 같은 방식을 통해 그 값이 결정된다는 정도만 알아두면 된다.

비용함수 Cost Complexity Function은 다음과 같다.

\[CC(T) = Err(T) + \alpha \dot L(T)\]

CC(T)는 의사결정나무의 Cost Complexity를 의미하며 이는 오류가 적으면서 Terminal Node의 수가 작은 것이 작은 값을 가진다. Err(T)는 test data에 대한 오분류율을 의미하며, L(T)는 Terminal Node의 수, \(\alpha\)는 가중치(0.01~0.1)를 의미한다. 이 식은 새로운 분기를 진행함으로써 생기는 오분류율 감소 이득이 Penalty항(\(\alpha\text{L(T)}\)) 증가보다 크지 못하면 더 이상 분기를 진행하지 않는다는 것을 의미한다.

그러나 가지치기를 진행해도 과적합(Overfitting)문제를 완벽하게 해결하지 못한다.

한계

그러나 의사결정나무가 완벽한 분류 알고리즘은 아니다. 의사결정나무는 데이터가 조금만 바뀌더라도 분기 기준이 상당히 달라질 수 있다. 데이터에 따라 형태의 변동성이 높아 안정성이 떨어지는(instability) 모델이라 할 수 있다. 즉, 의사결정나무는 high-variane 모델이라는 치명적인 단점을 갖는다.

이러한 한계를 극복하는 과정은 의사결정나무와 완전히 동떨어진 방법을 만들어내는 것이 아니다. 불완전한 나무’들’을 모아서 의사결정나무 모델의 한계를 극복해가는 과정을 이후의 업로드에서 알아보도록 하자.

이 글은 다음의 교재를 참고하였음을 밝힙니다.