[ML] Decision Tree

이정연·3일 전

ML

목록 보기

5/7

공부 기록

기본 프로세스

의사결정나무 - 데이터를 뿌리부터 잎까지 순차적으로 분기함
- 구성 성분(헷갈리는 것만 정리함)
  - 끝 마디: 자식 마디가 없는 마디
  - 중간 마디: 부모/자식 둘다 있는 마디
  - 가지: 뿌리 마디에서 끝 마디까지 중 가능한 경로 중 하나
  - 깊이: 가지 중 가장 많은 마디의 수
- 분류와 회귀 둘다 사용 가능
CART 알고리즘:
- 회귀
  1. 가능한 분할을 모두 탐색한다
  2. 가능한 분할 중 하나를 고정한다. (평균으로 구역 나눔)
  3. 고정된 분할에 대해 예측값을 계산한다.
  4. 오차가 더 작은 분할을 선택한다. ( = 분산 감소량이 많다)
- 분류
  1. 가능한 분할은 정해져 있다.
  2. 고정된 분할에 대해 예측값 계산한다.
  3. 오차가 더 작은 분할을 선택한다.
의사결정나무에서 결정해야 할 것
- 어떤 속성으로 분할할 것인가?
- 언제까지 분할할 것인가? (default: 분류 후 집합이 한 클래스로 몰리면 종료)

분할 속성 선택

; 어떤 속성으로 분할할 것인가?

Regression

: 가장 분산 감소량이 많은 속성 선택 → 표준편차를 줄이는 방향으로

모든 피처에 대해서 $S(T, X)$ 구하고, 가장 분산 감소량이 많은 $X$ 를 선택함
$S(T, X) = \sum\limits_{c\in X}P(c)S(c)$

Classification

: 가장 정보 이득이 큰 속성 선택 (*정보 이득 계산, 지니계수 계산 시험에 나옴 바오피셜)

정보 엔트로피
- 샘플 집합의 순도 측정
- 샘플 집합 D의 속성 값 중 k번째 클래스 샘플이 차지하는 비율 p_k 일 때 정보 엔트로피 $Ent(D)= -\sum\limits_{k=1}^{|Y|}p_klog_2p_k$
- Ent(D)의 값이 작을수록 D의 순도는 높아짐 → 작을수록 좋은 값
  - 순도가 100%: 정보 엔트로피 = 0
  - 순도가 50%: 정보 엔트로피 = 1 ⇒ 제일 헷갈리는 상태
정보 이득: Ent(D)가 줄어든 정도
$Gain(D,a) = Ent(D)-\sum\limits_{v=1}^V \frac{|D^v|}{|D|}Ent(D^v)$
- Ent(D): 원래 엔트로피 → 안나뉘어져 있을 때
  
  ⇒ 가장 정보 이득 큰 속성을 선택! (ID3의 분할 속성 선택 방법)
  
  정보 이득이 크다 == 불확실성이 크게 줄어든다
  
  *ID3
1. 루트노드에서 시작해서
2. 모든 속성(*feature)에 대해 정보이득 계산
3. 가장 정보이득이 큰 속성을 기준으로 분할
4. 각 자식 노드에서 과정 재귀적으로 반복함
정보 이득율
- 정보 이득 규칙은 취할 수 있는 값의 수가 비교적 많은 속성에 유리함. → 이렇게 되면 샘플 하나하나가 고유한 값 하나씩에 대응할 수 있음 ⇒ 정보 이득은 증가하지만 오버피팅 위험
- $Gain\ ratio (D,a) = \frac {Gain(D, a)}{IV(a)}$
- $IV = -\sum\limits_{v=1}^V \frac {|D^v|}{|D|}log_2\frac {|D^v|}{|D|}$
- 속성 a가 취할 수 있는 값의 수가 많아질 수록 IV의 값이 커짐 → 패널티 효과
지니계수 (얼마나 불평등한가?)
- 집합 내 순도를 측정하는 다른 방법
- 지니값: 집합 D에서 임의의 두 샘플을 골랐을 때, (복원 추출 했을 때) 고른 두 샘플이 서로 다른 클래스일 확률. $Gini(D) =\sum\limits_{k=1}^{|Y|}\sum\limits_{k'\ne k}p_kp_{k'} = 1-\sum\limits_{k=1}^{|Y|}p_k^2$
- 지니값이 작을수록 D의 순도가 높음 → 지니값은 작을수록 좋다.
- 지니계수 $Gini\ index(D) =\sum\limits_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v)$

가지치기

; ‘멈춘다’ 는 의미

의사결정나무의 과적합
- 과도한 반복 → 가지 수 많이 만들어냄 → 훈련 셋 자체를 기억해버리면 안됨

사전 가지치기

분할 전 미리 예측하여 노드 분할이 트리의 일반화 성능을 향상시킬 수 있다면 분할, 아니면 분할 정지 *일반화 성능: 훈련 데이터셋이 아닌 검증 데이터셋으로 알 수 있음
장점
- 의사결정트리가 많은 가지를 뻗지 못하도록 함.
- 훈련 시간과 테스트 시간 크게 줄여줌
단점
- 일반화 성능을 잠시 낮추더라도 계속되는 분할을 통해 일반화 성능 향상시킬 가능성 사전에 차단
- 과소적합 위험 증가