결정 트리: 지니 불순도 · 정보 이득 · 가지치기

결정 트리: 지니 불순도 · 정보 이득 · 가지치기

결정 트리(decision tree)는 "나이가 30 이하인가?", "소득이 300 이상인가?" 같은 예/아니오 질문을 차례로 던져 데이터를 잘게 나누는 모델입니다. 사람이 읽을 수 있는 규칙이 나오고 전처리가 거의 필요 없어 실무에서 아주 많이 쓰이며, 랜덤 포레스트와 그래디언트 부스팅의 부품이기도 합니다. 이 수업은 "어떤 질문이 좋은 질문인가"를 지니 불순도와 정보 이득으로 직접 계산하고, 트리가 과적합하는 이유와 깊이 제한 · 가지치기로 막는 법을 실행 결과로 봅니다.

들어가기 전에

• 정보 이론 최소한: 엔트로피 · 교차 엔트로피 · KL 발산 — 정보 이득은 엔트로피가 얼마나 줄었는가입니다.
• 모델 평가와 과적합 — 트리는 가만두면 학습 데이터를 다 외우므로 검증이 특히 중요합니다.

한눈에 보기

• 트리가 질문(분할)을 고르는 기준 — "나눈 뒤 각 쪽이 얼마나 한 클래스로 순수해졌나" — 을 압니다.
• 지니 불순도와 엔트로피로 두 후보 분할을 직접 비교해 어느 쪽이 좋은지 계산합니다.
• 회귀 트리가 분산을 가장 많이 줄이는 지점을 찾는 과정을 숫자 6개로 따라갑니다.
• 깊이를 키울수록 학습 정확도는 1로 가지만 테스트 정확도는 그렇지 않음을 실행 결과로 봅니다.
• max_depth · min_samples_leaf · ccp_alpha로 트리를 다스리는 법과 트리의 장단점을 정리합니다.

1. 질문으로 나누기

직관(해설용 비유): 스무고개와 같습니다. 좋은 첫 질문은 후보를 반쯤으로 확 줄여 주는 질문입니다. 결정 트리는 매 단계에서 "어떤 특성을 어떤 값에서 자르면 양쪽이 가장 깔끔하게 나뉘는가"를 모든 후보에 대해 계산하고 가장 좋은 것을 고릅니다.

단계(분류 트리)

1. 현재 노드의 데이터에 대해, 모든 특성 $j$와 가능한 임곗값 $t$를 후보로 둡니다($x_j \le t$면 왼쪽, 아니면 오른쪽).
2. 후보마다 나눈 뒤의 가중 불순도를 계산합니다.
3. 가중 불순도가 가장 작은(불순도 감소가 가장 큰) 후보로 나눕니다.
4. 자식 노드마다 1~3을 반복하다가, 노드가 순수해지거나 멈춤 조건(깊이, 최소 표본 수)에 걸리면 잎(leaf)으로 둡니다.
5. 잎의 예측은 그 안 데이터의 다수 클래스(회귀면 평균)입니다.

scikit-learn은 CART 알고리즘을 최적화한 버전을 쓰며, 항상 둘로 나누는 이진 트리를 만듭니다. 각 단계에서 지금 가장 좋은 분할만 고르는 탐욕적(greedy) 방법이라, 트리 전체로 최적이라는 보장은 없습니다.

2. 불순도: 지니와 엔트로피

노드 $m$에서 클래스 $k$의 비율을 $p_{mk}$라고 할 때, scikit-learn 문서의 두 기준은 다음과 같습니다.

지니의 뜻: 노드에서 무작위로 두 개를 뽑았을 때(복원 추출) 클래스가 서로 다를 확률입니다. 순수하면 0, 두 클래스가 반반이면 0.5입니다. 엔트로피는 클래스를 알아내는 데 필요한 평균 비트 수로, 반반이면 1비트입니다. 엔트로피로 잰 불순도 감소를 정보 이득(information gain)이라고 부릅니다. scikit-learn 기본값은 criterion='gini'입니다.

3. 숫자로 해 보기: 두 분할 비교(해설용)

예제 10개, 구매 5 · 비구매 5에서 시작합니다. 뿌리 노드의 지니 $= 1 - (0.5^2 + 0.5^2) = 0.5$, 엔트로피 $= 1$비트입니다.

분할 A — 왼쪽 5개(구매 4, 비구매 1), 오른쪽 5개(구매 1, 비구매 4)

• 각 자식 지니 $= 1 - (0.8^2 + 0.2^2) = 1 - 0.68 = 0.32$
• 가중 지니 $= 0.5 \times 0.32 + 0.5 \times 0.32 = 0.32$ → 감소 0.18
• 각 자식 엔트로피 $= -0.8\log_2 0.8 - 0.2\log_2 0.2 \approx 0.722$ → 정보 이득 $\approx$ 0.278

분할 B — 왼쪽 3개(구매 3, 비구매 0), 오른쪽 7개(구매 2, 비구매 5)

• 왼쪽은 순수: 지니 0, 엔트로피 0
• 오른쪽 지니 $= 1 - ((2/7)^2 + (5/7)^2) = 20/49 \approx 0.408$
• 가중 지니 $= 0.3 \times 0 + 0.7 \times 0.408 \approx 0.286$ → 감소 0.214
• 오른쪽 엔트로피 $\approx 0.863$, 가중 $\approx 0.604$ → 정보 이득 $\approx$ 0.396

두 기준 모두 B를 고릅니다. 한쪽을 완전히 순수하게 만든 분할이 점수가 더 좋았습니다. 지니와 엔트로피는 대부분의 경우 비슷한 분할을 고르며, 지니는 로그 계산이 없어 조금 빠릅니다. (위 숫자는 python으로 다시 계산해 확인했습니다.)

4. 회귀 트리: 분산을 줄이는 자리 찾기

정답이 실수이면 불순도로 분산(평균제곱오차)을 씁니다. 잎의 예측은 그 안의 평균입니다.

숫자로 해 보기(해설용): $x = 1, 2, 3, 4, 5, 6$, $y = 5, 6, 5, 20, 21, 22$. 뿌리 분산은 약 61.8입니다.

$t = 3.5$에서 가중 분산이 0.44로 가장 작습니다. 트리는 "$x \le 3.5$면 5.33, 아니면 21.0"이라는 계단 모양 예측을 만듭니다. 회귀 트리의 예측은 언제나 이런 계단 함수라서, 학습 범위 밖($x = 10$)에서도 마지막 계단 값(21.0)만 냅니다 — 추세를 외삽하지 못한다는 뜻입니다.

12345678910flowchart TB
  R[뿌리: 전체 데이터] --> Q1{모든 특성 · 임곗값 후보에서 불순도 감소 계산}
  Q1 --> S[가장 좋은 분할 x_j ≤ t 선택]
  S --> L[왼쪽 자식]
  S --> Ri[오른쪽 자식]
  L --> C{멈춤 조건? 순수 · max_depth · min_samples_leaf}
  Ri --> C
  C -- 아니오 --> Q1
  C -- 예 --> Leaf[잎: 다수 클래스 또는 평균으로 예측]
  Leaf --> P[필요하면 비용-복잡도 가지치기]

5. 과적합과 트리 다스리기

직관: 멈춤 조건이 없으면 트리는 잎마다 예제가 하나씩 남을 때까지 질문을 계속해 학습 데이터를 통째로 외웁니다. 잡음까지 규칙으로 만들어 버리는 것입니다.

실행해 보기: scikit-learn 내장 유방암 진단 데이터(569개, 특성 30개)를 학습 70% · 테스트 30%로 나눠(시드 0, 클래스 비율을 맞춘 층화 분할 stratify=y, 트리도 random_state=0) 깊이를 바꿔 봤습니다.

학습 정확도는 깊이와 함께 1.0까지 오르지만, 테스트 정확도는 0.89~0.91 사이에서 거의 늘지 않습니다. 학습 정확도가 1이라는 사실은 아무것도 보장하지 않습니다. (Python 3.14 · scikit-learn 1.9.0 실행 결과. 데이터 분할이 바뀌면 숫자도 바뀝니다.)

주요 손잡이(scikit-learn 기본값)

6. 비용-복잡도 가지치기

직관: 먼저 크게 키운 뒤, "잎을 하나 줄일 때 늘어나는 오류가 작은" 가지부터 잘라 냅니다. 잎 하나당 벌금 $\alpha$를 매기는 셈입니다. scikit-learn 문서의 식은 다음과 같습니다.

실행 결과(같은 데이터): ccp_alpha 0.0 → 잎 16개, 테스트 0.906 / 0.005 → 잎 7개, 0.918 / 0.01 → 잎 5개, 0.918 / 0.02 → 잎 4개, 0.901. 잎을 16개에서 5개로 줄여도 테스트 성능은 오히려 조금 올랐습니다. 적당한 $\alpha$는 cost_complexity_pruning_path로 후보를 뽑아 교차 검증으로 고릅니다.

역사 메모: CART는 Breiman · Friedman · Olshen · Stone의 책 Classification and Regression Trees(1984)에서 정리된 방법이며, "크게 키운 뒤 가지치기"가 그 핵심 아이디어 중 하나입니다.

7. 트리의 장단점

특성 중요도: 학습된 트리의 feature_importances_는 각 특성이 분할에서 줄인 불순도의 합(정규화)입니다. 어떤 특성이 많이 쓰였는지 빠르게 보는 데 좋지만, 값의 종류가 많은 특성을 과대평가하는 경향이 있어 해석에 주의합니다.

불안정성의 해법: scikit-learn 문서도 트리의 불안정성은 트리를 여러 개 묶은 앙상블로 누그러뜨린다고 적습니다. 다음 수업의 랜덤 포레스트와 그래디언트 부스팅이 바로 그것입니다.

연습 문제

1. 노드에 클래스 3개가 각 1/3씩 있습니다. 지니와 엔트로피는?

풀이: 지니 $= 1 - 3 \times (1/3)^2 = 2/3 \approx 0.667$. 엔트로피 $= \log_2 3 \approx 1.585$비트.

2. 예제 8개(양성 4 · 음성 4)를 왼쪽 (양성 4, 음성 0) · 오른쪽 (양성 0, 음성 4)로 나누면 지니 감소는?

풀이: 두 자식 모두 순수(지니 0)라 가중 지니 0, 감소 $= 0.5 - 0 = 0.5$로 가능한 최대입니다.

3. 4절 데이터에서 $x = 10$의 예측값은?

풀이: $x > 3.5$이므로 오른쪽 잎의 평균 21.0입니다. 트리는 학습 범위 밖으로 추세를 늘려 가지 못합니다.

4. 학습 정확도 1.0, 테스트 0.80인 트리를 개선하려면?

풀이: max_depth를 줄이거나, min_samples_leaf를 늘리거나, ccp_alpha로 가지치기하고 교차 검증으로 값을 고릅니다. 그래도 부족하면 랜덤 포레스트 같은 앙상블로 넘어갑니다.

스스로 점검

1. 트리가 분할을 고를 때 최소화하는 값은 무엇인가요?
   • 답: 자식 노드 불순도를 개수 비율로 가중 평균한 값 $G(Q_m, \theta)$입니다. 같은 말로, 불순도 감소(정보 이득)를 최대화합니다.
2. 결정 트리에 표준화가 필요 없는 이유는?
   • 답: 분할이 "한 특성 ≤ 임곗값" 비교라서, 크기를 늘리거나 줄이는 단조 변환을 해도 양쪽으로 가는 예제가 바뀌지 않기 때문입니다.
3. 회귀 트리가 외삽을 못 하는 이유는?
   • 답: 예측이 각 잎에 들어온 학습 데이터 평균인 계단 함수라서, 학습 범위 밖에서는 가장자리 잎의 값만 내기 때문입니다.

용어 정리

더 깊이 보려면

scikit-learn '1.10 Decision Trees'는 다중 출력 트리, 결측값 지원, 시간 복잡도, 실무 팁(데이터가 많고 특성이 많을 때의 요령)까지 정리합니다. 문서의 '최소 비용-복잡도 가지치기' 절은 $\alpha_{\text{eff}}$를 따라 잎을 줄여 가는 과정을 예제로 보여 줍니다.

다음에 볼 것

• 앙상블: 배깅 · 랜덤 포레스트 · 그래디언트 부스팅 — 불안정한 트리를 여러 개 묶어 강하고 안정적인 모델을 만듭니다.
• XGBoost: 확장 가능한 트리 부스팅 — 정규화 항을 넣은 부스팅 트리의 대표 구현입니다.

라이선스

이 글은 원문 번역이 아니라 KAITABASE가 직접 쓴 해설이며, 숫자 예와 실행 결과는 설명용입니다(python · scikit-learn으로 직접 계산 · 실행). 참고 자료 scikit-learn 문서는 BSD-3-Clause 라이선스입니다.

출처

• 참고: https://scikit-learn.org/stable/modules/tree.html (지니 · 엔트로피 · 회귀 기준 식, 분할 품질 G, 비용-복잡도 가지치기 식, CART, 과적합 대책 권고)
• Breiman, L., Friedman, J., Olshen, R., Stone, C. (1984). Classification and Regression Trees. Wadsworth.