CART 알고리즘은 결정 트리(Decision Tree)의 대표적인 구현 방식입니다.
특히 scikit-learn 같은 라이브러리에서 결정 트리를 구현할 때 CART 철학이 기본으로 사용됩니다.

결정 트리가 “트리 기반 분류/회귀”라는 큰 방법론이라면, CART는 이를 어떤 원칙으로 구축할지를 정의하는 구체적인 로직입니다.

CART 알고리즘의 주요 특징

1) 이진 분할 (Binary Splits)

CART는 각 노드에서 데이터를 항상 두 그룹으로 나눕니다.

  • 수치형 변수: 예) X > threshold ? → Yes / No
  • 범주형 변수: 예) “특정 범주인가?” → Yes / No

다중 분할 대신 이진 분할을 반복하는 것이 CART의 핵심 구조입니다.

2) 불순도(Impurity) 최소화

각 분할에서 불순도를 가장 크게 줄이는 변수/기준을 선택합니다.

  • 분류: 주로 지니 불순도(Gini Impurity) 사용
  • 회귀: MSE(평균제곱오차) 또는 분산 사용

값이 작을수록 노드의 순도가 높습니다.

3) 탐욕적(Greedy) 분할

CART는 매 순간 현재 노드 기준에서 가장 좋은 분할을 선택합니다.

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

실무에서는 전역 탐색보다 계산 가능성과 속도가 중요하기 때문에 이 방식이 널리 쓰입니다.

4) 가지치기(Pruning)

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

  • 사전 가지치기(Pre-pruning): max_depth, min_samples_split, max_leaf_nodes 등으로 성장 제한
  • 사후 가지치기(Post-pruning): 충분히 성장시킨 뒤 불필요한 가지 제거
  • 대표 방식: 비용 복잡도 가지치기(Cost Complexity Pruning, ccp_alpha)

가지치기는 모델을 단순화하고 일반화 성능을 높입니다.

결정 트리 맥락에서의 CART

CART는 결정 트리의 장점을 실용적으로 구현합니다.

  • 해석력 높음
  • 시각화 용이
  • 수치형/범주형 데이터 처리 가능
  • 비선형 관계 학습 가능

동시에 결정 트리의 단점도 함께 가집니다.

  • 과적합 위험
  • 데이터 변화에 민감한 구조(높은 분산)
  • 탐욕 분할로 인한 지역 최적화 가능성

따라서 CART는 단독 모델로도 유용하지만, 보통 가지치기/교차검증/앙상블과 함께 쓰여 안정성을 높입니다.

결론

CART는 결정 트리의 핵심 원리를 실용적으로 구현한 표준 알고리즘입니다.
이진 분할, 불순도 최소화, 탐욕적 학습, 가지치기 메커니즘을 통해 실제 문제에서 효율적이고 해석 가능한 트리 모델을 구축할 수 있습니다.