[Classification] Decision Tree

Decision Tree

Classification을 위해서 tree를 생성하고 그 tree에 따라 분류한다.

 

Model(Tree) 생성 방법

top-down recursive divide-and-conquer 방식

 

• top-down : Root부터 시작해서 test attribute를 선택하며
• divicde-and-conqure : 그 attribute에 대한 기준으로 sample들을 나눈다.
• recursive : 이 과정을 반복해서 leaf까지 내려가며 tree를 생성한다.

 

해당 branch까지 내려온 모든 sample이 같은 class를 갖거나 더 이상 test attribute로 선택할 attribute가 존재하지 않을 때 recursive를 중단한다.

만약 leaf까지 내려왔는데 모든 sample들의 class가 동일하지 않다면 다수결(majority voting)을 통해 class를 결정한다.

 

Decision Tree 예시

아래처럼 같은 level에서도 다른 test attribute로 나뉠 수 있다.

 

---

Test Attribute Selection

더 homogeneous하게 나누는 attribute를 선택한다.

즉, smaple들을 attribute로 나누었을 때 최대한 class가 같은 것 끼리 묶이도록 하는 attribute를 test attribute로 선택한다.

* heterogeneous : attribute로 나눴을 때 더 달라지는 것 (↔ homogeneouse)

 

Homogeneouse한 정도를 측정하기 위해서 information gain(entropy)과 gain ratio(gini)를 사용한다.

• Information gain
  • entropy(혼잡도)의 개념을 이용한다.
  • $Gain(A) = Info(D) - Info_{A}(D)$
  • 최대의 gain을 가지는 것이 최적의 test attribute이다.
• gain ratio
  • Information gian은 더 많은 value를 가지는 attribute에 편향되는 경향이 있다.
  • 때문에 gain ratio는 information gain 값을 attribute로 나눴을 때의 비율을 고려하여 normalize를 한다.
  • $gain \_ratio = Gain(A) / SplitInfo_A(D)$
• Gini index
  • gini의 개념을 이용한다.
  • $\Delta gini(A) = gini(D) - gini_A(D)$

 

비교

셋다 괜찮은 결과를 가진다.

 

그러나 선호하는 경향이 각각 달리 존재한다.

• information gain
  • 더 많은 value를 가지는 attribute에 편향된다.
• gain ratio
  • balanced 보다는 한쪽이 크고 한쪽이 작은 unbalanced 한 split에 편향된다.
• gini index
  • class의 수가 많을 때 어려움이 있다.
  • 나눠진 partition의 size와 purity가 balance된 것을 선호하는 경향이 있다.

 

---

Overfitting

생성된 tree가 training data에 대해 overfit되는 것을 overfitting이라 한다.

 

극단적인 경우에는 모든 smaple이 자기 자신에 대해 branch를 형성하여 하나의 leaf가 하나의 sample을 가리키는 것이다.

이렇게 되면 training data에 대해 100%인 tree를 형성하게 된다.

 

그러나 train data에는 noise와 outlier가 존재하기 때문에 unknown에 대한 정확도는 떨어지게 된다.

 

해결 방법

• Prepruning
  • tree를 구성할 때 threshold를 통해 미리 pruning을 한다.
  • split 했을 때 개선할 수 있는 gain의 값이 미미하면 더이상 내려가지 않도록 한다.
  • 단점 : gain의 threshold를 정하기 어렵다.
• Postpruning
  • 일단 완전히 다 내려간 후(fully grown) 각 노드에 대해서 내려가는 것이 좋은지 아닌지를 판단한다.
  • 해당 노드에서 내려갔을 때의 정확도와 안내려갔을 때의 정확도를 비교한다.
  • training data의 일부를 감추거나 training data와 다른 data를 사용해서

 

 

---

Large Database

빅데이터에 대해서는 모든 data가 메모리에 다 올라올 수 없기 때문에 data의 크기가 커질 수록 speed가 exponential하게 증가할 수도 있다.

때문에 reasonable speed로 수행할 수 있는 scalability가 중요하다.

 

Decision tree는 comparable한 방법이다.

• learning speed : decision tree는 다른 classification들에 비해 learning speed가 빠르다.
• interpretability : 간단하고 쉽게 이해할 수 있는 classification rule로 변환할 수 있다.
• SQL query : SQL query를 사용할 수 있다. → 조건에 맞는 데이터를 SQL을 통해 disk에서 쉽게 가져올 수 있다.
• comparable classificiation accuracy : 월등히 뛰어나지는 않지만 뒤쳐지지 않는 accuracy를 보인다.