3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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:

enter image description here

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

enter image description here

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

enter image description here

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ @bogatron: speaking of positive and negative examples can be confusing since the dataset has 4 different classes, the subset with weather = sunny just happens to have just two. $\endgroup$ – ee2Dev Feb 12 '15 at 13:50
  • $\begingroup$ You are correct - I mistakenly looked at the Parents attribute which only has two values (Yes/No) and just happened to work out to the same entropy value for Weather=Sunny. The answer is correct now. $\endgroup$ – bogatron Feb 12 '15 at 15:05
  • $\begingroup$ Unfortunately, I can't upvote you since I don't have enough points. $\endgroup$ – ee2Dev Feb 12 '15 at 15:53
  • $\begingroup$ @ee2Dev Thank you. Shall up-vote once I clear the up-vote threshold. $\endgroup$ – user1744649 Feb 13 '15 at 9:41
  • $\begingroup$ user1744649: Thanks if my answer was helpful you can also accept my answer. $\endgroup$ – ee2Dev Feb 13 '15 at 9:47
4
$\begingroup$

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}$

$\endgroup$
  • $\begingroup$ Thank you. Shall up-vote once I clear the up-vote threshold. $\endgroup$ – user1744649 Feb 13 '15 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.