결정 트리 (Decision Tree)

"날개가 있어? → 응. 날 수 있어? → 아니. → 펭귄." 결정 트리는 이런 스무고개를 데이터로부터 자동으로 만든다. 핵심은 어떤 질문을 먼저 던져야 답이 가장 빨리 갈리는가 — 이 "갈림의 정도"를 재는 자가 엔트로피와 지니 불순도다.

1. 불순도 — 한 상자가 얼마나 섞여 있나

한 노드에 A 클래스와 B 클래스가 섞여 있다. 얼마나 "지저분한지"를 숫자로 재자. 두 가지 척도가 쓰인다.

둘 다 한 클래스만 있으면 0(완벽하게 순수), 반반이면 최대(가장 혼란). 아래 슬라이더로 A의 비율을 바꿔 보라.

2. 정보 이득 — 어떤 질문이 가장 많이 갈라주나

부모 노드의 불순도에서, 질문으로 나눈 자식들의 가중 평균 불순도를 뺀 값이 정보 이득(Information Gain)이다. 클수록 좋은 질문.

새(분홍) vs 포유류(파랑) 8마리. 세 가지 질문 중 하나로 나눠 보자.

3. 트리 자라기 — 2차원 데이터를 잘라 나가기

좌표평면에 흩어진 두 클래스 점들. 트리는 매번 세로선 또는 가로선(x < t, y < t) 하나로 공간을 잘라 불순도를 낮춘다. 「한 번 나누기」를 눌러 가장 지저분한 잎을 최적의 선으로 쪼개 보라.

4. 과적합과 가지치기

깊이 제한을 풀면 트리는 결국 모든 점을 외워 학습 정확도 100%를 만든다. 하지만 그건 데이터의 노이즈까지 외운 것 — 새 데이터에서는 오히려 틀린다. 이것이 과적합(overfitting)이다.

• 사전 가지치기: max_depth, min_samples_leaf, min_impurity_decrease 로 미리 성장을 멈춘다.
• 사후 가지치기: 일단 크게 키운 뒤, 검증 데이터로 도움 안 되는 가지를 잘라낸다(cost-complexity pruning).
• 랜덤 포레스트: 데이터·특징을 무작위로 뽑아 얕은 트리 수백 개를 만들고 투표. 한 그루의 과적합을 평균으로 상쇄한다.

5. 코드로 정리

import math

def entropy(rows):
    n = len(rows)
    if n == 0: return 0.0
    h = 0.0
    for c in set(r.label for r in rows):
        p = sum(1 for r in rows if r.label == c) / n
        h -= p * math.log2(p)
    return h

def best_split(rows):
    base = entropy(rows); best = (0, None, None)
    for feat in features:
        for t in thresholds(rows, feat):
            left  = [r for r in rows if r[feat] < t]
            right = [r for r in rows if r[feat] >= t]
            if not left or not right: continue
            w = len(left)/len(rows)
            ig = base - (w*entropy(left) + (1-w)*entropy(right))   # 정보 이득
            if ig > best[0]: best = (ig, feat, t)
    return best

def build(rows, depth=0):
    if depth == MAX_DEPTH or entropy(rows) == 0:
        return Leaf(majority(rows))               # 멈춤 → 다수결 예측
    ig, feat, t = best_split(rows)
    if ig <= 1e-7: return Leaf(majority(rows))
    left  = build([r for r in rows if r[feat] < t], depth+1)
    right = build([r for r in rows if r[feat] >= t], depth+1)
    return Node(feat, t, left, right)