9장 - 의사결정 트리와 앙상블 기법

9장. 의사결정 트리와 앙상블 기법

의사결정 트리는 비선형 모델의 고전적 사례이며, 앙상블 기법과 결합하면 Kaggle 대회에서 최상위권을 차지하는 강력한 모델이 된다. 이 장에서는 의사결정 트리의 원리부터 배깅, 랜덤 포레스트, 부스팅까지 체계적으로 살펴본다.

9.1 의사결정 트리란 무엇인가

지금까지 다룬 선형 모델(선형 회귀, 로지스틱 회귀, SVM 등)은 입력 공간에 직선이나 초평면으로 결정 경계를 긋는다. 의사결정 트리(decision tree)는 이와 근본적으로 다른 비선형 모델이다.

스키 예제로 직관 잡기

캐나다 출신이라 스키를 좋아한다고 하자. 시간(월)과 위도(latitude)가 주어졌을 때 스키가 가능한지 여부를 예측하는 이진 분류 문제를 생각해 보자.

• x축: 시간 (1월~12월)
• y축: 위도 (+90도 = 북극, -90도 = 남극, 0도 = 적도)

북반구에서는 초겨울~초봄(1~3월)과 늦가을~겨울(11~12월)에 스키가 가능하고, 남반구에서는 5~8월쯤 가능하다. 적도 근처는 항상 불가능하다. 데이터를 시각화하면 양의 예(스키 가능)가 여러 분리된 영역에 흩어져 있다.

이런 데이터에 선형 분류기를 적용하면 적절한 결정 경계를 찾기 어렵다. SVM의 커널 기법으로 고차원 공간에 투영할 수도 있겠지만, 의사결정 트리를 사용하면 매우 자연스러운 방법으로 이 문제를 풀 수 있다.

재귀적 분할 (Recursive Partitioning)

의사결정 트리의 핵심 아이디어는 입력 공간을 탐욕적(greedy)이고 하향식(top-down)인 방식으로 재귀 분할하는 것이다.

트리는 데이터 공간을 상대로 스무고개를 하는 것과 같다. 예를 들어 다음과 같은 질문을 던질 수 있다.

1. "위도가 30도보다 큰가?" -- 이 질문으로 공간이 상단(예)과 하단(아니오)으로 나뉜다.
2. 상단 영역에 대해 다시 묻는다: "월이 3월보다 이전인가?"
3. 이렇게 재귀적으로 질문을 반복하여 공간을 점점 세분화한다.

분할의 형식적 정의

부모 영역 \(R_p\)가 주어졌을 때, 분할 함수 \(S_p\)를 특성 번호 \(j\)와 임곗값 \(t\)로 정의한다.

\[S_p(j, t) = \left( R_1, R_2 \right)\]

여기서

\[R_1 = \{x \in R_p \mid x_j < t\}, \quad R_2 = \{x \in R_p \mid x_j \geq t\}\]

즉, \(j\)번째 특성이 임곗값 \(t\)보다 작은지 여부에 따라 부모 영역을 두 자식 영역으로 나눈다.

9.2 분할 기준: 어떤 질문을 선택할 것인가

분할 함수의 형태를 정의했으니, 이제 어떤 \((j, t)\) 쌍을 선택해야 하는지 결정해야 한다. 이를 위해 영역에 대한 손실 함수를 정의한다.

오분류 손실 (Misclassification Loss)

\(C\)개의 클래스가 있을 때, 영역 \(R\) 안에서 클래스 \(c\)에 속하는 예제의 비율을 \(\hat{p}_c\)라 하자. 오분류 손실은 다음과 같다.

\[L_{\text{misclass}}(R) = 1 - \max_c \hat{p}_c\]

직관은 간단하다. 어떤 영역에서 예측을 해야 한다면 가장 많은 클래스를 선택할 것이고, 나머지 비율이 곧 오류율이 된다.

분할의 목표는 부모의 손실에서 자식들의 손실 합을 뺀 정보 이득을 최대화하는 것이다.

\[\max_{j,t} \left[ L(R_p) - \left( L(R_1) + L(R_2) \right) \right]\]

부모의 손실은 이미 결정되어 있으므로, 이는 자식들의 손실 합을 최소화하는 것과 같다.

오분류 손실의 한계

오분류 손실은 직관적이지만 민감도가 부족하다. 구체적인 예를 들어 보자.

부모 영역에 양성 900개, 음성 100개가 있다고 하자. 오분류 손실은 100이다.

• 분할 A: \(R_1\)에 양성 700개 + 음성 100개, \(R_2\)에 양성 200개 + 음성 0개 -- 손실 합 = 100 + 0 = 100
• 분할 B: \(R_1'\)에 양성 400개 + 음성 100개, \(R_2'\)에 양성 500개 + 음성 0개 -- 손실 합 = 100 + 0 = 100

분할 B가 더 많은 양성 예제를 깨끗하게 분리해냈으므로 직관적으로 더 좋은 분할이다. 하지만 오분류 손실로 보면 두 분할 모두 100으로 동일하며, 심지어 분할하기 전과도 같다. 오분류 손실은 이 차이를 감지하지 못한다.

교차 엔트로피 손실 (Cross-Entropy Loss)

이 문제를 해결하기 위해 정보 이론에서 빌려온 교차 엔트로피 손실을 사용한다.

\[L_{\text{cross}}(R) = -\sum_{c=1}^{C} \hat{p}_c \log_2 \hat{p}_c\]

직관적으로, 어떤 영역의 클래스 분포를 이미 아는 사람에게 특정 예제의 클래스를 알려주기 위해 필요한 비트 수와 같다. 한 클래스가 100%라면 정보를 전달할 필요가 없다(손실 = 0). 클래스 분포가 균등할수록 더 많은 정보를 전달해야 한다(손실이 크다).

기하학적 직관: 왜 교차 엔트로피가 더 좋은가

이진 분류 문제에서 x축을 양성 비율 \(\hat{p}\), y축을 손실로 놓고 그래프를 그려 보자.

교차 엔트로피 손실은 순볼록(strictly concave) 곡선을 그린다. 두 자식 영역의 손실을 곡선 위의 두 점으로 표시하고, 그 두 점을 잇는 직선의 중점(자식들의 평균 손실)을 구하면, 이 중점은 반드시 곡선 아래에 놓인다. 즉, 부모의 손실(곡선 위의 점)보다 자식들의 평균 손실(직선 위의 점)이 항상 작다. 분할이 동일한 점을 선택하지 않는 한, 항상 정보 이득이 발생한다.

반면 오분류 손실은 피라미드(선형) 모양이다. 같은 논리를 적용하면, 두 자식이 같은 쪽에 있을 때 직선과 곡선이 겹쳐 정보 이득이 0이 된다. 이것이 앞서 본 민감도 부족 문제의 근본 원인이다.

불균등 분할의 경우에도 평균 손실은 두 점을 잇는 선분 위의 임의의 점이 되므로, 순볼록 곡선 아래에 놓인다는 성질은 그대로 유지된다.

지니 손실 (Gini Loss)

교차 엔트로피 외에 자주 사용되는 또 다른 기준이 지니 손실이다.

\[L_{\text{Gini}}(R) = \sum_{c=1}^{C} \hat{p}_c (1 - \hat{p}_c)\]

지니 손실의 곡선도 교차 엔트로피와 매우 유사한 순볼록 형태를 띤다. 실제로 의사결정 트리 분할에 성공적으로 사용되는 기준들은 대부분 이러한 순볼록 함수의 형태를 갖는다.

9.3 의사결정 트리의 확장

회귀 트리 (Regression Tree)

지금까지는 분류 문제를 다루었지만, 의사결정 트리는 회귀 문제에도 그대로 적용할 수 있다. 이를 회귀 트리라 부른다.

스키 예제에서 "스키 가능 여부" 대신 "예상 적설량(인치)"을 예측한다고 하자. 공간을 분할하는 방식은 동일하되, 리프 노드에서 다수결 대신 해당 영역에 속하는 값들의 평균을 예측한다.

영역 \(R_m\)에서의 예측값:

\[\hat{y}_m = \frac{1}{|R_m|} \sum_{i \in R_m} y^{(i)}\]

이때 사용하는 손실 함수는 제곱 손실이다.

\[L_{\text{squared}}(R_m) = \frac{1}{|R_m|} \sum_{i \in R_m} (y^{(i)} - \hat{y}_m)^2\]

범주형 변수 (Categorical Variables)

의사결정 트리의 또 다른 장점은 범주형 변수를 자연스럽게 처리할 수 있다는 것이다. 위도를 연속값 대신 "북반구", "적도", "남반구"라는 세 범주로 표현한다면, "위치가 북반구인가?"와 같은 질문으로 분할할 수 있다.

다만 주의할 점이 있다. \(q\)개의 범주가 있으면 가능한 부분집합이 \(2^q\)개이므로, 범주가 많아지면 탐색이 급격히 어려워진다. 이진 분류의 특수한 경우에는 각 범주를 양성 비율로 정렬한 뒤 선형 탐색하면 최적 분할을 효율적으로 찾을 수 있다.

9.4 정규화: 과적합 방지

의사결정 트리를 제한 없이 끝까지 성장시키면, 극단적으로는 각 데이터 포인트마다 별도의 영역을 만들게 된다. 이는 명백한 과적합이다. 의사결정 트리는 본질적으로 높은 분산(high variance) 모델이므로 정규화가 필요하다.

일반적으로 사용되는 휴리스틱은 다음과 같다.

네 번째 방법(최소 손실 감소)은 매력적으로 보이지만, 실제로는 좋은 선택이 아닌 경우가 많다. 변수 간 상호작용이 있을 때, 첫 번째 질문 자체는 큰 이득을 주지 않더라도 후속 질문과 결합하면 큰 이득을 줄 수 있기 때문이다. 스키 예제에서 위도 질문만으로는 양성과 음성이 크게 분리되지 않지만, 위도 질문 이후 월(month) 질문을 더하면 영역이 깔끔하게 나뉜다. 최소 손실 감소 기준을 적용하면 이런 유의미한 분할을 놓칠 수 있다.

더 좋은 접근법은 **가지치기(pruning)**이다. 트리를 완전히 성장시킨 후, 검증 세트에서의 오분류율을 기준으로 불필요한 리프를 역방향으로 제거한다.

9.5 의사결정 트리의 실행 시간

다음과 같은 기호를 정의하자.

테스트 시간: 루트에서 리프까지 질문을 따라가므로 \(O(d)\)이다. 트리가 균형 잡힌 경우 \(d \leq \log n\)이므로 매우 빠르다.

훈련 시간: 각 데이터 포인트는 최대 \(O(d)\)개의 노드에 속하고, 각 노드에서의 처리 비용은 \(O(f)\)이다. 데이터 포인트가 \(n\)개이므로, 총 훈련 시간은 다음과 같다.

\[O(n \cdot f \cdot d)\]

\(n \times f\)는 데이터 행렬의 크기이고, \(d\)는 보통 \(\log n\) 이하이므로, 훈련 시간은 놀라울 정도로 빠르다.

9.6 의사결정 트리의 장단점

장점

• 설명이 쉽다: 비전문가에게도 "스무고개"라는 비유로 직관적으로 설명할 수 있다.
• 해석 가능하다: 트리를 시각화하면 모델이 어떤 기준으로 판단하는지 한눈에 파악할 수 있다.
• 범주형 변수를 자연스럽게 처리할 수 있다.
• 훈련과 예측이 빠르다.

단점

• 높은 분산: 과적합에 취약하다.
• 가법적 구조에 약하다: \(x_1 = x_2\)와 같은 대각선 결정 경계를 표현하려면 수많은 축 정렬 분할이 필요하다. 로지스틱 회귀라면 한 번에 해결할 문제를 의사결정 트리는 계단식으로 근사해야 한다.
• 예측 정확도가 낮다: 위 두 가지 문제로 인해 단독으로 사용하면 다른 알고리즘에 비해 성능이 떨어지는 경우가 많다.

의사결정 트리를 이렇게 깊이 다루는 이유는 앙상블 기법과 결합하면 이 단점들을 극복할 수 있기 때문이다. 실제로 Kaggle 등 데이터 과학 경진대회에서 최상위 성적을 내는 모델 중 상당수가 의사결정 트리 앙상블이다.

9.7 앙상블 기법: 왜 효과가 있는가

앙상블의 핵심 직관은 기초 통계에서 찾을 수 있다.

독립 확률 변수의 경우

\(X_1, X_2, \ldots, X_N\)이 **독립 동일 분포(IID)**인 확률 변수이고, 각각의 분산이 \(\sigma^2\)일 때, 평균의 분산은 다음과 같다.

\[\text{Var}\left(\frac{1}{N}\sum_{i=1}^{N} X_i\right) = \frac{\sigma^2}{N}\]

독립적인 모델을 \(N\)개 평균하면, 분산이 \(N\)분의 1로 줄어든다.

상관된 확률 변수의 경우

실제로는 모델들이 완전히 독립적이지 않다. 임의의 두 변수 간 상관계수가 \(\rho\)인 동일 분포 확률 변수들의 평균 분산은 다음과 같다.

\[\text{Var}\left(\frac{1}{N}\sum_{i=1}^{N} X_i\right) = \rho\sigma^2 + \frac{1 - \rho}{N}\sigma^2\]

이 공식에서 두 가지 전략이 도출된다.

1. *\(N\)을 늘린다*: 모델 수를 늘리면 두 번째 항 \(\frac{1-\rho}{N}\sigma^2\)이 줄어든다.
2. *\(\rho\)를 줄인다*: 모델 간 상관을 낮추면 첫 번째 항 \(\rho\sigma^2\)이 줄어든다.

앙상블의 네 가지 접근법

처음 두 접근법은 모델 간 상관을 가장 잘 줄여 주지만, 현실적으로는 배깅과 부스팅이 훨씬 실용적이다.

9.8 배깅 (Bootstrap Aggregation)

배깅(bagging)은 **부트스트랩 집계(Bootstrap Aggregation)**의 줄임말이다.

부트스트랩이란

통계학에서 부트스트랩은 추정치의 불확실성을 측정하는 기법이다. 핵심 아이디어는 다음과 같다.

1. 실제 모집단 \(P\)에서 훈련 세트 \(S\)를 추출했다.
2. 이상적으로는 \(P\)에서 여러 훈련 세트 \(S_1, S_2, \ldots\)를 독립적으로 추출하고 싶지만, 그럴 여유가 없다.
3. 대신 \(S\) 자체를 모집단으로 간주하고, \(S\)에서 **복원 추출(sampling with replacement)**로 크기 \(n\)인 새 표본 \(Z\)를 여러 개 만든다.

이렇게 만든 \(Z_1, Z_2, \ldots\)를 부트스트랩 표본이라 한다. 각 부트스트랩 표본에는 원래 훈련 세트의 약 3분의 2가 포함된다(일부 예제는 중복 선택되고, 일부는 빠지므로).

배깅의 절차

1. 부트스트랩 표본 \(Z_1, Z_2, \ldots, Z_M\)을 생성한다.
2. 각 \(Z_m\)에서 모델 \(G_m\)을 훈련한다.
3. 최종 예측은 개별 모델들의 평균(회귀) 또는 다수결(분류)로 결정한다.

\[G(x) = \frac{1}{M}\sum_{m=1}^{M} G_m(x)\]

편향-분산 관점에서의 분석

상관된 변수의 분산 공식을 다시 보자.

\[\text{Var} = \rho\sigma^2 + \frac{1-\rho}{M}\sigma^2\]

• 부트스트랩은 \(\rho\)를 낮춘다: 서로 다른 부트스트랩 표본으로 훈련하므로 모델 간 상관이 줄어든다.
• *\(M\)을 늘리면 두 번째 항이 줄어든다*: 부트스트랩 표본 수를 늘리는 것은 과적합을 유발하지 않는다. 단지 분산의 두 번째 항을 줄일 뿐이므로, 일반적으로 성능이 향상되기만 한다.
• *\(\rho\)에는 하한이 있다*: 부트스트랩 표본들은 모두 같은 \(S\)에서 추출되므로 여전히 상당한 상관을 갖는다. \(\rho\)를 0까지 줄일 수는 없다.

배깅의 대가는 편향이 약간 증가한다는 것이다. 각 부트스트랩 표본은 원래 훈련 세트의 약 3분의 2만 포함하므로, 개별 모델이 전체 데이터를 보지 못해 약간 덜 정교해진다. 그러나 일반적으로 분산 감소 효과가 편향 증가보다 훨씬 크다.

실무에서는 오류가 더 이상 감소하지 않을 때까지 \(M\)을 늘린다.

9.9 랜덤 포레스트 (Random Forest)

의사결정 트리는 높은 분산, 낮은 편향 모델이다. 이는 배깅에 이상적인 조합이다. 배깅이 분산을 줄여 주는 기법이고, 의사결정 트리의 주요 문제가 바로 높은 분산이기 때문이다.

랜덤 포레스트는 의사결정 트리에 배깅을 적용하되, 한 가지 핵심적인 무작위화를 추가한 것이다.

특성 부분 추출 (Feature Subsampling)

일반 배깅에서는 부트스트랩 표본만 달라지므로, 만약 하나의 매우 강력한 예측 변수가 있다면 모든 트리가 그 변수를 첫 번째 분할로 선택할 것이다. 이렇게 되면 모델 간 상관 \(\rho\)가 여전히 높게 유지된다.

랜덤 포레스트는 각 분할마다 전체 특성 중 무작위로 일부만 후보로 고려한다. 예를 들어 스키 예제에서, 첫 번째 분할에서는 위도만 볼 수 있고, 두 번째 분할에서는 월만 볼 수 있는 식이다.

이 방법이 효과적인 이유:

• 강력한 예측 변수가 있더라도 모든 트리가 같은 변수를 첫 분할로 사용하지 않게 되어 \(\rho\)가 더 감소한다.
• 개별 트리의 성능은 약간 떨어질 수 있지만, 앙상블 전체의 분산이 크게 줄어들어 최종 성능이 향상된다.

9.10 부스팅 (Boosting)

배깅이 분산을 줄이는 전략이라면, 부스팅은 편향을 줄이는 전략이다.

핵심 아이디어

배깅이 여러 모델의 예측을 평균하는 것이었다면, 부스팅은 모델을 순차적으로 추가한다. 이전 모델이 틀린 예제에 더 큰 가중치를 부여하여, 다음 모델이 그 실수를 수정하도록 유도한다.

의사결정 스텀프와 부스팅

부스팅에서는 보통 **의사결정 스텀프(decision stump)**를 기본 모델로 사용한다. 스텀프는 깊이가 1인 트리, 즉 질문을 하나만 하는 트리다. 스텀프를 사용하는 이유는 의도적으로 높은 편향, 낮은 분산 모델을 만들기 위해서다. 부스팅은 편향을 줄여 주는 기법이므로, 편향이 높은 모델과 결합할 때 가장 효과적이다.

부스팅의 작동 과정

구체적인 예를 들어 보자. \(x_1\), \(x_2\) 두 특성이 있는 이진 분류 문제에서 양성(+)과 음성(-) 데이터가 섞여 있다.

1. 1단계: 첫 번째 스텀프가 하나의 결정 경계를 긋는다. 일부 예제를 올바르게 분류하지만, 실수도 있다.
2. 재가중: 틀린 예제의 가중치를 키우고, 맞힌 예제의 가중치를 줄인다.
3. 2단계: 두 번째 스텀프가 재가중된 데이터에서 새로운 결정 경계를 긋는다. 이전에 틀렸던 예제를 맞히는 데 집중한다.
4. 이 과정을 반복한다.

AdaBoost 알고리즘

각 분류기 \(G_m\)에 가중치 \(\alpha_m\)을 부여한다. 가중치는 해당 분류기의 성능에 비례한다.

\[\alpha_m = \log\frac{1 - \text{err}_m}{\text{err}_m}\]

여기서 \(\text{err}_m\)은 \(m\)번째 분류기의 가중 오류율이다. 정확한 분류기일수록 \(\alpha_m\)이 크고, 부정확한 분류기일수록 작다.

최종 앙상블 분류기는 다음과 같다.

\[G(x) = \text{sign}\left(\sum_{m=1}^{M} \alpha_m G_m(x)\right)\]

각 \(G_m\)은 재가중된 훈련 세트에서 학습된다. 이전 단계에서 틀린 예제의 가중치가 커지므로, 새 분류기는 자연스럽게 이전의 실수를 보완하는 방향으로 학습된다.

그래디언트 부스팅과 XGBoost

AdaBoost와 유사한 원리로 **그래디언트 부스팅 머신(Gradient Boosting Machine)**과 XGBoost 등의 알고리즘이 파생되었다. 이들은 틀린 예제에 가중치를 재부여하고, 가법적(additive) 방식으로 모델을 순차적으로 추가한다는 동일한 핵심 아이디어를 공유한다.

9.11 배깅 vs 부스팅 비교

핵심 정리

이전 장: 8장 - 데이터 분할, 모델과 교차 검증 다음 장: 10장 - 신경망 입문