[ML] Random Forest

Reference

💻 딥러닝의 깊이 있는 이해를 위한 머신러닝 강의 4-2
🔗 랜덤 포레스트 - 위키백과

이번에 정리할 개념 Random Forest는 앞서 포스팅한 Decsion Tree와 흐름이 이어집니다. Decision tree가 뭔지 모른다면 참고하시는 걸 추천드리고, 대충 개념을 아신다면 참고 안 하셔도 됩니다.

또한, 위 Reference로 남긴 강의 내용을 바탕으로 정리하였음을 밝힙니다.

Random Forest

random forest도 머신러닝의 가장 기본적인 알고리즘 중 하나입니다.

이는 각각의 decision tree를 서로 독립적으로 학습한 다음에 decision tree에서 얻은 결과값들을 averaging하여 최종 결과를 출력하는 방법입니다.

• decision tree가 기본적으로 학습 속도가 빨라 random forest가 빈번하게 사용됩니다.
• ensemble model, averaging과 stacking이 가지는 최대 장점인 동시에 계산 가능하며 작동 속도가 빠릅니다.
• decision tree를 그대로 random forest의 한 개 모델로 사용하면 서로 다른 classifier가 비슷한 prediction을 출력합니다.
• 문제 해결을 위해 서로 다른 decision tree가 서로 다른 예측값을 출력하기 위해 Bootstrappimg과 random tree라는 두 가지 트릭을 사용합니다.

Bootstrap sampling

bootstrap sampling은 어떤 데이터셋을 만들어내는 과정입니다.

학습 데이터셋을 random하게 특정 개수만큼의 sample을 추출하고, 그 과정에서 똑같은 sample이 두 번 추출될 수 있습니다.

아웃라이어(Outlier)가 많은 환경에서 적용하기 좋으며,계산량이나 속도를 훨씬 빠르게 할 수 있습니다.

Bagging

bagging은 각각의 classifier가 서로 다른 데이터셋으로 학습되어 서로 다른 예측값을 출력하고, 그 결과값들을 모두 묶어 최종적으로 하나의 예측값을 출력하는 방법입니다.

Random trees

Random trees는 decision tree와 동일한 구조지만 splitting algorithm의 단순화에서 차이를 보입니다.

앞서 공부한 Decision Tree의 경우에는 feature 타입과 threshold를 미리 정해놓은 splitting algorithm을 기반으로 나누었습니다.

예를 들어서, 1:1 비율로 나누거나 한 개의 sample만 한쪽으로 따로 가도록 분류하는 방법 등이 있었습니다.

그런데 random forest는 feature type을 random하게 고릅니다.

그렇기 때문에 시작할 때 feature type을 정해놓고 시작하고 당연히 속도가 더 빨라집니다.

기본적으로 random tree를 새롭게 얻을 대마다 선택되는 feature type이 달라집니다.

따라서 ensemble model 내에 존재하는 여러 개의 decision trees가 모두 독립적인 classifier로 동작할 확률 가능성이 훨씬 더 커집니다.

더 쉽게 표현하자면, decision tree들 간의 의존성이 크게 줄어든다고 말 할 수 있습니다.

Bagging + Random trees

서로 다른 random tree를 학습합니다. 개별적인 random tree는 서로 다른 bootstrap 데이터셋을 기반으로 학습된 것입니다.

정리

Random forest는 다수의 decision tree를 학습하는 ensemble model입니다.

decision tree를 이용했을 때, 그 결과나 성능 변동 폭이 크다는 단점이 있어서

학습 데이터에 따라 생성되는 decision tree의 random한 성격을 일반화하기 위해 random forest 방법이 고안되었습니다.

bootstrap sampling 후 bagging하는 등의 방법을 통해 단점을 극복합니다.

위키백과의 설명을 그대로 가져오면

배깅(bagging)은 bootstrap aggregating의 약자로, 부트스트랩(bootstrap)을 통해 조금씩 다른 훈련 데이터에 대해 훈련된 기초 분류기(base learner)들을 결합(aggregating)시키는 방법이다.

부트스트랩이란, 주어진 훈련 데이터에서 중복을 허용하여 원 데이터셋과 같은 크기의 데이터셋을 만드는 과정을 말한다. 배깅을 통해 랜덤 포레스트를 훈련시키는 과정은 다음과 같이 세 단계로 진행된다.

1. 부트스트랩 방법을 통해 $T$개의 훈련 데이터셋을 생성한다.
2. $T$개의 기초 분류기(트리)들을 훈련시킨다.
3. 기초 분류기(트리)들을 하나의 분류기(랜덤 포레스트)로 결합한다(평균 또는 과반수투표 방식 이용).

트리는 작은 평균과 큰 분산(variance)을 갖기 때문에, 매우 깊이 성장한 트리는 훈련 데이터에 대해 과적합(overfitting)하게 된다.

부트스트랩 과정은 트리들의 편향은 그대로 유지하면서, 분산은 감소시키기 때문에 포레스트의 성능을 향상시킨다.

즉, 한 개의 결정 트리의 경우 훈련 데이터에 있는 노이즈에 대해서 매우 민감하지만, 트리들이 서로 상관화(correlated)되어 있지 않다면 여러 트리들의 평균은 노이즈에 대해 강인해진다.

포레스트를 구성하는 모든 트리들을 동일한 데이터셋으로만 훈련시키게 되면, 트리들의 상관성(correlation)은 굉장히 커질 것이다.

따라서 배깅은 서로 다른 데이터셋들에 대해 훈련 시킴으로써, 트리들을 비상관화시켜 주는 과정이다.