Scribd
Upload
3 views6 pages

Decision Tree Example

The document provides a numerical example of the ID3 decision tree algorithm, detailing the calculation of entropy and information gain for various attributes (Outlook, Temp, Humidity, Wind) in a dataset related to playing tennis. It shows how to compute the entropy for different subsets and determine the attribute with the maximum information gain, which is Outlook in this case. The example concludes with the classification of instances based on the derived decision tree.

Uploaded by

elumalainarendran29
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views6 pages

Decision Tree Example

The document provides a numerical example of the ID3 decision tree algorithm, detailing the calculation of entropy and information gain for various attributes (Outlook, Temp, Humidity, Wind) in a dataset related to playing tennis. It shows how to compute the entropy for different subsets and determine the attribute with the maximum information gain, which is Outlook in this case. The example concludes with the classification of instances based on the derived decision tree.

Uploaded by

elumalainarendran29
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Decision Tree – ID3 Algorithm numerical Example:

Day Outlook Temp Humidity Wind PlayTennis


D1 Sunny Hot High Weak No
D2 Sunny Hot High Strong No
D3 Overcast Hot High Weak Yes
D4 Rain Mild High Weak Yes
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Strong Yes
D8 Sunny Mild High Weak No
D9 Sunny Cool Normal Weak Yes
D10 Rain Mild Normal Weak Yes
D11 Sunny Mild Normal Strong Yes
D12 Overcast Mild High Strong Yes
D13 Overcast Hot Normal Weak Yes
D14 Rain Mild High Strong No

Attribute: Outlook

Values (outlook) = Sunny, Overcast, Rain

Pr(cj) is the probability of class cj in data set D


S = [9+,5-]

Entropy(S) = - 9/14 log2 9/14 – 5/14 log2 5/14 = 0.94

Ssunny <- [2+,3-]

Entropy(S) = - 2/5 log2 2/5 – 3/5 log2 3/5 = 0.971

SOvercast <- [4+,0-]

Entropy(S) = - 4/4 log2 4/4 – 0/4 log2 0/4 = 0

SRain <- [3+,2-]

Entropy(S) = - 3/5 log2 3/5 – 2/5 log2 2/5 = 0.971

Expected information (entropy) needed to classify a tuple in D:

Information needed (after using A to split D into v partitions) to


classify D:
v | Dj |
Info A ( D)    Info( D j )
j 1 |D|

Information gained by branching on attribute A

Gain(A)  Info(D)  Info A(D)


Gain(S,Outlook) = Entropy(S) - ∑v<-[Sunny,Overcast,Rain] |Sv| / |S| .

Entropy(Sv)

Gain(S,Outlook) = Entropy(S) – 5/14 Entropy(Ssunny) – 4/14

Entropy(Sovercast) – 5/14 Entropy(SRain)

= 0.2464

Values (Temp) = Hot, Mild, Cool

S= [9+,5-] Entropy(S) = 0.94

Shot <- [2+,2-] Entropy(S) = 1.0

Smild <- [4+,2-] Entropy(S) = 0.9183

Scool <- [3+,1-] Entropy(S) = 0.8113

Gain(S,Temp) = Entropy(S) - ∑v<-[Hot,Mild,Cool] |Sv| / |S| .

Entropy(Sv)

Gain(S, Temp) = Entropy(S) – 4/14 Entropy(SHot) – 6/14

Entropy(SMild) – 4/14 Entropy(SCool)

= 0.0289
Values (Humidity) = High, Normal

S= [9+,5-] Entropy(S) = 0.94

SHigh <- [3+,4-] Entropy(S) = 0.9852

SNormal <- [6+,1-] Entropy(S) = 0.5916

Gain(S,Humidity) = Entropy(S) - ∑v<-[High,Normal] |Sv| / |S| .

Entropy(Sv)

Gain(S,Humidity) = Entropy(S) – 7/14 Entropy(SHigh) – 7/14

Entropy(SNormal)

= 0.1516

Values (Wind) = Strong,Weak

S= [9+,5-] Entropy(S) = 0.94

SStrong <- [3+,3-] Entropy(S) = 1.0

SWeak <- [6+,2-] Entropy(S) = 0.8113

Gain(S, Wind) = Entropy(S) - ∑v<-[ Strong,Weak] |Sv| / |S| .

Entropy(Sv)

Gain(S, Wind) = Entropy(S) – 7/14 Entropy(SStrong) – 7/14

Entropy(SWeak)

= 0.0478
Gain(S, Outlook) = 0.2464 = max gain

Gain(S, Temp) = 0.0289

Gain(S, Humidity) = 0.1516

Gain(S, Wind) = 0.0478

Outlook [9+,5-] {D1,D2,..D14}

Sunny Overcast Rain

{D1,D2,D8,D9,D11} {D3,D7,D12,D13} {D4,D5,D6,D10,D14}

[2+,3-] [4+,0-] [3+,2-]

? YES ?
Day Temp Humidity Wind Playennis
D1 Hot High Weak No
D2 Hot High Strong No
D8 Mild High Weak No
D9 Cool Normal Weak Yes
D11 Mild Normal Strong Yes

D1,D2, D8 -> High - > No

D9, D11 -> Normal -> Yes

Day Temp Humidity Wind Playennis


D4 Mild High Weak Yes
D5 Cool Normal Weak Yes
D6 Cool Normal Strong No
D10 Mild Normal Weak Yes
D14 Mild High Strong No

D6,D14 -> Strong - > No

D4,D5,D10 -> Weak -> Yes

You might also like