Decision Trees (Part 3b) - Entropy

Entropy measures how well a given attribute separates the training examples w.r.t to their target classification, and is commonly used in the computation for information gain.

Given a set of data D, containing positive and negatives examples of a target predictive attribute, the entropy of D relative to this boolean classification is



where p+ is the proportion of positive examples in D and p- is the proportion of negative examples in D.

Consider the following example, which consists of 14 data records. It shows how customers fitting different criterias are approved/dis-approved in their credit card application.



This, D consists of 14 examples (9 positive examples (credit card approved) and 5 negative examples (credit card dis-approved)). Then the entropy of D w.r.t to this boolean classification is as follows:



In a nutshell, entropy specifies the minimum number of bits of information needed to encode the classification of an arbitrary member of D

If p+ is 1, then there is no need for any bit to encode whether a new test example is positive, since all the examples seen so far are positive examples. Hence, the entropy is 0. However, if p+ is 0.5, then 1 bit is needed to indicated whether a drawn sample is positive or negative example.

We will discuss how the entropy formulas can be used in computing the information gain of an attribute. An important note is that once we can determine the information gain of an attribute, we can then determine which attributes should be used in the top of a decision tree, and which are used in the later parts of the decision trees.