9. Decision Tree

What is Decesion Tree?

---

Decision Tree는 특정 조건에 기반하여 결정에 대한 모든 가능한 해결책을 시각적으로 나타낸 그래픽 표현이다

• 중간 노드는 여러 Alternatives 중에 어떠한 선택을 의미한다
• 리프 노드는 최종 Decision을 의미한다
• 그림에서 나이가 30세 이하이고, 학생이 아니면 컴퓨터를 사지 않을 것이라고 예측

 

Algorithm Overview

---

Decision Tree 알고리즘의 대략적인 과정

• 분할정복을 사용해서 Top-down 방식으로 트리를 형성한다
• 처음에는 모든 Training data는 Root로부터 시작한다
• 데이터들은 현재 단계에서 선택된 Feature를 기준으로 Recursive하게 나뉜다
• 이때 현재 단계에서 어떤 Feature를 선택할지는, Heuristic(간편 추론) 하거나 Statistical(통계적)한 방법으로 결정한다
  • Ex) Information Gain

 

Partitioning을 멈추기 위한 조건?

• Recursive하게 내려 가다가 현재 노드에 있는 데이터들의 Class가 모두 같으면 중단
  • 더 이상 분리할 필요가 없음
• 더 이상 남은 Feature가 존재하지 않으면 종료

 

Decision Tree Introduction

---

Decision Tree의 기본적인 아이디어는 Greedy, Recursive, Divide and Conquer

1. 최초의 트리는 비어있다
2. 데이터를 분류하기 위한 기준(Feature)을 선택한다
3. 더 이상 분류할 필요가 없다면 종료
4. 그렇지 않으면 2번 단계로 돌아가서 Recursive하게 데이터를 분리한다

 

• 가장 이상적인 케이스
• 그런데 보통 이렇지 않기 때문에, Recursive하게 계속 들어가야 한다

 

각 단계에서 어떤 Feature를 선택할지 어떻게 결정할 수 있을까?

• Algorithm
  • ID3: Entrophy
  • C4.5: Gain Ratio
  • CART: Gini index
• Common Idea
  • 각각의 Feature에 대해서 해당 Feature로 분리하게 되면, 얼마나 Heterogeneous한 결과가 나오는지 평가한다
    • Heterogeneous하지 않고, Homogeneous한 것이 좋다
    • 얼마나 많은 서로 다른 클래스의 데이터들이 섞여있는지를 평가한다
    • 분리를 했는데 서로 다른 클래스의 데이터가 많이 섞여있으면 해당 단계에서 선택하기에 별로 안 좋은 Feature
• Feature Types
  • Feature들은 Categorical한 것으로 가정 한다
    • 만약 그렇지 않으면 무수히 많은 Branch들이 뻗어나오게 된다
  • 만약 Categorical 하지 않고, Continuous 하다면 미리 Discretization이 되어 있어야 한다

 

Feature Selection

---

어떤 Feature를 선택하는 게 가장 좋을까?

• 해당 Feature로 데이터를 분류했을 때, 가장 Homogeneous하게 분류되는 것이 가장 좋다
  • 같은 말로 가장 덜 Heterogeneous하게 분리되어야 한다

• 예시에서 Age로 분류했을 때 가장 Homogeneous하게 분류된 것이다
• 해당 단계에서는 Age를 선택하는 게 베스트!

 

ID3

---

Iterative Dichotomiser 3

• ID3 방식은 Entropy(엔트로피) 에 기반한 Information Gain이 사용 된다
  • Entropy?
  • 엔트로피는 확률 분포 내에 있는 정보의 양을 수치적으로 나타낸 것
  • 쉽게 말해서 무질서도 로 생각할 수 있다
  • 그룹 내에 얼마나 데이터가 무질서하게 섞여있는지

 

• 엔트로피 값은 위의 식을 통해서 계산할 수 있다

 

• Entropy 값이 높을수록, 데이터의 분포가 더 Heterogeneous하다 는 것
• Entropy 값이 낮다는 것은, Pi 값이 매우 높거나 낮거나 둘 중 하나인 경우이다
  • Pi값이 1에 가까우면, 대부분의 데이터가 i에 속한다는 뜻이므로 엔트로피가 낮을 것이다
  • Pi값이 0에 가까우면, 해당 Class에 대한 데이터는 거의 존재하지 않는다는 의미이므로 엔트로피를 낮추는데 기여한다
    • 만약 2개의 클래스만 존재한다고 해보자, 하나의 클래스에 대해서 데이터가 존재하지 않으면 대부분의 데이터가 나머지 하나의 클래스에 속한다는 의미이므로 엔트로피가 낮을 것이다

 

• Information Gain은 분리하기 이전과 이후의 Entropy의 차이를 의미한다
• 특정 Attribute A에 대해 분류를 했을 때, 분류하기 전과 후의 Gain의 차이가 클수록 해당 Feature는 좋은 Feature 이다
• 보통은 분류하기 전의 Gain값이 더 클텐데, 전과 후의 차이가 크다는 것은 분류 이후의 Gain값이 많이 감소했다는 것을 의미한다

 

• 분리 이후에도 여전히 엔트로피가 높다면, Info Gain 값은 작아질 것이다

 

예시

• 모든 선택가능한 Feature에 대해서 Gain 값을 구한다
• 분류하기 이전의 Gain값과의 차가 가장 크게 벌어지는 Feature를 선택 한다
• 예시에서는 Credit을 선택했을 때, Gain의 차가 가장 크기 때문에 해당 단계에서는 Credit을 선택하는 것에 베스트!

 

C4.5

---

Evolution of ID3

• Information Gain은 Attribute Value의 수가 많은 Feature일수록 값이 커지는 경향이 있다 는 문제
  • Feature A는 5개의 Value를 가지고 있고, Feature B는 2개의 Value를 가지고 있다고 하자
  • A가 B보다 높은 Information Gain을 가지는 경향이 있다
  • 그럼 아무래도 A가 선택될 확률이 높아진다
• C4.5 알고리즘은 Gain Ratio를 사용 한다
  • Gain Ratio는 Information Gain을 Normalization한 것
  • Gain Ratio는 Feature를 선택할 때 Branch의 수를 고려한다

 

• SplitInfo는 단지 얼마나 많은 Branch가 있는지에만 집중한다
  • log(x)의 값은 x가 0에 가까워질수록 급격하게 작아진다
  • Branch가 많은 경우에는 x의 값이 0에 더 가까워질 것이고, SplitInfo의 값은 커지게 된다
• Gain Ratio는 Information Gain값을 SplitInfo로 나눠서 정규화를 한다
  • Gain Ratio는 Partition이 많은 Feature에는 더 많은 페널티를 준다 
  • Branch(Value)가 많은 경우에는 SplitInfo값이 크기 때문에, 나눠주면 Gain값이 작아지게 된다

 

예시

• Credit의 경우 Value가 3개 (Excellent, Fair, Poor)

 

CART

---

Classification And Regression Trees

• Gini Index?
  • Entropy와 비슷한 개념을 갖는다
  • CART는 ID3의 아이디어와 매우 비슷하다