Overview Decision Tree Director of TEAMLAB Sungchul Choi

Size: px

Start display at page:

Download "Overview Decision Tree Director of TEAMLAB Sungchul Choi"

창훈 낭
5 years ago
Views:

1 Overview Decision Tree Director of TEAMLAB Sungchul Choi

2 머신러닝의학습방법들 - Gradient descent based learning - Probability theory based learning - Information theory based learning - Distance similarity based learning

3 Overview - Akinator 스무고개로유명인, 캐릭터를맞추는게임

4 Overview

5 Decision Tree Classifier - Data 를가장잘구분할수있는 Tree 를구성함

6 Guess who 남자긴머리안경이름 예아니오예브라이언 예아니오아니오존 아니오예아니오에이프라 아니오아니오아니오아이오페

7 Guess who 안경을쓰고있는가? 남자인가 브라이언 남자인가 안경을쓰고있는가? 머리가긴가 존 머리가긴가 존브라이언에이프라아오이페 에이프라 아오이페

10 Decision Tree 만들기 - 어떤질문이가장많은해답을줄것인가? - 결국어떤질문은답의모호성을줄여줄것인가? - 문제를통해서 splitting point을설정 è 남은정보로 splitting point를설정하는식

11 Guess who 안경을쓰고있는가? 남자긴머리안경이름 예아니오예브라이언 예아니오아니오존 브라이언 남자인가 아니오예아니오에이프라 아니오아니오아니오아이오페 존 머리가긴가 에이프라 아오이페

12 Human knowledge belongs to the world.

13 Information theory - Entropy Decision Tree Director of TEAMLAB Sungchul Choi

14 Entropy - Entropy는목적달성을위한경우의수를정량적으로표현하는수치 è 작을수록경우의수가적음 - Higher Entropy à Higher uncertainty - Lower Entropy à Lower uncertainty Entropy 가작으면얻을수있는정보가많다.

15 Entropy h(d) = m P i=1 p i log 2 (p i ) where ( D p i Data set Probability of label i log 2 p(i) log 2 p(i) p(i) p(i)

16 Entropy h(d) = m P i=1 p i log 2 (p i ) where ( D p i Data set Probability of label i - 확률이 1 이면 Entropy 0 log 2 p(i) - 확률이작을수록커짐 p(i)

17 Entropy - Example

18 h(d) = mx i=1 h(d) = 9 14 log 2 =0.940bits p i log 2 (p i ) log

19 Human knowledge belongs to the world.

20 Algorithms of Decision Tree Decision Tree Director of TEAMLAB Sungchul Choi

21 Growing a Decision Tree - Decision Tree 를성장 ( 만드는 ) 시키는알고리즘이필요 - 어떻게하면가장잘분기 (branch) 를만들수있는가? - Data의 attribute 를기준으로분기를생성 - 어떤 attribute 를기준이면가장 entropy 가작은가? - 하나를자른후에그다음은어떻게할것인가?

22 Growing a Decision Tree

23 Growing a Decision Tree youth Age senior Middle_aged

24 Growing a Decision Tree youth Student Age Middle_aged buy senior yes no

25 Growing a Decision Tree youth Student Age Middle_aged buy senior Credit yes no fair excellent buy NOT

26 Growing a Decision Tree youth Student Age Middle_aged buy senior Credit yes no fair excellent buy NOT buy NOT

27 Growing a Decision Tree - Decision Tree 는재귀적으로생김 - 대상라벨에대해어떤 Attribute 가더확실한정보를제공하고있는가? 로 branch attribute를선택 - 확실한정보의선택기준은알고리즘별로차이가남 - Tree 생성후 pruning 을통해 Tree generalization 시행 - 일반적으로효율을위해 Binary Tree 를사용

28 Decision Tree 의특징 - 비교적간단하고직관적으로결과를표현 - 훈련시간이길고, 메모리공간을많이사용함 - Top-down, Recursive, Divide and Conquer 기법 - Greedy 알고리즘 -> 부분최적화

29 Decision Tree 의장점 - 트리의상단부분 attribute들이가장중요한예측변수 è attribute 선택기법으로도활용할수있음 - Attribute 의 scaling이필요없음 - 관측치의절대값이아닌순서가중요 à Outlier 에이점 - 자동적변수부분선택 ç Tree pruning

30 Algorithms of Decision Tree - 크게두가지형태의 decision tree 알고리즘존재 - 알고리즘별 attribute branch 방법이다름 - ID3 à C4.5(Ross Quinlan), CART - 연속형변수를위한 regression tree도존재

31 Human knowledge belongs to the world.

32 ID3 & Information Gain Decision Tree Director of TEAMLAB Sungchul Choi

33 Information Gain - Entropy 함수를도입하여 branch splitting - Information Gain: Entropy를사용하여속성별분류시 Impurity 를측정하는지표 - ( 전체 Entropy 속성별 Entropy ) 로속성별 Information Gain을계산함

34 Info(D) = nx i=1 Information Gain p i log 2 (p i ) 전체데이터 D 의정보량 Info A (D) = vx j=1 D j D Info(D j) 속성 A 로분류시정보량 Gain(A) =Info(D) Info A (D) A 속성의정보소득

35 ID3 Process

36 Growing a Decision Tree

37 Growing a Decision Tree Age Gain(age) =Info(D) Info a ge(d) Credit Gain(credit) =Info(D) Info credit (D) Income Gain(Income)=Info(D) Info Income (D) Student Gain(Studnet)=Info(D) Info Student (D)

38 Growing a Decision Tree Age Gain(age) =Info(D) Info a ge(d) Info age (D) = vx j=1 D j D Info(D j) j 3 {youth, moddle age, senior}

39 Growing a Decision Tree Age Gain(age) =Info(D) Info a ge(d) Info age (D) = vx j=1 Info age (D) = log log log 2 D j D Info(D j) log log 2 2 5

40 Growing a Decision Tree Age Gain(age) =Info(D) Info a ge(d) Info(D) = 9 14 log log Gain(age) =Info(D) Info a ge(d)

41 Growing a Decision Tree Age Gain(age) =Info(D) Info a ge(d) Info(D) = log log 2 14

42 Growing a Decision Tree Age Gain(age) =Info(D) Info a ge(d) j 3 {youth, moddle age, senior} Info age (D) = vx j=1 D j D Info(D j)

43 Growing a Decision Tree Age Gain(age) =Info(D) Info a ge(d)

44 Growing a Decision Tree Age Credit Gain(age) =Info(D) Info a ge(d) Income Gain(credit) =Info(D) Info credit (D) Student Gain(Income)=Info(D) Info Income (D) Gain(Studnet)=Info(D) Info Student (D)

45 Growing a Decision Tree youth Age Middle_aged buy senior

46 Growing a Decision Tree Income Student Gain(Income)=Info(D youth ) Info Income (D youth ) Gain(Student)=Info(D youth ) Info Student (D youth ) Credit Gain(credit) =Info(D youth ) Info credit (D youth )

47 Growing a Decision Tree youth Student Age Middle_aged buy senior Credit yes no fair excellent buy NOT

48 Human knowledge belongs to the world.

49 C4.5 & Gini Index Decision Tree Director of TEAMLAB Sungchul Choi

50 Information Gain 의문제점 - Attribute 에포함된값이다양할수록선택하고자함 Gain(A) =Info(D) Info A (D) Info A (D) = vx j=1 D j D Info(D j) Info(D) = nx i=1 p i log 2 (p i ) - 한 Attribute 가모두다른값을가질때? 보완을해줄다른 Measure 가필요

Gain Ratio - ID3 의발전형인 C4.5 알고리즘에서사용되는 measure http://dl.acm.org/citation.cfm?

51 Gain Ratio - ID3 의발전형인 C4.5 알고리즘에서사용되는 measure - Info(D) 의값을평준화시켜분할정보값을대신사용 SplitInfo A (D) = GainRatio(A) = vx j=1 D j D D j log 2 D log 2 p(i) Gain(A) SplitInfo A (D) = Info(D) Info a(d) SplitInfo A (D) p(i)

52 Gini Index - CART 알고리즘의 split measure - 훈련튜플세트를파티션으로나누었때불순한정도측정 Gini(D) =1 mx i=1 p 2 i =1 mx i=1 C i,d D where C i is a class - 데이터의대상속성을얼마나잘못분류할지를계산

53 Gini Index - 실제 Gini Index 는 Entropy 와비슷한그래프가그려짐 일때 Impurity 의최대화, 약극점에서 0 Gini(D) = mx p i (1 p i )=1 mx p 2 i i=1 i=1

54 Binary Split - CART 알고리즘은 Binary Split 을전제로분석함 - k 가속성내데이터분류의개수일때 2 k$1 1 개만큼의 Split 생성 k = =3 Gini A (D) = D 1 D Gini(D 1)+ D 2 D Gini(D 2) - 가장 Gini 값이적은분류를선택

55 Growing a Decision Tree

56 Growing a CART Decision Tree Age Gini age (D) Credit Gini credit (D) Income Gini income (D) Student Gini student (D)

57 Growing a CART Decision Tree Age Gini age (D) age 2 {youth, middle age, senior} age 1 2 {youth} = {middle age, senior} age 2 2 {middle age} = {youth, senior} age 3 2 {senior} = {youth, middle age} 세가지경우의모든 Gini Index 산출

58 Growing a CART Decision Tree Age Gini age (D) age 2 {youth, middle age, senior} Gini A (D) = D 1 D Gini(D 1)+ D 2 D Gini(D 2) Gini age1 (D) = 5 14 Gini(D 1) Gini(D 2) Gini(D 1 )=1 Gini(D 2 )=

59 Growing a CART Decision Tree Age Gini age (D) age 2 {youth, middle age, senior} age 1 2 {youth} = {middle age, senior} age 2 2 {middle age} = {youth, senior} age 3 2 {senior} = {youth, middle age} Min(Gini agei )=0.357

60 Growing a CART Decision Tree Min(Gini agei )=0.357 Min(Gini incomei )=0.443 Min(Gini credit )=0.429 Min(Gini student )=0.367

61 CODE Gini(D) =1 mx i=1 p 2 i =1 mx i=1 C i,d D

62 CODE

63 CODE Gini A (D) = D 1 D Gini(D 1)+ D 2 D Gini(D 2)

64 Human knowledge belongs to the world.

65 Tree prunning Decision Tree Director of TEAMLAB Sungchul Choi

66 Decision Tree 를만들다생기는문제점 - class의 leaf node 의결정 - 너무많을경우 à Overfitting - impurity 또는 variance 는낮은데, 노드에데이터가 1개 - 어떤시점에서트리가지치기해야할지결정이중요

67 Pre-pruning - Tree 를생성할때, 일정기준이하면노드생성 X è 하위노드개수, 하위노드의 label 비율 ( 한쪽이 95?) - Threshold를잡아줘야하는어려움, CHAID 등사용 - 계산효율이좋고, 작은데이터셋에서잘작동 - 속성을놓칠수있음, underfitting 가능성이높음

68 Post-pruning - Tree 를생성한후, 트리의오차율최소화를위해실행 - 오분류율최소화, cost complexity 최소화등을사용 - 검증을위한 validation set 을따로생성함

69 오분류율최소화 - 아래와같은검증데이터가있을경우

70 오분류율최소화

71 오분류율최소화

72 Human knowledge belongs to the world.

Probability Overview Naive Bayes Classifier Director of TEAMLAB Sungchul Choi

Probability Overview Naive Bayes Classifier Director of TEAMLAB Sungchul Choi 머신러닝의학습방법들 - Gradient descent based learning - Probability theory based learning - Information theory based learning - Distance