Decision Tree

• 정의: 특정 기준에 따라 데이터를 구분하는 트리 구조의 모델
• 특징
  • Classification과 Regression 모두 가능한 non-parametric 지도 학습 모델
  • 전체적인 모양이 나무를 뒤집어 놓은 것과 같음. → 이름이 Decision Tree
• 용어
  • Node: 네모 상자. 한 마디.
  • Root Node: 뿌리 마디. 나무가 시작되는 마디.
  • Intermediate Node: 중간 마디.
  • Terminal Node: 맨 마지막 마디. 나무의 끝에 위치하는 마디.
  • Depth: 가지를 이루고 있는 마디의 개수
  • Parent Node: 상위 마디
  • Child Node: 하위 마디. 한 마디로부터 분리되어 나간 2개 이상의 마디
• 작동원리
  • 각 노드로 내려오면서 해당 노드에서 데이터를 가장 잘 구분할 수 있는 질문을 기준으로 데이터를 구분한다.
  • 부모마디로부터 자식마디가 형성될 때, 어떤 feature로 분리하는 구분 기준은 트리 종류, 타깃 변수의 종류에 따라 다르다.

구분	CHAID 계열	Quinlan 계열 (ID3 / C4.5 / C5.0)	CART 계열
Regression (회귀)	F 통계량, p-value	–	분산 감소량 (Variance Reduction)
Classification (분류)	χ² 통계량, p-value	엔트로피(Entropy), 정보이득비(Gain Ratio)	지니지수(Gini Index)

 

• Overfitting을 막기 위한 방법과 HyperParameter
  • prunning: 트리를 완전히 만든 뒤, 불필요한 가지를 제거
    • Decision Tree의 분기수가 증가할 때 처음에는 새로운 데이터의 오분류율이 감소하나, 일정 수준 이상이 되면 오분류율이 되레 증가하는 현상이 발생한다. 이러한 문제를 해결하기 위해 pruning(가지치기)를 한다. pruning이란 전체 트리를 만든 다음 오분류율이 다시 증가하는 시점에서 적절히 가지를 쳐주는 것을 말한다. 이때 pruning의 기준은 1. valid set의 결과, 2. chi-square test, 3. loss function 등을 이용해 정한다.
  • max_depth: 트리의 최대 깊이(층 수)를 미리 제한
    

    

    max_depth를 3으로 셋팅했을 때

  • max_features
    • 최적의 분할을 위해 고려할 최대 feature 개수 (feature 수가 많아지면 트리의 복잡도가 커지므로 이를 조절하기 위한 하이퍼파라미터). 디폴트는 None. auto일 경우 제곱근.
  • min_samples_split
    • 노드를 분할하기 위한 최소한의 샘플 데이터 수: 리프노드가 되기 위한 최소 샘플 수를 조절함으로써 트리의 깊이를 조절한다.
  •  min_samples_leaf
    • 분할될 때 왼쪽 오른쪽 리프노드(자식노드들)에서 가져야 할 최소 샘플 데이터 수.
• Classification split Criterion
  • Gini Impurity: 임의로 하나의 샘플을 선택했을 때, 그것이 잘못 분류될 확률. 즉, 한 노드의 클래스 분포가 얼마나 “섞여 있는지”를 측정하는 지표
    • 수식:
      

      

    • 예시 

      클래스	비율 p_i	(p_i^2)
      A	0.5	0.25
      B	0.5	0.25
      합계		(1 - (0.25 + 0.25) = 0.5)

      → 지니값 0.5: 완전히 섞인 상태 (불순도 높음)
      → 지니값 0: 한 클래스만 존재 (순수 노드)
  • Entropy/Information Gain
    • Entropy: 한 노드 내의 데이터 불확실성(혼잡도)을 나타내는 지표. 엔트로피가 높을수록, 해당 노드의 데이터가 다양하게 섞여있다는 뜻
      • 수식:
        

        

      • 예시:
        

        클래스	비율 (p_i)	(-p_i * log_2(p_i))
        A	0.5	0.5
        B	0.5	0.5
        합계		1.0

        → Entropy = 1 → 완전히 섞임 (불확실성 최대)
        → Entropy = 0 → 한 클래스만 있음 (순수)
    • Information Gain(정보 이득): 부모 노드의 엔트로피에서 자식 노드들의 엔트로피 가중평균을 뺀 값으로, 얼마나 불확실성이 줄어들었는가(정보가 개선되었는가)를 나타냄
      • 수식:
        

        

      • 의미: Information Gain이 클수록 좋은 split. 즉, 엔트로피를 가장 많이 줄이는 feature를 선택한다. 
• 장점
  1. 쉽고 직관적이고, 모델 구조를 시각적으로 그려서 해석하기 쉽다.
  2. 다른 모델은 normalization, dummy encoding, 결측치 제거가 필요하지만, 트리 모델은 전처리가 거의 필요 없다. 일부 트리 알고리즘은 missing value를 스스로 처리할 수 있다.
  3. 트리로 학습 후 새로운 sample을 예측할 때는 root에서 leaf까지 내려가기만 하면 되므로, 예측 복잡도는 $O(\log n)$수준으로 예측 속도가 빠르다.
  4. 숫자형, 범주형 데이터 모두 다룰 수 있다. ( 사이킷런의 기본 구현은 범주형을 직접 지원하지 않아 Label encoding 혹은 One-hot encoding이 필요하다. )
  5. 하나의 입력으로 여러 결과를 동시에 내는 멀티타킷 회귀도 가능하다.
  6. White box model ↔ black box model (Neural Network) → 왜 이런 예측을 했는지 설명이 가능
  7. 각 노드 분할이 통계적으로 유의미한지 검증할 수 있다.
  8. 결정트리는 데이터 분포(정규성, 등분산성 등)에 대한 가정이 없어서, 모델 가정이 약간 어겨져도 성능이 괜찮다.
• 단점
  1. Overfitting: 오버피팅의 가능성이 높다. prunning, max_depth, min_samples_leaf 같은 규제가 필요하다.
  2. Unstable: 데이터가 약간만 바뀌어도 트리구조가 달라질 수 있다. → Random Forest나 Bagging 같은 앙상블 방법으로 완화가능하다.
  3. 트리 예측은 각 구간별 상수값을 주므로 출력값이 불연속적이다. 이는 회귀 문제에서 매끄럽게 변화하는 함수를 잘 근사하지 못한다. 외삽(Extrapolation)에 약하다.
  4. 최적의 트리 학습은 계산적으로 매우 어렵다. 그래서 greedy 알고리즘으로 각 노드마다 “지금 가장 좋은 분할”만 선택한다. 따라서 golbal optimum을 보장하지는 않는다.
  5. 비선형 문제(XOR 등)를 표현하기 어렵다. 여러 변수의 복잡한 조합관계는 학습이 어렵다.
  6. 데이터 불균형에 약하다. 한 클래스가 훨씬 많으면 그쪽으로 치우친 트리가 만들어진다. → Undersampling, Oversampling이 필요하다.
•  where?
1. 해석이 중요한 분석일 때
2. 입력변수 간의 관계가 비선형일 때
3. 전처리하기 어려운 데이터일 때
4. 변수 간 상호작용을 자동으로 반영하고 싶을 때
5. 작은 데이터셋에서 빠른 프로토타입을 만들 고 싶을 때
• Decision Tree는 불순도 기반 예측 정확도 중심의 트리인 CART와 통계적 검정 기반 유의성 중심의 트리인 CHAID, 정보이득 기반 엔트로피 중심 트리인 Quinlan 계열 트리(ID3, C4.5, C5.0)로 나뉜다. ( Quinlan 계열 (ID3/C4.5/C5.0)은 다루지 않는다. )
• CART모델은 불순도를 가장 많이 줄이는 split을 탐욕적으로 선택함으로써 통계적 유의성보다는 예측 성능 기준으로 트리를 만들고,
• CHAID는 통계적으로 유의하게 다른 그룹이 발견될 때만 분할하여, 귀무가설을 기각하는 split만 유지하여 트리를 만든다.
• CART(Classification And Regression Tree)
  • Classification과 Regression 지원.
  • Spilit criterion
    • Classification: Gini impurity or Entropy
    • Regression: Variance Reduction, MSE 감소
  • 항상 한 번에 두 개의 자식노드만 만든다.
  • 통계검정을 사용하지 않고 단순 impurity 감소량 기준으로 greedy 선택
  • pruning을 사용하여 복잡도를 감소시킨다. — cost complexity pruning (α-penalty 기반)
  • 단순하고 빠르며, 거의 모든 현대 트리 모델의 뿌리 역할을 함.
• CHAID (Chi-squared Automatic Interation Detection)
  • 주로 범주형 데이터를 기반으로 하여 통계성 유의성 검정 중심 트리
  • Split criterion
    • Classification: 카이제곱 통계량의 p-value
    • Regression: F 통계량
  • 하나의 feature에서 3개 이상의 가지가 나올 수 있다.
  • 통계 검정이 필수적이다. 각 split이 통계적으로 유의한 지 검정한다. p-value가 α보다 낮으면 split을 유지한다.
  • 자동적으로 p-value기준에서 정지하기 때문에 별도의 pruning은 없다.
  • 데이터 마이닝 초기 시절에서 많이 사용된 설명용 트리 모델. 예측보단 해석 중심의 모델이다.
• feature importance
  • Tree model은 해석 가능성이 높기 때문에 이를 활용해 feature importance를 구할 수 있다.
  • 예측 성능을 가장 높일 수 있는 feature를 찾을 때 CART를 이용하고, feature가 목표 변수와 통계적으로 유의미한 관계를 찾을 때는 CHAID를 이용한다.
  • CART로 feature importance를 확인할 때
    • 장점
      1. 예측 정확도와 직접적인 연결
      2. 속도가 빠르고 구현이 표준화
    • 단점
      1. feature 간 상관관계가 높을 시 왜곡이 가능하다. (multicollinerity)
      2. 통계적 유의성(p-value)은 제공되지 않는다.
      3. 중요도는 상대적이며, “유의미하다”는 보장은 아니다.
  • CHAID로 feature importance를 확인할 때
    • 장점
      1. 각 feature의 통계적 유의성을 직접 확인 가능하다.
      2. “왜 이 변수가 선택되었는가” 해석에 용이하다.
      3. 설문조사, 사회·마케팅 데이터 등 설명 중심 분석에 매우 적합하다.
    • 단점
      1. 예측 성능과 직접 연결되지 않는다.
      2. 수치형 변수 처리 유연성이 떨어진다.
      3. p-value 다중 검정 문제(α inflation) 가능
      4. 머신러닝 모델 feature importance처럼 자동화된 스케일을 제공하지 않는다.

 

구분	CHAID 계열	Quinlan 계열 (ID3/C4.5/C5.0)	CART 계열
핵심철학	통계적 유의성(p-value)	정보이득(Information Gain)	예측오차 감소(impurity reduction)
주요 분할 기준	χ², F, p-value	Entropy, Gain Ratio	Gini, Variance
데이터 유형	주로 범주형	범주형 + 연속형	범주형 + 연속형
분할 방식	다중 분할 (multiway)	다중 분할 (multiway)	이진 분할 (binary)
가지치기 방식	유의수준 기준	오차기반 가지치기	Cost-complexity pruning
대표 구현	SPSS CHAID, R CHAID	Weka J48, R C50	sklearn DecisionTreeClassifier , R rpart
분야 성격	해석·통계 중심	고전 데이터마이닝	머신러닝 실무 중심