의사 결정 트리 학습은 기계 학습에서 분류 및 회귀 작업 모두에 사용되는 지도 학습 방법이다. 모델은 내부 노드가 입력 특성에 대한 테스트를 나타내고, 분기는 해당 테스트의 결과를 나타내며, 리프 노드는 최종 예측 값 또는 클래스 레이블을 나타내는 트리 구조이다. 목표는 특성 공간을 목표 변수에 대해 가능한 한 동질적인 영역으로 분할하여 해석하기 쉬운 일련의 if-then-else 규칙을 만드는 것이다.
의사 결정 트리를 구축하는 과정은 선택된 분할 기준에 따라 훈련 데이터를 가장 잘 분리하는 특성을 재귀적으로 선택하는 것을 포함한다. 일반적인 기준으로는 정보 이론의 엔트로피에 기반한 정보 이득과, 무작위로 선택된 요소가 부분 집합의 레이블 분포에 따라 무작위로 레이블이 지정될 때 잘못 레이블이 지정될 빈도를 측정하는 지니 불순도가 있다. 트리는 모든 훈련 예제를 포함하는 루트 노드에서 시작하여 위에서 아래로 성장하며, 최대 깊이에 도달하거나, 리프당 최소 샘플 수를 가지거나, 추가 분할이 기준을 개선하지 못하는 경우와 같은 중지 조건이 충족될 때까지 계속된다.
역사적 발전
의사 결정 트리의 개념은 1963년 Morgan과 Sonquist가 Automatic Interaction Detection(AID) 시스템을 개발한 1960년대로 거슬러 올라간다. 이 초기 작업은 1970년대에 다른 분할 기준을 사용한 THAID 알고리즘으로 이어졌다. 이 분야는 1986년 Ross Quinlan이 정보 이득을 분할 기준으로 사용한 ID3 알고리즘을 도입하면서 1980년대에 큰 추진력을 얻었다. Quinlan은 이후 1993년에 C4.5를 개발하여 연속 속성, 누락 값 및 가지치기를 처리함으로써 ID3를 개선했다. 같은 시기에 Leo Breiman, Jerome Friedman, Richard Olshen, Charles Stone이 1984년에 Classification and Regression Trees(CART) 알고리즘을 도입했다. CART는 분류에 지니 불순도를, 회귀에 평균 제곱 오차를 사용했으며 가장 널리 사용되는 의사 결정 트리 알고리즘 중 하나가 되었다.
주요 알고리즘 및 변형
수년에 걸쳐 각각 고유한 특성을 가진 여러 의사 결정 트리 알고리즘이 개발되었다. ID3와 그 후속인 C4.5는 주로 분류에 사용되며 범주형 및 연속 특성(C4.5)을 모두 처리할 수 있다. CART는 분류 및 회귀 트리를 모두 지원하는 다재다능한 알고리즘으로, 각 내부 노드에 정확히 두 개의 분기가 있는 이진 트리를 생성한다. 1980년에 도입된 CHAID(Chi-squared Automatic Interaction Detection) 알고리즘은 카이제곱 테스트를 사용하여 최상의 분할을 결정하고 다중 분할을 생성할 수 있다. 더 최근의 알고리즘으로는 회귀를 위한 M5 알고리즘과 데이터의 무작위 부분 집합에 많은 의사 결정 트리를 구축하고 예측을 평균화하여 과적합을 줄이는 Random Forest 앙상블 방법이 있다.
장점 및 한계
의사 결정 트리는 학습된 모델을 인간이 쉽게 이해할 수 있는 순서도로 시각화할 수 있기 때문에 해석 가능성으로 인해 널리 사용된다. 정규화나 스케일링과 같은 데이터 전처리가 거의 필요하지 않으며 숫자 및 범주형 데이터를 모두 처리할 수 있다. 그러나 의사 결정 트리는 특히 전체 깊이로 성장할 때 훈련 데이터의 노이즈를 포착할 수 있으므로 과적합되기 쉽다. 또한 훈련 데이터의 작은 변동에 민감하여 약간의 변경으로 완전히 다른 트리가 생성될 수 있다. 또한 의사 결정 트리는 더 많은 분할을 생성하고 더 유익해 보이는 경향이 있으므로 수준이 많은 특성에 편향될 수 있다. 이러한 문제를 완화하기 위해 가지치기, 최소 리프 크기 설정, Random Forest 및 Gradient Boosting과 같은 앙상블 방법과 같은 기술이 일반적으로 사용된다.
응용 및 현대적 맥락
의사 결정 트리 학습은 의료 진단, 신용 위험 평가, 고객 이탈 예측 및 이미지 인식을 포함한 다양한 분야에 적용되었다. 현대 인공 지능의 맥락에서 의사 결정 트리는 종종 Gradient Boosting Machines(GBM) 및 XGBoost와 같은 앙상블 방법의 기본 학습기로 사용되며, 많은 구조화된 데이터 대회에서 최첨단 결과를 달성했다. 딥 러닝 모델과 같은 신경망은 이미지 및 음성 인식과 같은 비구조화된 데이터 작업을 지배하지만, 의사 결정 트리는 효율성과 해석 가능성으로 인해 표 형식 데이터에 강력한 선택으로 남아 있다. 또한 잔차 네트워크 아키텍처와 같은 다른 기술과 결합하여 사용되지만, 이는 주로 딥 러닝 개념이다. 의사 결정 트리의 단순성과 견고성은 학술 연구와 산업 응용 모두에서 지속적인 관련성을 보장한다.
소프트웨어 및 구현
많은 소프트웨어 라이브러리가 의사 결정 트리 알고리즘의 구현을 제공한다. Python의 scikit-learn 라이브러리는 최적화된 CART 버전을 기반으로 하는 DecisionTreeClassifier 및 DecisionTreeRegressor 클래스를 제공한다. R에는 재귀 분할을 위한 rpart 패키지와 조건부 추론 트리를 위한 party 패키지가 있다. 데이터 마이닝 작업을 위한 기계 학습 알고리즘 모음인 Weka에는 J48(C4.5의 Java 구현) 및 REPTree의 구현이 포함되어 있다. 이러한 도구를 통해 실무자는 의사 결정 트리 모델을 쉽게 구축, 시각화 및 평가할 수 있어 이 기술을 광범위한 사용자에게 접근 가능하게 만든다.