Decision Tree

1. Purpose & Motivation

1.1 Why decision trees exist

  • Many decisions are naturally hierarchical: a sequence of yes/no questions
  • Stakeholders need models they can visually inspect and understand
  • Handling both numerical and categorical features without preprocessing is valuable

1.2 The core problem it solves

Recursively partition the feature space using if-then rules to make predictions, producing a tree structure that is inherently interpretable.

2. Definition & Core Idea

2.1 Formal definition

A decision tree is a hierarchical model that splits data at each internal node based on a feature threshold, routes examples down branches, and assigns predictions at leaf nodes. It learns by greedily selecting splits that maximize information gain or minimize impurity.

2.2 Intuitive mental model

"Play 20 questions with the data: at each step, ask the single question that best separates the remaining examples."

3. How It Works

3.1 Tree construction (greedy top-down)

  1. Evaluate all possible feature splits
  2. Choose the split that best separates classes (or reduces variance)
  3. Create two child nodes
  4. Recurse on each child until a stopping criterion is met

3.2 Splitting criteria

Criterion Used for Measures
Gini Impurity Classification Probability of misclassification
Entropy / Info Gain Classification Reduction in uncertainty
MSE Reduction Regression Reduction in variance of target

3.3 Stopping criteria

  • Maximum tree depth reached
  • Minimum samples per leaf
  • Minimum impurity decrease threshold
  • All samples in a node belong to one class

4. Prediction

4.1 Classification trees

  • Each leaf stores a class label (majority vote of training samples in that leaf)
  • Can also output class probabilities (proportion of each class in the leaf)

4.2 Regression trees

  • Each leaf stores a continuous value (mean of training targets in that leaf)

5. Pruning

5.1 Why pruning matters

  • Unpruned trees tend to overfit by memorizing training data
  • Pruning removes branches that do not improve generalization

5.2 Pruning strategies

  • Pre-pruning: Stop growing early (max depth, min samples)
  • Post-pruning (Cost Complexity): Grow full tree, then remove branches that increase cross-validated error

6. Strengths & Limitations

6.1 Strengths

  • Highly interpretable and visualizable
  • Handles mixed feature types without preprocessing
  • Captures non-linear relationships and feature interactions
  • No feature scaling required

6.2 Limitations

  • High variance: small data changes can produce very different trees
  • Prone to overfitting without pruning
  • Greedy splitting may miss globally optimal structure
  • Axis-aligned splits create step-like decision boundaries

7. One-Sentence Summary

A decision tree recursively splits data using feature thresholds to form an interpretable, hierarchical set of if-then rules for classification or regression.

8. Related Knowledge Pages