AI/Machine Learning

[ML] 결정트리(Decision Tree) - 기본구조와 CART, ID3 알고리즘

heeee__ya 2021. 10. 3. 23:25

 

  결정트리(Decision Tree)는 머신러닝 알고리즘 중 하나로, flowchart 같은 구조를 가진다. 기본적으로 결정트리는 데이터에 있는 규칙을 통해 데이터셋을 분류/예측하는 지도학습(supervised) 모델이다. 결정에 다다르기 위해 스무고개와 같은 예/아니오 질문을 이어나가면서 학습한다. 질문들은 다음과 같이 트리 구조로 나타낼 수 있다.

 

mglearn.plots.plot_animal_tree()

 

각 네모칸을 트리의 노드(node)라고 하고, 특히 마지막 노드는 리프 노드(leaf node)라고 부른다(알고리즘 공부한 사람은 알겠지만 리프 노드=자식이 없는 노드 맞다, terminal node라고도 함). 에지(edge)는 질문의 답과 다음 질문을 연결한다.

 

 

 

기본 구조

scikit-learn의 breast cancer 데이터셋을 사용했다. cancer.target값은 양성과 악성에 대응하는 0과 1이다.

 

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier

cancer = load_breast_cancer()
X_train, X_test, y_train, y_test = train_test_split(cancer.data, cancer.target, stratify=cancer.target, test_size=0.2, random_state=123)
tree = DecisionTreeClassifier(random_state=123)
tree.fit(X_train, y_train)
print("test set accuracy: {:.3f}".format(tree.score(X_test, y_test)))
# test set accuracy: 0.923

 

트리 모듈의 export_graphviz 함수와 graphviz 모듈을 이용해 트리를 시각화할 수 있다. export_graphviz 함수를 통해 dot 파일 포맷으로 그래프를 저장할 수 있고, 이를 with open문을 이용해 열어준다.

 

from sklearn.tree import export_graphviz
import graphviz

export_graphviz(tree, out_file='breast_cancer_tree.dot', class_names=['WDBC-Malignant', 'WDBC-Benign'], feature_names=cancer.feature_names, impurity=False, filled=True)
with open("breast_cancer_tree.dot") as f:
    tree_graph = f.read()
display(graphviz.Source(tree_graph))

 

이미지 전부 출력하면 잘 안보이는 것 같아서 끝부분을 잘랐다.. 

  아무튼 이런식으로 루트 노드에서부터 분기를 이루면서 가장 많은 정보를 담을 수 있도록 계층적으로 영역을 분할해간다. 데이터를 분할하는 것은 각 분할된 영역이 한 개의 타깃값(하나의 클래스나 하나의 회귀 분석 결과)를 가질 때까지 반복된다. 위 그림의 리프 노드들을 보면 value=[1,0] 혹은 value=[0,2] 처럼 하나의 타깃으로만 분류되어 있다.

  분류의 예시가 가장 이해하기 쉬워서 가져왔는데, 예측(회귀 분석) 문제에도 트리를 사용할 수 있다. 다만 score함수가 Classifier에서처럼 accuracy 기반이 아니라 결정계수 \( R^2 \)이다. 참고

 

import graphviz
from sklearn.datasets import load_diabetes
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeRegressor
from sklearn.tree import export_graphviz

diabetes = load_diabetes()
X_train, X_test, y_train, y_test = train_test_split(diabetes.data, diabetes.target, test_size=0.2, random_state=123)
tree = DecisionTreeRegressor(random_state=123)
tree.fit(X_train, y_train)
print("test set accuracy(R^2 determination): {}".format(tree.score(X_test, y_test)))
# test set accuracy(R^2 determination): 0.15795709914946876
# DecisionTree에서 score는 결정계수임을 잊지말자

export_graphviz(tree, out_file='diabetes_tree.dot',feature_names=diabetes.feature_names, impurity=False, filled=True)
with open("diabetes_tree.dot") as f:
    tree_graph = f.read()
display(graphviz.Source(tree_graph))

 

 

이것도 전체 트리는 너무 커서 일부만 표시했다. 예측을 하려면 각 노드의 테스트 결과에 따라 트리를 탐색해나가고 새로운 데이터 포인트에 해당되는 리프 노드를 찾는다. 찾은 리프 노드들의 훈련 데이터 평균값이 이 데이터 포인트의 출력이 된다.

 

 

 

알고리즘 - "트리를 어떻게 분할할 것인가?"

지금까지 결정트리의 기본 구조를 살펴보았다. 다시 압축해서 설명하자면, 결정트리란 데이터에 있는 규칙을 학습을 통해 자동으로 찾아내 Tree 기반의 분류 규칙을 만드는 것이다. '데이터의 규칙'을 만들기 위한 과정에 다음과 같은 속성들이 포함된다.

 

  • 결정 노드(Decision Node): 규칙 조건
  • 리프 노드(Leaf Node/Terminal Node): 결정된 클래스의 값
  • 서브 트리(Sub Tree): 새로운 규칙 조건마다 생성됨

 

그렇다면 트리를 어떻게 쪼개나갈 것인가? 최대한 균일한(순도가 높은) 데이터 세트를 구성할 수 있도록 분할하는 것이 중요하다. 결정 노드는 정보 균일도가 높은 데이터 세트를 먼저 선택할 수 있도록 규칙 조건을 만든다.

결정트리를 만드는데 여러 가지 알고리즘이 사용될 수 있다. 가장 대표적인 것은 CART 알고리즘과 ID3 알고리즘이다.

 

  • CART(Classification and Regression Trees) - metric으로 Gini Index(Classification) 사용
  • ID3(Iterative Dichotomiser 3) - metric으로 Entropy function과 information gain 사용

 

1. CART (Classification And Regression Tree)

CART 알고리즘은 의사결정 트리 방법론 중 가장 잘 알려진 방법론 가운데 하나이다. 1984년 Brieman et. al 이 CART 기법을 발표한 이래로 기계 학습 실험의 필수기법이 되어왔다 [Berry and Linoff, 1997]. CART 기법은 전체 데이터셋을 갖고 시작하여 반복해서 두 개의 자식 노드(Child Node)를 생성하기 위해 모든 예측 변수(Predictor variables)를 사용하여 데이터 셋의 부분집합을 쪼갬으로써 의사결정트리를 생성한다 [Berry and Linoff, 1997, SPSS, 1998].

 - 출처 : https://ai-times.tistory.com/159

 

  scikit-learn의 DecisionTreeClassifier는 CART기반으로 구현되어 있다. CART 알고리즘은 불순도를 지니계수(Gini Index)로 계산한다(찾아보니까 분류 문제에서 지니계수를 사용하고, 회귀 문제에서는 RSS를 사용한다고 한다! 참고로 RSS는 오차제곱합으로, MSE이랑 같음).

 

여기서 C는 사건의 개수이고 \( p_i \)는 해당 split에서 사건이 발생할 확률이다. 위에서 계산된 Gini를 바탕으로 지니계수를 계산한다(Gini와 Gini index는 다르다,,, 다음 글에서 계산하는 방법을 다룬다)

지니계수는 데이터의 통계적 분산정도를 정량화해서 표현한 값으로, 0(complete equality)와 1(complete inequality) 사이의 값을 가진다. 이는 데이터가 다양한 값을 가질수록 평등하고(0에 가까움), 특정 값으로 쏠릴 경우에 불평등하다(1에 가까움)는 뜻이다. 결정트리에서는 지니계수의 값이 낮은 속성을 기준으로 분할한다. 즉, 가장 낮은 지니계수를 가진 피처가 결정트리에서의 루트 노드가 된다.

 

 

 

2. ID3 (Iterative Dichotomiser 3)

  ID3 알고리즘은 불순도를 엔트로피를 이용한 정보 이득(Information gain)으로 계산한다. 이 알고리즘은 독립변수가 모두 범주형(categorical)일 때만 가능하다는 단점이 있다. 범주형 변수에 대한 설명과 이를 처리하는 방법은 이전 포스트 참고.

  엔트로피(entropy)란, '주어진 집합의 혼잡도'를 의미하며 서로 다른 값이 섞여있으면 높고(1에 가까움) 같은 값만이 존재할 수록 낮다(0에 가까움). 그리고 정보이득이란 분할 전 엔트로피와 분할 후 엔트로피의 차이를 말한다. 

 

  • D: 주어진 데이터들의 집합
  • k-class set in sample: D에서의 k클래스에 속하는 레코드의 수
  • |sample|: 주어진 데이터들의 집합의 데이터 개수

엔트로피 값은 레코드 값 포함 비율에 로그를 적용하고 다시 가중치로 곱한 값을 모두 더한 것이다. 그리고 \( Ent(D) \)의 값이 작을수록 D의 순도는 높아진다(한 클래스에 몰려있다)

 

  • a: 특정 노드의 특성

\( Ent(D) \)에서 해당 피처에 속하는 부분집합들에 대한 엔트로피 값을 뺌으로써 정보이득을 구할 수 있다. 결정트리를 분할할 때 정보이득이 높은 노드를 우선적으로 선택한다.

 

 

 

결정트리의 장점 vs 단점

  결정트리의 가장 큰 장점은 시각화하고 편하고, 직관적으로 이해가 가능하다는 것이다. 머신러닝에서 가장 기본이 되는 모델인 만큼 앙상블 기법을 통해 랜덤 포레스트(random forest)나 그래디언트 부스팅 머신(gradient boosting machine)으로 발전하기도 했다. 또, 데이터의 스케일에 구애받지 않는다. 각 피처가 개별적으로 처리되어 데이터를 분할하는데 데이터 스케일의 영향을 받지 않으므로, 결정트리에서는 피처 정규화나 표준화 같은 전처리 과정이 필요없다.

  주요 단점은 pruning(가지치기)를 사용해도 과대적합되는 경향이 있어 일반화 성능이 좋지 않다는 것이다. 이를 대신해 앙상블 기법을 단일 결정트리의 대안으로 흔히 사용한다.