Random Forest

What is Random Forest?

랜덤 포레스트는 말 그대로 결정 트리(Decision tree)들이 모여 랜덤 포레스트를 구성합니다. 기존의 결정 트리의 단점은 Training data에 대해서 Overfitting이 된다는 경향이 있습니다. 하지만 여러 개의 결정 트리를 통해 랜덤 포레스트를 만들면 오버 피팅이 되는 단점을 해결할 수 있습니다. 물론 다른 결정트리들이 오버 피팅이 될 수 있지만 다수의 결정 트리들로 예측하기 때문에 그 영향력이 줄어들어 좋은 일반화 성능을 낼 수 있습니다.  일반적으로 랜덤 포레스트를 구성하기 위해서는 적게는 500개 ~ 많게는 10,000개의 결정 트리들을 사용한다고 합니다. 

 

---

Random Forest

State 1. 

 

 

먼저 입력 데이터들에 대한 Bootstrap sampling을 진행해야 합니다. training data에 대한 오버 핏팅을 없애기 위해 일부러 Bootstrap sampling과정을 이루는데 이는 예를 들어 100개의 입력 데이터가 있을 경우, 입력 데이터를 랜덤 샘플링을 하여 100개의 랜덤 한 데이터를 추출하여 각각의 N개의 Training subset 데이터로 N개의 decision tree에 구성해줍니다.

 

예를 들어 아래 Original Dataset(X, Y 각각 10개)가 있을 때 X, Y를 랜덤 샘플링을 하여 Training subset M개를 랜덤 하게 구축합니다. 

 

Original Dataset		Training subset 1		Training subset 2		Training subset M..
X_1	Y_1	X_4	Y_3	X_2	Y_1	X_7	Y_9
X_2	Y_2	X_1	Y_4	X_2	Y_3	X_7	Y_8
X_3	Y_3	X_3	Y_6	X_3	Y_2	X_6	Y_8
X_4	Y_4	X_3	Y_1	X_1	Y_4	X_7	Y_6
X_5	Y_5	X_9	Y_3	X_6	Y_1	X_5	Y_4
X_6	Y_6	X_8	Y_4	X_6	Y_9	X_7	Y_5
X_7	Y_7	X_3	Y_4	X_7	Y_8	X_4	Y_6
X_8	Y_8	X_8	Y_9	X_8	Y_8	X_3	Y_2
X_9	Y_9	X_1	Y_7	X_9	Y_8	X_2	Y_1

 

위의 표처럼 랜덤 샘플링 과정으로 데이터를 만들기 때문에 중복된 숫자가 겹쳐서 만들어질 수 도 있습니다.

 

Stage 2. 

 

 

이제 랜덤 하게 샘플링된 데이터들로 결정 트리를 구성해야하는데 기존의 결정트리에서 branch를 만들때 모든 Feature에 대한 Information gain 혹은 gini index를 통하여 가장 분류가 잘되는 Feature를 선택하여 결정트리를 만들어갔지만, 이번 Random forest에서 결정트리를 구성할 때는 모든 Feature가 아닌 특정 개수의 Feature를 선택하여 그중에 가장 좋은 Feature를 골라 사용합니다.

 

예를 들어 9개의(A.. I)까지의 feature가 존재할 때 매 분기를 만들 때마다 랜덤 한 3개의 Feature(ex. A, C, I) 중에 가장 분류가 잘되는 Feature를 골라 Decision tree를 구성합니다.  

 

Original Featrue	A	B	C	D	E	F	G	H	I
input Feature	A		C						I
Select Feature									I

 

Why choose random feature?

만약 기존의 방식대로 모든 Feature들 중에 가장 좋은 Feature만을 사용하여 tree를 구성하게 되면 다른 트리들도 결국 모두 비슷하게 만들어지고 이 또한 overfitting이기 때문에 feature 또한 랜덤 하게 구성합니다. 

 

그리고 현재 구성하고 있는 트리들 마다 잘 만들어지고 있는지 확인을 하는 작업 필요한데 이를 우리는 일반화 오차(Generalization error)를 통하여 알 수 있습니다.

 

Generalization error

랜덤 트리안에 결정 트리의 개수가 일정 수준 이상으로 커졌을 때 일반화 오차(Generalization error)를 구할 수 있습니다. 일반화 오차의 상한선은 다음과 같이 정의됩니다. 

 

 

ρ(각 트리 사이의 상관계수를 구한 뒤 평균)가 높아질수록 일반화 오차는 커지고 s(트리들의 평균 accuracy)가 높아질수록 일반화 오차는 감소하게 됩니다. 결국 일반화 오차를 구하면 현재 구성된 랜덤 포레스트의 성능을 알 수 있는 지표지가 되겠지요.

 

State 3, 4. 

 

이제 M개의 랜덤 트리를 만들었다면 Test data를 넣어 정확하게 분류가 되는지 진단(Aggregation)을 해봐야 합니다. 예를들어 우리는 지금 0과 1이라는 이진수 분류를 하는 랜덤트리를 만들었고 실제로 우리가 1이라는 숫자를 랜덤트리에 넣었을때 정확하게 분류가 잘 되었는지 확인을 해봐야합니다. 

 

Training Accuracy	Ensemble population	P(y=1) for a test instance	Predicted class label
0.80	Model 1	0.90	1
0.75	Model 2	0.92	1
0.88	Model 3	0.87	1
0.91	Model 4	0.34	0
0.77	Model 5	0.41	0
0.65	Model 6	0.84	1
0.95	Model 7	0.14	0
0.82	Model 8	0.32	0
0.78	Model 9	0.98	1

 

예로 9개의 결정 트리를 지나갔을 때 Training Accuracy가 높은 모델 4, 7, 8은 입력 데이터로 1을 넣었음에도 불과하고 0이라고 말하고 있습니다. 이 트리는 분명 오버핏팅된 트리입니다. 하지만 다른 트리들 같은 경우에는 상대적으로 과반수가 입력 데이터가 1이라고 말하고 있네요. 이때 우리는 simple majority voting을 통하여 과반수의 지지를 얻은 의견을 수용합니다.  수식으로 표현하면 아래와 같습니다.

 



class의 개수에 따라 개수의 숫자를 알 수 있는데 위의 표에서 test 입력 데이터에 대해 4개의 트리가 0, 5개의 트리가 1이라고 예측하고 있습니다. 그러면 수식을 따라 천천히 값을 구해보면 아래와 같이 구할 수 있습니다.

 

 

결국 label 1이라는 숫자가 가장 많이 나왔고 우리의 예측값은 '현재 들어온 입력 데이터는 1'이라는 결론을 내립니다.

 

 

Random forest의 묘리는 단 하나의 문제를 풀 때도 한 명의 똑똑한 사람보다 똑똑하지는 않더라도 수백 명의 평범한 사람들이 더 잘 푸는 원리라고 생각합니다. 여러 사람들의 분류 결과를 취합하여 예측하는 앙상블 모델의 일종인 Random forest에 대해 알아보았습니다. 감사합니다.

 

---

Ensemble(앙상블) learning

여러 개의 분류기(Classifier)를 생성하고 그 예측을 결합함으로써 보다 정확한 최종 예측을 도축하는 기법

 

앙상블 러닝의 목표는 다양한 분류기의 예측 결과를 결합하여 단일 분류기보다 신뢰성이 높은 예측 값을 얻는 것입니다.

---

 

본 글은 Hanyang University Computer and Software - Dong-Kyu Chae 교수님 수업 자료를 바탕으로 구성하였습니다.

 

Reference

https://ko.wikipedia.org/wiki/%EB%9E%9C%EB%8D%A4_%ED%8F%AC%EB%A0%88%EC%8A%A4%ED%8A%B8

https://ko.wikipedia.org/wiki/%EC%95%99%EC%83%81%EB%B8%94_%ED%95%99%EC%8A%B5%EB%B2%95 

Random Forests LEO BREIMAN Statistics Department, University of California, Berkeley, CA 94720