랜덤 포레스트

정의

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

역사

초기 랜덤 포레스트는 단일 트리를 확장할 때 가능한 결정(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)는 말그대로 결정을 내리기 위해 사용하는 트리로, 결정 과정을 간단한 문제들로 이루어진 계층 구조로 나눈다. 간단한 문제에 대해서는 매개변수(예: 모든 노드의 테스트 매개변수, 종단 노드에서 매개변수 등)를 사용자가 직접 설정할 수 있지만, 보다 복잡한 문제의 경우 학습 데이터로부터 트리 구조와 매개변수를 모두 자동으로 학습한다.

훈련과 테스트 과정

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

테스트 단계

이전에 본 적 없는 데이터 가 입력으로 주어졌을 때, 각 결정 트리는 사전에 정의된 많은 테스트 값을 계층적으로 적용한다. 루트 노드에서 시작해, 각 노드의 분할 함수를 입력 데이터 에 적용한다. 입력 데이터는 이진 테스트의 결과에 따라 오른쪽 또는 왼쪽의 자식 노드로 보내진다. 이 과정은 입력 데이터가 단말 노드에 도달할 때까지 반복된다.

트리에서 단말 노드는 대개 입력 에 대한 출력 값을 내는 예측기(분류기(classifier) 또는 회귀기(regressor))를 갖는다. 포레스트의 경우 각 트리 예측기들의 조합으로 단일 예측치를 만든다.

랜덤 포레스트

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

임의 노드 최적화

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

변수의 중요성

랜덤 포레스트를 이용해 분류 혹은 회귀문제에서 각 변수(variable)들의 중요성에 순위를 매길 수 있다. 다음에 설명할 방법은 랜덤 포레스트의 개념을 만든 레오 브레이먼(Leo Breiman)의 논문에 상세히 설명되어 있으며, R을 이용한 랜덤 포레스트 패키지
에 구현되어 있다.
데이터 집합 에서 변수의 중요성을 측정하기 위한 첫번째 단계는 데이터 집합에 맞추어 랜덤 포레스트를 훈련시키는 것이다.
랜덤 포레스트를 구성하는 과정에서 각 데이터 포인트에 대한 OOB-오차(out-of-bag error)가 구해진다. OOB(out-of-bag) 데이터는 부트스트랩을 통한 임의 중복추출 시 훈련 데이터 집합에 속하지 않는 데이터를 말하며, OOB-오차는 이 데이터의 실제 값과 각 트리로 부터 나온 예측 결과 사이의 오차로 정의된다.(만약 훈련과정에서 배깅을 사용하지 않는다면, OOB 데이터 대신 독립된 테스트 데이터를 이용해 오차를 계산할 수도 있음)

훈련단계 이후 데이터 포인트의 번째 특징의 중요성을 측정하기 위해서, 훈련 데이터 가운데 번째 특징 값을 치환하고, 이 변경된 데이터 집합에 대해 포레스트의 OOB-오차를 다시 계산한다. 번째 변수의 중요도 점수는 모든 트리들에 대해서 원본 데이터 집합의 OOB-오차와 값이 치환된 데이터 집합의 OOB-오차의 차이의 평균으로 정의된다. 이 점수는 차이들의 표준편차에 의해 정규화된다.

큰 중요도 점수를 가지는 변수는 작은 값을 갖는 변수보다 높은 순위의 중요성을 갖게된다.

키넥트에서의 신체 트랙킹

엑스박스 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)를 검출하기 위해 랜덤 포레스트를 적용하였다.
기존의 많은 종양 검출 연구들이 전체적인 종양덩어리를 검출하는데 초점을 맞췄다면 이 연구팀에서는 랜덤 포레스트가 내재적으로 다중 클래스 특성을 지니는 점을 이용하여 서로 다른 종류의 신경 조직을 동시에 검출하는 연구를 진행하였다. 특히 기존의 신경 조직 검출 알고리즘에 비하여 전처리과정 등이 많이 요구되지 않으며, 비교적 간단한 복잡도 모델로 높은 검출 정확도를 보이는 결과를 얻어 랜덤 포레스트의 유용성을 증명하였다.