Decision Tree

chelseey·2025년 4월 10일
패턴인식

XOR Problem

출력 y : XOR 연산의 결과
XOR 연산 : 두 입력이 다를 때 1, 같을 때 0을 반환
→ 같은 클래스에 속하는 점들이 서로 대각선 반대편에 위치

linear classifier의 한계 (ex.logistic regression)

→ 어떤 직선을 그어도 0과 1을 완벽히 분리할 수 없음

Decision Tree Example

Titanic dataset

Accuracy vs. Interpretability

머신러닝 알고리즘의
정확도(Accuracy)와 해석 가능성(Interpretability) 사이의 tradeoff

How to Make the Tree?

데이터를 재귀적으로 분할

전체 데이터를 하나의 노드(루트)로 시작하여,
각 노드에서 가장 좋은 기준을 찾아 데이터를 여러 하위 집합으로 분할
이 과정을 재귀적으로(recursive) 반복하면서,
각 노드의 데이터가 가능한 한 하나의 클래스(라벨)에 가까워지도록 함

분할 방식

  • 분할 변수 (Split Variable) 선택
    각 노드에서 데이터를 나누기 위해 선택하는 feature

  • 분할 값 (Split Value) 선택
    선택된 특징에 대해,
    데이터를 두 그룹(이상)으로 나누기 위한 임계치(threshold) 또는 값

분할 기준(Criteria) – Purity와 Impurity

: 노드의 데이터가 얼마나 잘 분리되었는지를 평가하는 척도

  • Purity (순도)
    한 노드에 포함된 샘플들이 한 가지 클래스에 치우쳐 있는 정도

  • Impurity (불순도)
    클래스가 섞여 있는 정도

Impurity (측정 방법)

Classification Error (Misclassification Rate)

: 현재 노드 t에서 가장 많은 클래스가 아닌 나머지 클래스의 비율을 모두 더한 값

Error(t)=∑j≠lp(j∣t),l=arg⁡max⁡ip(i∣t)\text{Error}(t) = \sum_{j \neq l} p(j|t) , l = \arg\max_i p(i|t)

tt : 현재 노드
p(j∣t)p(j|t) : 노드 t에 있는 샘플들 중 클래스 j일 확률
ll : 노드에서 가장 많이 등장한 우세 클래스(majority class)

• Binary Case (이진 분류의 경우)

0≤Error(t)≤0.50 ≤ Error(t) ≤ 0.5

모든 샘플이 한 클래스일 경우 오류는 0
두 클래스가 정확히 1:1이면 오류는 0.5

Gini index

: 노드에 포함된 데이터가 얼마나 섞여 있는지를 측정

GINI(t)=1−∑jp(j∣t)2GINI(t) = 1 - \sum_{j} p(j|t)^2

p(j∣t)p(j|t) : 노드 t에서 클래스 j가 나올 확률
∑jp(j∣t)2\sum_{j} p(j|t)^2 : 각 클래스 비율의 제곱을 더한 값

• Binary Case (이진 분류의 경우)

GINI(t)=∑i≠jp(i∣t)p(j∣t)=2⋅p(0∣t)⋅p(1∣t)GINI(t) = \sum_{i \neq j} p(i|t)p(j|t) = 2 \cdot p(0|t) \cdot p(1|t)
0≤GINI(t)≤0.50≤GINI(t)≤0.5

최솟값 0 : 노드가 모두 한가지 클래스일 경우
최댓값 0.5 : 클래스가 50:50으로 섞여 있을 때 (최대 불순도)

Entropy

: 데이터의 혼잡도(불확실성)를 측정

노드에 클래스가 섞여 있을수록 → 엔트로피 ↑
한 클래스만 있을수록 → 엔트로피 ↓ (순수함)

Entropy(t)=−∑jp(j∣t)log⁡2p(j∣t)Entropy(t) = -\sum_{j} p(j|t) \log_2 p(j|t)

t : 현재 노드
j : 클래스 index
p(j∣t)p(j|t) : 노드 t에서 클래스 j가 나올 확률
→ 각 클래스의 (비율 × 그 비율의 로그값)을 계산하고, 그 합의 음수값

• Binary Case (이진 분류의 경우)

0≤Entropy(t)≤10≤Entropy(t)≤1

클래스가 하나로 완전히 몰려 있으면 → Entropy = 0 (완전 순수)
클래스가 50:50으로 섞여 있으면 → Entropy = 1 (최대 불순도)

Impurity 민감도 순서

Entropy > Gini > Class Error

Information Gain

: 결정 트리에서 어떤 분할이 얼마나 좋은지를 평가하기 위한 기준
(부모 노드의 불순도(Impurity) - 자식 노드들의 가중 평균 불순도) 값으로 정의

Gain=Impurity부모−Impurity자식Gain = \text{Impurity}_{\text{부모}} - \text{Impurity}_{\text{자식}}
=Impurity부모−∑iNiN×Impurity자식i= \text{Impurity}_{\text{부모}}-\sum_i \frac{N_i}{N} \times \text{Impurity}_{\text{자식}_i}

NiN_i : 자식 노드의 샘플 수
NN : 부모 노드의 전체 샘플 수

부모 노드의 불순도에서 자식 노드의 가중 평균 불순도를 뺀 값이 크다
→ 분할 전보다 순도가 많이 개선되었다
→ Information Gain 클수록 좋음

Information Gain Ratio

Information Gain만 사용할 때의 문제점

카테고리형 변수의 값이 매우 다양하여 고유값이 많다면,
각 고유값마다 한두 개의 샘플로 매우 작은 자식 노드가 생성
→ 자식 노드들이 거의 모두 순수하게 되어 (불순도 = 0)
정보 이득이 매우 크게 측정될 수 있음
but 과도하게 데이터를 쪼개 overfitting

SplitInfo

: 분할 자체가 얼마나 세분화되었는지를 측정하는 값으로,
자식 노드에 할당된 샘플 비율을 바탕으로 엔트로피처럼 계산

SplitInfo=−∑iNiNlog⁡2NiN\text{SplitInfo} = - \sum_i \frac{N_i}{N} \log_2 \frac{N_i}{N}

정보 이득 비율 (Gain Ratio)

: 정보 이득을 분할 정보량으로 나눈 값

→ 정보 이득이 큰 분할이라 하더라도,
분할이 지나치게 세분화되어 있다면 (SplitInfo가 큰 경우) 값을 보정해 줌

GainRatio=Information GainSplitInfo\text{GainRatio} = \frac{\text{Information Gain}}{\text{SplitInfo}}

과도하게 자식을 많이 만드는 분할의 경우
Gain Ratio가 낮게 측정되어 선택되지 않도록 함

Regression Problem

t-statistic

: 두 그룹의 평균 차이가 우연에 의한 것인지,
아니면 통계적으로 유의한 차이가 있는지를 판단하기 위한 통계량
→ 분할의 효과를 평가

Variance

: 데이터가 평균 주변에서 얼마나 흩어져 있는지를 나타내는 지표

노드 내 분산이 낮으면 그 노드 내 데이터가 평균값 주변에 몰려 있어
예측 오차가 작아짐
최종 모델의 예측력이 향상되고,
노드별 예측 값(보통 평균값)과 실제 값 사이의 오차가 줄어듦

→ 회귀 트리의 분할 기준 : 분할 시 부모 노드의 전체 분산과 자식 노드들의 가중 분산의 합을 비교하여, 이 차이가 최대가 되는 분할 (자식 노드 분산 합이 최소인 경우)을 선택

Stopping Rule

: 트리의 성장을 언제 멈출지 결정
→ 과적합(overfitting)을 방지, 모델의 복잡도를 제어

기본 조건 (Obvious Conditions)

  • 모든 인스턴스가 동일한 클래스에 속할 때
    : 현재 노드에 있는 모든 데이터가 같은 클래스
    → 이미 순수한 노드이므로 더 이상 분할할 필요가 없음

  • 모든 속성(attribute) 값이 동일할 때
    : 현재 노드의 모든 인스턴스가 모든 속성에서 동일한 값을 가짐
    → 추가 분할 시 아무런 정보도 제공하지 않으므로 멈춤

• 클래스와 속성
속성 : 입력 데이터의 특성을 설명하는 변수이며
클래스 : 예측하고자 하는 결과나 카테고리
→ 각 속성 값들은 모델이 대학 입학 여부(클래스)를 예측하는 데 사용

보다 제한적인 조건 (More Restrictive Conditions)

  • 트리의 깊이 제한 (Depth Threshold)
    : 사용자가 사전에 정의한 최대 깊이(maximum depth)에 도달하면,
    더 이상 분할을 진행하지 않음

  • 최소 인스턴스 수 (Minimum Number of Instances)
    : 노드에 포함된 인스턴스의 수가 사용자가 정의한 최소한의 값보다 작으면, 더 이상 분할하지 않음

  • 불순도 감소의 유의미성 (Significant Decrease in Impurity)
    : 분할 후, 불순도(Gini, Entropy)가 사용자가 지정한 임계값(threshold)보다 크게 감소하지 않는다면, 더 이상 분할하지 않음

Prediction Method

루트 노드에서 시작하여, 조건(분할 규칙)을 따라 leaf 노드까지 내려가서 최종적으로 도달한 leaf 노드의 정보를 사용합니다.

분류 문제 (Classification)

: 예측하고자 하는 데이터가 분류되어 들어간 그 하나의 leaf 노드에 저장된 클래스 분포 중 다수 클래스를 예측값으로 사용

회귀 문제 (Regression)

: 예측하고자 하는 데이터가 분류되어 들어간 그 하나의 leaf 노드에 속한 값들의 평균을 예측값으로 반환

Pruning

결정 트리가 과적합(overfitting)되는 것을 막기 위해,
완전히 성장한(full grown) 트리에서 불필요한 가지(branch)를 제거하는 방법
→ 모델의 복잡도를 줄이고, 새로운 데이터에 대한 일반화 성능을 향상

  • Reduced-error Pruning (오차 축소 프루닝)

  • Cost-complexity Pruning (비용-복잡도 프루닝)

  • Rule Post-pruning (규칙 기반 후처리 프루닝)

Reduced-Error Pruning

1. 하위 노드에서부터 non-leaf 노드를 점검

트리의 가장 아래쪽, leaf 노드에 인접한 non-leaf 노드부터 점검

2. 임시로 가지 치기 (Temporary Pruning)

평가할 non-leaf 노드에서 그 아래 모든 자식 노드를 제거하고,
해당 노드를 임시 잎 노드(leaf node)로 만듦

임시 잎 노드에 소속된 학습 데이터의 다수 클래스를 찾아,
그 클래스를 임시 잎 노드의 예측 값으로 설정

3. 검증 집합을 통한 성능 평가

임시로 가지치기한 후의 트리를 사용하여
검증 집합(validation set)에 대한 예측 정확도를 측정

  • 프루닝 후의 트리가 원래 트리와 비교하여 성능이 같거나 더 나은 경우
    해당 프루닝을 수용(accept)
  • 프루닝 후 성능이 떨어진 경우
    임시 프루닝을 되돌려(undo) 원래 상태로 복원

4. 상향 방향으로 반복 진행

위의 과정을 모든 non-leaf 노드에 대해 수행
프루닝은 하위 노드부터 상위 노드로 점차 이동하며 적용

5. 종료 조건

모든 non-leaf를 평가한 후,
프루닝을 적용해도 검증 집합에 대한 성능이 더 이상 개선되지 않는다면 알고리즘은 종료

Cost-Complexity Pruning

비용 함수 (Cost Function)

Cα(T)=R(T)+α⋅∣T∣C_\alpha(T) = R(T) + \alpha \cdot |T|

R(T)R(T): 트리 T의 예측 오차(또는 불순도)

∣T∣∣T∣: 트리의 복잡도를 나타내는 지표, leaf node의 수
→ 잎 노드 수가 많을수록 트리가 복잡

αα: 복잡도에 부과하는 Penalty 계수

1. 초기 트리: fully grown 트리로 시작

2. α에 따른 서브트리 생성:

α=0에서부터 α 값을 증가시키면서,
비용 함수 Cα(T)C_\alpha(T)를 최소화하는 서브트리 T(α)들을 생성

α가 증가하면 불필요한 가지들이 제거되어 트리가 점차 단순해짐 (노드 수 감소)
생성되는 트리들은 nested (서로 포함)하는 구조를 이룸
→ 큰 α에 해당하는 트리는 작은 α'에 해당하는 트리의 부분집합

3. 최적의 트리 선택:

생성된 여러 개의 서브트리
T(α1),T(α2),…T(\alpha_1), T(\alpha_2), \dots 중에서, 검증 집합(validation set)에 대한 예측 성능이 가장 우수한 트리를 선택

Rule Post-Pruning

1. 트리를 규칙 집합으로 변환

결정 트리의 각 잎 노드까지 도달하는 경로를 하나의 규칙으로 표현
ex. "Outlook = sunny", "Humidity = high" 조건을 거쳐
leaf 노드에서 "No"라는 클래스로 분류될 경우

Outlook = sunny ∧ Humidity = high → No

2. 규칙에서 조건(antecedent) 가지치기

생성된 규칙에서 한 번에 하나씩 조건을 제거해 봄
ex. 위의 규칙에서 "Outlook = sunny" 또는 "Humidity = high" 중 하나를 제거하여 다음과 같은 후보 규칙들을 만듦

후보 1: Outlook = sunny → No
후보 2: Humidity = high → No

3. 각 후보 규칙 평가

각 후보 규칙을 검증 집합(validation set)에 적용하여 예측 성능을 측정

  • 조건을 제거한 후 성능이 유지되거나 오히려 개선
    해당 조건은 규칙에서 제거해도 무방하다고 판단
  • 조건 제거로 인해 성능이 나빠짐
    조건은 반드시 포함되어야 하는 중요한 조건

4. 최종 규칙 선택 및 정렬

각 규칙에 대해 조건 제거를 반복하여
최종적으로 가장 간단하면서도 예측 성능을 유지하는 규칙을 선택

최종적으로 얻어진 규칙들을 검증 데이터 기준으로 성능이 좋은 순서대로 정렬
→ 새로운 데이터를 예측할 때 어떤 규칙부터 적용할지 결정하는 데 사용

Various Decision Trees

CART (Classification And Regression Tree)

분류 문제와 회귀 문제에 모두 사용할 수 있는 알고리즘

각 노드에서 데이터를 두 개의 하위 집단으로만 분할
→ 분할 기준 : 분류 문제에서는 Gini 불순도(Gini index),
회귀 문제에서는 분산(variance) 감소량을 사용

특징:

분할 시 항상 두 그룹으로 나누기 때문에 트리 구조가 단순하고 해석하기 쉬움
회귀 트리의 경우, 각 잎 노드에 있는 값들의 평균을 예측값으로 사용

C4.5

C4.5는 각 노드에서 하나의 속성에 대해 여러 개의 하위 집단으로 분할
→ 연속형 속성의 경우 구간을 나누거나,
범주형 속성의 모든 값을 고려하여 다중 분할이 가능

분할 기준으로 엔트로피(Entropy)와 Information Gain, 그리고 정보 이득 비율(Gain Ratio)을 사용
→ 각 분할이 데이터의 불확실성을 얼마나 줄이는지를 평가

특징:

분할 시 여러 개의 Branch를 허용하기 때문에,
노드가 더 세분화되어 복잡한 데이터 분포를 잘 설명할 수 있음
Information Gain Ratio를 사용해,
고유값이 많은 속성으로 인한 과도한 분할을 보정

CHAID (CHi-squared Automatic Interaction Detection)

하나의 속성에 대해 여러 개의 하위 집단으로 데이터를 분할 가능

카이제곱(χ²χ²) 통계량을 사용하여 각 범주 간의 독립성을 판단
→ 분할 시 각 범주 간의 차이가 통계적으로 유의한지를 판단하여,
유의한 차이가 있는 경우에만 분할을 수행

특징:

분할 과정에서 통계적 검정을 사용하기 때문에,
분할이 의미 있는 차이에 기반함을 보장
범주형 변수에 강점을 보이며,
다중 분할을 통해 데이터의 상호작용(interaction)을 잘 포착

Back to XOR Problem

XOR 문제는 데이터가 대각선 방향으로 교차되어 있어
linear classifier(직선)로는 분리가 불가능함

  • 가로 선 (x₂ 기준)
    빨간 점선은 x₂ 값 기준으로 위아래로 데이터를 나눔

  • 세로 선 (x₁ 기준)
    x₁ 기준으로 수직 파란 점선으로 한 번 더 분할

→ 4개의 사각형 영역이 생기고, 각 영역에는 하나의 클래스만 존재하도록 분리

색으로 구분된 영역 (초록 / 노랑)마다 한 클래스만 존재하도록 잘 분리되어 있음
결정 트리는 x₁ 또는 x₂ 기준으로 반복적으로 나누면서
복잡한 비선형 경계도 표현 가능

Classification and Regression Decision Trees

분류(Classification) 결정 트리

• 트리 구조
트리의 각 내부 노드는 조건을 사용해 데이터를 두 개 이상의 그룹으로 나눔
최종 leaf node에는 데이터들이 모여 있고, 각 데이터들의 클래스가 기록되어 있음

• 예측
트리를 통해 분할한 후 도착한 leaf node에서 다수결(Majority Voting)로 예측

회귀(Regression) 결정 트리

• 트리 구조
분류 트리와 마찬가지로 조건을 사용해 데이터를 여러 구간으로 나누지만, 여기서는 타깃 변수(ex. 집값, 온도 등)가 연속적인 수치
최종 leaf node에는 해당 구간에 속한 연속형 값들이 저장됨

• 예측
새로운 데이터를 트리를 통해 분할한 후 도착한 leaf node의 데이터 값들의 평균값을 예측 결과로 사용

profile
chelseey
이전 포스트

Methods to Prevent Overfitting

다음 포스트

Model Evaluation and Validation

0개의 댓글