What are the best ways to revise decision trees for undergraduate exams?

The best way to revise decision trees for undergraduate exams is to master the mathematical formulas for splitting criteria, specifically Entropy and Gini impurity, and practice calculating information gain by hand for small datasets. You must also understand how trees are constructed recursively and be able to explain the mechanisms used to prevent overfitting, such as pre-pruning and cost-complexity pruning.

Examiners test decision trees heavily because they form the foundational building block for advanced ensemble methods like random forests and gradient boosted trees. If you cannot calculate a split manually or explain why an algorithm chooses one feature over another, you will drop straightforward marks. You need to move beyond viewing a decision tree as a simple flowchart. At the university level, you must treat it as a greedy, recursive partitioning algorithm. By understanding the maths driving the splits and the regularisation techniques keeping the model generalisable, you will easily handle both calculation questions and theoretical essay prompts. Let us break down exactly what you need to study.

Understand the anatomy and the recursive splitting process

To secure high marks, you need to describe the construction of a decision tree using the correct algorithmic terminology. Exam papers will expect you to know that the standard algorithm used for building decision trees in modern software libraries is CART (Classification and Regression Trees).

You must be able to explain that CART is a recursive, binary partitioning algorithm. It starts at the root node with the entire training dataset. The algorithm then evaluates every possible split across all available features. It selects the single split that results in the greatest decrease in impurity (or the greatest information gain). The dataset is then divided into two subsets, creating two child nodes. This exact same process is then called recursively on each child node.

Crucially, you must explicitly state in your exam answers that this is a greedy algorithm. It makes the locally optimal choice at each specific node in the hope of finding a good general solution. You should point out that this greedy heuristic makes the training process computationally feasible, but it does not guarantee that the final tree is the globally optimal structure for the dataset. Highlighting this limitation shows a deep, practitioner-level understanding of the algorithm.

Master the maths behind Gini Impurity and Entropy

The most common decision tree question on any undergraduate machine learning paper involves calculating a node split by hand. You will typically be given a small table of data and asked to determine which feature the root node should split on. To do this, you must memorise the formulas for Gini Impurity and Entropy.

Entropy is a measure of disorder within a set of data. The formula is the negative sum of the probability of each class multiplied by the base-2 logarithm of that probability: Entropy = - sum(p * log2(p))

Gini Impurity is a measure of how often a randomly chosen element from the set would be incorrectly labelled if it was randomly labelled according to the distribution of labels in the subset. The formula is one minus the sum of the squared probabilities of each class: Gini = 1 - sum(p^2)

Let us walk through a short worked example of calculating Gini Gain, as this is exactly what you will do in the exam hall. Imagine a parent node containing 10 students. 6 passed their module, and 4 failed.

First, calculate the Gini impurity of the parent node: Probability of pass = 6/10 = 0.6 Probability of fail = 4/10 = 0.4 Parent Gini = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 1 - 0.52 = 0.48.

Now, imagine we propose a split based on whether the student attended lectures. This splits the 10 students into two child nodes. Child 1 (Attended): Contains 5 students. 4 passed, 1 failed. Child 2 (Did Not Attend): Contains 5 students. 2 passed, 3 failed.

Calculate the Gini impurity for each child node: Child 1 Gini = 1 - (0.8^2 + 0.2^2) = 1 - (0.64 + 0.04) = 1 - 0.68 = 0.32. Child 2 Gini = 1 - (0.4^2 + 0.6^2) = 1 - (0.16 + 0.36) = 1 - 0.52 = 0.48.

Finally, calculate the weighted average of the child nodes and subtract it from the parent node to find the Gini Gain: Weighted Child Impurity = (5/10 * 0.32) + (5/10 * 0.48) = 0.16 + 0.24 = 0.40. Gini Gain = Parent Gini (0.48) - Weighted Child Impurity (0.40) = 0.08.

In an exam, you would repeat this process for any other proposed splits and recommend the feature that produces the highest Gini Gain. Practising this exact sequence until it becomes second nature is the most reliable way to secure calculation marks.

Memorise the differences between classification and regression trees

Students frequently lose marks by assuming decision trees are only used for classification tasks. Exam papers will often include a specific question asking you to contrast a classification tree with a regression tree. You need to articulate two major differences: the splitting criterion and the leaf node prediction.

In a classification tree, the algorithm evaluates splits using Gini Impurity or Entropy, as we have just calculated. When a new, unseen data point drops down the tree and lands in a leaf node, the final prediction is the mode (the most frequent class) of the training samples that reside in that leaf.

In a regression tree, the target variable is continuous, so calculating probabilities and entropy is impossible. Instead, the algorithm evaluates splits by seeking to minimise the Mean Squared Error (MSE) or the Residual Sum of Squares (RSS) within the resulting child nodes. The algorithm looks for a split that groups data points with similar continuous values together. When an unseen data point lands in a leaf node, the final prediction is the mean average of the target values of the training samples in that leaf.

Explain how to control overfitting through pruning

If you allow a decision tree algorithm to run indefinitely, it will continue splitting nodes until every single leaf is pure. This results in an incredibly deep, complex tree that perfectly memorises the training data. This tree will have very low bias but extremely high variance, meaning it will perform terribly on new, unseen data. Examiners will ask you how to solve this problem. You must be prepared to explain pruning.

There are two primary approaches to pruning: pre-pruning and post-pruning.

Pre-pruning, also known as early stopping, involves halting the growth of the tree before it perfectly classifies the training set. You achieve this by setting specific hyperparameters before training begins. In your exam, name specific hyperparameters to demonstrate practical knowledge. Mention restricting the maximum depth of the tree (max_depth), setting a minimum number of samples required to split an internal node (min_samples_split), or demanding a minimum number of samples to form a valid leaf node (min_samples_leaf).

Post-pruning involves allowing the tree to grow to its maximum depth and then working backwards to collapse nodes that do not provide sufficient predictive value. The most common method you need to know is cost-complexity pruning. This technique introduces a penalty parameter, alpha. The algorithm attempts to minimise a function that adds the tree’s error rate to the number of terminal leaves multiplied by alpha. By increasing alpha, you heavily penalise trees with too many leaves, forcing the algorithm to collapse weaker branches. Explaining the function of the alpha parameter is an excellent way to elevate your answer from a basic pass to a top grade.

How to answer this in an exam

To maximise your grade, you need to understand exactly what the mark scheme rewards. When answering calculation questions, mark schemes allocate the majority of points to your method, not just the final number. Write out the raw formula first (for example, the Gini formula). Then, write out the formula substituted with the specific numbers from the question. Finally, state your answer. If you make a simple arithmetic error in the final step, you will still retain almost all the marks for demonstrating the correct logic.

For theoretical essay questions, mark schemes reward precise technical vocabulary. Do not write that a tree “makes a choice”. Write that the algorithm “evaluates features to maximise information gain”. Do not say a tree “memorises the data”. State that an unpruned tree “suffers from high variance and overfits the training distribution”.

Finally, always bring your answers back to the bias-variance tradeoff. If an exam asks you to evaluate the performance of a decision tree, explicitly state that single trees are highly sensitive to small variations in the training data. Acknowledging this instability proves you understand why practitioners rarely use single decision trees in production, setting you up perfectly if the subsequent question asks about random forests.

Frequently Asked Questions

Do I need to memorise the log values for Entropy calculations? Usually, no. Exam papers often provide a small reference table of log base 2 values or allow a non-programmable calculator. However, you should definitely know that log2(1) is 0 and log2(0.5) is -1. Knowing these simple identities will significantly speed up your mental maths for pure nodes or perfectly even splits.

Why do we prefer Gini over Entropy in practice? Gini impurity is computationally faster because it does not require calculating complex logarithmic functions. When building massive ensemble models, this speed difference becomes highly significant. In terms of the final tree structure, both metrics usually produce very similar splits and resulting models.

Can decision trees handle categorical variables natively? Yes, theoretically. Older algorithms like ID3 can split on multiple categories at once, creating multi-way branches. However, the standard CART algorithm implemented in modern libraries like Scikit-Learn strictly performs binary splits. Therefore, you generally have to convert categorical variables into binary features (using one-hot encoding) before training the model.

What is the main disadvantage of a single decision tree? Instability. A tiny change or a single outlier in the training data can alter a split near the root node, resulting in a completely different final tree structure. This high variance and lack of generalisation is exactly why we use ensemble methods to average out the predictions of many different, uncorrelated trees.

The Full Marks Press Machine Learning guide covers this topic in depth, providing complete step-by-step walkthroughs of past paper calculations and essay frameworks. You can download a free copy of the core revision chapters at fullmarkspress.com/free.