[ML] 의사결정나무(Decision Tree)

juyeon lee·2023년 2월 28일

Machine Learning

목록 보기

3/11

1. 정의

지도학습에 해당되는 알고리즘 중 하나로, 데이터를 분석하여 이들 사이에 존재하는 패턴을 예측 가능한 규칙들의 조합으로 나타낸다. 그 모양이 나무와 같다고 해서 의사결정나무라고 부른다.

전체 자료를 여러 소집단으로 분류(Classification)하거나 예측(Prediction)하는 데 사용하며 분류와 회귀 문제에 모두 사용할 수 있다!

1.1 구조

전체 학습 데이터인 '뿌리 마디(root node)'에서 분리 규칙에 따라 가지를 뻗어나가 자식 마디가 없는 최하위 단계인 끝마디까지 분리된다.
가지(branch)는 마디와 마디를 잇는 선을 말하며, 깊이(depth)는 가지를 이루는 마디의 개수이다. 이 그림에서 의사결정나무의 깊이는 3이다.

1.2 분리 기준

부모마디로부터 자식마디들이 형성될 때, 입력변수의 선택과 병합이 이루어지는 기준
입력변수를 이용하여 목표변수의 분포를 파악한 후 자식마디를 형성

1.2.1 이산형(범주형) 목표변수

목표변수의 각 범주에 속하는 빈도에 기초하여 분리가 일어남
기준 : 카이제곱 통계량,지니지수, 엔트로피 지수 등
알고리즘 종류 : CHAID, CART, C4.5 ,ID3
▶ 분류나무

1.2.2 연속형 목표변수

목표변수의 평균과 표준편차에 기초하여 분리
기준 : F-통계량, 분산 감소량
알고리즘 종류 : CHAID, CART
▶ 회귀나무

2 불순도(Impurity)

그룹 안에 서로 다른 객체가 얼마나 섞여 있는지 수치로 표현
→ 다양하게 섞여 있을수록 불순도 높음
종류 : 지니지수, 엔트로피 카이제곱 통계량 등
이 세가지 모두 작을수록 불순도 낮아짐

그림에서 항아리 1,3은 순도 100%이고 항아리 2의 불순도가 가장 높다.

2.1 지니 지수

불순도 측정 지표, 데이터의 통계적 분산정도를 정량화해 표현한 값
지니지수 = 불확실성
즉, 얼마나 많은 것들이 섞여있는가? 를 의미
따라서 5:5 비율로 반반 섞여있을 때 최댓값을 가진다.
지니지수가 0 = 같은 특성들끼리 잘 모여있다!
그룹 내에 있는 구성원들의 특성이 동일해질수록 지니지수는 낮아진다.
정보 이득의 최대화 → 불순도 감소 → 지니 지수 감소
지니 지수 작을수록 불순도 낮음, 데이터 분산되어있음 $G(S) = 1-\sum_{i=1}^{k} p_i^2$

2.2 엔트로피 지수

불순도 측정 지표, 정보량(어떤 사건이 지닌 정보의 양)의 기댓값
집합 안에 같은 것들로 구성되어있는가?
정보 이득의 최대화 → 불순도 감소 → 엔트로피 지수 감소
= 분기 후 엔트로피가 가장 작아지는 지표를 선택하라!
따라서 엔트로피 지수 작을수록 불순도 낮다

E(S) = \sum_{i=1}^{k} p_i * I(x_i)

2.3 정보 획득 (Information Gain)

$I(x_i)$ = 사건의 정보량

$I(x) = log_2 1/p(x)$

x축은 사건 x가 발생할 확률, y축은 정보량을 나타내는 그래프이다.
→ 사건 x의 발생 확률이 증가할수록 정보량은 0에 수렴

즉, 자주 발생하는 사건일수록 그닥 많은 정보를 가지지는 않는다.

3 분석 과정

3.1 목표변수와 관계 있는 설명변수들 선택

3.2 의사결정나무 형성

분석 목적을 정의하고 그에 따라 분리 규칙을 찾아 나무를 형성시키는 과정
데이터의 구조에 따라 분리기준과 정지규칙 설정
각 마디의 최적 분리규칙과 적절한 정지규칙을 만족하면 나무의 성장을 중단시킴

3.2.1 분리 기준

의사결정나무를 생성할 때 가지를 나누는 기준
마디의 순수도 증가하고 불순도 감소하는 방향으로 분류 진행

3.2.2 정지 규칙

더 이상 트리가 분리되지 않도록 하는 규칙
→ 현재의 마디가 끝마디가 되도록
정지규칙 없다면? 각 끝마디가 하나의 범주만을 갖는 과적합 발생

❓ 언제 정지하는가

더 이상 분리해도 불순도가 줄어들지 않을 때
자식마디에 남은 데이터 수가 너무 적을 때
분석자가 지정한 규제 매개변수(parameter)에 도달했을 때
규제 매개변수 종류 : max_depth, min_samples_split, min_samples_leaf etc.

❓ 어떻게 정지시키는가

방법 1) 트리의 깊이 제한
깊이가 깊어질수록 즉, 나무가 복잡해질수록 과대적합 가능성이 높기 때문!
방법 2) 끝마디의 데이터 수를 제한
즉, 자식마디의 최소 관측치 수를 제한

3.3 가지치기

의사결정나무의 깊이가 깊어 과대적합을 방지하기 위함
불필요한 가지를 제거 → 모형의 복잡도 감소!

방법 1) 검증용 데이터 활용해 예측 정확도 낮은 가지 제거
= 오차를 크게할 위험이 높은 가지 제거
방법 2) 규칙의 타당성 검토하여 부적절한 규칙 가지는 가지 제거

3.3.1 가지치기하는 시점에 따른 분류

사전 : 트리를 만들기 전에 트리의 최대 깊이나 노드의 최소 개수를 미리 지정해서 더 이상 분할이 일어나지 않게 하는 방법
사후 : 트리를 만든 후 밑에서부터 데이터가 적은 노드를 삭제 또는 병합

3.4 모형 평가

이익, 위험, 비용 등을 고려하여 모형을 평가하는 단계
이익표나 위험도표, 검증용 데이터 이용하여 모형의 타당성 평가
교차 타당성 (교차검증) 등을 이용

3.5 분류 및 예측

완성된 의사결정나무 모형을 해석하고 모형을 결정

4. 알고리즘 종류

4.1 ID3 (Iterative Dichotomiser 3)

4.1.1 정의

반복적으로 이분하는 알고리즘

4.1.2 특징

불순도 지수로 엔트로피 지수를 사용
엔트로피를 작게 하는 방향으로 가지를 뻗어나가며 의사결정나무를 키우는 것이 핵심
독립변수가 모두 범주형일 때만 가능
상위 노드에서 사용된 변수는 다시 사용하지 않음

4.1.3 한계

연속형 변수일 때 이용할 수 x
선택된 변수의 범주값이 매우 많을 경우 하위 노드의 가지의 수가 매우 많아짐
(전체에 대해서 하위노드 생성)
모델 생성 시 깊이가 너무 깊이 들어가는 문제 발생

이러한 한계점을 보완하고 새로운 기능을 추가한 알고리즘이 바로 C4.5

4.2 C4.5

4.2.1 정의

ID3 알고리즘을 발전시킨 알고리즘
분류 모델에서 쓰이며 엔트로피 계수를 가장 많이 감소시키는 변수를 찾아 분리

4.2.2 특징

불순도 지수로 엔트로피 지수 사용
수치형 데이터에 대해 이진 분리 방식 사용
범주형 데이터는 모든 범주들에 대해 분리 (다지 분리) 방식 사용
▶ 범주의 개수와 리프 노드 개수가 동일하게 분리

❓ 무엇을 보완시켰을까

범주형 변수만 가능했던 ID3와 달리 수치형 변수도 가능
모델의 깊이가 깊어지지 않도록 제한 → 과적합과 가지치기와 관련

4.3 CART (Classificaion And Regression Tree)

4.3.1 정의

분류 나무와 회귀 나무 모두 사용 가능한 의사결정나무 알고리즘
불순도 지수로 지니지수를 이용하며
목표변수가 범주형인 경우 지니지수 를 가장 많이 감소시켜주는 변수를 찾아 분리
목표변수가 연속형인 경우, MSE를 이용해 분산량 감소가 가장 큰 변수를 찾아 분리

전체 데이터셋을 가지고 시작하고, 두 개의 자식 노드를 반복 생성하기 위해 모든 예측변수를 사용한다. 데이터셋의 부분집합을 쪼갬으로서 의사결정트리 생성

4.3.2 이진 분리 (Binary Split)

여러 개의 자식 노드가 아닌 단 두 개의 노드로 분리
'하나의 클래스와 나머지' 형태를 유지
따라서, ( 모든 지표 * 모든 레벨 개수 ) 만큼의 비교가 필요

4.3.3 회귀 나무 (Regression Tree)

분기 지표를 선택할 때, 사용하는 인덱스를 불순도지수가 아닌 실제값과 예측값의 오차를 사용한다.
나무의 깊이가 깊어질수록 예측값과 실체값의 오차가 줄어든다
= 데이터를 나누는 경계가 촘촘할수록 오차가 줄어든다

❓ 오차 계산

4.4 CHAID (Chi-Squared Automatic Interaction Detection)

4.4.1 분류모델

피어슨의 카이제곱 통계량 이용하여 분리
카이제곱 통계량 값이 크면 p-value는 작아짐
▶ p-value가 가장 작음 변수를 찾아 분리

4.4.2 회귀모델

분산 분석표(ANOVA)의 F-통계량 이용하여 분리
F-통계량 값이 크면 p-value는 작아짐
▶ p-value가 가장 작음 변수를 찾아 분리

4.4.3 특징

수치형, 범주형 종속변수 모두 가능
이지 분리, 다지 분리 모두 가능

📌 Python 코드 분석

https://todayisbetterthanyesterday.tistory.com/38
위 게시글을 참고하여 실습함

💻 Entropy 지수 이용한 의사결정나무 코드 실습

import pandas as pd
import numpy as np
import graphviz
import multiprocessing
import matplotlib.pyplot as plt
plt.style.use(['seaborn-whitegrid'])

from sklearn import tree
from sklearn.datasets import load_iris
from os import system  
iris = load_iris()


#의사결정나무 분류 
#criterion = "entropy" 를 추가하여 불순도 지수로 엔트로피 이용


clf2 = tree.DecisionTreeClassifier(criterion = "entropy")  # Information Gain - entropy
clf2 = clf2.fit(iris.data, iris.target)

# 시각화 
dot_data2 = tree.export_graphviz(clf2,        # 의사결정나무 모형 대입
                               out_file = None,     # file로 변환할 것인가
                               feature_names = iris.feature_names, # feature 이름
                               class_names = iris.target_names,   # target 이름
                               filled = True,        # 그림에 색상을 넣을것인가
                               rounded = True,       # 반올림을 진행할 것인가
                               special_characters = True)    # 특수문자를 사용하나

graph2 = graphviz.Source(dot_data2)              
graph2

트리 구조에서 색깔은 각 클래스를 나타낸다. 총 3개의 클래스로 분류가 되었으며 깊이 6인 트리 모형이 형성되었다.
지니지수를 이용한 트리 모형과 불순도 지수 이외는 동일한 형태의 트리이다.

가지치기

가지치기로 최대 깊이를 제한하여 모형을 만든다면?
깊이 제한을 2로 설정, 3개의 집단을 구분하기 위해서는 최소 깊이 2인 트리를 형성해야함

#가지치기
clf3 = tree.DecisionTreeClassifier(criterion = "entropy", max_depth = 2)
clf3.fit(iris.data, iris.target)

#시각화
dot_data3 = tree.export_graphviz(clf3,              
                               out_file = None,       
                               feature_names = iris.feature_names, 
                               class_names = iris.target_names,  
                               filled = True,        
                               rounded = True,        
                               special_characters = True)

가지치기 전 상태의 모형과 비교했을 때, 깊이를 2로 제한하여 단조로운 모형이 되었으며 entropy 지수가 증가하였다. 정확도는 낮아졌지만 직관적으로 이해하기 쉬운 모형은 가지치기를 진행한 모형이었다.

🔍 장단점

➕ 장점

직관적으로 이해하기 쉬움 ▶ 설명력이 좋다
전처리 과정을 거치지 않아도 분류 가능
선형성, 정규성, 등분산성 등의 가정 필요 X ▶ 비모수적 모형
대용량 데이터에서도 빠르게 생성
수치형, 변주형 변수 모두 사용 가능
두 개 이상의 변수의 영향 정도 쉽게 파악 가능
비정상 잡음 데이터에 민감함 없이 분류 & 이상치에도 민감하지 X

➖ 단점

각 변수의 고유한 영향력을 해석하기 어려움
분리 경계점에서 연속형 변수를 비연속형으로 구간화 처리하기 때문에 분류를 위해 0,1 혹은 가까운 값으로 분류모형의 예측력 떨어짐
학습용 자료에 의존하기 때문에 새로운 데이터에 대한 예측 정확하지 않음
과대적합 발생 가능성 높음

juyeon lee

이전 포스트

[ML] 회귀분석

다음 포스트