random tree(임의 숲)

랜덤 트리(random tree)

랜덤 트리는 서로 독립적이게 설계된다. 이진 트리를 보면 하나의 부모 노드로 부터 좌측 노드, 우측 노드으로 나뉜다.

       

                     [그림 1] 이진 트리

부모 노드는 질문을 갖고 있으며 질문의 결과에 따라 왼쪽, 오른쪽으로 분기 한다. 랜덤 트리는 트리 분류기

(tree classifier)를 사용한다. 트리 분류기의 노드는 질문을 갖고 있다. 이진 트리와 마찬가지로 특징 하나를 임계값과

비교하여 어느 쪽으로 진행할지 결정한다. 잎노드에 도착하면 부류를 결정하고 멈춘다.

     

                                        [그림 2] 트리 분류기 동작 방식 예

트리 분류기를 학습 시키려면 노드의 질문 Q를 만드는 방법과 잎 노드에 부류를 할당하는 방법을 결정해야 

한다. 트리 노드의 질문 Q1은 X를 두 집합Xleft, Xright로 나눈다. 이때 Xleft와 Xright는 순도가 높을수록 좋다.

(같은 부류의 데이터일수록 좋다) 예를 들어 두 부류(w1, w2)인 경우 Xleft에 모두 w1, Xright에 모두 w2로 분기되면

가장 이상적이다. 하지만 현실적으로 이런 상황은 거의 불가능 할 것이다. 따라서 순도를 최대로 하는 최적의 특징

과 분할점(임계값)을 찾아야 한다. 찾는 방법은 결정트리분기 를 참조 하면 된다.

이렇게 만든 질문을 루트 노드에 부여한 후 Xleft와 Xright를 가지고 각각 왼쪽과 오른쪽에서 같은 과정을 재귀적으로 

반복하면 된다. 이 분할을 언제까지 할지를 선택해야 하는데 순도 100%가 될되까지 분할하면 인식률은 좋으나 학습 

집합이 과적합(overfitting)되어 일반화 능력이 떨어지는 결과가 생긴다. 따라서 적절한 조건을 설정해 두고, 조건을 

만족하는 노드에서 멈추게 해야 한다. 멈춘 노드가 잎 노드(left node)가 된다. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

// 트리 분류기 학습 // 입력 : 학습 집합 X = {(x1,t1),(x2,t2), ... ,(xn,tn)} // 출력 : 트리 분류기 R   // 루트 노드를 가리키는 포인터   노드 하나를 생성하고 그것을 R이라 한다. split(R,X);   function split(T,X) {   if(X가 멈춤 조건을 만족)         T를 잎 노드로 설정하고 부류를 결정한다.   else {      T에서 최적의 특징과 그것의 최적 분할점을 찾아 질문 Q를 만든다.      Q로 X를 Xleft와 Xright로 나눈다.       새로운 노드 Tleft와 Tright를 생성한다.      T.leftChild = Tleft;      T.rightChild = Tright;      split(Tleft, Xleft);      split(Tright, Xright);   }  }

위 학습 알고리즘을 사용하면 하나의 트리 학습이 완료된다. 숲을 만드려면 각각의 트리의 독립성이 가장 중요하다.

만약 같은 학습집합을 가지고 위 알고리즘을 수행하면 같은 트리가 여러개 만들어 질것이다. 같은 트리를 여러개 구성해

봐야 동일한 결과를 출력하므로 아무 소용이 없다. 따라서 서로 다른 분류기는 나름의 차별성을 가져야 한다.

1 2 3 4 5 6 7 8 9 10

// 임의 숲 // 입력 : 학습 집합 X = {(x1,t1), (x2,t2), ..., (x3,t3)}, 샘플링 비율ρ(0≤ρ≤1), 분류기 개수 K // 출력 : 분류기 양상블 C = {Ck, 1≤k≤k}   C = φ; for(k=1 to K) {    X에서 임의로 ρN개의 샘플을 뽑아 X`라 한다. 이때 대치를 허용함    X`를 학습 집합으로 하고 [트리 분류기 학습] 알고리즘을 이용해 트리 분류기 Ck를 만든다.    트리 분류기를 C에 추가한다. }

참조 : 컴퓨터비전, 패턴인식(오일석)