Dicision Tree(의사결정나무)

Dicision Tree란?

Dicision Tree는 분류 및 회귀 작업에 사용되는 지도 머신 러닝 알고리즘의 한 유형이다. Dicision Tree를 구성하는 알고리즘에는 ID3, C4.5, CART(분류 및 회귀 트리) 등 여러 가지가 있지만 여기서는 ID3에 대해서 알아본다.

 

내부 노드는 특징 테스트 또는 결정점을 나타내고, 분기는 해당 테스트의 결과를 나타내며, 리프 노드는 최종 클래스 레이블 또는 목표 값을 나타내는 순서도와 같은 구조이다.

불순도는 데이터 내에서 여러 카테고리가 섞여 있어, 원하는 표본을 뽑을 확률이 적을 수록 커지는 개념이다. 다양한 과일들의 비율이 높아질수록 불순도는 증가한다. 

이 불순도를 지표로 만든 것을 엔트로피(Entropy)라고 하는데 Dicision Tree는 Sample이 가장 섞이지 않은 상태로 완전히 분류하는 것, 즉 엔트로피를 낮추도록 만드는것이다.

 

※ 엔트로피는 무질서한 정도를 수치화한 값, 0에서 1사이의 값을 가진다.

예를 들어, 이 노드에는 빨간공 3개 초록공 3개로 이루어져 있다. 이 노드의 엔트로피를 계산하면 다음과 같다. 

 

위의 그림처럼 Dicision Tree는 엔트로피를 최대한 낮추는 방향으로 분류 규칙을 만든다. 여기서 어떤 속성을 선택함으로써 데이터를 더 잘 구분(엔트로피가 감소)하게 되는 것을 정보 획득(Information Gain)이라고 한다.

정보 획득(Information Gain)은 상위노드의 엔트로피에서 하위노트의 엔트로피를 뺀 값이다.

특정 정보를 활용하여 분류하기 이전 엔트로피가 1이었고 분류 이후 엔트로피의 가중합이 0.8 이라면 Information Gain은 0.2이다. 불확실성, 즉 Entropy가 줄어들었으므로 분류하기 이전보다 더 값들이 나누어져 있음을 뜻한다.

예를 들어, 학생 데이터에서 수능 등급을 구분하는데 있어 수학 점수가 체육 점수보다 변별력이 더 높다고 하자 그러면 수학 점수 속성이 체육 점수 속성보다 정보획득이 높다고 말할 수 있다. 

 

왜? 수학 점수가 체육 점수보다 변별력이 높다고 하면 수학 점수 엔트로피는 체육 점수보다 더 낮아야한다. 수학 점수로 분류 이후 엔트로피 가중합을 0.2로 가정하고 체육 점수 분류 이후 엔트로피 가중합이 0.8로 가정하면 분류 이전 엔트로피를 1이라고 가정시 수학 점수 정보 획득은 1 - 0.2 = 0.8, 체육 점수 정보 획득은 1 - 0.8 = 0.2로 정보 획득 값이 클수록 변별력이 좋은것을 확인할 수 있다.

 

Dicision Tree의 학습(ID3)

Dicision Tree에서는 이렇게 각각의 특성에 따라 얻을 수 있는 정보획득을 측정하고 정보 획득이 가장 큰 특성이 첫번째 가지에 자리를 잡게 된다.

 

한번 Dicision Tree를 만들어보자.

Day	Outlook	Temperature	Humidity	Wind	PlayTennis
1	Sunny	Hot	High	Weak	No
2	Sunny	Hot	High	Strong	No
3	Overcast	Hot	High	Weak	Yes
4	Rain	Mild	High	Weak	Yes
5	Rain	Cool	Normal	Weak	Yes
6	Rain	Cool	Normal	Strong	No
7	Overcast	Cool	Normal	Strong	Yes
8	Sunny	Mild	High	Weak	No
9	Sunny	Cool	Normal	Weak	Yes
10	Rain	Mild	Normal	Weak	Yes
11	Sunny	Mild	Normal	Strong	Yes
12	Overcast	Mild	High	Strong	Yes
13	Overcast	Hot	Normal	Weak	Yes
14	Rain	Mild	High	Strong	No

다음과 같은 데이터가 있다고 가정하면 우리는 독립변수들로부터 그 날 PlayTennis의 여부를 결정하고자 한다. PlayTennis가 Yes와 No인 경우가 각각 9, 5개이므로 Root Node에서의 엔트로피는 약 0.940이다. 이제 우리는 특정 feature를 기준으로 분기를 나누어야 하는데, Outlook, Temperature, Humidity, Wind로 분기하였을 때 각각의 Information Gain을 계산한 후 Information Gain이 가장 큰 값으로 분기하도록 결정한다.

Wind	PlayTennis	Count
Weak	Yes	6
Weak	No	2
Strong	Yes	3
Strong	No	3

Wind를 선택하였을 때의 Information Gain을 구해보자. Wind 값 별로 PlayTennis 값을 세면 다음과 같다.

이렇게 Wind 특성의  Information Gain 값을 얻었다. 같은 원리로 다른 feature 들에 대해 Information Gain을 구하면 Temperature는 0.029, Humidity는 0.151, Outlook은 0.246의 값을 얻을 수 있다. 그리고 Decision Tree는 Information Gain이 가장 큰 Outlook을 사용하여 분류한다.

 

※ 여기서 H(S_Weak)의 값은 Wind 값이 Weak인 데이터만 모아서 따로 엔트로피를 계산한 값, H(S_Strong)의 경우도 마찬가지

만약 분류한 후 생긴 노드가 Terminal node(최상단 노드)가 아닌 Intermediate Node(최상단 노드가 아니면서 자식이 존재하는 노드)라면 그 Intermediate Node에서 위 과정을 반복해주어야 한다. 이 과정을 반복하면 위와 같은 Decision Tree를 얻을 수 있다.

 

하지만 Information Gain의 최솟값을 정해놓지 않으면 독립 변수가 많은 경우 Dicision Tree가 너무 깊게 만들어질 수도 있고, Overfitting의 위험도 있다. 그렇기 때문에 이를 threshold로 정해 놓아야 한다. 이외에도 maximal depth, minimal size of node 등이 threshold가 될 수 있다.

 

Dicision Tree의 장점 및 한계

의사 결정 트리의 몇 가지 장점은 다음과 같다.

	의사 결정 트리의 장점
이해하고 해석하기 쉽다.	의사 결정 트리는 비전문가도 시각화하여 설명할 수 있으므로 해석 가능성이 중요한 상황에서 널리 사용된다.
데이터 전처리가 거의 필요하지 않다.	의사 결정 트리는 스케일링이나 정규화 없이 범주형 및 연속형 특징을 처리할 수 있으며, 누락된 값도 처리할 수 있다.
비선형 관계	의사 결정 트리는 특징과 대상 변수 간의 복잡한 비선형 관계를 모델링할 수 있다.
빠른 예측	트리가 구성되면 루트에서 리프 노드까지 트리를 탐색하기만 하면 되므로 새 인스턴스에 대한 대상 변수를 빠르게 예측할 수 있다.

 

의사 결정 트리에는 몇 가지 한계도 있다.

	의사 결정 트리의 한계
과적합	의사 결정 트리는 쉽게 지나치게 복잡해지고 데이터 내 노이즈에 최적화하여 과적합될 수 있다. 그러나 가지치기, 최대 깊이 설정 또는 잎 노드 당 최소 샘플 수 등의 기법을 사용하여 이러한 문제를 완화할 수 있다.
불안정성	데이터의 작은 변화도 결정 트리 구조가 크게 달라지기 때문에 의사 결정 트리는 훈련 데이터에 민감하다. 이는 배깅 또는 랜덤 포레스트와 같은 앙상블 방법을 사용하여 해결할 수 있다.
불균형한 데이터 집합으로 인한 편향성	데이터셋이 불균형 할 경우 의사 결정 트리는 다수 클래스를 향해 편향될 수 있다. 클래스 가중치, 과소표본추출(Under-sampling) 또는 과대표본추출(Over-sampling) 등의 기법을 사용하여 이 문제를 완화할 수 있다.
탐욕 알고리즘	의사 결정 트리 구축 알고리즘은 일반적으로 탐욕 알고리즘이므로 각 노드에서 지역적인 최적화(Local optimization)를 하므로 전역적(Global)으로 최적의 트리를 만들지 못할 수 있다.

 

 

참고 자료

 

[1] 한 권으로 끝내는 <머신러닝 노트> 

[2] Must Learning with R

[3] 디지털 비지니스와 아홉가지 기반 기술

[4] https://process-mining.tistory.com/42

[5] https://tempdev.tistory.com/56