의사결정나무(Decision Tree) (2)

1. 재귀적 분할 알고리즘

 

2. 분류 나무 : CART

- Breiman 등이 개발

- 종류 : 분류 나무, 회귀 나무

- 분리 : 이진 분할

- 가지치기 (교차 타당도) : 학습 데이터로 나무 생성, 검증용 데이터로 가지치기

- 불순도 알고리즘 : Gini index (불확실성) 는 낮아지는게 좋음

 

3. 분류 나무 : C4.5

(1) C4.5, C5.0

- Quinlan 등이 개발

- 종류: 분류 나무, 회귀 나무

- 분리: 다중 분할

- 불순도 알고리즘: 엔트로피(불확실성), 정보이론, 정보이론 이득률

- 가지치기 (교차 타당도) : 학습 데이터만 이용하여 나무 성장 및 가지치기 수행

- 정보 이론 → 엔트로피

$log_2로 계산하지 않는 이유$ → bit 수로 정보 계산

$-log_2로 계산하는 이유$ : $log_2(1/2)$ = -1이기 때문에 +로 전환 필요

- 정보 이익(IG : Informatioin Gain) : 정보의 가치가 높아야 있음.

IG = E(brefore) - E(After)

 

(2) 정보 이득율 (information gain ratio)

- C4.5에서는 information gain → information gain ratio 추가 도입

- 가지수가 많을수록 information gain이 높아지는 경향을 보임

이진분할 vs 다중분할

- 단점 보완 위해 iV(instructive Value)를 도입하여 정보 이득율을 정규화

가지가 많으면 감점

- 이득율

 

 

4. 분류 나무

(1) 끝없는 분할의 단점

1) 과적합 (Overfitting)

- 학습용 데이터에 완전히 적합

- 학습용 데이터에 잡음도 포함되므로 케스트 데이터에서 오차는 일반적으로 증가

2) 과적합 피하는 방법

성장 멈추기 (Stop condition)

- 나무 모델의 깊이 파라미터로 설정

- 나무 모델을 성장시키면서 특정 조건에서 성장을 중단

- 노드 내의 최소 관측치의 수

- 불순도 최소 감소량 (CHAID에서 사용, 가지치기 사용하지 않고 종료)

 

가지치기 (Pruning)

완전 모형 생성 후 가지치기

데이터 버리는 개념 아닌 합치(merge)는 개념

나무 모델 생성 후 필요 없는 가지 제거

성장 멈추기보다 성능 우수

가지치기 비용함수를 최소로 하는 분기를 찾음

(2) 모델 학습의 목적

(잘못된 학습) 학습용 데이터에서는 높은 성과 → 평가용 데이터에서는 낮은 성과

(올바른 학습) 현재 데이터의 설명 → 미래 데이터 예측