[Data Science] Classification - Decision Tree

Decision Tree

• Decision tree는 feature를 기반으로 데이터를 나누어가며 leaf node서 데이터의 class label을 결정하는 top-down 방식의 모델이다.

Algorithm

• Basic idea: greedy & recursive & divide and conquer
• 종료 조건:
  
  1. 데이터가 같은 class label 밖에 남지 않았을 때.
  2. 더이상 partition할 수 있는 feature가 없을 때.

1. Root node만 있는 빈 트리에서 시작한다.
2. 선택한 feature에 따라 데이터를 나눈다. (partitioning)
   각각의 나뉜 데이터에 대해:
       3. 종료 조건이 만족되면 예측을 진행한다.
       4. 그렇지 않다면 2번으로 돌아가 partitioning을 반복한다.

Decision tree algorithm

Decision Tree Induction

• 그렇다면 어떤 기준으로 feature를 선택하여 분류할지에 대한 내용.
• 알고리즘
  1. ID3: Entropy
  2. C4.5: Gain Ratio
• Common idea: 가급적이면 하나로 묶일 수 있는 feature를 선택하자..! (more homogeneous, less heterogeneous)
  • 예를 들어, class A, B가 있다고 가정하자. 이를 '성인'이라는 feature에 따라 분류했더니 Yes - A:4, B:2, No - A:2, B:4로 분류되었다. 별개로 '성별'이라는 feature에 따라 분류했더니 남 - A:6, 여 - B:6으로 분류되었다. 이 경우, '성별'이라는 feature가 '성인'이라는 feature에 비해 더 homogeneous 하다는 것을 알 수 있다.

Decision tree induction

ID3: Iterative Dichotomiser 3

• Information Gain이라는 값을 바탕으로 엔트로피를 계산한다. A라는 feature로 partitioning 하였을 때, 전후 엔트로피의 차이를 확인한다. 엔트로피가 가장 적은 feature selection. (*엔트로피: 불확실성의 척도, 높을수록 데이터가 여러 데이터가 섞여있다는 의미. 낮을수록 단일 데이터가 많다는 의미.)
• 아래 수식을 통해 feature에 대한 Gain을 산출하여 가장 높은 값을 가진 feature를 선택한다. 
  p_i는 class i에 속하는 data D의 확률을 나타낸다. 예를 들어, 전체 데이터의 수가 10개일 때, class A 6개, B 4개가 있다면 p_red는 6/10이며 p_blue는 4/10이다.
• 계산 예시는 귀찮으니 패스... 

How to calculate Information Gain

Info(D) graph

C4.5: Evolution of ID3

• ID3는 큰 수를 따라 값이 편향되는 경우가 발생한다. 예를 들어, class A의 수가 120개이고, class B의 수가 12개라면 Gain의 값이 A에 대해 편향될 수 있다. 이를 방지하기 위해 비율을 고려한 Gain Ratio를 사용한다. 즉, information gain을 표준화하였다고 볼 수 있다.
• SplitInfo는 페널티라고 보면 된다. Feature에 의해 얼마나 많은 partition이 생겼는지 확인하며 partition이 많을수록 큰 값을 가진다. 이는 결과적으로 Gain Ratio의 감소로 이어진다.

How to calculate Gain Ratio

 

Overfitting

• Training set의 에러를 낮추기 위해 대해 너무 큰 depth, condition을 사용한다면 overfitting되어 실제 testing set의 에러는 더욱 심해질 수 있다.
• Overfitting을 방지하기 위해 tree pruning이라는 기법을 사용한다.

Tree Pruning

• Decision tree를 가지치기하여 overfitting을 방지하는 기법이다.
• 두 가지 접근법이 있다.
  1. Pre-pruning
  2. Post-pruning

Pre-pruning: Halt tree construction early

• Decision tree를 만드는 도중에 node의 split을 멈추는 방법이다.
• 적절한 threshold를 고르기가 어려움.
  : Minimum samples split, Maximum tree depth, Minimum gain 

Post-pruning: Remove branches from a "fully grown" tree

• Pre-pruning보다 더 많이 쓰는 방법
• Decision tree가 완성된 상태에서 node를 날리는 방법이다.
• Validation set을 사용하여 "best pruned tree"를 찾는 것이 목적이다.
• Original tree, pruned tree를 비교하여 정확도가 높은 쪽의 tree를 선택하여 original tree로 변경하며 모든 pruning 작업이 정확도가 낮아지는 경우 pruning을 종료한다.