면접 답변
가지치기에는 트리가 자라는 도중에 멈추는 사전 가지치기와, 충분히 키운 뒤 불필요한 가지를 잘라내는 사후 가지치기가 있습니다. 목적은 학습 데이터의 노이즈까지 외운 깊은 트리의 분산을 줄여 일반화 성능을 높이는 것입니다. 사전 가지치기는 최대 깊이, 잎의 최소 표본 수, 최소 불순도 감소량 같은 조건을 쓰며 빠르지만, 지금 당장 이득이 작은 분할 뒤에 있는 좋은 분할을 놓칠 수 있습니다. 사후 가지치기의 대표적인 방법은 CART의 비용-복잡도 가지치기입니다. 잎 개수에 페널티 알파를 주고, 잎을 줄일 때 오차가 가장 적게 늘어나는 가지부터 차례로 잘라 후보 트리를 만든 뒤, 교차 검증으로 가장 좋은 알파를 고릅니다. 예를 들어 scikit-learn에서는
ccp_alpha파라미터로 이 방법을 사용할 수 있습니다.
자세한 설명
사전 가지치기와 사후 가지치기
| 사전 가지치기(pre-pruning) | 사후 가지치기(post-pruning) | |
|---|---|---|
| 시점 | 트리를 키우는 동안 | 트리를 충분히 키운 뒤 |
| 방법 | 최대 깊이, 최소 표본 수, 최소 불순도 감소 | 서브트리를 잎으로 교체 |
| 장점 | 계산이 빠름 | 분할의 결과를 끝까지 본 뒤 판단 |
| 단점 | 근시안적으로 멈출 수 있음 | 전체 트리를 키우는 계산이 필요 |
사전 가지치기의 약점은 XOR에서 잘 드러난다. 균형 잡힌 XOR 데이터에서는 첫 분할의 불순도 감소가 0에 가깝지만, 두 번째 분할에서 완벽히 분류된다. “최소 불순도 감소” 조건이 있으면 첫 단계에서 멈춰 버리지만, 사후 가지치기는 전체 트리를 본 뒤 판단하므로 이 구조를 남길 수 있다.
축소 오차 가지치기
축소 오차 가지치기(reduced error pruning)는 가장 직관적인 사후 방법이다.
- 데이터를 학습용과 가지치기용 검증 데이터로 나눈다.
- 트리를 충분히 키운 뒤, 아래쪽 내부 노드부터 그 서브트리를 잎으로 바꿔 본다. 잎의 예측은 그 노드의 다수 클래스(회귀는 평균)이다.
- 검증 오차가 늘지 않으면 교체를 확정한다.
단순하지만 학습에 쓸 데이터 일부를 떼어 두어야 한다.
비용-복잡도 가지치기
CART의 비용-복잡도 가지치기(cost-complexity pruning)는 트리 \(T\)를 다음 기준으로 평가한다.
\[R_\alpha(T) = R(T) + \alpha \lvert \tilde{T} \rvert\]\(R(T)\)는 잎들의 학습 오차 합(분류라면 전체 표본 대비 오분류 비율 등), \(\lvert \tilde{T} \rvert\)는 잎 개수, \(\alpha \ge 0\)은 잎 하나에 매기는 페널티이다. \(\alpha = 0\)이면 전체 트리가, \(\alpha\)가 커질수록 작은 트리가 최적이 된다.
내부 노드 \(t\)를 잎으로 만들었을 때의 오차를 \(R(t)\), \(t\) 아래 서브트리의 오차를 \(R(T_t)\)라 하면, 둘의 비용이 같아지는 \(\alpha\)는 다음과 같다.
\[\alpha(t) = \frac{R(t) - R(T_t)}{\lvert \tilde{T}_t \rvert - 1}\]이 값은 “잎 하나를 줄일 때 늘어나는 오차”이다. 이 값이 가장 작은 노드, 즉 가장 약한 연결(weakest link)부터 잘라 나가면 점점 작아지는 트리열이 나온다. 그중 교차 검증 오차가 가장 좋은 \(\alpha\)의 트리를 고른다.
계산 예
표본이 100개이고, 서로 겹치지 않는 내부 노드 A, B가 있다고 하자.
| 노드 | 잎으로 만들면 오분류 | 서브트리 오분류 | 서브트리 잎 수 | \(\alpha(t)\) |
|---|---|---|---|---|
| A | 20개 | 8개 | 3 | \((0.20 - 0.08)/2 = 0.06\) |
| B | 10개 | 7개 | 2 | \((0.10 - 0.07)/1 = 0.03\) |
B의 \(\alpha\)가 더 작으므로 B를 먼저 자른다. B의 가지는 오차를 줄이는 효과에 비해 복잡도를 많이 쓰고 있기 때문이다.
C4.5의 비관적 가지치기
C4.5는 별도 검증 데이터 없이 학습 오차를 통계적으로 비관적인 값으로 보정해 가지치기 여부를 판단한다. 데이터를 나누지 않아도 되는 장점이 있지만, 가정에 기반한 휴리스틱이다.
관련 개념
- 과적합: 가지치기는 트리의 분산을 줄여 과적합을 막는 정규화이다. Q-13과 Q-28에 연결된다.
- 의사결정나무의 장단점: 해석이 쉽지만 불안정한 점이 가지치기와 앙상블이 필요한 이유이다. Q-8을 참고한다.
- 교차 검증: \(\alpha\)와 같은 복잡도 파라미터를 고르는 기본 방법이다. Machine Learning 11에서 이어진다.
- 트리 앙상블: 랜덤 포레스트는 깊은 트리를 평균해 분산을 낮추므로 보통 개별 트리를 강하게 가지치기하지 않고, 부스팅은 깊이를 얕게 제한한 트리를 쌓는 경우가 많다.
꼬리 질문
Q. 사전 가지치기와 사후 가지치기 중 무엇을 먼저 시도하나요?
속도가 중요하거나 대규모 데이터라면 깊이와 잎 크기 제한을 먼저 조정합니다. 해석할 단일 트리를 만드는 것이라면 ccp_alpha처럼 사후 가지치기도 함께 비교합니다.
Q. 가지치기를 너무 많이 하면 어떻게 되나요? 트리가 데이터의 구조를 충분히 표현하지 못해 편향이 커지고 과소적합이 생깁니다. 극단적으로는 뿌리 노드 하나만 남아 다수 클래스만 예측합니다.
Q. 오분류율 대신 지니 불순도로 가지치기해도 되나요? 가능합니다. 다만 CART의 고전적 설명은 분할 탐색에 불순도를, 분류 트리의 가지치기에 오분류 비용을 주로 쓰며, 구현마다 기준이 다를 수 있습니다. scikit-learn의 경우 분할에 사용한 불순도 기준으로 비용을 계산합니다.