의사결정나무(Decision Tree)-1

의사결정나무 분류

널리 사용되는 분류기 중 하나

복잡한 데이터에 대해 좋은 성능을 보임

학습 데이터로부터 설명 가능한 분류기준을 결정 (왜 이렇게 분류되었는지)

데이터를 뿌리부터 잎까지 순차적으로 분류

* leaf noad : 더이상 분리되지 않는 노드

 

Tree Introducion Algorithm

데이터로부터 DT 알고리즘을 만들어내는 알고리즘

 

Tree Introduction Algorithm 에서 만들어진 DT

-> test data 에 DT 적용

-> 각 data 에 class 를 부여할 수 있음

 

ex.

깉은 데이터의 분류에 대해 하나 이상의 서로 다른 트리 학습이 가능하다

splitting attribute 로 어떤 attribute 를 고르냐에 따라 트리 모양이 달라짐

 

위의 DT에 refund = No, Marital Status = Married, Taxable Income = 80K 인 test data 적용

-> defaulted = No 로 분류해줌

 

Hunt's Algorithm

Dt : node t 에 있는 학습 데이터 집합

 

만약 Dt 에 속한 데이터가 모두 하나의 클래스 Yt에 속해있다면, t는 Yt class 의 leaf node

만약 Dt 에 데이터가 속하지 않으면, t 는 default class Yd 로 분류

만약 Dt 에 속한 데이터가 둘 이상의 클래스에 속한다면, 데이터의 다른 feature 이용해서 더 작은 부분집합으로 분리  

 

ex.

Tree Induction 

Greedy Strategy

현재 단계에서 최선의 분류를 하는것이 목표

issue

1. 어떻게 분리할 것인지

 1) 어떻게 분리 기준 변수를 선택할것인지

 2) 최적의 분리 기준은 무엇인지

2. 언제까지 분리할 것인지

 

  1) 분리기준

attribute type 에 따라	분리의 수에 따라
1) nominal 2) ordinal 3) continuous	1) 2-way split (binary split)  2) multi-way split

 

  2) 어떤게 최적의 분리기준 ?

Greedy approach 상, 균질한(homogeneous) class 분포가 선호됨

== node 에 속한 class 가 한쪽에 몰려있을수록 좋음

 

균질성 체크를 위해, 불순도(impurity) 에 대한 측정이 필요

불순도가 높을수록 비균질 / 불순도가 낮을수록 = 순도가 높을수록 균질

분류를 해감에 따라 기존 불순도에 비해 분류 후 불순도가 얼마나 낮아졌는지를 관찰,

불순도 감소량(Gain) 이 가장 크게 된 분류가 좋은 분류

Gain = (분류 이전의 불순도) - ( 분류 이후의 불순도)

불순도 측정 지표

1) Gini index (지니계수)

2) Entropy (무작위도)

3) Misclassification error (오분류 오차)

 

1) Gini index