Random Forest

 

Introduction

*bagging: 데이터 셋을 독립적으로 생성하는 데 있어서 복원추출을 사용하는 방법론.

그렇게 복원 추출된 bootstrap에다가 variance가 높고 bias가 낮은 알고리즘(= 복잡도가 높은 알고리즘)을 개별적으로 학습시켜 최종적으로 결합하게 되면 효과를 봅니다.

 

• Random forest는 이 bagging의 특수한 형태입니다.
• Random forest는 반드시 decision tree를 base learner로 봅니다.
• 의사결정나무 알고리즘 여러개를 학습시켜 결합하게 되면 forest가 됩니다.
• Random forest는 ensemble의 다양성을 확보하기 위한 두가지 메커니즘을 갖고 있습니다.
  • bagging
  • 변수를 랜덤으로 선택한다.

Algorithm

• bootstrap size t만큼의 random sample을 만듭니다.
• 변수를 split 할 때 해당하는 영역을 분할하는 과정에서 원래 p개의 변수 중에서 m개의 변수만을 선택합니다.
  • e.g., 이번 영역에 대한 data를 분할할 때는, $x_1$만 사용한다. $x_2$는 사용하지 않는다. 이렇게 제약을 하는 것을 의미합니다.
• 이렇게 해서 의사결정 나무를 만들고 결과를 결합한다.

More detail

• 위 그림에서 왼쪽으로 가는 게 training data이고 오른쪽이 OOB data입니다.

 

Randomly selected variable

• bootstrap을 통해 선택된 데이터 셋이 있습니다. X는 25차원의 데이터입니다.
• bagging tree: bagging을 한 각각의 bootstrap에다가 모든 변수를 사용해서 의사결정나무를 쓰는 것입니다.
  • bootstrap을 이용하여 random으로 sampling한 후 decision tree 한개를 만듭니다.
  • 이 과정을 여러번 반복합니다.
  • 이 결과들을 하나로 묶으면 bagging tree라고 할 수 있습니다.
  • 이때, $T_1$, $T_2$, ..., $T_B$의 결과는 거의 비슷합니다. (왜냐면 같은 dataset에서 random sampling 한 것이기 때문입니다.)

• random forest는 위와 같은 그림이 있을 때 bootstrap을 사용한 후 -> random variable selection을 거치고 -> decision tree를 만듭니다.
• 변수 선택이 들어갔기 때문에 개별 tree의 성능은 떨어지지만, 이를 여러 개의 tree로 묶으면 성능이 올라갑니다. (이게 random forest의 재밌는 점입니다.)

 

Generalization Error (일반화 성능)

$Generalization\ Error\leq\frac{\bar\rho(1-s^2)}{s^2}$

• 여기서, $\rho$는 각각의 tree들이 갖고 있는 결과들의 상관관계이고,
• $s^2$는 얼마나 정확한지 나타내는 지표입니다.
• 따라서 알고리즘이 정확할수록 $s^2$는 높아지고, 개별 모델의 다양성이 높을수록 $\rho$는 낮아집니다.
• 즉, 개별 모델들이 성능이 높고, 그 모델들이 서로 연관성이 낮을수록 일반화 성능이 좋아집니다.

 

 

Variable Importance

 

• Random Forest의 장점은 변수의 중요도를 산출할 수 있다는 것입니다.
• dataset에서 bootstrap을 사용해 tree를 만들고, 남은 OOB data를 이 tree에 적용합니다.
  • train data를 재사용하지 않으면서 validation을 할 수 있습니다.
• $e_i$는 원래 OOB 데이터에 넣었을 때 에러입니다. $p_i$는 OOB data에서 중요도를 산출하고자 하는 $x_i$를 permutation 한 것의 에러입니다.
• 만약 $x_i$가 split에 사용되지 않았으면, $p_i$는 $e_i$와 같습니다. 왜냐면 그 변수를 사용하는 과정에서 tree에 한번도 사용되지 않았기 때문입니다.
  • 이를 다시 말하면 i번째 변수는 중요하지 않은 변수라는 것을 뜻합니다.
• $x_i$가 split에 자주 사용될수록 $p_i>e_i$가 될 것입니다. 왜냐면 random으로 permutation해서 정보를 뒤죽박죽 바꿔버렸기 때문입니다. 따라서 바뀌기 전의 데이터의 변수를 갖고 만든 모델이 망가져버린 것입니다.
• 정리하면, 둘 사이의 차이 ($p_i-e_i$)가 크면 클수록 중요한 변수로 판단합니다.

Example

• 예를 들어, 위에서 보이는 것처럼 원래 값인 $x_i$를 permutation 합니다.
• 만약 변수 i가 tree를 split 하는 데 한 번도 사용되지 않았다면, 즉, $x_1$, $x_2$, $x_7$만 사용되고 $x_i$는 사용되지 않았다고 하면, 원래 OOB data를 이용한 orginal 에러율 $e_i$와 permutation 시킨 $p_i$가 같아집니다.
• 그렇기 때문에 tree를 split 하는 데 사용되지 않은 변수라면 중요하지 않은 변수라고 할 수 있습니다.

• 이번에는, $x_i$가 여러 곳에서 사용된 중요한 변수라고 하겠습니다.
• 그렇다면 정보를 뒤죽박죽 섞었기 때문에 원래 OOB data의 에러율인 $e_i$보다 permutation시킨 에러율 $p_i$가 훨씬 크게 나타날 것입니다.

 

• m번째 tree에서 변수 i에 대한 random permutation 전후 OOB error의 차이는 아래와 같습니다.

$d_i^m=p_i^m-e_i^m$

• 전체 Tree들에 대한 OOB error 차이의 평균 및 분산입니다.

$\bar{d}_i=\frac{1}{m}\sum_{i=1}^m d_i^m$, $s_i^2=\frac{1}{m-1}\sum_{i=1}^m (d_i^m-\bar{d}_i)^2$

• i번째 변수의 중요도입니다.

$v_i=\frac{\bar{d}_i}{s_i}$

-> 평균이 높고 분산이 낮을수록 변수의 중요도는 올라갑니다.

 

 

[출처] : https://www.youtube.com/watch?v=nu_6PB1v3Xk&list=PLetSlH8YjIfWMdw9AuLR5ybkVvGcoG2EW&index=24