# How to calculate the entropy in the ID3 decision tree algorithm?

Here is the definition of the entropy

$$H(S)=-\sum_{x \in X} p(x) \log _{2} p(x)$$

Wikipedia's description of entropy breaks down the formula, but I still don't know how to determine the values of $$X$$, defined as

The set of classes in $$S$$

and $$p(x)$$, defined as

The proportion of the number of elements in class $$x$$ to the number of elements in set $$S$$.

Can anyone break this down further to explain how to find $$p(x)$$?

Suppose you have data:

color  height  quality
=====  ======  =======
green  tall    good
blue   short   medium
red    tall    medium
red    short   medium


To calculate the entropy for quality in this example:

X  = {good, medium, bad}
x1 = {good}, x2 = {bad}, x3 = {medium}


Probability of each x in X:

p1 = 1/6 = 0.16667
p2 = 2/6 = 0.33333
p3 = 3/6 = 0.5


for which logarithms are:

log2(p1) = -2.58496
log2(p2) = -1.58496
log2(p3) = -1.0


and therefore entropy for the set is:

H(X) = - (0.16667 * -2.58496) - (0.33333 * -1.58496) - (0.5 * -1.0)
= 1.45915


by the formula in the question.

Remaining tasks are to iterate this process for each attribute to form the nodes of the tree.

• how are p1, p2, and p3 calculated?
– MSB
Jul 3, 2022 at 20:47
• p1 = 1/6 = 0.16667 p2 = 2/6 = 0.33333 p3 = 3/6 = 0.5 Jul 10, 2022 at 18:01

Very nice example that makes perfect sense to me. To get the value into expected range [0..1] normalization is needed.

$$H(S)_{norm}=\frac{H(S)}{log_2(|S|)}=\frac{H( \{good, bad, bad, medium, medium, medium\} )}{log_2(3)}=\frac{1.459147917027245}{1.584962500721156}=0.9206198357143052 \in [0..1]$$

✔️