[Regression & Classifcation] Decision Tree

 

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

 

1. 트리의 원리

한국인이라면 어릴적에 스무고개 게임을 전부 해보셨을 것 같습니다. 정답에 대해 질문을 하면 예/아니요 답변을 듣고 정답을 맞춰가는 게임인데요. 오늘 알아볼 의사결정나무는 이러한 과정과 유사하게 진행됩니다.

좀 더 구체적으로 말하면 분기마다 모델에 사용하는 설명변수($X_1, X_2, \cdots, X_p$)가 구성하는 Sample Space를 더 작은 영역인 Sub-Space들로 나누는데요. 이때, 하나의 분기에서 여러개의 Sub-Space로 나눠질 수 있으나 겹치지 않는다는 특징이 있습니다. 트리를 나눌때 Sub-Space의 분산이나 불순도가 최소가 되도록하며, 특정 조건을 만족할때까지 트리를 잘게 쪼개나갑니다. 이렇게 트리모델이 구축되면 Sub-Space의 관측치를 이용해서 예측하게 됩니다.

 

 

 

 

2. 노드 불순도 지표

노드 불순도는 특정 노드의 혼잡도를 의미하며 값이 클수록 여러 값들이 노드에 섞여있다는 것을 의미하는데요.

분류 트리와 회귀 트리에 사용되는 지표가 다르며 공통적으로 지표가 낮을수록 노드의 불순도가 낮습니다.

• (회귀) : 오차제곱합(SSE) = $ \sum_{i:x_i \in R_j}(y_i - \overline{y_{R_j}})^2$
• (분류) : 엔트로피(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_i = \frac{1}{2}$일때 최댓값을 가집니다. 

 

 

 

3. 불순도 감소량 지표

불순도 감소량 같은 경우에는 트리에서 분기할때, 분기하기 전후의 불순도 차이를 의미합니다.

분기 전보다 후의 불순도가 작을수록 효과적으로 분리된것으로 불순도 감소량이 클수록 분류가 잘 되었다고 볼 수 있습니다.

 

• 정보이득(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})} $

 

정보이득(Information)을 사용하는 경우 한번 나눌때, 여러개의 노드로 나눌수록 값이 높아지는 것을 방지하기 위해 정보이득비율(GR)을 사용합니다. 그리고 정보이득에 지니지수를 사용할 수 있으나 보통은 정보이득은 엔트로피랑 함께 가더라고요.

 

아래 예시를 첨부했는데 개념이 어려우시다면 불순도랑, 불순도 감소량의 개념을 잘 설명한 블로그들이 많으니 참고해보시면 좋을 듯 합니다.

 

 

 

4. 트리 알고리즘

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

1. ID3 : Information Gain이 가장 큰 변수를 기준으로 해당 분기의 노드를 분할하는 방법 
   • 간단하고 빠르나 범주형 설명변수에서만 사용가능
   • 범주형 설명변수에 대한 다중분할(Multiway Split)를 수행
2. CART : 분류트리와 회귀트리를 구축하는데 사용되며 Gini 불순도 감소량(회귀에서는 SSE, MSE 감소량)이 가장 높은 변수를 기준으로 해당 분기의 노드를 분할하는 방법 (rpart::rpart)
   • 이진분할(Binary Split)을 수행해 노드에서 범주가 3개 이상이라면 "특정범주", "기타범주"로 구분해 계산을 수행
   • 비선형 모델링이 가능하며 범주 및 수치형 설명변수 모두 가능하다.
   • 가지치기(Pruning)를 적용
3. C4.5 : Information Gain Ratio가 가장 큰 변수를 기준으로 해당 분기의 노드를 분할하는 방법
   • 이진분할(Binary Split)을 수행해 노드에서 범주가 3개 이상이라면 "특정범주", "기타범주"로 구분해 계산을 수행
   • 범주 및 수치형 설명변수 모두 사용 가능하다.
   • 결측치가 있어도 사용이 가능하다.
   • C5.0 알고리즘은 C4.5알고리즘과 다르게 가중 오류를 최소화하며 필요없는 속성을 삭제하는 특징을 가지고 있으며 성능은 비슷하나 크기가 작고 빠르다는 장점을 가지고 있다. (C5.0::c5.0)
4. M5 : 주로 회귀트리에 사용되며 각 영역의 관측치로 적합한 선형회귀를 사용해 예측하는 알고리즘
   • 노드의 분리기준으로는 SD(Standard Devitation)을 사용한다.
   • 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)

• (선택) 표준화/정규화 (스케일 차이가 너무 크면 도움이 될 수 있음)
• 결측치 및 이상치처리 (트리는 결측치를 처리할 수 있으나 도움될 수 있음)
• 상관성제거(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.