의사결정 트리 유도란?
의사결정 트리 유도(Decision Tree Induction)는 분류 모델을 구축하는 대표적인 머신러닝 기법 중 하나로, 데이터의 속성값에 따라 재귀적으로 분할을 수행하며 트리 형태의 예측 모델을 만듭니다. 이 기법은 여러 독특한 특징과 장단점을 지니고 있는데, 지금부터 하나씩 자세히 살펴보겠습니다.
의사결정 트리 유도의 핵심 특징
1. 비모수적(Non-parametric) 방법
의사결정 트리 유도는 분류 모델을 구축하는 비모수적 방법입니다. 즉, 클래스나 각 속성이 따르는 확률 분포의 형태에 대해 사전에 어떤 가정도 필요로 하지 않습니다. 덕분에 다양한 유형의 데이터에 폭넓게 적용할 수 있다는 장점이 있습니다.
2. 최적 트리 탐색은 NP-완전 문제
최적의 의사결정 트리를 찾는 문제는 NP-완전(NP-complete) 문제로 알려져 있습니다. 이 때문에 대부분의 의사결정 트리 알고리즘은 방대한 가설 공간(hypothesis space)에서 탐색을 효율적으로 진행하기 위해 휴리스틱(heuristic) 기반 접근 방식을 사용합니다.
3. 뛰어난 계산 효율성
계산 비용이 적게 드는 다양한 트리 구축 기법이 개발되어 있어, 학습 데이터셋의 규모가 매우 크더라도 모델을 신속하게 생성할 수 있습니다. 또한 한 번 트리가 완성되면 테스트 데이터를 분류하는 속도가 매우 빠릅니다. 최악의 경우에도 시간 복잡도는 O(w)이며, 여기서 w는 트리의 최대 깊이를 의미합니다.
4. 구현의 용이성
의사결정 트리, 특히 크기가 작은 트리는 상대적으로 구현이 간단합니다. 여러 데이터셋에서 그 성능 역시 다른 분류 기법들과 비교해 손색이 없는 수준을 보입니다.
5. 이산값 함수 학습에 대한 표현력
의사결정 트리는 이산값(discrete-valued) 함수를 학습하는 데 표현력이 뛰어난 설명 체계를 제공합니다. 다만 특정 유형의 불리언(Boolean) 문제에는 잘 일반화되지 못하는 한계가 있습니다. 대표적인 예가 패리티(parity) 함수로, 이 함수는 True 값인 불리언 속성의 개수가 홀수일 때 0, 짝수일 때 1을 반환합니다.
6. 중복 속성에 대한 강건성
중복(redundant) 속성이 존재하더라도 의사결정 트리의 성능에는 영향을 미치지 않습니다. 어떤 속성이 데이터 내 다른 속성과 강한 상관관계를 가지면 그 속성을 중복 속성이라고 합니다. 두 중복 속성이 분할에 함께 사용되는 일은 없는데, 하나가 이미 선택되었기 때문입니다.
7. 무관 속성과 특징 선택의 필요성
반면 데이터셋에 분류에 도움이 되지 않는 무관(irrelevant) 속성이 많이 포함되어 있다면, 트리 성장 과정에서 이런 속성들이 우연히 선택될 수 있으며, 그 결과 불필요하게 복잡한 트리가 만들어질 수 있습니다. 전처리 단계에서 특징 선택(feature selection) 기법을 적용해 무관한 속성을 제거하면 의사결정 트리의 정확도를 향상시킬 수 있습니다.
8. 데이터 파편화(Data Fragmentation) 문제
대부분의 의사결정 트리 알고리즘은 하향식(top-down) 재귀 분할 방식을 사용하기 때문에, 레코드들은 트리를 따라 내려갈수록 점점 작은 집합으로 나뉩니다. 리프 노드에 도달했을 때 데이터 수가 너무 적으면 해당 노드의 클래스 표현에 대해 통계적으로 유의미한 판단을 내리기 어렵습니다. 이를 데이터 파편화 문제라고 합니다. 한 가지 해결책은 레코드 수가 특정 임계값 이하로 떨어지면 더 이상 분할하지 않도록 제한하는 것입니다.
9. 서브트리 반복 및 복제 문제
하나의 서브트리(subtree)가 의사결정 트리 내에서 여러 번 반복해서 나타날 수 있습니다. 이 경우 트리가 실제 필요한 것보다 복잡해지고 해석과 구현이 어려워집니다. 이러한 현상은 각 내부 노드에서 단일 속성 검증 조건(single attribute test condition)에만 의존하는 트리 구조에서 발생하기 쉽습니다.
또한 일부 의사결정 트리 알고리즘은 분할 정복(divide-and-conquer) 방식의 분할 기법을 사용하기 때문에, 동일한 검증 조건이 속성 공간의 여러 부분에 걸쳐 반복 적용될 수 있으며, 이것이 서브트리 복제(subtree replication) 문제로 이어집니다.