결정트리(Decision tree)란?

Decision Tree

• 분류와 회귀, 다중 출력도 가능한 알고리즘이다.
• 매우 복잡한 데이터셋도 학습할 수 있다.
• 강력한 머신러닝 알고리즘 중 하나인 랜덤 포레스트의 기본 구성 요소이기도 하다.

확률 추정

먼저, 어떻게 결정 트리가 예측을 만들어내는지 위 그림을 통해 보자.

새로 발견한 꽃의 품종을 분류하려고 한다고 하자. 먼저 루트 노드에서 시작하여 그 꽃의 길이가 2.45보다 짧은 지 검사한다. 만약 짧다면 왼쪾 노드로 이동한다. 이 경우 자식 노드가 없는 리프 노드이므로, 추가적인 검사를 하지 않고 노드에 있는 예측 클래스를 보고 setosa를 예측 값으로 내뱉는다.

노드의 구성 요소를 보면 gini라는 것이 있다. 이는 지니 불순도를 말하는 것이고, 그 노드의 불순도를 측정한다. 한 노드의 모든 샘플이 같은 클래스에 속해 있다면 그 노드를 순수(gini값 0)하다고 한다.

 

$$G_i = 1 - \sum p_{i,k}^2$$

 

만약, 한 샘플이 특정 클래스 k에 속활 확률을 추정하고자 한다면, 먼저 리프 노드를 찾기 위해 트리를 탐색하고, 그 노드에 있는 클래스 k의 훈련 샘플의 비율을 반환한다.

위 그림에서 어떤 꽃 x가 길이가 5cm이고, 너비가 1.5cm라고 한다면, 루프 노드에서 오른쪽 자식 노드로 이동하고, 그 자식 노드에서 왼쪽으로 이동하여 versicolor를 반환한다.

학습과 비용 함수

여기서 궁금한 것이, 그럼 저 노드들의 length, width와 같은 특성과 2.45, 1.75와 같은 특성의 값은 어떻게 정해지는 걸까?

 

일반적으로 CART 알고리즘을 사용하여 특성과 그 값의 쌍을 정한다. 즉, 해당 알고리즘을 사용하여 결정 트리를 학습시킨다. 이 특성과 값의 쌍을 통해 노드를 만들고, 그 노드를 이용하여 학습 데이터 셋을 분할해나가는 것이다. CART 알고리즘을 통해 CART 비용 함수를 최소화하는 특성과 그 값의 쌍을 구한다. 비용 함수를 최소화하는 파라미터를 탐색하기 위해 경사 하강법을 사용할 때와 그 틀이 같다.

 

특성과 그 값을 각각 k, t_k라 하면, CART 비용 함수는 다음과 같다.

 

$$ J(k, t_k) = \frac{m_{left}}{m} G_{left} + \frac{m_{right}}{m} G_{right} $$

 

여기서, G_left/right는 왼쪽/오른쪽 서브셋의 불순도를 나타내며, m_left/right는 왼쪽/오른쪽 서브셋의 샘플 수를 나타낸다.

트리의 깊이와 분할 시 필요한 최소 샘플 수, 리프 노드에 들어갈 최소 샘플 수 등을 통해 분할의 횟수를 조정할 수 있다.

 

CART 알고리즘은 탐욕적 알고리즘이다. 즉 맨 위 루트노드에서부터 시작해 분할을 진행한다. 따라서 현재 단계의 분할이 몇 단계를 거쳐 가장 낮은 불순도로 이어질 수 있을 지 고려하지 않고, 일단 '현재' 최적이라고 생각하는 기준을 통해 분할한다. 최적의 솔루션을 보장하지 않지만 종종 납득할만한 솔루션을 만들어낸다. 최적의 트리를 찾는 것은 NP-Complete 문제로 알려져 있다.

 

회귀

결정 트리는 회귀 문제에도 사용할 수 있다고 했다. 어떻게 그럴까?

 

아래 그림을 보자.

앞선 분류 트리와 비슷해 보인다. 차이는 각 노드에서 클래스를 예측하는 대신 어떤 값을 예측한다는 것이다. 예를 들어 Longitude가 -118인 샘플의 타겟값을 예측한다고 해보자. 루프 노드부터 순회하면 결국 value=1.421인 리프 노드에 도달하게 된다. 이 리프 노드에 있는 4967개의 훈련 샘플의 평균 타겟값이 예측 값이 된다. 이 예측 값을 사용해 100개 샘플에 대한 MSE를 계산하면 1.421이 된다.

 

학습에는 분류 트리에서와 마찬가지로 일반적으로 CART 알고리즘이 사용된다. 차이점은, 분류 트리에서는 훈련 세트를 불순도를 최소화하는 방향으로 분할하는 대신 MSE를 최소화하는 방향으로 분할한다.

 

문제점

• 계단 모양의 결정 경계를 만든다. 따라서 훈련 세트의 회전에 민감하다.
  • 훈련 세트를 더 좋은 방향으로 회전시키는 PCA 기법을 사용하여 문제점을 어느정도 해소할 수 있다.
• 훈련 세트에 있는 데이터의 작은 변화에도 매우 민감하다. 즉, 어떤 데이터를 훈련 세트에서 제거하면 결정 경계가 크게 바뀔 수 있다.

 

랜덤 포레스트는 많은 결정 트리에서 만든 예측을 평균하여 이런 불안정성을 극복할 수 있다.