패턴 인식 (Pattern Recognition)에서 아주 중요한
분류(Classification) 및 회귀(Regression) 모델 중 하나가
바로 결정 트리(Decision Tree)다.
이 글에서는
- 결정 트리의 기본 구성
- impurity
- split 기준
- pruning(가지치기)
까지 전부 정리해보고자 한다.
1. 결정 트리란?
XOR 문제와 결정 트리
XOR 문제는 선형 분리 불가능한 대표 예시다.
‼️ Linear Regression으로는 선형 분리가 어려움
👉 Decision Tree는 조건 분기를 통해 비선형 문제도 해결 가능
결정 트리
- 데이터를 분할(split)하면서 나무 구조로 학습하는 모델
- 각 노드는 데이터를 분기하는 기준(feature, threshold)을 갖고 있음
- 최종 리프 노드는 예측 값(class 또는 수치)을 가짐
2. 트리 생성 방법
분할 기준 (Split Rule)
- Split Variable: 어떤 variable로 나눌지
- Split Value: 어느 값을 기준으로 나눌지
좋은 분할이란?
👉 “불순도(Impurity)”가 감소해야 한다!
- 순수(pure): 한 클래스가 대부분
- 불순(impure): 클래스가 섞여 있음
3. 불순도 지표 (Impurity Measures)
Misclassification Error (분류 오류율)
- 가장 많은 클래스를 기준으로 했을 때 틀리는 비율
Gini Index
- 대표적인 impurity 측정 지표
- 수식: Gini(p) = 1 - Σ pᵢ²
- binary일 때 최대값은 0.5 (50:50으로 섞여있을 때)
Entropy
- 정보 이론에서 사용하는 지표
- 수식: Entropy(p) = -Σ pᵢ log₂(pᵢ)
- binary일 때 최대값은 1 (50:50)
4. 분할 기준: Information Gain
👉 부모 노드의 impurity와 자식 노드들의 impurity 차이로 정의됨
- 수식:
IG = Impurity(parent) - weighted average of Impurity(children) - impurity는 위에서 설명한 Gini, Entropy 등을 사용 가능
📌 정보 이득이 클수록 좋은 분할 기준!
문제점: 너무 잘 나누는 경우? (Over-split)
‼️ 이진 분류가 아닌 multiple split 경우에는 문제가 생긴다.
예: 이름(name)으로 split하면 거의 unique → 100% 정확하지만 일반화 불가
👉 해결: Information Gain Ratio
Information Gain을 분할 정보량(Split Info)으로 나눔
→ 다중 분할을 벌점(penalty) 처리
5. 회귀 문제에서의 트리 분할
분류가 아닌 수치 예측을 하고 싶을 때
t-static
두 집단 사이의 평균이 얼마나 차이 있는지
variance
자식 노드들의 분산(variance)을 최소화하는 방향으로 분할
→ 분산이 작을수록 예측 값들이 비슷 → 더 “순수”한 노드
6. 트리의 성장을 막는 방법 (Stopping Rule)
너무 깊은 트리는 오버피팅의 원인!
→ ‼️ 성능은 높지만 일반화 성능은 낮음
멈추는 조건 예시
- 트리의 깊이가 설정한 threshold 초과
- 노드 안 데이터 수가 설정한 threshold보다 적음
- 더 이상 impurity가 줄지 않음
7. 가지치기 (Pruning)
트리를 만든 후 불필요한 부분을 잘라내는 과정
Reduced Error Pruning
- 리프 노드부터 위로 올라가며 서브트리를 제거
- Validation set에서 성능 향상되면 제거 유지
Cost Complexity Pruning
- 다음을 최소화:
Cost = Error + α × (# 리프 노드 수)
→ α가 클수록 더 많이 자름
→ 정규화(L2 penalty)와 유사
Rule Post Pruning
- 트리를 규칙 집합(rule set)으로 변환
- 각 규칙에서 불필요한 조건을 제거
결론
정리
- Decision Tree는 해석력 + 성능의 균형을 맞추기 좋은 모델
- impurity(Gini, Entropy)를 기준으로 분할
- overfitting 방지를 위해 stopping rule / pruning 필수
- 분류도 회귀도 가능!
다음 글에서는?
모델 평가와 검증 방법
