랜덤 포레스트
기계 학습에서의 랜덤 포레스트()는 분류, 회귀 분석 등에 사용되는 앙상블 학습 방법의 일종으로, 훈련 과정에서 구성한 다수의 결정 트리로부터 부류(분류) 또는 평균 예측치(회귀 분석)를 출력함으로써 동작한다.
랜덤 포레스트는 여러 개의 결정 트리들을 임의적으로 학습하는 방식의 앙상블 방법이다. 랜덤 포레스트 방법은 크게 다수의 결정 트리를 구성하는 학습 단계와 입력 벡터가 들어왔을 때, 분류하거나 예측하는 테스트 단계로 구성되어있다. 랜덤 포레스트는 검출, 분류, 그리고 회귀 등 다양한 애플리케이션으로 활용되고 있다.
랜덤 포레스트의 초기 발전은 단일 트리를 확장하는 맥락에서 이용 가능한 결정(available decisions)에 대한 임의의 부분집합(random subset)에 대해 검색하는 아이디어를 도입한 얄리 아미트()와 도널드 게먼()의 연구에 영향을 받았다. 또한 임의의 부분공간(random subspace)을 선택하는 틴 캄 호()의 아이디어 역시 랜덤 포레스트의 디자인에 영향을 미쳤다. 포레스트가 성장할 때, 각 트리를 맞추기() 전에 임의로 선택한 부분공간으로 훈련 데이터를 투영() 시키는 과정에서 트리 사이에 변형이 일어난다.
현재의 랜덤 포레스트의 개념은 레오 브레이먼()의 논문에서 만들어졌다. 이 논문에서는 임의 노드 최적화(randomized node optimization, RNO)와 배깅(bootstrap aggregating, bagging)을 결합한 방법과 같은 CART(classification and regression tree)를 사용해 상관관계가 없는 트리들로 포레스트를 구성하는 방법을 제시하였다.
일반적으로 결정 트리를 이용한 방법의 경우, 그 결과 또는 성능의 변동 폭이 크다는 결점을 가지고 있다. 특히 학습 데이터에 따라 생성되는 결정 트리가 매우 달라지기 때문에 일반화하여 사용하기에 매우 어려움이 따른다. 특히, 결정 트리는 계층적 접근방식이기 때문에 만약 중간에 에러가 발생한다면 다음 단계로 에러가 계속 전파되는 특성을 가진다. 배깅(Bagging) 또는 임의 노드 최적화(Randomized node optimization)와 같은 임의화 기술은 결정 트리가 가진 이러한 단점을 극복하고 좋은 일반화 성능을 갖도록 한다.하나의 트리는 계층 구조로 이루어진 노드()들과 에지()들의 집합으로 구성된다. 노드들은 내부 노드()와 종단 노드()로 나뉜다. 그래프에서와 달리, 트리에서는 모든 노드가 들어오는 에지(incoming edge)를 오직 하나만 가지도록 제한된다. 각 내부 노드에서 나가는 에지(outgoing edge)의 개수는 제한이 없으나, 주로 두 개의 나가는 에지를 갖는 것으로 가정한다.
결정 트리()는 말그대로 결정을 내리기 위해 사용하는 트리로, 복잡한 문제를 간단한 문제들로 이루어진 계층 구조형태로 나누기 위한 기술이다. 간단한 문제에 대해서는 매개변수(예: 모든 노드의 테스트 매개변수, 종단 노드에서 매개변수 등)를 사용자가 직접 설정할 수 있지만, 보다 복잡한 문제의 경우 학습 데이터로부터 트리 구조와 매개변수를 자동으로 학습한다.
하나의 일반적인 데이터 포인트를 다음과 같이 벡터 formula_1로 정의한다.
여기서, formula_3는 스칼라 특징을 나타낸다. 실제 응용에서 특징의 차원 formula_4는 매우 큰 값을 갖는데, 심지어 무한대가 되기도 한다. 그러나 랜덤 트리 또는 랜덤 포레스트에서 formula_1내의 formula_4개의 모든 특징 원소들에 대해 미리 계산할 필요가 없으며, 필요한 기저()에 있는 특징들만 취급하는 것이 일반적이다.
종종 특징을 가능한 모든 특징들의 집합으로부터 하나의 함수 formula_7에 의해 임의로 추출된 것으로 생각하는 것이 편하다. formula_7는 관심 특징들의 부분집합을 선택하는 함수로, 다음과 같이 정의한다.
큰 범주에서 볼 때, 결정 트리의 기능은 오프라인 단계(훈련 또는 학습)와 온라인 단계(테스트) 두 가지로 나눌 수 있다.
훈련 단계에서는 종단 노드에 대한 매개변수와 내부 노드와 관련된 노드 분할 함수(split function)의 매개변수를 최적화하는 작업이 진행된다.
트리의 훈련 과정을 설명할 때, 훈련 데이터의 부분집합을 트리의 가지들과 연관시켜 생각하는 것이 편하다. 예를 들어, 노드 1(그림에서와 같이 0부터 너비-우선순위로 각 노드에 숫자가 부여된다)에 도달하는 훈련 데이터의 부분집합을 formula_10이라고 하고, 노드 1의 왼쪽과 오른쪽의 자식 노드를 각각 formula_11라고 하자. 이 때, 각 분할 노드 formula_12는 다음과 같은 특성 관계식을 갖는다.
데이터 포인트 formula_14의 훈련 집합 formula_15 및 실제 데이터 레이블(ground truth label)이 주어졌을 때, 트리의 매개변수는 정의한 목적 함수를 최소화 하도록 선택된다. 트리의 성장을 언제 멈출지 결정하기 위해 미리 정의된 여러가지 멈춤 조건이 적용된다.
formula_16개의 트리로 구성된 하나의 포레스트의 경우, 일반적으로 훈련 과정은 각 트리에 대해 독립적으로 formula_16번 반복된다. 랜덤 트리 또는 포레스트에서 주목할 사실은 임의성()이 오직 훈련 과정에서만 들어간다는 것이다. 트리가 형성되고 고정되어 있다면 테스트 단계에서는 완전히 결정적인 특성을 보인다. 즉, 동일한 입력 데이터 포인트에 대해 항상 동일한 결과를 보인다.
이전에 본 적 없는 데이터 포인트 formula_1가 입력으로 주어졌을 때, 각 결정 트리는 사전에 정의된 많은 테스트 값을 계층적으로 적용한다. 루트 노드에서 시작해, 각 노드의 분할 함수를 입력 데이터 formula_1에 적용한다. 입력 데이터는 이진 테스트의 결과에 따라 오른쪽 또는 왼쪽의 자식 노드로 보내진다. 이 과정은 입력 데이터 포인트가 단말 노드에 도달할 때까지 반복된다.
트리에서 단말 노드는 대개 입력 formula_1에 대한 출력 값을 내는 예측기(분류기() 또는 회귀기())를 갖는다. 포레스트의 경우 각 트리 예측기들의 조합으로 단일 예측치를 만든다.
훈련 단계에서 트리의 각 노드는 들어오는 데이터 포인트들을 최적으로 분리하기 위해 정보 획득량()을 측정 기준으로 사용한다. 구체적으로 각 노드에서 정보 획득량(신뢰, confidence)을 최대화하는 것이다. 정보 획득량은 다음과 같이 정의된다.
여기서, formula_22는 한 노드에 도달하는 데이터 집합을, formula_23는 이 노드의 formula_24, 왼쪽 혹은 오른쪽 방향 자식 노드로 들어가는 데이터 집합을 나타낸다(formula_22와 formula_23의 관계식은 훈련과 테스트 과정 참조). 또한, formula_27와 formula_28는 각각 데이터 집합에 속한 데이터 개수와 섀넌 엔트로피()를 가리킨다.
위 수식에서 볼 수 있듯이, 정보 획득량을 최대화하기 위해서는 결국 섀넌 엔트로피가 최소화 되어야 한다. 섀넌 엔트로피는 확률 변수의 조합으로 정보원(여기서는 formula_22)에 대한 불확실성을 보여주는 것으로 아래와 같이 정의된다.
여기서 formula_31는 전체 부류() 집합을 나타내며, formula_32는 각 부류에 대한 확률 질량 함수이다.
랜덤 포레스트의 가장 핵심적인 특징은 임의성()에 의해 서로 조금씩 다른 특성을 갖는 트리들로 구성된다는 점이다. 이 특징은 각 트리들의 예측()들이 비상관화() 되게하며, 결과적으로 일반화() 성능을 향상시킨다. 또한, 임의화()는 포레스트가 노이즈가 포함된 데이터에 대해서도 강인하게 만들어 준다.
임의화는 각 트리들의 훈련 과정에서 진행되며, 가장 널리 쓰이는 두 가지 방법으로는 임의 학습 데이터 추출 방법을 이용한 앙상블 학습법인 배깅()과 임의 노드 최적화()가 있다. 이 두 가지 방법은 서로 동시에 사용되어 임의화 특성을 더욱 증진 시킬 수 있다.
배깅(bagging)은 bootstrap aggregating의 약자로, 부트스트랩()을 통해 조금씩 다른 훈련 데이터에 대해 훈련된 기초 분류기()들을 결합()시키는 방법이다. 부트스트랩이란, 주어진 훈련 데이터에서 중복을 허용하여 원 데이터와 같은 크기의 데이터를 만드는 과정을 말한다. 배깅을 통해 랜덤 포레스트를 훈련시키는 과정은 다음과 같이 크게 세 단계로 구성되어있다.
트리는 작은 편향()과 큰 분산()을 갖기 때문에, 매우 깊이 성장한 트리는 훈련 데이터에 대해 과대적합(overfitting)하게 된다. 부트스트랩 과정은 트리들의 편향은 그대로 유지하면서, 분산은 감소시키기 때문에 포레스트의 성능을 향상시킨다. 즉, 한 개의 결정 트리의 경우 훈련 데이터에 있는 노이즈에 대해서 매우 민감하지만, 트리들이 서로 상관화()되어 있지 않다면 여러 트리들의 평균은 노이즈에 대해 강인해진다. 포레스트를 구성하는 모든 트리들을 동일한 데이터 집합으로만 훈련시키게 되면, 트리들의 상관성()은 굉장히 커질 것이다. 따라서 배깅은 서로 다른 데이터 집합들에 대해 훈련 시킴으로써, 트리들을 비상관화시켜 주는 과정이다.
훈련 단계에서 임의 노드 최적화는 훈련 목적 함수를 최대로 만드는 노드 분할 함수의 매개변수 formula_35의 최적값을 구하게 된다.
각 트리의 노드마다 분할 함수()를 가지고 있으며, 다음과 같이 표현할 수 있다.
0은 거짓(), 1은 참()을 가리킨다. 노드에 도달한 데이터는 분할 함수 결과에 따라 왼쪽 또는 오른쪽의 자식 노드로 보내지게 된다. 이러한 분할 함수는 매개변수 formula_37에 따라 결정된다.
따라서 노드 분할 함수는 다음과 같이 표현될 수 있다.
노드 분할 함수의 매개변수 formula_35의 가능한 모든 경우를 포함하는 집합을 formula_45라고 한다면, formula_12번째 노드의 훈련 단계에서 formula_47 인 부분집합 formula_48를 만든다. 매개변수의 최적값 formula_49는 formula_48안에서, 정보 획득량()으로 정의되는 목적 함수()를 최대로 만들게 하는 값으로 계산된다.
임의성의 정도()는 formula_54로 결정된다. formula_55 로 고정시켜 두고 랜덤 포레스트를 훈련시키는 경우, 매개변수 formula_56를 도입하여 임의성 정도를 설명할 수 있다. 이 같은 경우, formula_57가 임의성의 정도를 결정하는 것으로 볼 수 있다. 보통 formula_58의 값은 랜덤 포레스트의 트리들의 모든 노드에서 동일한 값을 사용한다. 만약 formula_59 이면, 랜덤 포레스트의 모든 트리들은 서로 동일하게 되며, 전체 시스템에 임의성이 주입되지 않는다. formula_60 인 경우에는 최대의 임의성과 비상관화(uncorrelated)된 트리들을 얻게 된다.
포레스트의 모든 트리들은 독립적으로 훈련 단계를 거친다. 테스트 단계에서 데이터 포인트 formula_1는 모든 트리에 동시로 입력되어 종단 노드에 도달하게 된다. 이러한 테스트 단계는 병렬적으로 진행될 수 있으며, 따라서 병렬 CPU 또는 GPU 하드웨어를 통해 높은 계산 효율성을 얻을 수 있다. 포레스트의 예측 결과는 모든 트리의 예측 결과들의 평균으로 얻는다. 분류의 경우를 보면 다음의 식과 같다.
다른 방법으로는 트리들의 결과들을 곱하는 방법이 있다.
여기서 formula_64는 확률 정규화()를 위한 상수()이다.
랜덤 포레스트의 가장 큰 영향을 미치는 매개변수들은 다음과 같다.
랜덤 포레스트를 이용해 분류 혹은 회귀문제에서 각 변수()들의 중요성에 순위를 매길 수 있다. 다음에 설명할 방법은 랜덤 포레스트의 개념을 만든 레오 브레이먼(Leo Breiman)의 논문에 상세히 설명되어 있으며, R을 이용한 랜덤 포레스트 패키지
에 구현되어 있다.
데이터 집합 formula_67에서 변수의 중요성을 측정하기 위한 첫번째 단계는 데이터 집합에 맞추어 랜덤 포레스트를 훈련시키는 것이다.
랜덤 포레스트를 구성하는 과정에서 각 데이터 포인트에 대한 OOB-오차()가 구해진다. OOB() 데이터는 부트스트랩을 통한 임의 중복추출 시 훈련 데이터 집합에 속하지 않는 데이터를 말하며, OOB-오차는 이 데이터의 실제 값과 각 트리로 부터 나온 예측 결과 사이의 오차로 정의된다.(만약 훈련과정에서 배깅을 사용하지 않는다면, OOB 데이터 대신 독립된 테스트 데이터를 이용해 오차를 계산할 수도 있음)
훈련단계 이후 데이터 포인트의 formula_12번째 특징의 중요성을 측정하기 위해서, 훈련 데이터 가운데 formula_12번째 특징 값을 치환하고, 이 변경된 데이터 집합에 대해 포레스트의 OOB-오차를 다시 계산한다. formula_12번째 변수의 중요도 점수는 모든 트리들에 대해서 원본 데이터 집합의 OOB-오차와 값이 치환된 데이터 집합의 OOB-오차의 차이의 평균으로 정의된다. 이 점수는 차이들의 표준편차에 의해 정규화된다.
큰 중요도 점수를 가지는 변수는 작은 값을 갖는 변수보다 높은 순위의 중요성을 갖게된다.
랜덤 포레스트와 "k"-최근접 이웃 알고리즘과의 관계는 2002년, 이 린(Yi Lin)과 전용호(Jeon, Yongho)에 의해 조명되었다. 이웃 가중치 구조(weighted neighborhoods schemes) 모델을 통해 두가지 알고리즘을 통합할 수 있다.
이 모델은 데이터 집합 formula_67에서 새로운 데이터 포인트 formula_72의 예측값 formula_73을 이웃한 데이터 포인트들과 가중치 함수 formula_74를 통해 구한다.
여기서 formula_76는 formula_77번째 데이터 포인트 formula_78와 새로운 데이터 포인트 formula_72와의 가중치로 음이 아닌 값을 갖고, 임의의 formula_72에 대해 모든 가중치들의 합은 1이 된다. 각 모델에서 가중치 함수는 다음과 같다.
이 식은 포레스트 전체가 개별 트리의 가중치들의 평균값으로 다시 이웃 가중치 구조(weighted neighborhoods schemes)를 이루는 것을 보여준다. 여기서 formula_72의 이웃 formula_78는 포레스트 중 적어도 하나의 트리에서 formula_72와 같은 종단 노드로 떨어지는 데이터 포인트를 의미하게 된다. 이렇게 하여 formula_72의 이웃은 트리의 구조와 데이터 집합의 구조에 복합적으로 의존한다. 랜덤 포레스트에서 이웃들의 분포가 각 매개변수들의 지역적 중요성에 따라 달라진다.
엑스박스 360에서 사용되는 모션 캡처 주변기기인 키넥트에서는 랜덤 포레스트를 이용하여 주어진 입력에서 신체의 각 부분을 분류한다.
훈련 단계에서는 미리 신체부분들이 라벨화(pre-labeled) 되어있는 깊이 지도()에서 2,000개의 픽셀(pixel)을 임의로 추출해 300,000장의 깊이 지도당 트리 하나씩 총 세개의 깊이(depth) 값이 20인 트리를 구성한다. 트리 구성 시 1,000개의 코어 클러스터()를 사용한 GPU연산으로 하루정도의 시간이 걸린다. 테스트 단계에서는 앞서 구성한 트리들을 이용하여 임의의 입력 깊이 사진의 배경을 제외한 모든 픽셀들을 분류하는데 엑스박스 GPU에서 5밀리초(200프레임/초)의 시간 성능을 보인다.
안토니오 크리미니시() 등은 랜덤 포레스트를 이용하여 3차원 컴퓨터 단층 촬영 영상(, CT) 내에서 주어진 복셀에 대해 해당 되는 해부학 구조가 어디인지 검출하고 해당 위치를 파악하는 방법을 제안하였다.
훈련 단계에서는 해당 복셀이 어떤 해부학 구조인지 그리고 해당 구조의 바운딩 박스() 정보를 가지는 55개의 복셀 포인트들을 가지고 6개의 트리를 통해 동시에 학습한다. 테스트 단계에서는 각 트리로부터 얻어진 주어진 복셀이 각 해부학 구조에 포함될 확률들의 평균을 통해 최종 확률을 계산하여 이 확률이 해당 해부학 구조에 속할 가능성(∈[0, 1])이 0.5 이상인지 아닌지를 확인하여 결정한다.
마이크로소프트 연구소, 브라운 대학교, 그리고 캠브리지 대학교 연구팀은 다채널 자기공명영상()으로 촬영된 뇌 영상에서 고악성도 신경교종()를 검출하기 위해 랜덤 포레스트를 적용하였다.
기존의 많은 종양 검출 연구들이 전체적인 종양덩어리를 검출하는데 초점을 맞췄다면 이 연구팀에서는 랜덤 포레스트가 내재적으로 다중 클래스 특성을 지니는 점을 이용하여 서로 다른 종류의 신경 조직을 동시에 검출하는 연구를 진행하였다. 특히 기존의 신경 조직 검출 알고리즘에 비하여 전처리과정 등이 많이 요구되지 않으며, 비교적 간단한 복잡도 모델로 높은 검출 정확도를 보이는 결과를 얻어 랜덤 포레스트의 유용성을 증명하였다.