Search

Random Forest (랜덤포레스트)

@Jihyun Choi @7/6/2022 @Hyun Ahn
: 다수의 Decision Tree(의사결정나무) 들을 생성 및 출력 결과를 종합하여 예측을 수행하는 앙상블 기반의 모델
•
대표적인 배깅(Bagging) 방식: 개별 모델들은 서로 독립적으로 작동(병렬적 방식)
•
개별 Decision Tree 생성 과정에서, 랜덤하게 데이터와 특징(= 변수) 집합을 선택 → 다양한 모습의 Decision Tree 들이 생성되므로 과적합(overfitting)을 방지할 수 있음
여러 Decision Tree 들의 출력 값을 수렴하여 최종 예측 값을 출력하는 Random Forest 의 개념

모델 생성 과정

1.
부트스트래핑을 통한 데이터셋 생성
•
원본 데이터와 동일한 크기의 데이터셋을 생성 by 랜덤 샘플링 (중복 허용)
•
Out-of-Bag Dataset: 부트스트래핑을 통해 생성된 데이터셋에서 제외된 원본 데이터
2.
일정 크기의 랜덤으로 선택된 변수 부분 집합을 이용하여 Decision Tree 를 생성
•
매 단계마다 변수 부분 집합 선택 수행: root node → internal nodes… → leaf node
•
# variable: 랜덤으로 선택할 변수 개수, 일반적으로 변수 개수의 제곱근에서 시작하여 증가
•
# variable 은 랜덤포레스트 학습 과정에서 최적화됨
3.
1-2 반복을 통해 다수의 Decision Tree 생성 → Random Forest 생성
•
in scikit-learn: n_estimators (트리 개수)
4.
Random Forest 를 사용하여 예측: 새로운 데이터에 대해 각 Deicision Tree 들이 예측한 결과들을 종합
5.
성능 평가: Out-of-Bag 데이터들을 대상으로 성능 측정
•
Out-of-Bag Error 계산 → 2번을 위한 # variables 를 학습

특징 중요도 계산

Random Forest 는 생성 과정에서 모델 설명을 위한 특징 중요도(feature importance) 를 자동으로 계산하기 때문에 설명 가능한 모델로 평가됨
특징 중요도는 특징 별 평균 불순도 감소(Mean Decrease in Impurity) 를 통해 산출됨

수식

•
T\mathcal{T}: Random Forest 의 Decision Tree 집합
◦
t∈Tt\in \mathcal{T}: 특정 Decision Tree
•
S\mathcal{S}: 트리 tt 의 노드 (= Split) 집합
◦
s∈Ss\in \mathcal{S}: 특정 노드
•
sl,srs_{l}, s_{r}: 노드 ss 의 자식 노드 (좌, 우)
◦
CART에 해당됨 (Binary Tree)
•
i(t,s)i(t, s): 노드 ss 에 대한 불순도
◦
ss 는 tt 의 노드
•
w(t,s)w(t,s): 노드 ss 의 비중
◦
노드 ss 의 샘플 수를 전체 샘플 수로 나눈 값
•
Δi(t,s)\Delta i(t,s): 노드 ss 의 불순도 감소 정도 (노드 평가 기준)
Δi(t,s)=w(t,s)i(t,s)−w(t,sl)i(t,sl)−w(t,sr)i(t,sr)\Delta i(t,s)=w(t,s)i(t,s)-w(t,s_{l})i(t,s_l)-w(t,s_r)i(t,s_r)
•
Sθ\mathcal{S}^\theta : 특징 θ\theta 에 해당되는 노드 집합
◦
특징 θ\theta 와 임계치를 이용하여 분할 규칙을 정의한 노드 집합
•
I(t,θ)I(t,\theta): 트리 tt 에서의 특징 θ\theta 의 중요도
◦
특징 θ\theta 에 해당되는 노드 집합의 불순도 감소 합계를 전체 노드 집합의 불순도 감소 합계로 나눈 값: [0,1][0,1]
I(t,θ)=∑s∈SθΔi(t,s)∑s∈SΔi(t,s)I(t,\theta)=\frac{\sum_{s\in \mathcal{S^{\theta}}}\Delta i(t,s)}{\sum_{s\in \mathcal{S}}\Delta i(t,s)}
•
I(θ)I(\theta): 특징 θ\theta 의 중요도
◦
모든 트리로부터 중요도를 합산하여 트리 갯수로 나눈 값 = 평균 특징 중요도
I(θ)=∑t∈TI(t,θ)∣T∣I(\theta)=\frac{\sum_{t \in \mathcal{T}}I(t,\theta)}{|\mathcal{T}|}

장점

•
분류(classification)와 회귀(regression) 문제 둘 다 적용 가능
•
각 피쳐의 상대적 중요성 측정 가능(특성 중요도)
•
결측치(Missing Value)를 다루기 쉬움
•
대용량 데이터 처리에 효과적(추가적 계산 X, 집계 O → 시간 단축)
•
Overfitting의 위험성이 적음

단점

•
차원이 높고 희소한 데이터에는 잘 작동하지 않음 (Bootstrap, Random Sampling 효과가 떨어짐)
•
많은 수의 Decision Tree 를 생성하거나, 트리 깊이에 제한이 없을 경우 학습에 많은 시간이 소요될 수 있음
◦
솔루션 : OOB(Out-of-bag) → 데이터의 2/3만 예측에 사용
•
모델 생성 이후에 새로운 데이터에 대한 재학습이 불가능 (트리 기반 모델의 한계)

Parameter

•
n_estimators : 생성할 결정 트리 개수
◦
트리가 많을수록 좋은 성능을 기대할 수 있지만 무조건적이지 않으며 개수에 비례해 학습 시수행 시간이 증가함
•
max_features : 무작위로 선택할 Feature의 개수
•
max_depth : 트리의 깊이
•
min_samples_leaf : leaf node가 되기 위한 최소 샘플 데이터 수
◦
leaf node(=리프 노드, 말단 노드) : 자식이 없는 노드
•
max_leaf_nodes : leaf node의 최대 개수
•
min_samples_split : 노드 분할을 위한 최소 데이터 수

References

1.
(Menze 2009) A comparison of random forest and its Gini importance with standard chemometric methods for the feature selection and classification of spectral data, BMC Bioinformatics
a.
impurity, feature importance 수식
2.
(Cassidy 2014) Calculating Feature Importance in Data Streams with Concept Drift using Online Random Forest, IEEE Int. Conf. on Big Data
a.
impurity, feature importance 수식
3.
a.
impurity, feature importance 계산
4.
a.
impurity, feature importance 수식
6.
랜덤 포레스트(Random Forest) 쉽게 이해하기, hleecaster (link)
7.
랜덤 포레스트(Random Forest)란?, tistory (link)
8.
랜덤 포레스트란 무엇입니까?, tibco (link)
Made with