[인공지능] 4-4 기계학습 : 결정트리

1. 결정트리

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

• 내부 노드 : 비교 속성
• 간선 : 속성 값
• 단말 노드 : 부류, 대표값

결정트리 학습 알고리즘

• 모든 데이터를 포함한 하나의 노드로 구성된 트리에서 시작
• 반복적인 노드 분할 과정

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

   

분할 속성 결정

• 어떤 속성을 선택하는 것이 효율적인가?
  -> 분할한 결과가 가능하면 동질적인 것으로 만드는 속성
• 엔트로피
  • 동질적인 정도 측정 가능 척조
  • 원래 정보량측정 목적의 척도임
    -> 동질적일수록 낮음
    

    

  p(c) : 부류 c에 속하는 것의 비율
  p(c)가 낮을수록 정확한 엔트로피

정보이득

IG = I - Ires
Ires : 특정 속성으로 분할한 후의 각 부분집합의 정보량의 가중평균

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

1. 엔트로피 I 계산

전체 데이터 집합에서 분류한다.

2. Pattern 기준 분할

주어진 Pattern 기준으로 분할한 후 서브집합에서 각각 엔트로피를 구한다.

3. Ires(Pattern) 구하기

Σ{ (서브집합의 데이터 개수) / (전체 데이터 개수) x 서브집합의 엔트로피}

4. IG(Pattern) 구하기

I - Ires(Pattern)

5. 분할 속성 선택

최종, 분할 속성 별로 계산한 정보이득 중 가장 큰 것을 선택한다.

정보이득 척도의 단점

• 속성값이 많은 것 선호
• 속성값이 많으면 데이터 집합을 많은 부분집합으로 분할
  • 작은 부분집합은 동질적인 경향을 보이게 됨
  • 많은 부분집합은 비동질적임

개선 척도 ↓

정보이득비

정보이득 척도를 개선한 것

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

  

  
  I(A)로 나눠버림

I(A) : 속성 A의 속성값을 부류로 간주하여 계산한 엔트로피

• 속성값이 많을수록 커짐
  

  

  
  

  

지니 지수

데이터 집합에 대한 지니값

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

  

  
  

  

  
  

  

Gini(A) = Σ (부분집합의 데이터 개수) / (전체 데이터 개수) x { (부류1의 개수) x (부분 집합 데이터 개수) x (부류2의 개수) x (부분 집합 데이터 개수) }

GiniGain(A) = Gini - Gini(A)

결정 트리 알고리즘

ID3 알고리즘 : 범주형 속성값을 갖는 데이터에 대한 결정트리 학습
C4.5 알고리즘 : 범주형, 수치형 속성값을 갖는 데이터로부터 결정트리 학습
C5.0 알고리즘 : C4.5를 개선한 알고리즘
CART 알고리즘 : 수치형 속성을 갖는 데이터에 대해 적용

회귀를 위한 결정트리

• 분류를 위한 결정트리와 차이점
  • 단말노드가 부류가 아닌 수치값
• 분할 속성 선택
  • 표준편차 축소 SDR을 최대로 하는 속성 선택

SDR(A) = SD - SD(A)