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

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

핵심 요약: 트리 기반 모델(Tree-based Model)은 “예/아니오” 질문을 반복해서 답을 찾는 모델이다. 단일 결정 트리(Decision Tree)는 해석이 쉽지만 불안정하고, 여러 트리를 합친 랜덤 포레스트(Random Forest)와 그래디언트 부스팅(Gradient Boosting, XGBoost/LightGBM/CatBoost)이 정형 데이터(Tabular Data)에서 가장 강력한 성능을 보인다.

핵심 용어 미리보기:

지니 불순도 (Gini Impurity): 한 노드(Node) 안에 서로 다른 클래스가 얼마나 섞여 있는지 측정하는 지표. 0이면 완전히 순수
가지치기 (Pruning): 트리가 너무 깊어져 과적합(Overfitting)되는 것을 막기 위해 불필요한 가지를 제거하는 기법
배깅 (Bagging): 데이터를 복원 추출(Bootstrap)하여 여러 모델을 독립적으로 만들고 결과를 평균내는 기법
부스팅 (Boosting): 이전 모델이 틀린 부분에 집중하여 순차적으로 모델을 개선하는 기법
조기 종료 (Early Stopping): 검증 세트(Validation Set) 성능이 나빠지기 시작하면 학습을 멈추는 기법

개요

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

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

탄생 배경

트리 기반 모델의 역사는 40년에 걸친 점진적 혁신의 여정이다. 시작점은 Breiman, Friedman, Olshen, Stone (1984)이 발표한 CART(Classification and Regression Trees)이다. CART는 데이터를 재귀적으로 이진 분할하는 단순하지만 강력한 아이디어를 제시했다. 마치 스무고개 게임(20 Questions Game)처럼, “이 특성이 임계값보다 큰가?”라는 질문을 반복하여 데이터를 분류하는 것이다.

그러나 단일 트리는 불안정하고 과적합에 취약했다. 이 문제를 해결한 것이 Leo Breiman (2001)의 랜덤 포레스트(Random Forest)이다. 핵심 아이디어는 놀랍도록 단순하다: 100명에게 같은 질문을 하고 다수결로 답을 정하면, 한 명에게 물어보는 것보다 훨씬 정확하다. 각 트리가 서로 다른 데이터와 특성을 보도록 하여 다양성을 확보하고, 이를 집계하여 분산을 줄인 것이다.

부스팅의 실용적 혁신은 Tianqi Chen & Carlos Guestrin (2016)의 XGBoost에서 정점에 달했다. 2차 테일러 전개를 이용한 분할 탐색, 정규화된 목적 함수, 결측값 자동 처리 등의 혁신을 담은 XGBoost는 2015년부터 2018년까지 Kaggle 대회의 우승 솔루션 대부분에 사용되며 “정형 데이터의 왕”이라는 별명을 얻었다. 이후 LightGBM (2017)과 CatBoost (2018)가 속도와 범주형 처리에서 각각의 강점을 더하며 현재의 그래디언트 부스팅 삼두체제를 형성했다.

핵심 개념

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})$

숫자로 이해하기

이메일이 스팸(Spam)인지 판별하는 트리를 생각해 보자.

첫 번째 질문: “무료”라는 단어가 포함되어 있나? → Yes
두 번째 질문: 링크(URL)가 포함되어 있나? → Yes
결론: 스팸(Spam)

이때 분할 기준으로 지니 불순도(Gini Impurity)를 계산해 보자. 100개의 이메일 중 스팸 60개, 정상 40개라면:

분할 전: $G = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 0.48$
“무료” 포함(80개: 스팸 55, 정상 25): $G = 1 - (0.6875^2 + 0.3125^2) = 0.43$
“무료” 미포함(20개: 스팸 5, 정상 15): $G = 1 - (0.25^2 + 0.75^2) = 0.375$

가중 평균 지니: $0.8 \times 0.43 + 0.2 \times 0.375 = 0.419$ . 분할 전(0.48)보다 낮아졌으므로 이 질문은 좋은 분할이다.

이득 비율 (Gain Ratio): 정보 이득을 분할 정보(Split Info)로 나눈 값 (다수 범주 특성에 대한 편향 보정)

회귀(Regression):

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

기준	특징
Gini	로그 계산 없이 빠름, 실무에서 가장 많이 사용
Entropy	정보 이론에 기반, Gini와 결과 차이 거의 없음
Gain Ratio	다수 값 특성에 대한 편향 보정 (C4.5)

트리 구성 알고리즘

알고리즘	분할 방식	특징
CART	이진 분할	분류와 회귀 모두 가능
ID3	다중 분할	범주형만 처리
C4.5	다중 분할	연속형 처리 가능, Gain Ratio 사용

가지치기 (Pruning)

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

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

장점과 단점

장점	단점
해석이 쉬움 (화이트박스)	높은 분산 (불안정)
특성 스케일링 불필요	과적합에 취약
혼합 데이터 타입 처리	탐욕적(greedy) 분할 (지역 최적)
비선형 관계 포착	축 정렬 경계만 가능

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

핵심 아이디어

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

알고리즘

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

핵심 하이퍼파라미터

파라미터	설명	기본값/가이드라인
`n_estimators`	트리 수	많을수록 좋으나 수확 체감
`max_features`	분할 시 고려할 특성 수	분류: $\sqrt{p}$ , 회귀: $p/3$
`max_depth`	최대 트리 깊이	None (완전 성장) 또는 제한
`min_samples_split`	분할 최소 샘플 수	2 (기본)
`bootstrap`	부트스트랩 사용 여부	True

왜 동작하는가

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

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

$\text{Var}_{\text{ensemble}} = \rho\sigma^2 + \frac{1-\rho}{n}\sigma^2$

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

OOB (Out-of-Bag) 오류

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

특성 중요도 (Feature Importance)

방법	설명	주의점
MDI (Mean Decrease in Impurity)	해당 특성의 불순도 감소 평균	높은 카디널리티 특성에 편향
MDA (Permutation Importance)	특성 값을 섞었을 때 정확도 감소	더 신뢰할 수 있으나 느림

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

핵심 아이디어

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

알고리즘

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

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

핵심 하이퍼파라미터

파라미터	설명	가이드라인
`n_estimators`	부스팅 라운드 수	학습률과 트레이드오프
`learning_rate` ( $\eta$ )	각 트리의 기여도	작을수록 더 많은 트리 필요
`max_depth`	개별 트리 깊이	3~8 (얕은 트리가 일반적)
`subsample`	행 샘플링 비율	확률적 그래디언트 부스팅
`colsample_bytree`	열 샘플링 비율	분산 감소에 도움

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) 계산

분할 이득 공식

$\text{Gain} = \frac{1}{2}\left[\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right] - \gamma$

여기서 $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 학습

상세 비교: XGBoost vs LightGBM vs CatBoost

속성	XGBoost	LightGBM	CatBoost
트리 성장	레벨 중심 (Level-wise)	리프 중심 (Leaf-wise)	대칭 (Symmetric)
속도	중간	가장 빠름	느림~중간
범주형 처리	인코딩 필요	네이티브 (기본)	최고 수준 네이티브
결측값 처리	네이티브	네이티브	네이티브
기본 성능	좋음	좋음	최고 (OOB)
GPU 지원	있음	있음	있음 (최고)
과적합 위험	중간	높음 (작은 데이터)	낮음

언제 사용하는가

상황	추천 모델
정형 데이터 (tabular data)	그래디언트 부스팅 (XGBoost/LightGBM/CatBoost)
해석 가능성이 최우선	단일 결정 트리
빠른 학습 + 적정 성능	랜덤 포레스트
범주형 특성이 많은 경우	CatBoost
대규모 데이터 + 빠른 학습	LightGBM
특성 중요도 분석	랜덤 포레스트, XGBoost
과적합이 걱정되는 작은 데이터	CatBoost, 랜덤 포레스트

실전 사례

XGBoost가 Kaggle 대회를 지배한 이야기 (2015-2018)

2015년, Kaggle의 Higgs Boson Machine Learning Challenge에서 XGBoost가 압도적인 성능을 보이며 주목받기 시작했다. 이후 XGBoost는 정형 데이터(Tabular Data) 대회에서 거의 독보적인 존재가 되었다.

2016년 KDD Cup에서 XGBoost 기반 솔루션이 우승했고, 같은 해 Kaggle의 “State Farm Distracted Driver Detection”, “Bosch Production Line Performance” 등 주요 대회에서도 상위권의 대부분이 XGBoost를 핵심 모델로 사용했다. 한 Kaggle Grandmaster는 “정형 데이터 대회에서 XGBoost를 시도하지 않는 것은 무기 없이 전쟁에 나가는 것과 같다”고 표현했다.

XGBoost의 성공 비결은 단순히 정확도만이 아니었다. 결측값 자동 처리로 전처리 부담을 줄이고, 조기 종료(Early Stopping)로 과적합을 효과적으로 방지하며, 병렬 처리로 대규모 데이터도 합리적인 시간 내에 학습할 수 있었다. 이 “실용적 완성도”가 경쟁에서의 우위를 만들어냈다.

2017년 이후 LightGBM이 속도 면에서 XGBoost를 추월하고, CatBoost가 범주형 데이터 처리에서 강점을 보이면서 경쟁 구도가 변했지만, 그래디언트 부스팅 계열이 정형 데이터의 사실상 표준(de facto standard)이라는 지위는 현재까지 유지되고 있다.

흔한 오해와 함정

1. “트리를 깊게 만들수록 항상 좋다”

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

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

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

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

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

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

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

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

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

다른 주제와의 연결

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

자주 묻는 면접 질문

랜덤 포레스트가 편향을 증가시키지 않고 분산을 줄이는 방법은?
- 개별 트리는 완전 성장(낮은 편향), 특성 무작위화로 트리 간 상관을 줄여 앙상블 분산 감소
부스팅 트리는 왜 얕고, 배깅 트리는 왜 깊은가?
- 부스팅: 순차적으로 편향을 줄이므로 약한 학습기(얕은 트리) 사용
- 배깅: 분산을 줄이므로 높은 분산(깊은 트리)인 모델이 효과적
XGBoost vs LightGBM: 어떤 상황에서 각각을 선호하는가?
- LightGBM: 대규모 데이터, 빠른 학습이 필요할 때
- XGBoost: 소규모 데이터, 더 안정적인 성능이 필요할 때
그래디언트 부스팅은 다양한 손실 함수를 어떻게 처리하는가?
- 손실 함수의 음의 기울기(negative gradient)를 유사 잔차로 사용하므로, 미분 가능한 모든 손실 함수에 적용 가능
특성 중요도 방법들의 차이점은?
- MDI: 불순도 감소 기반 (빠르지만 편향 있음)
- 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)

용어 정리

영어	한국어
Decision Tree	결정 트리
Random Forest	랜덤 포레스트
Gradient Boosting	그래디언트 부스팅
Gini Impurity	지니 불순도
Entropy	엔트로피
Information Gain	정보 이득
Pruning	가지치기
Bagging	배깅 (Bootstrap Aggregating)
Boosting	부스팅
Feature Importance	특성 중요도
Out-of-Bag	OOB (아웃 오브 백)
Early Stopping	조기 종료

참고 자료

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”