여러 규칙을 순차적으로 적용해 데이터를 분할함으로써 최종 클래스 또는 값을 예측하는 모형. 의사결정을 해 나가는 방식이 나무 줄기에서 가지가 뻗어나가는 모양과 유사해 '의사결정 나무(Decision Tree)'라는 이름을 갖게 됐다. 결정 트리라고도 한다. XGBoost, LightGBM 등 우리가 알고 있는 대부분의 부스팅 알고리즘이 의사결정 나무를 기반으로 한다.
$x=(x_{1}, x_{2}, \cdots, x_{d})^T$ 를 d차원상의 m개 셀로 분할한 후 셀의 평균 또는 셀 내에서 높은 비중의 범주로 y를 예측한다. 목표변수 y가 연속형이면 회귀 나무(Regression Tree), 범주형이면 분류 나무(Classification Tree)이다. 분할의 기준이 구체적으로 제시되기 때문에 해석이 명료하며, 매우 복잡한 데이터도 학습할 수 있는 강력한 모형이다.
노드(Node)와 깊이(Depth)
노드(Node)란 데이터를 분할하거나 최종적으로 예측을 수행하는 결정 지점을 의미한다. 루트 노드(Root Node)는 트리의 가장 상단에 위치해 분할이 시작되는 노드를, 리프 노드(Leaf Node)는 트리의 하단에 위치해 더이상 분기가 일어나지 않는 최종 노드를 의미한다. 루트 노드와 리프 노드 사이의 모든 노드는 내부 노드(Internal Node)이다. 그리고 루트 노드에서 리프 노드까지의 가장 긴 경로, 즉 최종 예측 결과에 이르기까지 거친 레이어 수를 깊이(Depth)라고 한다. 아래 이미지는 모형의 깊이가 2인 나무 모형의 의사결정 과정을 도식화한 것이다.
새로 발견한 붓꽃의 품종을 분류하는 문제에서 트리가 어떻게 예측을 하는지 살펴보자. 깊이가 0인 맨 꼭대기의 노드, 루트 노드에서 출발한다. 이 노드는 꽃잎의 길이가 2.45보다 짧은지 테스트한다. True이면 왼쪽의 하위 노드로, False이면 오른쪽의 하위 노드로 이동한다. 이때 하위 노드는 노드 간 역할을 부모-자식 관계에 비유해 자식 노드(Child Node)라 칭하기도 한다. 왼쪽의 노드는 아래에 자식 노드를 가지지 않는 리프 노드이므로 조건에 따라 ‘setosa’로 예측한다. 오른쪽의 노드에서 꽃잎의 길이가 2.45보다 길고 꽃잎의 너비가 1.75보다 작다면 ‘versicolor(왼쪽)’, 아니라면 ‘virginica(오른쪽)’로 예측한다.
의사결정나무는 이론적으로 각 셀에 한 개의 데이터만 존재할 때까지 학습을 계속할 수 있어 과대적합(Overfitting) 문제가 발생하기 쉽다. 그러므로 분할의 깊이를 제한하는 등 규제가 필요하다. 대표적인 규제변수로 분할의 깊이(`max_depth`), 분할에 필요한 최소 샘플 수(`min_samples_split`), 리프 노드의 최소 샘플 수(`min_samples_leaf`), 리프 노드의 최소 샘플 가중치 비율(`min_weight_fraction_leaf`), 최대 리프 노드 수(`max_leaf_nodes`), 분할에 고려할 최대 피처 수(`max_features`)가 있다. 제한 없이 결정 트리를 훈련시키고 불필요한 노드를 제거하는 알고리즘도 존재하며, 이 과정을 가지치기(pruning)라 한다.
분할 기준
노드는 데이터를 특정한 조건을 '기준'에 따라 분할한다. 분류와 회귀에서 그 기준이 다르며, 대표적인 측도는 아래와 같다.
회귀(Regression)
- SSE(Sum of Squared Error) : 데이터의 분할이 제곱 오차의 합을 최소화하도록 선택한다. 즉, 각 노드에서 가능한 모든 분할을 고려하고 가장 작은 SSE를 갖는 분할을 찾는다.
$$\text{SSE}_{total} = \sum_{i\in left}(y_{i}-\hat{y_{t}})^2 + \sum_{i\in right}(y_{i}-\hat{y_{t}})^2$$
***위 연산을 모든 경우의 수($(n-1) * p$)에 대해 수행하므로 데이터 사이즈($n$)가 크고 피처의 수($p$)가 많을 때 계산량이 급격히 증가한다. 이를 해결하기 위해 분할에 사용할 최대 피처 수를 제한하거나 가지치기를 수행할 수 있다.
분류(Classification)
- 지니 불순도(Gini Impurity) : 데이터가 얼마나 섞여 있는지 측정한다. 샘플이 모두 같은 클래스에 속하면 불순도는 0이다.
$$\text{Gini}(D)=1-\sum_{k=1}^{C}{p_{k}}^2$$
- 정보 이득(Information Gain) : 데이터셋을 특성으로 분할했을 때, 데이터의 불확실성이 얼마나 감소하는지를 측정한다.
$$\text{Information Gain}(D, A) = \text{Entropy}(D) - \sum_{v \in \text{Values}(A)} \frac{|D_v|}{|D|} \text{Entropy}(D_v)$$
- 크로스 엔트로피(Cross-Entropy) : 분류 모델의 예측 확률과 실제 클래스 분포 사이의 차이를 측정한다. 이 지표는 주로 로지스틱 회귀나 신경망 모델에서 사용되지만, 의사결정 나무의 분할 기준을 설정할 때도 사용할 수 있다.
$$\text{H}(D) = -\sum_{k=1}^{C}p_{k}\,log_{2}(p_{k})$$
계산 복잡도
나무 모형의 계산 복잡도는 여러 요소에 따라 달라진다. 특히 데이터 크기($n$), 피처 수($p$), 트리 깊이($d$)가 주요한 영향 요인이다.
- 학습 복잡도 : $O(n*p* log_{2}(n))$
- 성장 복잡도 : $O(2^{d}*n*p)$
- 예측 복잡도 : $O(log_{2}(n))$ or $O(d)$
각 노드에서 모든 샘플의 모든 특성을 비교하므로 훈련 복잡도는 $O(n*p* log_{2}(n))$이다. 트리의 깊이가 증가함에 따라 노드 수가 지수적으로 증가하므로, 트리 성장 복잡도는 $O(2^{d}*n*p)$이 된다. 한편, 예측 복잡도는 특성수와 무관하게 $O(log_{2}(n))$이다. 트리는 일반적으로 균형을 이루어 $O(log_{2}(n))$개 노드를 거치며, 각 노드는 하나의 특성값만 확인하기 때문이다.
일반적으로 최적의 트리를 찾는 것은 NP-Complete* 문제로 간주된다.
NP-Complete : P는 다항 시간 안에 풀 수 있는 문제의 집합이고, NP는 다항 시간 안에 답을 검증할 수 있는 문제의 집합이다. NP-Hard 문제는 모든 NP 문제를 다항 시간 안에 축소시킬 수 있는 문제이다. NP-Complete 문제는 NP이면서 NP-Hard인 문제를 뜻한다.
Reference
Aurélien Géron, Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow