Decision tree

Prerequisites

• Logarithms in base 2.
• Proportions within a group.
• The tennis dataset (same numbers).

The analogy

How it works

Data: play days (5): sunny 2, rainy 3; weak wind 4, strong 1. No-play days (5): sunny 3, rainy 2; weak 2, strong 3. Entropy of a group with proportions $p$ and $1 - p$: $H = -p\log_2 p - (1-p)\log_2(1-p)$.

Start with choosing the first split

Root: 5 play, 5 no, so $H = 1$ bit. Information gain = $H(\text{parent})$ − weighted average $H(\text{children})$. Predict, then open "Check".

Finish the picture: growing and stopping

After the wind split, each child is split again in the same way, until a stopping rule applies.

• Weak-wind child (4 play, 2 no). Predict the leaf label if we stop here.
  Check

  "Play", the majority. The tree would be right 4 times out of 6 in that branch.

• No stopping rule at all. Predict the training accuracy and the risk.
  Check

  The tree grows until every leaf is pure: 100% training accuracy, but it overfits. Limit the depth, require a minimum number of samples per leaf, or prune.

Full worked calculation

Every logarithm and every weighted average behind the root split, then the same decision made with Gini impurity. Data: 10 days, 5 play / 5 no.

1. 1Entropy of the root

   $$H = -0.5\log_2 0.5 - 0.5\log_2 0.5 = 0.5 + 0.5 = 1 \text{ bit}$$

   A 50/50 group is as uncertain as possible: you need one full yes/no question (1 bit) to know the answer. Every split will be judged by how much of this bit it removes.

2. 2Entropy of a 2/3 child (sunny)

   $$H = -0.4\log_2 0.4 - 0.6\log_2 0.6 = 0.4 \cdot 1.322 + 0.6 \cdot 0.737 = 0.529 + 0.442 = 0.971$$

   $\log_2 0.4 \approx -1.322$ and $\log_2 0.6 \approx -0.737$. The child is still very mixed, so its entropy is close to 1. Rainy (3/2) is the mirror image, also 0.971.

3. 3Gain of the outlook split

   $$\text{Gain} = 1 - \left(\tfrac{5}{10} \cdot 0.971 + \tfrac{5}{10} \cdot 0.971\right) = 1 - 0.971 = 0.029$$

   Each child's entropy is weighted by its share of the days. Asking about the outlook leaves us almost as uncertain as before: only 0.029 bits gained.

4. 4Entropies of the wind children

   $$H(\tfrac{4}{6}) = \tfrac{2}{3} \cdot 0.585 + \tfrac{1}{3} \cdot 1.585 = 0.918, \qquad H(\tfrac{1}{4}) = 0.25 \cdot 2 + 0.75 \cdot 0.415 = 0.811$$

   Weak wind (4 play, 2 no) and strong wind (1 play, 3 no) are both more lopsided than 50/50, so both have lower entropy than the root.

5. 5Gain of the wind split

   $$\text{Gain} = 1 - \left(0.6 \cdot 0.918 + 0.4 \cdot 0.811\right) = 1 - (0.551 + 0.325) = 0.125$$

   The weights are 6/10 and 4/10 because the children have different sizes. Wind removes 0.125 bits of uncertainty, four times more than outlook, so it becomes the root question.

6. 6Same decision with Gini impurity

   $$\text{Gini} = 1 - p^2 - (1 - p)^2: \quad \text{wind } 0.6 \cdot 0.444 + 0.4 \cdot 0.375 = 0.417 \;\;\text{vs}\;\; \text{outlook } 0.480$$

   Gini measures the chance of mislabelling a random item if you label randomly by the group's proportions. The root has 0.5; wind lowers it to 0.417, outlook only to 0.480. Gini and entropy agree, as they usually do.

The rule in plain words

At each node, try every feature (and threshold); pick the split with the largest information gain (or largest Gini decrease). Recurse on each child.

Stop when a node is pure, too small or too deep; label each leaf with its majority class (or mean value, for regression).

The code

Read this code after you have computed the two gains by hand. It will make more sense.

double entropy(int pos, int neg) {                       /* in bits */
    double n = pos + neg, h = 0;
    if (pos) h -= pos / n * log2(pos / n);
    if (neg) h -= neg / n * log2(neg / n);
    return h;
}

double info_gain(int lp, int ln, int rp, int rn) {         /* left and right child counts */
    double nl = lp + ln, nr = rp + rn, n = nl + nr;
    return entropy(lp + rp, ln + rn) - nl / n * entropy(lp, ln) - nr / n * entropy(rp, rn);
}

flowchart TD
  A["node with its examples"] --> B{"pure, too small or too deep?"}
  B -->|yes| L["leaf: predict the majority class"]
  B -->|no| C["try every feature and threshold"]
  C --> D["keep the split with the largest information gain"]
  D --> E["recurse on each child"]
          

How costly is it?

Entropy and information gain for a split into children $S_1, \dots, S_k$:

Gini impurity, $1 - \sum_c p_c^2$, is a cheaper alternative and usually picks the same splits.

Best for: tabular data with mixed numeric and categorical features, when you need a model people can read.

• Pro: Interpretable: the rules can be read and explained.
• Pro: No scaling needed; handles interactions and non-linear boundaries.
• Con: Overfits easily if not limited or pruned.
• Con: Unstable: a small change in the data can change the whole tree.

Common mistakes

• Forgetting to weight each child's entropy by its size.
• Using $\log$ in base $e$ while claiming the answer is in bits.
• Letting the tree grow without limits and trusting its 100% training accuracy.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• Splits are chosen by information gain because the best question is the one that makes the groups purest.
• Entropy is 1 for a 50/50 group because that is maximum uncertainty for two classes.
• Trees need no scaling because each split compares one feature with a threshold.
• Unlimited trees overfit because they can split until every training example has its own leaf.
• Prediction is fast because it follows one root-to-leaf path.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is a decision tree like the game "20 questions"?
   Sample answer

   Each question is chosen to narrow down the possibilities as much as possible, and you follow the answers down to a conclusion.

2. Compare the outlook and wind splits on the tennis data.
   Sample answer

   Outlook gives children with entropy 0.971 each, gain 0.029. Wind gives 0.918 and 0.811, weighted 0.875, gain 0.125. Wind is chosen.

3. Why does entropy skip the term when a count is 0?

   A good answer mentions $\log 0$.

   Sample answer

   $\log_2 0$ is undefined (minus infinity), but $p \log p \to 0$ as $p \to 0$, so the term is simply left out.

4. So what is a decision tree, in one sentence?
   Sample answer

   A model that predicts by following feature tests from the root to a leaf, with each test chosen to maximise information gain.

5. Why did wind give more information than outlook?

   A good answer compares how mixed the children are.

   Sample answer

   Outlook's children stay close to 50/50 (2/3 and 3/2), while wind's are more lopsided (4/2 and 1/3), so they are purer and their entropy is lower.

6. What do training and prediction cost?
   Sample answer

   Training is roughly $O(m\,n \log n)$; prediction is $O(\text{depth})$.

7. Give two pros and two cons of decision trees.
   Sample answer

   Pros: interpretable, and no scaling needed. Cons: overfit easily, and unstable to small data changes.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out Gini and gain ratio. I'd keep the 20-questions analogy, the wind-versus-outlook gain calculation, and "pick the purest split, stop before it memorises".

External resources

• scikit-learn: Decision trees: algorithms, parameters and visualisation.
• Wikipedia: Decision tree learning: ID3, C4.5, CART and split criteria.
• Google: Decision forests course: trees and forests, step by step.

Videos

• YouTube search: StatQuest decision trees: StatQuest builds a tree by hand.