ML Explorer · Level 3 · Classic ML
Decision trees
Label a case by asking it a few yes/no questions, each one chosen to sort the classes apart as well as it can.
Overview
Logistic regression and a linear support vector machine draw one straight boundary across the plot. A decision tree works differently. It asks a question about one feature, splits the cases into two groups, and then asks a new question inside each group.
We start with one question, measure how well it sorts the classes, let the tree choose its own questions, and then grow it too far on purpose.
The points are made up. See "About the data" at the end.
You'll learn
- how a tree labels a case, and how the Gini impurity scores a split
- why the tree chooses its questions one at a time, and what that costs
- why a very deep tree is perfect on the training data and worse on new cases
-
Twenty questions
A tree labels a case the way you play Twenty Questions: one yes/no question at a time.
Each point is one case with two features, x₁ across and x₂ up, both between 0 and 10. There are training cases: in class 0 (cyan circles) and in class 1 (violet triangles).
Ask one question: is x₁ less than 5? The answer cuts the plot in two along a straight line. The yes side holds circles and triangles; the no side holds circles and triangles.
Each side predicts its majority class: yes gives class 0, no gives class 1. The shading shows the prediction, and a line marks where it changes. This single question labels of the training cases correctly.
On the right is the same rule drawn as a tree. The question sits at the top, called the root. Yes goes left and no goes right. Each branch ends in a leaf, which shows the class it predicts and its counts, class 0 first.
The maths
Case has features and a label . A split on feature at threshold sends a case to the left if and to the right otherwise.
A leaf predicts the class that most of its training cases have. If a leaf holds equal numbers of both, this page predicts class 0. That tie rule is a choice; another program might pick differently.
-
How mixed is a side?
To compare questions, measure how mixed each side is. The Gini impurity is 0 for a side of one class and 0.5 for an even mix.
Write p for the share of triangles on one side. Its Gini impurity is G = 2p(1 − p). A side of all circles (p = 0) or all triangles (p = 1) has G = 0. A half-and-half side has G = 0.5, the most mixed two classes can be.
To score a whole split, average the two sides' G, weighting each side by its share of the cases. This is the weighted Gini. Lower is better.
For x₁ < 5 the yes side has G = and the no side G = , so the weighted Gini is . All cases together, before any split, have G = .
Slide the threshold. The chart shows the weighted Gini for every threshold on x₁. It moves in steps: it changes only when the line passes a point.
The lowest step runs from to , just above 5, with weighted Gini . Every threshold in it makes the same split. A tree uses the midpoint, . Our guess of 5 happened to land in it.
The maths
With the share of class in a group of cases (here is a share of cases, not a predicted probability),
With two classes, and , so .
If a split sends of the cases left and right, its weighted Gini is
The thresholds a tree tries are the midpoints between neighbouring values of the feature, once sorted. Any threshold between the same two values makes the same split, so nothing is missed.
Why not score a split by how many cases it gets right? A split can leave the majority unchanged on both sides, so the count of errors stays the same, yet make one side much purer. Gini notices that; a count of errors would not.
-
The greedy choice
The tree tries every threshold on every feature and keeps the split with the lowest weighted Gini.
The best split on x₁ is x₁ < , with weighted Gini : the solid curve on the chart, and the dashed line on the plot. The best on x₂ is x₂ < , with : the dashed curve, and the solid line.
So the x₂ split wins, and the tree's first question is "is x₂ less than ?".
This search is greedy: it takes the split that is best right now and never looks ahead to the questions that could follow.
Then the tree does the same inside each side: each one gets its own best question, and so on down. This is called recursive binary splitting.
The maths
At each node the tree picks the feature and midpoint with the lowest . On this page a tie goes to the lower feature number, then to the lower threshold.
A node becomes a leaf when it is pure (), when no split lowers its impurity, or when it reaches the maximum depth.
-
Growing the tree
Repeat the search inside every region and the tree grows. The maximum depth caps how many questions in a row a case can be asked.
Move the max depth slider from 1 to 8. Each new level can split every region again, so the regions get smaller.
Every region is a box with sides parallel to the axes. Each question looks at one feature only, so every cut runs straight across or straight up.
At max depth 2 one leaf holds 1 circle and 1 triangle. That is a tie, and the tie rule sends it to class 0.
From depth the tree stops growing: all leaves are pure, so there is nothing left to split.
The diagram draws three levels below the root. Deeper parts appear as dashed boxes with the number of splits hidden below them. The shading always shows the whole tree.
The maths
The depth of a leaf is the number of questions on the way to it. A tree of depth has at most leaves, and fewer when some branches stop early.
Max depth is one way to stop a tree. Others set a smallest leaf size, or grow a big tree and then cut back the branches that help least, which is called pruning.
-
Too deep
Training accuracy climbs all the way to 100% as the tree deepens. Test accuracy does not follow.
The chart shows training accuracy (solid line, dots) and test accuracy (dashed line, squares) for each max depth. The test cases come from the same source and were never used to grow the tree.
From depth , training accuracy is 100%. Every leaf is pure, so every training case lands in a leaf of its own class, including the whose labels were flipped at random. The tree has learned the noise.
Test accuracy peaks at depth , at , and falls to for the full tree.
For scale, the rule that made the data scores on the test cases, because of their labels were flipped too.
This is the overfitting lesson again, with depth in place of the curve's degree. In practice you choose the depth on a validation set, not on the test set.
The maths
Each label was flipped with probability 0.1, wherever the point lies. So even the rule that made the data is expected to be wrong on 10% of new cases, and no classifier can expect to do better than 90% on new cases here.
Here no two training cases share a value of x₁ or of x₂, so some split always lowers the impurity until every leaf is pure. Two cases with the same features and different labels could never be separated, and repeated values can stall a tree earlier. On this data, then, 100% training accuracy comes from how the tree grows, not from anything it has learned about new cases.
-
Reading a tree
To label a case, start at the root and answer each question until you reach a leaf.
This is the depth-2 tree, the one that did best on the test cases. The hollow diamond is a new case. Drag it, or tab to it and use the arrow keys.
At (2, 8): is x₂ less than ? No, so go right. Is x₁ less than ? Yes, so go left. That leaf holds circles and triangles, so the tree predicts class . The dashed box on the plot is that leaf's region.
The rule that made the data says class 1 at (2, 8): it sits in the small corner where x₁ < 3 and x₂ > 7. The depth-2 tree is too shallow to carve that corner out. The depth-3 tree does, yet scores lower on the test cases overall ( against ).
Greedy choices are not always the best overall. Here, by the tree's own measure (total leaf impurity), the greedy tree can be beaten. In step 3 the tree turned down x₁ < as its first question. Yet a depth-2 tree that starts with it, then splits each side as well as it can, ends with a total leaf impurity of , below the greedy tree's . The greedy search never finds it, because it never looks two questions ahead.
The maths
The total leaf impurity of a tree is , where leaf holds of the training cases. The comparison above tried every first question on this data, each followed by the best split on each side.
Searching every possible tree is hopeless beyond tiny examples: the number of trees grows far too fast. So trees are grown greedily, and the result is a good tree rather than the best possible one.
Lower impurity on the training cases is not the same as higher accuracy on new ones. The point here is only that the greedy tree is not the best tree by its own measure.
Quick check
Lesson complete
- A decision tree labels a case by a chain of yes/no questions, each about one feature. Its regions are boxes with sides parallel to the axes.
- Each split is chosen to give the lowest weighted Gini impurity, G = 1 − Σ pₖ², which is 2p(1 − p) with two classes.
- The search is greedy: the best split now, with no looking ahead. That keeps it fast, but the tree it finds is not always the best one.
- Depth is the overfitting knob. A full tree is perfect on the training data and learns its noise; choose the depth on a validation set.
Common misconceptions
- "The tree finds the best possible set of questions." It finds a good set, one question at a time. A different first question can lead to a better tree.
- "A deeper tree is a better tree." Past a point it fits the noise in the training data, and new cases suffer.
- "Trees need their features standardised, like k-NN." Multiplying a feature by a positive number moves its thresholds with it, and every split separates the same cases.
Further reading
- James, Witten, Hastie & Tibshirani, An Introduction to Statistical Learning (2nd ed.), Section 8.1, "The Basics of Decision Trees", which grows trees by recursive binary splitting, described there as top-down and greedy.
- The same book, Section 8.1.2, "Classification Trees", which defines the Gini index. It writes it as a sum of p(1 − p) over the classes, which equals 1 − Σ pₖ².
About the data. The cases are made up. Each point has x₁ = 10u₁ and x₂ = 10u₂, where u₁ and u₂ are uniform draws between 0 and 1 from mulberry32. Its class is 1 if (x₁ > 5 and x₂ > 3) or (x₁ < 3 and x₂ > 7), and 0 otherwise. Then a third draw u₃ flips the label if u₃ < 0.1. The draws come in the order u₁, u₂, u₃ for one point, then the next. The 80 training cases use seed 99 and the 400 test cases seed 100; 8 training labels and 40 test labels were flipped. The new case starts at (2, 8), chosen inside the small corner of the rule. Thresholds sit midway between neighbouring values; ties between splits go to the lower feature, then the lower threshold; a leaf tie goes to class 0. Displayed values are rounded; the calculations are not.
If this helped, you can .