6. 의사결정트리(Decision Tree)

의사결정트리란?

일련의 분류 규칙을 통해 데이터를 분류, 회귀하는 지도 학습 중 하나
특정 기준(질문)에 따라 데이터를 구분하는 모델
한번의 분기 때마다 변수 영역을 2개로 구분
- Root Node : 가장 처음 분류 기준
- Intermediate Node : 중간 분류 기준
- Leaf Node : 맨 마지막 분류 기준
Leaf Node가 가장 섞이지 않은 상태로 완전히 분류해 복합성(Entropy)를 낮도록 만드는 것이 목표

가장 데이터를 잘 구분할 수 있는 기준 설정
각 범주에서 다시 데이터를 가장 잘 구분할 수 있는 기준 설정
- 각 테스트는 하나의 특성에 대해서만 이루어지므로 나누어진 영역은 항상 축에 평행
각 분할된 영역(결정 트리의 Leaf)가 하나의 클래스 or 회귀분석 결과를 가질 때 까지 반복
- target 하나로만 이루어진 Leaf Node = Pure Node
- 지나치게 많이 반복할 경우 Overfitting이 됨

결정트리에서 분기 기준을 선택하기 위해 불순도라는 개념을 사용
- 복잡성을 의미
- 해당 범주안에 서로 다른 데이터가 얼마나 섞여 있는지를 의미
분기 기준을 설정할 시, 현재노드의 불순도에 비해 자식 노드의 불순도가 낮아지게 기준을 설정 해야 함
현재 노드의 불순도와 자식 노드의 불순도의 차이 = 정보획득(Information Gain)

I(A) = 1 - \sum^m_{k=1}p_k^2

E(D) = -\sum^k_{i=1}p_i\;log_2(p_i)

p_k = \frac{|k-class\;set\;in\; sample|}{sample}

결정트리 구성 단계 예시

1. Root Node의 불순도 계산

$E(경기) = -\frac{9}{14}log_2(\frac{9}{14}) - \frac{5}{14}log_2(\frac{5}{14}) = 0.940$

2. 나머지 속성에 대해 분할 후 자식노드의 불순도 계산

3. 각 속성에 대한 정보 획득 계산 후 정보획득이 최대가 되는 분기 조건 찾기

4. 모든 Leaf 노드의 불순도가 0이 될 때까지 반복 수행

Leaf Node가 한 가지 범주만을 가지게 되는 Pure Full Tree를 형성

과적합 문제로 인해 성능 저하가 발생하기 때문에 가지치기가 필요

의사결정트리를 사용하면 Leaf Node가 한 가지 범주만을 가지게 되는 Pure Full Tree를 형성하지만 과적합 문제로 인해 성능 저하가 발생하기 때문에 가지치기가 필요
결정트리의 특정 노드 밑의 하부 트리를 제거하여 성능을 높이는 효과

CC(T) = Err(T) + \alpha × L(T)

장점
- 전처리를 하지 않아도 된다.
- 수치형과 범주형 변수를 동시에 다룰 수 있다.
단점
- 샘플의 사이즈가 크면 효율성 및 가독성이 떨어진다.
- 한 번에 하나의 변수만을 고려하기 때문에 변수간의 상호작용 파악이 어렵다.
- 모든 단계마다 기준값의 선택이 중요하다.
- 각 예측 변수의 효과 파악이 어렵다.

딥러닝 지식의 백지에서 깜지까지