Calculating the entropy of an attribute in the ID3 algorithm when a split is perfectly classified
<p>I have been reading about the ID3 algorithm recently and it says that the best attribute to be selected for splitting should result in the maximum information gain which can be computed with the help of the entropy. </p>

<p>I have written a simple python program to compute the entropy. It is shown below:</p>

<pre><code>def _E(p, n):
    x = (p/(p+n))
    y = (n/(p+n))
    return(-1* (x*math.log2(x)) -1* (y*math.log2(y)))
</code></pre>

<p>However suppose we have a table consisting of 10 elements as follows:</p>

<p>x = [1, 0, 1, 0, 0, 0, 0, 0, 0, 0]</p>

<p>y = [1, 1, 1, 0, 1, 0, 1, 0, 1, 0]</p>

<p>Where x is the attribute and y is the class. Here P(0) = 0.8 and P(1) = 0.2. The entropy will be as follows:</p>

<p>Entropy(x) = 0.8*_E(5, 3) + 0.2*_E(2, 0)</p>

<p>However the second split P(1) is perfectly classified and this results in a math error since log2(0) is negative infinity. How is the entropy calculated in such cases?</p>

<p>The entropy of a split measures the uncertainty associated with the class labels in that split. In a binary classification problem (classes = {0,1}), the probability of class 1 (in your text, x) can range from 0 to 1. The entropy is maximum (with a value of 1) when x=0.5. Here both classes are equally probable. The entropy is minimum when one of the classes is absent, i.e. either x=0 or x=1. Here, there is no uncertainty regarding the class, hence the entropy is 0.</p>

<p><br/><br/>
Graph of entropy (y-axis) vs x (x-axis):</p>

<p><a href="http://i.stack.imgur.com/GXnDC.png" rel="nofollow"><img src="http://i.stack.imgur.com/GXnDC.png" alt="Graph of entropy (y-axis) vs x (x-axis)"></a></p>

<p><br/><br/>
The following calculation shows how to deal with the entropy calculation mathematically, when x=0 (the case when x=1 is analogous):</p>

<p><a href="http://i.stack.imgur.com/rCrwe.png" rel="nofollow"><img src="http://i.stack.imgur.com/rCrwe.png" alt="enter image description here"></a></p>

<p><br/>
In your program, you could treat x=0 and x=1 as special cases, and return 0. For other values of x, the above equation can be used directly.</p>

python machine-learning decision-tree