트리 기반 모델 (Tree-based Models)¶

난이도: 초급~고급
선수 지식: 기초 확률/통계, 정보 이론(엔트로피) 기본 개념
관련 문서: 앙상블 방법 | 과적합과 과소적합 | 하이퍼파라미터 최적화

개요¶

트리 기반 모델(Tree-based Models)은 특성 공간을 재귀적으로 분할하여 예측을 수행하는 모델 군이다. 단일 결정 트리(Decision Tree)부터 랜덤 포레스트(Random Forest), 그래디언트 부스팅(Gradient Boosting)까지, 실무에서 가장 많이 사용되는 모델 유형 중 하나이다.

특히 XGBoost, LightGBM, CatBoost는 정형 데이터(tabular data)에서 딥러닝을 포함한 다른 모델들보다 자주 우수한 성능을 보여, Kaggle 등 데이터 과학 대회에서 압도적으로 많이 사용된다.

핵심 개념¶

1. 결정 트리 (Decision Tree)¶

핵심 알고리즘¶

특성 공간을 재귀적으로 이진 분할(recursive binary partitioning)하여 예측한다.

분할 기준 (Splitting Criteria)¶

분류(Classification):

• 지니 불순도 (Gini Impurity): \(G = 1 - \sum_{k=1}^{K} p_k^2\)
• 엔트로피 (Entropy): \(H = -\sum_{k=1}^{K} p_k \log_2 p_k\)
• 정보 이득 (Information Gain): \(IG = H(\text{parent}) - \sum \frac{n_{\text{child}}}{n_{\text{parent}}} H(\text{child})\)
• 이득 비율 (Gain Ratio): 정보 이득을 분할 정보(Split Info)로 나눈 값 (다수 범주 특성에 대한 편향 보정)

회귀(Regression):

• 분산 감소 (Variance Reduction): MSE 기반
• MAE 기반 분할도 가능

트리 구성 알고리즘¶

가지치기 (Pruning)¶

과적합을 방지하기 위한 핵심 기법이다:

• 사전 가지치기 (Pre-pruning): 최대 깊이, 최소 샘플 수, 최소 불순도 감소 등 조기 종료 조건
• 사후 가지치기 (Post-pruning): 전체 트리를 먼저 성장시킨 후 불필요한 가지 제거
• 비용-복잡도 가지치기 (Cost-Complexity Pruning, CCP): \(R_\alpha(T) = R(T) + \alpha|T|\)
• 축소된 오류 가지치기 (Reduced Error Pruning)

장점과 단점¶

2. 랜덤 포레스트 (Random Forest)¶

핵심 아이디어¶

배깅(Bagging) + 무작위 특성 부분집합(Random Feature Subsets)

알고리즘¶

1. 훈련 데이터에서 부트스트랩 샘플 \(B\)개를 추출
2. 각 샘플로 트리를 성장시키되, 각 분할에서 무작위로 선택된 \(m\)개의 특성만 고려
3. 집계: 다수결 투표(분류) 또는 평균(회귀)

핵심 하이퍼파라미터¶

왜 동작하는가¶

• 부트스트랩으로 각 트리의 훈련 데이터를 다양화
• 특성 무작위 선택으로 트리 간 상관관계를 낮춤
• 결과적으로 분산(variance)을 감소시킴

수학적으로: 모델들의 분산이 \(\sigma^2\)이고 상관계수가 \(\rho\)일 때, 앙상블 분산은:

\(\rho\)를 줄이는 것이 핵심이며, 특성 무작위 선택이 이 역할을 한다.

OOB (Out-of-Bag) 오류¶

• 각 트리에서 부트스트랩에 포함되지 않은 샘플(약 36.8%)로 검증
• 별도 검증 세트 없이도 일반화 성능 추정 가능

특성 중요도 (Feature Importance)¶

3. 그래디언트 부스팅 (Gradient Boosting)¶

핵심 아이디어¶

약한 학습기(weak learner)를 순차적으로 잔차(pseudo-residual)에 맞춰 학습한다.

알고리즘¶

1. 초기화: \(F_0(x) = \arg\min_c \sum L(y_i, c)\)
2. \(m = 1, ..., M\)에 대해 반복:
3. 유사 잔차 계산: \(r_{im} = -\frac{\partial L(y_i, F_{m-1}(x_i))}{\partial F_{m-1}(x_i)}\)
4. 트리 \(h_m\)을 유사 잔차에 적합
5. 갱신: \(F_m(x) = F_{m-1}(x) + \eta \cdot h_m(x)\)

여기서 \(\eta\)는 학습률(learning rate)이다.

핵심 하이퍼파라미터¶

3.1 XGBoost¶

핵심 혁신¶

• 정규화된 목적 함수: \(\text{Obj} = \sum L(y_i, \hat{y}_i) + \sum \Omega(f_k)\), \(\Omega(f) = \gamma T + \frac{1}{2}\lambda\|w\|^2\)
• 손실의 2차 테일러 전개를 이용한 분할 탐색
• 근사 히스토그램 기반 분할 알고리즘
• 결측값의 자동 처리 (sparsity-aware split finding)
• 캐시 최적화 및 외부 메모리(out-of-core) 계산

분할 이득 공식¶

여기서 \(G\)는 1차 기울기 합, \(H\)는 2차 기울기 합이다.

3.2 LightGBM¶

핵심 혁신¶

• 리프 중심(Leaf-wise) 트리 성장: 최적 리프를 먼저 분할 (vs XGBoost의 레벨 중심)
• GOSS (Gradient-based One-Side Sampling): 큰 기울기의 샘플 유지, 작은 기울기에서 샘플링
• EFB (Exclusive Feature Bundling): 상호 배타적 특성을 번들링하여 차원 감소
• 히스토그램 기반 분할 (정확 탐색보다 훨씬 빠름)
• 범주형 특성 네이티브 지원

주의점¶

• 리프 중심 성장은 작은 데이터셋에서 과적합 위험 증가

3.3 CatBoost¶

핵심 혁신¶

• Ordered Target Statistics: 타깃 누출(target leakage) 없는 범주형 인코딩
• Ordered Boosting: 잔차 계산과 모델 학습에 다른 순열(permutation) 사용
• 대칭 트리 (Oblivious Decision Trees): 각 레벨에서 동일한 분할 기준
• 네이티브 GPU 학습

graph TB
    subgraph "Level-wise (XGBoost)"
        A1[Level 1] --> B1[Level 2]
        A1 --> B2[Level 2]
        B1 --> C1[Level 3]
        B1 --> C2[Level 3]
        B2 --> C3[Level 3]
        B2 --> C4[Level 3]
    end

    subgraph "Leaf-wise (LightGBM)"
        A2[Root] --> D1[Leaf]
        A2 --> D2[Best Leaf 선택]
        D2 --> E1[분할]
        D2 --> E2[분할]
    end

상세 비교: XGBoost vs LightGBM vs CatBoost¶

flowchart TD
    A[부스팅 라이브러리 선택] --> B{데이터 크기?}
    B -->|대규모| C{범주형 특성이 많은가?}
    B -->|소규모| D[CatBoost]
    C -->|예| E[CatBoost]
    C -->|아니오| F[LightGBM]
    A --> G{빠른 학습이 최우선?}
    G -->|예| H[LightGBM]
    A --> I{안정적 기본 성능?}
    I -->|예| J[CatBoost]

언제 사용하는가¶

흔한 오해와 함정¶

1. "트리를 깊게 만들수록 항상 좋다"¶

• 깊은 트리는 훈련 데이터를 암기(memorize)한다. 특히 부스팅에서는 얕은 트리(3~8)가 일반적이다.

2. "부스팅에서 트리 수를 늘리면 항상 성능이 올라간다"¶

• 과적합이 발생할 수 있다. 조기 종료(early stopping)와 검증 세트 모니터링이 필수적이다.

3. "랜덤 포레스트는 과적합하지 않는다"¶

• 트리 수가 많아지면 과적합 위험은 줄지만, 개별 트리가 지나치게 깊으면 여전히 과적합할 수 있다.

4. "특성 중요도(MDI)는 항상 신뢰할 수 있다"¶

• MDI는 높은 카디널리티 특성에 편향된다. 순열 중요도(Permutation Importance)가 더 신뢰할 수 있다.

5. "그래디언트 부스팅은 항상 랜덤 포레스트보다 낫다"¶

• 튜닝 없이 기본값으로 비교하면 랜덤 포레스트가 나을 수 있다. 부스팅은 튜닝에 민감하다.

다른 주제와의 연결¶

• 앙상블 방법: 배깅(RF)과 부스팅의 이론적 기초
• 과적합과 과소적합: 트리 깊이와 편향-분산 트레이드오프
• 하이퍼파라미터 최적화: 부스팅 모델의 튜닝 전략
• 정규화 이론: XGBoost의 L1/L2 정규화
• 손실 함수: 그래디언트 부스팅의 다양한 손실 함수

자주 묻는 면접 질문¶

1. 랜덤 포레스트가 편향을 증가시키지 않고 분산을 줄이는 방법은?

2. 개별 트리는 완전 성장(낮은 편향), 특성 무작위화로 트리 간 상관을 줄여 앙상블 분산 감소

3. 부스팅 트리는 왜 얕고, 배깅 트리는 왜 깊은가?

4. 부스팅: 순차적으로 편향을 줄이므로 약한 학습기(얕은 트리) 사용

5. 배깅: 분산을 줄이므로 높은 분산(깊은 트리)인 모델이 효과적

6. XGBoost vs LightGBM: 어떤 상황에서 각각을 선호하는가?

7. LightGBM: 대규모 데이터, 빠른 학습이 필요할 때

8. XGBoost: 소규모 데이터, 더 안정적인 성능이 필요할 때

9. 그래디언트 부스팅은 다양한 손실 함수를 어떻게 처리하는가?

10. 손실 함수의 음의 기울기(negative gradient)를 유사 잔차로 사용하므로, 미분 가능한 모든 손실 함수에 적용 가능

11. 특성 중요도 방법들의 차이점은?

12. MDI: 불순도 감소 기반 (빠르지만 편향 있음)
13. Permutation: 특성을 섞었을 때 성능 감소 (더 신뢰할 수 있지만 느림)

코드 예시¶

from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier
import xgboost as xgb
import lightgbm as lgb
from catboost import CatBoostClassifier

# 결정 트리
dt = DecisionTreeClassifier(max_depth=5, min_samples_leaf=10)
dt.fit(X_train, y_train)

# 랜덤 포레스트
rf = RandomForestClassifier(n_estimators=100, max_features='sqrt', oob_score=True)
rf.fit(X_train, y_train)
print(f"OOB Score: {rf.oob_score_}")

# XGBoost
xgb_model = xgb.XGBClassifier(
    n_estimators=1000, learning_rate=0.1, max_depth=6,
    subsample=0.8, colsample_bytree=0.8,
    early_stopping_rounds=50
)
xgb_model.fit(X_train, y_train, eval_set=[(X_val, y_val)])

# LightGBM
lgb_model = lgb.LGBMClassifier(
    n_estimators=1000, learning_rate=0.1, num_leaves=31,
    subsample=0.8, colsample_bytree=0.8
)
lgb_model.fit(X_train, y_train, eval_set=[(X_val, y_val)],
              callbacks=[lgb.early_stopping(50)])

# CatBoost
cat_model = CatBoostClassifier(
    iterations=1000, learning_rate=0.1, depth=6,
    cat_features=categorical_columns
)
cat_model.fit(X_train, y_train, eval_set=(X_val, y_val), early_stopping_rounds=50)

용어 정리¶

참고 자료¶

• Breiman (2001) - "Random Forests"
• Friedman (2001) - "Greedy Function Approximation: A Gradient Boosting Machine"
• Chen & Guestrin (2016) - "XGBoost: A Scalable Tree Boosting System"
• Ke et al. (2017) - "LightGBM: A Highly Efficient Gradient Boosting Decision Tree"
• Prokhorenkova et al. (2018) - "CatBoost: unbiased boosting with categorical features"