Decision trees
Logistic regression answered "will they win?" with a formula and a probability. A decision tree answers the same question in a completely different, very human way: it asks a series of yes/no questions and follows the answers, like a scout with a checklist. In this lesson you will walk a tree yourself, then learn the surprisingly simple rule a tree uses to choose its questions.
The core idea: ask questions in a smart order
You already reason this way. To guess if a team will win, you might ask: "Are they much stronger? Are they at home? Have they been in good form?" A decision tree does exactly that, but it learned which questions to ask, and in which order, from thousands of past matches.
Three quick words for the parts of a tree:
- The root is the first question at the top.
- A branch is the path you take based on a yes or no answer.
- A leaf is where you stop: the final prediction (Win, Draw, or Loss).
Walk a tree yourself
Below is a small trained tree. Pick any matchup in your head, then answer its questions. The glowing gold path shows the route your answers take, all the way down to a prediction.
How to use this lab
- Read the highlighted question at the top.
- Press Yes or No for the matchup you are imagining.
- Follow the gold path to the next question, and keep going until you reach a prediction box.
- Press Start over and try a very different matchup. Notice a single changed answer can send you to a completely different prediction.
But how did the tree choose those questions?
The way it picks those questions is simpler than you would expect. While the tree is being built, at every step it tries every possible question and keeps the one that splits the matches into the cleanest groups. "Clean" means each group is as one-sided as possible after the split, mostly wins on one side, mostly losses on the other.
So we need a way to measure how "mixed up" a group of matches is. That measure is called Gini impurity.
Gini impurity: a mixed-up meter
Imagine a bag of matches, each labelled Win or Loss. Gini impurity is a number that answers: "If I reach in and grab one, how likely am I to be surprised?"
- A bag that is all wins is not mixed up at all. Gini = 0 (pure).
- A bag that is a 50/50 split is as mixed up as possible. Gini = 0.5.
Lower Gini means a cleaner, more one-sided group, exactly what a good question produces. The formula for it:
That big Σ just means "add up." pi is the fraction of the group that is outcome i. So for wins and losses: take the fraction that are wins, square it; take the fraction that are losses, square it; add those, and subtract from 1.
All wins: fraction of wins = 1, losses = 0. Gini = 1 − (1² + 0²) = 1 − 1 = 0. Perfectly pure. A 50/50 bag: Gini = 1 − (0.5² + 0.5²) = 1 − 0.5 = 0.5. Maximum mix. Every real group sits between those two.
Worked example: is "playing at home" a good question?
Start with 10 past matches: 6 wins, 4 losses. How mixed up is that?
$$Gini_{\text{start}} = 1 - \left(\tfrac{6}{10}\right)^2 - \left(\tfrac{4}{10}\right)^2 = 1 - 0.36 - 0.16 = 0.48$$
Now split those same 10 by "played at home?". Say 6 were home matches (5 wins, 1 loss) and 4 were away (1 win, 3 losses).
$$Gini_{\text{home}} = 1 - \left(\tfrac{5}{6}\right)^2 - \left(\tfrac{1}{6}\right)^2 \approx 0.278$$
$$Gini_{\text{away}} = 1 - \left(\tfrac{1}{4}\right)^2 - \left(\tfrac{3}{4}\right)^2 = 0.375$$
The two groups are cleaner than the mixed start. Combine them, weighted by how many matches are in each:
$$Gini_{\text{after}} = \tfrac{6}{10}(0.278) + \tfrac{4}{10}(0.375) \approx 0.317$$
The mix dropped from 0.48 to 0.317. That drop is the payoff for asking "playing at home?".
Information gain: how much a question helped
That drop has a name: information gain. It is just how much the impurity fell after a split.
The tree computes this gain for every question it could ask, on every feature, and picks the question with the biggest gain. Then it does the same thing again inside each new group, and again, growing the tree one clean split at a time. That is the entire training algorithm.
Find the best split yourself
Now make it concrete. Below are 24 past matches spread out by ranking gap: teal dots are wins, coral are losses. Drag the gold line to split them into a left group and a right group, and watch the Gini numbers update live. Then let the computer reveal the split with the lowest weighted Gini, the one a real tree would pick here.
How to use this lab
- Teal dots = the higher-ranked team won. Coral dots = they did not.
- Drag the gold circle left or right. Everything left of the line is the left group, everything right is the right group.
- Watch the three Gini numbers change. Lower is cleaner. Try to make the weighted Gini as small as you can.
- Press Show the best split to see the exact threshold a real tree would choose, and how close you got.
One danger: growing too greedy
A tree can keep asking questions until every leaf holds a single match. That sounds perfect, but it is a trap. Such a tree has basically memorised the past instead of learning a general pattern, so it does badly on new matches it has never seen. This is called overfitting.
Think of a student who memorises the exact answers to last year's exam paper. They ace that paper, then fail the real exam because the questions changed. An overfit tree does the same thing: perfect on the matches it trained on, poor on tomorrow's game. The fix is to cap how deep the tree can grow, so it has to find real patterns instead of memorising.
Two models, side by side
You have now met both models in this course. They answer the same question in very different styles.
Gives a smooth probability (73%). One formula, every feature adds in. Great when factors add up cleanly.
Gives a category by asking questions in order. Easy to read as a flowchart. Great when factors only matter in combination.
Neither is "better." Real prediction systems often run both and combine them. The point of learning both is that you can now pick the right tool for the question in front of you.
- A tree predicts by asking yes/no questions: root to branches to a leaf.
- Gini impurity $= 1 - \sum p_i^2$ measures how mixed a group is (0 = pure, 0.5 = fully mixed).
- Information gain is how much impurity drops after a split.
- The tree keeps the split with the biggest gain, then repeats inside each group.
- Letting a tree grow too deep causes overfitting: it memorises instead of learning.
You understand the models. Time to see them as real code.