결정 트리 분기

이진트리의 경우 노드 Xt를 기준으로 왼쪽 자식과 오른쪽 자식으로 나뉘게 된다. 이때 어떤 것을 기준으로 자식을

둘로 나눌지를 선택해야 한다. 

                                [그림 1] 노드 분기

이때 어떤 기준으로 나눌지를 잘 선택해야 한다. 그냥 숫자의 경우 Xt보다 작으면 왼쪽, 크면 오른쪽으로 나누면 

그만이지만 여러개의 특징 벡터로 구성될 경우 쉽지 않은 질문이다. 정당한 방법에 의해 둘로 나눠야 한다. 이것은 

일종의 최적화 문제일 것이다.

후보들 중 여러개의 샘플들이 혼합되어 있는데, 이들을 어떻게 Xleft, Xright로 나눌지를 잘 결정해야 노드의 분기 과정

마지막에 잎노드에 도달했을때 같은 분류의 샘플들만 포함되어 있을것이다. 따라서 가능한 XTleft와 XTright에 각각 동질

의 샘플이 담기는 것이 좋다.

이런 동질을 측정해 주는 기준이 불순도(inpurity)이다. 불순도는 여러 방법으로 정의할 수 있는데, 엔트로피(entropy)를

사용한 정의이다. [식 1]은 엔트로피를 사용한 정의를 나타낸다.

Wi는 M개의 부류 중에서 i번째를 나타내며 P(Wi|T)는 노드 T에서 Wi가 발생할 확률이다. 엔트로피는 M 개의 부류가

같은 확률을 가질 때 가장 큰 값을 가진다. 같은 확률이라는 사실은 Xt에 같은 빈도를 나타낸다는 것을 의미하므로 

불순도가 가장 높다. 엔트로피는 어느 부류 하나의 확률이 1이고 나머지는 모두 0일때 0이다. 이떄 불순도가 0으로 제일

낮은 경우이다.

또 다른 측정 방법은 [식 2]로 정의되는 지니 불순도(Gini impurity)이다. 이 식은 어느 부류가 1의 확률을 갖는 경우에

최소값 0을 갖는다.

마지막으로 [식 3]으로 정의되는 오분류 불순도(misclassification impurity)이다. [식 3]을 보면 불순도는 바로 샘플

들을 가장 높은 확률의 부류로 분류했을 때 발생하는 오분류 비율과 같다.

불순도 측정은 노드 T에서 Wi가 발생할 확률 P(Wi|T)를 사용하는데 이것을 어떻게 추정할 것인가? 주어진 정보는

오로지 Xt뿐이다. 따라서 Xt에 Wi가 발생하는 빈도를 이용하여 [식4]와 같이 정의한다. |Xt|는 집합 Xt의 크기이다.

예1) 불순도 측정

     노드 T의 샘플 집합 Xt가 아래와 같다고 하자.

          

이 집합에는 아홉 개의 샘플이 있고 부류 w1이 3번 w2이 4번 그리고 w3이 2번 나타났다. 따라서 [식4]에 의해서

P(w1|T) = 3/9, P(w2|T) = 4/9, P(w3|T) = 2/9이 된다. [식1], [식2], [식3]를 각각 구하면 다음과 같다.

불순도는 하나의 노드를 대상으로 측정한다. 이제 이것을 이용해서 [그림 1]의 노드 분기에 필요한 최적의 질문을 

고르는데 사용할 기준 함수를 만들어야 한다. 분기 결과로 만들어지는 새로운 샘플 집합 XTleft, XTright는 가급적

불순도가 낮은 것이 좋다. 따라서 불순도 감소량을 [식 5]로 정의하고 그것을 기준 함수로 사용하면 된다.

극단적 예를 든다면 왼쪽과 오른쪽 자식 노드 모두 한 부류의 샘플만을 가지게 되어 불순도가 둘 다 0이 된다면

[식5]의 불순도 감소량 im(T)가 되어 이때 최대값이 된다. 따라서 이런 결과를 만드는 질문이 있다면 당연히 

그것을 노드 T의 질문으로 선택해야 한다. 실제에서는 Δim(T)를 최대로 하는 질문을 취하면 된다. 

[식6]은 부모 노드와 자식 노드의 불순도를 독립적으로 계산한 후 이들을 이용하여 불순도 감소량을 계산한다. 

불순도 감소량을 측정하는 다른 방법으로 투잉기준(twoing criteria)것도 있다. [식 6]은 투잉기준을 정의한다.

현재까지 후보 질문을 어떻게 생성할 것인지에 대해 정리했다. 후보 질문을 어떻게 생성할 것인지에 대해

구체적으로 정의해야 한다. 특징들 중에는 비계량인것과 계량인것이 존재한다. 비계량의 특징은 한정된 계수를

갖는다. 예를 들어 혈액형이라고하면 A, B, O, AB의 네 가지 값만 갖을 것이다. 이 예에서는 네 개의 후보 질문이

생긴다. 'xi = a?' 의 질문만 만들면 된다. 이에 비해 계량인 경우는 까다롭다. 이 경우에도 몇 개의 이산 값만을 가지면 

'xi < a?' 식의 질문을 만들면 된다. 계량에서는 양이라는 개념을 가지므로 등호 대신 부등호를 사용한다. 실수의 경우

범위를 나누어 구간화 하던지 혹은 샘플들이 갖는 값의 분포를 보고 인접한 두 값의 가운데를 a로 사용하면 된다.

예2) 후보 질문 생성

예1)과 같은 샘플집합을 활용할때, 샘플은 아래와 같은 세 개의 특징으로 표현되는데 앞의 두 개는 비계량이고

세 번째는 실수로 표현되는 계량 데이터라고 가정한다.

노드 T의 샘플 집합 Xt가 아래와 같다고 할때, 몸무게는 소수점 이하 첫재 자리까지 표현했다.

   

앞의 두 특징으로 아래와 같은 12개의 후보 질문이 만들어 진다.

                                          [그림 2] 샘플 집합 Xt

x3의 후보 질문은 샘플 값을 보고 만든다. 그들의 값은 아래와 같이 분포한다.

인접한 두 값의 가운데 값을 a라고 쓴다면 아래와 같이 여덟 개의 후보 질문이 만들어 진다.

이렇게 총 20개의 후보 질문이 생성되었다.

예3) 불순도 감소량 계산

예제2)의 데이터를 재활용 해보면 생성된 20개의 후보 질문 중 하나에 대해서만 불순도 감소량을 계산해 본다.

사용할 질문은 'x2=3?'(즉 선호품목이 스포츠용품?)이고 그에 따른 분기 결과는 [그림 3]과 같다.

                                                  [그림 3] 스포츠 용품인가? 라는 질문에 따른 분기 결과

이 분기 결과에 대한 불순도 감소량을 계산해 보면

총 세가지 불순도 측정 방법과 두 가지 불순도 감소량 측정 방법을 제시하였는데, 어떤 것을 사용하여야 좋을까?

여러 문헌에서 결정 트리의 성능은 불순도 측정 방법보다 멈춤 조건과 노드 가지치기 방법에 더 영향을 받는다는

실험 결과를 언급하고 있다. 띠리사 이들 방법중 하나를 선택해 사용하면 된다. 만약 성능 평가가 중요한 상황이라면

훈련집합을 수집한 후 각각의 방법을 테스트 해 평가하고 그 결과에 따라 최적의 방법을 고르는 수 밖에 없다.

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