Random Forest 랜덤 포레스트 정의와 기능

1. Random forest 등장 배경
2. Random forest 구조 및 원리
3. 주요 하이퍼파라미터
4. 기능 및 특징
5. 코드 구현(미완성)

---

1. RF(Random Forest) 등장 배경    

• Breiman[1]에 의해 제안된 다중 의사결정나무(Decision Tree)를 활용한 기계학습 알고리즘임
• 단일 의사결정나무의 경우 모든 피처를 변수로 사용하기 때문에 더 큰 조정(adjustment) 및 편향(bias)dl 발생하는 문제가 있어 성능을 개선하기 위해 제안된 강력한 기계학습 기법임[7]
• RF는 기존 1) Bagging(Bootstrap Aggregating)[2]의 이점을 살리고 2) Random subspace methods(=Attribute bagging)[3]을 추가함으로써 개별 트리간 상관성을 줄여 예측력을 향상시킨 앙상블(Ensemble) 기법

 

---

1) Bagging

• 정의: Bootstrap[12] sampling을 이용하여 여러 개의 training data를 생성하고 각 데이터마다 개별 DT모델을 구축해 주어진 하나의 데이터로 학습된 예측모형보다 성능이 향상된 모형을 만들 수 있는 앙상블 기법
• 특징
  • 편향(Bias)은 유지하면서 분산(Variance)을 줄여 모델의 성능을 향상시킬 수 있어 학습데이터의 이상치에 큰 영향을 받지 않음
  • 별도의 검증데이터(Validation Set) 없이 Out of Bag 데이터($x,(x\in L, x\notin L_b)$, 전체 데이터셋의 약 1/3에 해당)를 Hyper Parameter 최적화나 성능 검증에 활용할 수 있음
     

Bagging 알고리즘 구조

* Bagging 알고리즘
(1) 학습데이터($L={(x_i,y_i)|i=1,...,n}$), 기본 학습모델($ϕ$), Bootstrap sample 개수($B$) 설정

(2) $b = 1,...,B$에 대해 a ~ c 반복
     a. Bootstrap sampling을 통해 Bootstrap sample 데이터셋($L_b$) 생성
     b. $L_b$를 이용해 모형($\phi(x,L_b)$)학습
     c. Out of bag 데이터($O_b$)를 이용해 성능지표($e_b$) 계산

(3) Bagging은 각 셋에 대해 학습한 모형($ϕ(x, L_b), (b=1,…,B)$)을 얻게 되고 각 모형의 결과를 집계(Aggregation)하여 최종 Bagging 모형($ϕ_B(x)$)을 도출함[23]
    - 회귀 문제의 경우 Aggregation으로 평균값을 주로 사용함
$$\phi _B(x)=\frac{1}{B}\sum_{b=1}^{B}\phi (x,L_b)$$
    - 분류 문제의 경우 Aggregation으로 최빈값을 주로 사용함 
$$\phi _B(x)=Mode \phi (x,L_b)$$
(동률의 클래스가 여러 개 도출될 경우 임의로 라벨 번호가 작은 클래스를 선정함)

(4) 모형 성능지표 계산
$$\overline{e}=\frac{1}{B}\sum_{b=1}^{B}e_b$$

 

2) RSM, Random subspace method(= Feature bagging, attribute bagging)

• RSM은 bagging과 유사하게 bootstrap 샘플 데이터셋을 이용해 여러 개의 개별 트리를 만들지만, DT 구축 시 변수(feature)를 무작위로 선택(랜덤 복원 추출)한다는 점에서 차이가 있음
• 일반 DT의 경우 분기(branch)를 나눌 때 모든 변수를 고려하지만, RSM은 DT의 분기점(Node)을 탐색할 때 원래의 변수 개수보다 적은 수의 변수를 random 선택해 임의의 변수만을 가지고 branching하기 때문에 각각의 DT가 독립적으로 형성되게 함
• 앙상블 기법에 활용된 각 classifiers(estimators) 간의 상관관계(correlation)를 낮추는 역할을 함[6]
• 개별 트리 사이 상관성이 작아지면 RF의 일반화 오류(generalized error)가 작아져 예측력이 향상됨[4]

---

2. Random forest 구조 및 원리[1,17]

랜덤포레스트 구조

1) RF 기본 알고리즘

• Bootstrap sample을 훈련 데이터에서 추출하는 것을 반복해 다수의 DT(=bootstrap sample)를 생성함
• 각 bootstrap sample에 대해 트리를 구성하며, DT가 분지(branching)할 때마다 변수를 무작위로 m개 선정함
  • RF는 개별 트리를 생성할 때 분기마다 랜덤으로 변수 후보를 선택하고 이를 통해 개별 트리간 상관성을 줄임
• 각 트리는 출력값에 투표를 진행하여 모든 트리의 결과를 투표(voting)해 최종 결과값을 채택함
  (일반적으로 분류문제는 최빈값(다수결), 회귀문제는 평균값 사용 [14]) – 수식
  • 결과값을 평균화함으로써 모델은 overfitting을 줄이고 데이터에서 비선형 관계를 산출함

랜덤포레스트 알고리즘

2) Variable Importance

• RF는 회귀모델과 달리 개별 변수가 통계적으로 얼마나 유의한지 알 수 없기 때문에 Out of bag(OOB)를 이용하여 모델의 변수 중요도를 측정할 수 있음

1) 개별 DT에 대해 Out of bag(OOB) data에 대한 예측값을 구하고 Error를 계산함
2) 개별 DT의 OOB data에 대해 각 변수마다 자신을 제외한 나머지 변수는 그대로 두고, 해당 변수의 값만 무작위로 바꿔 넣어서 예측값을 구함
3) 1), 2)의 OOB Error 차이가 각 변수의 중요도

랜덤 포레스트 변수 중요도 알고리즘

3) 일반화 오류(Generalization error)

• 개별 분류기들의 strength와 그들간의 상관관계를 이용해 generalization error의 upper bound를 구할 수 있음
• RF는 tree 수가 충분히 많을 때 Strong law of large numbers에 의해 과적합되지 않고 그 에러는 limiting value에 수렴됨

$$Generalization error \leq \frac{var(mr)}{s^2}\leq \frac{\overline{\rho }(1-s^2)}{s^2}=\frac{\overline{\rho}}{s^2}-1 \rightarrow Upper bound of generalization error$$

$\overline{\rho}$: Decision tree 사이 평균 상관관계

$s$: 올바르게 예측한 tree와 잘못 예측한 tree 수 차이 평균

• Generalization error의 최대값(limiting value)이 작을수록 RF의 성능이 높아짐
  • 개별 tree의 정확도가 높을수록 $s$값 증가
  • Bagging, RSM은 각 모델들의 독립성, 일반화, 무작위성을 최대화시켜 모델간 상관관계($\rho$) 감소

(참고: https://rpubs.com/stoney/579763)

RPubs - RF

---

3. Random forest 주요 하이퍼파라미터(Hyper parameter)

파라미터명	default	설명
N_estimators	100	-     RF 내 base모델(DT) 개수 -     결정 트리가 많을수록 더 깔끔한 Decision boundary를 얻을 수 있으나 메모리와 훈련시간이 증가함
Max_features	Auto	-     RSM 과정에서 DT를 독립적으로 만들기 위해 무작위로 선택할 변수(feature) 개수 -     값이 클수록 RF 내 트리들이 서로 비슷해지고, 가장 두드러진 특성에 맞게 예측함 -     값이 작을수록 RF 내 트리들이 서로 달라지며 overfitting이 줄어듦 -     Auto(=sqrt): max_features = sqrt(n_features) -     log2: max_features = log2(n_features) -     None: max_features = n_features
criterion	gini	-     분할 품질을 측정하는 기능 (default : gini) -     Gini, entropy 등
Bootstrap	True	-     부트스트랩(중복허용 샘플링) 사용 여부 -     True면 전체 feature에서 복원추출해서 트리 생성
Max_depth		-     트리의 깊이
Min_samples_leaf	1	-     리프 노드에 있어야할 최소 샘플 수 (default: 1)
Min_samples_spllit	2	-     내부 노드를 분할하는데 필요한 최소 샘플 수 (default: 2)
Max_leaf_nodes		-     리프 노드의 최대 수
min_weight_fraction_leaf		-     min_sample_leaf와 같지만 가중치가 부여된 샘플 수에서의 비율
min_impurity_decrease		-     최소 불순도
Min_impurity_split		-    나무 성장을 멈추기 위한 임계치
oob_score	True	-    일반화 정확도를 줄이기 위해 OOB데이터 사용 여부

---

4. 기능 및 특징

• RF는 강력하고 유연하며 널리 사용되는 기계 학습 알고리즘으로 범주형 및 연속형 변수를 모두 처리할 수 있고 특히 복잡한 고차원 데이터 학습에 강력한 성능을 보임
• 분류, 회귀, 중요변수선택 등 다양한 문제에 활용됨[4-16]
• 임의 알고리즘으로 하위 집합에서 훈련 데이터를 무작위로 받고 트리를 형성하는 구조로 인해 다른 기계학습 알고리즘보다 강력한 성능을 보임 [13]
• 장점 및 단점

장점	-    Classification(분류) 및 Regression(회귀) 문제에 모두 사용 가능 -    각 DT의 결과값을 평균내서 결과를 도출하기 때문에 Missing value(결측치), 이상치에 강함 -    복잡하고 대용량 데이터 처리에 매우 효율적임[17] -    모델의 노이즈를 심화시키는 Overfitting 문제를 회피하여, 모델 정확도를 향상시킴[20] -    Classification 모델에서 상대적으로 중요한 변수를 선정 및 Ranking 가능
단점	-    black box 특성을 가져 모형의 해석이 어려움[12] -    다른 앙상블에 비해 유연하지 않음 -    계산량이 많고 학습에 소요되는 시간이 단일 DT에 비해 많음

---

5. 관련 연구

• RF는 회귀 및 분류 문제 모두에서 좋은 성능을 보이며 다양한 분야에서 사용됨

저자	활용모델	결과 요약
[4]	RF	-    전세계 190개국의 COVID-19 일일확진자 수를 RF 방법으로 추정하고 실제 데이터와 비교함 -    RF는 가까운 미래의 확진자 수 추정에 높은 성능을 보임
[5]	LR, ANN, XGBoost, RF	-    캐나다 온타리오주 COVID-19 환자 데이터 기반 사망률을 LR(Linear Regression), ANN(Artificial Neural Network), XGBoost, RF 모델으로 추정하고 중요도가 높은 변수를 제시함 -    4가지 모형 모두 높은 예측 성능을 보임
[6]	RF	-    RF 머신러닝 기법을 사용해 이란 및 다른 국가의 COVID-19로 인한 사망 추세를 예측하고 비교함 -    LASSO MLT을 사용한 변수 중요도 분석 결과 버스정류장까지의 거리, 베이커리, 병원, ATM, 최저온도 등으로 도출됨
[8]	RBDT, BRT, CART, RF	-    RBDT(Rule-Based Decision Tree), BRT(Boosted Regression Trees), CART(Classification And Regression Tree), RF 총 4개의 tree기반 모델을 지반 침하위험 공간 예측에 적용한 결과 RF가 가장 높은 성능을 보임
[9]	RF, RT	-    RF, RT(Regression Tree)를 활용해 인공강우 확률 계산
[10]	RF	-    Geodatabase 구축 단계에서 토지 피복 분류에 RF 알고리즘 활용
[15]	RF, DNN	-    호주 유방암 환자 데이터를 기반으로 재발 확률을 RF, DNN(Deep Neural Network)으로 각각 예측한 결과 RF 기법이 기존 연구에 비해 가장 높은 정확도를 달성함
[16]	RF, MLR	-    유럽 화재건수 시계열 데이터 기반 화재발생 가능성을 RF, MLR(Multiple Linear Regression)으로 분석한 결과 RF 모델이 MLR 모델보다 높은 예측 성능을 보임

---

References 

[1] Breiman, L. (2001). Random forests. Machine learning, 45, 5-32.

[2] Breiman, L. (1996). Bagging predictors. Machine learning, 24, 123-140.

[3] Ho, T. K. (1998). The random subspace method for constructing decision forests. IEEE transactions on pattern analysis and machine intelligence, 20(8), 832-844.

[4] Yeşilkanat, C. M. (2020). Spatio-temporal estimation of the daily cases of COVID-19 in worldwide using random forest machine learning algorithm. Chaos, Solitons & Fractals, 140, 110210.

[5] Snider, B., McBean, E. A., Yawney, J., Gadsden, S. A., & Patel, B. (2021). Identification of variable importance for predictions of mortality from COVID-19 using AI models for Ontario, Canada. Frontiers in Public Health, 9, 675766.

[6] Pourghasemi, H. R., Pouyan, S., Heidari, B., Farajzadeh, Z., Shamsi, S. R. F., Babaei, S., ... & Sadeghian, F. (2020). Spatial modeling, risk mapping, change detection, and outbreak trend analysis of coronavirus (COVID-19) in Iran (days between February International Journal of Infectious Diseases, 98, 90-108.

[7] Arabameri, A., Pradhan, B., Pourghasemi, H. R., Rezaei, K., & Kerle, N. (2018). Spatial modelling of gully erosion using GIS and R programing: A comparison among three data mining algorithms. Applied sciences, 8(8), 1369.

[8] Rahmati, O., Falah, F., Naghibi, S. A., Biggs, T., Soltani, M., Deo, R. C., ... & Bui, D. T. (2019). Land subsidence modelling using tree-based machine learning algorithms. Science of the Total Environment, 672, 239-252.

[9] Jeung, M., Baek, S., Beom, J., Cho, K. H., Her, Y., & Yoon, K. (2019). Evaluation of random forest and regression tree methods for estimation of mass first flush ratio in urban catchments. Journal of Hydrology, 575, 1099-1110.

[10] Izquierdo-Verdiguier, E., & Zurita-Milla, R. (2020). An evaluation of Guided Regularized Random Forest for classification and regression tasks in remote sensing. International Journal of Applied Earth Observation and Geoinformation, 88, 102051.

[11] Kontschieder, P., Bulo, S. R., Bischof, H., & Pelillo, M. (2011, November). Structured class-labels in random forests for semantic image labelling. In 2011 international conference on computer vision (pp. 2190-2197). IEEE.

[12] Efron, B., & Tibshirani, R. J. (1994). An introduction to the bootstrap. CRC press.

[13] Panov, P., & Džeroski, S. (2007). Combining bagging and random subspaces to create better ensembles. In Advances in Intelligent Data Analysis VII: 7th International Symposium on Intelligent Data Analysis, IDA 2007, Ljubljana, Slovenia, September 6-8, 2007. Proceedings 7 (pp. 118-129). Springer Berlin Heidelberg.

[14] Criminisi, A., Shotton, J., & Konukoglu, E. (2012). Decision forests: A unified framework for classification, regression, density estimation, manifold learning and semi-supervised learning. Foundations and trends® in computer graphics and vision, 7(2–3), 81-227.

[15] Al-Quraishi, T., Abawajy, J. H., Chowdhury, M. U., Rajasegarar, S., & Abdalrada, A. S. (2018). Breast cancer recurrence prediction using random forest model. In Recent Advances on Soft Computing and Data Mining: Proceedings of the Third International Conference on Soft Computing and Data Mining (SCDM 2018), Johor, Malaysia, February 06-07, 2018 (pp. 318-329). Springer International Publishing.

[16] Oliveira, S., Oehler, F., San-Miguel-Ayanz, J., Camia, A., & Pereira, J. M. (2012). Modeling spatial patterns of fire occurrence in Mediterranean Europe using Multiple Regression and Random Forest. Forest Ecology and Management, 275, 117-129.

[17] Cutler, A., Cutler, D. R., & Stevens, J. R. (2012). Random forests. Ensemble machine learning: Methods and applications, 157-175.

사이트 참고:  https://rpubs.com/stoney/579763

RPubs - RF