이번 장에서 학습할 트리(tree) 기반 방법은 예측변인 공간(predictor space)을 여러 개의 단순한 구역으로 계층화 또는 분할한다. 어떤 관측치에 대해 예측하기 위해서는 해당 관측치가 속한 구역에 있는 다른 훈련 관측치들의 평균이나 최빈값을 사용한다. 예측변인 공간을 나누는 규칙을 나무(tree)로 표현할 수 있기 때문에 이러한 방법을 결정 트리(decision tree) 방법이라고 한다. 트리 기반 방법은 간단하고 해석이 쉽다는 장점이 있지만, 예측 정확도가 낮기 때문에 여러 트리를 결합하는 배깅(bagging), 랜덤 포레스트(random forests), 부스팅(boosting)의 방법을 사용한다.
8.1 결정 트리의 기초
8.1.1 회귀 트리
회귀 트리를 만드는 과정은 다음과 같다. 먼저, \(X_1,X_2, . . .,X_p\)의 가능한 값들의 집합인 예측변인 공간을 \(J\)개의 겹치지 않는 별개의 구역, \(R_1,R_2, . . . , R_J\)로 나눈다. 단순성을 유지하고 예측 모델의 해석을 쉽게 하기 위하여 예측변인 공간을 고차원의 직사각형, 혹은 박스로 나눈다. 아래의 RSS를 최소화하는 박스 \(R_1, . . .,R_J\)를 찾는 것이 목적이다.
\[\sum^J_{j=1} \sum_{i∈R_j} (y_i − \hat{y}_{R_j})^2\]이때, \(\hat{y}_{R_j}\)는 \(j\)번째 박스에 속하는 훈련 관측치들의 반응변인의 평균이다. 예측변인 공간의 가능한 분할 방법을 모두 고려할 수 없기 때문에 재귀 이진 분할(recursive binary splitting)이라 불리는 하향식(top-down) 그리디(greedy) 접근을 취한다. 트리의 상단에서 시작하여 아래로 내려가며 연속적으로 예측변인 공간을 두 개의 새로운 가지로 분할하기 때문에 하향식이며, 각 스텝에서 최선의 분할만을 채택하기 때문에 그리디 방식이다.
재귀 이진 분할을 수행하기 위해서는 먼저 예측변인 \(X_j\)와 예측변인 공간을 \(\left\{X\vert X_j < s\right\}\)와 \(\left\{X\vert X_j ≥ s\right\}\)로 나눔으로써 RSS를 가장 크게 줄이는 컷포인트 \(s\)를 선택한다. 즉, 모든 예측변인 \(X_1, . . .,X_p\)와 각 예측변인에 대한 컷포인트 \(s\)의 모든 가능한 값들을 고려하여 RSS가 가장 낮은 트리를 만드는 예측변인과 컷포인트를 고르는 것이다. 수식으로 표현하면 어떤 \(j\)와 \(s\)에 대한 반평면(half-planes)의 짝을 아래와 같이 정의할 수 있다.
\[R_1(j, s) = \left\{X\vert X_j < s\right\}, \quad R_2(j, s) = \left\{X\vert X_j ≥ s\right\}\]그리고 아래를 최소화하는 \(j\)와 \(s\)의 값을 찾고자 하는 것이다.
\[\sum_{i: x_i∈R_1(j,s)} (y_i − \hat{y}_{R_1})^2 + \sum_{i: x_i∈R_2(j,s)} (y_i − \hat{y}_{R_2})^2\]이때, \(\hat{y}_{R_1}\)은 \(R_1(j, s)\)에 속하는 훈련 관측치들의 반응변인의 평균이고, \(\hat{y}_{R_2}\)은 \(R_2(j, s)\)에 속하는 훈련 관측치들의 반응변인의 평균이다.
중지 기준(stopping criterion)에 도달할 때까지 이 과정을 반복하되, 전체 예측변인 공간이 아니라 이전에 나누어진 구역들 중 하나의 구역을 선택해서 분할한다. 모든 구역 \(R_1, . . . , R_J\)가 생성된 후에는 어떤 테스트 관측치의 반응변인을 예측하기 위하여 해당 테스트 관측치가 속하는 구역에 존재하는 훈련 관측치들의 반응변인의 평균을 사용한다.
구역 \(R_1, . . . , R_J\)는 터미널 노드(terminal nodes) 혹은 리프(leaves)라고 불린다. 한편, 트리를 따라 예측변인 공간이 나뉘는 포인트들을 내부 노드(internal nodes)라고 하며, 이러한 노드들을 연결하는 트리의 분할을 가지(branches)라고 한다.
지금까지 설명한 방법에서는 트리가 지나치게 복잡해져 데이터에 과적합되어 테스트셋에서의 성능이 나빠질 수 있다. 한 가지 해결책은 아주 큰 트리 \(T_0\)를 만들고 가지를 쳐(pruning) 서브트리를 만드는 트리 프루닝(tree pruning)이다. 그렇다면 어떻게 테스트 오류율이 낮은 서브트리를 만들 수 있을까? 가능한 모든 서브트리를 고려하는 대신, 비용 복잡도 프루닝(cost complexity pruning) 또는 weakest link pruning을 사용할 수 있다. 이 방법에서는 음수가 아닌 튜닝 파라미터 \(α\)의 각 값에 대하여 아래를 최소화하는 서브트리 \(T ⊂ T_0\)가 존재한다.
\[\sum^{\vert T\vert}_{m=1} \sum_{i: x_i∈R_m} (y_i − \hat{y}_{R_m})^2 + α\vert T \vert\]이때, \(\vert T \vert\)는 트리 \(T\)의 터미널 노드의 개수, \(R_m\)은 \(m\)번째 터미널 노드에 해당하는 예측변인 공간의 서브셋, \(\hat{y}_{R_m}\)은 \(R_m\)에서의 예측된 반응변인, 즉 \(R_m\)에 속하는 훈련 관측치들의 반응변인의 평균이다. 튜닝 파라미터 \(α\)는 서브트리의 복잡도와 훈련 데이터에 대한 적합도 간의 트레이드오프를 조절한다. \(α = 0\)일 때 서브트리 \(T\)는 \(T_0\)와 같고, \(α\)가 증가함에 따라 더 많은 가지 치기가 발생한다. \(α\)의 값은 교차 검증을 통해 선택할 수 있다.
지금까지 배운 내용을 정리해보자. 회귀 트리를 만들기 위해서는 우선 재귀 이진 분할 방법을 사용해 훈련 데이터에 대하여 큰 트리를 생성한다. 트리의 생성은 각 터미널 노드가 일정 개수 미만의 관측치를 가질 때 종료된다. 이렇게 만들어진 큰 트리에 비용 복잡도 프루닝을 적용하여 \(α\)의 함수로 최선의 서브트리들을 도출한다. 마지막으로 k-폴드 교차검정을 통해 \(α\)의 값을 결정하고 그에 맞는 서브트리를 선택한다.
8.1.2 분류 트리
분류 트리에서는 각 관측치가 속하는 구역에 있는 훈련 관측치들이 가장 많이 분류되는 클래스로 해당 관측치를 예측한다. 회귀 트리에서와 마찬가지로 재귀 이진 분할을 사용하여 분류 트리를 만들 수 있다. 그러나 회귀 트리에서와 달리 분류 트리에서는 이진 분할을 수행하기 위한 기준으로 RSS 대신 다음의 두 가지 척도를 사용한다.
먼저 지니 인덱스(Gini index)는 아래와 같이 정의된다.
\[G = \sum^K_{k=1} \hat{p}_{mk}(1 − \hat{p}_{mk})\]이때, \(\hat{p}_{mk}\)는 \(m\)번째 구역에서 훈련 관측치들이 \(k\)번째 클래스에 속한 비율이다. 모든 \(\hat{p}_{mk}\)가 0 혹은 1에 가까울 때 지니 인덱스도 작아진다. 즉, 지니 인덱스는 노드에 속한 관측치들이 대부분 단일한 클래스에 속하는지 나타내는 노드의 순도(purity)에 대한 척도이다.
다음으로 교차 엔트로피(cross-entropy)는 아래와 같이 정의된다.
\[D = − \sum^K_{k=1} \hat{p}_{mk} \log \hat{p}_{mk}\]\(0 ≤ \hat{p}_{mk} ≤ 1\)이므로 \(0 ≤ −\hat{p}_{mk} \log \hat{p}_{mk}\)이다. 모든 \(\hat{p}_{mk}\)가 0 혹은 1에 가까울 때 교차 엔트로피도 0에 가까운 값을 가진다. 따라서 지니 인덱스와 마찬가지로 교차 엔트로피도 \(m\)번째 노드가 순수하면(pure) 작아진다.
분류 오류율(classification error)에 비해 지니 인덱스나 교차 엔트로피가 노드 순도에 더 민감하기 때문에 분류 트리에서 특정 분할의 질을 평가하는 데 사용된다.
8.1.3 트리의 장점과 단점
먼저, 트리의 장점은 매우 설명하기 쉽다는 것이다. 또한 시각적으로 표현할 수 있으며, 해석이 단순하다. 더미변수를 만들 필요 없이 질적 변인을 다룰 수 있다는 것 역시 장점이다. 그러나 트리는 다른 회귀 및 분류 방법에 비해 예측 정확도가 낮다는 치명적인 단점을 가지고 있다. 다음 절에서 배울 배깅, 랜덤 포레스트, 부스팅을 통해 많은 결정 트리를 종합한다면 트리의 예측 성능을 크게 향상시킬 수 있다.
8.2 배깅, 랜덤 포레스트, 부스팅
8.2.1 배깅
배깅(bagging) 혹은 bootstrap aggregation은 통계적 학습 방법의 분산을 줄일 수 있는 방법으로, 특히 결정 트리의 분산을 줄이는 데 유용하게 활용될 수 있다. \(n\)개의 독립적인 관측치 \(Z_1, . . . , Z_n\)이 각각 분산 \(σ^2\)을 가진다고 할 때, 관측치의 평균 \(\bar{Z}\)의 분산은 \(σ^2/n\)으로 계산된다. 즉, 관측치들을 평균 내는 것이 분산을 줄일 수 있다. 따라서 통계적 학습 방법의 분산을 줄임으로써 예측 성능을 높일 수 있는 방법은 모집단에서 많은 훈련 세트를 취하여 각 세트로 별개의 예측 모델을 만들고 그 결과를 평균 내는 것이다. 다시 말해, \(B\)개의 별개의 훈련 세트를 사용해 \(\hat{f}^1(x), \hat{f}^2(x), . . . , \hat{f}^B(x)\)를 계산하고 이것들의 평균을 구하여 아래와 같은 하나의 저분산(low-variance) 통계 학습 모델을 얻는 것이다.
\[\hat{f}_{avg}(x) = \frac 1 B \sum^B_{b=1} \hat{f}^b(x)\]보통은 훈련 세트가 여러 개 존재하지 않기 때문에 하나의 데이터셋에서 반복적으로 샘플을 얻는 부트스트랩을 활용한다. 즉, \(B\)개의 부트스트랩 된 훈련 세트를 생성하여 \(b\)번째 세트에 모델을 훈련시켜 \(\hat{f}^{∗b}(x)\)를 얻고 모든 예측 결과를 평균 내어 아래의 값을 구하는 것이다.
\[\hat{f}_{bag}(x) = \frac 1 B \sum^B_{b=1} \hat{f}^{*b}(x)\]회귀 문제에서 배깅을 사용하기 위해서는 \(B\)개의 부트스트랩 된 훈련 세트에 \(B\)개의 회귀 트리를 만들고 그 결과를 평균 내어 예측에 사용한다. 이때 트리들은 깊게 만들어지고 별도의 가지 치기는 수행하지 않는다. 개별 트리들은 분산이 높지만 편향이 낮으며, 이 트리들을 평균 내면 분산을 낮출 수 있다. 한편, 질적인 결과를 예측해야 하는 분류 문제에 배깅을 적용하는 가장 간단한 접근법은 각 \(B\)개의 트리가 예측한 클래스 중 다수결(majority vote)을 택하는 것이다. 즉, \(B\)개의 예측 결과 중 가장 빈번하게 나타난 클래스가 최종 예측 결과가 된다.
배깅을 활용한 모델에서는 교차 검정 없이도 out-of-bag (OOB) 오류를 통해 테스트 오류를 추정할 수 있다. 평균적으로 배깅에서 각 트리는 관측치의 2/3 정도만을 적합에 사용하는데, 이때 사용되지 않은 나머지 1/3의 관측치를 OOB 관측치라고 부른다. \(i\)번째 관측치가 OOB인 트리들을 활용하여 해당 관측치의 반응변인을 예측할 수 있다. 그러면 \(i\)번째 관측치에 대하여 약 \(B/3\)개의 예측 결과를 얻을 수 있고, 회귀에서는 이것들을 평균 내어, 분류에서는 다수결을 취하여 단일한 예측값을 구할 수 있다. 이런 식으로 \(n\)개의 관측치에 대한 개별 OOB 예측을 구할 수 있고, 여기에서 전반적인 OOB MSE 혹은 분류 오류율을 계산할 수 있다. 이러한 OOB 오류는 대량의 데이터셋에 배깅을 수행하여 교차 검정이 어려울 때 테스트 오류를 편리하게 추정할 수 있는 방법이다.
배깅은 예측 정확도를 높여준다는 장점이 있지만 해석 가능성(interpretability)은 단일한 결정 트리에 비해 떨어진다. 대신 회귀에서는 RSS, 분류에서는 지니 인덱스를 사용해 각 예측변인의 중요도를 구할 수 있다. 예를 들어, 회귀에서는 특정 변수를 기준으로 한 분할로 인해 감소한 RSS의 총량을 모든 \(B\)개의 트리에서 평균 내볼 수 있다. 그 값이 클수록 해당 변수는 중요하다고 할 수 있을 것이다.
8.2.2 랜덤 포레스트
랜덤 포레스트는 트리들의 상관관계를 제거(decorrelate)함으로써 배깅 방법을 좀 더 개선한다. 배깅에서와 같이 부트스트랩 된 훈련 샘플들에 대하여 다수의 결정 트리를 만들되, 각 트리에서 분할을 수행할 때 모든 \(p\)개의 예측변인 중 \(m\)개의 랜덤 샘플 예측변인만을 고려한다. 각 분할에서 새로운 \(m\)개의 예측변인 샘플이 선택되고, 보통 \(m ≈\sqrt{p}\)이다.
배깅에서는 거의 모든 트리가 상단의 분할(top split)에 강력한 예측변인을 사용한다. 결과적으로 모든 트리들이 서로 비슷해지고 예측 결과 역시 높은 상관을 가진다. 이렇듯 높은 상관을 가지는 값들을 평균 내다보면 분산을 크게 줄이기 어려워진다. 랜덤 포레스트에서는 각 분할에서 예측변인 중 일부만 고려하게 하여 나무들의 상관관계를 제거함으로써 이러한 문제를 극복했다. 데이터셋에 서로 상관을 가지는 예측변인이 많다면 랜덤 포레스트에서 \(m\)의 개수를 줄이는 것이 더 도움이 될 것이다.
8.2.3 부스팅
부스팅은 결정 트리의 예측 성능을 높일 수 있는 또 다른 방법이다. 배깅에서는 각 트리가 다른 트리들과는 독립적으로 부트스트랩 데이터셋에 훈련되었다. 이와 달리 부스팅에서는 트리들이 순차적으로(sequentially) 만들어진다. 부스팅은 부트스트랩 샘플링을 활용하지 않고, 각 트리가 원래의 데이터셋의 변형된 형태에 적합된다.
회귀 상황을 생각해보자. 우선 \(\hat{f}(x) = 0\)으로 두고 훈련 세트의 모든 \(i\)에 대한 잔차 \(r_i = y_i\)로 둔다. 그리고 \(b = 1, 2, . . .,B\)에 대하여 다음을 반복한다. (a) 훈련 데이터 \((X, r)\)에 \(d\)번 분할하는(터미널 노드의 개수가 \(d+1\)인) 트리 \(\hat{f^b}\)을 적합시킨다. (b) 아래 식과 같이 새로운 트리의 축소(shrunken) 버전을 더하여 \(\hat{f}\)을 업데이트 한다.
\[\hat{f}(x) ← \hat{f}(x) + λ \hat{f^b}(x)\](c) 아래 식과 같이 잔차를 업데이트 한다.
\[r_i ← r_i − λ \hat{f^b}(x_i)\]반복이 완료되면 배깅에서와 같이 여러 결정 트리를 평균 내어 부스팅의 결과를 낸다.
\[\hat{f}(x) = \sum^B_{b=1} λ \hat{f^b}(x)\]위 과정에서 트리는 결과 \(Y\)가 아니라 현재의 잔차에 적합된다. 그리고 이 새로운 트리를 적합된 함수에 결합하여 잔차를 업데이트하는 것이다. 부스팅에서 각각의 트리는 다소 작지만(터미널 노드의 개수가 적지만), 잔차에 작은 트리를 적합시킴으로써 \(\hat{f}\)을 천천히 개선해 나갈 수 있다.
부스팅에는 세 개의 튜닝 파라미터가 존재한다. 첫째, 트리의 개수 \(B\)이다. \(B\)가 너무 커지면 과적합이 발생할 수 있으므로 교차 검정을 통해 적절한 값을 결정한다. 둘째, 수축(shrinkage) 파라미터 \(λ\)로 부스팅의 학습 속도를 조절한다. 대개 0.01과 0.001 사이의 값을 가지며, 값이 너무 작을 경우 \(B\)의 값이 매우 커져야 좋은 성능을 얻을 수 있다. 셋째, 각 트리에서의 분할의 개수 \(d\)로 부스팅 된 앙상블의 복잡도를 조절한다. 각 트리가 단일 분할로 구성된 \(d = 1\)일 때도 좋은 성능을 보인다. 이 경우 각 항이 하나의 변인만을 가지기 때문에 가법(additive) 모델을 적합시키는 것과 같다. \(d\)개의 분할은 최대 \(d\)개의 변인을 포함하기 때문에 \(d\)는 부스팅 모델의 상호작용 차수(order)를 조절하는 상호작용 깊이(interaction depth)라고 할 수 있다.
부스팅 분류 트리 역시 회귀와 비슷한 방식으로 작동하나, 좀 더 복잡하므로 자세한 과정은 생략한다.