Skip to the lesson
ML Explorer Reju Sam John

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.

About 10 minutes · No maths needed; the maths is there if you want it

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
  1. Twenty questions

    A tree labels a case the way you play Twenty Questions: one yes/no question at a time.

    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 ii has features xi=(xi1,xi2)\mathbf{x}_i = (x_{i1}, x_{i2}) and a label yi∈{0,1}y_i \in \{0, 1\}. A split on feature jj at threshold tt sends a case to the left if xij<tx_{ij} < t 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.

  2. 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.

    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 maths

    With pkp_k the share of class kk in a group of cases (here pp is a share of cases, not a predicted probability),

    G=1−∑kpk2G = 1 - \sum_k p_k^2

    With two classes, p1=pp_1 = p and p0=1−pp_0 = 1 - p, so G=1−(1−p)2−p2=2p(1−p)G = 1 - (1-p)^2 - p^2 = 2p(1-p).

    If a split sends nLn_L of the nn cases left and nRn_R right, its weighted Gini is

    Gsplit=nLn GL+nRn GRG_{\text{split}} = \frac{n_L}{n}\,G_L + \frac{n_R}{n}\,G_R

    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.

  3. The greedy choice

    The tree tries every threshold on every feature and keeps the split with the lowest weighted Gini.

    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 jj and midpoint tt with the lowest GsplitG_{\text{split}}. 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 (G=0G = 0), when no split lowers its impurity, or when it reaches the maximum depth.

  4. 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.

    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 dd has at most 2d2^d 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.

  5. Too deep

    Training accuracy climbs all the way to 100% as the tree deepens. Test accuracy does not follow.

    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.

  6. 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.

    The maths

    The total leaf impurity of a tree is ∑leavesnℓn Gℓ\sum_{\text{leaves}} \frac{n_\ell}{n}\,G_\ell, where leaf ℓ\ell holds nℓn_\ell of the nn 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

Why does a fully grown tree get 100% training accuracy?

No. The rule itself is wrong on the cases whose labels were flipped. The full tree gets those right too, which means it has learned the noise, and on the test cases it scores against the rule's .

Right. On this data the tree keeps splitting until every leaf is pure, so each training case is predicted correctly by construction. That says nothing about new cases.

The tree never sees the test cases while it grows. Its leaves are pure only for the training cases; on the test cases the full tree scores .

The data are noisy on purpose: of the training labels were flipped. The full tree still gets 100%, because it memorises those cases too.

At the root, which split does the tree choose?

That is the best split on x₁, but its weighted Gini is higher. The tree keeps the split with the lowest weighted Gini.

Right. Its weighted Gini, , is the lower of the two, so the tree asks about x₂ first.

Equal sizes are not the aim; pure sides are. The weighted Gini already takes each side's size into account, and the x₂ split scores lower.

The tree never looks at the test cases. It chooses splits by their weighted Gini on the training cases.

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.
Next lesson: Bagging and random forests →

Further reading

  1. 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.
  2. 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 .