C5 알고리즘이란?
C5는 호주 연구자 J. Ross Quinlan이 수년간 개발하고 지속적으로 개선해 온 의사결정나무(decision tree) 알고리즘의 최신 버전입니다. 이전 버전인 ID3는 1986년에 확립되어 머신러닝 분야에 큰 영향을 미쳤으며, 그 후속 버전들은 현재 여러 상용 데이터 마이닝 서비스에서 활용되고 있습니다.
CART와 유사한 트리 생성 및 가지치기 방식
C5로 생성되는 트리는 CART 알고리즘으로 만들어지는 트리와 매우 유사합니다. CART와 마찬가지로 C5 역시 먼저 과적합(overfitting)된 트리를 생성한 뒤, 이를 가지치기(pruning)하여 더 일반화 성능이 좋은 모델을 만듭니다.
다만 C5의 가지치기 방법은 상당히 복잡하면서도 독특한데, 후보 서브트리(subtree) 중에서 선택할 때 검증 세트(validation set)를 사용하지 않는다는 점이 특징입니다.
검증 세트 없이 가지치기하는 이유
C5는 트리를 생성할 때 사용한 동일한 데이터를 가지치기 방법을 결정하는 데에도 활용합니다. 이러한 접근 방식은 알고리즘이 학계에서 탄생했다는 배경과 깊은 관련이 있습니다.
과거 대학 연구자들은 훈련 세트로 사용할 대량의 실제 데이터를 확보하기가 매우 어려웠습니다. 그래서 그들은 부족한 데이터셋에서 마지막 데이터 한 조각까지 짜내려고 많은 시간과 노력을 기울여야 했습니다. 반면 비즈니스 현장의 데이터 마이너들은 이런 문제를 겪을 필요가 없죠.
오류율 기반 가지치기 원리
C5는 각 노드의 오류율을 계산한 뒤, 실제 오류율이 이보다 상당히 나쁠 것이라고 가정하는 방식으로 트리를 가지치기합니다. 어떤 노드에 N개의 레코드가 있고 그중 E개가 잘못 분류되었다면, 해당 노드의 오류율은 E/N이 됩니다.
통계적 표본 추출과의 유추
C5는 통계적 표본 추출(sampling)과의 유추를 통해 리프(leaf) 노드에서 나타날 수 있는 최악의 오류 비용에 대한 추정치를 도출합니다. 이 유추는 리프의 데이터를 '각각 두 가지 가능한 결과 중 하나를 갖는 일련의 시행(trial)'의 결과로 해석하는 방식으로 작동합니다.
C5는 훈련 데이터에서 관찰된 오류 수를 이 범위의 하한으로 간주하고, 상한값으로 대체하여 리프의 예상 오류 비용, 즉 아직 보지 못한(unseen) 데이터에 대한 E/N을 산출합니다. 노드가 깊어질수록 오류 비용은 커지며, 어떤 노드의 다중 오류에 대한 상한 추정치가 그 자식 노드들의 오류 추정치보다 작다면 해당 자식 노드들은 가지치기됩니다.
좋은 모델의 조건과 자동 가지치기의 필요성
모델의 궁극적인 목표는 이전에 접해 보지 못한 데이터에 대해서도 일관성 있는 예측을 수행하는 것입니다. 이 목표를 달성하지 못하는 규칙은 모델에서 제거되어야 합니다.
일부 데이터 마이닝 도구는 사용자가 의사결정나무를 수동으로 가지치기할 수 있는 기능을 제공합니다. 이는 유용한 기능이지만, 더 나아가 통계 기반의 자동 가지치기를 옵션으로 지원하는 데이터 마이닝 소프트웨어가 기대됩니다.
이상적인 소프트웨어는 단순히 "검증 세트 결과의 분포가 훈련 그룹 결과의 분포와 달라 보인다"는 주관적 판단이 아니라, 보다 객관적이고 덜 주관적인 기준으로 불필요한 분할(split)을 거부할 수 있어야 합니다.