Decision Tree(의사결정나무)

 

Decision Tree(의사결정나무)는 의사결정 규칙을 Tree 구조로 나타내어 자료에 대한 패턴을 파악하는 알고리즘입니다.

 

그림1. 임의의 동물에 대해 포유류 여부를 판정하는 의사결정나무

 그림 1은 임의의 동물이 주어졌을 때, 체온과 새끼를 낳는지의 여부에 의해 포유류/포유류가 아님을 결정하는 decision tree입니다.

(어릴 때 하던 스무고개, 심리테스트와도 비슷합니다.)

여기에서 각 점(원과 사각형)을 node, 각 화살표를  edge라고 합니다.

 

 디시전 트리의 노드 종류는 다음 3가지로, 일반 tree의 노드 호칭과 비슷입니다.

    - root node: 들어오는 edge가 없고 나가는 edge가 0개 이상인 노드

    - internal node: 들어오는 edge가 한 개이고 나가는 edge가 2개 이상인 노드

    - leaf node: 들어오는 edge가 한 개이고 나가는 edge가 없는 노드

 

leaf node 가 아닌 노드를 non-terminal node라고도 합니다.

 

분류 문제에 사용되는 decision tree에서, 각  리프 노드는 클래스 라벨(분류 하고자 하는 종류) 혹은 각 라벨을 갖게 될 확률을 가진 벡터에 할당된다. 포유류 여부를 판정하는 문제에서는 포유류/포유류 아님이 클래스 라벨이 됩니다.

 

non-terminal 노드에는 주어진 데이터를 분류하기 위한 테스트 조건이 명시되어 있습니다. 그림 1의 경우 첫 번째 테스트 조건은 체온, 두 번째 테스트 조건은 새끼를 낳는지의 여부입니다.

임의의 동물이 주어졌을 때, 루트 노드에서부터 테스트 조건에 대한 결과를 따라 내려오다 보면 해당 동물의 클래스를 찾게 됩니다.

 

 

의사결정나무를 데이터 공간을 가로지르는 서로 수직인 hyper-plane의 총체로 볼 수도 있습니다.

각 노드를 거칠 때마다 우리는 노드가 가진 조건에 따라 하나의 자식 노드를 고르게 됩니다.

이 과정을 각 노드가 가진 조건에 따라, 하나의 hyper-plane을 이용해 데이터 공간을 서로 겹치지 않는 두 개의 공간으로 자르는 과정으로도 생각할 수 있습니다.

 

그림2. 의사결정나무

 

의사결정나무의 한 가지 특성은 비선형 알고리즘이라는 것입니다.

선형 알고리즘이란, 인풋 데이터 $x$에 대해 $h(x)= \theta^T x$의 형태로 나타낼 수 있는 알고리즘을 뜻합니다.

 

그림3

만약 linear regression을 가지고 그림 3의 왼쪽 데이터를 분류한다면, 높은 정확도를 기대할 수 없을 것입니다.

그러나 위와 같이 공간을 분할해 가며 답을 찾는 의사결정나무의 경우 보다 높은 정확도로 붉은 점과 초록색 점을 분리해낼 수 있을 것이라고 기대할 수 있습니다.

 

의사결정나무 inducer(classifier)란 주어진 데이터셋으로부터 자동으로 의사결정나무를 생성하는 알고리즘입니다.

주어진 학습 데이터셋으로부터 최적의 의사결정나무를 찾아내는 것은 아주 어려운 문제입니다.

 

- 주어진 데이터셋으로부터 가장 간단한 의사결정나무를 찾아내는 과제: NP-hard

- 새로운 학습 데이터를 검증할 때 거치는 테스트의 기대값이 가장 적은 이진 의사결정나무를 찾아내는 과제: NP-complete

- 주어진 의사결정나무와 동치인 가장 간단한 의사결정나무를 찾아내는 과제: NP-hard

- 주어진 의사결정 테이블로부터 가장 간단한 의사결정나무를 찾아내는 과제: NP-hard

 

따라서, 최적의 의사결정나무 알고리즘을 사용하는 것은 오직 데이터셋이 작을 때만 유효한 전략이며,

현실적으로 문제를 해결할 때는 휴리스틱한 방법이 종종 개입됩니다.

 

이제 의사결정나무의 영역을 분할하는 방법을 알아보겠습니다.

의사결정나무에 의해 나누어진 각 영역 $R$에 정의되는 loss function을 $L$이라고 하겠습니다.

그러면 어떤 영역 $R$을 자식 영역 $R_1, R_2$로 분할하는 바람직한 방법은 분할한 후의 loss가 줄어드는 방법일 것입니다.

또, 자연스럽게 자식 영역 $R_1, R_2$의 사이즈에 따라 loss값에 가중치를 줄 수 있을 것입니다.

따라서 영역을 분할할 때는 다음 식을 최대화하는 방향으로 분할하여야 합니다. 

 

$L(R_p) - \frac{|R_1|L(R_1) + |R_2|L(R_2)}{|R-1|+|R_2|}$

 

이렇게 줄어드는 loss값의 양을 information gain이라고도 합니다.

 

각 영역에 적용할 loss function은 해결하고자 하는 과제가 분류(classification)인지 회귀(regression)인지에 따라 달라집니다.

분류 과제의 경우 loss function은 종종 cross-entropy를 사용해 정의됩니다.

 

$L(R) = -\sum_{c} \hat{p_c} \log_2\hat{p_c}$

 

위 식에서 $c$는 각 카테고리를 표현합니다.

회귀 과제의 경우 트레인 데이터 셋 $(x_1, y_1), \ldots, (x_n, y_n)$에 대한 loss function은 다음과 같이 sqaured loss를 사용하여 정의됩니다.

이 때 예측결과 $\hat{y}$는 해당 영역의 모든 타겟 벡터 $y_i$의 합으로 정해집니다.

 

$\hat{y} = \frac{\sum_{i \in R}y_i}{|R|}$

$L(R) = \frac{\sum_{i \in R}(y_i-\hat{y})^2}{|R|}$

 

fully grown 의사결정나무란 각 리프 노드들이 정확히 하나의 트레이닝 데이터포인트에 할당되도록 나무를 끝까지 키우는 것입니다.

이렇게 의사결정나무를 끝까지 키우게 되면, high variance low bias모델을 얻게 됩니다.

즉, 트레인 데이터에 오버피팅되기가 쉽습니다.

 

그림4. bias-variance tradeoff

따라서, 몇 가지 멈춤 조건을 이용해 의사결정나무의 성장을 언제 머출지 정하는 것이 필요합니다.

몇 가지 흔한 방법은 다음과 같습니다.

• 최소 leaf 크기: leaf 영역 $R$의 크기가 일정 임계치 이하로 작아지면 $R$을 분할하지 않는다
• 최대 깊이: 임계치 이상의 깊이로는 분할하지 않는다
• 최대 노드 개수: 의사결정나무가 특정 임계치 개수 이상의 노드를 가지면 멈춘다

그림5. additive structure에 대한 의사결정나무(좌)와 선형 모델(우)의 적용

의사결정나무 방법의 장, 단점은 다음과 같습니다.

• 장점: 
  • 계산 비용이 적다
  • 학습 과정에 대한 설명력이 높다
  • 범주형 변수를 처리하기 쉽다
  • 복잡한 데이터 세트도 학습할 수 있다
• 단점:
  • variance가 크다(overfitting되기 쉽다)
  • additive 구조에 대한 모델링이 힘들다

 

참고: 

[1] https://www-users.cs.umn.edu/~kumar001/dmbook/ch4.pdf

[2] http://www.ise.bgu.ac.il/faculty/liorr/hbchap9.pdf

[3] http://cs229.stanford.edu/notes/cs229-notes-dt.pdf