결정 트리 - Decision Tree #이론 + 파이썬 코드 #쉬운 정리

결정 트리 구성 요소

 

 

 

 

 

 

 

 

결정트리 장단점

- 장점 : (1) 해석하기 쉽다.

           (2) 가변수를 만들지 않고도 질적 변수를 사용할 수 있다.

- 단점 : (1) 제한을 두지 않으면 과적합될 우려가 있다.

           (-> 보완 : Pruning)

           (2) 예측력이 떨어질 수 있다

           (-> 보완 : 랜덤 포레스트, 부스팅, 배깅 등 사용)

 

 

 

회귀트리와 분류트리의 차이점

- 예측값 :

  회귀는 각 클래스의 평균을 예측값으로 내놓음

  분류는 클래스를 예측값으로 내놓음

   ★ 분류트리의 경우, 한 부모 노드에서 같은 클래스 값의 자식노드를 내놓는 경우가 있음

                               --> 불순도의 차이가 존재하기 때문!

 

- 분할의 기준:

  회귀는 RSS를 사용

  반면, 분류는 분류오류율, 지니 지수, 교차엔트로피 등을 사용

 

 

 

분류의 분할 기준

각 분할 기준에 대한 수식은 다음과 같다

 

 

 

(1) 분류오류율

$$ E = 1 - \underset{max}{k} (\hat{p}_{mk}) $$

• where $\hat{p}_{mk}$ 은 $K$ 번째 클래스에서 나온 $m$ 번째 영역 內 훈련 관측치들의 비율

(2) 지니지수(Gini index)

$$G = \sum_{k=1}^{K} \hat{p}_{mk} (1- \hat{p}_{mk})$$

(3) 교차엔트로피(Cross-entropy)

$$D = - \sum_{k=1}^{K} \hat{p}_{mk} \log \hat{p}_{mk}$$

 

★ 분류오분율보다 지니지수와 교차엔트로피가 트리빌딩에 민감함

★ 낮을 수록 노드가 pure함

 

 

종류

- 일반적으로 Decision tree로 CART, C4.5, CHIAD가 잘 알려져 있음

* CART : classification and regressor tree

* CHIAD : Chi-squared Automatic Interaction Detection

 

 

CART로 결정트리 설명

- 재귀이진분할(recursive binary spliting) 방법을 사용

- Top-down의 greedy한 방법이라고 표현함

 * Top-down : 루트노드부터 예측공간을 연속해 분할해가기 때문

 *  Greedy : 특정 단계에서 가장 좋은 분할을 선택하기 때문

 

 

작동원리

- RSS(회귀의 경우), 불순도(분류의 경우, Gini Index, Cross-Entropy 등 사용)가 낮은 변수$X_J$와 절단점 s를 찾아 분리함

- 분리된 나머지 공간에서 위를 반복

- 어떤 정지규칙을 만족하면 멈춤

 

★그러나, 트리가 너무 복잡할 수 있기 때문에 과적합 우려가 높음 

-> 보완1 : RSS/불순도 등이 임계값을 초과하는 동안 트리빌딩 과정을 진행

               (BUT, 그 이후 RSS/불순도 값을 크게 줄이는 분할이 올 수 있는데 못함...)

-> 보완 2: 가장 큰 트리 $T_0$를 만들어주고, 가지치기(pruning)로 서브트리를 얻는 방법

 

 

 

pruning 방법

- 여기서는 Cost Complexity pruning(or weakest link pruning)을 소개하고자 함 

 

(1) 최대 가지수를 가지고 있는 가장 큰 트리 $T_0$를 만들어준 다음 pruning 시작

$ \sum_{m=1}^{|T|}$  $\sum_{ x_{i} \in R_{m} }$  $ (y_{i} - y_{R_m} )^{2} + \alpha |T| $

                             where  $|T|$ : 트리 T의 터미널 노드수

                                       $R_m$ : m번째 터미널 노드에 해당하는 공간의 부분집합 

- 뒷항으로 제한을 둔 것과 마찬가지임.

 

 

(2) 여기서 $\alpha$ 를 조율해봄 >  Cross-validation를 함 >  MSE를 구해본다.

* $\alpha = 0$이면 서브트리 $T$는 $T_0$와 같음

* $\alpha$가 커지면 뒷항이 크게 증가하기 때문에, 트리가 작을 때 위 식이 최소로 됨

 

 

(3) MSE를 가장 작게 만드는 $\alpha$를 선택 > $\alpha$에 대응하는 서브트리를 반환함

 

 

 

Python으로 구현

-학습 : sklearn.tree의 DecisionTreeClassifier 사용 (회기일 경우, DecisionTreeRegressor 사용)

-시각화 : sklearn.tree의 export_graphviz 사용

*확장자 .dot 파일로 추출하기 때문에 png나 pdf로 변환하는 작업 필요)

 

 

iris 데이터로 실습한다

 

(1) 관련 라이브러리 불러오기

### sklearn.datasets의 iris 데이터로 연습
# 라이브러리 불러오기

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier

 

(2) 결정트리에 fitting 시키기

## Decision Tree에 fitting시키기

iris = load_iris()
X = iris.data[:, 2:] #꽃잎의 길이와 넓이
y = iris.target


tree_clf = DecisionTreeClassifier(max_depth=2)
tree_clf.fit(X,y)

 

(3) 시각화

## Deicision Tree 시각화
from sklearn.tree import export_graphviz


export_graphviz(
    tree_clf,
    out_file = "iris_tree.dot",
    feature_names = iris.feature_names[2:],
    class_names = iris.target_names,
    rounded = True,
    filled = True
)

 

(4)  .dot 파일을 png 파일로 변환

import graphviz

with open("./iris_tree.dot", encoding='UTF8') as f:
    dot_graph = f.read()
    dot = graphviz.Source(dot_graph)
    dot.format = 'png'
    dot.render(filename='iris_tree', directory='./images', cleanup=True)
dot

 

 

★여기서 작동하지 않는다면, graphviz 설치 필요 ↓

 

conda install python-graphviz

 

 

 

 

 

 

 

 

 

 

(5) 해석하는 방법

- 루트노드 : 길이가 2.45 이하 true면 왼쪽(주황색 터미널 노드)으로 감!

- 주황색 터미널 노드 : 지니지수가 0임. 완전 pure함. sample은 50개가 분류되었으며, class는 setosa로 예측

 

 

 

(6) 새 Data로 예측하기

-길이가 5cm이고 너비가 1.5cm인 꽃잎의 경우, array[1]노드로 분류할 확률이 높음. (array 0부터 시작) 

- array 0 : setosa, 1: versicolor, 2: virginica

- 즉, versicolor로 분류할 확률이 90.7%

 

# 길이가 5cm이고 너비가 1.5cm인 꽃잎의 경우

tree_clf.predict_proba([[5, 1.5]])

array([[0. , 0.90740741, 0.09259259]])

 

 

- 이가 5cm이고 너비가 1.5cm인 꽃잎을 versicolor로 분류하였음 

tree_clf.predict([[5,1.5]])

array([1])

 

 

 

 

 

 

참고 : 

1) 핸즈온 머신러닝

2) katalog.egloos.com/3191268

Decision Tree(의사결정트리)