Decision Tree

Decision Tree는 말 그대로, 트리 형태의 구조를 세워 Classification을 수행하는 기법이다.

---

특성

Decision Tree는 아래와 같은 세 가지 특징을 지니고 있다.

Greedy, Recursive, and Divide & Conquer

1. Greedy

다음단계를 고려하지 않고, 현재 상태만 고려한다.

 

2. Recursive

같은 방식을 재귀적으로 반복한다. (아래 동작순서를 통해 이해할 수 있다.)

 

3. Divide & Conquer

큰 문제를 같은 작은 문제들로 쪼개서 해결한다. (마찬가지로 아래 동작순서를 통해 이해할 수 있다.)

 

---

구조

Decision Tree는 leaf node와 그렇지 않은 node로 구성되어 있다.

Classification의 측면에서 각 노드의 의미를 이해해보자.

 

# Branch Node

Alternatives 사이의 선택(Choice)을 의미한다.

 

# Leaf  Node

Class의 결정(Decision)을 의미한다.

---

동작순서

Decision Tree의 동작순서를 pseudo code로 알아보도록 하자.

1)빈 tree에서
2)Feature를 선택해 데이터를 split
	(split된 데이터에 대해)
    3)if 더 쪼갤 수 없다면 decision(prediction)을 만들 것
    4)elif 더 쪼갤 수 있다면, split한 데이터에 대해(2) recursive하게 다시 수행

아래 그림을 통해 Decision Tree의 동작순서를 이해해보도록 하자.

즉, 특정 feature를 기준으로 데이터를 split하는 것을 더 이상 쪼갤 수 없을 때까지 재귀적으로 반복하는 것이 Decision Tree이다.

---

Split의 기준이 되는 계산법들

위에서 Decision Tree는 특정 feature를 기준으로 데이터를 split 하는 것을 반복하는 기법이라고 했다.

그렇다면, split을 할 feature를 정하는 것은 어떤 것을 기준으로 할까?

여러 기준이 있으나, "How Heterogeneous of the Result of Splitting?"을 공통적으로 따르고 있다.

즉, split을 한 후 데이터의 heterogeneous한 정도가 낮게 만드는 feature일 수록, 선택될 확률이 높은 feature인 것이다.

 

대표적인 기준 세 가지를 살펴보도록 하자.

 

# ID3 - Information Gain

ID3는 Information Gain을 계산해, 그 값이 높은 feature를 선택한다.

Information gain은 아래와 같이, 'split을 통해 얻어진 정보량'을 계산한 값이다.

$$Gain(A) = Info(D) - Info_{A}(D)$$

여기서 정보(info)는 엔트로피를 의미하는데, 데이터가 혼재되어 있는 정도를 의미한다고 이해하면 되겠다.

$$Info(D) = entropy = -\sum_{i=1}^{m}p_{i}log_{2}(p_{i})$$

(p_i는 각 class가 데이터 상에 존재하는 확률을 의미한다.)

즉, split을 하기 이전 원래 데이터의 엔트로피와, split을 진행한 후 데이터들의 엔트로피가 얼마나 감소했는지를 기준으로 feature를 정하는 것이 ID3이다.

 

# C4.5 - Gain Ratio

Gain Ratio는, 값의 범위가 큰 feature에 대한 패널티를 없애기 위해 Information Gain에 추가적으로 feature의 value 개수를 고려한 계산이다.

$$Gain Ratio = Gain(A)\over SplitInfo_{A}(D)$$

여기서 SplitInfo가, feature가 가지고 있는 value 개수를 고려해준다.

$$SplitInfo_{A}(D) = -\sum_{j=1}^{m}{|D_{j}|\over |D|} * log_{2}{|D_{j}|\over |D|}$$

 

# CART - Gini Index

엔트로피 대신 지니계수를 정보로서 사용했다고 이해하면 되겠다.

엔트로피가 얼마나 감소했는지 대신, 지니계수가 얼마나 감소했는지(Reduction in Impurity)를 계산한다.

$$gini(D) = (1-\sum_{i=1}^{v}p_{i}^{2})$$

$$Reduction in Impurity = \Delta gini(A) = gini(D) - gini_{A}(D)$$

 

---

Decision Tree의 Overfitting

더이상 나눌 수 없을 때까지 splitting을 반복하는 Decision Tree의 특성상, Overfitting이 발생할 가능성이 있다.

이에 대응하는 방법이 크게 두 가지가 있는데, Pruning(가지치기)과 Ensemble(앙상블)이 그것이다.

하나씩 살펴보자.

 

# Pruning

말 그대로, 잔가지에 해당하는 branch를 쳐내는 기법이다.

1) Pre-Pruning

Tree를 만드는 과정에서, gain이 기준보다 작을 것 같으면 split하지 않는 방식이다.

2) Post-Pruning

Tree를 다 만들고, pruning 전후의 classification 정확도를 비교해, 성능이 나아질 때만 pruning한다.

 

*단, pruning은 calidation set에 대해서만 시행한다!

---

# Ensemble

여러 모델을 사용하여 낸 결과들을 종합해 최종 Decision을 만드는 기법이다.

앙상블 기법의 Decision Tree이므로, 여기서는 Random Forest에 해당하겠다.

 

작동방식을 살펴보자.

1) Tree의 수(B)만큼:
	1.1)각 Tree마다 데이터 sample을 다르게 하여 random sampling
    1.2)각 Tree마다 feature sample을 다르게 하여 feature sampling
2) B개의 Tree Decision의 다수결에 따라 최종 Decison Making

샘플링을 데이터와 feature 모두에 대해 시행하는 이유는, 다양한 tree를 생성해 overfitting을 막기 위함이다.

다수결에 의해 최종 decision을 만드나, tree별로 weight를 부여하는 것도 가능하다.

---

Decision Tree의 장점

Decision Tree의 장점을 간단히 짚고 넘어가자.

먼저, Tree 형태의 특성으로 인해 Classification Rule을 사람이 이해하기가 쉽고 간단하다.

또한, 상대적으로 다른 기법에 비해 Performance가 좋은 편이다.