랜덤 포레스트

시리즈의 일부
기계 학습 및 데이터 마이닝
문제 분류 클러스터링 회귀 이상 검출 데이터 클리닝 자동 ML 어소시에이션 규칙 강화 학습 구조화된 예측 기능 엔지니어링 기능 학습 온라인 학습 준지도 학습 비지도 학습 순위 매기기 학습 문법 유도
지도 학습 (분류 • 회귀) 의사결정 트리 앙상블 배깅 부스팅 랜덤 포레스트 k-NN 선형 회귀 네이비 베이즈 인공신경망 로지스틱 회귀 분석 퍼셉트론 관련 벡터 머신(RVM) 서포트 벡터 머신(SVM)
클러스터링 버치 치유하다 계층적 k자형 기대 최대화(EM) DBSCAN 광학 평균 이동
치수 축소 인자 분석 CCA ICA LDA NMF PCA PGD t-SNE
구조화된 예측 그래픽 모델 베이즈 네트 조건부 랜덤 필드 히든 마르코프
이상 검출 k-NN 국소 특이치 계수
인공신경망 자동 인코더 인지 컴퓨팅 딥 러닝 딥 드림 다층 퍼셉트론 RNN LSTM GRU ESN 저장고 계산 제한 볼츠만 기계 GAN somerset. 컨볼루션 뉴럴 네트워크 유넷 트랜스포머 비전. 스파이킹 뉴럴 네트워크 메모리 트랜지스터 전기화학 RAM(ECRAM)
강화 학습 Q-러닝 사사 시간차(TD) 멀티 에이전트 셀프 플레이
인간과의 학습 액티브 러닝 크라우드 소싱 휴먼 인 더 루프
모델 진단 학습 곡선
이론. 커널 머신 바이어스-분산 트레이드오프 컴퓨터 학습 이론 경험적 리스크 최소화 오컴 러닝 PAC 학습 통계학 학습 VC 이론
기계학습장 NeurolIPS ICML ML JMLR ArXiv:cs.LG
관련 기사 인공지능 용어집 기계 학습 연구를 위한 데이터 세트 목록 기계학습의 개요
v t

랜덤 포레스트 또는 랜덤 의사결정 포레스트는 분류, 회귀 및 훈련 시간에 다수의 의사결정 트리를 구성함으로써 작동하는 기타 작업을 위한 앙상블 학습 방법이다.분류 태스크의 경우 랜덤 포리스트의 출력은 대부분의 트리에 의해 선택된 클래스입니다.회귀 작업의 경우 개별 나무의 평균 또는 평균 예측이 ^[1][2]반환됩니다.랜덤 의사결정 포레스트는 의사결정 트리의 훈련 ^{[3]: 587–588} 세트에 과적합하는 습관을 수정한다.랜덤 포레스트는 일반적으로 의사결정 트리를 능가하지만, 그 정확도는 경사 부스트^{[citation needed]} 트리보다 낮다.그러나 데이터 특성은 ^[4][5]성능에 영향을 줄 수 있습니다.

무작위 의사결정 포레스트의 첫 번째 알고리즘은 1995년 Tin Kam^[1] Ho가 무작위 부분 공간 ^[2]방법을 사용하여 만들었다. Ho의 공식에서, 이것은 유진 클라인버그가 ^[6][7][8]제안한 분류에 대한 "단층적 식별" 접근방식을 구현하는 방법이다.

이 알고리즘의 확장 기능은 2006년 "랜덤 포레스트"를 상표로 등록한^[11] Leo^[9] Breiman과 Adele Cutler에 ^[10]의해 개발되었습니다(2019년 현재^[update], Minitab, Inc.^[12] 소유).이 확장은 Breiman의 "배깅" 아이디어와 특징의 무작위 선택을 결합하며, Ho에 의해^[1] 처음 도입된 후 Amit과^[13] Geman에 의해 독립적으로 도입되어 분산 제어된 의사결정 트리의 컬렉션을 구축한다.

랜덤 포레스트는 구성이 거의 필요 없는 상태에서 광범위한 데이터에 대해 합리적인 예측을 생성하기 때문에 기업에서 "블랙박스" 모델로 자주 사용됩니다.

역사

무작위 의사결정 포레스트의 일반적인 방법은 1995년에 ^[1]Ho에 의해 처음 제안되었다.Ho는 사선 하이퍼플레인으로 분할된 나무의 숲이 선택된 특징 치수에만 민감하도록 무작위로 제한되는 한 과도한 훈련에 시달리지 않고 성장에 따라 정확성을 얻을 수 있다는 것을 확립했다.같은^[2] 선에 따른 후속 연구에서는 일부 기능 치수에 대해 랜덤하게 영향을 받지 않는 한 다른 분할 방식도 동일하게 동작한다는 결론을 내렸습니다.더 복잡한 분류기(더 큰 숲)가 거의 단조롭게 더 정확해지는 것에 대한 이러한 관찰은 분류기의 복잡성이 과적합에 의해 손상되기 전에 특정 수준의 정확도로만 증가할 수 있다는 일반적인 믿음과 극명한 대조를 보인다.과도한 훈련에 대한 숲 방법의 저항성에 대한 설명은 클라인버그의 확률적 ^[6][7][8]변별 이론에서 찾을 수 있다.

랜덤 포레스트에 대한 Breiman의 개념의 초기 개발은 단일 트리를 성장시키는 맥락에서 노드를 분할할 때 사용 가능한 결정의 랜덤 서브셋을 검색하는 아이디어를 도입한 Amit과 Geman의^[13] 작업에 의해 영향을 받았다.Ho의 무작위^[2] 부분 공간 선택 아이디어는 무작위 포레스트 설계에도 영향을 미쳤다.이 방법에서는 나무숲을 성장시켜 각 나무 또는 각 노드를 맞추기 전에 무작위로 선택된 서브스페이스에 트레이닝 데이터를 투영함으로써 나무 사이의 변화를 도입한다.마지막으로, 결정론적 최적화가 아닌 각 노드의 결정이 무작위 절차에 의해 선택되는 무작위 노드 최적화의 아이디어가 Thomas G에 의해 처음 도입되었다. 디에테리히.^[14]

무작위 숲의 적절한 도입은 Leo Breiman의 ^[9]논문에서 이루어졌다.이 문서에서는 CART와 같은 절차를 사용하여 랜덤 노드 최적화 및 배깅을 조합하여 상관되지 않은 트리의 포레스트를 구축하는 방법에 대해 설명합니다.또한, 본 논문은 랜덤 포레스트의 현대적 실천의 기초를 형성하는 몇 가지 요소, 특히 다음과 같은 몇 가지 이전에 알려진 것과 새로운 것을 결합한다.

1. 일반화 오류의 추정치로 봉지 밖의 오류를 사용합니다.
2. 치환을 통한 변수 중요도 측정.

보고서는 또한 숲의 나무 강도와 그 상관관계에 따라 달라지는 일반화 오류에 대한 바운드의 형태로 무작위 숲에 대한 첫 번째 이론적 결과를 제공한다.

알고리즘.

예비: Decision Tree 학습

Decision Tree는 다양한 기계 학습 태스크에 널리 사용되는 방법입니다.나무 학습은 "데이터 마이닝을 위한 기성 절차로 기능하기 위한 요건을 충족시키는 데 가장 근접한다"고 Hastie 등은 말한다.이는 "규모 조정 및 기타 특징 값의 다양한 변환 하에서 불변하며 관련 없는 특징의 포함에 강하며 검사 가능한 모델을 생성하기 때문"이다.그러나 정확하지 않은 경우는 거의 없습니다.^{[3]: 352}

특히, 매우 깊게 자란 나무는 매우 불규칙한 패턴을 학습하는 경향이 있습니다. 즉, 그들은 훈련 세트에 너무 잘 맞습니다. 즉, 편중이 낮지만 편차가 매우 큽니다.랜덤 포레스트는 ^{[3]: 587–588} 분산 감소를 목표로 동일한 훈련 세트의 서로 다른 부분에 대해 훈련되는 다중 심층 의사결정 트리의 평균을 내는 방법입니다.이는 편견이 약간 증가하고 해석 가능성이 일부 상실되는 대신 발생하지만, 일반적으로 최종 모델에서 성능을 크게 향상시킨다.

포레스트는 의사결정 트리 알고리즘의 노력을 하나로 모으는 것과 같습니다.많은 나무들의 팀워크를 취함으로써 하나의 랜덤 트리의 성능을 향상시킵니다.매우 유사하지는 않지만, 포레스트는 k-fold 교차 검증의 효과를 제공한다.

배깅

랜덤 포레스트 훈련 알고리즘은 트리 학습자에게 부트스트랩 집약 또는 배깅의 일반적인 기술을 적용합니다.반응이 Y = y₁, ..., y인_n 교육 세트 X = x₁, ..., x가_n 주어진 경우, 반복적으로(B회) 배깅은 교육 세트를 대체하여 랜덤 표본을 선택하고 다음 표본에 트리를 적합시킵니다.

b = 1, ..., B의 경우:

1. 예를 들어 X, Y에서 n개의 트레이닝 예를 샘플로 추출합니다.이것들을_b X, Y라고_b 부릅니다.
2. X, Y에_b 대해_b 분류 또는 회귀_b 트리 f를 훈련합니다.

훈련 후 x'에 대한 모든 개별 회귀 트리의 예측을 평균화하여 보이지 않는 표본 x'에 대한 예측을 할 수 있습니다.

$({displaystyle {hat {f}}=sum frac {1}{B}\sum _{b=1}^{B}f_{b}(x'))$

또는 분류목의 경우 다수결로 처리한다.

이 부트스트래핑 절차는 치우침을 증가시키지 않고 모형의 분산을 감소시키기 때문에 모형 성능을 향상시킵니다.즉, 단일 나무의 예측은 훈련 세트에서 소음에 매우 민감하지만, 나무가 상관 관계가 없는 한 많은 나무의 평균은 그렇지 않다.단순히 단일 훈련 세트에서 많은 트리를 훈련시키면 강한 상관관계가 있는 트리(또는 훈련 알고리즘이 결정론적인 경우에는 같은 트리도 여러 번)를 얻을 수 있다. 부트스트랩 샘플링은 다른 훈련 세트를 보여줌으로써 트리의 상관관계를 해제하는 방법이다.

또한 예측의 불확실성에 대한 추정은 x'에 대한 모든 개별 회귀 트리에서 예측의 표준 편차로 할 수 있다.

$({displaystyle\displaystyle={b=1}^{B}(f_{b}(x')-{\hat {f})^2}}{B-1}})}$

표본/나무 수 B는 자유 모수입니다.일반적으로 트레이닝 세트의 크기와 특성에 따라 수백에서 수천 그루의 트리가 사용됩니다.최적의 트리 수 B는 교차 검증을 사용하거나 부트스트랩 ^[15]샘플에 x가 없는_i 트리만을 사용하여 각 트레이닝 샘플_i x의 평균 예측 오차인 봉지 오류를 관찰함으로써 찾을 수 있습니다.훈련과 테스트 오류는 몇 개의 트리를 맞춘 후에 안정되는 경향이 있습니다.

배깅에서 랜덤 포레스트까지

위의 절차에서는 트리의 원래 배깅알고리즘에 대해 설명합니다.랜덤 포레스트에는 또 다른 유형의 배깅스킴도 포함됩니다.즉, 학습 프로세스의 각 후보에서 기능의 랜덤 서브셋을 선택하는 수정된 트리 학습 알고리즘을 사용합니다.이 프로세스를 "피처 배깅"이라고 부르기도 합니다.그 이유는 일반적인 부트스트랩샘플 내의 트리의 상관관계입니다.1개 또는 소수의 피쳐가 응답변수(타깃 출력)의 매우 강력한 프레딕터일 경우 이들 피쳐는 많은 B 트리에서 선택되기 때문에 상관관계가 생깁니다.Ho는 ^[16]배깅과 랜덤 부분공간 투영이 다양한 조건에서 정확도 향상에 어떻게 기여하는지에 대한 분석을 제공한다.

통상, p 피쳐의 분류상의 문제에 대해서는,^{[3]: 592} 분할 마다 「p」(반올림) 피쳐가 사용됩니다.회귀 문제에 대해 발명가는 최소 노드 ^{[3]: 592} 크기 5를 기본값으로 p/3(반올림)를 권장합니다.실제로 이들 파라미터의 최선의 값은 문제에 따라 다르므로 조정 ^{[3]: 592} 파라미터로 취급해야 합니다.

기타 트리

랜덤화의 한 단계를 추가하면 매우 랜덤화된 트리(ExtraTree)가 생성됩니다.개별 트리의 앙상블이라는 점에서 일반적인 랜덤 포레스트와 비슷하지만, 두 가지 주요 차이점이 있다. 첫째, 각 트리는 (부트스트랩 샘플이 아닌) 전체 학습 샘플을 사용하여 훈련되고 둘째, 트리 학습자의 하향식 분할이 랜덤화된다.고려 중인 각 특징(예: 정보 게인 또는 지니 불순물)에 대해 국소적으로 최적의 컷포인트를 계산하는 대신 랜덤 컷포인트를 선택한다.이 값은 피쳐의 경험적 범위 내의 균일한 분포(트리의 교육 세트)에서 선택됩니다.그런 다음 랜덤으로 생성된 모든 분할 중에서 가장 높은 점수를 얻은 분할을 선택하여 노드를 분할합니다.일반적인 랜덤 포레스트와 마찬가지로 각 노드에서 고려되는 랜덤으로 선택된 기능의 수를 지정할 수 있습니다.이 파라미터의 기본값은 분류의 경우 p$\$ $회귀$의 경우$$p\$displaystyle$$p$입니다.$여기$서 p$\display$p는$$ ^[17]모델 내의 피쳐 수입니다.

특성.

가변 중요도

랜덤 포레스트를 사용하여 회귀 또는 분류 문제에서 변수의 중요도를 자연스럽게 순위를 매길 수 있습니다.다음 기술은 Breiman의 원본 논문에서^[9] 설명되었으며 R 패키지 랜덤으로 구현됩니다.숲.^[10]

데이터 $집합$에서 변수 중요도를 측정하는 첫 번째 ${\displaystyle {단계}_{}}$는 D n${\displaystyle =}$ { (${\displaystyle {}_{}{X}_{}}$ ${\displaystyle {}_{}}$ ,${\displaystyle {}_{}{Y}_{}}$ ${\displaystyle i_{}^{}}$ )${\displaystyle {}_{}^{}}$} ${\displaystyle {\mathrm{i}}_{}^{}}$ ${\displaystyle {=}_{}^{}}$ n ( \ $displaystyle$\$mathcal${$D} _${ n } = \ { ( $X$_ {$$$i$ ) 。$Y_{i}\}_{i=1}^{n}$은(는) 데이터에 랜덤 포레스트를 적합시킵니다.장착 프로세스 중에 각 데이터 포인트의 봉지 외 오류가 기록되고 포레스트 전체에 걸쳐 평균화됩니다(훈련 중에 봉지를 사용하지 않을 경우 독립 테스트 세트의 오류를 대체할 수 있습니다).

훈련 후 $\displaystyle$j -th$$ 피쳐의 중요성을 측정하기 위해 훈련 데이터 간에 $\displaystyle$j -th$$ 피쳐 값을 치환하고 이 교란된 데이터 세트에 대해 아웃오차를 다시 계산합니다.$\display$ j$$-th$$ 피쳐의 중요도 점수는 모든 트리의 치환 전후의 봉지 이탈 오류의 차이를 평균하여 계산됩니다.점수는 이러한 차이의 표준 편차에 의해 정규화됩니다.

이 점수에 대해 큰 값을 생성하는 피쳐가 작은 값을 생성하는 피쳐보다 더 중요한 것으로 순위가 매겨집니다.가변 중요도 측정의 통계적 정의는 ^[18]Zhu 등에 의해 제공되고 분석되었다.

이 변수 중요도 결정 방법에는 몇 가지 단점이 있습니다.수준 수가 다른 범주형 변수를 포함하는 데이터의 경우 랜덤 포레스트는 수준이 더 높은 속성으로 치우칩니다.이 문제를^[19][20][4] 해결하기 위해 부분 순열이나 편향되지^[21][22] 않은 나무 재배와 같은 방법을 사용할 수 있습니다.데이터에 출력과 유사한 관련성을 가진 상관 특성 그룹이 포함되어 있으면 더 작은 그룹이 더 큰 ^[23]그룹보다 선호됩니다.

가장 가까운 네이버와의 관계

랜덤 포레스트와 k-근접 인접 알고리즘(k-NN)의 관계는 ^[24]2002년에 Lin과 Jeon에 의해 지적되었다.둘 다 소위 말하는 가중 이웃 제도라고 볼 수 있습니다.${\displaystyle {}_{}}$ 모델은 교육${\displaystyle }$세트 {${\displaystyle {}_{}}$( ${\displaystyle x_{}}$ i${\displaystyle {}_{}}$, y ${\displaystyle i_{}^{}}$) } ${\displaystyle {\mathrm{i}}_{}^{}}$ ${\displaystyle {=}_{}^{}}$ 1$$({$displaystyle \{i},y_{i})$에서 제작됩니다.$\}_{i=1}^{$$n}:$ 가중치$$ 함수 W:로 공식화된 점의 "$후드"$를 보고 새로운 점 x'에 대해$y$를 예측합니다$.$

${\displaystyle {hat {y}=\sum _{i=1}^{n}W(x_{i},x'),y_{i}.}$

${\displaystyle {}_{}}$서${\displaystyle }$W ( x${\displaystyle {}_{}{i}_{}}$ , ${\displaystyle {}^{}}$ ${\displaystyle )}$ )$${ $displaystyle$W ( $x$_ {$i$ , $x$' ) }는$$ 같은 트리의 새로운 포인트x'에 상대적인 i번째 트레이닝 포인트의 음이 아닌 가중치입니다.특정 x'의 경우, $포인트{\displaystyle {}_{}}$($표시$ 스타일$x_i$})의 가중치는 1이 되어야 한다.체중 함수는 다음과 같이 제공됩니다.

• k-NN에서 가중치는 W${\displaystyle (x_{}}$ i${\displaystyle {}_{}}$ ${\displaystyle {}^{}}$θ) $=$ $(x_{i,x$')=$xx$가 x'에 가장 가까운 k점 중 하나이면 frac_i${1}{k}}$이고, 그렇지 않으면 0입니다.
• 트리에서 x가 x'와 같은 잎의 k' 포인트 중 하나이면_i${\displaystyle }$W ( ${\displaystyle {}_{}{i}_{}}$ , $x$ ${\displaystyle )}$ ) ${\displaystyle =}$ ${\displaystyle 1\frac{\mathrm{}}{}}$ ${\displaystyle \frac{{}^{}}{}}$ ( \ $displaystyle W$ ( x _ { i , x ' ) =$frac${$1$} {k '$$}}} 입니다.

포레스트는 개별 $가중치{\displaystyle {}_{}}$ ${\displaystyle {함수}_{}}$Wj(\$displaystyle W_{$j$\})$를 가진 m개 나무 세트의 예측을 평균화하기 때문에 예측은 다음과 같습니다.

${\displaystyle {hat {y}}=sum frac {1}{m}\sum _{j=1}^{m}\sum _{i=1}^{n}W_{j}(x_{i},x'),y_{i}=\sum _{i=1}^{n}\leftflac {1}{m}\sum _{j=1}^{m}W_{j}(x_{i,x')\right),y_{i}.}$

이는 전체 숲이 다시 개별 나무의 가중치를 평균하는 가중치 근린구조임을 보여준다.이 해석에서 x'의 이웃은 $(\$i$$})의 모든 $tree{\displaystyle }$j(\$displaystyle$ j$)$에서 동일한 잎을 공유하는 $지점$입니다. 이와 같이 x'의 이웃은 트리의 구조, 즉 훈련 세트의 구조에 따라 복잡한 방식으로 달라집니다.린과 전은 랜덤 포레스트에 의해 사용되는 이웃의 모양이 각 ^[24]특성의 지역적 중요성에 적응한다는 것을 보여준다.

랜덤 포레스트를 사용한 비지도 학습

구성의 일부로서 랜덤 포레스트 예측 변수는 자연스럽게 관측치 사이의 차이점을 측정한다.라벨이 부착되지 않은 데이터 간의 랜덤 포레스트 차이성 측정을 정의할 수도 있다. 아이디어는 "관측된" 데이터와 적절하게 생성된 합성 ^[9][25]데이터를 구별하는 랜덤 포레스트 예측기를 구성하는 것이다.관측된 데이터는 레이블이 없는 원본 데이터이며 합성 데이터는 기준 분포에서 추출됩니다.랜덤 포레스트 차이성은 혼합 변수 유형을 매우 잘 처리하고 입력 변수의 단조로운 변환에 불변하며 외부 관측치에 강력하기 때문에 매력적일 수 있다.랜덤 포레스트 차이성은 고유 변수 선택으로 인해 많은 수의 반연속 변수를 쉽게 다룬다. 예를 들어, "Addcl 1" 랜덤 포레스트 차이성은 각 변수가 다른 변수에 얼마나 의존하는지에 따라 각 변수의 기여도를 가중치한다.랜덤 포레스트 차이성은 조직 마커 ^[26]데이터를 기반으로 환자의 클러스터를 찾는 등 다양한 애플리케이션에서 사용되어 왔다.

변종

의사결정 트리 대신, 선형 모델이 랜덤 포레스트, 특히 다항 로지스틱 회귀 분석과 순진한 베이즈 분류기에서 ^[5][27][28]기본 추정기로 제안되고 평가되었다.예측 변수와 목표 변수의 관계가 선형인 경우 기본 학습자는 앙상블 ^[29][5]학습자와 동일하게 높은 정확도를 가질 수 있습니다.

커널 랜덤 포레스트

기계학습에서 커널 랜덤 포레스트(KeRF)는 랜덤 포레스트와 커널 메서드 간의 연결을 확립합니다.정의를 약간 수정함으로써 랜덤 포레스트를 커널 메서드로 다시 작성할 수 있습니다.커널 메서드는 해석하기 쉽고 ^[30]분석하기 쉽습니다.

역사

Leo^[31] Breiman은 랜덤 포레스트와 커널 메서드의 연관성을 최초로 발견한 사람이다.그는 트리 구성에서 i.i.d. 랜덤 벡터를 사용하여 재배되는 랜덤 포레스트는 진정한 여백에 작용하는 커널과 동등하다고 지적했다.Lin과^[32] Jeon은 랜덤 포레스트와 적응형 가장 가까운 네이버 간의 연결을 확립하여 랜덤 포레스트가 적응형 커널 추정치로 보일 수 있음을 암시합니다.Davies와^[33] Ghahramani는 랜덤 포레스트 커널을 제안했고 이것이 최첨단 커널 메서드를 경험적으로 능가할 수 있다는 것을 보여주었다.디스콘셋은^[30] 먼저 KeRF 추정치를 정의하고 KeRF 추정치와 랜덤 포레스트 사이의 명시적 연결을 제공했다.그는 또한 중심 랜덤^[34] 포레스트와 균일한 랜덤 포레스트,^[35] 즉 랜덤 포레스트의 두 가지 단순화된 모델인 커널에 대해 명시적인 표현을 제공했습니다.그는 이 두 개의 KeRF 중심 KeRF와 균일한 KeRF로 명명하고 이들의 일관성 비율에 대한 상한을 증명했다.

표기법 및 정의

예비:중심림

중심^[34] 포레스트는 Breiman의 원래 랜덤 포레스트를 단순화한 모델로, 모든 속성 중에서 속성을 균일하게 선택하고 사전 선택 속성을 따라 셀 중앙에서 분할을 수행합니다.$레벨{\displaystyle }$k(\$displaystyle$ k$)$의 완전 바이너리 트리가 구축되면 알고리즘이 정지됩니다$.$서 k$displaystyle k\in\mathbb$ {N$$$})$는 알고리즘의 파라미터입니다.

균일한 숲

균일한^[35] 포레스트는 Breiman의 원래 랜덤 포레스트의 또 다른 단순화된 모델로서, 모든 피처 중에서 균일하게 피처를 선택하고 미리 선택된 피처를 따라 셀 측면에 균일하게 그려진 포인트에서 분할을 수행합니다.

랜덤 포레스트에서 KeRF로

교육 샘플 ${\displaystyle D_{}}$ n ${\displaystyle =}${ ( ${\displaystyle {}_{}}$i , ${\displaystyle {}_{}{i}_{}}$ ) ${\displaystyle {}_{}^{}}$ ${\displaystyle i_{}^{}}$ ${\displaystyle {=}_{}^{}}$ ${\displaystyle 1_{}^{}}$ { $style${$mathcal${ $D} _$ { n } = \ { \ { \ $mathbf${ $X } _$ { $i$} }[0,1]p의 Y_{나는})\와 같이}_{i=1}^{n}}×R{\displaystyle[0,1]^{p}\times}독립 확률 변수 어디 E⁡[Y2]<>은 독립된 프로토 타입 쌍(X, Y){\displaystyle(\mathbf{X},Y)},;∞{\displaystyle \operatorname{E}[Y^{2}]&lt으로 유통, \infty}-valued{R}\mathbb. 우리는 번째 예측을 목표로 한다.eresp$회귀{\displaystyle }$ $함수{\displaystyle }$ m${\displaystyle (x\mathbf{})}$ ${\displaystyle =}$ ${\displaystyle E}$ ${\displaystyle [}$ [ Y${\displaystyle x\mathbf{}}$ X$$${\displaystyle =}$ $]$ { $displaystyle$m ( \ $mathbf { x$ } ) = \$operatorname${ E } [$Y$\ $mid$ \ $mathbf$$$}$$$=${ E } 를 추정하여 랜덤 $변수{\displaystyle \mathbf{}}$X { \ $displaystyle Y$$$} 와 관련지어집니다.랜덤화 회귀 트리.${\displaystyle m_{}}$n (${\displaystyle x\mathbf{}}$ , ${\displaystyle {}_{}}$j$$) { $displaystyle m_{n}(\mathbf {x}$ ,\$mathbf${\})를 $나타냅니다{\displaystyle {}_{}}$.$Theta$}$_{j}}$$$j {\$displaystyle$ j} -th$$ 트리의 $지점{\displaystyle }$$$x {\$displaystyle$ $\$$mathbf {x}$의 예측값. 여기서 ${\displaystyle {}_{}}$1, ${\displaystyle ...,{}_{}}$M \$displaystyle \mathbf {$x}$Theta } _{1},\ldots,\mathbf$${\}$$Theta$}$_{M}$은(는) 독립 랜덤 변수이며 일반 랜덤 변수${style$ \mathbf$${}로 분포됩니다.${\displaystyle {샘플}_{}}$ Dn(\$displaystyle\mathcal {D}}_{n$과는 무관한 Theta }$$$}$ } 。이 랜덤 변수는 노드 분할에 의해 유발되는 랜덤성과 트리 구축을 위한 샘플링 절차를 설명하기 위해 사용할 수 있습니다.트리가 결합되어 유한 포레스트 $추정치{\displaystyle {}_M}$ ,${\displaystyle {}_{}n\mathbf{}}$ (${\displaystyle }$x , ${\displaystyle \underset{}{\overset{}{\theta }}}$ 1, ${\displaystyle ...}$ , ${\displaystyle {\theta }_{}}$M )$=$ ${\displaystyle 1\frac{\mathrm{}}{}}$ ${\displaystyle \frac{M}{}}$ (${\displaystyle \underset{}{\overset{}{}}}$j ${\displaystyle \underset{}{\overset{}{=}}}$ ${\displaystyle \underset{}{\overset{}{1}}}$ M ${\displaystyle n_{}}$( ${\displaystyle x\mathbf{}}$ ,${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle j_{}}$ $){$ $display$ m$_$ {$M$ , $n$} ( \ $mathbf$ { x$}$ , \ $Theta _$ {1} \$Ldots$ ,$Ta$ )가$됩니다.$${\displaystyle \underset{}{\overset{}{}}\frac{{n\mathbf{}}_{}}{}}$ ${\displaystyle \frac{Y_{}}{}}$ ${\displaystyle \frac{{}_{}{\mathbf{}}_{}}{}}$ ${\displaystyle \frac{{{\mathbf{}}_{}}_{}}{}}$ X ${\displaystyle \frac{{{}_{}{a}_{}}_{}}{}}$ A${\displaystyle \frac{{{}_{}}_{}}{}}$(${\displaystyle \frac{{}_{}x\mathbf{}}{}}$ ,${\displaystyle \frac{{}_{}}{{}_{}}}$ ${\displaystyle \frac{{j_{}}_{}}{}}$) N (${\displaystyle \frac{}{}}$x , ${\displaystyle \frac{{\theta }_{}}{}}$ ${\displaystyle \frac{{\mathrm{}}_{}}{}}$) { $displaystyle$ m $_${ $n$} = \ $sum$_ { i$}^{$ n } { \ $frac$ { Y $_${ i$$} \ $mathbf { X$} $_ i$ } \ $in$a _ { $n$（ \ $mathb$）$x{\displaystyle {\mathrm{}}_{}}$$(\$$displaystyle$$\Theta_{$j$\})$ 및$$ 데이터 $세트{\displaystyle {\mathcal{}}_{}}$ $(\$n})으로 $설계$된 ${\displaystyle x_{}(\backslash }$displaystyle\$mathbf$ ${$$x})$ 및 n${\displaystyle {}_{}x\mathbf{}}$, ${\displaystyle {display}_{}}$ j${\displaystyle {}_{}}$ ${\displaystyle \underset{}{\overset{}{=}}}$ ${\displaystyle {{}_{}}_{}}$ ${\displaystyle {{\mathbf{}}_{}}_{}}$ ${\displaystyle {{}_{}{}_{}{A}_{}}_{}}$($x$ j$)$를 $포함$합니다.$n}\mathbf {1}_{\mathbf {X}_{i}\in$ A_${n}(\mathbf${$x},\Theta _{$j$\}\})\}:$

따라서 랜덤 포레스트 추정치는 모든 $x{\displaystyle \mathbf{}[}$ [${\displaystyle 0}$, ${\displaystyle 1{}^{}}$]$d${\$displaystyle \mathbf {x } \$$in{\displaystyle {}_{}}$ [0 , $1 ]^{$d$\}\},$${\displaystyle M_{}}$ ${\displaystyle n_{}}$(${\displaystyle \frac{{x\mathbf{}}_{}}{}}$ ,${\displaystyle {\theta \mathrm{}}_{}}$1,${\displaystyle }$… , ${\displaystyle {\theta }_{}}$M ) ${\displaystyle =}$ ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{\mathrm{M}}}\underset{}{\overset{}{m}}}$ 1 M ${\displaystyle \underset{}{\overset{}{=}}}$ ${\displaystyle 1\frac{\mathrm{}}{}}$ M （${\displaystyle \underset{n}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{\mathrm{i}}}}$ ${\displaystyle \underset{}{\overset{}{=}}}$ 1 ${\displaystyle \underset{}{\overset{}{}}\frac{{}_{}{{}_{}}_{}{}_{}{\mathbf{}}_{}}{}}$ ${\displaystyle \frac{{{\mathbf{}}_{}}_{}}{}}$ ${\displaystyle \frac{{{}_{}}_{}}{}}$ ${\displaystyle \frac{{X_{}}_{}}{}}$ ）${\displaystyle \frac{{{}_{}}_{}}{}}$ 。$_{1},\ldots,\Theta _{M}=sum$_{$j=1}^{M}\left(\sum$_{$i=1}^{n}{\frac {Y_{$i}\$mathbf {X}_i}\in$ {$xf}$a_${n})$따라서 데이터 점의 밀도가 높은 셀에 있는 관측치의 기여는 인구가 적은 셀에 속하는 관측치의 기여보다 작습니다.랜덤 포레스트 방법을 개선하고 잘못된 추정을 보상하기 위해 디스켓은^[30] 다음과 같이 KeRF를 정의했다.

$({displaystyle {m}_{M,n}(\mathbf {x},\Theta _{1},\Theta _{M})=blac {1}{\sum _j=1}{M}N_{n}(\mathbf {x},\Theta _{j})_{{M})_1}_SUM})_{{{{{{{{}}}_SM}_SM}을(\sum})Y_{i}\mathbf {1}_{\mathbf {X}_{i}\in A_{n}(\mathbf {x},\Theta _{j}})$

이는 포레스트의 x$\$ 가$$ $포함$된 셀에 $\$ 가 $떨어지는{\displaystyle {}_{}}$ 평균과 동일합니다.$M{\displaystyle }${\$displaystyle$ M$}$ 유한$$ 포레스트의 $연결{\displaystyle {}_{}}$ 함수를 K${\displaystyle M_{},}$ ${\displaystyle n_{}}$ (${\displaystyle x\mathbf{}}$, z ) ${\displaystyle =}$ ${\displaystyle \frac{1}{}}$ M${\displaystyle \underset{j}{\overset{}{}}}$ j ${\displaystyle \underset{}{\overset{}{=}}}$ ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{}}{\mathbf{}}_{}}$ 1 ${\displaystyle {\mathbf{}{}_{}}_{}}$ A ${\displaystyle {n\mathbf{}{}_{}}_{}}$( x ,${\displaystyle {{\theta }_{}}_{}}$ j$$) { $displaystyle K_{M$,$n$} (\$mathbf {x$, \ $mathbfz$} ) =$frAC { 1$ .x$(\$와$$z(\$displaystyle \mathbf {z$ $간$에 공유되는 셀의 이온은${\displaystyle {\stackrel{}{}}_{}}거의{\displaystyle {\stackrel{}{}}_{}}$ ${\displaystyle {확실}_{}}$하게${\displaystyle {}_{}}$m ~${\displaystyle {}_{}{M}_{}}$ ,${\displaystyle n\mathbf{}}$ (${\displaystyle \frac{{\mathbf{}}_{}}{}}$ ,${\displaystyle {\mathrm{}}_{}{1}_{}}$, … ,${\displaystyle {}_{}}$) M ) ${\displaystyle \frac{\underset{}{\overset{}{=}}}{}}$ ${\displaystyle \frac{\underset{}{\overset{}{=}}}{}}$ ${\displaystyle \frac{1_{}{N}_{}}{}}$Y ${\displaystyle \frac{K\mathbf{}}{}}$ M , n${\displaystyle \frac{}{}}$, n , ${\displaystyle \frac{\underset{}{\overset{}{n}}}{}}$ ( x , x ) 、 i${\displaystyle \frac{{}_{}}{\underset{}{\overset{}{}}}}$ ${\displaystyle \frac{{}_{}}{}}$ 、 n 、 ${\displaystyle \frac{n_{}}{}}$ 、 n 、 n${\displaystyle \frac{{}_{}}{}}$、 ${\displaystyle \frac{n_{}}{}}$ ) 、 n 、 n 、 n 、 n 、 n 、 n 、 n 、 n 、 n 、 n .$athbf {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} _{\ell$ KeRF를 정의합니다.

중심 KeRF

$레벨{\displaystyle }$ k$(\displaystyle$ k$)$의 Centered KeRF의 구성은 m${\displaystyle {}_{}}$~${\displaystyle M\mathbf{}}$ , n${\displaystyle {}_{}}$(${\displaystyle }$x , ${\displaystyle {1\mathrm{}}_{}}$1, ${\displaystyle ...}$ , ${\displaystyle {\theta }_{}}$M$$) \ $displaystyle${$m} _$ {$M$ , $n$} （ \ $mathbf${ x$}$ , \ $Ta${ $1$} )에 $의해{\displaystyle {\stackrel{}{}}_{}}$ 예측되는 것을 제외하고 중심 포레스트와 동일합니다$.$

${\displaystyle {begin{aligned}K_{k}^{cc}(\mathbf {x},\mathbf {z})=\sum _{k_{1}^{d}k_{j}=k}&{\frac {k}!}{k_{1}!\cdots k_{d}!}}\frac {1}{d}\right)^{k}\text _{j=1}^{d}\mathbf {1}_{\lceil 2^{k_{j}x_{j}\rceil =\lceil 2^{k_{j}z_{j}\rceil },\\\&{text{f} for }\mathbin {}, \lceil}, \lceil {kf}\end { aligned}}$

균일한 KeRF

균일한 KeRF는 균일한 포레스트와 같은 방법으로 구축됩니다.단, 예측은 m${\displaystyle {\stackrel{}{}}_{}}$~${\displaystyle {}_M}$ ,${\displaystyle {}_{}{n}_{}}$ (${\displaystyle x\mathbf{}}$ ${\displaystyle ,}$ ${\displaystyle {\theta \mathrm{}}_{}}$ 1, ${\displaystyle ...}$ , ${\displaystyle m_{}}$M$$) (\$style${$tilde${$m} _$ {$M$ , $n$} (\ $mathbf {x}$ , \ $Theta$_ {$1$ , \ $ldots$, \ $Ta$_ M$$$}$ ) )에 의해 이루어집니다.

$\displaystyle K_{k}^{uf}(\mathbf {0},\mathbf {x})=\sum _{k_{1},\ldots,k_{d},\sum _{j}k=k}{\frac {k}!}{k_{1}!\ldots k_{d}!}}\frac {1}{d}\right)^{k}\frac {{m=1}^{d}\left(1-x_{m}\sum _{j=0}^{k_{m}-1}{\frac {(-\ln x_{m})^{j}}{j}!}\right){\text{모든 }}\mathbf {x}\in [0,1]^{d}.}$

특성.

KeRF와 랜덤 포레스트의 관계

각 셀의 점 수를 제어하면 KeRF와 랜덤 포레스트가 제공하는 예측은 근접하다.

( a${\displaystyle {}_{}}$ ) ,${\displaystyle {}_{}}$(${\displaystyle }$b${\displaystyle {}_{}{n}_{}}$) \ $displaystyle$( $a_{n}$ ) ,${\displaystyle }$( $b_{n}$ ) 등의$$ 시퀀스가 존재한다고 가정합니다.

$\displaystyle a_{n}\leq N_{n}(\mathbf {x},\Theta)\leq b_{n}{\text{및}}a_{n}\leq {frac {1}{M}\sum _{m=1}^{M}N_{n}{\lefx},{Ta}}, {Ta},}$

그럼 거의 확실히

${\displaystyle m_{M,n}(\mathbf {x})-{\tilde {m}_{M,n}(mathbf {x})\leq {b_{n}-a_{n}}{\tilde {m}_{M,n}(mathbf {x})$

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

$나무{\displaystyle }$ $수 M$이 무한대로$$되면$$ 무한 랜덤 포레스트와 무한 KeRF가 됩니다.각 셀의 관측치 수에 경계가 있는 경우 추정치는 가깝습니다.

( $({\displaystyle }$ n${\displaystyle }$)${\displaystyle }$, ( ${\displaystyle a_{}}$)${\displaystyle }$, ( ${\displaystyle b_{}}$) { $displaystyle$( \ $varepsilon$_ { $n$} ) , ($a$ _ n } , ( b$_$ { $n$) } ${\displaystyle {such}_{}}$ ( ( ( ( (가 존재한다고 가정합니다.

• $\displaystyle \operatorname {E} [N_{n}(\mathbf {x},\Theta)]\geq 1,}$
• ${\displaystyle \operatorname {P} [a_{n}\leq N_{n}(\mathbf {x},\Theta)\leq b_{n}\mid {mathcal {D}}_{n}\geq 1-\varepsilon _{n}/2,}$
• $\displaystyle \operatorname {P} [a_{n}\leq \operatorname {E} _{\Theta }[N_{n}(\mathbf {x},\Theta)]\leq b_{n}\mid {mathcal {D}_{n}\geq 1-\varepsilon _{n}/2,}$

그럼 거의 확실히

$(\displaystyle m_{\infty}(\mathbf {x})-{\infty}(\mathbf {x})\leq {b_{n}-a_{n}}{\tilde {m}_{\inftyn}{\tilde {mathbarex}+n})_v}$

일관성 결과

유한 분산 σ 2<과ε{\displaystyle \varepsilon}은 솟구치가우스 잡음, X의 독립적{\displaystyle \mathbf{X}}, Y)m(X)+ε{Y=m(\mathbf{X})+\varepsilon\displaystyle},;∞{\displaystyle \sigma ^{2}<, \infty}. 게다가, X{\displaystyle \mathbf{X}}를 취하다는[${\displaystyle 0}$ , ${\displaystyle 1{}^{}}$]${\displaystyle d^{}}$ $\$ $displaystyle$[ $0$, $1$]^{$d},$m$$$$\ $displaystyle$은 Lipschitz입니다.디스콜셋은^[30] 중심 KeRF와 균일한 KeRF에 대한 일관성 비율의 상한을 입증했다.

중심 KeRF의 일관성

k→ ∞{\displaystyle k\rightarrow \infty}과 n/2k→ ∞{\displaystyle n/2^{k}\rightarrow \infty}을 제공하는 것, 지속적인 C1>0{\displaystyle C_{1}>. 0}일 경우 존재하는 2≤ C1n− 1/(3+d일지가, 모든 n{n\displaystyle}에, E[m부터 ncc(X)− m(X)].⁡ 2)${\displaystyle {}^{}(}$ $n$ )$$2 \ $displaystyle$ \$mathbb${ E$}$ [ { \ $tilde${$m} _$ { $n$} （ \ $mathbf { X$ } ） -$m$ ( \ $mathbf${ $X$} ) ]^{$2}\leq C_{-1/(3+d\log$ 2) （$log$ n ） }$$（ log n$$}

균일한 KeRF의 일관성

k→ ∞{\displaystyle k\rightarrow \infty}과 n/2k→ ∞{\displaystyle n/2^{k}\rightarrow \infty}을 제공하는 것, 지속적인 C>0{\displaystyle C>0}과 E2≤ Cn− 2/(6+3d로그 ⁡ 2)(로그⁡ n)2{\displaystyle \mathbb[m~행복 f(X)− m(X)]존재한다.{E}는 경우${\tilde {m}_{n}{$uf$}(\mathbf {X})-m(\mathbf {X})]{2}\leq$ Cn$^{-2/(6+3d\log$ 2$)}(\log$n)^{$2$

단점들

랜덤 포레스트는 종종 단일 의사결정 트리보다 더 높은 정확도를 달성하지만 의사결정 트리에 존재하는 본질적인 해석 가능성을 희생한다.의사결정 트리는 선형 모델, 규칙 기반 모델 및 주의 기반 모델과 함께 쉽게 해석할 수 있는 매우 작은 기계 학습 모델 패밀리 중 하나입니다.이러한 해석 가능성은 의사결정 트리의 가장 바람직한 특성 중 하나입니다.이를 통해 개발자는 모델이 데이터에서 현실적인 정보를 학습했음을 확인할 수 있으며 최종 사용자가 ^[5][3]모델에 의해 결정된 결정에 대해 신뢰와 신뢰를 가질 수 있습니다.예를 들어, 의사결정 트리가 결정을 내리기 위해 선택한 경로를 따르는 것은 매우 사소한 일이지만, 수십 또는 수백 개의 트리의 경로를 따르는 것은 훨씬 더 어렵습니다.성능과 해석성을 모두 달성하기 위해 일부 모델 압축 기법은 랜덤 포레스트를 동일한 ^[5][36][37]의사결정 함수를 충실하게 재현하는 최소한의 "다시 태어난" 의사결정 트리로 변환할 수 있도록 한다.예측 속성이 목표 변수와 선형적으로 상관되는 것이 확인되면 랜덤 포레스트를 사용하면 기본 ^[5][29]학습자의 정확도가 향상되지 않을 수 있습니다.또한, 다중 범주형 변수의 문제에서 랜덤 포레스트는 ^[38]기본 학습자의 정확도를 높일 수 없을 수 있다.

「 」를 참조해 주세요.

• Boosting – 기계학습 방법
• Decision Tree 학습– 머신 러닝 알고리즘
• 앙상블 학습 – 통계 및 기계 학습 기술
• 그라데이션 부스트 – 기계 학습 기술
• 비모수 통계량
• 랜덤화 알고리즘– 어느 정도의 랜덤성을 논리 또는 절차의 일부로 사용하는 알고리즘

레퍼런스

추가 정보

외부 링크

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