Learning by Asking Questions
Imagine you are trying to decide whether to play tennis on a given day. You might ask: Is it sunny? If so, is the humidity high? If not, is it windy? A chain of yes/no questions eventually leads you to a decision. This is exactly how a decision tree works — it is a model that makes predictions by repeatedly splitting data based on feature values, following a branching path from root to leaf.
Decision trees are among the most interpretable machine learning models. Unlike neural networks or support vector machines, you can read a decision tree like a flowchart and understand exactly why a prediction was made. This transparency makes them invaluable in medicine, finance, and any domain where explanations matter as much as accuracy.
Anatomy of a Decision Tree
A decision tree has three types of nodes. The root node is the top of the tree — it contains all training samples and applies the first split. Internal nodes (also called decision nodes) represent feature tests: "Is temperature > 75°F?" Each internal node splits the data into two or more branches. Leaf nodes (terminal nodes) are the endpoints — they contain no more splits and hold the final prediction, either a class label (for classification) or a numeric value (for regression).
The depth of a tree is the number of edges from root to the deepest leaf. A stump (depth = 1) makes a single split. Deep trees can capture complex patterns but risk overfitting. The path from root to a leaf defines the rule used for any prediction — this is the interpretability advantage.
Decision trees can handle both tasks. Classification trees predict a discrete class label — the leaf returns the majority class of its training samples. Regression trees predict a continuous value — the leaf returns the mean of its training samples. The splitting criteria differ (Gini / entropy for classification; variance for regression), but the algorithm structure is identical.
How to Split: Impurity Measures
The core question in building a tree is: which feature and threshold should we split on? The goal is to find splits that create the purest possible child nodes — ideally, each child contains samples from only one class. Two impurity measures are widely used.
Gini impurity measures the probability that a randomly chosen sample would be misclassified if labeled according to the class distribution in the node. A pure node (all samples the same class) has Gini = 0. A maximally impure node (50/50 split of two classes) has Gini = 0.5.
Entropy (from information theory) measures the average information content of class labels in a node. Like Gini, entropy is 0 for a pure node. It is slightly more expensive to compute (involves logarithms) but theoretically grounded in information theory.
To choose a split, the algorithm computes Information Gain: the reduction in entropy (or Gini) from parent to children, weighted by the fraction of samples in each child. The split with the highest Information Gain is chosen.
Growing the Tree: The CART Algorithm
The most common algorithm for building decision trees is CART (Classification and Regression Trees). It is a greedy algorithm: at each node, it exhaustively searches all features and all possible thresholds to find the split that minimizes impurity. It does not look ahead — the locally best split is chosen at every step.
The procedure is recursive: after each split, the same algorithm is applied to each child node independently, until a stopping criterion is met. Common stopping criteria include: maximum tree depth reached, minimum number of samples required to split a node, minimum impurity decrease required for a split, or minimum number of samples required in a leaf.
Finding the globally optimal tree is computationally intractable (NP-hard). The greedy approach makes locally optimal choices at each node and produces reasonable results in polynomial time. This is why decision trees built with CART are not globally optimal — but in practice they work well, especially when used as base learners in ensemble methods.
The Overfitting Problem
If allowed to grow without constraint, a decision tree will eventually perfectly memorize the training data — it creates one leaf per training sample, achieving 100% training accuracy. But this deep, complex tree will generalize poorly to new data: it has learned the noise in the training set, not the underlying pattern.
This is the classic overfitting problem. A single decision tree is particularly prone to overfitting because of its high variance: small changes in the training data can produce dramatically different trees. This sensitivity is both a weakness and, paradoxically, the reason decision trees are powerful as base learners in ensemble methods like random forests.
Pruning: Controlling Complexity
The primary tool for fighting overfitting in decision trees is pruning — removing parts of the tree that do not improve generalization. There are two main approaches.
Pre-pruning (early stopping) halts tree growth before it fully memorizes the training data. Hyperparameters like max_depth, min_samples_split, and min_impurity_decrease impose hard limits during construction. Pre-pruning is fast but requires tuning.
Post-pruning grows the full tree first, then removes subtrees that do not improve performance on a validation set. Cost-complexity pruning (also called weakest-link pruning) is a principled post-pruning method: it adds a penalty term α for each leaf, and sweeps over values of α to find the optimal tree size. This is implemented in scikit-learn as ccp_alpha.
Feature Importance
A useful by-product of training a decision tree is feature importance. For each feature, we sum the total impurity reduction it caused across all nodes where it was used as a split, weighted by the number of samples passing through those nodes. Features that appear near the root and reduce impurity greatly are considered more important.
This gives an intuitive, model-derived ranking of features. However, decision tree feature importances can be biased toward high-cardinality features (features with many unique values), because they offer more possible split points. Methods like permutation importance or SHAP values provide more reliable estimates.
Key Hyperparameters
max_depth: Maximum depth of the tree. The most important regularization parameter. Start with 3–5 and tune upward.
min_samples_split: Minimum number of samples required to split an internal node. Higher values prevent the tree from making splits on very small groups, reducing variance.
min_samples_leaf: Minimum number of samples required to be at a leaf node. Ensures that every prediction is backed by at least this many training examples, smoothing predictions.
max_features: Number of features to consider when looking for the best split. Relevant when used in ensemble methods — using a random subset introduces diversity between trees.
criterion: The impurity measure used ("gini" or "entropy" for classification; "squared_error" for regression). In practice, Gini and entropy produce very similar trees.
Advantages and Limitations
Decision trees excel in several scenarios. They are interpretable — you can visualize and explain every prediction. They handle mixed data types (categorical and numerical features) without preprocessing. They are non-parametric and make no assumptions about the distribution of data. They also perform implicit feature selection — irrelevant features simply do not get used in splits.
However, decision trees have significant weaknesses. They have high variance and are sensitive to small changes in the data. They can create biased splits with imbalanced datasets. Axis-aligned splits mean they struggle with diagonal decision boundaries (e.g., classifying x + y > 0 requires a staircase of splits). And their expressivity is limited compared to ensemble methods.
In practice, a standalone decision tree is rarely the best model for tabular data. Its real importance is as the building block for ensembles: random forests average many decorrelated trees to reduce variance, while gradient boosting sequentially fits trees to residuals for high accuracy. Understanding decision trees deeply is the foundation for understanding both.
- Decision trees predict by recursively splitting data with yes/no feature tests, following a path from root to leaf.
- Gini impurity and entropy both measure node purity; the split with the highest Information Gain is chosen at each step.
- CART is a greedy algorithm — it finds the locally optimal split at each node but is not globally optimal.
- Unconstrained trees overfit. Pre-pruning (max_depth, min_samples) and post-pruning (ccp_alpha) control complexity.
- Feature importance is a useful by-product but can be biased toward high-cardinality features.
- Decision trees are interpretable, handle mixed data, and require no feature scaling — but have high variance.
- The true value of decision trees is as building blocks for ensemble methods: random forests and gradient boosting.