의사결정트리(Decision Tree) 회귀트리, pruning 쉽게 이해하기

 결정 트리 학습법(decision tree learning)은 머신러닝 학습 방법 중, 결과 데이터(output variable)로 학습시키는 지도 학습(supervised learning)에 해당된다. Output variable 이 연속적인 값일 경우(월급, 몸무게, 넓이 등) 회귀(regression)를 사용하며, output variable이 카테고리에 해당한다면(성별, 국적, 직급 등) 분류(classification)를 사용한다. 여기서는 회귀 트리 (Regression tree)를 설명하고자 한다.

 

 

회귀 트리 개념

 회귀 트리는 RSS(오차 제곱합)를 가장 잘 줄일 수 있는 변수(predictor)를 기준으로 분기(split)를 만들어 결과를 예측하는 매우 단순한 모델이다. 어떤 변수가 중요한지, 변수의 값에 따라 예측 결과가 무엇인지 한눈에 볼 수 있어 설명력이 좋은 장점이 있다.

 아래 그림과 같이 야구선수의 경력(Year)과 안타 수(Hits)로 연봉(Salary)을 예측하고자 할 때, RSS가 가장 줄어드는 선(경력이 4.5인 선)을 긋고 그다음으로 좋은 선(안타 수가 117.5인 선)을 그어 나가며 트리를 완성할 수 있다.

 

Hitter data

 

 

회귀 트리 학습

 회귀 트리는 top-down으로 진행되며, greedy(탐욕) 방식으로 가장 좋은 가지를 찾아서 분기를 나누는 방식을 반복한다. 모든 변수 $X_1, …, X_p$ 와 모든 가능한 cutpoint $s$에 대해 RSS를 가장 많이 줄여주는 j와 s를 선택하게 된다. j와 s로 나뉜 구역(half-planes)은 다음과 같이 정의 가능하다.

 

$R_1(j,s) = \{X|X_j<s\}  and  R_2(j,s)=\{X|X_j \geq s\}$

 

 다음 수식을 최소화시키는 j와 s를 구하는 식으로 첫 분기를 나눈다.

 

$\sum_{i: x_i \in R_1(j,s)} (y_i-\hat{y}_{R_1})^2 + \sum_{i: x_i \in R_2(j,s)} (y_i-\hat{y}_{R_2})^2$

 

 $R_1, R_2$로 구획을 나눌 때 $R_1(j,s)$ 에 속한 데이터들과 구획 내의 평균 $\hat{y}_{R_1}$ 와의 차이를 구한 뒤 제곱하고, 이를 $R_2$도 마찬가지로 진행한 뒤 모두 더함으로 RSS를 구한다.

 

 

가지치기(Pruning)

 회귀 트리의 파라미터로는 크게 depth와 node수가 있다. 데이터에 적합한 depth와 node 수를 다양하게 바꿔가며 cross validation으로 모델을 고르면 된다.

 Pruning은 depth와 node 수를 충분히 크게 하여 큰 tree를 만든 뒤 다시 적당한 크기로 pruning을 하여 subtree를 모델로 고르는 방식이다. Pruning 방식이 갖는 장점은 현재 tree로는 성능이 크게 좋지 않지만 depth가 더 깊어짐으로써 성능이 높은 케이스를 발견할 수 있기 때문이다. 가령 다음 케이스는 depth가 1인 경우 성능이 아주 나쁘지만, depth가 2인 경우 성능이 아주 좋아지는 것을 볼 수 있다. 이런 경우 충분히 큰 트리를 만든 후 적절하게 pruning 하는 방식이 좋은 결과로 이어진다. 

 

Pruning이 좋은 예시

 

 Cross validation을 통해 모든 subtree를 만들어보고 모델을 고르는 것은 효율적이지 못하다. 이에 Cost complexity pruning을 사용해볼 수 있는데, 적당한 tuning parameter $\alpha$를 사용하여 말단 노드 (leaf node)의 개수를 의미하는 $|T|$ 의 크기를 조정할 수 있다. 다음과 같이 RSS에 $\alpha|T|$를 더한 수식을 사용하여 적당한 subtree를 고를 수 있다.

 

$\sum^{|T|}_{m=1} \sum_{x_i \in R_m} (y_i - \hat{y}_{R_m})^2 + \alpha|T|$

 

 Tree size에 따른 MSE를 그려본 결과는 다음과 같이 나온다.

Tree size 와 MSE관계