의사결정 트리(decision tree)는 흐름도(flowchart)와 유사한 구조를 가진 트리 형태의 예측 모델입니다. 각 내부 노드(internal node)는 특정 속성에 대한 검증(test)을 나타내고, 각 가지(branch)는 그 검증의 결과를 의미하며, 잎 노드(leaf node)는 최종 클래스 또는 클래스 분포를 나타냅니다. 트리의 가장 위에 있는 노드를 루트 노드(root node)라고 부릅니다.
의사결정 트리 학습 알고리즘
알고리즘 – 주어진 학습 데이터(training data)로부터 의사결정 트리를 생성합니다.
입력 – 이산값(discrete-valued) 속성으로 표현된 학습 샘플(samples), 그리고 속성들의 집합(attribute-list)
출력 – 의사결정 트리
알고리즘 절차
- 노드 N을 생성합니다.
- 모든 샘플이 동일한 클래스 C에 속한다면, 클래스 C 레이블을 가진 잎 노드로 N을 반환합니다.
- 속성 목록(attribute-list)이 비어 있다면, 샘플 중 가장 빈도가 높은 클래스(다수결, majority voting)로 레이블된 잎 노드로 N을 반환합니다.
- 속성 목록 중 정보 이득(information gain)이 가장 높은 속성을 검증 속성(test-attribute)으로 선택합니다.
- 노드 N을 검증 속성으로 레이블링합니다.
- 검증 속성의 각 알려진 값 ai에 대해 샘플을 분할(partition)합니다.
- 조건 test-attribute = ai에 해당하는 가지를 노드 N으로부터 생성합니다.
- test-attribute = ai를 만족하는 샘플들의 집합을 si라 정의합니다.
- 만약 si가 비어 있다면, 샘플 전체에서 가장 흔한 클래스로 레이블된 잎 노드를 연결합니다.
- 그렇지 않다면, Generate_decision_tree(si, attribute-list − test-attribute)가 반환하는 노드를 해당 가지에 연결합니다.
의사결정 트리 유도(Decision Tree Induction)
데이터로부터 의사결정 규칙을 자동으로 생성하는 과정을 규칙 유도(rule induction) 또는 자동 규칙 유도라고 합니다. 의사결정 트리를 구축하면서 암묵적으로 규칙을 만드는 것 역시 넓은 의미의 규칙 유도에 포함되지만, 일반적으로는 트리 유도(tree induction) 또는 의사결정 트리 유도라는 용어가 더 많이 사용됩니다.
의사결정 트리 유도의 기본 알고리즘은 탐욕적(greedy) 알고리즘입니다. 이 알고리즘은 하향식(top-down) 재귀적 분할 정복(divide-and-conquer) 방식으로 의사결정 트리를 생성하며, 유명한 의사결정 트리 유도 알고리즘인 ID3의 기본 형태이기도 합니다.
기본 알고리즘의 동작 방식
- 트리는 학습 샘플 전체를 대표하는 하나의 노드에서 시작합니다.
- 모든 샘플이 같은 클래스에 속한다면, 그 노드는 잎 노드가 되고 해당 클래스로 레이블링됩니다.
- 알고리즘은 샘플을 개별 클래스로 분할할 속성을 고르기 위한 휴리스틱으로, 엔트로피(entropy)에 기반한 측도인 정보 이득을 사용합니다. 선택된 속성은 노드의 "검증(test)" 또는 "판단(decision)" 속성이 됩니다. 이 형태의 알고리즘에서는 모든 속성이 범주형(categorical), 즉 이산값이어야 하므로, 연속형 속성은 사전에 이산화(discretization)해야 합니다.
- 검증 속성의 각 알려진 값마다 가지가 생성되며, 샘플들은 그에 맞게 분할됩니다.
- 각 분할 지점에서 남은 샘플들에 대해 동일한 과정을 재귀적으로 반복하여 의사결정 트리를 완성합니다. 한 번 노드에서 사용된 속성은 그 노드의 자손(descendant) 노드에서는 다시 고려되지 않습니다.
마무리: 의사결정 트리의 특징
의사결정 트리는 해석이 직관적이고 시각화가 쉬워 데이터 마이닝과 머신러닝 분야에서 널리 활용됩니다. 다만 학습 데이터에 과적합(overfitting)되기 쉬우므로, 실무에서는 가지치기(pruning)나 랜덤 포레스트(random forest)와 같은 앙상블 기법과 함께 사용하는 것이 일반적입니다.