의사결정나무의 분할과 가지치기

핵심 요약

의사결정나무는 설명변수의 조건으로 데이터를 반복 분할해 범주형 또는 연속형 목표를 예측하는 지도학습 알고리즘이다. 분류나무는 지니 불순도·엔트로피 등의 가중 감소량, 회귀나무는 제곱오차 등의 감소량을 기준으로 후보 분할을 비교한다.

각 노드에서 당장 가장 좋은 분할을 고르는 탐욕적 방식이므로 전체 나무의 전역 최적해를 보장하지 않는다. 너무 깊은 나무는 훈련 자료의 잡음까지 학습하기 쉽다. 최대 깊이·최소 잎 표본 수 같은 사전 제약과 비용-복잡도 사후 가지치기를 교차검증으로 정하고, 마지막 테스트 자료는 조정이 끝난 뒤 한 번 평가한다.

학습 목표

• 분류나무와 회귀나무의 입력·출력·잎 예측값을 구분한다.
• 지니·엔트로피와 표본 수로 가중한 불순도 감소를 계산한다.
• 회귀나무의 잎 평균과 제곱오차 감소를 계산한다.
• 사전 정지와 비용-복잡도 사후 가지치기의 차이를 설명한다.
• 불안정성·불균형·고카디널리티 편향·데이터 누수를 진단한다.

1. 나무의 구조와 예측

• 분류나무: 잎의 클래스 빈도·비율로 예측 클래스 또는 클래스 확률을 정한다.
• 회귀나무: 제곱오차 기준에서는 잎에 속한 목표값의 평균을 예측값으로 사용한다.

아래 예시는 한 관측치가 조건을 따라 잎에 도달하는 구조를 보여준다. 잎의 4/5는 해당 잎에서 이탈이 5명 중 4명이라는 뜻이다.

flowchart TD
    A["전체 고객 10명"] --> B{"사용기간 ≤ 12개월?"}
    B -->|예| C["잎: 이탈 4/5"]
    B -->|아니오| D{"문의 횟수 ≥ 3회?"}
    D -->|예| E["잎: 이탈 3/4"]
    D -->|아니오| F["잎: 이탈 0/1"]

단일 나무의 경로는 사용기간≤12개월 같은 국소 규칙으로 읽기 쉽다. 그러나 나무가 깊어지면 규칙 수가 많아지고 작은 데이터 변화에도 상위 분할이 달라질 수 있어 해석 안정성이 낮아진다. 잎의 비율은 확률 추정치로 쓸 수 있지만 표본이 작은 잎에서는 값이 극단적이고 보정이 나쁠 수 있다.

2. 재귀 분할과 탐욕적 선택

현재 노드 t에서 후보 변수와 분할점을 모두 비교한 뒤 불순도 또는 오차 감소가 가장 큰 후보를 선택한다. 자식 노드에서 같은 절차를 반복한다.

훈련 노드 → 후보 분할 생성 → 각 후보의 가중 감소량 계산
          → 현재 최선 분할 선택 → 자식 노드에서 반복 → 정지·가지치기

수치형 변수의 후보는 보통 정렬된 서로 다른 값 사이의 임곗값에서 만든다. 범주형 변수는 범주 집합 분할, 순서화 또는 원-핫 인코딩 등 구현에 따라 처리법이 다르다. 결측값·학습 때 없던 범주의 처리도 라이브러리마다 다르므로 사용 구현을 확인한다.

이 선택은 현재 노드에서의 국소 최적이다. 첫 분할을 나중에 되돌려 모든 가능한 나무를 전수 탐색하지 않으므로 전체적으로 가장 좋은 나무가 보장되지는 않는다. 감소량이 같은 후보의 처리도 구현과 설정에 따라 달라질 수 있다.

3. 분류나무의 불순도

노드 t의 클래스 k 비율을 p(k|t)라 하면 대표 기준은 다음과 같다.

Gini(t) = 1 - Σ p(k|t)²
Entropy(t) = -Σ p(k|t) log₂ p(k|t)

p=0인 엔트로피 항은 극한값 0 log 0=0으로 처리한다.

순수 노드는 한 클래스의 비율이 1이므로 두 기준 모두 0이다. 좋은 분할은 부모보다 표본 수로 가중한 자식 불순도를 작게 만든다.

ΔI = I(parent) - [nL/n × I(left) + nR/n × I(right)]
n = nL + nR

지니 감소 계산

부모 노드에 양성 6개, 음성 4개가 있고, 분할 뒤 왼쪽은 (양성 5, 음성 0), 오른쪽은 (양성 1, 음성 4)라고 하자.

따라서 가중 자식 Gini는 0.16, 감소량은 0.48-0.16=0.32다. 자식 크기가 다르면 단순 평균이 아니라 반드시 nL/n, nR/n으로 가중한다.

정보이득은 엔트로피의 같은 형태의 감소량이다. 범주 수나 후보 분할점이 많은 변수는 우연히 큰 감소를 만들 기회가 많다. 정보이득을 쓰는 알고리즘에서는 이를 완화하기 위해 분할정보로 나눈 이득비(gain ratio)를 사용하기도 한다.

4. 회귀나무의 분할 기준

제곱오차 기준의 잎 예측값은 잎의 평균이며, 후보 분할은 부모의 제곱오차합에서 자식들의 제곱오차합을 뺀 값으로 비교할 수 있다.

SSE(t) = Σ(yi - ȳt)²
ΔSSE = SSE(parent) - [SSE(left) + SSE(right)]

목표값이 [2,3,8,9]인 부모를 [2,3]과 [8,9]로 나누는 예를 보자.

자식 SSE 합은 1, 감소량은 37-1=36이다. 구현에 따라 SSE, MSE 또는 분산 감소로 표현할 수 있으므로 합과 평균의 스케일 차이를 확인한다. 절대오차 기준을 지원하는 구현에서는 잎 예측값이 중앙값이 될 수 있다.

5. 사전 정지와 사후 가지치기

5.1 사전 정지

나무를 자라는 중에 복잡도를 제한한다.

루트 깊이를 0으로 세는지 1로 세는지는 구현에 따라 다르다. min_samples_split은 부모 노드의 분할 자격, min_samples_leaf는 분할 결과 자식의 최소 크기라는 차이를 구분한다.

5.2 비용-복잡도 사후 가지치기

먼저 큰 나무를 만든 뒤, 오차 개선보다 복잡도 비용이 큰 가지를 제거한다. 대표 목적함수는 다음과 같다.

Rα(T) = R(T) + α|L(T)|,    α ≥ 0

R(T)는 잎별 훈련 오차의 합, |L(T)|는 잎 수다. α=0이면 복잡도 벌점이 없고, α가 커질수록 일반적으로 더 작은 부분나무가 선택된다. 약한 연결고리 가지치기는 α가 변할 때의 중첩된 부분나무 후보를 만들고, 그중 α를 교차검증으로 고른다.

가지치기는 분산을 낮추는 대신 편향을 높일 수 있다. 따라서 항상 성능을 높이는 규칙이 아니며, 훈련 정확도가 아니라 검증 성능과 규칙 안정성으로 강도를 선택한다. 테스트 자료를 보며 α를 고르면 테스트 누수다.

6. 편향-분산과 평가 절차

분류 불균형에서는 정확도만 보지 않고 정밀도·재현율·F1·PR-AUC와 오류 비용을 확인한다. 클래스 가중치는 분할 점수와 잎의 예측 비율을 바꿀 수 있다. 가중치·재표본추출과 하이퍼파라미터 선택은 훈련 폴드 안에서 수행하고, 검증·테스트는 원래 분포를 유지한다.

회귀나무는 MAE·RMSE 등으로 평가한다. 시간·집단 구조가 있으면 무작위 분할 대신 그 구조에 맞는 검증을 사용한다. 훈련·검증·테스트 전체에서 목표값으로 파생된 특성이나 미래 정보를 제거한다.

7. 변수 중요도와 해석 주의

불순도 기반 중요도는 한 변수가 만든 가중 불순도 감소를 합산한다. 빠르지만 후보 분할점이나 범주 수가 많은 변수에 유리할 수 있다. 검증 자료의 순열 중요도로 보완할 수 있으나, 상관된 변수끼리는 한 변수를 섞어도 다른 변수가 정보를 대신해 중요도가 낮게 보일 수 있다.

중요도는 예측 기여의 단서이지 인과효과가 아니다. 단일 나무의 상위 분할도 표본이 바뀌면 달라질 수 있으므로 부트스트랩·교차검증 반복에서 선택 빈도와 성능 안정성을 함께 본다.

수치형 변수는 순서 기반 임곗값으로 나누므로 보통 표준화가 필요 없다. 단조 변환은 값의 순서를 유지하지만, 범주 인코딩·결측 처리 방식은 가능한 분할 구조를 바꿀 수 있다. 모든 전처리는 훈련 폴드에서 학습한다.

8. 대표 알고리즘 구분

시험에서는 알고리즘 이름보다 “분류·회귀 가능 여부, 분할 기준, 이진·다지 분할, 가지치기 방식”의 조합을 확인한다.

9. 사례 적용

상황: 통신사는 고객 이탈 여부를 예측하고 상담사가 이해할 수 있는 규칙을 원한다. 기존 나무는 훈련 정확도 99%, 과거 홀드아웃 정확도 76%, 깊이 24이며 일부 잎에는 한 명만 있다.

판단 과정:

1. 큰 성능 차이와 단일 표본 잎에서 과대적합을 의심한다.
2. 시간 순서와 이탈 정의를 고정하고 미래 정보를 제거한 훈련·검증·테스트를 다시 구성한다.
3. 훈련 폴드 안에서 max_depth, min_samples_leaf, 클래스 가중치와 α를 교차검증한다.
4. 정확도와 함께 이탈 재현율·정밀도·PR-AUC, 오류 비용과 잎별 표본 수를 비교한다.
5. 반복 폴드에서 상위 규칙과 변수 중요도의 안정성을 확인한다.
6. 모든 선택을 고정한 뒤 미래 테스트 자료에서 한 번 평가한다.

결론: 복잡도를 낮추되 검증 성능과 규칙 안정성을 함께 보며, 해석 가능한 단일 나무가 성능 요건을 충족하지 못하면 랜덤포레스트·그래디언트 부스팅과의 성능-해석성 절충을 비교한다.

예시의 부모 지니는 0.500이고 두 자식은 각각 0.219이므로 가중 불순도 감소는 0.281이다. 분할은 자식 노드를 더 순수하게 만들지만 계속 반복하면 훈련 자료에 과대적합한다.

학습 정확도가 가장 높은 깊이가 아니라 검증 성능과 안정성이 좋은 복잡도를 고른다.

시험 판단 포인트

• 의사결정나무는 분류와 회귀에 사용하는 지도학습 알고리즘이다.
• 분류 분할은 가중 지니·엔트로피 감소, 회귀 분할은 제곱오차 감소 등을 사용할 수 있다.
• 지니의 다중 클래스 최댓값은 1-1/K, 엔트로피의 밑 2 최댓값은 log₂K다.
• 자식 불순도는 표본 수로 가중하며 단순 평균하지 않는다.
• 재귀 분할은 국소 최선을 고르는 탐욕적 탐색으로 전역 최적 나무를 보장하지 않는다.
• min_samples_split과 min_samples_leaf의 적용 대상을 구분한다.
• α가 커질수록 비용-복잡도 벌점이 강해져 일반적으로 나무가 단순해진다.
• 가지치기 강도와 모든 전처리는 훈련·검증에서 선택하고 테스트로 조정하지 않는다.
• 불순도 중요도는 많은 분할 후보를 가진 변수에 편향될 수 있으며 인과효과가 아니다.

자주 틀리는 부분

• 지니 불순도가 클수록 순수하다고 해석하지 않는다.
• 자식 노드 불순도를 표본 수 가중 없이 평균하지 않는다.
• 분류 불순도와 회귀 제곱오차 기준을 혼동하지 않는다.
• 훈련 정확도가 가장 높은 나무를 자동으로 최종 선택하지 않는다.
• 가지치기가 항상 검증 성능을 높인다고 단정하지 않는다.
• 표준화가 불필요하다는 말을 범주 인코딩·결측 처리도 불필요하다는 뜻으로 확대하지 않는다.
• 변수 중요도가 높다고 인과효과가 크다고 해석하지 않는다.