[Machine Learning] 결정트리

결정 트리의 형태

결정 트리

• 트리 형태로 의사결정 지식을 표현한 것
  • 내부 노드(internal node): 비교 속성
  • 간선(edge): 속성 값
  • 단말 노드(terminal node): 부류(class), 대표값

결정 트리 학습 알고리즘

결정 트리 알고리즘

• 모든 데이터를 포함한 하나의 노드로 구성된 트리에서 시작
• 반복적인 노드 분할 과정
  1. 분할 속성 선택
  2. 속성값에 따라 서브 트리 생성
  3. 데이터를 속성값에 따라 분배

분할 속성의 결정

• 어떤 속성을 선택하는 것이 효율적인가?
  • 분할한 결과가 가능하면 동질적인 것(불순도가 낮은 것)으로 만드는 속성을 선택

엔트로피

• 엔트로피(Entropy)

  • 불순도를 나타내는 척도로, [-1, INF) 범위의 값을 가지며 클수록 불순도가 높음
  • 단위로는 bits를 사용(정보량)
  • p(c)는 부류 c에 속하는 것의 비율

  

  • 2개 부류가 있는 경우의 엔트로피

    

• 정보 이득
  • IG = I - I_res
    • I_res: 특정 속성으로 분할한 후의 각 부분집합의 정보량의 가중평균
  • 정보이득이 클수록 우수한 분할 속성

👍 예시

학습 데이터

(pattern 기준 분할 시)

(outline 기준 분할 시)

(dot 기준 분할 시)

최종 분할 선택

• IG(Pattern) = 0.246
• IG(Outline) = 0.151
• IG(Dot) = 0.048

분할 2회 수행 이후 최종 결정 트리

• 정보이득 척도의 단점
  • 속성 값이 많은 것 선호
    • 예) 학번, 이름 등
  • 속성 값이 많으면 데이터집합을 많은 부분집합으로 분할
  • 테스트 데이터에 대해 좋은 성능을 보이기 어려움
• 개선 척도
  • 정보 이득비
  • 지니 지수

정보 이득비

• 정보 이득비(Information gain ratio)

  • 속성값이 많은 속성에 대해 불이익

  

• I(A)

  • 속성 A의 속성값을 부류(class)로 간주하여 계산한 엔트로피
  • 속성값이 많을수록 커지는 경향

  

  👍 예시

  

지니 지수

• 지니 지수(Gini Index)

  • 데이터 집합에 대한 Gini 값

    • i, j가 부류를 나타낼 때

    

    

  • 속성 A에 대한 지니 지수값 가중평균

    

  • 지니 지수 이득 (Gini index gain)

    

👍 예시

분할속성 평가 척도 비교

결정트리를 이용한 회귀

회귀를 위한 결정트리에서는 출력값이 수치값인 데이터를 사용한다.

분류를 위한 결정트리와 차이점

• 단말 노드가 부류(class)가 아닌 수치값
• 해당 조건을 만족하는 것들이 가지는 대표값

분할 속성 선택

• 표준편차 축소 SDR를 최대로하는 속성 선택

  

  • 표준편차 SD

    

  • SD(A)

    • 속성 A를 기준으로 분할 후의 부분 집합별 표준편차의 가중 평균

👍 예시