Question

Given the following six instances each with five attributes (Outlook, Temperature, Humidity, Wind, Day) and one class label, calculate Entropy of the whole system • calculate Information gain for attribute "Outlook" • calculate Gini-index for attribute "Outlook" • What is the information gain and Gini-index for attribute “Day Explain why “Day" is NOT a good feature being used as the root node of a decision tree. How to avoid using “Day” as the root node to create the tree ID 1 2 3 Outlook Sunny Sunny Overcast Overcast Sunny Rain Temperature Humidity Hot High Cool High Cool Normal Hot High Mild High Cool Normal Wind Weak Strong Weak Weak Weak Weak Day Class Monday No Tuesday No Wednesday No Thursday Yes Friday Yes Saturday Yes 5 6

Answer 1

a. The class attribute has two instances namely Yes and No. So, the entropy of the whole system is:

Entropy of the system = -p/(p+n) X log₂ [p/(p+n)] - n/(p+n) X log₂ [n/(p+n)]

where p is the number of positive(yes) in class and n is the number of negative(no) in class.

So, in the above dataset, we have p = 3 and n = 3

Putting the values of p and n in the above equation:

= -p/(p+n) X log₂ [p/(p+n)] - n/(p+n) X log₂ [n/(p+n)]

= -3/(3+3) X log₂ [3/(3+3)] -3/(3+3) X log₂ [3/(3+3)]

On calculating we get,

Entropy of class attribute or the whole system = 1

Information Gain I(p_i,n_i) formula is same as formula of entropy given above = -p/(p+n) X log₂ [p/(p+n)] - n/(p+n) X log₂ [n/(p+n)]

b. Information Gain For attribute Outlook:

In Outlook there are three instances namely Sunny, Overcast, and Rain. So we will calculate total number of Yes(p) and total number of No(n) for Outlook = Sunny. Similarly, calculate total number of Yes and total number of No for Outlook = Overcast and for Outlook = Rain.

Information Gain of Outlook if it is Sunny = -p_i/(p_i+n_i) X log₂ [p_i/(p_i+n_i)] - n_i/(p_i+n_i) X log₂ [n/(p_i+n_i)]

Here p_i=1  and n_i=2 if Outlook is Sunny.

So putting in the formula:

Information Gain of Outlook if it is Sunny = -1/(1+2) X log₂ [1/(1+2)] - 2/(1+2) X log₂ [2/(1+2)]

= -1/3 X log₂ [1/3)] - 2/(3) X log₂ [2/(3)]

= -0.333 X -1.586 - 0.666 X -0.586

= 0.528 + 0.390

= 0.918

Similarly, calculate total number of Yes and total number of No for Outlook = Overcast

Information Gain of Outlook if it is Overcast = -p_i/(p_i+n_i) X log₂ [p_i/(p_i+n_i)] - n_i/(p_i+n_i) X log₂ [n/(p_i+n_i)]

Here p_i=1  and n_i=1 if Outlook is Overcast.

So putting in the formula:

Information Gain of Outlook if it is Overcast= -1/(1+1) X log₂ [1/(1+1)] - 1/(1+1) X log₂ [1/(1+1)]

= 1

Similarly, calculate total number of Yes and total number of No for Outlook = Rain

Information Gain of Outlook if it is Rain= -p_i/(p_i+n_i) X log₂ [p_i/(p_i+n_i)] - n_i/(p_i+n_i) X log₂ [n/(p_i+n_i)]

Here p_i=1  and n_i=0 if Outlook is Rain.

So putting in the formula:

Information Gain of Outlook if it is Rain= -1/(1+0) X log₂ [1/(1+0)] - 0/(1+0) X log₂ [0/(1+0)]

= 0

So, information gain for attribute Outlook is as follows:

Outlook	Yes(pi)	No(ni)	Information Gain of Outlook
Sunny	1	2	0.918
Overcast	1	1	1
Rain	1	0	0

c. Gini Index For attribute Outlook:

Gini Index for a particular value of an attribute:

= 1 - (Probability of positive samples)² - (Probability of negative samples)²

In Outlook as we already know that there are three instances namely Sunny, Overcast, and Rain. So we will calculate total number of Yes(p) and total number of No(n) for Outlook = Sunny. Similarly, calculate total number of Yes and total number of No for Outlook = Overcast and for Outlook = Rain.

Gini Index of (Outlook = Sunny) = 1 - (Probability of positive samples)² - (Probability of negative samples)²

Here p_i=1  and n_i=2 if Outlook is Sunny.

So putting in the formula:

Gini Index of (Outlook = Sunny) = 1 - (1/3)² - (2/3)² = 0.444

Gini Index of (Outlook = Overcast) = 1 - (Probability of positive samples)² - (Probability of negative samples)²

Here p_i=1  and n_i=1 if Outlook is Overcast.

So putting in the formula:

Gini Index of (Outlook = Overcast)= 1 - (1/2)² - (1/2)² = 0.5

Gini Index of (Outlook = Rain) = 1 - (Probability of positive samples)² - (Probability of negative samples)²

Here p_i=1  and n_i=0 if Outlook is Rain.

So putting in the formula:

Gini Index of (Outlook = Rain)= 1 - (1/1)² - (0/1)² = 0

Outlook	Yes(pi)	No(ni)	Gini Index of particular value of Outlook
Sunny	1	2	0.444
Overcast	1	1	0.5
Rain	1	0	0

Now, Gini Index of attribute Outlook = Weighted Sum of Gini Indexes of values of attribute Outlook

= (probability of total Instances of Outlook=Sunny in dataset)* Gini Index of (Outlook=Sunny) + (probability of total Instances of Outlook=Overcast in dataset)* Gini Index of (Outlook=Overcast) + (probability of total Instances of Outlook=Rain in dataset)* Gini Index of (Outlook=Rain)

= (3/6)*0.444 + (2/6)*0.5 + (1/6)*0

= 0.222 + 0.166

Gini Index of attribute Outlook = 0.388

d. Information Gain and Gini Index of attribute Day:

As we can see in the dataset that the attribute Day also has 6 different instances such as Monday, Tuesday....Saturday here if we will try to calculate the information gain, then either p_i or n_i will become 0 for a particular day because only Yes or NO is there for a single day. So information gain and Gini Index both will become 0. I will show you one example of this by solving for Day=Monday and Day=Thursday

Calculate total number of Yes and total number of No for Day = Monday

Information Gain of (Day=Monday) = -p_i/(p_i+n_i) X log₂ [p_i/(p_i+n_i)] - n_i/(p_i+n_i) X log₂ [n/(p_i+n_i)]

Here p_i=0 and n_i=1 if Day is Monday.

So putting in the formula:

Information Gain of (Day=Monday) = -0/(0+1) X log₂ [0/(0+1)] - 1/(0+1) X log₂ [1/(0+1)]

Information Gain of (Day=Monday) = 0

Calculate total number of Yes and total number of No for Day = Thursday

Information Gain of (Day=Thursday) = -p_i/(p_i+n_i) X log₂ [p_i/(p_i+n_i)] - n_i/(p_i+n_i) X log₂ [n/(p_i+n_i)]

Here p_i=1 and n_i=0 if Day is Thursday.

So putting in the formula:

Information Gain of (Day=Thursday) = -1/(1+0) X log₂ [1/(1+0)] - 0/(1+0) X log₂ [0/(1+0)]

Information Gain of (Day=Thursday) = 0

Similarly, for all other days, the information gain will be 0 and hence Information Gain for attribute Day = 0.

Also,

Gini Index For attribute Day:

Gini Index for a particular value of an attribute:

= 1 - (Probability of positive samples)² - (Probability of negative samples)²

In Day as we already know that there are 6 different instances, so we will calculate the total number of Yes(p) and the total number of No(n) for Day= Monday.

Gini Index of (Outlook = Sunny) = 1 - (Probability of positive samples)² - (Probability of negative samples)²

Here p_i=0 and n_i=1 if Day=Monday

So putting in the formula:

Information Gain of (Day= Monday) = 1 - (0/1)² - (1/1)² = 0

Similarly, for Day=Thursday:

Here p_i=1 and n_i=0

So putting in the formula:

Gini Index of (Day= Monday) = 1 - (1/1)² - (0/1)² = 0

So similarly, Gini Index for all days = 0 and hence

Therefore, Gini Index Of attribute Day = 0

e. Information Gain refers to the information which is learnt by the model to classify the instances, but as Day has 0 Information Gain, our model will not be able to learn how to correctly identify different instances. So, as already seen above, Day is not a good attribute or feature being used as the root node of a decision tree because it has 0 Information Gain and 0 Gini Index. Whereas, while constructing a decision tree, we should always select and attribute or feature with the Highest Information Gain but here Day has the lowest.

To avoid using Day as the root node to create the decision tree, we can either remove it from the data set completely or ignoring it while calculations. Also, we can use pruning that is removing nodes from decision tree which help nothing or very little while classifying different instances. Pruning will only be done if by chance a person has selected Day as the root node. But in this case, it is preferred to completely remove the attribute Day from the dataset to avoid using it as the root node for the decision tree.

Thanks!