결정트리

• 일정한 규칙으로 계층 및 구역을 나누어서 여러가지 예측 공간을 만드는 것.
• 모든 분할의 경우의 수에서 최적의 분할 규칙을 만족시키는 것은 불가능 -> CART 알고리즘 사용

CART (Classification And Regression Trees) 알고리즘

• 항상 Binary split
• 전체 최적 트리를 찾지 않고 현재 계층에서 가장 좋은 규칙을 찾는 greedy algorithm
• 정지 조건에 도달할때까지 분할된 각 예측 공간에서 재귀적으로 분할

Regression Tree 분할 규칙

오차 제곱의 합(RSS: Residual Sum of Squares)이 최소화되게 하는것.

Classification Tree 분할 규칙

• 지니 척도
• 크로스 엔트로피
• classification error rate

위의 세가지를 모두 split 하는데 사용할 수 있지만 노드의 클래스 혼합 정도를 측정하는 불순도(impurity) 지표인 지니척도와 크로스 엔트로피는 split 의 기준으로, classification error rate 는 트리의 최종 예측 성능 평가에 주로 사용됨.

위 그림에서 세 노드는 모두 Yes 를 예측함. 분할 전/후의 classification error rate 를 계산해보면
$가중평균 공식: E_{total} = \frac{N_{left}}{N} E_{left} + \frac{N_{right}}{N} E_{right}$

• $N$: 부모 노드의 전체 샘플 수
• $N_{left}, N_{right}$: 각 자식 노드의 샘플 수
• $E_{left}, E_{right}$: 각 자식 노드의 분류 오류율

분할 전 $= 20\%$, 분할 후 $= 20\%$

으로 분할 전과 후의 classification error rate 가 달라지지 않았음.

그러나 지니 척도로 계산 시

분할 전 $= 32\%$, 분할 후 $\approx 26\%$

으로 낮아지는 것을 볼 수 있음.

Tree Pruning (가지치기)

트리의 계층이 깊을수록 분기가 많아지기때문에 과적합되어 일반화 성능이 떨어질 가능성이 크다. 이를 해결하기 위한 가장 간단한 방법은 계층이 너무 깊어지지 않게 제한하는 것이지만 이 방식의 문제는 성능이 좋은 분기점이 발생하기 전에 학습이 중단될 수 있다는 것이다. 더 좋은 방법은 계층이 깊은 큰 트리를 만든 이후 마치 나무에서 가지를 치듯 불필요한 분기를 통합하는 것.
하지만 여기서 불필요한 분기인지는 어떻게 판단할 수 있을까?

단일 트리의 장점

• 모델이 데이터를 어떻게 나누었는지 규칙을 확인할 수 있기때문에 해석이 쉬움
• 선형회귀처럼 수치간 거리를 사용하지 않고 임계점을 기반으로 분할하기에 관측값의 스케일링이 필요 없음
• correlation 이 큰 특성들은 하나의 특성에서 기준한 규칙으로 나누었을 때 자연스럽게 함께 분리되기에 다중공선성에 내성이 있으며 연관되어있는 특성끼리 자연히 묶이게 됨
• 선형회귀는 모델을 아래와 같은 수식으로 표현하는데 이는 특성간 독립적이라는 것을 가정
  $y(x,w) = w_0 + w_1 x + w_2 x^2 + w_3 x^3 + \cdots + w_M x^M$
  그러나 현실에서는 특성간 관련성이 있는 경우가 매우 많다(예시:위치 좌표 <-> 습도). 결정 트리 구조는 구조상 계층적 분기를 통해 하위 분기가 상위 분기의 의미를 내포하기때문에 특성간 관련성을 자동으로 학습.

단일 트리의 단점

• 학습 데이터가 조금 바뀌면 트리 구조가 크게 바뀜 => 학습 데이터에 따른 트리의 분산이 큼
• greddy algorithm 을 사용하기에 최종 학습된 트리의 성능이 최고의 성능을 낸다고 보장할 수 없음
• 데이터의 분할이 $X_j < s$ 형태로 이루어지기 때문에 특성축과 평행한 경계만 형성 가능. 특성과 관측값이 증가/감소 등의 선형관계를 가지면 계단식으로 표현할 수 밖에 없으며 이마저도 선형회귀모델보다 성능이 떨어짐
  

Bootstrap Aggregation (Bagging)

• 결정 트리는 training data set 에 따라 학습된 트리 모양의 차이가 큰게 단점.
• 이를 개선하기위해 CV 를 하듯이 여러개의 training set 으로 나누고 set 의 수만큼 학습된 트리를 만든 후 타겟이 범주형이라면 각 트리 결과의 다수결을, 수치형이라면 평균을 return 함.
• 배깅 방식의 단점은 기존 단일 결정트리에서 바로 확인 할 수 있었던 노드의 분할 기준을 통한 해석의 용이성이 사라졌다는 것.
• 그러나 지니 척도를 사용하여 특성의 중요도를 얻을 수는 있음

Random Forest

• 배깅 방식의 또 다른 문제점은 배깅을 통해 학습되는 모든 트리는 데이터 셋을 샘플링을 했기 때문에 데이터 셋 안의 특성은 모두 같다는 것이다.
• 만약 특성들 중 타겟에 큰 영향을 미치는 특성이 있으면 모든 트리들은 학습할 때 큰 영향의 특성을 기준으로 먼저 분리를 시작한다.
• 이는 비슷한 구조의 트리들을 만들게 되고, 결국 단일 트리의 큰 분산을 줄이기 위한 장치들의 효율을 떨어뜨리는 결과를 낳게 된다.
• Random forest 는 노드 분할을 위한 기준을 찾을 때 데이터의 모든 특성을 확인하는 것이 아니라 임의로 선택한 특성만 사용하여 그 특성 중 분할에 가장 유리한 기준을 세워서 노드를 분할함. (이런 방식은 각각의 노드 분할때마다 이루어짐)

Boosting

• 첫번째 트리는 일반 트리와 동일하게 학습함
• 두번째 트리부터는 이전 트리의 틀린 부분을 보완함

AdaBoost

(이전 트리에서 틀린 부분에 가중치를 높혀 다음트리에서 가중치 높은 타겟을 더 잘 맞추도록 학습한다는데 정확하게 모르겠음)

Gradient Boosting

• 두번째 트리부터는 이전 트리의 오차 그 자체를 예측하도록 학습함.
• 오차를 줄여나가는 부분에서 Gradient Descent(경사하강법)을 사용하기때문에 이름도 gradient boosting.

예시

Train X = 5, Train Y = 10 일 때

1. 첫번째 트리가 x=5 에 대하여 y = 8 이라고 예측함
2. 두번째 트리는 10(실제 값) - 8(예측 값) = 2 를 학습하여 x=5 로 입력되면 예측은 2가 됨
3. 최종적으로 학습된 모델에 x = 5를 넣으면
   첫번째 트리 $f_1(5) = 8$
   두번째 트리 $f_2(5) = 2$
   여기서 learning rate $\gamma$ 가 0.1 로 설정했다면 최종 결과 predict Y는
   $F(5) = 8 + (0.1 \times 2) = 8.2$

XG Boost

Light GBM

Cat Boost

reference

• James, G., Witten, D., Hastie, T., & Tibshirani, R. (2013).
  An Introduction to Statistical Learning: with Applications in R.
  New York: Springer.