Random Forest

https://en.wikipedia.org/wiki/Random_forest

Random forest - Wikipedia

Random Forests 혹은 Random Decision Forests는 분류classification와 회귀regression 등에 사용하기 위한 앙상블 학습의 한 종류이며 여러 개의 decision tree로 구성되어 있다.

 

분류classification를 위해서는 tree 중에 하나를 고르고, 회귀regression를 위해서는 각각 트리의 평균average or mean을 이용한다.

 

Raondom decision forest는 decision tree가 학습 데이터training data에 과적합overfitting되는 것을 보완하기 위해 탄생했다. (The Elements for Statistical Learning, Hastie et al, 2008, ISBN 0-387-95284-5) Random forests는 대체로 decision tree보다 더 좋은 결과를 내지만, 정확도accuracy가 gradient boosted tree보다 낫다. 

 

최초의 random decision forest는 1995년에 Tin Kam Ho가 만들었다.  Random subspace method를 사용했으며, Ho의 공식은 Eugene Kleinberg가 제안한 분류classification에 "stochastic discrimination"와 같이 접근 한 것과 같다.

 

Leo Breiman과 Adele Cutler가 알고리즘을 더욱 발전시켰다. 그들은 2006년에 "Random Forests"를 trademark로 등록다.

 

Ho는 Leo Breiman의 "Bagging" 개념과 feature를 임의random로 고르는 방법을 결합시켰다. 이후에 Amit과 Geman은 분산variance를 제어하여 desicion tree로 이루어진 집합체collection를 구성하는 법을 제시했다.

 

Random forests는 단순한 설정만으로도 넓은 범위의 데이터를 통해 신뢰할만한 예측을 하기 때문에 상업적인 용도로in business 자주 쓰이는 "blackbox" 모델이다.

 

 

 

Algorithm

 

Travor John Hastie는 다음과 같이 말하기도 했는데, "Tree learning은 데이터 마이닝에 적합한 기성품의 형태에 가장 가깝다. 자료를 scaling하거나 feature의 값을 다양하게 변형해도 영향을 받지 않으면서, 관련없는 feature를 포함하더라도 유효한robust 결과를 도출하기 때문이다. 그러나 정확성은 떨어진다."

 

트리는 매우 불규칙한 패턴을 학습하기 위해서 깊게 확장되며 학습training 데이터에 과적합overfit된다. 과적합되면 bias는 낮고 분산variance은 높아진다. Random forest는 여러 개의 깊은 decision tree를 평균내는 방법이다. 분산을 줄이기 위해서, 학습 데이터의 집합 내에서 부분을 추출하여 여러 차례 학습 시킨다. 이렇게 하면 bias는 약간 상승하고 해석력interpretability이 약간 상실된다. 그러나 대체로 최종 모델에서 성능이 대폭 상승한다.

 

Forest는 decision tree 학습의 효과를 한 데 모으는 것과 같다. Decision tree를 많이 모을 수록 단일 random tree의 성능은 개선된다. 비슷하지는 않지만, forest는 마치 k-fold cross validation와 비슷한 효과를 보인다.

 

 

Bagging

Bagging 혹은 Bootstrap aggregating

 

학습 데이터가 다음과 같이 주어 졌을 때,

Bagging은 전체 학습 데이터에서 샘플을 임의로 추출하여, 아래와 같은 작업을 B번 반복한다.

 

For b = 1,...,B:
1. X, Y 중에서 n개를 교체해 가며 뽑는다. 뽑힌 샘플을 X_{b}, Y_{b}라고 한다.

2. X_{b}, Y_{b}로 분류나 회귀를 트리에서 수행한다.

 

학습이 모두 끝난 이후, 

회귀 트리였다면, 관측되지 않은 샘플 x'는 모든 개별 회귀 트리에서 x'에 대한 회귀 결과를 평균 내어 구한다.

분류 트리였다면, 개별 트리의 결과를 모아서 가장 많은 수를 x'에 대한 분류 결과로 삼는다.

 

 

bias를 상승시키지 않고 모델의 분산을 감소시키므로 bootstrapping을 하면 모델의 성능이 개선된다. 다시 말하면, 개별 트리는 학습 데이터의 noise에 매우 민감하지만, 트리들 사이에 상관 관계가 없다면, 트리들의 평균은 noise에 민감하지 않다. 단순히 많은 트리들을 하나의 학습 데이터 집합에서 학습시킨다면 트리들 사이에는 강력한 연관성이 생긴다. (만약 학습 알고리즘이 deterministic 하다면 동일한 트리를 여러번 반복 시켜도 연관성이 생긴다.)

bootstrap sampling을 함으로써 트리 사이의 연관성을 약화시킨다.de-correlating

 

더하여, 불확실한 예측에 대한 추정치an estimate of the uncertainty of the prediction는 모든 개별 회귀 트리에서 예측을 한 결과에 대한 표준편차로 나타낼 수 있다.

B는 샘플이나 트리의 갯수이며, x'는 예측하고자 하는 값이다. B는 cross-validation이나 out-of-bag error를 관측하여 최적의 값으로 조정할 수 있다. out-of-bag error, 각각의 학습 샘플