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.
How it works
- Try candidate feature thresholds at the current node.
- Choose the split with the greatest decrease in weighted child impurity or regression loss.
- Repeat within each child until a stopping rule is reached.
- Predict from leaf class frequencies or the mean target for squared-error regression.
- 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)
- Decision Tree for RegressionProMediumSolve
- CART Recursive Tree BuilderProMediumSolve
Build it step by step
- Random Forest from Scratch15 steps, your code runs in the browser