결정 트리 가지치기(Pruning)란? 사전 가지치기와 사후 가지치기 방식 총정리

결정 트리 가지치기(Pruning)란?

가지치기(Pruning)는 결정 트리(decision tree)의 크기를 줄이는 절차입니다. 트리의 크기를 제한하거나 판별력이 거의 없는 영역을 제거함으로써 과적합(overfitting) 위험을 줄일 수 있습니다.

훈련 데이터에는 노이즈나 이상치(outlier)가 포함되어 있어, 트리가 이러한 이상 현상까지 학습하는 가지를 만들 수 있습니다. 가지치기는 바로 이런 가지들을 잘라내어 트리의 일반화 성능(generalization performance)을 높이는 역할을 합니다.

대부분의 가지치기 기법은 통계적 측정값을 활용해 신뢰도가 가장 낮은 가지부터 제거합니다. 그 결과 분류 속도가 빨라지고, 독립적인 테스트 데이터를 올바르게 분류하는 능력 또한 향상됩니다.

트리 가지치기에는 크게 두 가지 접근 방식이 있습니다.

1. 사전 가지치기(Pre-pruning) 방식

사전 가지치기는 말 그대로 트리를 만드는 도중에 구축을 조기에 중단하는 방식입니다. 예를 들어, 특정 노드에서 훈련 샘플을 더 이상 분할하지 않기로 결정하면 해당 노드는 잎(leaf)이 됩니다. 이 잎은 해당 샘플 집단에서 가장 빈도가 높은 클래스나, 샘플들의 확률 분포를 나타내게 됩니다.

트리를 구성할 때는 통계적 유의성(statistical significance), 카이제곱 검정(χ²), 정보 획득량(information gain) 등의 척도를 사용해 분할의 적절성을 평가합니다. 만약 어떤 노드에서 샘플을 분할했을 때 그 결과가 사전에 정해둔 임계값(threshold)보다 낮다면, 해당 집단의 분할을 중단합니다.

다만 이 방식에는 적절한 임계값을 선택하기 어렵다는 문제가 있습니다. 임계값이 너무 높으면 트리가 지나치게 단순해져 성능이 떨어질 수 있고, 반대로 너무 낮으면 충분한 단순화가 이루어지지 않습니다.

2. 사후 가지치기(Post-pruning) 방식

사후 가지치기는 완전히 성장한 트리에서 불필요한 가지를 제거하는 방식입니다. 트리의 노드는 그 가지들을 잘라냄으로써 가지치기되며, 대표적인 예로 비용 복잡도 가지치기(cost complexity pruning) 알고리즘이 있습니다. 가지치기된 노드는 잎이 되고, 이전 가지들 사이에서 가장 많은 클래스로 레이블이 지정됩니다.

이 알고리즘은 트리 내 각 비잎(non-leaf) 노드에 대해 다음과 같이 작동합니다.

• 먼저, 해당 노드의 하위 트리(subtree)를 잘라냈을 때 발생할 예상 오류율(expected error rate)을 계산합니다.
• 다음으로, 가지치기를 하지 않았을 경우의 예상 오류율을 계산합니다. 이때 각 가지의 오류율에 해당 가지를 따라가는 관측치 수를 가중치로 곱해 합산합니다.
• 만약 가지치기를 했을 때 예상 오류율이 더 높아진다면 하위 트리를 그대로 유지하고, 그렇지 않다면 해당 노드를 가지치기합니다.

이렇게 점진적으로 가지치기된 여러 개의 트리 집합을 만든 후, 독립적인 테스트 세트를 사용해 각 트리의 성능을 평가합니다. 최종적으로는 예상 오류 비용(expected error cost)이 가장 낮은 결정 트리를 선택하게 됩니다.

두 방식의 핵심 차이 요약