CART 알고리즘이란?
CART(Classification and Regression Trees, 분류 및 회귀 나무)는 1984년 리오 브라이먼(Leo Breiman), 제롬 프리드먼(Jerome Friedman), 리처드 올셴(Richard Olshen), 찰스 스톤(Charles Stone) 4인이 처음 발표한 대표적인 의사결정나무 알고리즘입니다. 이름에서 알 수 있듯이 CART는 분류(Classification) 문제와 회귀(Regression) 문제 모두에 활용할 수 있습니다. 이 알고리즘은 이진 트리(binary tree) 형태로 트리를 구성하며, 순도(purity)를 높이는 새로운 분할 지점을 더 이상 찾을 수 없을 때까지 데이터를 반복적으로 나누는 방식으로 작동합니다.
후보 서브트리: 복잡성과 정확성의 균형
완성된 트리가 항상 최선의 예측 모델은 아닙니다. 트리가 너무 깊으면 학습 데이터에는 잘 맞지만 새로운 데이터에는 성능이 떨어지는 과적합(overfitting)이 발생하기 때문입니다. 이를 해결하기 위해 CART는 모델의 복잡성과 학습 데이터의 오분류율 사이에서 서로 다른 균형점을 보여주는 여러 개의 단순화된 서브트리(subtree)를 후보 모델로 만들어 둡니다. 그다음 검증용 데이터셋(validation set)에 이 후보들을 적용하고, 오분류율이 가장 낮은 트리를 최종 모델로 선택합니다.
가지치기(Pruning)의 원리
CART는 반복적인 가지치기(pruning) 과정을 통해 후보 서브트리들을 도출합니다. 목표는 잎(leaf) 하나당 예측력 기여도가 가장 낮은 가지부터 우선적으로 잘라내는 것입니다. 어떤 가지가 덜 유익한지 판단하는 기준이 바로 '조정된 오류율(adjusted error rate)'이라는 개념입니다.
조정된 오류율은 학습 데이터에서 각 노드의 오분류 비용에, 트리에 포함된 잎의 개수에 비례하는 복잡성 페널티(complexity penalty)를 더해 계산한 값입니다. 이를 통해 오분류율이 페널티를 상쇄하지 못하는 약한 가지(weak branch)를 식별하고, 해당 가지를 가지치기 대상으로 지정할 수 있습니다.
검증 데이터로 최적 트리 고르기
다음 단계는 후보 서브트리 중 새로운 데이터(레코드)에 가장 잘 작동하는 트리를 선별하는 것입니다. 각 후보 서브트리를 검증 데이터셋에 적용해 보고, 전체 오류율이 가장 낮은 트리가 최종 '승자'가 됩니다. 승리한 서브트리는 과학습(overtraining)의 영향을 제거할 만큼 충분히 가지치기되면서도, 중요한 정보를 잃지 않을 만큼 절제된 상태를 유지한다는 점이 특징입니다.
CART 가지치기의 한계
이 가지치기 방식은 오분류율에만 의존하며, 각 클래스가 나타날 확률(probability)은 고려하지 않습니다. 그 결과, 모든 잎이 동일한 클래스를 예측하는 서브트리는 같은 예측 결과를 내는 공통 부모 노드로 통합되어 버립니다.
또 다른 한계는 목표 클래스가 소수인 경우에 드러납니다. 예를 들어 상위 1% 또는 10%처럼 데이터의 극히 일부만을 대상으로 하는 모델을 만들 때, 이 가지치기 방식은 트리의 성능을 오히려 저하시킬 수 있습니다. 잘려나간 잎들 중 일부에 목표 클래스가 매우 집중된 영역이 포함되어 있을 수 있기 때문입니다. 이런 경우 SAS Enterprise Miner를 비롯한 일부 도구는 사용자가 이러한 목적에 맞게 트리를 최적으로 가지치기할 수 있는 기능을 제공합니다.
마무리: 선택된 트리의 성능 평가
승자로 선정된 서브트리는 검증 데이터셋을 분류하는 과정에서의 전체 오류율을 기준으로 선택된 것입니다. 선택된 서브트리가 다른 여러 데이터셋에 적용되었을 때도 계속해서 가장 좋은 성능을 낼 것으로 기대할 수 있지만, 엄밀히 말하면 이 트리를 선택하게 만든 오류율은 실제 성능을 다소 과대평가했을 가능성이 있습니다. 따라서 최종 모델의 신뢰성을 확인하려면 독립적인 테스트 데이터를 통해 성능을 한 번 더 검증하는 것이 좋습니다.