Notice
Recent Posts
Recent Comments
Link
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
Archives
Today
Total
관리 메뉴

이지훈님의 블로그

Decision Tree + ID3알고리즘 본문

ML

Decision Tree + ID3알고리즘

개발자입니다. 2017. 7. 1. 23:18

Decision Tree(결정트리) 

어떤 항목에 대한 관측값과 목표값을 연결시켜주는 예측 모델로써 결정 트리를 사용한다. 


장점 

1. 결과를 해석하고 이해하기 쉽다.간략한 설명만으로 결정 트리를 이해하는 것이 가능하다.

2. 자료를 가공할 필요가 거의 없다.다른 기법들의 경우 자료를 정규화하거나 임의의 변수를 생성하거나 값이 없는 변수를 제거해야 하는 경우가 있다.

3. 수치 자료와 범주 자료 모두에 적용할 수 있다.

4. 대규모 데이터 세트도 잘 동작한다.


한계 

1. 휴리스틱 기법을 기반하기 때문에 최적 결정트리라고 보장할 수 없다.

2. 너무 복잡한 결정트리를 만들 수 있다.

3. 약간의 차이에 따라 (레코드의 개수의 약간의 차이) 트리의 모양이 많이 달라질 수 있다. 두 변수가 비슷한 수준의 정보력을 갖는다고 했을 때, 약간의 차이에 의해 다른 변수가 선택되면 이 후의 트리 구성이 크게 달라질 수 있다.


알고리즘 : ID3, C4.5, CART 등이 있다.


ID3알고리즘 (범주형 자료만 분류 가능)

1. 루트노드 생성

2. 현재 트리에서 모든 단말노드에 대해서 아래를 반복한다.

A. 해당 노드의 샘플들이 같은 클래스이면, 해당 노드는 단말노드가 되고, 해당 클래스로 레이블을 부여

B. 더 이상 사용할 수 있는 속성이 없으면 수행 종료

C. Information Gain이 높은 속성을 선택해서 노드를 분할



Entropy (평균 정보량)  

출력값을 나타내기 위해 필요한 평균 비트 수

확률분포에 대한 기대값




공이 8개가 있다. 

여기서 어떤 하나의 공을 뽑을 확률은 1/8이고,  이 때 정보량은 3(bit)이다. 어떤 공인지 찾기 위해 3번의 질문이 필요하다는 의미이다. 



문제를  바꿔서, 빨간공이 3개,  파란공이 5개 있을 경우의 엔트로피를 계산해보자.





이 때의 엔트로피는 약 0.953이다. 정보량에 해당 공을 뽑을 확률을 한 번 더 곱해줘야 한다. 

즉 가중평균으로 엔트로피를 구한다.


엔트로피 참고자료 : http://www.aistudy.com/control/information_theory.htm


Information Gain

원래의 엔트로피와 세부 클래스로 분할된 후의 엔트로피의 차이이다.

information Gain이 클수록 분류하기 좋다는 것을 의미

ID3알고리즘은 Information Gain를 사용하여 노드를 결정한다.



직접 Information Gain을 계산해보자. Outlook, Temp, Humidity, Windy 등을 보고 언제 테니스를 치는지에 대해 분류하는 예제이다.


Outlook

Temperature

Humidity

Windy

Play?

sunny

hot

high

FALSE

No

sunny

hot

high

TRUE

No

overcast

hot

high

FALSE

Yes

rain

mild

high

FALSE

Yes

rain

cool

normal

FALSE

Yes

rain

cool

normal

TRUE

No

overcast

cool

normal

TRUE

Yes

sunny

mild

high

FALSE

No

sunny

cool

normal

FALSE

Yes

rain

mild

normal

FALSE

Yes

sunny

mild

normal

TRUE

Yes

overcast

mild

high

TRUE

Yes

overcast

hot

normal

FALSE

Yes

rain

mild

high

TRUE

No



Play의 엔트로피 계산




E(Play, Outlook)

 

Play

 

Yes

No

Total

Outlook

sunny

3

2

5

overcast

4

0

4

rain

3

2

5



E(Play,Temperature )

 

Play

 

Yes

No

Total

Temp..

hot

2

2

4

mild

4

2

6

cool

3

1

4



E(Play, Humidity)

 

Play

 

Yes

No

Total

Humidity

high

3

4

7

normal

6

1

7



E(Play, Windy)

 

Play

 

Yes

No

Total

Windy

TRUE

3

3

6

FALSE

6

2

8



이제 Information Gain을 구해보자.



Infomation Gain이 가장 큰 것은 Outlook이다. Outlook으로  분류하자.






이제 Sunny에서 분류를 하자.


Outlook

Temperature

Humidity

Windy

Play?

sunny

hot

high

FALSE

No

sunny

hot

high

TRUE

No

sunny

mild

high

FALSE

No

sunny

cool

normal

FALSE

Yes

sunny

mild

normal

TRUE

Yes




Humidity를 선택할 경우 Information Gain이 가장크다. Humidity를 가지로 선택한다.

이제 트리는 다음과 같은 모양을 가지게 된다.



Humidity에 속하는 클래스들은 모드 같은 레코드를 가지므로 Humidity에서 더 이상 가지를 만들지 않는다.


Outlook

Temperature

Humidity

Windy

Play?

sunny

hot

high

FALSE

No

sunny

hot

high

TRUE

No

sunny

mild

high

FALSE

No


Outlook

Temperature

Humidity

Windy

Play?

sunny

cool

normal

FALSE

Yes

sunny

mild

normal

TRUE

Yes


이제 Outlook에서 Overcast를 선택했을 때를 보자. 이 경우도 Play가 모두 Yes로 같은 class를 가지므로 넘어간다.


Outlook

Temperature

Humidity

Windy

Play?

overcast

hot

high

FALSE

Yes

overcast

cool

normal

TRUE

Yes

overcast

mild

high

TRUE

Yes

overcast

hot

normal

FALSE

Yes


트리에 가능한 가지는 Temperature, Windy 두 속성이 남았다.


Outlook

Temperature

Windy

Play?

rain

mild

FALSE

Yes

rain

cool

FALSE

Yes

rain

cool

TRUE

No

rain

mild

FALSE

Yes

rain

mild

TRUE

No




Rainy를 선택했을 때, Windy가 가지가 된다. 그리고 Windy의 속성에 따라 Play가 모두 같은 class를 가지므로 더 이상 가지를 만들지 않는다.

더 뻗어나갈 가지가 없으므로 트리는 아래 그림으로 완성된다.








'ML' 카테고리의 다른 글

Naive Bayesian Classification (python code)  (0) 2017.07.18
Logistic Regression  (0) 2017.07.10
Decision Tree + C4.5알고리즘  (0) 2017.07.03
Linear Regression  (0) 2017.04.20
Linear Classifier  (0) 2016.07.13
Comments