랜덤 포레스트: 두 판 사이의 차이

내용 삭제됨 내용 추가됨

인라인

2015년 4월 29일 (수) 22:49 판

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

도입

정의

랜덤 포레스트는 여러 개의 결정 트리들을 임의적으로 학습하는 방식의 앙상블 방법이다. 랜덤 포레스트 방법은 크게 다수의 결정 트리를 구성하는 학습 단계와 입력 벡터가 들어왔을 때, 분류하거나 예측하는 테스트 단계로 구성되어있다. 랜덤 포레스트는 검출, 분류, 그리고 회귀 등 다양한 어플리케이션으로 활용되고 있다.

역사

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

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

동기

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

기여

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

배경지식

결정 트리

하나의 트리는 계층 구조로 이루어진 노드(node)들과 에지(edge)들의 집합으로 구성된다. 노드들은 내부(internal) 노드와 종단(terminal) 노드로 나뉘어진다. 그래프에서와 달리, 트리에서는 모든 노드가 들어오는 에지(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(c)log(p(c)),

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

랜덤 포레스트

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

배깅

배깅을 이용하여

T

개의 결정트리들로 구성된 랜덤 포레스트를 학습하는 과정.

S_{0}

는 전체 학습 데이터 집합을 의미한다.

S_{0}^{t}

는

t

번째 결정트리를 위해 배깅을 통해 임의로 선택된 학습 데이터들로,

S_{0}

의 부분집합이다.

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

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

임의 노드 최적화

약한 학습기 모델

각 트리의 노드마다 이진 노드 분할 함수(binary split function)을 가지고 있으며, 이 함수에 따라 왼쪽 자식 노드로 보내질 것인지 또는 오른쪽 자식 노드로 보내질 것인지 결정된다. 트리 내 $j$ 번째 노드의 경우, 아래와 같은 이진 노드 분할 함수를 가지며, 이를 약한 학습기 모델(weak learner model)이라고 부른다.

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

0은 거짓(false), 1은 참(true)을 가리킨다. 노드에 도달한 데이터는 분할 함수 결과에 따라 왼쪽 또는 오른쪽의 자식 노드로 보내지게 된다. 이 약한 학습기(weak learner)는 매개변수 ${\boldsymbol {\theta }}=(\phi ,\psi ,\tau )$ 에 따라 결정된다. $\psi$ 는 데이터를 나누는 기하학적 특성을 나타낸다. 즉, 축과 평행한 초평면(axis-aligned hyperplane), 비스듬한 초평면(oblique hyperplane) 또는 일반적인 평면(general surface) 등으로 데이터를 나눌 지를 나타낸다. 매개변수 벡터 $\tau$ 는 이진 테스트(binary test)의 부등식에서 임계값(threshold value)들을 가지고 있다. 필터 함수 $\phi$ 는 벡터 $\mathbf {v}$ 에서 몇 개의 특징(features)들만을 선택한다. 이러한 매개변수들은 각 노드에서 최적화된다.

훈련 목적 함수

노드 분할 함수의 매개변수 ${\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}).

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

앙상블 모델

파일:RF testing ensemble.gif

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

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

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

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

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

위의 식에서 $Z$ 는 확률 표준화(probabilistic normalization)를 해주는 분할 함수(partition function)이다.

중요 매개변수

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

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

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

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

하나의 트리에서 종단노드까지 최대 몇개의 노드(테스트)까지 거칠 것인지를 결정하는 매개변수이다. 최대 허용 깊이가 작으면 언더피팅(under-fitting)이 일어나고, 최대 허용 깊이가 크면 오버피팅(over-fitting)이 일어나기때문에 적절한 값을 설정하는 것이 중요하다.

임의성의 정도와 종류
약한 학습기 모델의 선택
훈련 목적 함수의 정의
실제 적용에서의 특징 벡터의 선택

특성

매개변수의 중요성

랜덤 포레스트에서는 분류 혹은 회귀문제에서 각 매개변수들을 중요성에 따라 순서매길 수 있다. 이 기술은 랜덤 포레스트의 개념을 만든 레오 브레이먼(Leo Breiman)의 논문 ^[3] 에서 기술되어 있고, R의 랜덤 포레스트 패키지 ^[4] 에서 구현되어 있다. 데이터 집합 ${\mathcal {D}}_{n}=\{(\mathbf {v} _{i},Y_{i})\}_{i=1}^{n}$ 에서 매개변수 중요성을 측정하기 위한 첫번째 단계는 데이터 집합에 맞는(fit) 랜덤 포레스트를 구성하는 것이다. 랜덤 포레스트가 구성되는 과정에서 각 데이터 포인트들의 out-of-bag error(임의의 데이터 포인트에 대해서 그 데이터가 Bootstrap에 의해 교체된 트리들에 의한 에러값의 평균)은 기록되고 포레스트 전체의 평균 에러값이 구해진다.

훈련단계 이후 $j$ 번째 매개변수 중요성을 측정하기 위해서, 데이터 집합에서 $j$ 번째 매개변수들의 값을 변경하고, 이 변경된 데이타 집합에 대해 포레스트의 out-of-bag error를 다시 계산한다. $j$ 번째 매개변수의 중요도 점수는 모든 트리들에 대해서 원본 데이터 집합의 out-of-bag error와 값이 변경된 데이터 집합의 out-of-bag error의 차이들의 평균으로 정의된다. 이 점수는 차이들의 표준편차를 이용하여 표준화한다. 큰 중요도 점수를 가지는 매개변수는 작은 값을 갖는 매개변수보다 높은 순위의 매개변수 중요성을 갖게된다.

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

랜덤 포레스트와 k-최근접 이웃 알고리즘과의 관계는 2002년, Lin, Yi와 Jeon, Yongho에 의해 조명되었다.^[5] 이웃 가중치 구조 (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'}$ 와의 가중치로 음이 아닌 값을 갖고, 임의의 $\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'}$ 의 이웃은 트리의 구조와 데이터 집합의 구조에 복합적으로 의존한다. Lin, Yi와 Jeon, Yongho는 랜덤 포레스트에서 이웃들의 분포가 각 매개변수들의 지역적 중요성에 따라 달라지는 것을 보였다.^[5]

응용분야

키넥트에서의 신체 트랙킹

엑스박스 360에서 사용되는 모션 캡쳐 주변기기인 키넥트에서는 랜덤 포레스트를 이용하여 주어진 입력에서 신체의 각 부분을 분류한다.^[6] 훈련 단계에서는 미리 신체부분들이 라벨화(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) 내에서 주어진 복셀에 대해 해당 되는 해부학 구조가 어디인지 검출하고 해당 위치를 파악하는 방법을 제안하였다.^[7] 훈련 단계에서는 해당 복셀이 어떤 해부학 구조인지 그리고 해당 구조의 바운딩 박스(bounding box) 정보를 가지는 55개의 복셀 포인트들을 가지고 6개의 트리를 통해 동시에 학습한다. 테스트 단계에서는 각 트리로부터 얻어진 주어진 복셀이 각 해부학 구조에 포함될 확률들의 평균을 통해 최종 확률을 계산하여 이 확률이 해당 해부학 구조에 속할 가능성(∈[0, 1])이 0.5 이상인지 아닌지를 확인하여 결정한다.

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

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

의사코드

랜덤 결정 트리 학습

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

같이 보기

주석 및 참고자료

↑ Amit, Yali; Geman, Donald (1997). “Shape quantization and recognition with randomized trees”. 《Neural Computation》 9 (7): 1545–1588. doi:10.1162/neco.1997.9.7.1545. CS1 관리 - 여러 이름 (링크)
↑ Ho, Tin Kam (1998). “The Random Subspace Method for Constructing Decision Forests”. 《IEEE Transactions on Pattern Analysis and Machine Intelligence》 20 (8): 1545–1588. doi:10.1109/34.709601.
↑ ^가 ^나 Leo Breiman (2001). “Random Forests”. 《Machine Learning》 45 (1): 5–32. doi:10.1023/A:1010933404324.
↑ Liaw, Andy (2015년 4월 27일). “Documentation for R package randomForest” (PDF). 2015년 4월 27일에 확인함.
↑ ^가 ^나 Lin, Yi; Jeon, Yongho (2002). 《Random forests and adaptive nearest neighbors》 (기술 보고서). Technical Report No. 1055. University of Wisconsin.
↑ Jamie Shotton (January 2013). “Real-time human pose recognition in parts from single depth images”. 《CACM》 56 (1): 116–124. doi:10.1145/2398356.2398381.
↑ Antonio Criminisi (September 2010). “Regression Forests for Efficient Anatomy Detection and Localization in CT Studies”. 《MICCAI workshop》 6533: 106–117. doi:10.1007/978-3-642-18421-5_11.
↑ Darko Zikic (October 2012). “Decision Forests for Tissue-Specific Segmentation of High-Grade Gliomas in Multi-channel MR”. 《MICCAI》 7512: 369–376. doi:10.1007/978-3-642-33454-2_46.

바깥 고리

랜덤 포레스트 분류기 설명 (레오 브레이먼의 사이트)
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#을 이용한 구현
파이썬을 이용한 구현
매트랩을 이용한 구현

[Amit&Geman1997-1] Amit, Yali; Geman, Donald (1997). “Shape quantization and recognition with randomized trees”. 《Neural Computation》 9 (7): 1545–1588. doi:10.1162/neco.1997.9.7.1545. CS1 관리 - 여러 이름 (링크)

[Ho1998-2] Ho, Tin Kam (1998). “The Random Subspace Method for Constructing Decision Forests”. 《IEEE Transactions on Pattern Analysis and Machine Intelligence》 20 (8): 1545–1588. doi:10.1109/34.709601.

[breiman2001-3] 가 ^나 Leo Breiman (2001). “Random Forests”. 《Machine Learning》 45 (1): 5–32. doi:10.1023/A:1010933404324.

[rpackage-4] Liaw, Andy (2015년 4월 27일). “Documentation for R package randomForest” (PDF). 2015년 4월 27일에 확인함.

[linjeon02-5] 가 ^나 Lin, Yi; Jeon, Yongho (2002). 《Random forests and adaptive nearest neighbors》 (기술 보고서). Technical Report No. 1055. University of Wisconsin.

[kinect2013-6] Jamie Shotton (January 2013). “Real-time human pose recognition in parts from single depth images”. 《CACM》 56 (1): 116–124. doi:10.1145/2398356.2398381.

[RegressionInCT-7] Antonio Criminisi (September 2010). “Regression Forests for Efficient Anatomy Detection and Localization in CT Studies”. 《MICCAI workshop》 6533: 106–117. doi:10.1007/978-3-642-18421-5_11.

[ForestInMR-8] Darko Zikic (October 2012). “Decision Forests for Tissue-Specific Segmentation of High-Grade Gliomas in Multi-channel MR”. 《MICCAI》 7512: 369–376. doi:10.1007/978-3-642-33454-2_46.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ 160번째 줄: / 160번째 줄: @@
 ===다채널 자기공명영상 내 고악성도 신경교종 검출===
-마이크로소프트 연구소, 브라운 대학교, 그리고 캠브리지 대학교 연구팀은 다채널 자기공명영상 (Multi-channel Magnetic resonance image)으로 촬영된 뇌 영상에서 고악성도 신경교종 (High-grade gliomas)를 검출하기 위해 랜덤 포레스트를 적용하였다.
+마이크로소프트 연구소, 브라운 대학교, 그리고 캠브리지 대학교 연구팀은 다채널 자기공명영상 (Multi-channel Magnetic resonance image)으로 촬영된 뇌 영상에서 고악성도 신경교종 (High-grade gliomas)를 검출하기 위해 랜덤 포레스트를 적용하였다.<ref name="ForestInMR">{{저널 인용 |저자 = Darko Zikic |날짜 = October 2012 |제목 = Decision Forests for Tissue-Specific Segmentation of High-Grade Gliomas in Multi-channel MR |저널 = MICCAI |권 = 7512 |호 = |쪽 = 369&ndash;376 |doi=10.1007/978-3-642-33454-2_46|url = http://link.springer.com/chapter/10.1007/978-3-642-33454-2_46}}</ref>
 기존의 많은 종양 검출 연구들이 전체적인 종양덩어리를 검출하는데 초점을 맞췄다면 이 연구팀에서는 랜덤 포레스트가 내재적으로 다중 클래스 특성을 지니는 점을 이용하여 서로 다른 종류의 신경 조직을 동시에 검출하는 연구를 진행하였다. 특히 기존의 신경 조직 검출 알고리즘에 비하여 전처리과정 등이 많이 요구되지 않으며, 비교적 간단한 복잡도 모델로 높은 검출 정확도를 보이는 결과를 얻어 랜덤 포레스트의 유용성을 증명하였다.