🌳

의사 결정 나무 (Decision Tree)

의사 결정 나무 분류법

널리 사용되는 비선형 분류 모형 중 하나로, 복잡한 데이터에 대해서 좋은 성능을 보인다.
설명가능한 (Interpretable, Explaniable)한 모델 중 하나이다.

Tree Induction

•
Greedy Strategy를 이용해서 나눈다.
•
어떻게 분리할 것인가?
◦
분리 기준 변수는 무엇인가?
◦
최적의 분리는 무엇인가?
•
언제까지 분리할 것인가?

Hunt's Algorithm

DtD_t : nodet_t에 있는 학습 데이터의 수 일때,
•
DtD_t에 속한 데이터가 모두 하나의 Class yty_t에 속한다면 tt는 yty_t의 leaf node이다.
•
DtD_t에 속한 데이터가 존재하지 않으면, tt는 기본 클래스 ydy_d의 leaf node
•
DtD_t에 속한 데이터가 둘 이상의 클래스에 속해 있다면, 특정 기준을 이용하여 데이터를 더 작은 분류로 분리한다.

어떻게 분류할 것인가?

명목형 변수에 의한 분류

•
Multi-Way Split : 서로 다른 값을 모두 이용하여 분리
•
Binary Split : 이진 트리가 되도록 두개의 부분 집합으로 분리

순서형 변수에 의한 분류

•
Multi-Way Split : 순서형 변수를 이산적인 클래스로 나눠서 분리
•
Binary Split : 두개의 부분집합으로 분리
* 순서형 변수는 순서를 어긋나게 부분 집합으로 분리하면 안됨

연속형 변수에 의한 분류

•
Multi-Way Split
•
Binary Split
구간을 적당하게 잘 나누어 주는 것이 중요하다.

어떻게 나눈 것이 잘 나눈 것인가?

Greedy Approach

Homogeneous한 Class 분포가 선호된다.
C0 5, C1 5 보다는 C0 9, C1 1를 선호한다는 뜻

Impurity

얼마나 Homogeneous 한지를 나타내는 값

1. Gini Index

GINI(t)=1−∑j[p(j∣t)]2GINI(t) = 1- \sum _j [p(j|t)]^2
p(j∣t)p(j|t)는 nodet_t에서 클래스 jj의 상대 빈도이다.
따라서 데이터들이 모든 클래스에 균일하게 분포할 때 1−1nc1-\cfrac{1}{n_c}로 최댓값을 갖고, 한 클래스에만 분포할 때 0으로 최솟값을 갖는다.
GINIsplit=∑i=1kninGINI(i)GINI_{split} = \sum_{i=1}^k \cfrac{n_i}{n}GINI(i) 로 분리된 이후의 GIni Index를 구할 수 있다.

2. Entropy

물리에 나오는 엔트로피와 유사한 것. 무질서 = 서로 다른 클래스가 많이 섞여있다.
Entropy(t)=−∑jp(j∣t)log⁡p(j∣t){\rm Entropy}(t) = -\sum_j p(j|t)\log p(j |t)
모든 클래스에 균일하게 분포할 때 log⁡nc\log n_c로 최댓값을 갖고, 한 클래스에만 분포할 때 0으로 최솟값을 갖는다.
GAINsplit=Entropy(p)−(∑i=1kEntropy(i))GAIN_{split} = Entropy(p) - (\sum^k_{i=1} Entropy(i))
GAIN이 가장 높아지도록 분리한다.
ID3이나 C4.5에서 사용한다.
Entropy 기반의 분리는 최대한 많이 분리해서 순도가 높도록 분류하려는 경향이 있다. 이런 경우는 GainRATIO를 이용하려 분류하면 좋다.
GainRATIOsplit=GAINsplitSplitINFOGainRATIO_{split} = \cfrac{GAIN_{split}}{SplitINFO} , SplitINFO=−∑i=1kninlogninSplitINFO = -\sum_{i=1}^k \cfrac{n_i}{n} log \cfrac{n_i}{n}

3. Misclassification Error

Error(t)=1−max⁡ip(i∣t)Error(t) = 1-\max_i p(i|t)
따라서 데이터들이 모든 클래스에 균일하게 분포할 때 1−1nc1-\cfrac{1}{n_c}로 최댓값을 갖고, 한 클래스에만 분포할 때 0으로 최솟값을 갖는다.
Misclassification Error의 경우는 Gain이 없다. (Splited 되어도 값이 같다.)

Tree Induction의 중단

•
한 노드 안의 데이터가 모두 같은 클래스에 속할 경우 분리를 중단
•
한 노드 안의 데이터의 입력 값이 모두 비슷한 경우 분류 중단
•
Overfitting을 방지하기 위해 조기 종료를 하기도 함

Decision Tree의 Overfitting

Decision Tree는 Overfitting이 굉장히 많이 발생하는 알고리즘 중 하나이고, Training Error 만으로 모델이 잘 작동할 것이라고 판단하기 어려움.

Decision Tree에서의 Generalization Error 근사

•
Optimistic Approach : Training Error = General Error
•
Pessimistic Approach : Leaf Node 1개당 0.5 만큼의 Error를 더해서 근사하는 방법, Leaf Node가 너무 많으면 당연히 Error가 줄것이니까 Leaf Node의 수와 Error를 같이 줄이는 방법이다.
•
Reduced Error Pruning (REP) : Val Set과 Train Set을 나누는 방법

Occam's Razor

같은 Generalization Error에서는 모델이 단순할 경우 좋은 모델이다.

Pre-Pruning (Early Stopping Rule)

•
한 노드에 속한 데이터가 일정 수 이하일 때
•
한 노드에 속한 데이터의 클래스 분포가 모든 입력 변수에 독립적일 때
•
어떤 분리도 Impurity를 개선하지 못할 때

Post-Pruning

•
끝까지 학습하고 완성된 트리의 노드를 제거하는 방법
•
가지치기에 의해 Generalization Error가 개선된다면 제거된 상태로 유지
•
Sub-Tree를 해당 Tree에 속한 데이터 중 가장 많은 수의 클래스 라벨로 결정함