의사결정나무

"오늘 카페에서 공부할 수 있을까?"
→ 자리가 있나? → 와이파이가 되나? → 조용한가?
이처럼 질문에 Yes/No로 답하면서 결론을 내리는 구조가 바로 의사결정나무(Decision Tree)다.
가장 직관적이고 해석하기 쉬운 머신러닝 알고리즘 중 하나로, 분류와 회귀 모두에 사용할 수 있다.

1. 의사결정나무란?

의사결정나무는 데이터를 특성(feature)을 기준으로 반복적으로 분할해서 최종적으로 예측값을 출력하는 트리 구조의 모델이다. 사람이 실제로 의사결정하는 방식과 유사하게 작동한다.

트리의 구성 요소

• 루트 노드(Root Node): 트리의 시작점. 전체 데이터를 가장 잘 분리하는 특성으로 첫 질문
• 내부 노드(Internal Node): 중간 분기점. 또 다른 특성으로 질문
• 리프 노드(Leaf Node): 더 이상 분할되지 않는 끝점. 최종 예측값 출력
• 가지(Branch): 각 질문의 Yes/No 또는 조건별 경로
• 깊이(Depth): 루트에서 리프까지의 최대 거리. 트리의 복잡도를 나타냄

 

 

 

2. 어떤 기준으로 분할하는가? — 불순도

의사결정나무의 핵심 질문은 "어떤 특성, 어떤 기준값으로 분할해야 가장 좋은가?"이다. 이를 판단하는 척도가 불순도(Impurity)다.

불순도는 한 노드 안에 여러 클래스가 섞여 있는 정도를 나타낸다. 완전히 한 클래스만 있으면 불순도 = 0 (순수하다), 클래스가 반반 섞여 있으면 불순도가 가장 높다. 분할 후 불순도가 가장 많이 줄어드는 방향으로 분기한다.

① 지니 불순도 (Gini Impurity)

가장 많이 사용되는 불순도 척도다. 노드에서 무작위로 데이터를 선택했을 때 잘못 분류될 확률을 의미한다.

Gini = 1 − Σ pₖ²

pₖ: k번째 클래스의 비율  |  범위: 0 (완전 순수) ~ 0.5 (이진 분류 시 최대)
클래스가 K개일 때 최대 지니 = 1 − 1/K

📌 지니 불순도 계산 예시

노드 A: 합격 8명, 불합격 2명 (총 10명)

p(합격) = 8/10 = 0.8, p(불합격) = 2/10 = 0.2
Gini_A = 1 − (0.8² + 0.2²) = 1 − (0.64 + 0.04) = 0.32

노드 B: 합격 5명, 불합격 5명 (총 10명) — 가장 불순한 상태

p(합격) = 0.5, p(불합격) = 0.5
Gini_B = 1 − (0.5² + 0.5²) = 1 − (0.25 + 0.25) = 0.50 (최대)

노드 C: 합격 10명, 불합격 0명 — 완전 순수

Gini_C = 1 − (1.0² + 0.0²) = 1 − 1 = 0.00 (최소)

 

② 엔트로피 (Entropy)

정보 이론에서 유래한 불순도 척도다. 노드의 혼잡도(무질서도)를 측정하며, 정보 이득(Information Gain)을 최대화하는 방향으로 분할한다.

Entropy = −Σ pₖ · log₂(pₖ)

pₖ = 0이면 해당 항 제외 (0 × log 0 = 0으로 처리)
범위: 0 (완전 순수) ~ log₂K (K개 클래스 균등 분포일 때 최대)
이진 분류 시 최대 엔트로피 = 1

정보 이득 = 분할 전 엔트로피 − Σ (nᵢ/n) · 엔트로피(자식 노드 i)

정보 이득이 클수록 분할 후 불순도가 많이 감소한다 → 좋은 분할
C4.5 알고리즘은 정보 이득을 특성의 분기 수(Split Information)로 나눈 이득 비율을 사용

📌 엔트로피와 정보 이득 계산 예시

배달 주문 20건: 재주문 12건, 이탈 8건. "리뷰 4점 이상인가?"로 분할한다.

분할 전 엔트로피

p(재주문) = 12/20 = 0.6, p(이탈) = 8/20 = 0.4
H(전체) = −(0.6·log₂0.6 + 0.4·log₂0.4)
= −(0.6·(−0.737) + 0.4·(−1.322))
= 0.442 + 0.529 = 0.971

분할 후: 리뷰 4점 이상(14건: 재주문11, 이탈3) / 미만(6건: 재주문1, 이탈5)

H(4점 이상) = −(11/14·log₂(11/14) + 3/14·log₂(3/14)) ≈ 0.749
H(4점 미만) = −(1/6·log₂(1/6) + 5/6·log₂(5/6)) ≈ 0.650

가중 평균 엔트로피 = (14/20)×0.749 + (6/20)×0.650 = 0.524 + 0.195 = 0.719
정보 이득 = 0.971 − 0.719 = 0.252

 

③ 분산 감소 (Variance Reduction) — 회귀 트리

회귀 문제에서는 불순도 대신 분산 감소를 기준으로 분할한다. 분할 후 각 자식 노드의 분산이 줄어드는 정도가 클수록 좋은 분할이다.

분산 감소 = Var(부모) − Σ (nᵢ/n) · Var(자식 노드 i)

Var(노드) = (1/n) · Σ(yᵢ − ȳ)²
분산 감소가 클수록 자식 노드 내의 값들이 더 균일해졌다는 뜻

💡 지니 vs 엔트로피 — 어느 것을 쓸까?
실제로 두 척도의 결과 차이는 크지 않다. 대부분의 경우 어느 것을 써도 비슷한 트리가 만들어진다.
• 지니: 로그 계산이 없어 빠르다. CART 알고리즘에서 기본값으로 사용.
• 엔트로피: 정보 이론적 해석이 가능하다. C4.5, ID3 알고리즘에서 사용.
→ sklearn의 DecisionTreeClassifier는 기본값이 지니(criterion='gini')다.

 

3. 의사결정나무 분할 과정 — 전체 흐름

의사결정나무는 다음 과정을 재귀적으로 반복한다.

1. 최선의 분할 찾기: 모든 특성과 모든 가능한 분기점을 시험해서 불순도를 가장 많이 줄이는 (특성, 기준값) 쌍을 선택
2. 데이터 분할: 선택한 기준으로 현재 노드의 데이터를 두 그룹으로 나눔
3. 자식 노드 생성: 각 그룹으로 자식 노드를 만들고 1~2번 과정 반복
4. 종료 조건 확인: 아래 중 하나라도 만족하면 해당 노드를 리프로 설정
   · 노드의 불순도가 0 (완전히 순수)
   · 최소 샘플 수 이하
   · 최대 깊이 도달

📌 전체 분할 과정 예시: 헬스장 재등록 예측

고객 16명의 데이터(나이, 방문 횟수/월, 만족도 점수)로 재등록 여부를 예측하는 트리를 만든다.

원본 데이터 구성

재등록: 10명 / 이탈: 6명
Gini(루트) = 1 − (10/16)² − (6/16)² = 1 − 0.391 − 0.141 = 0.469

분할 후보 1: 방문 횟수 ≥ 8회/월

· 8회 이상(10명): 재등록 9, 이탈 1 → Gini = 1−(9/10)²−(1/10)² = 0.18
· 8회 미만(6명): 재등록 1, 이탈 5 → Gini = 1−(1/6)²−(5/6)² = 0.278
가중 Gini = (10/16)×0.18 + (6/16)×0.278 = 0.113 + 0.104 = 0.217
Gini 감소 = 0.469 − 0.217 = 0.252

분할 후보 2: 만족도 ≥ 4점

· 4점 이상(9명): 재등록 8, 이탈 1 → Gini = 0.198
· 4점 미만(7명): 재등록 2, 이탈 5 → Gini = 0.408
가중 Gini = (9/16)×0.198 + (7/16)×0.408 = 0.111 + 0.178 = 0.289
Gini 감소 = 0.469 − 0.289 = 0.180

최적 분할 선택

방문 횟수 ≥ 8회가 Gini 감소 0.252로 더 크다 → 루트 노드: "방문 횟수 ≥ 8회?"
이후 각 자식 노드에 대해 동일한 과정 반복 → 트리 완성

 

반응형

 

4. 가지치기 (Pruning) — 과적합 방지

제약 없이 트리를 키우면 학습 데이터의 모든 패턴(노이즈까지)을 외워버려 과적합이 발생한다. 이를 방지하기 위해 트리를 일부러 작게 만드는 것이 가지치기(Pruning)다.

사전 가지치기 (Pre-Pruning)

트리를 성장시키는 도중에 조건이 충족되면 조기에 성장을 멈춘다.

주요 제한 파라미터:
• max_depth: 최대 트리 깊이
• min_samples_split: 분할을 위한 최소 샘플 수
• min_samples_leaf: 리프 노드의 최소 샘플 수
• max_features: 분할 시 고려할 최대 특성 수

사후 가지치기 (Post-Pruning)

트리를 완전히 키운 후, 성능에 기여가 적은 가지를 제거한다.

• 비용-복잡도 가지치기(Cost-Complexity Pruning)가 대표적
• ccp_alpha: 클수록 더 많이 가지를 제거
• sklearn에서 지원하며 교차 검증으로 최적 alpha를 탐색

💡 과적합된 트리 vs 가지치기한 트리의 차이
과적합 트리: 학습 데이터 정확도 99% → 새 데이터 정확도 72% (암기만 잘함)
가지치기 트리: 학습 데이터 정확도 88% → 새 데이터 정확도 85% (진짜 패턴을 학습)
→ 학습 정확도가 약간 낮아지더라도 실제 성능은 높아질 수 있다.

 

5. 주요 의사결정나무 알고리즘

알고리즘	분할 기준	분기 방식	가지치기	특징
ID3	정보 이득	다중 분기	없음	범주형만 처리, 역사적 최초 알고리즘
C4.5	이득 비율	다중 분기	사후	연속형 처리, 결측값 처리, ID3 개선
CART	지니 / 분산 감소	이진 분기	사후	분류+회귀 모두 지원, sklearn 기본
CHAID	카이제곱 검정	다중 분기	통계적	범주형 특성에 강함, 통계적 유의성 기반

💡 sklearn의 Decision Tree는 CART 알고리즘을 사용한다
CART(Classification and Regression Tree)는 항상 이진 분기(Yes/No)를 만든다.
분류: 지니 또는 엔트로피로 분할 / 회귀: 분산 감소로 분할
→ 하나의 알고리즘으로 분류·회귀를 모두 처리할 수 있다.

 

6. 특성 중요도 (Feature Importance)

의사결정나무의 큰 장점 중 하나는 어떤 특성이 예측에 얼마나 중요한지를 수치로 알 수 있다는 것이다. 각 특성이 분할에 기여한 불순도 감소량을 합산해서 중요도를 계산한다.

특성 j의 중요도 = Σ (해당 특성으로 분할된 노드에서의 불순도 감소량 × 노드 샘플 비율)

전체 특성 중요도의 합 = 1 (정규화됨)
값이 클수록 해당 특성이 예측에 더 큰 역할을 한다

📌 특성 중요도 활용
• 불필요한 특성 제거 (Feature Selection): 중요도가 0에 가까운 특성 제거 → 모델 단순화
• 비즈니스 인사이트: "재등록 예측에서 방문 횟수(중요도 0.52)가 만족도(0.31)보다 더 중요하다"
• 과적합 감지: 노이즈 특성이 높은 중요도를 가지면 과적합 신호

 

7. 의사결정나무의 장단점

장점

• 결과를 사람이 직접 읽고 이해할 수 있다 (White-box 모델)
• 특성 스케일링 불필요 (거리 기반이 아님)
• 분류·회귀 모두 사용 가능
• 범주형·연속형 특성 모두 처리
• 결측값이 있어도 비교적 잘 처리
• 특성 중요도를 자동으로 계산
• 비선형 관계를 자연스럽게 처리

단점

• 과적합이 쉽게 발생 (가지치기 필수)
• 데이터의 작은 변화에도 트리 구조가 크게 바뀜 (불안정성)
• 클래스 불균형에 편향 (다수 클래스 선호)
• XOR 같은 비선형 패턴 학습이 어려울 수 있음
• 단일 트리의 예측 정확도는 앙상블보다 낮음

📌 의사결정나무가 앙상블의 기반이 되는 이유
의사결정나무 하나(단일 트리)는 성능이 제한적이지만,
여러 트리를 결합하면 훨씬 강력해진다.
• 랜덤 포레스트: 여러 트리를 병렬로 학습 후 다수결/평균 (배깅 기반)
• 그래디언트 부스팅(XGBoost, LightGBM): 이전 트리의 오류를 순차적으로 보완 (부스팅 기반)
→ 의사결정나무를 잘 이해해야 앙상블 알고리즘도 제대로 이해할 수 있다.

📌 핵심 정리

• 의사결정나무: 특성으로 반복 분할해 트리 구조로 예측. 분류·회귀 모두 가능
• 구성 요소: 루트 노드(시작) → 내부 노드(분기) → 리프 노드(예측값)
• 분할 기준: 불순도(Impurity)를 가장 많이 줄이는 방향으로 분할
• 지니 불순도: 1 − Σpₖ². 0(순수) ~ 0.5(이진 최대). 빠르고 많이 쓰임
• 엔트로피: −Σpₖ·log₂pₖ. 정보 이득 최대화. C4.5에서 사용
• 회귀 기준: 분산 감소. 분할 후 자식 노드 분산의 합이 최소화되는 방향
• 가지치기: 과적합 방지. 사전(max_depth 등 제한) / 사후(ccp_alpha)
• CART: sklearn 기본. 항상 이진 분기. 분류+회귀 모두 지원
• 특성 중요도: 불순도 감소 기여량으로 측정. 특성 선택·해석에 활용
• 앙상블의 기반: 랜덤 포레스트, XGBoost 모두 의사결정나무를 기본 단위로 사용