결정 트리란 무엇인가?
결정 트리 유도(decision tree induction)는 클래스 레이블이 붙어 있는 학습 데이터(훈련 튜플)로부터 결정 트리를 학습하는 과정을 말합니다. 결정 트리는 순서도(flowchart)와 유사한 트리 구조로, 각 내부 노드(internal node)는 특정 속성에 대한 검증(test)을 나타내고, 각 분기(branch)는 그 검증의 결과를 의미하며, 각 잎 노드(leaf node 또는 terminal node)는 하나의 클래스 레이블을 나타냅니다. 트리의 최상위에 위치한 노드를 루트 노드(root node)라고 부릅니다.
결정 트리의 구조와 동작 원리
예를 들어 '컴퓨터 구매 여부(buys computer)'라는 개념을 정의한다고 가정해 보겠습니다. 이는 전자제품 회사 AllElectronics의 고객이 컴퓨터를 구매할 가능성이 있는지를 예측하는 것입니다. 이때 내부 노드는 사각형으로, 잎 노드는 타원으로 표현합니다. 일부 결정 트리 알고리즘은 모든 내부 노드가 정확히 두 개의 자식 노드로 분기되는 이진 트리(binary tree)만 생성하는 반면, 다른 알고리즘은 비이진 트리(non-binary tree)도 만들 수 있습니다.
클래스 레이블을 알 수 없는 튜플(tuple) X가 주어지면, 해당 튜플의 속성 값들을 결정 트리와 비교하여 검사합니다. 그런 다음 루트 노드에서 잎 노드까지의 경로를 추적하게 되며, 도달한 잎 노드가 바로 그 튜플에 대한 클래스 예측 결과를 제공합니다. 또한 결정 트리는 분류 규칙(classification rules) 형태로 변환할 수도 있습니다.
결정 트리의 주요 장점
1. 별도의 사전 지식 불필요
결정 트리 분류기를 개발할 때 특별한 도메인 지식이나 매개변수 설정이 필요하지 않습니다. 따라서 탐색적 지식 발견(exploratory knowledge discovery)에 매우 적합합니다.
2. 고차원 데이터 처리 가능
결정 트리는 차원이 큰 데이터도 효과적으로 처리할 수 있습니다.
3. 직관적인 표현
학습된 지식을 트리 형태로 표현하기 때문에 직관적이며 사람이 이해하기 쉽습니다.
4. 빠른 학습과 분류
결정 트리 유도의 학습 단계와 분류 단계 모두 간단하고 빠르게 수행됩니다.
다양한 실무 활용 분야
일반적으로 결정 트리 분류기는 우수한 정확도를 보이지만, 실제 성공 여부는 주어진 데이터의 특성에 따라 달라질 수 있습니다. 결정 트리 유도 알고리즘은 의료, 제조 및 생산, 금융 분석, 천문학, 분자 생물학 등 다양한 응용 분야에서 분류 작업에 활용되어 왔으며, 여러 상용 규칙 유도(rule induction) 시스템의 기반이 되기도 했습니다.
가지치기(Tree Pruning): 과적합 방지의 핵심
트리를 구성하는 동안에는 속성 선택 측도(attribute selection measure)를 사용하여 튜플들을 서로 다른 클래스로 가장 잘 분할하는 속성을 선택합니다. 그러나 결정 트리를 구축할 때 일부 분기에는 훈련 데이터에 포함된 노이즈(noise)나 이상치(outlier)가 반영될 수 있습니다. 가지치기(pruning)는 이러한 불필요한 분기를 식별하여 제거함으로써, 학습 과정에서 보지 못한(unseen) 데이터에 대한 분류 정확도를 높이는 것을 목표로 합니다.
대표 알고리즘: ID3, C4.5, CART
ID3, C4.5, CART와 같은 대표적인 알고리즘들은 탐욕적(greedy), 즉 역추적(backtracking)을 하지 않는 방식으로, 결정 트리를 하향식(top-down) 재귀적 분할 정복(divide-and-conquer) 방법으로 구축합니다. 대부분의 결정 트리 유도 알고리즘도 이와 같은 하향식 접근을 따르는데, 이는 클래스 레이블이 있는 훈련 튜플 집합에서 시작하여, 트리가 구축되는 동안 훈련 집합을 점진적으로 더 작은 부분집합들로 재귀적으로 분할해 나가는 방식입니다.