컴퓨터공학 300 주제 시리즈의 266번째 글이다. 전체 지도는 여기.

한 줄 요약

결정 트리는 “특징 ≤ 임계값?” 질문을 불순도가 가장 많이 줄어드는 순서로 쌓아 데이터를 나누고, 랜덤 포레스트는 데이터와 특징을 무작위로 바꿔 가며 만든 여러 트리의 투표로 한 트리의 불안정함을 줄인다.

왜 필요한가

표 형태의 데이터(행 = 사례, 열 = 특징)는 실무 데이터의 대부분이다. 고객 테이블, 거래 로그, 센서 기록. 이런 데이터에서는 트리 기반 모델이 강하다.

  • 특징의 스케일을 맞출 필요가 없다. 대소 비교만 하기 때문이다.
  • 비선형 관계와 특징 간 상호작용을 따로 만들어 주지 않아도 잡아낸다.
  • 단일 트리는 사람이 읽을 수 있는 규칙이 된다.

로지스틱 회귀가 직선 하나로 공간을 가른다면, 트리는 축에 평행한 칸막이를 여러 번 쳐서 공간을 상자로 나눈다.

핵심 개념

트리는 질문의 연쇄다

아래는 모양을 보여 주기 위한 예시다.

               [소득 <= 40 ?]
               /            \
            예                아니오
      [나이 <= 55 ?]       [나이 <= 38 ?]
       /        \           /        \
    구매 안 함   구매      ...        구매

예측할 때는 뿌리에서 질문에 답하며 잎까지 내려간다. 잎의 다수 클래스(분류) 또는 평균값(회귀)이 답이다.

어떤 질문을 고르나 — 불순도

한 노드에 클래스가 섞여 있는 정도를 불순도로 잰다. 클래스 비율이 pk 일 때

지표 식 완전히 순수 반반(2클래스)
지니 1 − Σ pk² 0 0.5
엔트로피 −Σ pk log₂ pk 0 1

모든 특징, 모든 임계값 후보에 대해 나눠 보고, 자식 노드 불순도의 가중 평균이 가장 작은(= 불순도 감소가 가장 큰) 분할을 고른다. 엔트로피 기준의 감소량을 정보 이득이라 부른다. 매 단계 그 자리에서 최선만 고르는 탐욕적 방법이라 전역 최적의 트리를 보장하지는 않는다. 최적 트리를 찾는 문제는 일반적으로 계산이 매우 어렵기 때문에 이렇게 근사한다.

과적합과 가지치기

트리를 끝까지 키우면 잎마다 샘플 하나가 남아 학습 데이터를 100% 맞힌다. 그리고 새 데이터에서는 잘 틀린다. 그래서 깊이 제한(max_depth), 잎의 최소 샘플 수(min_samples_leaf), 비용-복잡도 가지치기(ccp_alpha) 같은 장치로 키를 제한한다.

단일 트리의 더 큰 문제는 분산이 크다는 것이다. 데이터가 조금만 바뀌어도 뿌리의 질문이 바뀌고, 그 아래 전체가 달라진다.

배깅과 랜덤 포레스트

분산이 큰 모델 여러 개를 평균 내면 분산이 줄어든다. 단, 모델끼리 서로 덜 닮아야 효과가 크다.

  1. 부트스트랩: 원래 데이터 n 개에서 복원 추출로 n 개를 뽑아 트리마다 다른 데이터를 준다. 한 번도 안 뽑힌 샘플(약 3분의 1, n 이 크면 1/e ≈ 36.8%)은 그 트리의 검증용으로 쓸 수 있다. 이것이 OOB(out-of-bag) 오차다.
  2. 특징 무작위 선택: 분할할 때마다 특징의 일부만 후보로 본다. 강한 특징 하나가 모든 트리의 뿌리를 독차지하는 것을 막아 트리끼리의 상관을 낮춘다.
  3. 투표/평균: 분류는 다수결(또는 확률 평균), 회귀는 평균.

Breiman(2001)이 정리한 랜덤 포레스트는 1 과 2 를 결합한 방법이다.

부스팅과의 차이

  랜덤 포레스트(배깅) 그래디언트 부스팅
트리 생성 독립적으로 병렬 앞 트리의 오차를 보정하며 순차
줄이는 것 주로 분산 주로 편향
튜닝 민감도 낮음 높음(학습률, 트리 수)

직접 해 보기

(나이, 소득)으로 구매 여부를 맞히는 작은 표에서 지니 불순도로 최적 분할을 찾고, 깊이 1 트리(그루터기) 25개로 작은 포레스트를 만든다.

import random
from collections import Counter
# (나이, 소득) -> 구매 여부
data = [(22,20,0),(25,35,0),(28,50,1),(32,60,1),(35,30,0),(40,80,1),
        (45,40,0),(50,90,1),(55,45,0),(60,70,1),(30,55,1),(48,38,0),
        (26,48,0),(58,42,1),(38,62,0),(44,47,1)]   # 경계 근처 예외들
def gini(rows):
    n = len(rows)
    if n == 0: return 0
    c = Counter(r[-1] for r in rows)
    return 1 - sum((v/n)**2 for v in c.values())
def best_split(rows):
    best = (gini(rows), None, None)
    for f in (0, 1):
        for t in sorted({r[f] for r in rows}):
            L = [r for r in rows if r[f] <= t]; R = [r for r in rows if r[f] > t]
            g = (len(L)*gini(L) + len(R)*gini(R)) / len(rows)
            if g < best[0]: best = (g, f, t)
    return best
print("뿌리 지니:", round(gini(data), 3))
g, f, t = best_split(data)
print(f"최적 분할: {['나이','소득'][f]} <= {t}, 가중 지니 = {g:.3f}")
# 랜덤 포레스트 맛보기: 부트스트랩 + 그루터기(깊이 1) 다수결
random.seed(0)
stumps = []
for _ in range(25):
    boot = [random.choice(data) for _ in data]
    g, f, t = best_split(boot)
    if f is None: continue
    L = Counter(r[-1] for r in boot if r[f] <= t).most_common(1)[0][0]
    R = Counter(r[-1] for r in boot if r[f] > t).most_common(1)[0][0]
    stumps.append((f, t, L, R))
def predict(x):
    votes = Counter(L if x[f] <= t else R for f, t, L, R in stumps)
    return votes.most_common(1)[0][0], dict(votes)
print("그루터기 수:", len(stumps))
print("(33, 65) 예측:", predict((33, 65)))
print("(52, 33) 예측:", predict((52, 33)))

실행 결과:

뿌리 지니: 0.5
최적 분할: 소득 <= 40, 가중 지니 = 0.273
그루터기 수: 25
(33, 65) 예측: (1, {0: 1, 1: 24})
(52, 33) 예측: (0, {0: 22, 1: 3})

뿌리의 지니는 0.5, 구매/비구매가 반반이다. 최적 분할은 “소득 ≤ 40” 이고 가중 지니가 0.273 으로 떨어졌다. 왼쪽(소득 40 이하) 5명은 모두 비구매로 순수하다. 0 이 되지 못한 것은 오른쪽에 소득이 40 을 넘는데도 사지 않은 예외 3명(나이 26·38·55)이 섞여 있기 때문이다.

포레스트 예측에서 투표가 24:1, 22:3 으로 갈린 점을 보라. 부트스트랩 표본마다 최적 분할이 달라졌다는 뜻이다. 이 다양성이 앙상블의 원천이다. 투표 비율은 그대로 예측의 확신도로 쓸 수 있다. 이 코드는 부트스트랩만 쓴 배깅이다. 진짜 랜덤 포레스트라면 분할마다 특징 후보를 무작위로 줄이는 단계가 더 붙는다.

현업에서는

  • 표 데이터의 기본값: 정형 데이터 경진대회와 실무에서 그래디언트 부스팅(XGBoost, LightGBM 등)과 랜덤 포레스트는 가장 먼저 시도하는 강력한 기준선이다.
  • 특징 중요도의 함정: 불순도 감소 기반 중요도는 값의 종류가 많은 특징(ID, 연속값)을 과대평가하는 경향이 있다. 순열 중요도(permutation importance)로 교차 확인하는 것이 안전하다. scikit-learn 문서도 이 점을 경고한다.
  • 설명이 필요할 때: 깊이 3~4 의 단일 트리는 현장 담당자에게 보여 줄 수 있는 규칙표가 된다. 성능은 포레스트로, 설명은 얕은 트리로 나누어 쓰기도 한다.
  • 외삽 불가: 회귀 트리는 잎의 평균만 내놓으므로 학습 범위 밖의 값을 예측하지 못한다. 시간에 따라 계속 증가하는 지표를 예측할 때 주의한다.

확인 문제

  1. 클래스 비율이 (0.8, 0.2) 인 노드의 지니 불순도는?
  2. 결정 트리에서 특징 표준화가 필요 없는 이유는?
  3. 랜덤 포레스트가 분할마다 특징 일부만 보는 이유는?
  4. 부트스트랩에서 특정 샘플이 한 번도 뽑히지 않을 확률은 n 이 클 때 얼마로 수렴하는가?
  5. 배깅과 부스팅이 주로 줄이는 오차는 각각 무엇인가?

풀이

  1. 1 − (0.64 + 0.04) = 0.32
  2. 분할이 “특징 ≤ 임계값” 대소 비교라서 단조 변환(스케일 변경)을 해도 분할 결과가 같기 때문이다.
  3. 강한 특징이 모든 트리를 지배하면 트리끼리 비슷해져 평균의 분산 감소 효과가 약해진다. 후보를 제한해 트리 간 상관을 낮춘다.
  4. (1 − 1/n)^n → 1/e ≈ 0.368
  5. 배깅은 분산, 부스팅은 편향.

더 읽을거리 (References)