[ML][Ensemble]Decision Tree(결정트리)

Machine Learning 주제에서 Ensemble 학습에 들어가기 전에 Ensemble 학습의 대표적인 모델인 Random Forest가 Decision Tree 기반으로 되어있기 때문에 Decision Tree에 대해 공부하고 Ensemble 학습에 대해서 공부해보도록 하겠습니다

 

Decision Tree(결정트리)

Decision Tree란 의사 결정 규칙과 그에 따른 결과들을 Tree 구조로 나타낸 모델입니다

예측을 위해 여러 Region으로 Segmenting 하는 과정을 거치게 되고 분류 및 회귀에서 모두 사용 가능합니다

 

아래의 그림에서 "Years <4.5" 라는 의사결정규칙에 따라 $R_1$이 분류되고 그 후 "Hits < 117.5" 라는 규칙에 의해 $R_2, R_3$로 분류됩니다

 

Root Node : Tree 최상단에 위치하며, 데이터 분류의 시작점

Internal Node : 하나의 Feature에 대한 조건으로 분할되는 노드 

Terminal Node(Leaf Node) : 결정트리로 나누어진 Region

 

그림에서 분류에 대한 기준을 명확하게 알 수 있듯이 Decision Tree의 장점은 모델의 해석력에 있습니다

거기에 더해 Feature에 대한 전처리(Scaling, Regularization 등)가 불필요하다는 장점이 있습니다

하지만 Tree의 Depth가 너무 크면 Overfitting이 발생할 수 있고, 불균형한 데이터셋에서 특정 클래스에 편향된 Tree가 생성될 수 있다는 단점이 존재합니다

---

알고리즘

Regression with Decision Tree

회귀 결정 트리는 Loss Function을 최소화 하는 Region $R_1,\; R_2,\; \cdots\; R_J$를 찾는 것이 목표입니다

$$\sum \limits_{j=1}^{J} \sum \limits_{x_i \in R_j} (y_i - {\bar{y}}_{R_j})^2$$

이제 RSS Loss를 최소화하기 위해 Greedy Algorithm을 토대로 Region을 찾는 과정을 반복합니다(일정 기준을 만족 시 멈춤 ex) 각 Region에 5개 이하의 샘플)

사실상 모든 Region을 고려하는 것은 불가능하기 때문에 Top-down, Greedy 방법론(Recursive Binary Splitting)을 사용한다

 

1. Loss를 최대로 감소시키는 $R_k$($X_j < s$)를 찾는다

$$\sum \limits_{m=1}^{|T|} \sum \limits_{x_i \in R_m} (y_i - {\bar{y}}_{R_m})^2$$

2. Splitting Point s를 기준으로 Region을 새롭게 정의

Example

$X_1$	$X_2$	y
1	2	3
2	3	6
3	1	7
4	2	9

 

1. $X_1 = 2.5$로 Split 하는 경우

분할 전 MSE :

$$MSE(parent) = \frac{1}{4} \left( (3-6.25)^2 + (6-6.25)^2 + (7-6.25)^2 + (9-6.25)^2 \right) = 5.1875$$

분할 후 MSE : 

• 왼쪽 노드
  • $MSE(Left\,Node) = \frac{1}{2} \left( (3-4.5)^2 + (6-4.5)^2 \right) = 2.25$
• 오른쪽 노드 
  • $MSE(Right\,Node)=\frac{1}{2}​((7−8)2+(9−8)^2)=1$
• 전체 분할 후 MSE
  • $MSE(Split) = \frac{2}{4} \times 2.25 + \frac{2}{4} \times 1 = 1.625$

 

2. $X_2 = 2.5$로 Split하는 경우

분할 전 MSE : 5.1875

분할 후 MSE : 

• 왼쪽 노드
  • $MSE(Left\,Node) = \frac{1}{3} \left( (3-6.33)^2 + (7-6.33)^2 + (9-6.33)^2 \right) = 7.5556$
• 오른쪽 노드 
  • $MSE(Right\,Node)=0$
• 전체 분할 후 MSE
  • $MSE(Split) = \frac{3}{4} \times 7.5556 + \frac{1}{4} \times 0 = 5.6667$

$X_1 = 2.5$로 split할 때의 MSE Loss의 감소량이 더 크기 때문에 $X_1 = 2.5$가 더 좋은 분류 기준이 된다

Classification with Decision Tree

Classification에서는 MSE Loss를 사용할 수 없기 때문에 Information Gain(정보 이득) 관점에서 평가하게 됩니다

Information Gain을 간략하게 설명드리면 아래와 같습니다

※Information Gain

불순도(Impurity)

다양한 클래스가 어느 정도 섞여 있는지를 의미합니다

불순도 측정은 주로 Gini Index와 Entropy 지수를 이용합니다

1. Gini Index

$$Gini\;Index = 1 - \sum \limits_{i=1}^{n} {p_i}^2$$

2. Entropy

$$Entropy = - \sum \limits_{i=i}^{n} p_i \log{p_i}$$
이 때, $p_i = \frac{해당\;클래스에\;속한\;샘플\;수}{전체\;샘플\;수}$ 입니다

 

Information Gain

Split 전후의 불순도 차이를 의미합니다

분할 후 불순도의 차이가 클수록 Information Gain이 큽니다

$$Information\; Gain = Entropy(parents) - \sum \limits_{i=1}^{k} \frac{n_i}{n} Entropy(Child_i)$$

최적의 Decision Tree를 위해서는 Information Gain이 클수록 만들어야 하기 때문에 Split 전후 불순도 차이가 크도록 만들어야 합니다

즉, 분할 후 Gini Index 또는 Entropy를 최소화하기 위해 회귀 결정 트리와 같은 Greedy 방법을 기반으로 Spliting Point를 찾고 이를 기준으로 분리하게 됩니다