Decision Trees

A decision tree is a flowchart that makes a prediction. You start at the top and answer a question about the data; the answer sends you down a branch to another question, and so on, until you reach a leaf that gives the final answer, the predicted class.

• Each internal node asks a question about one feature, for example "is the outlook sunny?"
• Each branch is a possible answer.
• Each leaf is a decision, the class the tree predicts for anything that reaches it.

The great appeal is transparency. Many machine learning models are black boxes, but you can print a decision tree and follow exactly why it made any prediction. That readability makes trees popular wherever a decision has to be explained, like credit approvals or medical triage.

To choose a good question, we need to measure how mixed up a set of examples is. If a group is all one class, it is pure and certain. If it is a fifty-fifty mix, it is as uncertain as possible. Entropy is the number that captures this, from 0 (perfectly pure) to 1 (maximally mixed, for two classes).

• All examples the same class: entropy 0, no uncertainty.
• Half and half (two classes): entropy 1, maximum uncertainty.
• Anything in between: entropy somewhere between 0 and 1.

Now the key idea. When we split a group of examples using some question, we create smaller subgroups. Information gain measures how much the split reduced entropy: the uncertainty before, minus the (weighted) uncertainty after.

The subgroups are weighted by their size, so a split that produces one big pure group and one small messy one still scores well. To build the tree, the algorithm simply tries every possible question and picks the one with the highest information gain. That question becomes the node, and the process repeats on each subgroup.

The classic algorithm that does this is ID3. It is refreshingly simple: at each node, choose the feature with the highest information gain, split on it, and recurse on each branch until the groups are pure or you run out of features.

Numbers on a page are abstract, so try it directly. Below are points of two classes, red and blue. Choose which feature to split on (the horizontal or vertical axis), then drag the split line. The panel shows the entropy before, the weighted entropy after, and the information gain. Hunt for the split with the highest gain, then notice which axis can even produce a good one.

Left unchecked, a decision tree will keep splitting until every leaf is perfectly pure, memorising the training data down to its noise. This is overfitting: the tree scores perfectly on data it has seen and poorly on anything new, because it learned the quirks of the sample rather than the real pattern.

Two cures:

• Pruning: cut the tree back, removing branches that add little real value, so it stays simpler and generalises better. You can stop growing early or trim after the fact.
• Random forests: instead of one tree, train many trees on random slices of the data and features, and let them vote. No single tree overfits the same way, so the crowd is far more robust than any individual. This is one of the most reliable machine learning methods there is.

• A decision tree classifies by asking a chain of questions ending at a leaf; it is readable.
• Entropy measures how mixed a group is, from 0 (pure) to 1 (evenly split).
• Information gain is the drop in entropy from a split; the tree picks the split with the most gain.
• ID3 builds the tree by choosing the highest-gain feature at each node and recursing.
• The Gini index is a common alternative impurity measure to entropy.
• Trees overfit if grown fully; pruning and random forests fix this.