랜덤 트리(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)가 된다. 

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