Decision Tree

Decision tree

1. 의사결정 트리란?

• 결정트리는 의사 결정 규칙과 그 결과들을 트리 구조로 도식화한 의사 결정 지원 도구의 일종이다. 목표에 가장 가까운 결과를 낼 수 있는 전략을 찾기 위해 주로 사용된다.

• 분류(classification)기술 중 가장 일반적으로 사용되는 방법이다.

• eager learning과 관련있다. 미리 분류해놓은 tree를 가지로 query가 들어오면 tree를 거쳐 답을 내준다.

2. 의사결정 트리 알고리즘이란?

• 결정 트리를 구성하는 알고리즘에는 주로 하향식 기법이 사용되며, 각 진행 단계에서는 주어진 데이터 집합을 가장 적합한 기준으로 분할하는 변수값이 선택된다.

• 서로 다른 알고리즘들은 '분할의 적합성'을 측정하는 각자의 기준이 있다.(ex.동질성 측정)

3. 의사결정 트리의 장점은?

• easy to understand 이해하기 쉽다.
• mapped nicely to a set of business rules
• applied to a variety of real classification and prediction problems
• make no prior assumptions about the data 자료를 가공할 필요가 거의 없다.
• able to process both numerical and categorial attributes in data 수치 자료와 범주 자료 모두에 적용할 수 있다.
• 대규모의 데이터 셋에서도 잘 동작한다. 특히 속성이 많은 data를 유연하게 다룰 수 있다.

4. 의사결정 트리의 단점은?

• 각 노드에서의 최적값을 찾아내는 탐욕 알고리즘같은 휴리스틱 기법을 기반으로 하고 있어 최적 결정 트리를 알아낸다고 보장할 수 없다. (local maximum에 갇히는 문제 그래서 unstable하다.)
• 훈련 데이터를 제대로 일반화하지 못할 경우 너무 복잡한 결정 트리를 만들 수 있다.
• 배타적 논리합이나 패리티, 멀티 플렉서와 같은 문제를 학습하기 어렵다.
• 약간의 차이에 따라 트리의 모양이 많이 달라질 수 있다.
• limited to one target attribute 한 개의 속성만 target으로 정할 수 있다.

5. 표현방법

• internal node는 attribute variable을 적는다.
• each branch는 attribute value을 적는다.
• each leaf node는 classification value을 적는다.

아래 예시는 'outlook' 속성이 있고 이 속성의 value 값으로 sunny, overcast, rain이 있고 리프 노드의 값은 날씨에 따라 테니스를 치러 나갈것인가 YES, 안 나갈것인가를 NO정하는 classification value 이다.

#play tennis rule in your brain:
if(Outlook == Sunny && Humidity == Normal) 
|| (Outlook == Overcast)
|| (Outlook == Rain && Wind = Weak) then Yes
else No

6. decision tree types

• binary decision trees - only two choices in each split (성적 예시) 

• N-way or ternary decision trees - three or more choices in at least one of its split (테니스 예시)

7. tree split

트리는 split 과정을 통해 좀 더 작은 자식을 생성한다. 하지만 잘 생각해보자 split을 그냥 멍청하게 자를것인가?

• 아니다. 가장 정보력이 높은 속성으로 먼저 자르면 큰 뭉텅이로 자식을 나눌 수 있다. 그런다음 다음으로 정보량이 가장 많은 걸로 또 split을 한다. (이런 방식이 top-down 방식이다.)

이제는 정보력이 높은 속성을 어떻게 detect를 하느냐가 문제인 것이다.

8. tree split 똑똑하게 하기

• best split을 하기 위해 각 속성으로 분류했을때 나오는 자식들의 homogeneous 속성을 평가하면 된다. 즉, 동족성이다. 이 속성을 purity 순도라고 한다.

• 간단한 예시를 들어보자

불투명한 주머니에 흰 공 10개, 검은 공이 10개가 들어있다고 하자. 어떤 속성으로 인해 이 주머니가 2개로 나눠졌다. 아래그림을 보면 왼쪽 Good Split 의 자식 주머니의 purity가 오른쪽 Poor Split 보다 높은것을 알 수 있다.

• 만약 data group 이 여러개의 classes(several target values)를 가지고 있다면 이것은 impure하다고 말한다.

• 만약 data group 이 one class(one target value)를 가지고 있다면 이것은 pure하다고 말한다.

• purity를 increase 하는 방향으로 split을 한다면 이것은 best split방법이 될 것이다.

9. 순도를 어떻게 측정 할 것인가?

• information gain based on entropy 개념을 다룰 것이다.

• **Gini (population diversity)**개념을 다룰 것이다.

• Information Gain Ratio(as simple variation of Information Gain)

• Chi-square Test based(on chi-square distribution in Statistics)

10. Information Gain이란?

• Entropy란? impurity를 측정하는 단위이다. 

  엔트로피 개념을 좀 더 이해하기 쉽게 설명하자면, 불투명한 주머리가 있다고 가정하자. 이 주머니 속에 하얀색 공만 있다면?

  에잇! 이미 다 알고 있다. == 에너지가 0 이다. 에너지가 낮다.

  하지만 주머니 속에 하얀 공 5개, 검은 공 5개가 있다면?

  ...??!?!?! 모른다. == 에너지가 1이다. 에너지가 높다.

  즉, 확률이 높을 수록 에너지가 낮고, 로또에 당첨되는 것처럼 확률이 낮으면 에너지가 굉장히 높다.

• information gain이란? split을 함으로써 부모와 자식의 불순도가 얼마나 차이나는지 비교하기 위해서 고안한 식이다.

  

11. information gain: Example

• data set 

  target variable인 Transportation의 엔트로피 값은 1.571

- 만약, Gender로 split을 할 경우 Target인 버스, 전철, 차고 각각 분류해서

  남성5명 (버스3 + 전철1 + 차1)의 Entropy를 구해 1.37
 ​     
  여성5명 (버스1 + 전철2 + 차2)의 Entropy를 구해 1.522

Information gain 식에 대입하면

• 만약, Car ownership으로 split하면 Gain이 0.534

• 만약, Travel Cost로 split하면 Gain이 1.210

• 만약, Income Level로 split하면 Gain이 0.695

• 즉, Gain이 가장 높은 1.210이 채택되면서 root는 Travel Cost가 된다.

근데 아마 Expensive와 Standard는 깔끔하게 pure하게 나오는데 cheap부분이 딱 떨어지지 않을 거다. 그럼 또 반복한다.

분류된 부분은 제거하고 계산이 필요한 부분만 남겨서 다시 Target Variable의 Entropy(S)를 새로 구하고 똑같이 계산해준다. ​ ​

• Entropy(S) =0.722

  

  • Gender의 Gain =0.322

  • Car ownership = 0.171

  • Income level = 0.171

  • 가장 높은 Gender가 다음 속성 node으로 선정되고 또 나눈다. Target Variable인 Transportation이 pure하게 딱 떨어질 때까지 반복한다.

​

​ - 3회차 반복 ​

fin

12. Gini purity 계산법

• 비슷한 개념인데 계산법이 좀 더 단순하다.
• 간단한 예시로 주머니에 흰 공이 10개, 검은 공이 10개 있다고 하자. 그럼 Gini값은 0.5이다.