Decision Trees, Entropy and Information Gain

A decision tree classifies data by asking a sequence of simple questions, much like a doctor working through a checklist or a game of twenty questions. The clever part is deciding which question to ask first. Decision trees make that choice mathematically, using entropy and information gain from information theory, and in this article we compute both by hand on a small dataset.

How a Decision Tree Works

A tree has three kinds of parts:

• Internal nodes test a feature, for example "Did the student attend tutoring?"
• Branches represent the possible answers.
• Leaves give the final prediction, such as "Pass" or "Fail".

To classify a new example, you start at the root and follow the branches that match its features until you reach a leaf. Training a tree means choosing, at each node, the question that best separates the classes. A good question produces child groups that are as pure as possible, ideally containing just one class each. To measure purity we need entropy.

Entropy: Measuring Uncertainty

For a set \(S\) containing classes in proportions \(p_1, p_2, \dots, p_k\), the entropy is

$$ H(S) = -\sum_{i=1}^{k} p_i \log_2 p_i $$

with the convention \(0 \log_2 0 = 0\). For two classes:

• A pure set (all one class) has \(H = 0\): no uncertainty.
• A 50/50 split has \(H = -0.5\log_2 0.5 - 0.5\log_2 0.5 = 1\) bit: maximum uncertainty.
• Anything in between gives a value between 0 and 1.

Entropy is measured in bits because, roughly speaking, it is the average number of yes/no questions needed to identify the class of a randomly chosen member.

Information Gain

When we split \(S\) on a feature \(A\) into subsets \(S_v\), the weighted average entropy of the children is

$$ H(S \mid A) = \sum_{v} \frac{|S_v|}{|S|}\,H(S_v) $$

The information gain is the reduction in entropy:

$$ \text{IG}(S, A) = H(S) - H(S \mid A) $$

The ID3 algorithm, introduced by J. Ross Quinlan in 1986, simply chooses the feature with the largest information gain at each node, splits, and repeats on each child.

The Dataset

A tutor recorded results for ten students, noting whether each studied many hours (High) or few (Low) and whether they attended tutoring:

Overall there are 6 passes and 4 fails.

Worked Example 1: Choosing the Root Split

Step 1: Entropy of the whole set. With \(p_{\text{pass}} = 0.6\) and \(p_{\text{fail}} = 0.4\), and using \(\log_2 0.6 \approx -0.7370\) and \(\log_2 0.4 \approx -1.3219\):

$$ H(S) = -0.6(-0.7370) - 0.4(-1.3219) = 0.4422 + 0.5288 = 0.9710 $$

Step 2: Split on Study hours.

• High: 5 students, 4 pass and 1 fail. \(H = -0.8\log_2 0.8 - 0.2\log_2 0.2 = 0.2575 + 0.4644 = 0.7219\)
• Low: 5 students, 2 pass and 3 fail. \(H = 0.9710\) (the same proportions as the root, just swapped)

$$ H(S \mid \text{Study}) = \tfrac{5}{10}(0.7219) + \tfrac{5}{10}(0.9710) = 0.8464 $$

$$ \text{IG}(\text{Study}) = 0.9710 - 0.8464 = 0.1245 $$

Step 3: Split on Tutoring.

• Yes: 4 students, all pass. \(H = 0\)
• No: 6 students, 2 pass and 4 fail. Using \(\log_2(1/3) \approx -1.5850\) and \(\log_2(2/3) \approx -0.5850\):

$$ H = -\tfrac{1}{3}(-1.5850) - \tfrac{2}{3}(-0.5850) = 0.5283 + 0.3900 = 0.9183 $$

$$ H(S \mid \text{Tutoring}) = \tfrac{4}{10}(0) + \tfrac{6}{10}(0.9183) = 0.5510 $$

$$ \text{IG}(\text{Tutoring}) = 0.9710 - 0.5510 = 0.4200 $$

Step 4: Decide. Tutoring gives much more information (0.420 bits against 0.125 bits), so it becomes the root. Its "Yes" branch is already pure and becomes a leaf labelled Pass.

Worked Example 2: Growing the Next Level

Now consider only the six students who did not attend tutoring (students 5 to 10): 2 pass and 4 fail, with entropy 0.9183. The only remaining feature is Study hours.

Step 1: Children.

• High (students 5, 7): 1 pass, 1 fail. \(H = 1\)
• Low (students 6, 8, 9, 10): 1 pass, 3 fail.

$$ H = -0.25\log_2 0.25 - 0.75\log_2 0.75 = 0.5 + 0.3113 = 0.8113 $$

Step 2: Weighted entropy.

$$ H(S_{\text{No}} \mid \text{Study}) = \tfrac{2}{6}(1) + \tfrac{4}{6}(0.8113) = 0.3333 + 0.5409 = 0.8742 $$

Step 3: Gain.

$$ \text{IG} = 0.9183 - 0.8742 = 0.0441 $$

The gain is small. Splitting further would create leaves predicting "Fail" for both High and Low (since fails form the majority or a tie in each), so the split changes no predictions. A sensible tree stops here:

1. Attended tutoring? Yes → Pass
2. No → Fail (correct for 4 of 6 students)

The final tree classifies 8 of the 10 students correctly with a single question.

Gini Impurity: The Alternative

The CART algorithm, used by default in Python's scikit-learn, measures impurity with the Gini index:

$$ G(S) = 1 - \sum_{i} p_i^2 $$

For our root, \(G = 1 - (0.6^2 + 0.4^2) = 1 - 0.52 = 0.48\). After splitting on Tutoring, the "Yes" child has \(G = 0\) and the "No" child has \(G = 1 - (\tfrac{1}{9} + \tfrac{4}{9}) = 0.4444\), giving a weighted Gini of \(0.6 \times 0.4444 = 0.2667\). For Study hours the weighted Gini is \(0.5(0.32) + 0.5(0.48) = 0.40\). Gini also prefers Tutoring. In practice Gini and entropy usually choose the same splits; Gini is slightly faster because it avoids logarithms.

Avoiding Overfitting

A tree allowed to grow without limit can memorise every training example, including the noise. Common remedies are:

• Pre-pruning: set a maximum depth, a minimum number of samples per leaf, or a minimum gain.
• Post-pruning: grow a full tree, then remove branches that do not improve performance on validation data.
• Ensembles: random forests and gradient boosting combine many trees to reduce variance and usually beat a single tree.

A further subtlety: information gain is biased towards features with many distinct values, such as a student ID number, which splits the data into pure single-member groups. Quinlan's later C4.5 algorithm corrects for this using the gain ratio, which divides the gain by the entropy of the split itself.

Did You Know?

• Entropy in this sense was defined by Claude Shannon in his 1948 paper that founded information theory.
• Decision trees are among the most interpretable models: a doctor or loan officer can read the rules directly.
• Continuous features such as marks or income are handled by testing thresholds like "marks ≤ 55" and choosing the threshold with the best gain.

Key Takeaways

• Entropy \(H = -\sum p_i\log_2 p_i\) measures how mixed a group is, from 0 (pure) to 1 bit for a two-class 50/50 split.
• Information gain is the drop in weighted entropy after a split; trees choose the feature with the largest gain.
• Gini impurity is a quicker alternative that usually agrees with entropy.
• Pruning, depth limits and ensembles prevent trees from overfitting.

Need help building decision trees, calculating information gain or finishing a data mining assignment? Amathify's experts and PhD scholars provide step-by-step solutions; message us on WhatsApp or use the Ask a Question form.