Decision Trees
Introduction
A decision tree makes predictions by asking a sequence of simple yes/no questions about the input features. Each question compares one feature to a threshold — for example, "is x₁ ≤ 4.5?" — and the answer routes the example down to a child node. After a few such questions you reach a leaf, which holds the final prediction. Because every question looks at a single feature, a decision tree carves the feature space into axis-aligned rectangular regions, each assigned one class.
Trees are popular because they are interpretable (you can read the rules straight off the tree), need almost no data preprocessing (no feature scaling, and they handle non-linear boundaries naturally), and form the building block of powerful ensembles like random forests and gradient-boosted trees. The catch is that a single unconstrained tree will happily memorize the training data, so controlling its complexity is essential.
Core intuition: recursively split the data into purer and purer groups. Keep cutting the feature space with horizontal and vertical lines until each region is (mostly) a single class, then predict that class for anything that lands there.
How a tree decides where to split
Growing a tree is a recursive, greedy procedure. At each node we look at the data that reached it and ask: of all the candidate splits — every feature paired with every sensible threshold — which one separates the classes best? "Best" is measured by how much a split reduces impurity.
Measuring impurity
A node is pure if all its samples belong to one class, and impure if the classes are mixed. Let pₖ be the fraction of samples in the node that belong to class k. Two standard measures:
Gini impurity
G = 1 − Σₖ pₖ²
The probability that two samples drawn at random from the node have different labels. Ranges from 0 (pure) to 1 − 1/C for C balanced classes (0.5 for 2 classes, ≈0.667 for 3). Used by CART; cheap because it needs no logarithms.
Entropy
H = −Σₖ pₖ log₂ pₖ
The average number of bits needed to encode the class of a sample. Ranges from 0 (pure) to log₂C for C balanced classes (1 bit for 2 classes, ≈1.585 for 3). Used by ID3 and C4.5.
Both are 0 only when the node is pure and peak when the classes are evenly mixed. In practice Gini and entropy almost always pick the same splits; Gini is slightly faster, which is why it is CART's default. Try toggling between them in the demo below — the tree rarely changes.
Information gain
A candidate split sends some samples left and some right. We score it by how much it lowers impurity, weighting each child by its share of the samples:
where n is the number of samples at the parent and n_left, n_right the counts in each child. When impurity is entropy this quantity is literally the information gain; with Gini it is sometimes called the Gini decrease. A larger gain means a cleaner separation. The tree is greedy: at each node it scans all candidate splits and keeps the single one with the highest gain — it never backtracks to reconsider an earlier choice, so the result is a good tree, not a provably optimal one (finding the globally optimal tree is NP-hard).
Worked example. A node has 8 samples: 4 of class A, 4 of class B, so Gini = 1 − (0.5² + 0.5²) = 0.5. A split sends {4 A, 0 B} left and {0 A, 4 B} right. Both children are pure, so each has Gini 0 and the weighted child impurity is 0. The gain is 0.5 − 0 = 0.5 — a perfect split.
Candidate thresholds
For a numeric feature, the splits worth trying are the midpoints between consecutive sorted values of that feature. Any threshold between two adjacent values produces the same partition, so the midpoints are the only candidates we need to test. This is exactly what the demo does for both features at every node.
Reaching a leaf and predicting
Recursion stops when a node is pure, when it hits a depth or minimum-samples limit, or when no split improves impurity. The node then becomes a leaf. For classification a leaf predicts the majority class of its training samples (and can report class proportions as probabilities); for regression a leaf predicts the mean of its samples' targets, and impurity is replaced by variance / mean squared error.
Interactive: grow a decision tree
This demo grows a real greedy CART-style tree in your browser. At every node it searches all axis-aligned thresholds on both features, picks the split with the maximum information gain, and recurses until it reaches the depth limit, hits the min-samples limit, or makes a node pure. The colored rectangles behind the points are the actual decision regions; the diagram on the right is the resulting tree. Raise max depth and watch the boundary grow more intricate — and the training accuracy climb toward 100% as the tree starts to overfit the noise.
Colored regions are the tree's decisions. Click on the plot to add a point of the selected class and watch the tree re-grow.
Increase past ~4 and watch the boundary fragment to fit individual points (overfitting).
A node with fewer samples becomes a leaf — a simple pre-pruning regularizer.
Boxes are internal nodes (chosen feature/threshold); circles are leaves (predicted class). Each node shows its impurity and sample count.
Things to try: (1) Set max depth to 1 — the tree makes a single cut, the crudest possible boundary. (2) Crank depth to 7–8 — every stray point gets its own little box; train accuracy hits 100% but the regions look like noise, not signal. (3) Toggle Gini vs entropy — the splits almost never change. (4) Add a class-0 (red) point deep inside the green region and watch a new sliver get carved out just for it.
Overfitting and how to control it
A tree with no limits will keep splitting until every leaf is pure — in the worst case one training point per leaf. That gives perfect training accuracy and terrible generalization: the model has memorized noise, drawing absurdly specific rectangles around individual points. This is high variance. The remedies all limit how complex the tree can become:
Pre-pruning (early stopping)
- max_depth — cap the number of question levels.
- min_samples_split — refuse to split a node that is too small.
- min_samples_leaf — require each leaf to hold a minimum count.
- min_impurity_decrease — split only if the gain clears a threshold.
Post-pruning
Grow the full tree, then collapse branches that do not help on held-out data. Cost-complexity pruning (CART's ccp_α) minimizes error + α · (number of leaves), trading accuracy against size; larger α prunes more aggressively. The best α is chosen by cross-validation.
The bias–variance tradeoff is visible directly in the demo: shallow trees underfit (high bias, coarse boundary), deep unconstrained trees overfit (high variance, jagged boundary), and the sweet spot is somewhere in between — usually found with cross-validation. In practice, a single well-pruned tree is often beaten by an ensemble of many slightly-overfit trees (random forests, gradient boosting), which average away the variance.
Tree-learning algorithms
Several classic algorithms share the recursive-splitting idea but differ in the details:
| Algorithm | Splitting criterion | Splits | Notes |
|---|---|---|---|
| ID3 | Information gain (entropy) | Multi-way, categorical only | Earliest; biased toward many-valued features; no pruning. |
| C4.5 | Gain ratio (normalized gain) | Multi-way; handles numeric | Successor to ID3; handles missing values; post-prunes. |
| CART | Gini (classification) / MSE (regression) | Strictly binary | Does both classification & regression; cost-complexity pruning. Basis of scikit-learn. |
C4.5 uses gain ratio rather than raw information gain because plain gain is biased toward features with many distinct values (an ID column would "perfectly" split the data). Gain ratio divides the gain by the entropy of the split itself to penalize that. The demo above implements binary CART-style splits with your choice of Gini or entropy.
Pros and cons
| Pros | Cons |
|---|---|
| Highly interpretable — rules read directly off the tree | Prone to overfitting without depth/pruning limits |
| No feature scaling or normalization needed | High variance — small data changes can reshape the tree |
| Handles numeric and categorical features and non-linear boundaries | Only axis-aligned splits — diagonal boundaries need many steps |
| Fast prediction: O(depth) comparisons | Greedy, so not globally optimal; can be unstable |
| Naturally handles multi-class problems and missing values | Single trees are usually beaten by ensembles on accuracy |
Key Takeaways
- A decision tree recursively splits feature space with axis-aligned thresholds, carving it into rectangular regions that each predict one class (or, for regression, a mean value).
- Splits are chosen to maximize information gain = impurity(parent) − weighted impurity(children), using Gini (G = 1 − Σ pₖ²) or entropy (H = −Σ pₖ log₂ pₖ); both are 0 for a pure node.
- Growth is greedy: each node picks the single best split among candidate feature/threshold pairs and never backtracks — good but not globally optimal.
- Leaves predict the majority class (classification) or the mean target (regression) of the samples that reached them.
- Unconstrained trees overfit; max_depth, min_samples, and pruning (especially cost-complexity pruning) trade variance for bias and improve generalization.
- CART (binary, Gini/MSE) underlies most modern libraries; ID3 and C4.5 are its entropy-based ancestors. Single trees power ensembles like random forests and gradient boosting.