결정 트리Decision Tree
특징 하나와 임계값 하나로 된 질문(xⱼ ≤ t)을 뿌리부터 되풀이해 데이터를 나누고, 마지막에 닿은 잎의 다수 클래스나 평균으로 예측하는 지도 학습 모델이다.
1요약
- 결정 트리는 지도 학습의 분류 · 회귀에서 한 특징 · 한 임계값의 질문을 되풀이해 입력 공간을 축에 평행한 직사각형 조각으로 나누는 모델로(Breiman 1984 · Quinlan 1986), 랜덤 포레스트 · 그래디언트 부스팅 같은 앙상블이 이 트리를 수백 그루 묶어 돈다.
- 선형 모델은 특징 사이 상호작용과 문턱 효과를 사람이 식에 넣어야 하지만, 트리는 «A 이고 B 이면»의 규칙을 데이터에서 스스로 찾는다 — 지폐 영상 데이터에서 질문 두 번(깊이 2)이면 시험 정확도 86.9%, 네 번이면 95.1% 다(UCI Banknote · 직접 실행).
- 「트리가 이상하다」는 끝까지 자란 깊이(과적합) · 표본마다 바뀌는 모양(분산) · 다수 클래스로 쏠린 잎 셋으로 가른다(scikit-learn 1.10 문서).
2등장 배경
1960년대 설문 분석에서는 소득 같은 결과에 나이 · 학력 · 지역이 어떻게 함께 작용하는지 보려고 상호작용 항을 회귀식에 하나씩 넣어 봤는데, 변수가 몇십 개면 조합을 다 시험할 수 없었다. 1963년 Morgan · Sonquist 는 표본을 결과 차이가 가장 큰 두 집단으로 되풀이해 나누는 자동 상호작용 탐지(AID) 를 제안했고(Morgan 1963), 1980년 Kass 는 분할 여부를 카이제곱 검정으로 정하는 CHAID 를 냈다(Kass 1980).
1984년 Breiman · Friedman · Olshen · Stone 은 이진 분할 · 회귀 트리 · 비용 복잡도 가지치기를 묶은 CART 를 정리했고(Breiman 1984), 1986년 Quinlan 은 정보 이득으로 범주형 속성을 고르는 ID3 를 발표해 C4.5 로 이었다(Quinlan 1986). 같은 시기 Hyafil · Rivest 는 가장 작은 이진 결정 트리를 찾는 문제가 NP-완전임을 보였고(Hyafil 1976), 그래서 모든 알고리즘이 한 단계씩 고르는 탐욕 방식을 쓴다.
지금 scikit-learn 의 결정 트리는 최적화한 CART 이고(scikit-learn 1.10 문서 1.10.6), 트리 한 그루보다 여러 그루를 묶은 앙상블이 표 데이터의 주력이 되면서 트리는 그 기본 단위로 남았다.
3쉽게 이해하기 — 질문 카드로 귤과 레몬을 가르는 선별장
과일 선별장의 하람은 귤 7개와 레몬 5개가 섞인 바구니를 받는다. 「지름 6 cm 이하?」와 「끝이 뾰족한가?」 두 질문 카드를 대 보니, 뾰족한 쪽에는 레몬 4개만 모이고 나머지 8개에는 레몬이 1개뿐이라 뒤 카드가 더 깨끗하게 가른다. 남은 8개에 다시 「지름 6 cm 이하?」를 묻자 귤 7개와 레몬 1개로 갈렸지만, 하람은 과일 한 개만 가르는 질문은 다음 바구니에서 틀리기 쉽다며 그 카드를 잘라 낸다. 새 과일이 들어오면 남은 질문 순서표를 위에서부터 물어 상자를 정한다.
그림 1 · 섞임을 가장 크게 줄이는 질문부터 골라 바구니를 나누고, 과일 한 개만 가르는 질문은 잘라 낸 질문 순서표가 새 과일의 상자를 정한다.
그림 2 · 두 질문 가운데 나눈 뒤 섞임의 가중 평균이 더 낮은 쪽(0.146)을 고르며, 그만큼 줄어든 섞임(0.340)이 질문의 점수다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 과일 바구니 | 학습 데이터 | 특징(크기 · 모양)과 레이블(귤 · 레몬)을 가진 표본 n개 |
| 질문 카드 | 분할 규칙 (j, t) | 특징 xⱼ 가 임계값 t 이하인지 묻는 이진 질문 |
| 섞임 비교 | 불순도 감소 | 나눈 뒤 Gini · 엔트로피의 가중 평균이 가장 낮은 질문을 고름 |
| 둘로 나눈 더미 | 자식 노드 | 질문의 예 · 아니오로 갈린 표본 묶음 · 여기서 다시 질문 |
| 이름 붙인 상자 | 잎 노드 | 다수 클래스(분류) · 평균(회귀)이 예측값 |
| 잘라 낸 카드 | 가지치기 | 학습 불순도가 조금 늘더라도 잎 수를 줄임 |
| 새 과일 | 예측 | 뿌리에서 잎까지 질문을 따라 내려감 · 질문 수 = 깊이 |
| 하람 | 학습 알고리즘(CART) | 후보 질문을 전부 재 보고 지금 가장 좋은 하나를 고름 |
⚠ 비유가 맞지 않는 곳: 하람은 질문을 경험으로 떠올리지만 알고리즘은 특징마다 정렬된 값 사이 중간값을 전부 후보로 재고, 지금 단계의 최선만 고르므로 두 단계 뒤까지 본 최선은 보장하지 않는다. 한 질문은 특징 하나만 보므로 «길이 ÷ 폭»처럼 두 특징을 섞은 기준은 질문 여러 개를 쌓아야 흉내 낸다.
4구조 — 노드 · 분할 기준 · 정지 조건 · 가지치기
그림 3 · 트리는 분할 규칙을 가진 노드와 예측값을 가진 잎으로 이뤄지고, 모양은 분할 기준 · 정지 조건 · 가지치기 세 설정이 정한다.
| 요소 | 크기 | 역할 | 값 · 근거 |
|---|---|---|---|
| 노드 데이터 Qₘ | 노드 m 의 표본 nₘ 개 | 분할할 대상 · 뿌리 = 학습 표본 전체 | scikit-learn 1.10 문서 1.10.7 |
| 분할 θ = (j, t) | 특징 1개 · 임계값 1개 | xⱼ ≤ t 이면 왼쪽 자식 | 후보 = 정렬된 서로 다른 값 사이 중간값(1.10.7) |
| 불순도 H | 노드마다 값 하나 | Gini Σpₖ(1 − pₖ) · 엔트로피 −Σpₖ log pₖ · 회귀 = MSE | 기본 gini(DecisionTreeClassifier 문서) |
| 분할 품질 G | 후보마다 값 하나 | (n_ | 1.10.7 |
| 정지 조건 | 설정 값 | max_ | 기본 None · 2 · 1 = 끝까지 자람(DecisionTreeClassifier 문서) |
| 가지치기 α | 0 이상 실수 | R_α(T) = R(T) + α × 잎 수 · 가장 약한 고리부터 자름 | 기본 ccp_ |
| 잎 | 잎마다 클래스 비율 | 다수 클래스 · 클래스 비율 = predict_ | 1.10.1 · 1.10.7.2 |
학습은 노드마다 특징별 정렬과 후보 훑기를 해 비용이 O(특징 수 × nₘ log nₘ) 이고, 예측은 깊이만큼 비교만 하면 된다(scikit-learn 1.10 문서 1.10.4). 엔트로피 기준으로 나누는 것은 잎의 클래스 비율로 잰 로그 손실을 줄이는 것과 같다(1.10.7.1).
🔑 트리는 한 번 고른 분할을 되돌리지 않는다 — 뿌리 분할이 표본 몇 개 때문에 바뀌면 그 아래 모든 노드가 다른 데이터를 받아 트리 전체가 달라진다.
5동작 — 지폐 영상 1,372장으로 CART 한 번
UCI Banknote 로 직접 실행한 사례다 — 진폐 · 위폐 모양 시편을 산업용 카메라로 400 × 400 화소로 찍고, 웨이블릿 변환 영상에서 뽑은 variance · skewness · curtosis · entropy 넷이 특징이며 클래스는 0 · 1 이다(UCI Banknote). CART 를 NumPy 로 구현했고 기준은 Gini, 난수는 시드 0 하나다.
- 데이터 — 1,372장을 시드 0 으로 섞어 학습 960장 · 시험 412장으로 나눈다 · 학습 쪽 클래스 0 은 529장, 1 은 431장이다.
- 뿌리 불순도 — Gini = 1 − (529/960)² − (431/960)² = 0.4948 이다.
- 분할 탐색 — 네 특징의 모든 중간값을 재면 특징별 최대 감소는 variance 0.2471 · skewness 0.1128 · curtosis 0.0434 · entropy 0.0037 이고, variance ≤ −0.218 이 뿌리 분할이 된다(왼쪽 412장 · 오른쪽 548장).
- 둘째 분할 — 왼쪽은 skewness ≤ 9.308 로 373장(클래스 1 이 351장) · 39장(클래스 0 이 38장)으로, 오른쪽은 variance ≤ 1.791 로 211장 · 337장으로 나뉜다 · 깊이 2 에서 학습 89.4% · 시험 86.9% 다.
- 끝까지 성장 — 기본값처럼 잎이 순수해질 때까지 키우면 깊이 7 · 잎 23 · 학습 100% · 시험 98.06% 다.
- 가지치기 경로 — 유효 α 가 가장 작은 가지부터 잘라 잎 23 → 21(α 0.00103) → … → 8(α 0.0106) → 2(α 0.0616) → 1 까지 15개의 하위 트리가 나온다.
- α 고르기 — 학습 960장 안에서 5겹 교차 검증을 하면 최고 98.96% 를 내는 가장 큰 α 가 0.00205 이고, 이때 잎 18 · 깊이 6 · 시험 97.82% 다.
그림 4 · 뿌리는 variance ≤ −0.218 로 960장을 412 · 548장으로 나누고, 깊이 2 에서 잎 넷 가운데 211장 잎만 Gini 0.458 로 아직 섞여 있다.
그림 5 · 같은 960장에서 임계값을 옮기며 잰 Gini 감소는 variance −0.218 에서 0.247 로 가장 크고, skewness 의 최대 0.113 을 크게 앞서 뿌리 분할이 된다.
그림 6 · 잎이 줄어도 시험 정확도는 잎 12 개 근처까지 97 ~ 98% 에 머물고, 그 아래에서 학습 · 시험이 함께 떨어진다 — 교차 검증은 잎 18 을 고른다.
시드 0 ~ 9 로 분할을 바꿔 되풀이하면 뿌리는 언제나 variance 였지만 임계값은 −0.218 ~ 0.705 로 움직였고, 끝까지 자란 잎 18 ~ 27개가 가지치기 뒤 12 ~ 22개(19 ~ 43% 줄임)가 되는 동안 시험 정확도 차이는 −1.2 ~ +0.7%p 였다(직접 실행).
🔑 이 데이터에서 가지치기가 줄인 것은 시험 오류가 아니라 잎 수다 — 잎 23 → 18 에서 시험 정확도는 0.24%p 만 바뀌어, 같은 성능을 더 작은 규칙 집합으로 낸다.
6비교 — ID3 · C4.5 · CART · CHAID
| 기준 | ID3 | C4.5 | CART | CHAID |
|---|---|---|---|---|
| 분할 기준 | 정보 이득(엔트로피) | 이득 비율(값이 많은 속성 치우침 보정) | Gini(분류) · 제곱 오차(회귀) | 카이제곱 검정의 유의 확률 |
| 가지 수 | 범주 수만큼 다중 분기 | 범주형 다중 · 연속형 구간 | 언제나 이진 | 다중(비슷한 범주를 합침) |
| 연속형 특징 | 직접 다루지 않음 | 구간으로 나눠 씀 | 정렬 값 사이 임계값 | 미리 구간으로 나눔 |
| 목표 | 분류 | 분류 | 분류 · 회귀 | 분류 중심 |
| 크기 조절 | 최대로 키운 뒤 가지치기를 붙이는 것이 보통 | 규칙으로 바꾼 뒤 조건을 지움 | 비용 복잡도 가지치기(α) | 검정이 유의하지 않으면 멈춤 |
| 근거 | Quinlan 1986 · scikit-learn 1.10.6 | scikit-learn 1.10.6 | Breiman 1984 · 1.10.9 | Kass 1980 |
분석회귀도 해야 하거나 앙상블의 기본 단위로 쓸 트리는 이진 분할 · 회귀 · 가지치기를 함께 가진 CART 를 쓰고, 범주형 설문 문항이 많아 분기 하나에 여러 범주를 나란히 보여야 하면 CHAID · C4.5 를 고른다. 근거는 표의 「가지 수」 · 「목표」 행이며, 오늘 널리 쓰는 scikit-learn 구현도 CART 다(scikit-learn 1.10.6).
선형 회귀 · 로지스틱 회귀와의 비교는 선형 회귀의 표가, 트리 여러 그루를 묶어 분산을 줄이는 방식은 앙상블이 맡는다.
7실무 진단 — 결정 트리의 문제 가르기
분석학습 · 시험 정확도 차이와 트리 크기부터 보고, 다음에 시드를 바꿔 모양이 흔들리는지, 마지막으로 클래스 비율 · 예측 범위를 본다. 끝까지 자란 트리는 기본값에서 생기는 가장 흔한 문제이고(DecisionTreeClassifier 문서), 크기를 잡아야 그 뒤의 안정성 · 치우침 점검이 같은 모델 위에서 이뤄지기 때문이다.
| # | 증상 | 의심 원인 | 단계 | 확인 자료 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | 학습 100% · 시험이 그보다 낮음 · 잎 수가 표본에 가까움 | 끝까지 자란 트리(과적합) | 학습 설정 | 깊이 · 잎 수 · ccp_ | 기본값 그대로면 끝까지 자람(DecisionTreeClassifier 문서) · max_ |
| 2 | 표본을 조금 바꾸면 분할 특징 · 임계값 · 잎 수가 바뀜 | 높은 분산(불안정) | 모델 | 시드별 뿌리 분할 · 잎 수 · 시험 정확도 범위 | 작은 변화로 전혀 다른 트리가 나옴(scikit-learn 1.10 문서) · 사례 임계값 −0.218 ~ 0.705 · 안정이 필요하면 앙상블 |
| 3 | 소수 클래스를 거의 맞히지 못함 | 다수 클래스로 쏠린 잎 | 데이터 | 잎별 클래스 비율 · 클래스별 재현율 | 학습 전 클래스 균형 · class_ |
| 4 | 회귀 예측이 계단 모양 · 학습 범위 밖에서 일정 | 조각별 상수 예측 | 출력 | 학습 목표 범위 · 잎 값 목록 | 외삽을 못 함(scikit-learn 1.10 문서) · 추세가 있으면 선형 회귀와 견줌 |
| 5 | XOR 꼴 관계에서 첫 분할이 거의 무작위 | 한 특징씩 보는 탐욕 분할 | 알고리즘 | 특징별 최대 불순도 감소 | 패리티 · XOR 은 표현이 어려움 · 특징 조합을 새 특징으로 만듦(scikit-learn 1.10 문서) |
사례는 1행(잎 23)과 2행(임계값 흔들림)이 보이고, 클래스 비율이 529 : 431 로 고른 편이라 3행은 해당하지 않는다.
8시험 대비
www.q-net.or.kr시험에서는 노드 · 분할 기준 · 가지치기를 묻는 정의 · 특징형, ID3 · C4.5 · CART 를 «분할 기준 · 가지 수 · 목표»로 가르는 비교형이 나올 수 있다. 정의형은 Gini · 엔트로피 식 하나와 작은 분할 계산을, 비교형은 알고리즘 표와 «언제 무엇을» 한 줄을 넣는다.
- 개요 — 정의(한 특징 · 한 임계값 질문의 반복) · 분류 · 회귀 · 앙상블의 기본 단위
- 구조 — 그림 3 뿌리 · 내부 노드 · 잎 + 분할 기준 · 정지 조건 · 가지치기 표
- 분할 원리 — Gini · 엔트로피 식 · 분할 품질 G · 그림 5 임계값별 감소 곡선(variance −0.218 · 0.247)
- 학습 사례 — 그림 4 깊이 2 트리(960 → 412 · 548) · 깊이별 정확도
- 가지치기 — R_α(T) · 가장 약한 고리 · 그림 6 잎 수 대 정확도 · 교차 검증 α 0.00205
- 비교와 한계 — ID3 · C4.5 · CART · CHAID 표 · 불안정 · 외삽 불가 → 앙상블
꼭 쓸 키워드
불순도지니 계수엔트로피정보 이득이득 비율이진 분할비용 복잡도 가지치기가장 약한 고리최대 깊이탐욕 알고리즘
다른 답안과 차이를 내는 한 가지는 그림 5 처럼 «한 특징의 임계값을 옮기며 잰 불순도 감소 곡선»으로 분할이 고르는 과정을 숫자로 보이는 것이다 — 최적 트리가 NP-완전이라 이 탐욕 선택을 쓴다는 근거(Hyafil 1976)를 한 줄 붙인다.
9오해와 사실
- 오해엔트로피 기준이 Gini 기준보다 늘 더 좋은 트리를 만든다.사실사례 뿌리에서 두 기준은 같은 분할 variance ≤ −0.218 을 골랐다(Gini 감소 0.247 · 정보 이득 0.396 bit · 직접 실행) — 엔트로피 기준은 잎 비율로 잰 로그 손실을 줄이는 것과 같다(scikit-learn 1.10.7.1).
- 오해결정 트리도 특징을 표준화해야 한다.사실분할은 한 특징 안 값의 순서만 쓰므로 정규화 · 더미 변수 같은 준비가 거의 필요 없다(scikit-learn 1.10 문서) — 단조 증가 변환을 해도 같은 표본 묶음이 나온다.
- 오해트리가 고른 분할 특징이 결과의 원인이다.사실분할 특징은 예측에 쓴 근거이지 인과 증거가 아니다 — 같은 데이터도 시드에 따라 뿌리 임계값이 −0.218 ~ 0.705 로 바뀌었다(직접 실행 · 시드 0 ~ 9).
10핵심 정리
| 구분 | 맡는 일 | 식 · 설정 | 사례 값(지폐 960장) | 흔한 실패 |
|---|---|---|---|---|
| 분할 규칙 | 표본을 둘로 나눔 | xⱼ ≤ t · 중간값 후보 전수 | 뿌리 variance ≤ −0.218 | 후보를 일부만 봄 |
| Gini 불순도 | 섞임을 잼 | Σpₖ(1 − pₖ) | 뿌리 0.4948 | 감소가 아닌 값 자체로 비교 |
| 분할 품질 G | 후보 고르기 | (n_ | 감소 0.2471 · skewness 0.1128 | 표본 수 가중을 빼먹음 |
| 정지 조건 | 크기 상한 | max_ | 기본값 → 깊이 7 · 잎 23 | 기본값을 그대로 둠 |
| 가지치기 α | 약한 가지 제거 | R(T) + α × 잎 수 | α 0.00205 → 잎 18 | α 를 시험 데이터로 고름 |
| 잎 | 예측값 | 다수 클래스 · 비율 · 평균 | [333, 4] → 클래스 0 | 범위 밖 회귀 외삽 |
| 불안정 | 표본에 민감 | 시드별 비교 | 임계값 −0.218 ~ 0.705 | 트리 하나로 원인 해석 |
11참고 문헌
- 먼저 볼 문헌
- ★ scikit-learn 1.9.1 User Guide 1.10 Decision Trees — 분할 품질 식(1.10.7) · 비용 복잡도 가지치기(1.10.9) · 장단점과 실무 팁을 볼 때
- ★ scikit-learn 1.9.1 API Reference - sklearn.tree.DecisionTreeClassifier — 기본값(gini · max_depth None · min_samples_leaf 1 · ccp_alpha 0.0)을 확인할 때
- ★ Banknote Authentication (UCI Machine Learning Repository · DOI 10.24432/C55P57 · CC BY 4.0) — 사례 데이터 1,372장 · 특징 4개를 내려받아 따라 해 볼 때
- ★ Classification and Regression Trees (Breiman · Friedman · Olshen · Stone · Wadsworth · CRC 재간) — CART 의 이진 분할 · 회귀 트리 · 비용 복잡도 가지치기 원전을 볼 때
- 본문 근거
- Induction of Decision Trees (Machine Learning 1(1) 81-106) — Springer · 1986-03 ·
doi.org/10.1007/BF00116251· 확인 2026-11-12 - Problems in the Analysis of Survey Data, and a Proposal (Journal of the American Statistical Association 58(302) 415-434) — American Statistical Association · 1963-06 ·
doi.org/10.1080/01621459.1963.10500855· 확인 2026-11-12 - An Exploratory Technique for Investigating Large Quantities of Categorical Data (Journal of the Royal Statistical Society Series C 29(2) 119-127) — Royal Statistical Society · 1980 ·
doi.org/10.2307/2986296· 확인 2026-11-12 - Constructing Optimal Binary Decision Trees is NP-complete (Information Processing Letters 5(1) 15-17) — Elsevier · 1976-05 ·
doi.org/10.1016/0020-0190(76)90095-8· 확인 2026-11-12