랜덤 포레스트

랜덤 포레스트 또는 랜덤 결정 포레스트는 분류, 회귀 및 기타 작업을 위한 앙상블 학습 방법으로, 훈련 과정에서 다수의 결정 트리를 생성하여 작동한다. 분류 작업에서 랜덤 포레스트의 출력은 가장 많은 트리가 선택한 클래스이다. 회귀 작업에서 출력은 트리들의 예측값의 평균이다.[^1][^2] 랜덤 포레스트는 결정 트리가 훈련 세트에 과적합하는 경향을 보정한다.

랜덤 결정 포레스트의 최초 알고리즘은 1995년 Tin Kam Ho에 의해[^1] 랜덤 부분공간 방법을[^2] 사용하여 만들어졌으며, Ho의 공식화에서 이는 Eugene Kleinberg가 제안한 분류에 대한 "확률적 판별" 접근법을 구현하는 방법이었다.[^3][^4][^5]

이 알고리즘의 확장은 Leo Breiman[^6]과 Adele Cutler에 의해 개발되었으며, 이들은 2006년에 "Random Forests"를 상표로 등록하였다[^24] (현재 Minitab, Inc. 소유).[^25] 이 확장은 Breiman의 "배깅" 아이디어와 Ho에 의해 처음 도입되고[^1] 이후 Amit과 Geman에 의해 독립적으로 도입된[^7] 특징의 무작위 선택을 결합하여, 분산이 제어된 결정 트리 모음을 구축한다.

역사

랜덤 결정 포레스트의 일반적인 방법은 1993년 Salzberg와 Heath에 의해 처음 제안되었으며,[^26] 무작위화된 결정 트리 알고리즘을 사용하여 여러 트리를 생성한 다음 다수결 투표를 통해 결합하는 방법이었다. 이 아이디어는 1995년 Ho에 의해 더욱 발전되었다.[^1] Ho는 사선 초평면으로 분할하는 트리의 포레스트가, 선택된 특징 차원에만 민감하도록 무작위로 제한되는 한, 과훈련에 시달리지 않으면서 성장할수록 정확도를 높일 수 있음을 확립하였다. 같은 맥락의 후속 연구[^2]에서는 다른 분할 방법도 일부 특징 차원에 무감각하도록 무작위로 강제되는 한 유사하게 동작한다고 결론지었다. 더 복잡한 분류기(더 큰 포레스트)가 거의 단조적으로 더 정확해진다는 이 관찰은, 분류기의 복잡도가 일정 수준의 정확도까지만 성장할 수 있고 그 이상은 과적합에 의해 손상된다는 일반적인 믿음과 극명하게 대조된다. 포레스트 방법의 과훈련에 대한 저항성의 설명은 Kleinberg의 확률적 판별 이론에서 찾을 수 있다.[^3][^4][^5]

Breiman의 랜덤 포레스트 개념의 초기 발전은 Amit과 Geman의 연구[^7]에 영향을 받았으며, 이들은 단일 트리를 성장시키는 맥락에서 노드를 분할할 때 사용 가능한 결정들의 무작위 부분집합을 탐색하는 아이디어를 도입하였다. Ho의 랜덤 부분공간 선택 아이디어[^2] 또한 랜덤 포레스트의 설계에 영향을 미쳤다. 이 방법은 트리의 포레스트를 성장시키며, 각 트리 또는 각 노드를 적합시키기 전에 훈련 데이터를 무작위로 선택된 부분공간에 투영하여 트리 간에 변이를 도입한다. 마지막으로, 각 노드에서의 결정이 결정론적 최적화가 아닌 무작위화된 절차에 의해 선택되는 무작위화된 노드 최적화의 아이디어는 Thomas G. Dietterich에 의해 처음 도입되었다.[^27]

랜덤 포레스트의 본격적인 소개는 Leo Breiman의 논문[^6]에서 이루어졌으며, 이 논문은 세계에서 가장 많이 인용되는 논문 중 하나가 되었다.[^28] 이 논문은 CART와 유사한 절차를 사용하여, 무작위화된 노드 최적화 및 배깅과 결합하여 비상관 트리의 포레스트를 구축하는 방법을 설명한다. 또한 이 논문은 이전에 알려진 것과 새로운 것을 포함한 여러 요소를 결합하며, 이는 현대 랜덤 포레스트 실무의 기초를 형성한다. 특히:

1. 일반화 오류의 추정치로 아웃오브백 오류를 사용하는 것.
2. 순열을 통해 변수 중요도를 측정하는 것.

이 보고서는 또한 랜덤 포레스트에 대한 최초의 이론적 결과를 제시하며, 이는 포레스트 내 트리의 강도와 상관관계에 의존하는 일반화 오류의 상한 형태이다.

알고리즘

예비 지식: 결정 트리 학습

결정 트리는 다양한 기계 학습 작업에 널리 사용되는 방법이다. Hastie 등에 따르면, 트리 학습은 거의 "데이터 마이닝을 위한 기성품 절차"에 가까운데, "이는 특성 값의 스케일링 및 기타 다양한 변환에 대해 불변이고, 무관한 특성의 포함에 대해 견고하며, 검사 가능한 모델을 생성하기 때문이다. 그러나 정확도가 높은 경우는 드물다".^8

특히 매우 깊게 성장한 트리는 매우 불규칙한 패턴을 학습하는 경향이 있다. 즉, 훈련 세트에 과적합하여 편향은 낮지만 분산이 매우 높다. 랜덤 포레스트는 동일한 훈련 세트의 서로 다른 부분에서 훈련된 여러 깊은 결정 트리를 평균화하여 분산을 줄이는 방법이다.^8 이로 인해 편향이 약간 증가하고 해석 가능성이 일부 손실되지만, 일반적으로 최종 모델의 성능이 크게 향상된다.

배깅

랜덤 포레스트의 훈련 알고리즘은 부트스트랩 집계, 즉 배깅의 일반적인 기법을 트리 학습기에 적용한다. 훈련 세트 = , ..., 와 응답 = , ..., 이 주어졌을 때, 배깅은 훈련 세트에서 복원 추출로 무작위 표본을 반복적으로(B회) 선택하고 이 표본들에 트리를 적합시킨다:

훈련 후, 미관측 표본 에 대한 예측은 에 대한 모든 개별 회귀 트리의 예측을 평균하여 만들 수 있다:

\hat{f} = \frac{1}{B} \sum_{b=1}^Bf_b (x')

또는 분류 트리의 경우 다수결 투표를 통해 예측할 수 있다.

이 부트스트래핑 절차는 편향을 증가시키지 않으면서 모델의 분산을 줄이기 때문에 더 나은 모델 성능으로 이어진다. 이는 단일 트리의 예측이 훈련 세트의 잡음에 매우 민감한 반면, 트리들이 상관되지 않는 한 많은 트리의 평균은 그렇지 않다는 것을 의미한다. 단일 훈련 세트에서 많은 트리를 단순히 훈련시키면 강하게 상관된 트리를 생성하게 되고(또는 훈련 알고리즘이 결정적이라면 동일한 트리를 여러 번 생성하게 됨), 부트스트랩 표본 추출은 서로 다른 훈련 세트를 보여줌으로써 트리의 상관성을 제거하는 방법이다.

추가적으로, 예측의 불확실성 추정은 에 대한 모든 개별 회귀 트리 예측의 표준편차로 구할 수 있다: \sigma = \sqrt{\frac{\sum_{b=1}^B (f_b(x') - \hat{f})^2}{B-1} }.

표본 수(즉, 트리 수) 는 자유 매개변수이다. 일반적으로 훈련 세트의 크기와 특성에 따라 수백에서 수천 개의 트리가 사용된다. 는 교차 검증을 사용하거나 아웃오브백 오류를 관찰하여 최적화할 수 있다: 아웃오브백 오류란 각 훈련 표본 에 대해, 를 부트스트랩 표본에 포함하지 않은 트리만을 사용한 평균 예측 오류이다.[^9]

훈련 오류와 테스트 오류는 일정 수의 트리가 적합된 후 수렴하는 경향이 있다.

배깅에서 랜덤 포레스트로

위의 절차는 트리에 대한 원래의 배깅 알고리즘을 설명한다. 랜덤 포레스트는 또 다른 유형의 배깅 기법도 포함한다: 학습 과정에서 각 후보 분할마다 특성의 무작위 부분집합을 선택하는 수정된 트리 학습 알고리즘을 사용한다. 이 과정을 때때로 "특성 배깅"이라고 한다. 이를 수행하는 이유는 일반 부트스트랩 표본에서 트리 간의 상관성 때문이다: 하나 또는 소수의 특성이 응답 변수(목표 출력)에 대해 매우 강한 예측 변수인 경우, 이러한 특성이 많은 트리에서 선택되어 트리들이 상관되게 된다. 배깅과 무작위 부분공간 투영이 서로 다른 조건에서 정확도 향상에 어떻게 기여하는지에 대한 분석은 Ho에 의해 제시되었다.[^10]

일반적으로, p 개의 특성을 가진 분류 문제의 경우, 각 분할에서 \sqrt{p} (내림) 개의 특성이 사용된다.^8 회귀 문제의 경우 개발자들은 최소 노드 크기 5를 기본값으로 하여 p/3 (내림)를 권장한다.^8 실제로는 이러한 매개변수의 최적값은 모든 문제에 대해 개별적으로 조정해야 한다.^8

극단적 무작위 트리(ExtraTrees)

한 단계의 무작위화를 더 추가하면 극단적 무작위 트리, 즉 ExtraTrees가 만들어진다. 일반 랜덤 포레스트와 마찬가지로 개별 트리의 앙상블이지만, 두 가지 주요 차이점이 있다: (1) 각 트리는 (부트스트랩 표본이 아닌) 전체 학습 표본을 사용하여 훈련되며, (2) 하향식 분할이 무작위화된다: 고려 중인 각 특성에 대해 국소적으로 최적인 분할점(예: 정보 이득 또는 지니 불순도 기반)을 계산하는 대신 여러 개의 무작위 분할점이 선택된다. 값은 특성의 경험적 범위(트리의 훈련 세트 내) 내에서 균일 분포로부터 선택된다. 그런 다음, 무작위로 선택된 모든 분할 중에서 가장 높은 점수를 산출하는 분할이 노드 분할에 선택된다.

일반 랜덤 포레스트와 마찬가지로, 각 노드에서 고려할 무작위로 선택된 특성의 수를 지정할 수 있다. 이 매개변수의 기본값은 분류의 경우 \sqrt{p}, 회귀의 경우 p이며, 여기서 p는 모델의 특성 수이다.[^29]

고차원 데이터를 위한 랜덤 포레스트

기본 랜덤 포레스트 절차는 특성의 수가 많지만 이들 중 표본 분류에 유익한 특성이 소수에 불과한 상황에서는 잘 작동하지 않을 수 있다. 이는 유익한 특성과 트리에 주로 집중하도록 절차를 유도함으로써 해결할 수 있다. 이를 달성하기 위한 몇 가지 방법은 다음과 같다:

• 사전 필터링: 대부분 잡음에 불과한 특성을 제거한다.[^30][^31]
• 강화된 랜덤 포레스트(ERF): 각 트리의 각 노드에서 단순 무작위 표본 추출 대신 가중 무작위 표본 추출을 사용하여, 더 유익해 보이는 특성에 더 큰 가중치를 부여한다.[^32][^33][^34]
• 트리 가중 랜덤 포레스트(TWRF): 더 정확한 트리에 더 큰 가중치를 부여한다.[^35][^36]

속성

변수 중요도

랜덤 포레스트는 회귀 또는 분류 문제에서 변수의 중요도를 자연스러운 방식으로 순위 매기는 데 사용할 수 있다. 다음 기법은 Breiman의 원래 논문에서 설명되었다.[^11]

순열 중요도

데이터 집합 \mathcal{D}n ={(X_i, Y_i)}{i=1}^n에서 특성의 중요도를 측정하기 위해, 먼저 데이터에 대해 랜덤 포레스트를 훈련시킨다. 훈련 과정에서 각 데이터 포인트에 대한 OOB(out-of-bag) 오차가 기록되고 포레스트 전체에 걸쳐 평균이 계산된다. (훈련 중 배깅을 사용하지 않는 경우, 대신 독립적인 테스트 집합에서 오차를 계산할 수 있다.)

훈련 후, OOB 표본에서 해당 특성의 값을 순열(permute)하고 이 교란된 데이터 집합에서 OOB 오차를 다시 계산한다. 특성의 중요도는 모든 트리에 대해 순열 전후의 OOB 오차 차이를 평균하여 계산한다. 점수는 이 차이들의 표준편차로 정규화된다.

이 점수에서 큰 값을 산출하는 특성은 작은 값을 산출하는 특성보다 더 중요한 것으로 순위가 매겨진다. 변수 중요도 측정의 통계적 정의는 Zhu 등에 의해 제시되고 분석되었다.[^37]

이 변수 중요도 결정 방법에는 몇 가지 단점이 있다:

• 특성마다 값의 수가 다를 때, 랜덤 포레스트는 값이 더 많은 특성을 선호한다. 이 문제의 해결책으로는 부분 순열[^38][^39][^12]과 비편향 트리 성장이 있다.[^40][^41]
• 데이터에 유사한 관련성을 가진 상관된 특성 그룹이 포함되어 있으면, 큰 그룹보다 작은 그룹이 선호된다.[^42]
• 공선성 특성이 있는 경우, 이 절차가 중요한 특성을 식별하지 못할 수 있다. 해결책은 상관된 특성 그룹을 함께 순열하는 것이다.[^13]

불순도 평균 감소 특성 중요도

랜덤 포레스트에 대한 이 특성 중요도 접근법은 분할 과정에서 불순도를 크게 감소시키는 변수를 중요한 것으로 간주한다.[^43] 이 방법은 Leo Breiman의 저서 *분류 및 회귀 트리(Classification and Regression Trees)*에 기술되어 있으며[^44] sci-kit learn과 R의 기본 구현이다. 정의는 다음과 같다:\text{unormalized average importance}(x)=\frac{1}{n_T} \sum_{i=1}^{n_T} \sum_{\text{node }j \in T_i | \text{split variable}(j) = x} p_{T_i}(j)\Delta i_{T_i}(j),여기서

• x는 특성
• n_T는 포레스트 내 트리의 수
• T_i는 트리 i
• p_{T_i}(j)=\frac{n_j}{n}는 노드 j에 도달하는 표본의 비율
• \Delta i_{T_i}(j)는 트리 i의 노드 j에서의 불순도 변화

노드에 속하는 표본의 불순도 측정으로는 예를 들어 다음과 같은 통계량을 사용할 수 있다: *엔트로피 *지니 계수 *평균 제곱 오차

정규화된 중요도는 모든 특성에 대해 정규화하여, 정규화된 특성 중요도의 합이 1이 되도록 얻어진다.

sci-kit learn의 기본 구현은 잘못된 특성 중요도를 보고할 수 있다:[^13]

• 높은 카디널리티 특성을 선호한다
• 훈련 통계량을 사용하므로 테스트 집합에 대한 예측에서의 특성 유용성을 반영하지 않는다[^45]

최근접 이웃과의 관계

랜덤 포레스트와 -최근접 이웃 알고리즘(-NN) 사이의 관계는 2002년 Lin과 Jeon에 의해 지적되었다.[^14] 두 방법 모두 소위 가중 이웃 방식으로 볼 수 있다. 이는 훈련 집합 {(x_i, y_i)}{i=1}^n으로 구축된 모델로, 새로운 점에 대한 예측값 \hat{y}를 가중 함수로 형식화된 해당 점의 "이웃"을 살펴봄으로써 생성한다:\hat{y} = \sum{i=1}^n W(x_i, x') , y_i.여기서 W(x_i, x')는 같은 트리 내에서 새로운 점에 대한 번째 훈련 포인트의 비음수 가중치이다. 임의의 에 대해, 포인트 x_i의 가중치 합은 1이어야 한다. 가중 함수는 다음과 같다:

• -NN에서, W(x_i, x') = \frac{1}{k}는 이 에 가장 가까운 개의 점 중 하나일 때이며, 그렇지 않으면 0이다.
• 트리에서, W(x_i, x') = \frac{1}{k'}는 이 와 같은 리프에 있는 개의 점 중 하나일 때이며, 그렇지 않으면 0이다.

포레스트는 개별 가중 함수 W_j를 가진 개의 트리 예측을 평균하므로, 그 예측은 다음과 같다:\hat{y} = \frac{1}{m}\sum_{j=1}^m\sum_{i=1}^n W_{j}(x_i, x') , y_i = \sum_{i=1}^n\left(\frac{1}{m}\sum_{j=1}^m W_{j}(x_i, x')\right) , y_i.

이는 전체 포레스트가 다시 가중 이웃 방식이며, 가중치는 개별 트리의 가중치를 평균한 것임을 보여준다. 이 해석에서 의 이웃은 임의의 트리 j에서 같은 리프를 공유하는 포인트 x_i이다. 이러한 방식으로, 의 이웃은 트리의 구조에, 따라서 훈련 집합의 구조에 복잡한 방식으로 의존한다. Lin과 Jeon은 랜덤 포레스트가 사용하는 이웃의 형태가 각 특성의 지역적 중요도에 적응함을 보여준다.[^14]

비지도 학습

구축 과정의 일부로서, 랜덤 포레스트 예측기는 자연스럽게 관측값 간의 비유사도 측정을 이끌어낸다. 이와 유사하게, 원래의 "관측된" 데이터를 참조 분포에서 적절히 생성된 합성 데이터와 구별하도록 포레스트를 훈련시킴으로써 레이블이 없는 데이터 간의 비유사도를 정의할 수 있다.[^11] 랜덤 포레스트 비유사도는 혼합된 변수 유형을 매우 잘 처리하고, 입력 변수의 단조 변환에 불변이며, 이상치 관측값에 강건하다는 점에서 매력적이다. 랜덤 포레스트 비유사도는 내재적 변수 선택 기능 덕분에 다수의 준연속 변수를 쉽게 처리한다. 예를 들어, "Addcl 1" 랜덤 포레스트 비유사도는 각 변수가 다른 변수에 얼마나 종속적인지에 따라 각 변수의 기여도에 가중치를 부여한다. 랜덤 포레스트 비유사도는 다양한 응용 분야에서 사용되어 왔으며, 예를 들어 조직 표지자 데이터를 기반으로 환자 군집을 찾는 데 활용되었다.[^46]

변형

결정 트리 대신 선형 모델이 랜덤 포레스트의 기본 추정기로 제안되고 평가되었으며, 특히 다항 로지스틱 회귀와 나이브 베이즈 분류기가 그 대상이다.[^15][^47][^48] 예측 변수와 목표 변수 간의 관계가 선형인 경우, 기본 학습기가 앙상블 학습기와 동등하게 높은 정확도를 가질 수 있다.[^16][^15]

커널 랜덤 포레스트

기계 학습에서 커널 랜덤 포레스트(KeRF)는 랜덤 포레스트와 커널 방법 간의 연결을 확립한다. 정의를 약간 수정하면 랜덤 포레스트는 커널 방법으로 다시 작성될 수 있으며, 이는 더 해석 가능하고 분석하기 쉽다.[^17]

역사

레오 브레이먼(Leo Breiman)[^18]은 랜덤 포레스트와 커널 방법 간의 연결을 최초로 발견한 사람이다. 그는 트리 구성에서 독립 동일 분포(i.i.d.) 랜덤 벡터를 사용하여 훈련된 랜덤 포레스트가 실제 마진에 작용하는 커널과 동등하다는 점을 지적했다. Lin과 Jeon[^19]은 랜덤 포레스트와 적응적 최근접 이웃 간의 연결을 확립하여 랜덤 포레스트가 적응적 커널 추정으로 볼 수 있음을 시사했다. Davies와 Ghahramani[^20]는 커널 랜덤 포레스트(KeRF)를 제안하고 이것이 최신 커널 방법들을 경험적으로 능가할 수 있음을 보였다. Scornet[^17]은 KeRF 추정량을 최초로 정의하고 KeRF 추정량과 랜덤 포레스트 간의 명시적 연결을 제시했다. 그는 또한 랜덤 포레스트의 두 가지 단순화된 모델인 중심 랜덤 포레스트[^21]와 균일 랜덤 포레스트[^22]에 기반한 커널의 명시적 표현을 제시했다. 그는 이 두 KeRF를 중심 KeRF와 균일 KeRF로 명명하고 일관성 수렴 속도의 상한을 증명했다.

표기법 및 정의

예비 사항: 중심 포레스트

중심 포레스트[^21]는 브레이먼의 원래 랜덤 포레스트를 단순화한 모델로, 모든 속성 중에서 균일하게 하나의 속성을 선택하고 미리 선택된 속성을 따라 셀의 중심에서 분할을 수행한다. 알고리즘은 레벨 k의 완전 이진 트리가 구축되면 멈추며, 여기서 k \in\mathbb{N} 는 알고리즘의 매개변수이다.

균일 포레스트

균일 포레스트[^22]는 브레이먼의 원래 랜덤 포레스트를 단순화한 또 다른 모델로, 모든 특성 중에서 균일하게 하나의 특성을 선택하고 미리 선택된 특성을 따라 셀의 변에서 균일하게 추출된 점에서 분할을 수행한다.

랜덤 포레스트에서 KeRF로

훈련 표본 \mathcal{D}_n ={(\mathbf{X}i, Y_i)}{i=1}^n이 [0,1]^p\times\mathbb{R} 값을 갖는 독립 확률 변수들로 주어지고, 독립 원형 쌍 (\mathbf{X}, Y)과 같은 분포를 따르며, \operatorname{E}[Y^2]<\infty라 하자. 우리는 회귀 함수 m(\mathbf{x})=\operatorname{E}[Y \mid \mathbf{X} = \mathbf{x}]를 추정하여 확률 변수 \mathbf{X}에 대응하는 반응 Y를 예측하고자 한다. 랜덤 회귀 포레스트는 M개의 무작위화된 회귀 트리의 앙상블이다. m_n(\mathbf{x},\mathbf{\Theta}j)를 j번째 트리에 의한 점 \mathbf{x}에서의 예측값이라 하고, 여기서 \mathbf{\Theta}1,\ldots,\mathbf{\Theta}M 은 독립 확률 변수로 일반적 확률 변수 \mathbf{\Theta}와 같은 분포를 따르며 표본 \mathcal{D}n과 독립이다. 이 확률 변수는 노드 분할 및 트리 구성을 위한 샘플링 절차에 의해 유도되는 무작위성을 기술하는 데 사용될 수 있다. 트리들은 결합되어 유한 포레스트 추정량 m{M, n}(\mathbf{x},\Theta_1,\ldots,\Theta_M) = \frac{1}{M}\sum{j=1}^M m_n(\mathbf{x},\Theta_j)을 형성한다. 회귀 트리에 대해 m_n = \sum{i=1}^n\frac{Y_i\mathbf{1}{\mathbf{X}i\in A_n(\mathbf{x},\Theta_j)}}{N_n(\mathbf{x}, \Theta_j)}이며, 여기서 A_n(\mathbf{x},\Theta_j)는 \mathbf{x}를 포함하는 셀로 무작위성 \Theta_j와 데이터셋 \mathcal{D}n으로 설계되며, N_n(\mathbf{x}, \Theta_j) = \sum{i=1}^n \mathbf{1}{\mathbf{X}_i\in A_n(\mathbf{x}, \Theta_j)}이다.

따라서 랜덤 포레스트 추정량은 모든 \mathbf{x}\in[0,1]^d에 대해 m_{M,n}(\mathbf{x}, \Theta_1,\ldots,\Theta_M) =\frac{1}{M}\sum_{j=1}^M \left(\sum_{i=1}^n\frac{Y_i\mathbf{1}{\mathbf{X}i\in A_n(\mathbf{x},\Theta_j)}}{N_n(\mathbf{x}, \Theta_j)}\right)을 만족한다. 랜덤 회귀 포레스트는 두 수준의 평균화를 가지는데, 먼저 트리의 대상 셀에 있는 표본들에 대한 평균화, 그 다음 모든 트리에 대한 평균화이다. 따라서 데이터 포인트 밀도가 높은 셀에 있는 관측값들의 기여는 밀도가 낮은 셀에 속한 관측값들의 기여보다 작다. 랜덤 포레스트 방법을 개선하고 추정 오류를 보정하기 위해 Scornet[^17]은 KeRF를 다음과 같이 정의했다. \tilde{m}{M,n}(\mathbf{x}, \Theta_1,\ldots,\Theta_M) = \frac{1}{\sum{j=1}^M N_n(\mathbf{x}, \Theta_j)}\sum_{j=1}^M\sum_{i=1}^n Y_i\mathbf{1}{\mathbf{X}i\in A_n(\mathbf{x}, \Theta_j)}, 이는 포레스트에서 \mathbf{x}를 포함하는 셀에 속하는 Y_i들의 평균과 같다. M 유한 포레스트의 연결 함수를 K{M,n}(\mathbf{x}, \mathbf{z}) = \frac{1}{M} \sum{j=1}^M \mathbf{1}{\mathbf{z} \in A_n (\mathbf{x}, \Theta_j)}, 즉 \mathbf{x}와 \mathbf{z} 사이에서 공유되는 셀의 비율로 정의하면, 거의 확실하게 \tilde{m}{M,n}(\mathbf{x}, \Theta_1,\ldots,\Theta_M) = \frac{\sum_{i=1}^n Y_i K_{M,n}(\mathbf{x}, \mathbf{x}i)}{\sum{\ell=1}^n K_{M,n}(\mathbf{x}, \mathbf{x}_{\ell})}이 성립하며, 이것이 KeRF를 정의한다.

중심 KeRF

레벨 k의 중심 KeRF 구성은 중심 포레스트와 동일하지만, 예측이 \tilde{m}{M,n}(\mathbf{x}, \Theta_1,\ldots,\Theta_M) 로 이루어지며, 대응하는 커널 함수 또는 연결 함수는 다음과 같다. K_k^{cc}(\mathbf{x},\mathbf{z}) = \sum{k_1,\ldots,k_d, \sum_{j=1}^d k_j=k} \frac{k!}{k_1!\cdots k_d!} \left(\frac 1 d \right)^k \prod_{j=1}^d\mathbf{1}_{\lceil2^{k_j}x_j\rceil=\lceil2^{k_j}z_j\rceil}, \qquad \text{ for all } \mathbf{x},\mathbf{z}\in[0,1]^d.

균일 KeRF

균일 KeRF는 균일 포레스트와 동일한 방식으로 구축되지만, 예측이 \tilde{m}{M,n}(\mathbf{x}, \Theta_1,\ldots,\Theta_M) 로 이루어지며, 대응하는 커널 함수 또는 연결 함수는 다음과 같다. K_k^{uf}(\mathbf{0},\mathbf{x}) = \sum{k_1,\ldots,k_d, \sum_{j=1}^d k_j=k} \frac{k!}{k_1!\ldots k_d!}\left(\frac{1}{d}\right)^k \prod_{m=1}^d\left(1-|x_m|\sum_{j=0}^{k_m-1}\frac{\left(-\ln|x_m|\right)^j}{j!}\right) \text{ for all } \mathbf{x}\in[0,1]^d.

성질

KeRF와 랜덤 포레스트 간의 관계

각 셀의 포인트 수가 제어되면 KeRF와 랜덤 포레스트의 예측은 근접한다:

다음과 같은 수열 (a_n),(b_n) 이 존재하여, 거의 확실하게 a_n\leq N_n(\mathbf{x},\Theta)\leq b_n \text{ and } a_n\leq \frac 1 M \sum_{m=1}^M N_n {\mathbf{x},\Theta_m}\leq b_n. 이 성립한다고 가정하자. 그러면 거의 확실하게, |m_{M,n}(\mathbf{x}) - \tilde{m}{M,n}(\mathbf{x})| \le\frac{b_n-a_n}{a_n} \tilde{m}{M,n}(\mathbf{x}).

무한 KeRF와 무한 랜덤 포레스트 간의 관계

트리의 수 M이 무한대로 가면 무한 랜덤 포레스트와 무한 KeRF를 얻는다. 각 셀의 관측값 수가 유계이면 그 추정량들은 근접한다:

다음과 같은 수열 (\varepsilon_n), (a_n),(b_n)이 존재하여, 거의 확실하게

• \operatorname{E}[N_n(\mathbf{x},\Theta)] \ge 1,
• \operatorname{P}[a_n\le N_n(\mathbf{x},\Theta) \le b_n\mid \mathcal{D}_n] \ge 1-\varepsilon_n/2,
• \operatorname{P}[a_n\le \operatorname{E}\Theta [N_n(\mathbf{x},\Theta)] \le b_n\mid \mathcal{D}n] \ge 1-\varepsilon_n/2, 이 성립한다고 가정하자. 그러면 거의 확실하게, |m{\infty,n}(\mathbf{x})-\tilde{m}{\infty,n}(\mathbf{x})| \le \frac{b_n-a_n}{a_n}\tilde{m}{\infty,n}(\mathbf{x}) + n \varepsilon_n \left( \max{1\le i\le n} Y_i \right).

일관성 결과

Y = m(\mathbf{X}) + \varepsilon라 가정하고, 여기서 \varepsilon는 \mathbf{X}와 독립인 중심 가우시안 잡음이며 유한 분산 \sigma^2<\infty를 갖는다. 또한 \mathbf{X}는 [0,1]^d 위에서 균일 분포를 따르고 m은 립시츠 조건을 만족한다. Scornet[^17]은 중심 KeRF와 균일 KeRF에 대한 일관성 수렴 속도의 상한을 증명했다.

중심 KeRF의 일관성

k\rightarrow\infty이고 n/2^k\rightarrow\infty이면, 모든 n에 대해 상수 C_1>0가 존재하여 다음이 성립한다. \mathbb{E}[\tilde{m}_n^{cc}(\mathbf{X}) - m(\mathbf{X})]^2 \le C_1 n^{-1/(3+d\log 2)}(\log n)^2.

균일 KeRF의 일관성

k\rightarrow\infty이고 n/2^k\rightarrow\infty이면, 상수 C>0가 존재하여 다음이 성립한다. \mathbb{E}[\tilde{m}_n^{uf}(\mathbf{X})-m(\mathbf{X})]^2\le Cn^{-2/(6+3d\log2)}(\log n)^2.

단점

랜덤 포레스트는 단일 결정 트리보다 높은 정확도를 달성하는 경우가 많지만, 결정 트리의 본질적인 해석 가능성을 희생한다. 결정 트리는 선형 모델, 규칙 기반 모델, 어텐션 기반 모델과 함께 쉽게 해석할 수 있는 비교적 소수의 머신러닝 모델 군에 속한다. 이러한 해석 가능성은 결정 트리의 주요 장점 중 하나이다. 이를 통해 개발자는 모델이 데이터로부터 현실적인 정보를 학습했는지 확인할 수 있으며, 최종 사용자는 모델이 내린 결정에 대해 신뢰와 확신을 가질 수 있다.^15 예를 들어, 결정 트리가 결정을 내리기 위해 따르는 경로를 추적하는 것은 매우 간단하지만, 수십 또는 수백 개의 트리가 따르는 경로를 추적하는 것은 훨씬 더 어렵다. 성능과 해석 가능성을 모두 달성하기 위해, 일부 모델 압축 기법은 랜덤 포레스트를 동일한 결정 함수를 충실히 재현하는 최소한의 "본래부터(born-again)" 결정 트리로 변환할 수 있다.[^15][^49][^50]

랜덤 포레스트의 또 다른 한계는 특성이 목표 변수와 선형적으로 상관되어 있는 경우, 랜덤 포레스트가 기본 학습기의 정확도를 향상시키지 못할 수 있다는 점이다.[^15][^16] 마찬가지로 여러 범주형 변수가 있는 문제에서도 그러하다.[^23]

같이 보기

• • • • • • 추가 읽을거리

• • 외부 링크

• 랜덤 포레스트 분류기 설명 (Leo Breiman의 사이트)
• Liaw, Andy & Wiener, Matthew "randomForest를 이용한 분류와 회귀" R News (2002) Vol. 2/3 p. 18 (R용 랜덤 포레스트 패키지 사용에 대한 논의)

---

참고 문헌

[^1]: cite conference first = Tin Kam last = Ho title = 랜덤 결정 포레스트 conference = Proceedings of the 3rd International Conference on Document Analysis and Recognit

[^2]: cite journal first = Tin Kam last = Ho name-list-style = vanc title = 결정 포레스트 구축을 위한 랜덤 부분공간 방법 journal = IEEE Transactions on Pattern Analysis and Machine

[^3]: Kleinberg, Eugene. 확률적 판별

[^4]: Kleinberg, Eugene. 패턴 인식을 위한 과적합 방지 확률적 모델링 방법

[^5]: Kleinberg, Eugene. 확률적 판별의 알고리즘적 구현에 관하여

[^6]: cite journal first = Leo last = Breiman author-link = Leo Breiman name-list-style = vanc title = 랜덤 포레스트 journal = [[Machine Learning (journal) Machine Learning]] year = 2001 vo

[^7]: cite journal last1 = Amit first1 = Yali last2 = Geman first2 = Donald author-link2 = Donald Geman name-list-style = vanc title = 무작위 트리를 이용한 형상 양자화 및 인식

[^9]: 통계적 학습 입문. Springer

[^10]: cite journal first = Tin Kam last = Ho title = 결정 포레스트 생성자의 비교 우위에 대한 데이터 복잡도 분석 journal = Pattern Analysis and Applications volume = 5 i

[^11]: Liaw, Andy. R 패키지 randomForest 문서

[^12]: Piryonesi S. Madeh. 인프라 자산 관리에서 데이터 분석의 역할: 데이터 크기 및 품질 문제 극복. (2020-06-01)

[^13]: 기본 랜덤 포레스트 중요도에 주의하라

[^14]: Lin, Yi. 랜덤 포레스트와 적응적 최근접 이웃

[^15]: Piryonesi, S. Madeh. 성능 지표 유형이 유연 포장 열화 모델링에 미치는 영향을 기계 학습으로 분석. (2021-02-01)

[^16]: Smith, Paul F.. 신경과학에서의 예측을 위한 랜덤 포레스트 회귀와 다중 선형 회귀의 비교. (2013-10-01)

[^17]: cite arXiv first = Erwan last = Scornet title = 랜덤 포레스트와 커널 방법 year = 2015 eprint = 1502.03836 class = math.ST

[^18]: cite journal first = Leo last = Breiman author-link = Leo Breiman title = 예측자 앙상블에 대한 일부 무한 이론 institution = Technical Report 579, Statistics Dept. UCB year = 2000

[^19]: cite journal first1 = Yi last1 = Lin first2 = Yongho last2 = Jeon title = 랜덤 포레스트와 적응적 최근접 이웃 journal = Journal of the American Statistical Association volume =

[^20]: Davies, Alex. 빅데이터를 위한 랜덤 포레스트 커널 및 랜덤 분할 기반 기타 커널

[^21]: cite journal first1 = Leo last1 = Breiman first2 = Zoubin last2 = Ghahramani name-list-style = vanc title = 단순 랜덤 포레스트 모델의 일관성 journal = Statistical Departm

[^22]: Arlot, Sylvain. 순수 랜덤 포레스트 편향 분석

[^23]: Piryonesi, Sayed Madeh. 자산 관리에 대한 데이터 분석의 적용: 온타리오 도로의 열화 및 기후 변화 적응 (박사 학위 논문). (November 2019)

[^24]: 미국 상표 등록 번호 3185828, 2006/12/19 등록.

[^25]: RANDOM FORESTS Health Care Productivity, Inc.의 상표 - 등록 번호 3185828 - 일련번호 78642027 :: Justia Trademarks

[^26]: Heath, D., Kasif, S. and Salzberg, S. (1993). ''k-DT: 다중 트리 학습 방법.'' In ''Proceedings of the Second Intl. Workshop on Multistrategy Learning'', pp. 138-149.

[^27]: cite journal first = Thomas last = Dietterich title = 결정 트리 앙상블 구축을 위한 세 가지 방법의 실험적 비교: 배깅, 부스팅, 무작위화 journal = [

[^28]: Cite Q Q135104889

[^29]: Cite journal doi = 10.1007/s10994-006-6226-1 title = 극도로 무작위화된 트리 journal = Machine Learning volume = 63 pages = 3–42 year = 2006 vauthors = Geurts P, Ernst D, Wehenkel L url =

[^30]: Dessi, N. & Milia, G. & Pes, B. (2013). 마이크로어레이 데이터 분류에서 랜덤 포레스트 성능 향상. Conference paper, 99-103. 10.1007/978-3-642-38326-7_15.

[^31]: Ye, Y., Li, H., Deng, X., and Huang, J. (2008) 숨겨진 웹 검색 인터페이스 탐지를 위한 특성 가중 랜덤 포레스트. Journal of Computational Linguistics and Chinese Language Processing, 13,

[^32]: Amaratunga, D., Cabrera, J., Lee, Y.S. (2008) 강화된 랜덤 포레스트. Bioinformatics, 24, 2010-2014.

[^33]: Ghosh D, Cabrera J. (2022) 고차원 유전체 데이터를 위한 강화된 랜덤 포레스트. IEEE/ACM Trans Comput Biol Bioinform. 19(5):2817-2828. doi:10.1109/TCBB.2021.3089417.

[^34]: Amaratunga, D., Cabrera, J., Shkedy, Z. (2014). DNA 마이크로어레이 및 기타 고차원 데이터의 탐색과 분석. New York: John Wiley. Second Edition. 0.1002/9781118364505.

[^35]: Winham, Stacey & Freimuth, Robert & Biernacka, Joanna. (2013). 예측 성능 향상을 위한 가중 랜덤 포레스트 접근법. Statistical Analysis and Data Mining. 6. 10.1002/sam.11196.

[^36]: Li, H. B., Wang, W., Ding, H. W., & Dong, J. (2010, 10-12 Nov. 2010). 고차원 잡음 데이터 분류를 위한 트리 가중 랜덤 포레스트 방법. Paper presented at the 2010 IEEE 7th Internation

[^37]: cite journal vauthors = Zhu R, Zeng D, Kosorok MR title = 강화 학습 트리 journal = Journal of the American Statistical Association volume = 110 issue = 512 pages = 1770–1784

[^38]: cite conference author=Deng, H. author2=Runger, G. author3=Tuv, E. title=다중값 속성에 대한 중요도 측정의 편향과 해결 방법 conference=Proceedings of the 21st International

[^39]: cite journal vauthors = Altmann A, Toloşi L, Sander O, Lengauer T title = 순열 중요도: 보정된 특성 중요도 측정 journal = Bioinformatics volume = 26 issue = 10 pag

[^40]: cite journal last1 = Strobl first1 = Carolin last2 = Boulesteix first2 = Anne-Laure last3 = Augustin first3 = Thomas name-list-style = vanc title = 분류를 위한 비편향 분할 선택

[^41]: Painsky, Amichai. 트리 기반 방법에서 교차 검증 변수 선택이 예측 성능을 향상시킨다. (2017)

[^42]: cite journal vauthors = Tolosi L, Lengauer T title = 상관된 특성을 사용한 분류: 특성 순위의 신뢰성 문제와 해결 방법 journal = Bioinformatics volume = 27 issue = 14

[^43]: Ortiz-Posadas, Martha Refugio. 생의학 문제에 적용된 패턴 인식 기법. Springer Nature. (2020-02-29)

[^44]: Breiman, Leo. 분류 및 회귀 트리. Routledge. (2017-10-25)

[^45]: https://scikit-learn.org/stable/auto_examples/inspection/plot_permutation_importance.html 31. Aug. 2023

[^46]: cite journal vauthors = Shi T, Seligson D, Belldegrun AS, Palotie A, Horvath S title = 조직 마이크로어레이 프로파일링에 의한 종양 분류: 신세포암에 적용된 랜덤 포레스트 군집화

[^47]: 다중 클래스 분류를 위한 랜덤 포레스트: 랜덤 다항 로짓

[^48]: 데이터베이스 및 전문가 시스템 응용: 제18회 국제 학술대회, DEXA 2007, 레겐스부르크, 독일, 2007년 9월 3-7일, 논문집

[^49]: Sagi, Omer. 설명 가능한 결정 포레스트: 결정 포레스트를 해석 가능한 트리로 변환.. (2020)

[^50]: Vidal, Thibaut. 재탄생 트리 앙상블. PMLR. (2020)