머신러닝에서의 의사결정나무
정의
의사결정나무decision tree는 트리 구조를 가지고 입력된 데이터의 피쳐에 따라 분기를 거쳐 최종적으로 출력값을 찾는 머신러닝 기법을 말한다.
설명
의사결정나무는 고전적인 머신러닝 기법 중에서도 직관적이고 이해하기 쉬운 편에 속하며, 자연스럽게 그 응용또한 다양한 기법이다. 비지도학습에 k-평균 군집화가 있다면 지도학습에는 의사결정나무가 있다고 말해도 과언이 아니다.
소수 맞추기 문제
의사결정라는 게 트리구조에서 어떻게 일어나는지 이해하기 위해 ‘1부터 10까지의 자연수 중 소수를 맞추는 문제’가 있다고 상상해보자. 의사결정나무는 각 노드의 질문에 따라 데이터를 나누고, 결과적으로 ‘자연수를 보고 소수라고 할 것인지’에 대한 의사결정을 하게 된다.
- ($A$): 이 노드는 트리의 루트root다. 해당 수가 $3n-1$ 꼴로 나타나는지를 묻는다. $2, 5, 8$ 이 여기에 속한다.
- ($B_{1}$): 해당 수가 $7$ 보다 작은지를 묻는다. $2, 5$ 는 모두 소수고, $8$ 은 합성수기 때문에 이 노드는 리프leaf 노드가 된다.
- ($B_{2}$): 해당 수가 $2^{n} -1$ 꼴로 나타나는지를 묻는다. $1, 3, 7$ 이 여기에 속한다. 그 외의 경우엔 모두 합성수다.
- ($C$): 해당 수가 $2$ 보다 큰지를 묻는다. $3, 7$ 은 모두 소수고, $1$ 은 합성수기 때문에 이 노드는 리프 노드가 된다.
이러한 구조에 따라, 우리는 $x$ 를 이 트리에만 집어넣으면 $x$ 가 소수인지에 대한 결정을 내릴 수 있다. 그러나 바로 이 예시에서 볼 수 있듯 의사결정나무는 오버피팅에 취약하다는 특징이 있는데, 주어진 데이터 $1, \cdots , 10$ 에 대해서는 100%의 정확도를 보였지만 당장 $x = 11$ 는 ($B_{1}$) 노드에서 합성수 판정을 받게 될 것이다. 이는 의사결정나무가 제대로 된 소수의 규칙을 알아내지 못하고―데이터를 특징을 파악하지 못하고, 피상적인 성능에만 집착한 나머지 일반화된 추론 능력까지 갖추지 못했기 때문이다.
CART 알고리즘 1
당연하지만 위 예시처럼 사람이 직접 트리를 만들 일은 없고, 실제로는 CARTClassification And Regression Tree라는 알고리즘을 통해 트리를 만든다. 기본적으로 CART는 데이터의 특정 피쳐를 반으로 가르는 것을 반복하는 바이너리 서치binary search로 성능을 향상 시키는 분기가 어디서 일어나는지 전략을 취한다.
분류 문제
분류 문제의 경우엔 다음과 같이 지니 불순도Gini impurity 혹은 엔트로피를 손실함수로 두고 최소화하는 방식으로 트리를 찾는다. $$ G \left( D \right) = 1 - \sum_{k=1}^{C} p_{k}^{2} = \sum_{k=1}^{C} p_{k} \left( 1 - p_{k} \right) $$ 여기서 $p_{k}$ 는 데이터 $D$ 에 속하는 클래스 $k$ 의 비율이다. 노드에서 분류되는 데이터가 순수할수록 지니 불순도는 작아지며 의사결정나무가 데이터를 잘 분류하고 있는 것으로 본다.
여기서 다시 오버피팅 이야기를 하지않을 수 없는데, 소수 맞추기 문제에서 보았듯 의사결정나무는 데이터에서 단 한번 등장하는 경우만을 위한 케이스를 만들어낼 수도 있기 때문에, 어지간한 데이터에 대해서는 어떻게든 분기를 늘려서 어거지로 데이터에 맞추는 게 가능하다. 지니 불순도가 낮다는 것은 분류 결과가 순수한 여러 서브셋으로 나누었다는 것이지 진정으로 그 데이터를 파악한 것은 아니라는 것에 주의해야 한다.
회귀 문제
의사결정나무는 태생적으로 분류기의 기질을 가졌지만, CART 알고리즘의 그 이름 그대로 분류 혹은 회귀 문제 양쪽에 사용할 수 있다. 회귀문제의 경우 피쳐를 나누어 각 구역에서 종속변수의 평균을 예측값으로써 사용하며, 손실함수로는 평균제곱오차mean squared error를 사용한다. 그림에서는 $x$ 라는 피쳐를 $x_{1}$ 보다 작은지, $x_{2}$ 보다 큰지, 그 사이인지에 따라 세 구역으로 나누고, 각 구역에서 오렌지색으로 표시된 평균을 사용하는 식이다.
그러나 또다시, 어김없이, 이번에도 오버피팅의 위험이 도사리고 있다. 위 그림에서는 의사결정나무가 데이터를 세 구역으로 나누어서 비선형적인 관계를 성공적으로 파악하는 것으로 보이지만, 다음과 같이 구간을 더 세밀하게 나누는 것으로 트레이닝 데이터에서의 로스를 더 줄일 수가 있다.
이러한 억지 끼워 맞추기는 한도 끝도 없기 때문에 그 퍼포먼스는 끊임없이 의심해보아야 한다. 의사결정나무에 숙련되기 위해서 가장 중요한 것은 첫째도, 둘째도, 셋째도 오버피팅에 대한 경계심이다.
프루닝
가지치기pruning란 말 그대로 의사결정나무의 가지를 쳐내는 것으로, 앞서 말한 것처럼 너무 과하게 케이스를 나눠서 발생하는 오버피팅을 방지하기 위한 전략이다. 프루닝 방법은 크게 사전과 사후로 나눌 수 있다.
- 사전 프루닝: 트리를 만들 때, 일정 깊이 이상으로 트리가 자라지 못하게 하거나, 노드에 속하는 데이터의 수가 일정 이하로 떨어지면 더 이상 분기를 하지 않는 등의 제약을 거는 방법이다.
- 사후 프루닝: 일단 트리를 다 만든 후에, 검증 데이터에서의 성능이 오히려 떨어지는 노드를 찾아서 그 노드를 쳐내는 방법이다.
같이보기
Breiman, L., Friedman, J., Olshen, R. A., & Stone, C. J. (2017). Classification and regression trees. Chapman and Hall/CRC. https://doi.org/10.1201/9781315139470 ↩︎