[Regression & Classifcation] Decision Tree

안녕하세요. 이번 포스팅에서는 의사결정나무에 대해 알아보겠습니다.

 

1. 트리의 원리

한국인이라면 어릴 적 한 번쯤은 스무고개 게임을 해보셨을 것이라 생각합니다.
정답에 대해 질문을 던지고, 그에 대한 예 / 아니요의 답변을 바탕으로 점점 범위를 좁혀가며 정답을 맞혀가는 게임입니다.

오늘 알아볼 의사결정나무(Decision Tree) 역시 이러한 스무고개 게임과 매우 유사한 방식으로 동작합니다.

의사결정나무는 매 분기마다 설명변수 

$$x_1, x_2, \cdots, x_p$$

가 구성하는 전체 표본 공간(Sample Space)을 더 작은 부분 공간(Sub space)들로 나누어 나갑니다.

매 분할(Split) 과정에서 여러 개의 부분 공간으로 나뉠 수 있지만, 각 영역은 서로 겹치지 않는(disjoint) 공간이라는 특징을 가집니다.

분할을 수행하기 위해 분산(회귀 문제)이나 불순도(분류 문제)가 최소가 되도록 분기 기준을 선택하며, 미리 설정한 조건을 만족할 때까지 이러한 분할을 반복합니다.

이렇게 트리 모델이 구축되면, 각 구간에 포함된 학습 데이터의 정보를 활용하여 새로운 관측치에 대한 예측을 수행하게 됩니다.

 

 

 

 

2. 노드 불순도 지표

노드 불순도(node impurity)는 하나의 노드에 서로 다른 값들이 얼마나 섞여 있는지를 나타내는 지표입니다.
불순도의 값이 클수록 노드가 혼잡한 상태이며, 값이 작을수록 하나의 값(또는 범주)로 잘 정리된 상태라고 볼 수 있습니다.

의사결정나무에서는 문제의 유형에 따라 서로 다른 불순도 지표를 사용하지만, 공통적으로 불순도 값이 낮을수록 분할이 잘 이루어졌다고 해석합니다.

 

• (회귀) 오차제곱합(SSE) : $ \sum_{i:x_i \in R_j}(y_i - \overline{y}_{R_j})^2$로 여기서 $\overline{y}_{R_j}$는 노드 $R_j$에 속한 반응변수의 평균을 의미합니다.

• (분류) 엔트로피(Entropy) : $-\sum_{i=1}^{L}p_ilog_2(p_i)$
  
  
• (분류) 지니지수(Gini Coefficient) : $\sum_{i=1}^{L} p_i(1-p_i) = 1 - \sum_{i=1}^{L} p_i^2$

 

분류 문제에서 가장 이상적인 경우는 하나의 노드에 단일 범주만 존재하는 경우입니다.
이때 해당 범주의 비율은 $p=1$이 되며, 엔트로피와 지니지수가 0의 값을 가지게 됩니다.

 

반대로, 이진 분류 문제에서 두 클래스가 동일한 비율로 섞여 있는 경우 $p = \frac{1}{2}$에는 엔트로피와 지니지수 모두 최대값을 가지게 됩니다.

이는 해당 노드가 가장 불확실한 상태임을 의미합니다.

분할을 반복할수록 각 노드의 분산이나 불순도는 계속 감소하게 됩니다.
그러나 이러한 과정을 제한 없이 진행하면 학습 데이터에 과도하게 맞춰진 과적합(overfitting) 문제가 발생할 수 있습니다.

따라서 실제 모델링에서는 어느 시점에서 분할을 멈출지에 대한 기준이 필요하며,
이에 대한 내용은 5. Pruning에서 자세히 설명하겠습니다.

 

 

3. 불순도 감소량 지표

불순도 감소량(impurity decrease)은 의사결정나무에서 노드를 분기할 때, 분기 전후의 불순도 차이를 의미합니다.
즉, 하나의 분기를 통해 얼마나 불확실성이 줄어들었는지를 수치로 나타낸 지표입니다.

분기 이후의 불순도가 분기 이전보다 작을수록 데이터가 효과적으로 분리되었다고 볼 수 있으며,
이때 불순도 감소량이 클수록 좋은 분할로 판단합니다.

 

• 정보이득(Information Gain) : 분기 전 노드의 엔트로피와 분기 후 자식 노드들의 엔트로피 가중 평균의 차이

$$ IG = Entropy_{before} - Entropy_{after} = Entropy_{before} - \sum_{i=1}^{n}\frac{N_i}{N}Entropy(Region_i)$$

• 정보이득비율(Information Gain Ratio) : 정보이득에서 분할의 복잡도에 따른 패널티를 부여

$$ GR = \frac{IG}{\sum_{i=1}^{n}\frac{N_i}{N}log(\frac{N_i}{N})} = \frac{Entropy_{before} - Entropy_{after}}{\sum_{i=1}^{n}\frac{N_i}{N}log(\frac{N_i}{N})} $$

 

정보이득을 사용하는 경우 한번 나눌때, 여러개의 노드로 나눌수록 값이 높아지는 것을 방지하기 위해 정보이득비율(GR)을 사용합니다.

정보이득은 엔트로피 기반 불순도 감소량이지만, 지니지수를 사용하여 불순도 감소량을 계산할 수도 있습니다.

 

 

 

4. 트리 알고리즘

트리를 구축하는 대표적인 알고리즘에 대해 알아보겠습니다.

1. ID3 : Information Gain이 가장 큰 변수를 기준으로 해당 분기의 노드를 분할하는 방법 
   • 간단하고 빠르나 범주형 설명변수에서만 사용가능
   • 범주형 설명변수에 대한 다중분할(Multiway Split)를 수행
     
     
2. CART : 분류트리와 회귀트리를 구축하는데 사용되며 Gini 불순도 감소량(회귀에서는 RSS 감소량)이 가장 높은 변수를 기준으로 해당 분기의 노드를 분할하는 방법 (rpart::rpart)
   • 이진분할(Binary split)
   • 비선형 모델링이 가능하며 범주형과 수치형 설명변수 모두 사용 가능하다.
   • 가지치기(Pruning)를 적용
     
     
3. C4.5 : Information Gain Ratio가 가장 큰 변수를 기준으로 해당 분기의 노드를 분할하는 방법
   • 다중분할(Multiple split) 지원
   • 범주형과 수치형 설명변수 모두 사용 가능하다.
   • 결측치가 있어도 사용이 가능하다.
     
4. M5 : 주로 회귀트리에 사용되며 각 영역의 관측치로 적합한 선형회귀를 사용해 예측하는 알고리즘
   
   • Cubist는 M5 tree model을 확장한 규칙 기반 모델(Rule-Based Model)이다.
   • 분리기준으로는 표준편차감소(Standard Devitation Reduction)을 사용
     
     

$$SDR = sd(T) - \sum_{j=1}^{J}\frac{|T_j|}{|T|}sd(T_j)$$

 

 

 

5. 가지치기(Pruning)

가지치기는 과적합 방지를 위해서 사용되며 사전가치지기와 사후가지치기로 구분됩니다. 

 

 

 

6. 전처리(Preprocessing)

• (필요X) 표준화/정규화 
• (권장 X) 상관성제거(decorrelate) - 차원축소(PCA, PLS, ICA, UMAP), 변수선택법
• 결측치처리는 도움이 될 수 있고 이상치에는 로버스트 하다.
• Data Sampling - Oversampling / UnderSampling

 

 

 

7. 장단점(Pros and Cons)

• 해석이 쉽고 분류 및 회귀 문제에 사용이 가능하다
• 입력변수의 스케일링이 필요하지 않다.
• 이상치에 강하며 로버스트하다.
• 과적합의 가능성이 존재한다.
• 데이터에 따라 성능의 변동이 크다.

 

 

 

Reference

• James, G., Witten, D., Hastie, T., & Tibshirani, R. (2013). An introduction to statistical learning. New York: springer.
• Hastie, T., Tibshirani, R., & Friedman, J. (2009). The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media.
• Yaseen et al. (2015) Comparison of M5 Model Tree and Nonlinear Autoregressive with eXogenous inputs (NARX) Neural Network for urban stormwater discharge modelling
• Wang, Y., & Witten, I. H. (1997, July). Induction of model trees for predicting continuous classes. In Poster papers of the 9th European Conference on Machine Learning. Springer.