[ML][Ensemble] Random Forest(랜덤 포레스트), OOB(Out Of Bag)

Random Forest를 공부하기 전 앞서 봤던 Bagging에 대해 더 알아보고 시작해야합니다

Bagging은 Bootstrap을 통해 B개의 데이터셋을 만든다고 설명했었습니다

여기서 원래 n개의 데이터가 존재하는 데이터 셋 $X$에서 j번째 데이터 $x_j$에 집중해서 보고자합니다

1. $X$에서 임의의 데이터 추출 => 첫번째 Bootstrap 데이터 셋의 첫번째 Observation

여기서 $x_j$가 뽑히지 않을 확률 : $1 - \frac{1}{n}$ 

 

2. $X$에서 임의의 데이터 복원 추출 => 첫번째 Bootstrap 데이터 셋의 두 번째 Observation

여기서 $x_j$가 뽑히지 않을 확률 : $1 - \frac{1}{n}$ 

 

이 과정을 n번 반복하여 첫번째 Bootstrap 데이터 셋의 n번째 Observation까지 추출을 완료하면 첫번째 Bootstrap 데이터셋이 완성됩니다

 

이 때 n이 충분히 크다면 첫번째 Bootstrap 데이터셋에서 $x_j$가 포함되지 않을 확률은 아래와 같습니다

$$\underset{n \rightarrow \infty}{\lim} (1-\frac{1}{n})^n = \frac{1}{e} \approx \frac{1}{3}$$

즉, B개의 Bootstrap 데이터셋을 생성했을 때, $x_j$를 포함하지 않는 Bootstrap 데이터 셋의 비율이 대략 $\frac{1}{3}$이 된다는 것과 같습니다

---

OOB(Out - Of - Bag) Error Estimation

OOB(Out - Of - Bag)

OOB란 하나의 Bagged Tree를 학습할 때 사용되지 않은 샘플들을 의미합니다

위에서 보았듯이 대략 $\frac{1}{3}$의 샘플들은 사용되지 않고, 대략 $\frac{2}{3}$의 샘플들만으로 학습을 합니다

OOB Prediction

i번째 샘플이 포함되지 않은 Bootstrap 데이터 셋으로 학습된, 대략 $\frac{B}{3}$개의 Tree들의 i번째 샘플에 대한 예측(평균, Majority vote)

OBB Error

각 샘플들의 OOB Prediction을 통해 얻은 Error

이는 Test Error에 대한 유효한 추청값이 될 수 있습니다

이는 교차검증, 검증 데이터셋을 사용하는 다른 ML 모델과 달리 쉽게 Test Error를 추정할 수 있다는 장점이 있습니다

(Bagging을 사용한 Random Forest Model의 성능을 평가하는 중요한 지표가 됩니다)

---

Random Forest(랜덤 포레스트)

이제 Bagging을 사용한 Random Forest 모델입니다

Bagged Tree를 사용한 Model은 여러 Tree들의 결합이므로 Bagged Tree Model의 분산은 각 Tree의 분산 + 공분산입니다

이 때, Bagged Tree는 복원추출이므로 각 Tree가 독립이라 하기 어렵기 때문에 공분산이 0이 되지 못하게 됩니다

따라서, 전체 Model의 분산이 커질 수 있다는 단점이 있습니다(분산오류 증가)

 

Random Forest는 이러한 Bagged Tree 사이의 상관관계를 없애 성능을 향상시킨 모델입니다

원래 p개의 Feature가 존재한다면, 이를 모두 고려하여 Split을 결정해 Decision Tree를 학습합니다

 

하지만 강력한 Feature가 존재한다면, B개의 모든 Tree가 Top Split을 이 Feature를 기준으로 사용할 것이기 때문에 Tree들 사이의 상관관계가 커지게 됩니다

상관관계가 커지게 된다면 각 Tree 간의 공분산이 커지게 되므로, 분산오류를 크게 줄이지 못합니다

$$Var(\frac{Z_1+Z_2 + \cdots Z_n}{n} = \bar{Z}) = \frac{\sum \limits_{i=1}^{n} Var(Z_i) + 2 \sum_{i\le i \lt j \le n}Cov(Z_i, Z_j)}{n^2}$$

(이 때 공분산은 $Cov(X, Y) = E[XY] - \mu_X \mu_Y$, 상관계수는 $Corr(X, Y) = \frac{Cov(X, Y)}{\sigma_X \sigma_Y}$ 입니다)

 

따라서 Random Forest는 이러한 상관관계를 줄이고자 p개의 Feature 중 m개를 랜덤하게 선택해 Decision Tree를 학습합니다

상관관계가 줄어든 결정 트리를 사용하기 때문에 분산 감소 효과가 증폭됩니다

일반적으로, $m \approx \sqrt{p}$값을 사용할 때 효과가 제일 좋습니다