Post

Decision Tree

Based on the lecture “Intro. to Machine Learning (2023-2)” by Prof. Je Hyuk Lee, Dept. of Data Science, The Grad. School, Kookmin Univ.

Decision Tree


  • 결정 트리(Decision Tree) : 순도(Uniformity)를 최대로 가져가는 이진 판별 규칙들로 구성된 수형도(Tree)를 세우고 관측치를 분류하는 알고리즘

    02

    • 루트 노드(Root Node) : 깊이가 0 인 꼭대기 노드로서 최상위 노드
    • 결정 노드(Decision Node) : 규칙 조건
    • 리프 노드(Leaf Node) : 하위 노드가 존재하지 않는 노드로서 최종 범주
    • 서브트리(Subtree) : 어떠한 규칙 노드를 루트 노드로 가지는 하위 트리로서 판별 규칙 집합의 부분집합

Recursive Partitioning


  • 재귀적 분기(Recursive Partitioning) : 판별 규칙을 기준으로 상위 노드를 분할하여 순도가 높은 하위 노드를 생성하는 반복적인 과정

    • 판별 규칙 : 어떤 분기에서 하나의 설명변수를 사용하여 생성한 분할 조건

      03

    • 순도(Purity) : 어떤 노드에 속한 관측치들이 동일한 범주에 속하는 정도

      04

      • 순도를 정확히 측정하기 어려우므로 그 대리변수로서 불순도(Impurity)를 사용함

Discriminant Rule

  • 어떤 노드에 대하여, 설명변수 Xixi 를 기준으로 해당 노드를 분할한다고 하자

    y={NLeft,ifXixiNRight,ifXi<xi
  • 판별 규칙 Xixi 의 비용 J(Xixi) 는 다음과 같음

    J(Xixi)=mLeftmILeft+mRightmIRight
    • m : 결정 노드에 속한 관측치 갯수
    • mLeft : 좌측 하위 노드로 분기한 관측치 갯수
    • ILeft : 좌측 하위 노드의 불순도
    • mRight : 우측 하위 노드로 분기한 관측치 갯수
    • IRight : 우측 하위 노드의 불순도
  • 설명변수 Xi 기준 분할 시 최적의 분기점 x^i 는 다음과 같음

    x^i=argminxiJ(Xixi)
  • 특정 노드를 분할하는 최적의 설명변수 X^i 는 다음과 같음

    X^i=argminXi{minJ(X1),minJ(X2),,minJ(Xn)}

Impurity

  • 지니 지수(Gini Index) : 불순도를 경제적 불평등 개념 에 기초하여 계산한 지표

    I(Nk)=1i=1cpi2
    • c : 범주 갯수
    • pi : 노드 Nk 에서 i 번째 범주에 속하는 관측치 비율
  • 엔트로피 지수(Entropy Index) : 불순도를 정보 획득의 불확실성 개념 에 기초하여 계산한 지표

    I(Nk)=i=1c[pilog2pi]
    • c : 범주 갯수
    • pi : 노드 Nk 에서 i 번째 범주에 속하는 관측치 비율

Pruning


05

  • 가지치기(Pruning) : 자세하게 구분된 영역을 통합함으로써 과적합을 방지하는 기법으로서, Full Tree 를 생성하여 모든 노드에 대하여 비용 복잡도 지수를 계산하고, 그 값이 가장 낮은 노드에 대하여 가지치기를 반복적으로 수행하면서 최적의 가지치기 강도 α 하 트리를 도출함

  • 비용 복잡도 지수(Cost-Complexity)

    Rα(T)=L(T)+α|Leaf(T)|L(T)=m=1|Leaf(T)|xiRm(yiy^i)2
    • T : 타깃 노드를 루트 노드로 하는 서브트리
    • Leaf(T) : T 의 리프 노드 집합
    • Rmleaf(T) : Tm 번째 리프 노드
    • xiRm : Rm 에 속한 i 번째 관측치 벡터
    • α : 가지치기 강도
    • L(T) : T 의 훈련 관측치에 대한 예측 손실
    • Rα(T) : 타깃 노드의 비용 복잡도 지수

DTR


06

  • 재귀적 분기

    X^i=argminXi{J(X1,x^1),J(X2,x^2),,J(Xn,x^n)}x^i=argminxiJ(Xi,xi)J(Xi,xi)=mLeftmLLeft+mRightmLRight
  • 손실 함수

    07

    • 판별 분석 : 불순도(Impurity)를 최소화하도록 분기

      LGINI(Nk)=1i=1cpi2
    • 회귀 분석 : 오차(Error)를 최소화하도록 분기

      LMSE(Nk)=i=1m(yiy^i)2
This post is licensed under CC BY 4.0 by the author.