랜덤 포레스트

기계 학습에서의 랜덤 포레스트(영어: random forest)는 분류, 회귀 분석 등에 사용되는 앙상블 학습 방법의 일종으로, 훈련 과정에서 구성한 다수의 결정 트리로부터 부류(분류) 또는 평균 예측치(회귀 분석)를 출력함으로써 동작한다.

도입

정의

랜덤 포레스트는 다수의 결정 트리들을 학습하는 앙상블 방법이다. 랜덤 포레스트는 검출, 분류, 그리고 회귀 등 다양한 문제에 활용되고 있다.

역사

초기 랜덤 포레스트는 단일 트리를 확장할 때 가능한 결정(available decisions)중 임의의 부분집합(random subset)에서 검색하는 아이디어를 도입한 얄리 아미트(Yali Amit)와 도널드 게먼(Donald Geman)의 연구에 영향을 받았다. 또한 임의의 부분공간(random subspace)을 선택하는 틴 캄 호(Tin Kam Ho)의 아이디어 역시 랜덤 포레스트의 디자인에 영향을 미쳤다. 포레스트가 성장할 때, 각 트리를 학습하기(fitting) 전에 임의로 선택된 부분공간으로 훈련 데이터를 투영(projection) 시키는 과정에서 트리 사이에 차이가 발생한다.

현재의 랜덤 포레스트의 개념은 레오 브레이먼(Leo Breiman)의 논문에서 만들어졌다. 이 논문은 랜덤 노드 최적화(randomized node optimization, RNO)와 배깅(bootstrap aggregating, bagging)을 결합한 방법과 같은 CART(classification and regression tree)를 사용해 상관관계가 없는 트리들로 포레스트를 구성하는 방법을 제시했다.

동기

일반적으로 결정 트리를 이용한 방법의 경우, 그 결과 또는 성능의 변동 폭이 크다는 결점을 가지고 있다. 특히 학습 데이터에 따라 생성되는 결정 트리가 랜덤성에 따라 매우 다르기 때문에 일반화하여 사용하기에 어려움이 따른다. 특히, 결정 트리는 계층적 접근방식이기 때문에 만약 중간에 에러가 발생한다면 다음 단계로 에러가 계속 전파되는 특성을 가진다. 배깅(Bagging) 또는 랜덤 노드 최적화(Randomized node optimization)와 같은 랜덤화 기술은 결정 트리가 가진 이러한 단점을 극복하고 좋은 일반화 성능을 갖도록 한다.

기여

• 월등히 높은 정확성
• 간편하고 빠른 학습 및 테스트 알고리즘
• 변수소거 없이 수천 개의 입력 변수들을 다루는 것이 가능
• 임의화를 통한 좋은 일반화 성능
• 다중 클래스 알고리즘 특성

결정 트리

 이 부분의 본문은 결정 트리 학습법입니다.

하나의 트리 구조

하나의 트리는 계층 구조로 이루어진 노드(node)들과 에지(edge)들의 집합으로 이루어져 있다. 또한 노드는 내부 노드(internal node)와 종단 노드(terminal node, leaf node)로 나뉜다. 그래프에서와 달리, 트리에서는 모든 노드가 들어오는 에지(incoming edge)를 하나만 가진다. 반면 각 내부 노드에서 나가는 에지(outgoing edge)의 개수에는 제한이 없으나, 주로 두 개의 나가는 에지를 갖는 것으로 가정한다.
결정 트리(decision tree)는 말그대로 결정을 내리기 위해 사용하는 트리로, 결정 과정을 간단한 문제들로 이루어진 계층 구조로 나눈다. 간단한 문제에 대해서는 매개변수(예: 모든 노드의 테스트 매개변수, 종단 노드에서 매개변수 등)를 사용자가 직접 설정할 수 있지만, 보다 복잡한 문제의 경우 학습 데이터로부터 트리 구조와 매개변수를 모두 자동으로 학습한다.

수학적 표기법

하나의 일반적인 데이터 포인트를 다음과 같이 벡터 $\mathbf {v}$로 정의한다.

$\mathbf {v} =(x_{1},x_{2},\cdots ,x_{d})\in \mathbb {R} ^{d},$

여기서, $x_{i}$는 스칼라 입력을 나타낸다. 실제 응용에서 입력의 차원 $d$는 매우 큰데, 심지어 무한대가 되기도 한다. 그러나 랜덤 트리 또는 랜덤 포레스트의 계산에서 $\mathbf {v}$내의 $d$개의 모든 원소를 사용하지 않으며, 필요한 기저(basis)에 있는 값들만 취급하는 것이 일반적이다. 종종 입력을 가능한 모든 입력들의 집합으로부터 하나의 함수 $\phi (\mathbf {v} )$에 의해 임의로 추출된 것으로 생각하는 것이 편하다. $\phi (\mathbf {v} )$는 입력의 부분집합을 선택하는 함수로, 다음과 같이 정의한다.

$\phi :\mathbb {R} ^{d}\mathbb {\rightarrow } \mathbb {R} ^{d'},\,{\textrm {with}}\,d'\ll d.$

훈련과 테스트 과정

큰 범주에서 볼 때, 결정 트리의 기능은 오프라인 단계(훈련 또는 학습)와 온라인 단계(테스트) 두 가지로 나눌 수 있다.

훈련 단계

결정 트리 훈련 단계

훈련 단계에서는 종단 노드에 대한 매개변수와 내부 노드와 관련된 노드 분할 함수(split function)의 매개변수를 최적화하는 작업이 진행된다. 트리의 훈련 과정을 이해할 때, 훈련 데이터의 부분집합을 트리의 가지들과 연관시켜 생각하는 것이 편하다. 예를 들어, 노드 1(그림에서와 같이 0부터 너비-우선순위로 각 노드에 숫자가 부여된다)에 도달하는 훈련 데이터의 부분집합을 $S_{1}$이라고 하고, 노드 1의 왼쪽과 오른쪽의 자식 노드를 각각 $S_{1}^{\mathrm {L} },S_{1}^{\mathrm {R} }$라고 하자. 이 때, 각 분할 노드 $j$는 다음과 같은 관계식을 갖는다.

$S_{j}=S_{j}^{\mathrm {L} }\cup S_{j}^{\mathrm {R} },S_{j}^{\mathrm {L} }\cap S_{j}^{\mathrm {R} }=\emptyset ,S_{j}^{\mathrm {L} }=S_{2j+1},S_{j}^{\mathrm {R} }=S_{2j+2}.$

데이터 포인트 $\{\mathbf {v} \}$의 훈련 집합 $S_{0}$ 및 실제 데이터 레이블(ground truth label)이 주어졌을 때, 트리의 매개변수는 정의한 목적 함수를 최소화 하도록 선택된다. 트리의 성장을 언제 멈출지 결정하기 위해 미리 정의된 여러 가지 멈춤 조건이 적용된다. $T$개의 트리로 구성된 하나의 포레스트의 경우, 일반적으로 훈련 과정은 각 트리에 대해 독립적으로 $T$번 반복된다. 랜덤 트리 또는 포레스트에서 주목할 사실은 랜덤성(randomness)이 오직 훈련 과정에만 존재한다는 것이다. 트리가 형성된 후 고정되어 있다면 테스트 단계에서는 완전히 결정론적인 특성을 보인다. 즉, 동일한 입력 데이터에 대해 항상 동일한 결과를 낸다.

테스트 단계

결정 트리 테스트 단계

이전에 본 적 없는 데이터 $\mathbf {v}$가 입력으로 주어졌을 때, 각 결정 트리는 사전에 정의된 많은 테스트 값을 계층적으로 적용한다. 루트 노드에서 시작해, 각 노드의 분할 함수를 입력 데이터 $\mathbf {v}$에 적용한다. 입력 데이터는 이진 테스트의 결과에 따라 오른쪽 또는 왼쪽의 자식 노드로 보내진다. 이 과정은 입력 데이터가 단말 노드에 도달할 때까지 반복된다.
트리에서 단말 노드는 대개 입력 $\mathbf {v}$에 대한 출력 값을 내는 예측기(분류기(classifier) 또는 회귀기(regressor))를 갖는다. 포레스트의 경우 각 트리 예측기들의 조합으로 단일 예측치를 만든다.

정보 획득량과 섀넌 엔트로피

 이 부분의 본문은 쿨백-라이블러_발산입니다.

훈련 단계에서 트리의 각 노드는 들어오는 데이터들을 최적으로 분리하기 위해 정보 획득량(information gain)을 기준으로 사용한다. 다시 말해 각 노드에서 정보 획득량(신뢰, confidence)을 최대화하는 방향으로 데이터를 분리한다. 정보 획득량은 다음과 같이 정의된다.

$I=H(S)-\sum _{i\in \{\mathrm {L} ,\mathrm {R} \}}{\frac {\left|S^{i}\right|}{\left|S\right|}}H(S^{i}),$

여기서, $S$는 한 노드에 도달하는 데이터 집합을, $S^{i}$는 이 노드의 $i\in \{\mathrm {L} ,\mathrm {R} \}$, 왼쪽 혹은 오른쪽 방향 자식 노드로 들어가는 데이터 집합을 나타낸다($S$와 $S^{i}$의 관계식은 훈련과 테스트 과정 참조). 또한, $\left|\,\cdot \,\right|$와 $H(S)$는 각각 데이터 집합에 속한 데이터 개수와 섀넌 엔트로피(Shannon entropy)를 가리킨다.
위 수식에서 볼 수 있듯이, 정보 획득량을 최대화하기 위해서는 결국 섀넌 엔트로피가 최소화되어야 한다. 섀넌 엔트로피는 확률 변수의 조합으로 정보원(여기서는 $S$)에 대한 불확실성을 보여주는 것으로 아래와 같이 정의된다.

$H(S)=-\sum _{c\in {\mathcal {C}}}p\log(p(c)),$

여기서 ${\mathcal {C}}$는 전체 부류(class) 집합을 나타내며, $p(c)$는 각 부류에 대한 확률 질량 함수이다.

랜덤 포레스트

랜덤 포레스트의 가장 큰 특징은 랜덤성(randomness)에 의해 트리들이 서로 조금씩 다른 특성을 갖는다는 점이다. 이 특성은 각 트리들의 예측(prediction)들이 비상관화(decorrelation) 되게하며, 결과적으로 일반화(generalization) 성능을 향상시킨다. 또한, 랜덤화(randomization)는 포레스트가 노이즈가 포함된 데이터에 대해서도 강인하게 만들어 준다. 랜덤화는 각 트리들의 훈련 과정에서 진행되며, 랜덤 학습 데이터 추출 방법을 이용한 앙상블 학습법인 배깅(bagging)과 랜덤 노드 최적화(randomized node optimization)가 자주 사용된다. 이 두 가지 방법은 서로 동시에 사용되어 랜덤화 특성을 더욱 증진 시킬 수 있다.

배깅을 이용한 포레스트 구성

 이 부분의 본문은 배깅입니다.

배깅을 이용하여 $T$개의 결정트리들로 구성된 랜덤 포레스트를 학습하는 과정. $S_{0}$는 전체 학습 데이터 집합을 의미한다. $S_{0}^{t}$는 $t$ 번째 결정트리를 위해 배깅을 통해 임의로 선택된 학습 데이터들로, $S_{0}$의 부분집합이다.

배깅(bagging)은 bootstrap aggregating의 약자로, 부트스트랩(bootstrap)을 통해 조금씩 다른 훈련 데이터에 대해 훈련된 기초 분류기(base learner)들을 결합(aggregating)시키는 방법이다. 부트스트랩이란, 주어진 훈련 데이터에서 중복을 허용하여 원 데이터셋과 같은 크기의 데이터셋을 만드는 과정을 말한다. 배깅을 통해 랜덤 포레스트를 훈련시키는 과정은 다음과 같이 세 단계로 진행된다.

1. 부트스트랩 방법을 통해 $T$개의 훈련 데이터셋을 생성한다.
2. $T$개의 기초 분류기(트리)들을 훈련시킨다.
3. 기초 분류기(트리)들을 하나의 분류기(랜덤 포레스트)로 결합한다(평균 또는 과반수투표 방식 이용).

트리는 작은 과 큰 분산(variance)을 갖기 때문에, 매우 깊이 성장한 트리는 훈련 데이터에 대해 과적합(overfitting)하게 된다. 부트스트랩 과정은 트리들의 편향은 그대로 유지하면서, 분산은 감소시키기 때문에 포레스트의 성능을 향상시킨다. 즉, 한 개의 결정 트리의 경우 훈련 데이터에 있는 노이즈에 대해서 매우 민감하지만, 트리들이 서로 상관화(correlated)되어 있지 않다면 여러 트리들의 평균은 노이즈에 대해 강인해진다. 포레스트를 구성하는 모든 트리들을 동일한 데이터셋으로만 훈련시키게 되면, 트리들의 상관성(correlation)은 굉장히 커질 것이다. 따라서 배깅은 서로 다른 데이터셋들에 대해 훈련 시킴으로써, 트리들을 비상관화시켜 주는 과정이다.

임의 노드 최적화

임의 노드 최적화 방식을 통해 학습하는 과정. 각각의 트리 내 존재하는 노드마다 분할 함수 $h(.)$을 이용하여 각 노드에서의 정보 획득량이 최대가 되도록 최적화하여 학습하는 방법

훈련 단계에서 임의 노드 최적화는 훈련 목적 함수를 최대로 만드는 노드 분할 함수의 매개변수 ${\boldsymbol {\theta }}$의 최적값을 구하게 된다.

노드 분할 함수

각 트리의 노드마다 분할 함수(split function)를 가지고 있으며, 다음과 같이 표현할 수 있다.

$h(\mathbf {v} ,{\boldsymbol {\theta }}_{j})\in \left\{0,1\right\},$

0은 거짓(false), 1은 참(true)을 가리킨다. 노드에 도달한 데이터는 분할 함수 결과에 따라 왼쪽 또는 오른쪽의 자식 노드로 보내지게 된다. 이러한 분할 함수는 매개변수 ${\boldsymbol {\theta }}=(\phi ,\psi ,\tau )$에 따라 결정된다.

• $\phi$는 필터 함수로 벡터 $\mathbf {v}$에서 몇 개의 특징(feature)들만을 선택한다. 이 과정은 특징 배깅(feature bagging)이라고도 불린다. 특징을 선택하는 이유는 배깅을 통해 얻은 트리들 간의 상관성에 있다. 즉, 한 개의 특징 또는 극소수의 특징들이 결과에 대해 강한 예측 성능을 지닌다면, 훈련 과정 중 여러 트리 노드에서 이러한 특징들이 중복되어 선택되고 결과적으로 트리들이 상관화되기 때문이다.
• $\psi$는 분할 함수의 기하학적 특성을 나타낸다. 즉, 어떤 기하학적 특성을 이용해 데이터를 분리할 지를 나타내는 것으로 평행한 초평면(axis-aligned hyperplane), 비스듬한 초평면(oblique hyperplane) 또는 일반적인 평면(general surface) 등이 사용될 수 있다.
• $\tau$는 매개변수 벡터로 이진 테스트(binary test)의 부등식에서 임계값(threshold value)들을 가지고 있다.

따라서 노드 분할 함수는 다음과 같이 표현될 수 있다.

• 노드 분할 함수가 선형적일 때

$h(\mathbf {v} ,{\boldsymbol {\theta }}_{j})=[\tau _{1}>\phi (\mathbf {v} )\cdot \psi >\tau _{2}]$

• 노드 분할 함수가 비선형일 때

$h(\mathbf {v} ,{\boldsymbol {\theta }}_{j})=[\tau _{1}>\phi (\mathbf {v} )^{\top }\psi \,\phi (\mathbf {v} )>\tau _{2}]$

훈련 목적 함수

노드 분할 함수의 매개변수 ${\boldsymbol {\theta }}$의 가능한 모든 경우를 포함하는 집합을 ${\mathcal {T}}$라고 한다면, $j$번째 노드의 훈련 단계에서 ${\mathcal {T}}_{j}\subset {\mathcal {T}}$ 인 부분집합 ${\mathcal {T}}_{j}$를 만든다. 매개변수의 최적값 ${\boldsymbol {\theta }}_{j}^{*}$는 ${\mathcal {T}}_{j}$안에서, 정보 획득량(information gain)으로 정의되는 목적 함수(objective function)를 최대로 만들게 하는 값으로 계산된다.

${\boldsymbol {\theta }}_{j}^{*}=\arg {\underset {{\boldsymbol {\theta }}_{j}\in {\mathcal {T}}_{j}}{\max }}I_{j},$

$I_{j}=I(S_{j},S_{j}^{\mathrm {L} },S_{j}^{\mathrm {R} },{\boldsymbol {\theta }}_{j})=H(S_{j})-\sum _{i\in \left\{\mathrm {L} ,\mathrm {R} \right\}}{\frac {\left|S_{j}^{i}\right|}{\left|S_{j}\right|}}H(S_{j}^{i}).$ ($I,S,H$에 대한 설명은 결정 트리 참조)

임의성의 정도(the amount of randomness)는 $\left|{\mathcal {T}}_{j}\right|/\left|{\mathcal {T}}\right|$로 결정된다. $\left|{\mathcal {T}}\right|=\infty$ 로 고정시켜 두고 랜덤 포레스트를 훈련시키는 경우, 매개변수 $\rho =\left|{\mathcal {T}}_{j}\right|$를 도입하여 임의성 정도를 설명할 수 있다. 이 같은 경우, $\rho =1,...,\infty$가 임의성의 정도를 결정하는 것으로 볼 수 있다. 보통 $\rho$의 값은 랜덤 포레스트의 트리들의 모든 노드에서 동일한 값을 사용한다. 만약 $\rho =\left|{\mathcal {T}}\right|$ 이면, 랜덤 포레스트의 모든 트리들은 서로 동일하게 되며, 전체 시스템에 임의성이 주입되지 않는다. $\rho =1$ 인 경우에는 최대의 임의성과 비상관화(uncorrelated)된 트리들을 얻게 된다.

앙상블 모델

앙상블 모델을 이용한 랜덤 포레스트 테스트 과정. 각 결정트리로부터 얻어진 결과를 평균, 곱하기, 또는 과반수 투표 방식을 통해 최종 결과를 도출해낸다.

포레스트의 모든 트리들은 독립적으로 훈련 단계를 거친다. 테스트 단계에서 데이터 포인트 $\mathbf {v}$는 모든 트리에 동시로 입력되어 종단 노드에 도달하게 된다. 이러한 테스트 단계는 병렬적으로 진행될 수 있으며, 따라서 병렬 CPU 또는 GPU 하드웨어를 통해 높은 계산 효율성을 얻을 수 있다. 포레스트의 예측 결과는 모든 트리의 예측 결과들의 평균으로 얻는다. 분류의 경우를 보면 다음의 식과 같다.

$p(c|\mathbf {v} )={\frac {1}{T}}\sum _{t=1}^{T}p_{t}(c|\mathbf {v} )$

다른 방법으로는 트리들의 결과들을 곱하는 방법이 있다.

$p(c|\mathbf {v} )={\frac {1}{Z}}\prod _{t=1}^{T}p_{t}(c|\mathbf {v} ),$

여기서 $Z$는 확률 정규화(probabilistic normalization)를 위한 상수(constant)이다.

중요 매개변수

랜덤 포레스트의 가장 큰 영향을 미치는 매개변수들은 다음과 같다.

• 포레스트의 크기 (트리의 개수) ${\mathit {T}}$

총 포레스트를 몇 개의 트리로 구성할 지를 결정하는 매개변수이다. 포레스트가 작으면 트리들을 구성하고 테스트 하는데 걸리는 시간이 짧은 대신, 일반화 능력이 떨어져 임의의 입력 데이터 포인트에 대해 틀린 결과를 내놓을 확률이 높다. 반면에 포레스트의 크기가 크다면 훈련과 테스트 시간은 증가하지만, 포레스트의 결과값은 각 트리의 결과들에 평균을 취한 것으로 큰 포레스트의 결과값은 작은 포레스트보다 비교적 연속적이며 일반화 능력이 우수하다.

• 최대 허용 깊이 ${\mathit {D}}$

하나의 트리에서 루트 노드부터 종단 노드까지 최대 몇개의 노드(테스트)를 거칠 것인지를 결정하는 매개변수이다. 최대 허용 깊이가 작으면 과소적합(underfitting)이 일어나고, 최대 허용 깊이가 크면 과대적합(overfitting)이 일어나기 때문에 적절한 값을 설정하는 것이 중요하다.

• 임의성의 정도와 종류
• 노드 분할 함수의 선택
• 훈련 목적 함수의 정의
• 실제 적용에서의 특징 벡터의 선택

특성

변수의 중요성

랜덤 포레스트를 이용해 분류 혹은 회귀문제에서 각 변수(variable)들의 중요성에 순위를 매길 수 있다. 다음에 설명할 방법은 랜덤 포레스트의 개념을 만든 레오 브레이먼(Leo Breiman)의 논문에 상세히 설명되어 있으며, R을 이용한 랜덤 포레스트 패키지 에 구현되어 있다. 데이터 집합 ${\mathcal {D}}_{n}=\{(\mathbf {v} _{i},Y_{i})\}_{i=1}^{n}$에서 변수의 중요성을 측정하기 위한 첫번째 단계는 데이터 집합에 맞추어 랜덤 포레스트를 훈련시키는 것이다. 랜덤 포레스트를 구성하는 과정에서 각 데이터 포인트에 대한 OOB-오차(out-of-bag error)가 구해진다. OOB(out-of-bag) 데이터는 부트스트랩을 통한 임의 중복추출 시 훈련 데이터 집합에 속하지 않는 데이터를 말하며, OOB-오차는 이 데이터의 실제 값과 각 트리로부터 나온 예측 결과 사이의 오차로 정의된다.(만약 훈련과정에서 배깅을 사용하지 않는다면, OOB 데이터 대신 독립된 테스트 데이터를 이용해 오차를 계산할 수도 있음)
훈련단계 이후 데이터 포인트의 $j$번째 특징의 중요성을 측정하기 위해서, 훈련 데이터 가운데 $j$번째 특징 값을 치환하고, 이 변경된 데이터 집합에 대해 포레스트의 OOB-오차를 다시 계산한다. $j$번째 변수의 중요도 점수는 모든 트리들에 대해서 원본 데이터 집합의 OOB-오차와 값이 치환된 데이터 집합의 OOB-오차의 차이의 평균으로 정의된다. 이 점수는 차이들의 표준편차에 의해 정규화된다.
큰 중요도 점수를 가지는 변수는 작은 값을 갖는 변수보다 높은 순위의 중요성을 갖게된다.

k-최근접 이웃 알고리즘과의 관계

랜덤 포레스트와 k-최근접 이웃 알고리즘과의 관계는 2002년, 이 린(Yi Lin)과 전용호(Jeon, Yongho)에 의해 조명되었다. 이웃 가중치 구조(weighted neighborhoods schemes) 모델을 통해 두가지 알고리즘을 통합할 수 있다. 이 모델은 데이터 집합 ${\mathcal {D}}_{n}=\{(\mathbf {v} _{i},Y_{i})\}_{i=1}^{n}$에서 새로운 데이터 포인트 $\mathbf {v'}$의 예측값 ${\hat {Y}}$을 이웃한 데이터 포인트들과 가중치 함수 $W$를 통해 구한다.

${\hat {Y}}=\sum _{i=1}^{n}W(\mathbf {v} _{i},\mathbf {v'} )Y_{i}\,,$

여기서 $W(\mathbf {v} _{i},\mathbf {v'} )$는 $i$번째 데이터 포인트 $\mathbf {v} _{i}$와 새로운 데이터 포인트 $\mathbf {v'}$와의 가중치로 음이 아닌 값을 갖고, 임의의 $\mathbf {v'}$에 대해 모든 가중치들의 합은 1이 된다. 각 모델에서 가중치 함수는 다음과 같다.

• k-최근접 이웃 알고리즘에서, $\mathbf {v'}$와 가장 가까운 k개의 데이터 포인트 $\mathbf {v} _{i}$에 대해 $W(\mathbf {v} _{i},\mathbf {v'} )={1 \over k}$, 그 외의 데이터 포인트에 대해 $W(\mathbf {v} _{i},\mathbf {v'} )=0$
• 결정 트리에서, $W(\mathbf {v} _{i},\mathbf {v'} )$는 새로운 데이터 포인트 $\mathbf {v'}$가 $\mathbf {v} _{i}$와 같은 단말 노드로 떨어질 확률을 의미한다.
• 랜덤 포레스트에서는, 독립적인 가중치 함수 $W_{j}$를 갖는 m개의 트리 집합들의 예측값을 평균내어 사용하기에, 포레스트의 전체의 예측값은 다음과 같이 나타낼 수 있다.

${\hat {Y}}={\frac {1}{m}}\sum _{j=1}^{m}\sum _{i=1}^{n}W_{j}(\mathbf {v} _{i},\mathbf {v'} )\,Y_{i}=\sum _{i=1}^{n}\left({\frac {1}{m}}\sum _{j=1}^{m}W_{j}(\mathbf {v} _{i},\mathbf {v'} )\right)\,Y_{i},$

이 식은 포레스트 전체가 개별 트리의 가중치들의 평균값으로 다시 이웃 가중치 구조(weighted neighborhoods schemes)를 이루는 것을 보여준다. 여기서 $\mathbf {v'}$의 이웃 $\mathbf {v} _{i}$는 포레스트 중 적어도 하나의 트리에서 $\mathbf {v'}$와 같은 종단 노드로 떨어지는 데이터 포인트를 의미하게 된다. 이렇게 하여 $\mathbf {v'}$의 이웃은 트리의 구조와 데이터 집합의 구조에 복합적으로 의존한다. 랜덤 포레스트에서 이웃들의 분포가 각 매개변수들의 지역적 중요성에 따라 달라진다.

응용사례

키넥트에서의 신체 트랙킹

엑스박스 360에서 사용되는 모션 캡처 주변기기인 키넥트에서는 랜덤 포레스트를 이용하여 주어진 입력에서 신체의 각 부분을 분류한다. 훈련 단계에서는 미리 신체부분들이 라벨화(pre-labeled) 되어있는 깊이 지도(depth map)에서 2,000개의 픽셀(pixel)을 임의로 추출해 300,000장의 깊이 지도당 트리 하나씩 총 세개의 깊이(depth) 값이 20인 트리를 구성한다. 트리 구성 시 1,000개의 코어 클러스터(core cluster)를 사용한 GPU연산으로 하루정도의 시간이 걸린다. 테스트 단계에서는 앞서 구성한 트리들을 이용하여 임의의 입력 깊이 사진의 배경을 제외한 모든 픽셀들을 분류하는데 엑스박스 GPU에서 5밀리초(200프레임/초)의 시간 성능을 보인다.

컴퓨터 단층 촬영 영상 내 해부학 구조 검출 및 위치파악

안토니오 크리미니시(Antonio Criminisi) 등은 랜덤 포레스트를 이용하여 3차원 컴퓨터 단층 촬영 영상(Computed Tomography, CT) 내에서 주어진 복셀에 대해 해당 되는 해부학 구조가 어디인지 검출하고 해당 위치를 파악하는 방법을 제안하였다. 훈련 단계에서는 해당 복셀이 어떤 해부학 구조인지 그리고 해당 구조의 바운딩 박스(bounding box) 정보를 가지는 55개의 복셀 포인트들을 가지고 6개의 트리를 통해 동시에 학습한다. 테스트 단계에서는 각 트리로부터 얻어진 주어진 복셀이 각 해부학 구조에 포함될 확률들의 평균을 통해 최종 확률을 계산하여 이 확률이 해당 해부학 구조에 속할 가능성(∈[0, 1])이 0.5 이상인지 아닌지를 확인하여 결정한다.

다채널 자기공명영상 내 고악성도 신경교종 검출

마이크로소프트 연구소, 브라운 대학교, 그리고 캠브리지 대학교 연구팀은 다채널 자기공명영상(Multi-channel Magnetic resonance image)으로 촬영된 뇌 영상에서 고악성도 신경교종(High-grade gliomas)를 검출하기 위해 랜덤 포레스트를 적용하였다. 기존의 많은 종양 검출 연구들이 전체적인 종양덩어리를 검출하는데 초점을 맞췄다면 이 연구팀에서는 랜덤 포레스트가 내재적으로 다중 클래스 특성을 지니는 점을 이용하여 서로 다른 종류의 신경 조직을 동시에 검출하는 연구를 진행하였다. 특히 기존의 신경 조직 검출 알고리즘에 비하여 전처리과정 등이 많이 요구되지 않으며, 비교적 간단한 복잡도 모델로 높은 검출 정확도를 보이는 결과를 얻어 랜덤 포레스트의 유용성을 증명하였다.

의사코드

랜덤 결정 트리 학습 TreeNode LearnDT(S) repeat featureTests times let f = RndFeature(); let r = EvaluateFeatureResponses(S, f); repeat threshTests times let t = RndThreshold(r); let (S_l, S_r) = Split(S, r, t); let gain = InfoGain(S_l, S_r); if gain is best then remember f, t, S_l, S_r; end end end if best gain is insufficient or treeDepth is greater than D return LeafNode(HistogramExamples(S)); else treeDepth = treeDepth + 1; return SplitNode(f, t, LearnDT(S_l), LearnDT(S_r)); end end

랜덤 결정 트리 테스트 double[] ClassifyDT(node, v) if node.IsSplitNode then if node.f(v) >= node.t then return ClassifyDT(node.right, v) else return ClassifyDT(node.left, v) end else return node.P end end

랜덤 포레스트 학습 Forest LearnDF(countTrees, S) // allocate memory let forest = Forest(countTrees) // loop over trees in forest for t = 1 to countTrees let S_t = RandomSplit(S) forest[t] = LearnDT(S_t) end // return forest object return forest end

랜덤 포레스트 테스트 double[] ClassifyDF(forest, v) // allocate memory let P = double[forest.CountClasses] // loop over trees in forest for t = 1 to forest.CountTrees let P’ = ClassifyDT(forest.Tree[t], v) P = P + P’ // sum distributions end // normalise P = P / forest.CountTrees end

같이 보기

• 결정 트리 학습법
• k-최근접 이웃 알고리즘
• 나이브 베이즈 분류
• 비모수 통계
• 기계 학습

외부 링크

• 랜덤 포레스트 분류기 설명 (레오 브레이먼의 사이트)
• Liaw, Andy & Wiener, Matthew "Classification and Regression by randomForest" R News (2002) Vol. 2/3 p. 18 (R을 위한 랜덤 포레스트 패키지 사용에 대한 토론)
• Ho, Tin Kam (2002). "A Data Complexity Analysis of Comparative Advantages of Decision Forest Constructors". Pattern Analysis and Applications 5, p. 102-112 (배깅과 랜덤 부분집합 방법 비교)
• C#을 이용한 구현
• 파이썬을 이용한 구현
• 매트랩을 이용한 구현