Decision tree

A decision tree partitions the feature space into axis-aligned regions by recursive binary splitting. At each node the learner searches every feature and threshold for the split that most reduces an impurity measure: Gini impurity or entropy (information gain) for classification, mean squared error for regression. Leaves predict the majority class, or class proportions, or the mean target of their training samples. Finding the optimal tree is NP-hard, so all practical algorithms are greedy and top-down.

The main algorithm families are ID3 (Quinlan, 1986), which used information gain on categorical features; its successor C4.5, which handles numeric features by thresholding and prunes with error estimates; and CART (Breiman, Friedman, Olshen and Stone, 1984), which builds strictly binary trees for both classification and regression and prunes by cost-complexity. scikit-learn implements an optimised CART.

Unconstrained trees keep splitting until leaves are pure and so memorise the training set, a textbook case of overfitting with high variance: small changes in the data can produce a completely different tree. Controls are pre-pruning (maximum depth, minimum samples per leaf or split, minimum impurity decrease) and post-pruning such as CART's minimal cost-complexity pruning, tuned by cross-validation. Trees need no feature scaling, handle mixed data types, and capture interactions naturally, but their axis-aligned, piecewise-constant predictions approximate smooth or diagonal boundaries poorly and cannot extrapolate beyond the training range.

A shallow tree is one of the few models whose full decision logic a person can read, which is why it is used as an interpretable model and as a surrogate to explain black-box models. Impurity-based feature importances from trees are cheap but biased toward features with many distinct values; permutation importance is the usual check. Their instability is also the reason ensembles work so well: random forests average many decorrelated trees to cut variance, and gradient boosting adds many shallow trees in sequence to cut bias.