Random Forests 정리

정의

- an ensemble method consisting of  ➀ a bagging of un-pruned decision tree learners

- with ➁ a randomized selection of features at each split

 

Bagging과의 차이점

- Bagging : untilizint the same full set of predictors to determine each split while constructing a tree

 

- Random Forests : selecting the best features in a randomly selection subset of feature at each split (Additinal Randomness)

 

 

Additional Randomness

개별 DT를 construct할때 Node를 Split하는 Feature의 후보군을 선택할때

단순 Best Feature (e.g. GAIN, Entropy를 최소화하는 Feature) 를 뽑는 것이 아니라

그 안에서 Random성을 추가로 준다.

 

=> 그 안에서의 Randomness = 후보군을 Random으로 Select하여 그 안에서의 Best Feature를 고른다.

 

=> 그냥 Bagging of Decision Tree방식에서는 암만 Bootstrap Sample을 통해 Corelation을 낮추어도 어쩔수 없이

출발하는 Dataset이 동일 하므로 생성된 DT간에 Corelation이 있는데 DT 형성 과정의 Additional Randomness를 통하여 이를 더욱 줄일 수 있다.

 

=> 이때 각 DT들이 Node Split과정에서 일부 Feature를 고려하지 않음으로 인해 발생하는 개별 Tree 성능의 저하가 있다.

하지만 경험적으로 이러한 성능저하는 Forests를 형성하는 과정 (Majority Voting or Averaging)에서

극복이 가능하고 Corelation을 낮추는 긍정적인 방향으로만 작동하는 것이 확인 되었다.

 

Random Forests와 관련된 Parameter

- N_trees : number of trees to build

- m_try : number of features to be selected at each split

 

 

Advantages

. Overall

- 정확도가 높다 (SVM, NN과도 비빌 수 있다.)

- SVM, NN에 비해 학습이 빠르고 파라미터 수가 적다. (good for large datasets)

- 기본적으로 DT기반이기 때문에 interpretable하다.

 

. Traing

- it generates an internal unbiased estimate of the generalization error (Cross validation is unnecessary)

- Resistance to over training.

 

 

Illustration

 

Out Of Bag

Bootstrap Sample은 Data Set D의 data를 random하게 복원 추출하여 생성된다.

이때 각 data 에대하여 해당 data가 bootstrap에 select될 확률은 약 33%이다.

 

Bootstrap Sample별 생성된 Decision Tree에 대하여 전체 데이터엔 있지만 Bootstrap엔 선택되지 않아 Tree build에 관여 하지 않은 data들을 OOB (out of bag)라 부른다.

 

OOB를 활용하면 Random Forests에서는

1. Model (Random Forsts)의 성능 평가의 기준을 얻을 수 있다.

2.  Variable (Feature) Importance를 구할 수 있다.

 

1. 성능 평가 using OOB Error

 

모든 data S 에 대하여
   1. S를 OOB 로 가지는 DT를 모두 찾는다.
   2. 해당 DT들을 합쳐 sub-forest를 만든다. 
   3. sub-forest로 S의 output을 구해 Ground Truth와 비교하여 Error를 구한다.
=> 모든 data에 대한 Error를 avarage한다.

 

sub-forest는 S에 대한 정보가 없기 때문에 train/test set을 구분하는 일반적인 방식의 성능평가가 필요없다.

= 이 방식을 활용하면 random forests는 모든 data를 train에 활용하며 test에도 활용 할 수 있다.

+

DT의 개수를 미리 구하지 않은 경우 해당 Error를 통해 DT의 개수를 조정하는 것이 가능하다.

 

2.  Variable Importance 구하기

 

 모든 DT에 대해서
   1. OOB sample을 통해 에러(e)를 구한다.
   2. k-th feature를 random하게 permute한 OOB data를 DT에 넣어 k-th feature를 없앤 에러(e_k)를 구한다.
 
k-th feature의 중요도는 DT별로 구해진 |e-e_k|의 average에 비례한다.