[요약] 핸즈온 머신러닝 - 06. 결정 트리

(이진)결정트리

개념

• 매 노드마다 참 / 거짓을 분류하는 2진 트리를 만든다.
• 부모 노드는 어떤 특성에 대한 조건을 만들고 이에 대한 참 / 거짓 자식 노드를 가진다.
• 만약 자식 노드에서 참 / 거짓을 분류할 적절한 조건을 찾지 못했다면 리프노트가 되며 class 를 예측한다.
• 이 과정을 모든 자식 노드가 리프노드가 될때 까지 또는 지정한 depth 에 도달할 때 까지 반복한다.

노드의 구성

• sample : 노드에 해당하는 훈련 샘플 개수.
• value : 노드에 속한 샘플의 클래스별 개수.
• gini : 불순도.

특징

• 직관적이고, 시각적이며, 결정의 사유가 명확하다(= 화이트박스 모델).
• 데이터 전처리가 거의 필요하지 않다.
• 학습이 완료되기 전 까지 클래스의 개수를 예측할 수 없다.
• 불안정하다 
  • 샘플 데이터의 회전에 민감하다 : 서로 직교한 특성 축을 기준으로 결정 경계를 생성하므로, 축이 회전하면 학습 결과도 달라진다.
  • 학습 시 (경사하강법의 시작점 처럼 랜덤한 요소가 있으므로) 매번 결과가 달라질 수 있다.

 

분류기

CART 훈련 알고리즘

여러개의 결정 경계를 교차하여 분류기를 생성한다. 노드에 속한 샘플이 얼마나 "안 섞였는지" 를 나타내는 gini 불순도를 기준(=criterion)으로 이용하여 비용 함수를 정의한다.

지니 불순도

$G_{i}=1-\sum_{k=1}^{N}p_{i,k}^{2}$

비용함수

$J(k,t_{k})=\frac{m_{left}}{m}G_{left}+\frac{m_{right}}{m}G_{right)$
$G_{left/rigfht} = 두 서브셋의 불순도$
$m_{left/right} = 두 서비슷의 샘플수$

클래스 확률 측정

• 샘플을 결정 트리의 루트 노드에서 부터 시작해서 특정 리프노드에 속할 때 가지 분류한다.
• 클래스 k 에 속할 확률은 $\frac{value_{k}}{sample}$ 이다.
• 복잡도 = $O(\log_{2}(m))$ 로 매우 빠르다.

Criterion(기준) 의 선택

지니 불순도 외에 엔트로피를 이용할 수 도 있다. 이 경우 두 자식노드의 엔트로피를 낮추는 방향으로 결정경계를 생성해나간다.

엔트로피

$H_{i}=-\sum_{k=1}^{N}P_{i,k}log_{2}(p_{i,k})$ | 단 $p_{i,k}\neq0$

지니 불순도가 엔트로피보다 계산이 빠르다.
엔트로피가 지니 불순도 보다 샘플 분포가 고르다.

규제

• 앞서 다룬 알고리즘과 달리 결정 트리는 학습을 완료하기 전 까지 몇개의 특성을 사용할 지 모른다 (=비파라미터 모델).
• 파라미터가 모델의 데이터 구조와 밀접하게 연관 되어있다 == 과대 적합.
• 이를 막기 위해 여러가지 제약 조건을 걸어 규제로 사용한다.
  • max depth : 결정 트리의 깊이를 제한하여 과대 적합을 막는다.
  • 조건 미 충족시 클래스 무시하기 등의 제약 조건으로 결정 경계를 단순화 한다.

 

회귀

결정 트리를 회귀로도 사용할 수 있다.

비용함수

지니 불순도나 엔트로피 대신 MSE 를 Criterion 으로 사용하면 결정 경계를 기준으로 예측값을 value 로 가지는 결정 트리를 만들 수 있다.