SECTION 01
1. 의사결정 트리의 개념과 기본 구조
의사결정 트리 (Decision Tree) 는 흥미있는 아이템을 분류하거나 평가하기 위한 절차를 그래픽으로 표현한 것이다. 예를들면, 환자의 증상이 주어졌을 때, 가능성 있는 진단명을 결정하고 치료 방법을 추천하기 위해 사용될 수 있다. 즉 축적해 놓은 자료로부터 환자의 증상에서 간염이라는 진단을 얻고 그래서 사망할 가능성을 예상하기 위해 decision tree 를 사용할 수 있다. 그것은 class 를 나타내는 문자나 수치로 해당 영역의 요소에 해당 범위의 요소를 매핑하여 기능을 표현한다. tree 의 내부 node 에서, 소수의 가능한 출력을 내는 하나의 테스트를 찾는다. 각 테스트의 결과에 따라 나누어서, 알고자하는 아이템과 같은 class 문자나 수치를 포함하는 잎 (leaf) 에 도달하게 된다. 각 leaf 는 그 leaf 로 떨어지는 각 class 의 예들의 갯수를 보여준다. 이러한 leaves 는 보통 하나의 class 가 아니며, 따라서 가장 흔하게 발생하는 class 문자를 선택하게 된다.
... 의사결정 트리는 일련의 속성을 가진 객체나 상황 (object or situation)을 입력으로 취해 yes/no 의 결정을 출력한다. 이럴 경우의 의사결정 트리는 불 함수 (Boolean function) 로 표현한다. 훨씬 더 넓은 범위의 출력을 가진 함수로 표현될 수도 있다 .... AITopics : Decision Tree Learning
계층적 트리 구조의 핵심 구성 요소
의사결정 트리는 컴퓨터 과학의 계층적 트리(Tree) 자료구조를 지도학습(Supervised Learning) 분류 및 회귀 문제에 적용한 대표적인 화이트박스(White-Box) 모델입니다. 데이터를 입력받아 마치 스무고개 놀이를 하듯 최적의 질문을 던져 공간을 점진적으로 분할해 나갑니다.
🌱 루트 노드 (Root Node)
전체 데이터셋이 위치하는 최상단 시작점입니다. 데이터의 전체 불확실성을 가장 크게 줄여줄 수 있는 최우선 속성(Feature)을 선정하여 최초의 분기를 수행합니다.
🌿 내부 노드 / 결정 노드 (Internal Node)
특정 속성의 조건(예: "나이 > 50", "혈당 ≥ 120", "혈액형 == A")에 대한 질문과 테스트를 수행하여 하위 브랜치로 데이터를 분류하는 중간 마디입니다.
🎋 가지 / 브랜치 (Branch / Edge)
노드의 속성 테스트 조건에 따른 분기 경로를 나타냅니다. 참(True)/거짓(False), 범주형 속성의 각 값들, 혹은 수치형 변수의 구간 분할을 통해 다음 노드로 연결됩니다.
🍂 리프 노드 / 단말 노드 (Leaf Node)
더 이상 분기가 일어나지 않는 트리의 최종 종착지입니다. 분류(Classification)에서는 다수결에 따른 최종 클래스 라벨(Class Label)을 할당하고, 회귀(Regression)에서는 속한 데이터들의 평균값(Mean Value)을 출력합니다.
SECTION 02
2. 의사결정 트리의 수학적 원리와 핵심 분할 알고리즘
의사결정 트리가 스스로 학습한다는 것은, "어떤 속성을 기준으로 데이터를 나누어야 가장 순수(Pure)하고 불확실성이 적은 하위 그룹들로 분할되는가?"를 수학적 목적함수에 따라 탐욕적(Greedy)으로 결정하는 과정입니다.
순도(Purity)와 불순도(Impurity)의 수학적 척도
1) 엔트로피 (Entropy) 와 정보 이득 (Information Gain) — ID3 알고리즘
클로드 섀넌(Claude Shannon)의 정보 이론에서 출발한 개념으로, 데이터 집합 $S$ 내의 무질서도와 불확실성을 수치화합니다. 클래스가 균등하게 섞여 있을 때 엔트로피는 최대가 되며, 하나의 클래스로만 이루어지면 0(완전한 순수 상태)이 됩니다.
■ 엔트로피 공식 (Entropy Formula) :
Entropy(S) = - ∑i=1c pi log2(pi)
(여기서 c 는 클래스의 총 개수이며, pi 는 데이터셋 S 에서 i 번째 클래스가 차지하는 비율)
특정 속성 $A$ 로 분할했을 때 엔트로피가 얼마나 감소했는가를 측정한 것이 정보 이득(Information Gain)입니다. ID3 알고리즘은 매 단계마다 정보 이득이 최대가 되는 속성을 분할 기준으로 선택합니다.
■ 정보 이득 공식 (Information Gain) :
Gain(S, A) = Entropy(S) - ∑v ∈ Values(A) (|Sv| / |S|) × Entropy(Sv)
2) 정보 이득 비율 (Gain Ratio) — C4.5 / C5.0 알고리즘
정보 이득(Information Gain)은 주민등록번호나 고객 ID처럼 고유값의 수가 매우 많은 속성을 선택할 때, 각 하위 노드가 순수해지는 착시가 생겨 과적합되는 치명적인 편향(Bias)이 존재합니다. 로스 퀸란(Ross Quinlan)은 이를 해결하기 위해 분할 자체의 고유 정보량을 패널티로 부여하는 분할 정보량(Split Information)을 도입하고 정보 이득 비율(Gain Ratio)을 제안하였습니다.
■ 분할 정보량 및 정보 이득 비율 (Gain Ratio Formula) :
SplitInfoA(S) = - ∑v (|Sv| / |S|) log2(|Sv| / |S|)
GainRatio(S, A) = Gain(S, A) / SplitInfoA(S)
3) 지니 불순도 (Gini Impurity) — CART 알고리즘
레오 브레이먼(Leo Breiman) 등이 개발한 CART(Classification and Regression Trees) 알고리즘은 로그 계산의 연산 오버헤드를 줄이고 실용적 성능을 높이기 위해 지니 불순도(Gini Index)를 도입하였습니다. 집합에서 임의로 추출한 원소가 무작위로 할당된 클래스와 일치하지 않을 확률을 의미합니다.
■ 지니 불순도 공식 (Gini Impurity) :
Gini(S) = 1 - ∑i=1c (pi)2
지니 불순도가 0일 때 가장 순수한 상태이며, 이진 분할(Binary Split)을 기반으로 하여 범주형 분류뿐만 아니라 분산 축소(Variance Reduction)를 통해 연속형 수치를 예측하는 회귀 트리(Regression Tree)까지 폭넓게 지원합니다.
대표적인 의사결정 트리 알고리즘 비교
| 알고리즘 |
개발자 / 연도 |
분할 척도 (Criterion) |
분기 형태 |
연속형 변수 / 결측값 |
| ID3 |
Ross Quinlan (1986) |
정보 이득 (Information Gain) |
다자 분기 (Multi-way) |
범주형 전용 / 결측값 미지원 |
| C4.5 / C5.0 |
Ross Quinlan (1993) |
정보 이득 비율 (Gain Ratio) |
다자 분기 (Multi-way) |
연속형 지원 / 결측값 자동 처리 / 사후 가지치기 |
| CART |
Breiman et al. (1984) |
지니 불순도 / 분산 감소량 (MSE) |
이진 분기 (Binary Split) |
분류 및 회귀 지원 / 연속형 최적화 / 비용복잡도 가지치기 |
| CHAID |
Gordon Kass (1980) |
카이제곱 통계량 (χ² Test) |
다자 분기 (Multi-way) |
통계적 유의성 기반 사전 가지치기 |
SECTION 03
3. 과적합(Overfitting)의 위험과 가지치기(Pruning) 전략
의사결정 트리는 분할을 거듭할수록 학습 데이터(Training Data)에 대한 분류 오차를 0으로 만들 수 있습니다. 그러나 트리가 지나치게 깊어지면 데이터 속에 포함된 불필요한 노이즈와 이상치(Outlier)까지 모두 외워버려, 새로운 테스트 데이터(Unseen Test Data)에 대한 예측력이 급격히 떨어지는 과적합(Overfitting) 현상이 발생합니다. 이를 통제하는 핵심 기법이 바로 가지치기 (Pruning)입니다.
🛑 1) 사전 가지치기 (Pre-pruning / Early Stopping)
트리가 완전히 성장하기 전에 특정 하이퍼파라미터 조건을 만족하면 분기를 조기에 중단하는 방식입니다.
- 최대 깊이 제한 (max_depth) : 트리가 내려갈 수 있는 층수를 제한
- 분할 최소 샘플 수 (min_samples_split) : 노드 분할을 허용할 최소 데이터 수 지정
- 리프 최소 샘플 수 (min_samples_leaf) : 단말 노드가 가져야 할 최소 샘플 수 강제
- 불순도 감소 최소치 (min_impurity_decrease) : 특정 기준 이상의 정보 이득이 없을 시 분할 중지
✂️ 2) 사후 가지치기 (Post-pruning / Cost-Complexity)
트리를 학습 데이터에 맞춰 최대로 성장(Full Tree)시킨 뒤, 하단부의 리프 노드부터 검증 데이터(Validation Set)의 성능을 평가하며 가지를 잘라내는 방식입니다.
- 비용-복잡도 가지치기 (Cost-Complexity Pruning, Minimal Cost-Complexity) : 오차율과 단말 노드 수의 가중합을 최소화
- 비용 함수 : Rα(T) = R(T) + α × |T| (여기서 |T| 는 리프 노드의 수, α 는 복잡도 패널티 계수)
- 사전 가지치기의 조기 종료(Horizon Effect) 약점을 극복하여 훨씬 견고한 일반화 성능을 제공
SECTION 04 · SPECIAL FOCUS
4. 의사결정 트리가 인공지능(AI)과 기계학습 발전에 기여한 결정적 역할
의사결정 트리는 단순한 하나의 통계적 분류기를 넘어, 현대 인공지능과 머신러닝의 패러다임을 형성하고 발전시키는 데 있어 가장 중요한 초석(Cornerstone) 역할을 하였습니다. 그 역사적·기술적 기여는 다음과 같이 4대 핵심 축으로 요약됩니다.
🌟 ① 설명 가능 인공지능(XAI)과 화이트박스(White-Box) 모델의 원형 확립
현대 딥러닝과 대규모 인공신경망은 탁월한 성능을 자랑하지만, 수억 개의 가중치 매개변수가 얽혀 왜 그러한 판단을 내렸는지 추적하기 어려운 '블랙박스(Black-Box)' 문제를 안고 있습니다. 반면, 의사결정 트리는 루트에서 리프까지 이어지는 경로가 곧 완벽한 논리적 IF-THEN 규칙의 집합입니다.
이러한 투명성(Transparency)과 해석 가능성(Interpretability) 덕분에, 의사결정 트리는 신뢰성과 설명 책임(Accountability)이 생명인 의료 진단(환자의 간염 진단 및 예후 예측), 금융 신용평가 및 대출 심사, 법률 판결 지원, 자율주행 안전 규제 등 고위험 의사결정 분야에서 타 모델의 검증 기준이자 가장 신뢰받는 의사결정 도구로 자리잡았습니다.
🌲 ② 앙상블 학습(Ensemble Learning)의 탄생과 현대 정형 데이터 AI의 제왕 등극
단일 의사결정 트리는 훈련 데이터의 사소한 변화에도 트리 구조가 크게 바뀌는 고분산(High Variance) 약점을 가집니다. 그러나 인공지능 연구자들은 이 약점을 역이용하여 "수많은 서로 다른 불안정한 트리들을 결합하면 기적적인 일반화 성능을 얻을 수 있다"는 앙상블(Ensemble) 혁명을 일으켰습니다.
📦 배깅 · 랜덤 포레스트 (Random Forest, 2001)
레오 브레이먼이 제안한 랜덤 포레스트는 부트스트랩 샘플링과 무작위 속성 선택을 통해 수백 개의 다양한 트리를 독립적으로 학습시키고 투표(Voting)하여 분산을 획기적으로 줄였습니다. 하이퍼파라미터 튜닝 없이도 강력한 성능을 발휘하는 실무 머신러닝의 표준이 되었습니다.
🚀 부스팅 · XGBoost / LightGBM / CatBoost
트리를 순차적으로 만들며 이전 트리의 잔차(Residual)와 오차를 학습하는 Gradient Boosting Machine(GBM)과 이를 고도화한 XGBoost, LightGBM은 캐글(Kaggle) 경진대회와 글로벌 IT 산업 현장의 정형 데이터(Tabular Data) 분석에서 딥러닝을 압도하는 절대적인 표준 알고리즘으로 군림하고 있습니다.
📊 ③ 데이터 마이닝과 지식 발견(KDD)의 실용적 자동화
전통적인 통계 모델이나 선형 회귀, 서포트 벡터 머신(SVM), 신경망은 데이터의 정규화(Normalization), 표준화(Standardization), 결측값 대체, 이상치 제거와 같은 복잡하고 정밀한 데이터 전처리 과정을 요구합니다.
그러나 의사결정 트리는 데이터의 스케일에 완전히 독립적(Scale Invariant)이며, 비선형적 상호작용과 다중공선성(Multicollinearity)에 영향을 받지 않습니다. 더욱이 학습 과정에서 노드 분할에 기여한 정도를 수치화하여 **특성 중요도(Feature Importance)**를 자동으로 계산해 줌으로써, 대규모 데이터셋에서 핵심 변수를 발굴하는 특성 선택(Feature Selection)의 핵심 방법론을 제공하였습니다.
🧩 ④ 기호주의(Symbolism)와 연결주의(Connectionism)의 가교 및 규칙 귀납
초기 인공지능(전문가 시스템 등)은 인간 전문가가 직접 손으로 IF-THEN 규칙을 작성해야 하는 "지식 획득의 병목(Knowledge Acquisition Bottleneck)"에 부딪혀 인공지능 겨울(AI Winter)을 겪었습니다. 의사결정 트리는 방대한 데이터로부터 컴퓨터가 스스로 최적의 기호적 규칙(Symbolic Rules)을 자동으로 귀납 학습(Inductive Learning)할 수 있음을 완벽하게 증명함으로써, 기호주의 AI의 한계를 극복하고 데이터 주도형 현대 머신러닝 시대를 개막한 결정적 도약대였습니다.
SECTION 06 · RESEARCH PAPERS
6. 학술 논문 및 연구 자료 (Research Papers)
의사결정나무 및 데이터마이닝 분야의 국내 주요 학술 연구 문헌 아카이브입니다. 원문 PDF 및 학회 정보 링크가 유지되어 있습니다.
저자 : 오을임, 김구 · 학회 : 한국행정학회 (2002)
SECTION 07 · SITES & TERMS
7. 관련 사이트 및 용어 색인 (Terms & Sites)
글로벌 전문 지식 사이트
aistudy 핵심 연관 용어 (Terms)
aistudy 인공지능 & 기계학습 포털