머신러닝에서 가장 직관적이면서 널리 쓰이는 모델 중 하나가 결정 트리(Decision Tree)입니다.
그중 대표 구현 방식이 CART(Classification And Regression Tree)입니다.

1. 결정 트리(Decision Tree)란?

결정 트리는 데이터를 조건문으로 반복 분할하여 최종 예측을 수행하는 트리 구조 모델입니다.

  • 루트 노드(Root Node): 첫 분할이 시작되는 노드
  • 내부 노드(Decision Node): 중간 분할 조건을 담는 노드
  • 리프 노드(Leaf Node): 최종 예측값을 내는 노드

새 데이터는 루트에서 시작해 조건을 따라 내려가며 분류/회귀 결과를 얻습니다.

2. CART 알고리즘의 기본 원리

(1) 이진 분할(Binary Splits)

CART는 항상 데이터를 두 그룹으로 나눕니다.

  • 예: X > 10 ? → YES / NO
  • 범주형도 YES / NO 분할로 처리

(2) 불순도(Impurity) 최소화

분할 목표는 노드 내 데이터 순도를 높이는 것입니다.

  • 분류: 지니 불순도(Gini Impurity) 주로 사용
  • 회귀: MSE/분산(Variance) 기반

불순도가 낮을수록 노드가 더 순수합니다.

(3) 탐욕적(Greedy) 분할

매 단계에서 가장 좋은 분할을 즉시 선택합니다.

  • 장점: 계산 효율 높음
  • 한계: 전체 최적해(global optimum) 보장은 어려움

(4) 가지치기(Pruning)

결정 트리는 과적합 위험이 커서 가지치기가 중요합니다.

  • 사전 가지치기(Pre-pruning): max_depth, min_samples_split 등으로 성장 제한
  • 사후 가지치기(Post-pruning): 크게 만든 뒤 불필요 가지 제거
  • CART 대표 방식: 비용 복잡도 가지치기(Cost Complexity Pruning, ccp_alpha)

3. 결정 트리의 장점

  • 해석 용이: 분할 기준과 예측 경로가 명확
  • 시각화 용이: 트리 구조를 그림으로 표현 가능
  • 다양한 데이터 처리: 수치형/범주형 모두 활용 가능
  • 전처리 부담 낮음: 스케일링 필수 아님
  • 비선형 관계 학습 가능
  • 특성 중요도 제공 가능

4. 결정 트리의 단점

  • 과적합 위험 큼
  • 데이터 변화에 구조가 민감(불안정성)
  • 탐욕 분할로 인한 지역 최적화 한계
  • 연속형 변수 분할이 비효율적일 수 있음
  • 결정 경계가 계단형이라 부드러운 경계 표현에 약함

5. CART와 앙상블 모델

CART는 단일 모델로도 유용하지만, 보통 앙상블에서 강력해집니다.

  • 랜덤 포레스트(Random Forest): 다수 트리의 평균/투표
  • 그래디언트 부스팅(Gradient Boosting): 오차를 순차 보정
  • XGBoost, LightGBM, CatBoost: CART 기반 고성능 확장

즉, CART는 현대 트리 기반 모델의 핵심 기반입니다.

6. 마무리

CART는 이진 분할 → 불순도 최소화 → 탐욕적 분할 → 가지치기의 흐름으로 동작합니다.
단순하면서도 강력하고, 앙상블 모델의 기초이므로 반드시 이해해야 할 핵심 알고리즘입니다.