의사결정 트리와 랜덤 포레스트

의사결정 트리(Decision tree)는 흐름도와 비슷합니다. 하지만 그런 트리가 모인 숲은 머신러닝에서 가장 강력한 도구 중 하나가 됩니다.

유형: Build 언어: Python 선수 지식: Phase 1 (09 정보 이론, 06 확률) 예상 시간: 약 90분

학습 목표

• 지니 불순도(Gini impurity), 엔트로피(Entropy), 정보 이득(Information gain)을 직접 구현해 최적의 의사결정 트리 분할을 찾습니다.
• 최대 깊이(max depth), 최소 샘플 수(min samples) 같은 사전 가지치기(Pre-pruning) 제어를 포함해 의사결정 트리 분류기(Decision tree classifier)를 처음부터 만듭니다.
• 부트스트랩 샘플링(Bootstrap sampling)과 특성 무작위화(Feature randomization)를 사용해 랜덤 포레스트(Random forest)를 구성하고, 왜 분산(Variance)이 줄어드는지 설명합니다.
• MDI(Mean Decrease in Impurity) 기반 특성 중요도(Feature importance)와 순열 중요도(Permutation importance)를 비교하고, MDI가 언제 편향되는지 식별합니다.

문제

표 형태 데이터(Tabular data)가 있다고 해봅니다. 행은 샘플이고, 열은 특성이며, 예측하고 싶은 타깃 열이 있습니다. 여기에 신경망(Neural network)을 바로 적용할 수도 있습니다. 하지만 표 형태 데이터에서는 의사결정 트리, 랜덤 포레스트, 그래디언트 부스팅 트리(Gradient boosted tree) 같은 트리 기반 모델(Tree-based model)이 딥러닝보다 꾸준히 좋은 성능을 내는 경우가 많습니다. 구조화된 데이터 기반 Kaggle 대회에서도 Transformer보다 XGBoost와 LightGBM이 더 자주 강합니다.

이유가 있습니다. 트리는 숫자형과 범주형이 섞인 특성을 큰 전처리 없이 다룰 수 있습니다. 특성 공학(Feature engineering)을 많이 하지 않아도 비선형 관계를 포착합니다. 또 해석 가능합니다. 나무를 보면 어떤 조건 때문에 예측이 만들어졌는지 직접 따라갈 수 있습니다. 여러 트리를 평균내는 랜덤 포레스트는 중간 규모 데이터셋에서 과적합(Overfitting)에 꽤 강합니다.

이번 lesson에서는 재귀적 분할(Recursive splitting)로 의사결정 트리를 처음부터 만든 뒤, 그 위에 랜덤 포레스트를 쌓습니다. 분할 기준의 수학인 지니 불순도, 엔트로피, 정보 이득을 구현하고, 약한 학습기(Weak learner)의 앙상블(Ensemble)이 어떻게 강한 모델이 되는지 이해합니다.

개념

의사결정 트리가 하는 일

의사결정 트리(Decision tree)는 예/아니오 질문을 순서대로 던져 특성 공간(Feature space)을 직사각형 영역으로 나눕니다.

graph TD
    A["나이 < 30?"] -->|예| B["소득 > 50k?"]
    A -->|아니오| C["신용 점수 > 700?"]
    B -->|예| D["승인"]
    B -->|아니오| E["거절"]
    C -->|예| F["승인"]
    C -->|아니오| G["거절"]

각 내부 노드(Internal node)는 어떤 특성이 임계값(Threshold)을 넘는지 검사합니다. 각 잎 노드(Leaf node)는 예측을 만듭니다. 새 데이터 포인트를 분류할 때는 루트에서 시작해 조건에 맞는 가지를 따라가다가 잎에 도달합니다.

트리는 위에서 아래로 만들어집니다. 각 노드에서 데이터를 가장 잘 나누는 특성과 임계값을 선택합니다. 여기서 "가장 좋다"는 말은 분할 기준(Split criterion)으로 정의합니다.

분할 기준: 불순도 측정

각 노드에는 샘플 집합이 있습니다. 이 샘플을 나눈 뒤 자식 노드가 가능한 한 "순수"해지기를 바랍니다. 순수하다는 것은 각 자식 노드가 대부분 하나의 클래스만 포함한다는 뜻입니다.

지니 불순도(Gini impurity) 는 해당 노드의 클래스 분포에 따라 무작위 샘플에 라벨을 붙였을 때, 잘못 분류될 확률을 측정합니다.

Gini(S) = 1 - sum(p_k^2)

p_k는 집합 S에서 클래스 k가 차지하는 비율입니다.

순수 노드처럼 모든 샘플이 하나의 클래스라면 Gini = 0입니다. 이진 분류에서 클래스가 50/50이면 Gini = 0.5입니다. 값이 낮을수록 좋습니다.

예: 고양이 6개, 개 4개

Gini = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 0.48

엔트로피(Entropy) 는 노드 안의 정보량 또는 무질서도를 측정합니다. Phase 1 Lesson 09에서 다룬 개념입니다.

Entropy(S) = -sum(p_k * log2(p_k))

순수 노드에서는 entropy = 0입니다. 이진 분류에서 50/50이면 entropy = 1.0입니다. 이 값도 낮을수록 좋습니다.

예: 고양이 6개, 개 4개

Entropy = -(0.6 * log2(0.6) + 0.4 * log2(0.4))
        = -(0.6 * -0.737 + 0.4 * -1.322)
        = 0.442 + 0.529
        = 0.971 bits

정보 이득(Information gain) 은 분할 뒤 불순도, 즉 엔트로피나 지니 불순도가 얼마나 줄었는지를 뜻합니다.

IG(S, feature, threshold) = Impurity(S) - weighted_avg(Impurity(S_left), Impurity(S_right))

가중치는 각 자식 노드에 들어간 샘플 비율입니다.

각 노드의 탐욕적 알고리즘(Greedy algorithm)은 모든 특성과 가능한 모든 임계값을 시험한 뒤 정보 이득이 가장 큰 (feature, threshold) 쌍을 선택합니다.

분할이 동작하는 방식

현재 노드에 특성이 n개, 샘플이 m개 있다고 해봅니다.

1. 각 특성 j에 대해 반복합니다. (j = 1부터 n)
   • 샘플을 특성 j 값으로 정렬합니다.
   • 서로 다른 연속 값 사이의 중간점을 임계값 후보로 시험합니다.
   • 각 임계값의 정보 이득을 계산합니다.
2. 정보 이득이 가장 큰 특성과 임계값을 선택합니다.
3. 데이터를 왼쪽(feature <= threshold)과 오른쪽(feature > threshold)으로 나눕니다.
4. 각 자식 노드에 같은 과정을 재귀적으로 반복합니다.

이 탐욕적 방식은 전역 최적 트리(Global optimum tree)를 보장하지 않습니다. 최적의 트리를 찾는 문제는 NP-hard입니다. 그래도 실전에서는 탐욕적 분할이 잘 동작합니다.

중단 조건

중단 조건이 없으면 트리는 모든 잎이 순수해질 때까지 자랍니다. 극단적으로는 잎 하나에 샘플 하나만 남을 수 있습니다. 이렇게 하면 학습 데이터는 완벽히 외우지만 일반화는 매우 나빠집니다.

사전 가지치기(Pre-pruning) 는 트리가 완전히 자라기 전에 멈춥니다.

• 최대 깊이: 트리가 정해진 깊이에 도달하면 분할을 멈춥니다.
• 잎당 최소 샘플 수: 노드 샘플이 k개보다 적으면 멈춥니다.
• 최소 정보 이득: 최선의 분할이 불순도를 충분히 줄이지 못하면 멈춥니다.
• 최대 잎 노드 수: 전체 잎 개수를 제한합니다.

사후 가지치기(Post-pruning) 는 트리를 끝까지 키운 뒤 잘라냅니다.

• 비용-복잡도 가지치기(Cost-complexity pruning): scikit-learn에서 사용하는 방식으로, 잎 개수에 비례하는 페널티를 더합니다. 페널티를 키우면 더 작은 트리가 됩니다.
• 감소 오류 가지치기(Reduced error pruning): 서브트리를 제거해도 검증 오류가 증가하지 않으면 해당 서브트리를 제거합니다.

사전 가지치기는 더 단순하고 빠릅니다. 사후 가지치기는 유용한 추가 분할을 너무 일찍 막지 않기 때문에 더 좋은 트리를 만들 때가 많습니다.

회귀용 의사결정 트리

회귀(Regression)에서는 잎의 예측값이 해당 잎에 들어온 타깃 값의 평균입니다. 분할 기준도 바뀝니다.

분산 감소(Variance reduction) 가 정보 이득을 대신합니다.

VR(S, feature, threshold) = Var(S) - weighted_avg(Var(S_left), Var(S_right))

분산을 가장 많이 줄이는 분할을 고릅니다. 트리는 입력 공간을 여러 영역으로 나누고, 각 영역에서는 상수값, 즉 평균을 예측합니다.

랜덤 포레스트: 앙상블의 힘

단일 의사결정 트리는 분산이 큽니다. 데이터가 조금만 바뀌어도 전혀 다른 트리가 나올 수 있습니다. 랜덤 포레스트는 많은 트리의 예측을 평균내 이 문제를 줄입니다.

graph TD
    D["학습 데이터"] --> B1["부트스트랩 샘플 1"]
    D --> B2["부트스트랩 샘플 2"]
    D --> B3["부트스트랩 샘플 3"]
    D --> BN["부트스트랩 샘플 N"]
    B1 --> T1["트리 1<br>(무작위 특성 부분집합)"]
    B2 --> T2["트리 2<br>(무작위 특성 부분집합)"]
    B3 --> T3["트리 3<br>(무작위 특성 부분집합)"]
    BN --> TN["트리 N<br>(무작위 특성 부분집합)"]
    T1 --> V["예측 집계<br>(다수결 또는 평균)"]
    T2 --> V
    T3 --> V
    TN --> V

두 가지 무작위성이 트리를 다양하게 만듭니다.

배깅(Bagging, bootstrap aggregating): 각 트리는 학습 데이터에서 복원 추출한 부트스트랩 샘플로 학습합니다. 각 부트스트랩에는 원래 샘플의 약 63%가 등장합니다. 나머지는 OOB(Out-of-bag) 샘플로, 검증에 사용할 수 있습니다.

특성 무작위화(Feature randomization): 각 분할에서 전체 특성이 아니라 무작위 특성 부분집합만 고려합니다. 분류에서는 기본적으로 sqrt(n_features)를 사용합니다. 회귀에서는 보통 n_features/3을 사용합니다. 이렇게 하면 모든 트리가 같은 지배적 특성에서만 분할되는 일을 막을 수 있습니다.

핵심 통찰은 이렇습니다. 서로 덜 상관된 트리를 많이 평균내면 편향(Bias)을 크게 늘리지 않고 분산을 줄일 수 있습니다. 개별 트리는 평범할 수 있지만, 앙상블은 강해집니다.

특성 중요도

랜덤 포레스트는 자연스럽게 특성 중요도 점수를 제공합니다. 가장 흔한 방법은 다음과 같습니다.

MDI(Mean Decrease in Impurity): 각 특성에 대해, 해당 특성이 사용된 모든 트리와 모든 노드에서의 불순도 감소량을 합산합니다. 앞쪽 분할에서 불순도를 크게 줄이는 특성이 더 중요하게 평가됩니다.

importance(feature_j) = feature_j가 사용된 모든 노드에 대해 합산:
    (n_samples_at_node / n_total_samples) * impurity_decrease

이 방법은 학습 중 계산할 수 있어 빠릅니다. 다만 가능한 분할점이 많은 고유값 많은 특성(High-cardinality feature)에 편향됩니다.

순열 중요도(Permutation importance) 는 대안입니다. 한 특성의 값을 섞은 뒤 모델 정확도가 얼마나 떨어지는지 측정합니다. 더 신뢰할 수 있지만 더 느립니다.

트리가 신경망을 이기는 경우

표 형태 데이터에서는 트리와 포레스트가 신경망을 이기는 경우가 많습니다.

신경망은 이미지, 텍스트, 오디오처럼 공간적 또는 순차적 구조가 있는 데이터에서 강합니다. 평평한 특성 테이블에서는 트리가 기본 선택지입니다.

만들어 보기

Step 1: 지니 불순도와 엔트로피

두 분할 기준을 직접 만들고, 좋은 분할에 대해 두 기준이 대체로 같은 방향을 가리키는지 확인합니다.

import math

def gini_impurity(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return 1.0 - sum((c / n) ** 2 for c in counts.values())

def entropy(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return -sum(
        (c / n) * math.log2(c / n) for c in counts.values() if c > 0
    )

Step 2: 최선의 분할 찾기

모든 특성과 모든 임계값을 시험합니다. 정보 이득이 가장 큰 분할을 반환합니다.

def information_gain(parent_labels, left_labels, right_labels, criterion="gini"):
    measure = gini_impurity if criterion == "gini" else entropy
    n = len(parent_labels)
    n_left = len(left_labels)
    n_right = len(right_labels)
    if n_left == 0 or n_right == 0:
        return 0.0
    parent_impurity = measure(parent_labels)
    child_impurity = (
        (n_left / n) * measure(left_labels) +
        (n_right / n) * measure(right_labels)
    )
    return parent_impurity - child_impurity

Step 3: DecisionTree 클래스 만들기

재귀적 분할, 예측, 특성 중요도 추적을 구현합니다.

class DecisionTree:
    def __init__(self, max_depth=None, min_samples_split=2,
                 min_samples_leaf=1, criterion="gini",
                 max_features=None):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.min_samples_leaf = min_samples_leaf
        self.criterion = criterion
        self.max_features = max_features
        self.tree = None
        self.feature_importances_ = None

    def fit(self, X, y):
        self.n_features = len(X[0])
        self.feature_importances_ = [0.0] * self.n_features
        self.n_samples = len(X)
        self.tree = self._build(X, y, depth=0)
        total = sum(self.feature_importances_)
        if total > 0:
            self.feature_importances_ = [
                fi / total for fi in self.feature_importances_
            ]

    def predict(self, X):
        return [self._predict_one(x, self.tree) for x in X]

Step 4: RandomForest 클래스 만들기

부트스트랩 샘플링, 특성 무작위화, 다수결 투표를 구현합니다.

class RandomForest:
    def __init__(self, n_trees=100, max_depth=None,
                 min_samples_split=2, max_features="sqrt",
                 criterion="gini"):
        self.n_trees = n_trees
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.max_features = max_features
        self.criterion = criterion
        self.trees = []

    def fit(self, X, y):
        n = len(X)
        for _ in range(self.n_trees):
            indices = [random.randint(0, n - 1) for _ in range(n)]
            X_boot = [X[i] for i in indices]
            y_boot = [y[i] for i in indices]
            tree = DecisionTree(
                max_depth=self.max_depth,
                min_samples_split=self.min_samples_split,
                max_features=self.max_features,
                criterion=self.criterion,
            )
            tree.fit(X_boot, y_boot)
            self.trees.append(tree)

    def predict(self, X):
        all_preds = [tree.predict(X) for tree in self.trees]
        predictions = []
        for i in range(len(X)):
            votes = {}
            for preds in all_preds:
                v = preds[i]
                votes[v] = votes.get(v, 0) + 1
            predictions.append(max(votes, key=votes.get))
        return predictions

전체 보조 메서드(helper method)까지 포함한 구현은 code/trees.py에서 확인합니다.

사용하기

scikit-learn으로 랜덤 포레스트를 학습하는 코드는 세 줄에 가깝습니다.

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)

rf = RandomForestClassifier(n_estimators=100, random_state=42)
rf.fit(X_train, y_train)
print(f"정확도: {rf.score(X_test, y_test):.4f}")
print(f"특성 중요도: {rf.feature_importances_}")

실전에서는 그래디언트 부스팅 트리인 XGBoost, LightGBM, CatBoost가 랜덤 포레스트보다 더 강한 경우가 많습니다. 이 모델들은 트리를 순차적으로 만들며, 각 트리가 이전 트리의 오류를 보정합니다. 하지만 랜덤 포레스트는 잘못 설정하기 어렵고 하이퍼파라미터 튜닝을 거의 요구하지 않습니다.

산출물 만들기

이 lesson의 산출물은 outputs/prompt-tree-interpreter.md입니다. 이 프롬프트는 의사결정 트리 분할을 비즈니스 이해관계자에게 설명하는 데 사용합니다.

훈련된 트리의 구조, 깊이, 사용된 특성, 분할 임계값, 정확도를 프롬프트와 함께 제공합니다. 그러면 모델이 배운 내용을 평이한 규칙으로 바꾸고, 특성 중요도를 정리하며, 과적합이나 데이터 누수(Data leakage)를 경고하고, 다음 실험 방향을 추천합니다. 코드에 익숙하지 않은 사람에게 트리 기반 모델을 설명해야 할 때 사용합니다.

연습문제

1. 2차원 데이터셋과 3개 클래스로 단일 의사결정 트리를 학습합니다. 분할을 손으로 따라가고 직사각형 결정 경계(Decision boundary)를 그립니다. max_depth=2와 max_depth=10에서 경계가 어떻게 달라지는지 비교합니다.

2. 회귀 트리를 위한 분산 감소 분할을 구현합니다. y = sin(x) + noise 형태의 점 200개를 만들고 회귀 트리를 학습합니다. 트리의 구간별 상수 예측을 실제 곡선과 함께 그립니다.

3. 트리 개수를 1, 5, 10, 50, 200개로 바꿔 랜덤 포레스트를 만듭니다. 트리 개수에 따른 학습 정확도와 테스트 정확도를 그립니다. 테스트 정확도는 어느 지점에서 포화되지만 보통 감소하지 않는다는 점을 관찰합니다.

4. 다섯 개 데이터셋에서 지니 불순도와 엔트로피를 분할 기준으로 비교합니다. 정확도와 트리 깊이를 측정합니다. 대부분의 경우 두 기준은 거의 같은 결과를 만듭니다. 왜 그런지 설명합니다.

5. 순열 중요도를 구현합니다. 한 특성이 랜덤 노이즈이지만 고유값이 매우 많은 데이터셋에서 MDI 중요도와 비교합니다. MDI는 노이즈 특성을 높게 평가할 수 있지만, 순열 중요도는 그렇지 않습니다.

핵심 용어

더 읽을거리

• Breiman: Random Forests (2001) — 랜덤 포레스트의 원 논문입니다.
• Grinsztajn et al.: Why do tree-based models still outperform deep learning on tabular data? (2022) — 표 형태 데이터에서 트리 기반 모델과 신경망을 비교합니다.
• scikit-learn Decision Trees documentation — 의사결정 트리 사용법과 시각화 도구를 확인할 수 있습니다.
• XGBoost: A Scalable Tree Boosting System (Chen & Guestrin, 2016) — Kaggle에서 자주 쓰이는 그래디언트 부스팅 계열의 대표 논문입니다.