Classic machine learning

Decision tree

Like a game of twenty questions, a decision tree narrows down an answer through simple tests. Each split sends an example down one branch. A leaf returns a class distribution or a numeric prediction.

YesNoHours < 2?3 fail, 3 passPredict fail3 fail, 0 passPredict pass0 fail, 3 pass
One test separates six students into two pure leaves, reducing weighted Gini impurity from 0.5 to 0.

How it works

  1. Try candidate feature thresholds at the current node.
  2. Choose the split with the greatest decrease in weighted child impurity or regression loss.
  3. Repeat within each child until a stopping rule is reached.
  4. Predict from leaf class frequencies or the mean target for squared-error regression.
  5. Use validation to choose tree size or pruning strength.

$$\Delta I=I(\mathrm{parent})-\frac{n_L}{n}I(L)-\frac{n_R}{n}I(R)$$

The knobs that matter

max_depth
Limits the number of successive splits.
min_samples_leaf
Larger leaves smooth predictions and discourage tiny groups.
Pruning strength
A larger complexity penalty removes more branches.

What interviewers ask

  • How do you choose the root split?
  • How do Gini impurity and entropy differ?
  • Why does an unrestricted tree overfit, and how would you prune it?
  • How does a regression tree choose splits and leaf predictions?

Common mistakes

  • Averaging child impurities without weighting by sample counts.
  • Assuming greedy splits produce the globally best tree.

When to use it

Use a small tree when simple rules and feature interactions matter. A single deep tree can change sharply with small changes in training data.

Implement it (6 problems)

Build it step by step

Learn it

Interview questions about decision tree