Tree-based Model, Bagging

랜덤포레스트가 뭐길래? 회의에서 당당하게, 수식없이 알아보자

$ f(X) = \sum_{m} c_m * I(x \in R_m) $
Objective function : $ \sum_{J} \sum_{i \in R_j} (y_i-\hat{y}_{R_j})^2 $

• 설명변수 공간, $ X_1, ..., X_p $ 에 대한 가능한 값들의 집합 → J개의 다르고 겹치지 않는 영역 $ R_1, ..., R_j $ 로 분할
• 영역 $ R_j $ 에 속하는 모든 관측치들에 대해 동일한 예측, 예측값은 $ R_j $ 의 training 관측치들에 대한 반응변수 값의 평균

분할의 모든 경우 다 고려하는 것은 현실적으로 불가능 : top-down greedy 방법 사용
다음 식을 최소로 하는 j와 s 값 :
$ \sum_{i:x_i \in R1=\{X|X_j<s\}}(y_i-\hat{y}_{R_1})^2 + \sum_{i:x_i \in R2=\{X|X_j\geq s\}}(y_i-\hat{y}_{R_2})^2 $

cost complexity prunning (weakest link prunning) 가지치기
Cost Function = Err(T) + $ \alpha $ |T| , |T| : 터미널 노드 수
Full Tree에서 hyperparameter $ \alpha $ 에 의해서 비용함수를 최소로 하는 SubTree 선택 (0이면 Full Tree)
$ \alpha $ 는 검증셋 또는 교차검증 사용해서 선택

https://ratsgo.github.io/machine%20learning/2017/03/26/tree/
https://danbi-ncsoft.github.io/study/2018/12/06/entropy.html
그냥 오분류율은 충분히 민감하지 않아 다른 measure(불순도)가 선호됨.
분할전 Gini Index $ \sum_{j=1}^{J} p_j(1-p_j) $ , j:변수가 가지는 Class 수
분할후 $Gini.Index(A) = \sum _{ i=1 }^{ d }{ { \left( { R }_{ i }\left( 1-\sum _{ k=1 }^{ m }{ { p }_{ ik }^{ 2 } } \right) \right) } } $
분할전 Entropy $ -\sum _{ k=1 }^{ m }{ { p }_{ k }\log _{ 2 }{ { (p }_{ k }) } } $
분할후 $ Entropy(A)=\sum _{ i=1 }^{ d }{ { R }_{ i } } \left( -\sum _{ k=1 }^{ m }{ { p }_{ k }\log _{ 2 }{ { (p }_{ k }) } } \right) $ (Ri=분할 전 레코드 가운데 분할 후 i 영역에 속하는 레코드의 비율)
분할전 → 분할후 줄어드는 양이 큰 변수분할 선택

• 심지어 선형회귀보다 설명하기 쉽다
• 인간의 의사결정 과정을 더 밀접하게 반영한다고 생각된다 (적어도 일부 사람들에게)
• 그래픽으로 나타내기 쉽고, 비전문가도 쉽게 해석할 수 있다.
• 가변수들을 만들지 않고 질적 설명변수들을 쉽게 처리할 수 있다.
• 변수 정규화, 표준화 등 안해도 된다

예측 정확도가 낮다.
trees are inherently high-variance,
the bushier they are, the higher the variance.

분산이 각각 $ \sigma^2 $ 인 n개의 독립적인 관측치 $ Z_1, ... , Z_n $ 의 평균 $ \bar{Z} $ 의 분산은 $ \sigma^2/n $. 즉, 관측치들의 집합은 평균하는 것은 분산을 줄인다.

• 자연스러운 방법은 모집단으로부터 많은 수의 training 셋을 취하고, 각 training 셋으로 별도의 예측 모델을 만들어 예측 결과들을 평균하는 것
  • 하지만 다수의 training set을 일반적으로 가질 수 없다
• 단일 훈련자료로부터 반복하여 표본들을 샘플링함으로써 bootstrap.

$ \hat{f}_{bag}(x) = {1\over B} \sum \hat{f}^{*b}(x) $ (평균 or voting)

with positive pairwise correlation $ \rho $, the variance of the average is $ \rho \sigma^2 + {{(1-\rho)}\over{B}} \sigma^2 $

하지만 각각 독립인 것은 어떻게? → Random Forest

트리들의 correlation을 줄여줌. 상관성을 제거(decorrelate) 간단한 방법으로 배깅된 트리들보다 더 나은 성능을 제공
배깅에서와 마찬가지로 Bootstrap된 훈련 표본들에 대해 다수의 Decision Tree를 만든다. 그러나 트리 내에서 분할이 고려될 때마다 p개 설명변수들의 전체 집합에서 m개 설명변수들로 구성된 랜덤표본이 분할 후보로 선택된다.

• tree 수 B, 각각 나무에서 선택하는 feature 수 m < p
  • 트리의 수 B는 배깅에서 결정적(critical) 파라미터는 아님. 아주 큰 B 값을 사용해도 과적합이 일어나지 않을 것.
  • m = p 를 사용하여 만들면 단순히 배깅.
  • 보통 $ m \approx \sqrt{p} $ 를 사용. (regression의 경우 p/3)
  • 자료 하나의 매우 강한 설명변수가 다수의 적당히 강한 설명변수와 함께 있다고 해보자. 그러면, 배깅된 트리들의 컬렉션에서 대부분 또는 모든 트리들이 이 강한 설명 변수를 맨 위의 분할(top split)에서 사용할 것. 그 결과 배깅된 트리들은 모두 서로 상당히 유사하게 보일 것.
• Bootstrap : 보통 전체 데이터세트 크기의 80%, 기술적으로 세번째 hyperparameter
• minimum node size (terminal node의 data수) : classification 1, regression 5 (R randomForest PKG의 기본 값)

각각의 배깅된 트리는 평균적으로 관측치들의 약 2/3을 이용. ''5장 2번 연습문제?''
limit 설명
각 Bootstrap 표본의 개수가 n 일 때, j번째 관측치가 Bootstrap 표본에 있지 않을 확률은 $ (1-1/n)^n $
$ (1-1/n)^n \to 1/e $
나머지 1/3을 Out-Of-Bag (OOB) 관측치 → OOB에 대한 오차. → B가 충분히 큰 경우 OOB오차는 LOOCV 오차와 사실상 동일

• by random permutation (p번 더 계산) : OOB prediction (j-th 변수 random permutation 후 prediction → tree들의 MSE차이의 평균)
• 회귀트리들을 배깅하는 경우, 주어진 설명변수에 대한 분할 때문에 RSS가 감소되는 총량을 모든 B개 트리에 대해 평균한 값. 분류는 지니 지수가 감소되는 총량의 평균.

Random Seed 따라 결과 값이 달라질 수 있다.
변수의 수가 늘어나면, 특히 예측과 크게 상관없는 변수들이 많으면, 성능 저하
학습 뿐 아니라, 실제 예측 시간. Many Tree 계산 필요
High Dimension, Sparse Data (text) 에 약함

adaptive nearest-neighbor estimator 로 해석될 수 있음

(extremely randomized trees)
https://velog.io/@nata0919/Extra-Trees-%EC%A0%95%EB%A6%AC
극도로 무작위화(Extremely Randomized)된 기계 학습 방법
데이터 샘플 수와 특성 설정까지 랜덤

1. 관측치를 부트스트랩하지 않고
기본적으로 bootstrap = False 로 여러 트리를 구축한다 . samples are drawn without replacement
In sampling without replacement, each sample unit of the population has only one chance to be selected in the sample.
2. 노드는 최상의 분할이 아닌 임의의 분할로 분할된다 .
노드는 모든 노드에서 선택된 기능의 무작위 하위 집합 간의 무작위 분할을 기반으로 분할된다.
출처: https://goatlab.tistory.com/entry/Machine-Learning-ExtraTree [GOATLAB:티스토리]

편향과 분산 차이
엑스트라 트리는 모든 데이터를 사용하기 때문에 랜덤 포레스트에 비해 편향이 감소함
무작위 선택의 영향으로 분산 또한 감소

속도
엑스트라 트리는 데이터를 랜덤 분할 후 선택함
최적의 분할을 계산하지 않아서 속도가 빠름