Calculating entropies of attributes

Question

Can you please show the step by step calculation of Entropy(Ssun)? I do not understand how 0.918 is arrived at.

I tried but I get the values as 0.521089678, 0.528771238, 0.521089678 for Sunny, Windy, Rainy.

I was able to calculate the target entropy (Decision) correctly as = -(6/10)*log(6/10) + -(2/10)log(2/10) + -(1/10)log(1/10) + -(1/10)log(1/10) = 1.570950594

I am totally stuck at the next step. Request your help.

Reference: http://www.doc.ic.ac.uk/~sgc/teaching/pre2012/v231/lecture11.html Please search for "The first thing we need to do is work out which attribute will be put into the node at the top of our tree:" to reach the line I am referring to.

Answer 1

Consider the formula for Entropy:

$E(S) = \sum_\limits{i=1}^{n}-p_{i}\log_2p_{i}$

Expanding that summation for the four concept decision attributes for your problem gives

$E(S) = -p_{cinema}\log_2\left(p_{cinema}\right) - p_{tennis}\log_2\left(p_{tennis}\right) - p_{stayin}\log_2\left(p_{stayin}\right) - p_{shopping}\log_2\left(p_{shopping}\right)$

There are three observations where Weather=Sunny. Of those three, one has Decision=Cinema and two have Decision=Tennis. So for Weather=Sunny you have $p_{cinema}=\frac{1}{3}$, $p_{tennis}=\frac{2}{3}$, and other decision probabilities are zero. Plugging those values into the equation above gives

$ \begin{align} E(S_{Sun}) &= -\frac{1}{3}\log_2\left(\frac{1}{3}\right)-\frac{2}{3}\log_2\left(\frac{2}{3}\right) - \left(0\right)\cdot\log_2\left(0\right) - \left(0\right)\cdot\log_2\left(0\right) \\ &= 0.38998 + 0.52832 + 0 + 0 \\ &= 0.918 \end{align}$

Answer 2

Let me first explain the concept of entropy for decision trees:

Entropy is a so called impurity measure for a set of elements. Impurity - being the opposite of purity - is referring to the distribution of the decision categories (or class labels) within the set. Initially, each row in the table is one element and your set of elements are all rows of your table. This set is called pure if it just consists of the same class label and it is called impure if it contains all different class labels in the same proportion. Translating into the values of entropy (remember being an impurity measure, the set has in the latter case the highest possible value and in the former case (just the same class label) the lowest value. The lowest possible value for entropy is 0.

So let's choose a visual respresentation to illustrate what really counts and what does not matter for the entropy.

1) You start off with the initial table which contains the following class labels:

Please note that for computing the entropy none of the remaining attributes, attribute values matter, also the order of the rows don't matter (entropy is a measure for a set of elements)

2) You convert the different class labels to different colors

3) So instead of this table with the colored class labeled, you just draw a circle ("ball") for each class label (=element)

Now you throw all the balls in a bag. There you go! Your elements of a set are represented as balls in a bag. If you open the bag and look into it, you might see

1. just balls of the same color --> one pure color. The entropy says, it's not impure at all, I give it a zero! entropy = 0
2. the same amount of balls in different colors --> that doesn't look pure at all, it's impure! The entropy assigns the highest possible value to this set (bag). The highest possible entropy value depends on the number of class labels. If you have just two, the maximum entropy is 1. In your case, you have 4 different class labels, so the maximum entropy would be e.g. if you had 12 balls and 3 balls of each color. The maximum entropy of a 4 class set is 2.
3. none of the above. Then your entropy is between the two values. If one color is dominant then the entropy will be close to 0, if the colors are very mixed up, then it is close to the maximum (2 in your case).

How does a decision tree use the entropy?

Well, first you calculate the entropy of the whole set. That impurity is your reference. What your decision tree tries to achieve is to reduce the impurity of the whole set. So the information Gain for a given attribute is computed by taking the entropy of the whole set and subtracting it with the entropies of sets that are obtained by breaking the whole set into one piece per attribute category. To make sure a set with just a few elements don't get the same weight as a set with many elements the entropies of sets are multiplied by their relative frequency.

Coming back to the example, for computing the Gain (S, parents) you need to compute the weighted entropies of the two sets: set 1 = all rows with category(parent) = yes and set 2 = all rows with category(parent) = no).

Set 1 refers to five rows, all having the decision category = cinema(just 5 orange balls!) So the weight is 5 rows out of 10 rows = 5/10 = 0.5. And the entropy is 0 (totally pure) or by applying the formula:

You have a sum over all class labels so n = 4. So you assign a class label to each of the i's. E.g.

For i = 1 being cinema: - (5/5 * log(3/3) = - (1 * log(1)) = - (1*0) = 0

For i = 2 being tennis: - (0/5 * log(0/3) = - (0 * log(0)) = 0

For i = 3 being stay in: - (0/5 * log(0/3) = - (0 * log(0)) = 0

For i = 4 being shopping: - (0/5 * log(0/3) = - (0 * log(0)) = 0

So the sum of all four is 0. 0 times the weight 0.5 equals 0.

Set 2 also refers to five rows, having the decision categories = 1*cinema, 2*tennis, 1*stay in, 1*shopping So the weight is also 5 rows out of 10 rows = 5/10 = 0.5. Applying the formula:

For i = 1 being cinema: - (1/5 * log(1/5) = - (0.2 * -2,32) = 0.46

For i = 2 being tennis: - (2/5 * log(2/5) = - (0.4 * -1,32) = 0.53

For i = 3 being stay in: - (1/5 * log(1/5) = - (0.2 * -2,32) = 0.46

For i = 4 being shopping: - (1/5 * log(1/5) = - (0.2 * -2,32) = 0.46

So the sum of all four is 1.92. 1.92 times the weight 0.5 = 0.96. Thus, the Gain for this attribute is: Initial entropy - weighted entropies for all attribute categories: 1.57 - 0 - 0.96 = 0.61.

For the other attributes you do the same calculation.