Project 39: Decision Tree Classifier from Scratch

A self-contained deep-dive from the canonical Math from Foundations to Machine Learning curriculum.

  • Difficulty: Advanced
  • Time: 2-3 weeks
  • Language: Python with NumPy and Pandas
  • Prerequisites: Projects 2, 12, and 37
  • Source: ML-Found P16

What You Will Build

Build an interpretable classification tree using recursive binary partitioning. Implement class counts, Gini impurity and entropy, weighted impurity reduction/information gain, candidate thresholds, recursive node construction, prediction traversal, and probability estimates at leaves. Add stopping controls for depth, sample count, impurity, and minimum gain, plus either reduced-error or cost-complexity-style pruning. Print and visualize the tree, and return a decision path explaining every prediction. Evaluate on synthetic and real tabular data with train/validation/test separation. Compare unrestricted and constrained trees to reveal overfitting, and compute feature importance from accumulated impurity reduction while documenting its biases.

Real World Outcome

Training on a Titanic-style dataset prints the root split, node/leaf counts, depth, train/test metrics, and a readable tree. Querying one row returns its probability and path, such as sex <= ... -> age > ... -> leaf. Learning curves compare deep, shallow, and pruned versions.

Core Question

How can greedy local questions partition a feature space into useful prediction regions, and why does a perfectly pure training tree often generalize poorly?

Concepts You Must Understand First

  1. Entropy and Gini impurity: both quantify class mixture, with zero at a pure node. See Géron, Hands-On Machine Learning, ch. 6.
  2. Weighted information gain: a split is judged by child impurity weighted by child size.
  3. Recursive partitioning: each internal node owns a rule and child subproblems. See James et al., An Introduction to Statistical Learning, tree chapter.
  4. Stopping and pruning: limiting structure regularizes a high-variance learner.
  5. Evaluation and explanation: leaf frequencies estimate probabilities; a path provides a local reason, not a causal explanation.

Build Milestones

  1. Implement impurity/count helpers and verify them on pure, balanced, and skewed labels.
  2. Enumerate valid numeric thresholds and select the split with highest weighted gain.
  3. Recursively build nodes, leaves, prediction traversal, and probability output.
  4. Add depth/sample/gain constraints and validation-based pruning.
  5. Export text/diagram views, decision paths, feature importance, and held-out comparisons.

Hints in Layers

  1. Candidate thresholds can be midpoints between sorted distinct feature values where labels may change.
  2. Keep node data minimal: feature, threshold, children, counts, impurity, and sample count.
  3. Use a validation set for pruning decisions; the test set remains untouched until the tree is final.

Common Pitfalls and Debugging

  • Symptom: gain is negative or children look purer but score worse. Cause: child impurities were not weighted by size. Fix: test the formula on a hand split.
  • Symptom: recursion never terminates. Cause: a split sends all rows to one child. Fix: reject empty/no-progress splits and require positive gain.
  • Symptom: training accuracy is perfect, test accuracy poor. Cause: unrestricted depth. Fix: tune stopping/pruning on validation data.

Definition of Done

  • Gini, entropy, and weighted gain match hand calculations.
  • Every accepted split creates two nonempty smaller child problems.
  • Prediction probabilities and decision paths are reproducible.
  • Multiple pre-pruning controls and one post-pruning strategy work.
  • Held-out metrics compare unrestricted, constrained, and pruned trees.
  • Feature importance is reported with a warning about interpretation bias.

Previous: Project 38 · Complete learning path · Next: Project 40