Decision Trees

Doctors, loan officers and mechanics often reason the same way: ask one question, then another depending on the answer, until the case is clear. Is the fever above 39 °C? If so, is there a rash? A decision tree learns such a sequence of questions from data. It is one of the few models whose entire logic can be printed on a page and read by a non-specialist, and it is the building block of the strongest classical methods, random forests and boosted trees.

What a tree is

A decision tree is a flowchart.

• Each internal node asks a question about a single feature, usually of the form is feature $j$ at most $\theta$?
• Each branch follows one answer.
• Each leaf gives a prediction: the majority label of the training points that end up there (or, for probabilities, their class proportions).

To classify a new point, start at the root and follow the answers to a leaf.

Geometrically, each question cuts the feature space with an axis-aligned line (a hyperplane perpendicular to one axis), and each leaf corresponds to a box. A tree of depth $D$ can produce up to $2^D$ boxes, which lets it approximate complicated boundaries with a staircase of rectangles.

Measuring how mixed a node is

A good question splits a mixed group of points into purer groups. To make "pure" precise, let $p$ be the fraction of class $+1$ among the points at a node.

The entropy of the node's labels is

It is 0 when the node is pure ($p = 0$ or $p = 1$) and largest, 1 bit, when the classes are evenly mixed ($p = 0.5$). It measures how uncertain we are about the label of a random point at the node.

A popular alternative is the Gini impurity, $G(p) = 2p(1 - p)$, with the same shape: 0 when pure, largest at $p = 0.5$. It is slightly cheaper to compute and usually picks very similar splits.

Choosing a question: information gain

Suppose a question splits a node's $n$ points into a left group of $n_L$ points and a right group of $n_R$. The information gain is the drop in impurity, weighting each child by its share of the points:

To pick the question at a node, try every feature and every useful threshold (the midpoints between consecutive sorted values of that feature), and choose the one with the largest gain.

A worked example

A node holds 10 points: 6 positive, 4 negative. Its entropy is $H(0.6) = -0.6\log_2 0.6 - 0.4\log_2 0.4 \approx 0.971$ bits. Two candidate questions:

• Question A sends 5 points left (5 positive, 0 negative) and 5 right (1 positive, 4 negative). Left entropy 0; right $H(0.2) \approx 0.722$. Weighted: $0.5 \times 0 + 0.5 \times 0.722 = 0.361$. Gain $= 0.971 - 0.361 = 0.610$.
• Question B sends 4 left (3 positive, 1 negative) and 6 right (3 positive, 3 negative). Entropies $H(0.75) \approx 0.811$ and $H(0.5) = 1$. Weighted: $0.4 \times 0.811 + 0.6 \times 1 = 0.924$. Gain $= 0.971 - 0.924 = 0.047$.

Question A is far better: it produces a perfectly pure child. The tree takes A and repeats the procedure inside each child.

Growing the tree

The standard algorithm is greedy and recursive.

1. At the root, choose the question with the highest gain.
2. Split the data accordingly and repeat in each child.
3. Stop at a node when it is pure, or a stopping rule fires: a maximum depth, a minimum number of points per leaf, or a minimum gain.

Greedy means each question is the best at that moment, not the best for the tree as a whole. Finding the globally optimal tree is NP-hard, and greedy growth works well in practice.

Overfitting and how to stop it

Let a tree grow until every leaf is pure and it will reach zero training error on almost any data set, by giving isolated noisy points their own tiny boxes. Such a tree has high variance: change a few training points and its structure changes completely. The remedies all limit complexity:

• Pre-pruning: cap the depth, require a minimum number of points per leaf, or require a minimum gain to split.
• Post-pruning: grow a large tree, then remove subtrees whose removal does not hurt (or barely hurts) validation error. Cost-complexity pruning does this with a penalty per leaf, chosen by cross-validation.
• Ensembles: average many trees, which is the subject of Module 11 and usually the most effective fix of all.

Strengths and weaknesses

Strengths: readable rules; no need to scale features (only their order matters); handles mixed numeric and categorical features; fast to predict; captures interactions between features naturally (a question on feature 2 asked only when feature 1 is large).

Weaknesses: axis-aligned staircases approximate diagonal boundaries poorly; a single tree is unstable; and greedy growth can miss splits that only pay off two levels down (the classic example is XOR, where no single first split has any gain).