====== Tree-based Model, Bagging ====== [[blog:easy_random_forest]] ===== Decision Tree ===== ====Regression Tree==== $ 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 관측치들에 대한 반응변수 값의 평균 === Fitting === 분할의 모든 경우 다 고려하는 것은 현실적으로 불가능 : top-down greedy 방법 사용 다음 식을 최소로 하는 j와 s 값 : $ \sum_{i:x_i \in R1=\{X|X_j 분할후 줄어드는 양이 큰 변수분할 선택 ==pros== * 심지어 선형회귀보다 설명하기 쉽다 * 인간의 의사결정 과정을 더 밀접하게 반영한다고 생각된다 (적어도 일부 사람들에게) * 그래픽으로 나타내기 쉽고, 비전문가도 쉽게 해석할 수 있다. * 가변수들을 만들지 않고 질적 설명변수들을 쉽게 처리할 수 있다. * 변수 정규화, 표준화 등 안해도 된다 ==cons== 예측 정확도가 낮다. trees are inherently high-variance, the bushier they are, the higher the variance. ===== Bagging (Bootstrap AGGregation) ===== 분산이 각각 $ \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 ===== Random Forest ===== 트리들의 correlation을 줄여줌. 상관성을 제거(decorrelate) 간단한 방법으로 배깅된 트리들보다 더 나은 성능을 제공 배깅에서와 마찬가지로 Bootstrap된 훈련 표본들에 대해 다수의 Decision Tree를 만든다. 그러나 트리 내에서 분할이 고려될 때마다 p개 설명변수들의 전체 집합에서 m개 설명변수들로 구성된 랜덤표본이 분할 후보로 선택된다. ====hyperparameter==== * 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의 기본 값) ====Out of Bag 오차 추정==== 각각의 배깅된 트리는 평균적으로 관측치들의 약 2/3을 이용. ++ ''5장 2번 연습문제?'' | [[https://www.quora.com/Why-is-the-limit-1-frac-1-n-n-equal-to-frac-1-e|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개 트리에 대해 평균한 값. 분류는 지니 지수가 감소되는 총량의 평균. ==== Cons ==== Random Seed 따라 결과 값이 달라질 수 있다. 변수의 수가 늘어나면, 특히 예측과 크게 상관없는 변수들이 많으면, 성능 저하 학습 뿐 아니라, 실제 예측 시간. Many Tree 계산 필요 High Dimension, Sparse Data (text) 에 약함 ====기타==== adaptive nearest-neighbor estimator 로 해석될 수 있음 {{tag>data_analysis random_forest decision_tree bagging}} ~~DISCUSSION~~