2 minute read

Decision Tree

Naive bayesian처럼 확률을 기반으로 하지 않고 추론을 하고 싶다면 어떤 방법이 있을까? 이 방법이 Decision Tree이다.

Input A,B,C 를 통해서 play = T/F 을 추론해야 한다고 하자. A,B,C 로 가능한 조합은 총 222 = 8 가지이다. 이 모든 경우의 수를 확인하지 않고 정당한 추론을 하기 위해서는 어떻게 해야 할까?

joowan1108

가장 중요한 feature만 고려하여 추론을 하는 방법이 있다. 예를 들어 A를 가장 중요한 feature로 보고 A를 기준으로 data을 나누면 A = T 일 때는 Play가 항상 T이기에 다른 feature B,C를 고려하지 않아도 된다.

Decision tree는 이치럼 가장 중요한 feature을 토대로 data을 tree 형태로 구성하여 추론을 도와주는 방법이다.

Attribute Selection

그렇다면 가장 중요한 feature는 어떻게 고를 수 있을까?

Decision tree에서는 방금의 A처럼 data를 나눴을 때, 나뉘어진 split의 impurity가 가장 적다면 이 feature을 가장 중요하다고 본다

그렇다면 이 impurity는 어떻게 계산할 것인가?

엔트로피 개념을 사용하는 것이다. 엔트로피는 불확실성을 의미하는 개념으로 높을수록 복잡하고 impurity가 높다고 보면 된다. 엔트로피로 impurity을 계산하는 방법에 대해 더 알아보자

Set의 Impurity Measure

하나의 집합 안에 1과 0만 들어있다고 할 때, 집합에서 1이 나올 확률을 $P_1$, 집합에서 0이 나올 확률을 $P_0$ 이라고 하자. 그렇다면 이 set의 entropy는 다음처럼 계산된다.

\[Entropy = -P_1 * \log_2 P_1 - P_0 * \log_2 P_0\]

계산 예시는 다음과 같다.

joowan1108

Entropy는 $P_1$ 과 $P_2$ 가 같을 때 최대값을 가진다. 즉, impurity가 높을수록 entropy의 값이 높아진다는 것이다.

joowan1108

Split의 Impurity Measure

이 계산법을 토대로 특정 attribute에 대해 data을 나눴을 때의 entropy를 계산하는 방법을 알아보자.

T,T,T,F,F가 T,T 와 T,F,F 으로 나뉘었다고 하자. 이 split의 impurity을 계산하기 위해서 두 단계를 거치면 된다.

  1. 각 SET의 entropy 계산

    T,T의 entropy는 $-1\log_2 1 - 1\log_2 1 = 0$

    T,F,F의 entropy는 $-\frac {1} {3} *\log_2 \frac {1} {3} -\frac {2} {3} *\log_2 \frac {2} {3}$

  2. 모든 set의 average entropy 계산 = Split의 entropy

    $-\frac {2} {5} * (T,T 의 entropy) -\frac {3} {5} * (T,F,F 의 entropy)$

Selecting Attribute

이 값을 토대로 각 Attribute의 gain을 계산하면 impurity가 가장 낮게 해주는 attribute을 결정할 수 있다.

Gain(S,a)의 의미는 attribute a을 통해 impurity가 얼만큼 감소했는지를 의미한다.

\[\text{Gain(S,a) = Entropy(S) - Entropy of splits by a}\]

joowan1108

계산 과정은 다음과 같다.

joowan1108

이 gain 값이 높을수록 적합한 attribute인 것이다.

이때, attribute selection은 한번만 하는게 아니라 split을 통해 subtree가 생기면 이 subtree에 대해 또 attribute selection을 반복하고 계속 split 해야 한다. 이때, split을 통해 split entropy가 0이 된다면, 즉 subtree에 존재하는 data의 label이 모두 같다면, 이때는 split을 멈춘다.

joowan1108

지금까지 배운 방법을 ID3 라고 한다.

Questions

Decision tree는 data에 대해서 유일한가?

$\rightarrow$ X

어떤 decision tree을 최고라고 할까?

$\rightarrow$ 노드 수가 적고 높이가 제일 낮을수록 더 generalized된 tree로 본다. 반대로 복잡하고 노드 수가 많을수록 data에 overfitting 되었다고 본다.

그렇다면 ID3는 최적의 decision tree을 생성하는가?

$\rightarrow$ X ID3는 항상 현재 상태에서 가장 gain이 높은 split을 선택하는 Greedy algorithm 이기 때문에 optimal한 decision tree는 생성하지 못한다.

Decision tree의 overfitting은 어떻게 막을까?

$\rightarrow$ 생성 도중에는 깊이를 제한하거나 data가 수가 적다면 split이 되는 것을 방지하여 막을 수 있다.

$\rightarrow$ 생성된 뒤에는 pruning 작업을 수행할 수 있다. Data를 training, validation, test으로 나누었다고 할 때, leaf node들을 하나로 합치는 과정 또는 tree의 leaf node 중에서 validation set에서 classification에 영향을 주지 않는 node들을 제거하는 과정을 pruning이라고 한다.

Merge Pruning

joowan1108

Post Rule Pruning

Decision tree를 if then 문으로 바꾼 뒤에 이를 하나씩 제거해보면서 validation set에서 어떤 rule이 가장 영향력이 없었는지 평가하고 제거하는 과정으로 보면 된다.

You May Also Enjoy