[Practical Statistics for Data Scientists] A팀: Bagging and the Random Forest

Ensemble Methods

1096년, 통계학자 Francis Galton이 영국의 한 박람회를 방문했는데 여기서 소의 몸무게를 맞히기 위한 대회가 개최 중이 었다. 이 대회에서는 800개의 추측이 답안으로 제출되었는데 대부분 다른 값을 가지고 있었다. 놀라운 점은 이렇게 각기 다른 추측값 800개를 이용해 평균과 중위수를 구했더니 소의 실제 무게와 1%도 차이나지 않았다는 점이다. 즉 하나의 추측값은 실제 값과 다소 다를 수 있지만 추측 값들을 여러 개 모아 평균을 내면 좀 더 실제 값에 가까운 값을 얻을 수 있다는 것을 발견한 것이다. James Surowiecki는 그가 저술한 '군중의 지혜'에서 이 현상을 설명했다. 

현재 모델링을 할 때 이 현상을 배경으로 하는 '앙상블 기법'을 사용하는데 이는 여러 개의 모델을 만든 후 해당 모델들에서 얻은 값들을 여러 방법으로 융합해 사용하는 기법이다.

 

Bagging (앙상블 기법 중 하나)

Bagging은 bootstrap을 이용해 여러 개의 샘플 집합을 만든 뒤, 각 샘플 집합에 대해 모델을 만들고 이를 통해 얻은 결과 값을 voting해 사용하는 앙상블 기법 중 하나이다. 방금 설명한 과정을 classification에 대입해 다시 풀어보면 다음과 같다.

<Training>
1.  k 개의 bootstrap 샘플들을 만든다  -  S[1], S[2], …, S[k]
2. 각 샘플 S[i]을 이용해 k개의 서로 다른 classifier를 만든다. 이때 k개 모델은 동일한 learning algorithm을 이용해야 한다.
<Testing>
1. 얻은 k개의 classifiers의 결과를 가지고 동일한 가중치로 voting을 진행해 최종 classification 결과를 얻는다.

 

Random Forest

Random Forest 기법은 Bagging + Decision tree + 랜덤한 subspace의 attribute로 쪼개기를 동시에 적용한 기법이다. 

 

우선 자세한 설명을 들어가기 전 앞서 tree 단원에서 배웠을 decision tree의 개념을 잠시 복습해보자. 

decision tree(결정 트리)는 위 그림의 왼쪽 부분처럼 label이 있는 table 데이터가 주어지면 이를 같은 의미를 가지는 tree 형태로 바꾼 것을 말한다. 이때 결정 트리는 각 열(attribute)를 기준으로 트리를 쪼갠다. 기본적으로 하나의 table을 가지고 하나의 결정 트리를 만들 경우 최적의 트리를 만드는 법이 수학적으로 잘 알려져 있다.(entropy와 gain 이용) 즉, 해당 방법으로 구한 최적의 결정 트리는 약간의 차이가 있을 수는 있지만 거의 동일한 트리를 형성한다.

 

여기까지 결정 트리의 기본 구조를 알았다면 이제 random forest에 대해 알아보자. random forest는 '숲' 이라는 말에서 짐작할 수 있듯이 bagging 기법을 이용해 여러 개의 결정 트리를 만들어 앙상블 하는 것을 말한다. 나무를 여러 개 만들기 때문에 숲이라는 이름이 붙었다고 생각하면 된다. 그렇다면 random은 왜 들어간 것일까? 이는 random forest가 결정 트리를 만들때 랜덤성을 추가하기 때문이다. 자세한 내용은 아래 random forest 진행과정과 함께 설명하겠다.

첫 번째 과정은 bagging을 진행하기 위해 bootstrap 샘플들을 만드는 과정이다. 기본적으로 테이블 데이터셋을 많이 사용하기 때문에 original table 데이터셋에서 bootstrap을 통해 여러 개의 샘플 테이블을 얻는다. 

두 번째는 각 bootstrap 샘플에 대해 결정 트리를 만드는 것이다. 이때 바로 랜덤성이 사용된다. 기존의 트리는 트리를 쪼갤 열(attribute)을 선택 할 때 데이터셋의 모든 열 중 가장 최적인 열(가장 데이터를 label에 맞게 잘 나눌 수 있는 열)을 선택하지만 random forest에서는 열 중 특정 몇 개를 랜덤으로 선택한 후 그중 가장 최적인 열을 선택해 트리를 쪼갠다. 이는 모든 트리의 분할과정, 즉 열을 선택할 때마다 항상 동일하게 적용된다. 

 

이 방법으로 모든  bootstrap 샘플에 대해 결정 트리를 만든다. 만약 샘플이 100개였다면 100개의 결정트리가 생성될 것이다. 그렇다면 왜 굳이 랜덤성을 사용할까? 단순히 생각해보면 이미 최적의 트리를 구하는 법이 알려져 있는데도 랜덤성을 끼워 최적의 트리 100개가 아닌 성능을 보장할 수 없는 결정 트리 100개를 만든 것이나 마찬가지다. 그럼에도 불구하고 랜덤성을 사용하는 이유는 앙상블의 효과를 극대화 할 수 있기 때문이다. 만약 최적의 방법을 사용해 트리 100개를 만든다면 이는 데이터 셋은 다르겠지만 만들어진 트리의 구조는 거의 동일할 것으로 예측되므로 앙상블의 효과가 미미할 수 있다. 반면 랜덤성을 추가하면 다양성이 훨씬 풍부한 트리 100개가 만들어져 앙상블을 시행할 때 더 높은 기대효과를 얻을 수 있다. 

 

마지막으로 이렇게 해서 100개의 결정 트리를 얻었다면 bagging에서 처럼 voting을 통해 최종 label을 결정한다. 한 가지 덧붙이자면 random forest가 아주 좋은 성능을 내기 위해서는 수백~수천 개 정도의 결정 트리의 앙상블이 필요하다고 한다.