Decision tree Algorithm (ID3)

This is 2nd part of Decision tree tutorial. In last part we talk about Introduction of decision tree, Impurity measures and CART algorithm for generating the tree.

PART I-DECISION TREE CART ALGORITHM

This tutorial is about another important algorithm used in generating decision tree known as ID3. It is an acronym for iterative dichotomiser 3.

Formula

It will help in building tree,

So lets get started!!!

we will take the same weather data set , we have taken for explaining CART algorithm in previous story.

It has four attributes, outlook, humidity, temperature and wind.

The attribute which will have highest information gain is selected as a node.

ID3

1. It uses entropy as metric.
2. It is used for only classification problem

Root node

From the data set,we have

1. Number of observations = 14
2. Number of observations having Decision ‘Yes’ = 9
3. probability of ‘Yes’ , p(Yes) = 9/14
4. Number of observations having Decision ‘No’ =5
5. probability of ‘No’ , p(No) = 5/14

As we have four attribute, outlook, temperature, humidity, and wind

Information Gain on Sunny outlook factor

1. Number of instance for sunny outlook factor=5
2. Decision =’Yes’, prob(Decision=’Yes’ | outlook=sunny)=2/5
3. Decision =’No’, prob(Decision=’No’ | outlook=sunny)=3/5

Summary of Information Gain for all the attribute

1. Gain(Decision, outlook) = 0.247
2. Gain(Decision, wind ) = 0.048
3. Gain(Decision, temperature) = 0.029
4. Gain(Decision, humidity) = 0.151

So, outlook has the highest information gain so it is selected as first node/ root node.

Information Gain on Temperature under Sunny outlook factor

Summary of information gain on all attribute under Sunny outlook factor

1. Gain(sunny, temp) = 0.57
2. Gain(sunny, humidity) = 0.97
3. Gain(sunny, wind) =0.019

we can see that information gain of ‘Humidity’ attribute is higher than other. so, it is next node under sunny outlook factor.

Information Gain on overcast outlook factor

1. Total number of Observation =4
2. Prob(Decision=’Yes’,overcast)=1
3. Prob(Decision=’No’,overcast)=0

Since, All the decision are ‘Yes’ , so

Entropy(Decision, Overcast)=0

So, if outlook=overcast then decision is ‘Yes’ . so, It is a leaf node. It cant be further divided.

Information Gain on humidity factor

humidity takes two value, normal and high.

From the both table, you can infer that, whenever humidity is high decision is ‘No’

And, when humidity is normal decision is ‘Yes’

Information Gain on Rainfall outlook factor

1. Number of instance for rainfall outlook factor=5
2. Decision =’Yes’, prob(Decision=’Yes’ | outlook=rainfall)=3/5
3. Decision =’No’, prob(Decision=’No’ | outlook=rainfall)=2/5

Information Gain on Wind under rainfall outlook factor

Entropy (rainfall, wind) =0

Gain(rainfall, wind)=0.97

Summary of information Gain on all features under rainfall outlook factor

1. Gain(rainfall, wind)=0.97
2. Gain(rainfall, temp)=0.019

So, wind attribute has highest information gain. So it is selected as next node under rainfall outlook factor.

Information Gain on wind

wind takes two value, weak and strong.

From the two table, the decision is always ‘No’ when wind is ‘strong’ and decision is always ‘Yes’ when wind is ‘weak’. So wind is also an leaf node.

So, we have explained the generation of decision tree in step by step manner.

That’s it. Thank you,