데이터 분류(2) - 의사결정 트리

Decision tree(의사결정 트리)는 단순하면서 가장 널리 이용되고 있는 분류 기법으로, 일련의 질문들과 가능한 대답들로 이루어진 트리 형태의 구조를 가지며 트리는 3종류의 노드를 갖는다.

 

의사결정 트리의 3가지 노드 특징

 

Decision Tree에서 각 terminal node에는 하나의 class label이 붙는다. root와 다른 internal node들을 포함하는 non-terminal node(비단말 노드)들에는 서로 다른 특성을 갖는 특성들을 갖는 레코드들을 분리시키기 위한 속성 시험조건들이 들어간다. 

 

   ex) 포유류 판별 기준 

       1. 체온이 따뜻한가 차가운가? (따뜻) 표유류, (차가움) 비표유류

       2. 분만이 가능한가? (가능) 포유류, (불가능) 비포유류  

       3. ... etc

 

포유류 판별 기준 기반 노드 분류

 

 

 

 

Hunt's Algorithm (헌트 알고리즘)

   -  데이터를 분할하기 위해 어떤 속성을 사용할 것인가에 대해 국지적으로 최적인 일련의 의사결정을 내림으로써 의사결정 트리를 키워나가는 Greedy Strategy(탐욕적 전략)을 주로 이용

   - Hunts' Algorithm의 의사결정 트리는 Training records들을 연속적으로 더 단순한 부분집합들로 분할하는 재귀적 방식으로 성장

      : 부분집합들로 분할하기 위해 Attribute test condition(속성 시험 조건)이 선택 됨

 

대출금 체납이 예상되는 대출가의 예측을 위한 훈련집합, 의사결정트리  

 

Decision Tree를 유도하는 학습 Algorithm은 두 가지 문제에 대해 다룰 필요성이 있다

   1. 훈련 레코드의 분할 방식은?

      각 재귀단계의 레코드들을 더 작은 부분집합으로 나누기 위한 Attribute test condition을 선택해야 함.

      이 단계의 수행을 위해 서로 다른 속성 타입에 대한 시험조건 명시뿐만 아니라 각 조건의 우수성 여부를 평가하는 객관적인 척도로 제공

 

   2. 분할 절차 정지는 어떻게 ? 

       트리 성장 과정을 끝내기 위한 정지 조건을 설치, 모든 레코드가 같은 class에 속하거나 동일한 속성 값들을 가질 때까지 노드를 확장

       이 외 조기 종료도 가능하긴 하나 추후 재논의 예정

 

 

Attribute test condition(속성시험 조건) 표현 방법

  - 분할 개수에 따른 표현

     Binary Split(이진 분할) : 속성 값을 두 개의 부분집합으로 분할 (최적화 필요)

     Multi-way Split(다중 분할) : 속성 값을 3개 이상의 가능한 많은 파티션으로 분리

  - 속성의 종류에 따른 표현

     Nominal(명목형)   :  이진/다중 분할 모두 적용 가능

     Ordinal(서열형)    : 이진/다중 분할 모두 적용 가능하나 서열적 특성에 위배되지 않는 범위 내에서 적용

     Continuous(연속형)   :   서열형 속성이 되도록 discretization(이산화)을 진행

                                           1. 정적 방법 : 시작 시점에 1번만 discretiation 진행

                                           2. 동적 방법 : 분할이 필요할 때마다, 동일 너비, 동일 빈도 등으로 Discretization 진행

     Binary Decision(이진결정)   :  모든 가능한 분할을 고려하고 이 중 최선의 분할을 찾음

 

 

그렇다면 최선의 분할(Best Split)을 선택하는 척도는? 

 자식노드들의 impurity(불순도)를 기반으로 한다. 불순도가 작을수록 클래스 분포는 더 비대칭(skewed)이 된다. 

 예를들어, 클래스 분포 (0,1)은 불순도가 0이며, 균일한 클래스 분포(0.5, 0,5)를 갖는 노드는 불순도가 가장 높다. 

Best Split 을 위해서는 Impurity Mesure를 낮추는 방향으로 분할을 시도해야한다.

[example]

Best Split을 위한 시험 조건이 얼마나 잘 수행되는지 알기 위해서는 부모 노드의(before split) Impurity와 자식노드의 (after split) Impurity를 비교해 볼 필요가 있다. 그 차이가 크면 클수록 더 좋은 시험이 된다. 위 example에서 before split의 class 분포는 (0.5, 0.5)고 

   - Own Car로 분할 시, (0.6, 0.4)와 (0.4, 0.6)이며 

   - Car Type으로 분할 시, (0.25, 0.75), (1, 0), (1/8, 7/8)이다

결국 각 노드에서 클래스 1 분포가 skewed(편중) 되도록 분할하는 것이 좋은 분할법이며 클래스 분류가 잘 된 경우(특정 class에 편중된 경우) 불순도가 작아지고 잘 되지 않은 경우(클래스가 고르게 분포된 경우)에는 불순도가 커진다

 

            -> 특정 클래스의 비율(p)이 아주 작거나 높을 경우엔 불순도가 낮아지나, 0.5에 가까운 경우에는 불순도가 높아진다. 

 

 

gain(이득), Δ는 분할의 우수성을 결정하기 위해 사용될 수 있는 기준이다. 

 

Information Gain(정보이득)

  - Entropy가 위의 gain 식의 불순 척도로 사용될 경우, Entropy 차이를 information gain이라 한다

 

 

트리를 구축하는 기준에 대해 공부해보았다! 

그렇다면 트리 구축의 중단 시점은.. 언제일까? 

    - 노드에 속하는 모든 records들이 동일한 class를 가질 때

    - 노드에 속하는 모든 records들이 동일(유사한) 속성을 가질 때

    - 노드의 records 수가 임계치 이하로 떨어질 때