의사결정 트리(decision tree)는 흐름도(flow-chart)와 유사한 형태의 트리 구조입니다. 각 내부 노드(internal node)는 특정 속성에 대한 검사(test)를 나타내고, 각 가지(branch)는 그 검사의 결과를 정의하며, 잎 노드(leaf node)는 최종 클래스 또는 클래스 분포를 설명합니다. 트리에서 가장 상위에 위치한 노드를 루트 노드(root node)라고 합니다.
의사결정 트리의 재귀적 구성 절차
의사결정 트리를 구성하는 문제는 재귀적으로 정의할 수 있습니다. 먼저 루트 노드에 배치할 속성을 하나 선택하고, 해당 속성이 가질 수 있는 각 값마다 하나의 가지를 만듭니다. 이 과정에서 전체 예제 집합은 속성 값별로 여러 부분 집합으로 나뉩니다.
이 절차는 각 가지에 대해, 해당 가지에 도달한 인스턴스들만을 대상으로 재귀적으로 반복됩니다. 만약 어떤 노드에 도달한 인스턴스들이 모두 동일한 분류를 가진다면, 그 지점에서 더 이상 트리를 확장하지 않고 종료합니다.
순도의 척도: 정보(Information)
노드의 순도(purity)를 측정하는 데 사용되는 척도는 정보(information)이며, 비트(bit)라는 단위로 표현됩니다. 트리의 각 노드에는 이 정보 값이 연관되어 있으며, 해당 노드에 도달한 인스턴스들이 주어졌을 때 새로운 인스턴스를 '예(yes)' 또는 '아니오(no)'로 분류하기 위해 필요한 예상 정보량을 나타냅니다. 정보 이득(information gain)이 가장 큰 속성을 우선적으로 선택하는 것이 효율적인 트리 구성의 핵심입니다.
가지치기(Pruning)란 무엇인가?
가지치기(pruning)는 의사결정 트리의 크기를 줄이는 절차입니다. 트리의 크기를 제한하거나 분류 능력이 거의 없는 영역을 제거함으로써 과적합(overfitting)의 위험을 줄이는 데 활용됩니다.
학습 데이터에는 노이즈(noise)나 이상치(outlier)가 포함되기 쉽습니다. 가지치기는 이러한 이상 현상에 지나치게 맞춰진 가지들을 잘라내어, 트리의 일반화 성능(generalization performance)을 향상시킵니다.
또한 많은 방법들이 통계적 측정값을 활용해 신뢰도가 낮은 가지들을 제거합니다. 그 결과 분류 속도가 빨라지고, 독립적인 테스트 데이터를 보다 정확하게 분류하는 능력이 향상되는 효과를 얻을 수 있습니다.
의사결정 트리 학습 알고리즘
알고리즘(Algorithm) — 주어진 학습 데이터(training data)로부터 의사결정 트리를 생성합니다.
입력(Input) — 이산형(discrete-valued) 속성으로 기술된 학습 샘플(samples), 그리고 후보 속성들의 집합(attribute-list).
출력(Output) — 의사결정 트리.
방법(Method)
- 노드 N을 생성한다.
- 만약 samples가 모두 동일한 클래스 C에 속한다면,
- 클래스 C로 라벨링된 잎 노드로서 N을 반환한다.
- 만약 attribute-list가 비어 있다면(null),
- samples에서 가장 빈번하게 나타나는 클래스로 라벨링된 잎 노드로서 N을 반환한다. // 다수결 투표(majority voting)
- attribute-list 중 정보 이득(information gain)이 가장 큰 속성을 골라 test-attribute로 지정한다.
- 노드 N을 test-attribute로 라벨링한다.
- test-attribute의 각 알려진 값 ai에 대해 // 샘플을 분할(partition)한다.
- 조건 test-attribute = ai에 대해 노드 N으로부터 가지를 하나 확장한다.
- si를 samples 중 test-attribute = ai를 만족하는 샘플들의 집합이라 하자.
- 만약 si가 비어 있다면,
- samples에서 가장 일반적인 클래스로 라벨링된 잎 노드에 연결한다.
- 그렇지 않으면, Generate_decision_tree(si, attribute-list − test-attribute)가 반환하는 노드를 해당 가지에 연결한다.