의사결정나무 기본 개념
의사결정나무는 지도학습 분류 알고리즘 중 하나로, 데이터를 계층적으로 분할하며 결정 규칙을 도출합니다. 이 알고리즘은 다음과 같은 특징을 가집니다.
- 장점: 계산 비용이 적당하며, 결과가 직관적으로 해석 가능합니다. 또한 중간값 결측에 강건하고, 불필요한 특성이 포함된 데이터도 처리할 수 있습니다.
- 단점: 과적합(overfitting) 문제가 발생할 수 있습니다.
- 지원 데이터 타입: 연속형 수치 데이터와 범주형 데이터 모두 지원합니다.
핵심 원리: 정보 이득과 엔트로피
의사결정나무 구축 시 가장 중요한 것은 데이터를 가장 효과적으로 분할할 특성을 선택하는 것입니다. 이를 위해 정보 이득(Information Gain)을 기준으로 사용하며, 정보 이득은 엔트로피 감소량으로 정의됩니다.
엔트로피(Entropy)는 데이터의 무질서도를 측정하는 지표로, 정보 이론의 창시자인 클로드 섀넌(Claude Shannon)의 이름을 따서 섀넌 엔트로피라고도 합니다. 엔트로피가 높을수록 데이터가 혼합되어 있음을 의미합니다.
엔트로피 공식은 다음과 같습니다:
H(S) = -Σ p(x) × log₂(p(x))
여기서 p(x)는 특정 클래스의 확률을 나타냅니다.
Python 구현
ID3 알고리즘을 Python으로 구현해보겠습니다. 코드는 모듈화되어 있으며, 각 함수의 역할이 명확합니다.
import math
from collections import Counter
from typing import List, Any, Dict
def calculate_entropy(dataset: List[List[Any]]) -> float:
"""데이터셋의 엔트로피를 계산합니다."""
total_records = len(dataset)
class_frequencies = Counter(record[-1] for record in dataset)
entropy_value = 0.0
for frequency in class_frequencies.values():
probability = frequency / total_records
entropy_value -= probability * math.log2(probability)
return entropy_value
def generate_sample_data() -> tuple:
"""물고기 분류 예제 데이터셋을 생성합니다."""
dataset = [
[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']
]
feature_labels = ['물 위에 뜸', '오리발']
return dataset, feature_labels
def partition_data(records: List[List[Any]], feature_idx: int, value: Any) -> List[List[Any]]:
"""특정 특성과 값을 기준으로 데이터를 분할합니다."""
partitioned_records = []
for record in records:
if record[feature_idx] == value:
# 선택한 특성을 제외한 나머지 특성들로 새 레코드 구성
new_record = record[:feature_idx] + record[feature_idx + 1:]
partitioned_records.append(new_record)
return partitioned_records
def find_optimal_feature(records: List[List[Any]]) -> int:
"""정보 이득이 최대가 되는 특성의 인덱스를 반환합니다."""
feature_count = len(records[0]) - 1
base_entropy = calculate_entropy(records)
max_info_gain = 0.0
optimal_feature = -1
for idx in range(feature_count):
feature_values = [record[idx] for record in records]
unique_values = set(feature_values)
weighted_entropy = 0.0
for value in unique_values:
subset = partition_data(records, idx, value)
subset_probability = len(subset) / len(records)
weighted_entropy += subset_probability * calculate_entropy(subset)
info_gain = base_entropy - weighted_entropy
if info_gain > max_info_gain:
max_info_gain = info_gain
optimal_feature = idx
return optimal_feature
def get_majority_vote(classes: List[Any]) -> Any:
"""클래스 목록에서 가장 빈도가 높은 클래스를 반환합니다."""
class_counts = Counter(classes)
return class_counts.most_common(1)[0][0]
def build_tree(records: List[List[Any]], labels: List[str]) -> Dict:
"""재귀적으로 의사결정나무를 구축합니다."""
class_column = [record[-1] for record in records]
# 종료 조건 1: 모든 인스턴스가 동일한 클래스인 경우
if class_column.count(class_column[0]) == len(class_column):
return class_column[0]
# 종료 조건 2: 더 이상 분할할 특성이 없는 경우
if len(records[0]) == 1:
return get_majority_vote(class_column)
split_feature_idx = find_optimal_feature(records)
split_feature_label = labels[split_feature_idx]
tree_structure = {split_feature_label: {}}
remaining_labels = labels[:split_feature_idx] + labels[split_feature_idx + 1:]
split_values = [record[split_feature_idx] for record in records]
unique_split_values = set(split_values)
for value in unique_split_values:
subtree = build_tree(
partition_data(records, split_feature_idx, value),
remaining_labels
)
tree_structure[split_feature_label][value] = subtree
return tree_structure
실행 예제
구현된 코드를 실행하여 실제로 의사결정나무가 어떻게 구축되는지 확인해보겠습니다.
>>> dataset, feature_names = generate_sample_data()
>>> calculate_entropy(dataset)
0.9709505944546686
>>> dataset.append([1, 1, 'maybe'])
>>> calculate_entropy(dataset)
1.3709505944546687
엔트로피가 증가한 것은 데이터가 더 혼합되었음을 보여줍니다.
재귀적 구축 과정
의사결정나무는 재귀적으로 구축됩니다. 각 노드에서 최적의 특성을 선택하고, 데이터를 분할한 후 하위 노드에 대해 동일한 과정을 반복합니다. 재귀는 다음 조건에서 종료됩니다:
- 현재 노드의 모든 인스턴스가 동일한 클래스를 가질 때
- 더 이상 분할 가능한 특성이 없을 때 (이 경우 다수결로 클래스 결정)
ID3 알고리즘은 각 분할 시점마다 정보 이득이 최대화되는 특성을 선택하므로, 효율적인 분류 규칙을 생성합니다.