머신러닝을 공부하다 보면 가장 직관적이면서도 강력한 알고리즘인 Decision Tree(의사결정나무)를 만나게 된다. 하지만 실무나 캐글(Kaggle) 같은 대회에서는 Decision Tree 하나만 쓰기보다는 이를 발전시킨 Random Forest나 XGBoost 같은 앙상블 모델을 주로 사용한다.

오늘은 Decision Tree의 핵심 원리부터 시작해서, 왜 이 모델이 Low Bias, High Variance 모델인지, 그리고 이를 극복하기 위해 나온 Bagging, Boosting, Stacking 기법까지 하나의 흐름으로 정리한다.

1. Decision Tree (의사결정나무)란?

Decision Tree는 쉽게 말해 "스무고개" 게임과 같다. 데이터를 가장 잘 구분할 수 있는 질문을 계속 던져가며 마지막에 정답을 맞히는 방식이다.

1) 작동 원리: Classification vs Regression

Tree는 목적에 따라 두 가지로 나뉜다.

• Classification Tree (분류):

  • 마지막 Leaf Node에 도달했을 때, 해당 구역(Region)에 가장 많이 포함된 클래스(Mode, 최빈값)를 예측값으로 내놓는다.

  • 예: "이 구역에 참치 10마리, 고등어 2마리가 있네? 그럼 여기 들어온 새로운 물고기는 참치야!" (Majority Voting)

• Regression Tree (회귀):

  • 마지막 Leaf Node에 있는 데이터들의 평균값(Mean)을 예측값으로 내놓는다.

  • 데이터 공간을 여러 개의 직사각형 구간(Region)으로 나누고, 각 구간의 대표값을 할당하는 방식이다.

2) 학습 방법: 어떻게 쪼갤 것인가? (Tree Growing)

Tree는 데이터를 나눌 때 **"어떤 질문(Feature & Split point)으로 나눠야 가장 깔끔하게(Homogenous) 나뀔까?"**를 고민한다. 이때 **Greedy Algorithm(탐욕 알고리즘)**을 사용한다. 즉, 당장의 분기점에서 Loss Function을 가장 크게 줄이는 최적의 선택을 한다.

① Classification의 기준: Gini Index & Cross-Entropy

분류 문제에서는 불순도(Impurity)를 낮추는 방향으로 학습한다.

• Gini Index: $G = \sum_{k=1}^K p_k(1-p_k) = 1 - \sum_{k=1}^K p_k^2$

• 불순도가 낮을수록(0에 가까울수록) 한 종류의 데이터만 모여 있다는 뜻이다.

② Regression의 기준: RSS (Residual Sum of Squares)

회귀 문제에서는 오차를 줄여야 한다. 이를 위해 Recursive Binary Splitting을 사용한다.

• 여기서 $\hat{y}_{R_j}$는 해당 구역(Region)의 평균값이다.

• 나누기 전과 후의 RSS 차이가 가장 큰(오차가 가장 많이 줄어드는) 지점을 찾아서 쪼갠다.