[ML] Decision Tree

 

 

 

if-then 규칙으로 트리를 구성하고 이 트리를 바탕으로 분류를 수행한다. - Classification

루트 노드는 전체 데이터를 처음 분할하는 노드, 내부 노드는 특정 기준으로 데이터를 나누는 조건, 리프 노드는 최종 예측 결과가 저장되는 위치이다.

 

규칙을 정하는게 매우 중요하다. 

입력 데이터의 특정 포인트를 기준으로 잘라내고, 이 포인트는 impurity가 낮아야 한다. (misclassification)

 

impurity를 측정할 때는 Entropy, Variance, Gini Index, Misclassification 등 여러 방법을 사용한다.

 

 

 

 

각 방법들을 좌표평면에 표현하면 저렇게 나온다.

Misclassification은 분할했을 때 impurity가 개선되지 않는다는 문제가 있는데.. 현재 노드가 자식 노드로 분할되더라도 impurity의 평균은 같게 되니 impurity가 줄어들지 않는다.

 

따라서 Gini Index나 Entropy를 사용하자. 현재 노드가 가지는 impurity가 자식들의 가중평균보다 높게 설정할 수 있다.

웬만하면 Gini Index를 사용하는 편이다.

 

Split으로 impurity가 얼마나 낮아지는지를 분석하는 방법으로는 impurity drop과 information gain방식이 있다.

 

 

 

 

여기서 N_left는 좌측 노드, N_right는 우측 노드를 의미한다.

Information gain이 높고, Impurity가 낮은 쪽으로 흘러가는 경우가 가장 유리하다.

 

 

 

 

 

 

 

계산하는 예시.. 쭉 보고 넘어가자. Information과 Impurity 간의 관계가 중요함.

 

Decision Tree는 그리디하게 작동하다 보니.. Total Maximum을 고려하지 않고 Local Maximum만 고려한다.

이건 모델의 한계니까 어쩔 수 없음. 그래서 웬만하면 Ensemble 방식으로 다른 모델과 함께 사용한다.

 

당연한 말이지만 overfitting을 피하기 위해 트리의 depth를 적당하게 조절해 줘야 한다.

 

학습 데이터와 Validation 데이터를 7:3정도로 분리하자.

Max Depth / Max Leaf Nodes / Min Data for Split 등 여러 옵션을 사용해 트리에 규제를 줄 수 있다.

아예 트리의 크기를 제한해버리는 방식도 있다. 

 

Prunning

Stopping 기준의 대안으로, 가지치기 같은 방법을 사용한다.

 

 

 

 

 

가장 작은 Impurity Decrease를 가지는 Lear Node와 그 노드의 모든 Sibling 노드를 제거하는 방식이다.

Validation Data 없이 계산만으로 구현할 수 있다.

 

1. Full Tree를 생성한다.

2. Pruning 을 수행한다.

    - Sub Tree를 찾는다.

    - Full Tree의 Cost와 Sub Tree의 Cost를 계산한다.

    - Full Tree의 Cost가 더 크다면 Sub Tree를 채택한다.

 

 

Decision Tree에서는 결측값을 대충 다뤄도 된다. 원래는 평균이나 median으로 채우거나.. 여러 방법으로 결측값을 채워줬지만.

아무 값이나 넣어주자. 결측값을 위한 값으로 ? 값을 사용하기도 한다.

 

Decision Tree 알고리즘은 웬만하면 CART를 사용한다.

그런데 다른 것들도 있긴 하다. 구분 기준이 Chi-Squared Test를 쓰는 것도 있고. 

 

 

 

 

이해하기 쉽고 사용하기도 쉽지만 성능이 굉장히 떨어진다.