의사결정나무(Decision Tree) 쉽게 이해하기

의사결정나무(Decision Tree)란 ?

 

 

의사결정나무(decision tree) 또는 나무 모형(tree model)은 의사결정 규칙을 나무 구조로 나타내어 전체 자료를 몇 개의 소집단으로 분류(classification) 하거나 예측 (prediction)을 수행하는 분석방법이다. 목표변수가 이산형인 경우의 분류나무(classification tree)와 목표변수가 연속형인 경우의 회귀나무(regression tree)로 구분된다.

 

---

 

■ 의사결정나무(decision tree) 장점

 

1) 결과를 해석하고 이해하기 쉽다.
2) 자료를 가공할 필요가 거의 없다.

3) 수치 자료와 범주 자료 모두에 적용할 수 있다.

3) 화이트박스 모델을 사용한다.

5) 안정적이다.

6) 대규모의 데이터 셋에서도 잘 동작한다.

 

■ 의사결정나무(decision tree) 단점

 

1) 각 노드에서의 최적값을 찾아내는 탐욕 알고리즘 같은 휴리스틱 기법법을 기반으로 하고 있어 최적 결정 트리를 알아낸다고 보장할 수는 없다.

2) 훈련 데이터를 제대로 일반화하지 못할 경우 너무 복잡한 결정 트리를 만들 수 있다.

3) 배타적 논리합이나 패리티,멀티플렉서와 같은 문제를 학습하기 어렵다.

4) 약간의 차이에 따라 트리의 모양이 많이 달라질 수 있다.

---

 

나무에서 분할되는 부분을 노드(node) 라 하고 가장 처음 노드를 root node(뿌리 마디), 중간 노드를 Intermediate node(중간 마디), 가장 마지막 노드를 terminal node(끝 마디)라 한다.

 

상위 노드로에서 하위노드로 트리구조를 형성하는 단계마다 분류변수와 분류 기준값의 선택이 중요하다. 목표변수가 이산형인 경우 상위노드에서 가지분할을 수행할 때, 분류변수와 분류 기준값의 선택 방법으로 카이제곱 통계량(Chi-square statistic)의 -값, 지니 지수(Gini index), 엔트로피 지수(entropy index) 등이 사용된다.

 

분할이 일어날 때, 카이제곱통계량의 p- 값은 그 값이 작을수록 자식노드 간의 이질성이 크고, 지니 지수나 엔트로피 지수는 그 값이 클수록 자식노드 내의 이질성이 큼을 의미한다. 따라서 이 값들이 가장 작아지는 방향으로 가지분할을 수행하게 된다.

 

즉, 쉽게 말하자면 불순도가 낮아지는 방향으로 나눠야 한다. 그리고 그 방법으로 ID3, CART, C4.5 등 여러 알고리즘이 있다.

불순도(Impurity)와 엔트로피(Entropy)란

불순도(Impurity)란 해당 범주 안에 서로 다른 데이터가 얼마나 섞여 있는지를 뜻한다. 아래 그림에서 위쪽 범주는 불순도가 낮고, 아래쪽 범주는 불순도가 높다. 바꾸어 말하면 위쪽 범주는 순도(Purity)가 높고, 아래쪽 범주는 순도가 낮다. 위쪽 범주는 다 빨간점인데 하나만 파란점이므로 불순도가 낮다고 할 수 있다. 반면 아래쪽 범주는 5개는 파란점, 3개는 빨간점으로 서로 다른 데이터가 많이 섞여 있어 불순도가 높다.

한 범주에 하나의 데이터만 있다면 불순도가 최소(혹은 순도가 최대)이고, 한 범주 안에 서로 다른 두 데이터가 정확히 반반 있다면 불순도가 최대(혹은 순도가 최소)이다. 의사 결정 나무는 불순도를 최소화(혹은 순도를 최대화)하는 방향으로 학습을 진행한다.

 

엔트로피(Entropy)는 불순도(Impurity)를 수치적으로 나타낸 척도이다. 엔트로피가 높다는 것은 불순도가 높다는 뜻이고, 엔트로피가 낮다는 것은 불순도가 낮다는 뜻이다. 즉, 엔트로피가 1이면 불순도가 최대이고 한 범주 안에 서로 다른 데이터가 정확히 반반 있다는 뜻이다. 엔트로피가 0이면 불순도는 최소고 한 범주 안에 하나의 데이터만 있다는 뜻이다.

 

엔트로피를 구하는 공식

 

엔트로피를 공식으로 한번 이해해보자.

 

먼저 확률 p는 전체 데이터에서 특정 데이터가 차지하는 비율을 말한다. 쉽게 말하면 주머니에서 파란색 공을 뽑을 확률. 우리가 아는 그것 맞다. 이제 공식을 살펴보자. 엔트로피를 구하는 식은 확률 p를 곱해서 더하는 구조를 가지고 있는데 이것은 정보의 기댓값(평균값)을 뜻한다. 그리고 확률에 log2를 취한다는 것은 데이터의 정보를 표현하기 위해서 필요한 비트 수를 확인할 수 있다는 뜻이다. (비트는 0과 1로 나타남)

 

즉, 다시 말하자면 이 공식은 데이터가 몇 개의 비트로 나타낼 수 있는지, 필요한 정보의 크기가 얼마만큼인지 알아보는 것이다. 필요한 정보의 공간이 크다는 말은 엔트로피가 크다는 것이다. 정보가 복잡할 수록 필요한 정보를 저장할 공간이 더 커야하니까 말이다. 정리하자면 필요한 모든 비트 수를 평균한 값이 엔트로피가 된다. 그리고 맨 앞의 마이너스(-)는 지수를 양수로 만들기 위해서 사용되었다.

 

출처 : bkshin.tistory.com/entry/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-4-%EA%B2%B0%EC%A0%95-%ED%8A%B8%EB%A6%ACDecision-Tree

정보획득량(Information gain)

 

정보획득량이란? 전체 Entropy와 분할 후 Entropy의 차이이다.

이것이 무슨 말일까. 앞에서 엔트로피는 불순도를 의미하는 것이었다. 전체 엔트로피가 최대 불순도 1이었을 때, 분류 후에도 1이면 정보획득량은 0이 된다. 반대로 전체 엔트로피가 1이었을 때, 분류 후에 0이면 정보획득량은 1이 된다. 이것은 정보획득량이 크다는 것은 불순도가 줄어든다고 볼 수 있다. 즉, 정보획득량의 값이 높을수록 분학의 성능이 좋은 것이고, 낮을수록 분할의 성능이 좋지 못한 것이다.

그럼 정보획득량이 왜 필요할까 ? 의사결정나무를 만드는 과정을 살펴보자.

 

 

1. 독립변수와 종속변수를 정한다.

 

2. 모든 독립 변수들에 대해서 가장 높은 정보획득(information gain)을 만드는 독립 변수를 찾는다.

 

3. 2의 과정을 더 이상 일정 이상의 정보획득(information gain)이 없을 때까지 (혹은 다른 threshold를 만족할 때까지) 반복한다. 

 

4. 잎사귀(leaf)에 도달한다.

 

 

이렇듯 정보획득량을 이용해서 더 이상 정보획득이 없을 때까지 트리를 만든다. 

관련 예제를 통해보면 정확하게 이해할 수 있다.

 

 

▼트리 예제

bskyvision.com/598

결정 트리(Decision Tree) 알고리즘, ID3 소개

 

의사결정나무의 다양한 방법

기존의 엔트로피를 사용해서 불순도를 계산하게 되면 log때문에 계산이 조금 느릴 수 있다. 그래서 조금 더 간편한 지니계수나 카이제곱스퀘어를 쓰기도 한다.

 

엔트로피는 데이터의 불순도가 희석되는 방향으로 나눈다면 카이제곱스퀘어는 상관관계가 가장 적도록 나눈다.

 

 

 

불순도를 계산하는 방법에 따라 ID3, CART, C4.5 등 여러 알고리즘로 불리게 되는데 이것은 다음에 한번 또 정리해야겠다.

 

 

 

 

실습

1. 필요한 모듈을 불러옵니다.

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

#Dot to png
import pydot

 

2. 데이터를 불러옵니다

#샘플 데이터 로드(유방암 데이터 세트)
cancer = load_breast_cancer()
 
#훈련, 테스트 데이터 셔플
X_train, X_test, y_train, y_test = train_test_split(
cancer.data, cancer.target, stratify=cancer.target, random_state=42)

 

3. 모델을 만듭니다.

#의사결정 트리 선언
dTreeAll = DecisionTreeClassifier(random_state=0)
 
#훈련 (모든 리프 노드 사용)
dTreeAll.fit(X_train, y_train)

 

4. 평가 점수 출력

#점수 출력
print("Train Set Score1 : {:.2f}".format(dTreeAll.score(X_train, y_train)))
print("Test  Set Score1 : {:.2f}".format(dTreeAll.score(X_test, y_test)))
 

Train Set Score2 : 0.98

Test Set Score2 : 0.94

 

 

5. 시각화

#의사결정트리 시각화
export_graphviz(dTreeLimit, out_file="dicisionTree1.dot", class_names=["malignant","benign"],
                feature_names=cancer.feature_names, impurity=False, filled=True)

#Encoding 중요
(graph,) = pydot.graph_from_dot_file('dicisionTree1.dot', encoding='utf8')


#Dot 파일을 Png 이미지로 저장
# error : http://yeyyyyee.blogspot.com/2019/10/graphviz-dot-not-found-in-path.html

graph.write_png('dicisionTree1.png')

 

▼결과