의사결정나무/Decision Tree 총정리, 1편 회귀 문제에서 트리는 어떻게 돌아가는가?

본 책은 ISLR 및 기타 교재, 온라인 material들을 참고했습니다.

 

---

 

트리 모형에 대한 개괄

- 트리 모형은 하나의 feature space를 여러 공간으로 묶는 segmenting, stratifing의 성격을 갖고 있다.
- 이렇게 각각 형성된 segment에 속한 observation들은 같은 value를 갖는 것으로 추측하고, 단일한 prediction 값을 가질 수 있다.
- 트리 모형은 literacy의 측면에 있어서 상당히 유리하다. 직관적이고 해석하기 쉽다.
- 그러나 prediction accuracy의 측면에서는 손해를 보는 부분들이 존재한다.
- 생각해 보면 당연한 일이다. 각 segment에 속한 값들을 '하나로 뭉그러뜨려서' '하나의 예측값'을 갖게 한다고 하니, 그 segment 안에서의 variance는 놓치게 될 수 밖에.
- 그러나 이러한 약점을 상쇄할 수 있는 똑똑한 트릭들이 몇 가지 존재한다. 잘 알려진 배깅, 부스팅, 랜덤포레스트 등이 그것이다.

 

---

 

트리 모형의 기초 개념

- 위에서 이야기한 것처럼, feature space가 여러 공간으로 segmenting 된 것을 terminal node 혹은 leave of the tree라고 부른다,
- feature space가 쪼개지는 부분을 internal node라고 부른다.
- node들을 연결하는 부분을 가지branches라고 부른다.

---

 

실제로 tree를 building하는 것은 다음과 같은 과정을 거친다.

1. feature space를 나눈다. 즉, X_1, X_2, X_3, ... , X_P의 변수 공간을, 서로소인 공간 R_1, R_2, ... , R_J의 J개의 공간으로 나눈다.
2. 새로 나눠진 공간 R_J 안에 있는 관측치들은 전부 같은 prediction 값을 산출한다. 이 때 이 prediction 값은 해당 지역에 있는 observation들의 response 값의 평균치이다.

이 때 할 수 있는 자연스러운 질문은, "R_1, R_J를 어떻게 적절하게 잘 구성할 것인가?"이다.

이를 위해 다음과 같은 목적함수를 최소화한다.

즉, 각 공간 R_J의 예측값과 실제값의 차이(loss)가 최소가 되도록 하는 R_1 ~ R_J를 찾는 것이다.

---

이를 위해 recursive binary splitting이라는 전략을 채택한다.

 

이는 top-down/greedy 방식이다. 

* top-down이라는 건 single region부터 시작해서 여러 region으로 나뉘어가는 과정을 tree 모양으로 그려보면 위에서 아래로 내려가는 형태를 띄기 때문이다.

* greedy하다는 건 앞뒤 고려하지 않고 각 step에서 loss를 가능한 한 최소화하겠다는 뜻이다.


이를 위해서 다음과 같은 목적함수를 j와 s에 대해 최소화한다.

s는 j가 나뉘어지는 분기점cutpoint이다.

 

이제 전체 region에서 두 개의 region, 곧 R1과 R2로 나뉘어졌다.

이 다음 단계에서는 R1과 R2 둘 중 하나의 공간을 선택하여, 다시 두 공간으로 나눈다.

이러한 단계가 일정 기준을 만족할 때까지 반복한다.

---

문제는 이렇게 트리를 구축할 시, overfitting이 발생할 확률이 굉장히 크다.

따라서 트리의 사이즈를 약간 축소시키면서 과적합을 방지하는데, 이를 가지치기pruning이라 부른다.

 

트리 분기split을 조금 덜 하면 bias가 조금 높아지는 대신 variance를 낮출 수 있다.

 

이를 위해 엄청나게 큰 트리 T_0를 생성한 다음, 큰 나무의 가지치기를 통해 새로 나무를 얻는다.

이렇게 얻은 나무를 subtree라고 부른다.

각 subtree에 대해 교차검증을 이용해 test performance를 측정하고,

가장 성능이 괜찮게 pruning된 subtree를 최종 모델로 결정한다.

문제는 모든 predictor에 대해 가능한 모든 subtree를 고려한다는 것은 연산상 불가능하다는 것이다.

---

이를 위해 Cost complexity pruning이라는 방법을 사용한다.

cost complexity pruning은 α라는 hyperparameter를 사용해 다음과 같은 목적함수를 최소화한다.

여기서 |T|는 전체 트리 T의 terminal nodes의 개수이고, Rm은 m번째 terminal node에 대응하는 분할된 feature 공간이다.

이 목적함수를 최소화하는 것이 목적이므로, α가 크면 클수록 전체 cost 값은 linear하게 커질 것이다.따라서 α는 |T|, 곧 terminal node의 개수가 너무 커져서 tree가 too complex해지는 것을 막는다.

 

이를 이용해, 다음과 같은 알고리즘을 돌린다.

1. recursive binary splitting을 이용해, 아주 큰 트리를 생성한다.

2. Cost complexity pruning을 적용한다.
3. K-fold CV를 이용해 적정한 α값을 산정한다.

  - 1,2번 스텝을 k번째 fold를 제외한 나머지 data에 적용한다.

  - 해당 α값을 사용한 모델이, k번째 fold를 validation set으로 사용해 얼만큼 성능이 나오는지 validate한다.
  - 결과값들의 기대값을 확인하고 적정한 α값을 선택한다.

4. 1~3의 과정을 통해 정한 α값에 대응하는 subtree를 최종 선택한다.

 

 

 

---

다음 편에서는 분류 문제에서 tree 모형이 어떻게 돌아가는지 알아보도록 하겠다.