결정 트리(decision tree)

트리 형태로 의사결정 지식을 표현한 것

• 내부 노드(internal node): 비교 속성
• 간선(edge): 속성 값
• 단말 노드(terminal node): 부류(calss), 대표값
  

결정트리 학습 알고리즘

모든 데이터를 포함한 하나의 노드로 구성된 트리에서 시작

• 반복적인 노드 분할과정

  1. 분할 속성을 선택
  2. 속성값에 따라 서브트리를 생성
  3. 데이터를 속성값에 따라 분배

• 분할 속성의 결정

  • 어떤 속성을 선택하는 것이 효율적인가?
    • 분할한 결과가 가능하면 동질적인 것으로 만드는 속성 선택
  • 엔트로피 (불순도의 개념)
    • 동질적인 정도 측정 가능 척도
    • 원래 정보량 측정 목적의 척도
    • 2개 부류가 있는 경우의 엔트로피(반반 섞였을 때 불순도 최대!)

• 엔트로피 특성: 섞인 정도(불순도)가 클 수록 큰 값

• 정보 이득 : 정보 이득이 클 수록 우수한 분할 속성

• 학습 데이터의 예
  부류정보가 있는 데이터

• 엔트로피 계산
  

• 데이터 집합 분할과 정보 이득

  • pattern 기준 분할
    
  • outline 기준 분할
    
  • dot 기준 분할
    
  • 최종 결정 트리
    

• 정보이득 척도의 단점

  • 속성값이 많은 것을 선호한다.
    -> 속성값이 많으면 데이터집합을 많은 부분집합으로 분할 -> 작은 부분집합은 동질적인 경향

• 개선 척도

  • 정보이득비(information gain ratio)
  • 지니 지수(gini index)

• 정보이득비 척도

  • 정보이득 척도를 개선한 것: 속성값이 많은 속성에 불이익
  • I(A): Intrinsic information(entropy)
    속성 A의 속성값을 부류로 간주하여 계산한 엔트로피
    속성값이 많을 수록 커지는 경향

• 지니 지수: 데이터 집합에 대한 Gini 값(i,j는 부류를 나타냄)
  
  - 속성 A에 대한 지니 지수값 가중평균
  - 지니지수이득

• 분할속성 평가 척도 비교
  

결정트리를 이용한 회귀

• 회귀를 위한 결정트리
  • 출력값이 수치값
• 분류를 위한 결정트리와의 차이점
  • 단말노드가 부류가 아닌 수치값임
  • 해당 조건을 만족하는 것들이 가지는 대표값
• 분할 속성 선택
  표준편차 축소 SDR를 최대로 하는 속성 선택