Decision tree

Also known as: classification tree · regression tree

On this page 7

A decision tree is a supervised learning model that predicts an outcome by passing each example through a hierarchy of if-then tests on its features, ending in a leaf that holds a class label or a numeric value. Machine learning practitioners call the variant that predicts categories a classification tree and the variant that predicts numbers a regression tree; together they are often grouped under the name CART.

Decision trees matter for two reasons. They are among the most interpretable models in machine learning, because a single prediction can be traced as a readable path of conditions. They are also the building block of the strongest tabular methods, including random forest and gradient boosting, which combine hundreds or thousands of trees.

How a decision tree splits the data

A decision tree is built by recursive binary partitioning: the algorithm searches every feature and candidate threshold, chooses the split that best separates the target, and then repeats the search independently inside each resulting subset. The process is greedy, which means each split is optimal only locally and the algorithm never revisits earlier choices.

Each internal node stores one test, such as “income below 42,000” or “color is red”. Each leaf node stores the prediction: the majority class (or class proportions) for classification and the mean of the training targets for regression. Prediction cost is proportional to tree depth, so a balanced tree with depth 10 needs at most ten comparisons per example.

The quality of a split is measured by how much it reduces node impurity. The table below lists the criteria used in common implementations.

CriterionTaskWhat it measures
Gini impurityClassificationProbability of mislabeling a random sample drawn from the node
Entropy (information gain)ClassificationReduction in uncertainty, in bits, after the split
Gain ratioClassificationInformation gain normalized by split size, used in C4.5
Mean squared errorRegressionVariance of targets around the leaf mean
Mean absolute errorRegressionDeviation around the leaf median, more robust to outliers
Common split criteria

In practice Gini impurity and entropy produce very similar trees; Gini is slightly cheaper to compute because it avoids logarithms, which is why it is the default in many libraries.

Main decision tree algorithms

Several classic induction algorithms define how trees are grown, which split types they allow and how they handle missing data. Most modern software follows the CART approach with binary splits, but the older families still appear in literature and in some statistical tools.

AlgorithmSplit typeDistinctive feature
ID3Multiway on categorical featuresUses information gain; no pruning or numeric thresholds
C4.5 and C5.0Multiway and numeric thresholdsGain ratio, pruning and handling of missing values
CARTBinary onlyGini or squared error, cost-complexity pruning, surrogate splits
CHAIDMultiwayChi-square significance tests, popular in market segmentation
Conditional inference treesBinaryPermutation tests that reduce bias toward many-valued features
Classic tree induction algorithms

The choice of algorithm matters less than the stopping and pruning settings, because those decide whether the final tree generalizes or memorizes the training data.

Controlling depth, overfitting and pruning

An unrestricted decision tree keeps splitting until every leaf is pure, which typically yields near-zero training error and poor test accuracy. This is the classic high-variance side of the bias-variance tradeoff: small changes in the training data can produce a completely different tree.

Two strategies limit this. Pre-pruning stops growth early through hyperparameters, while post-pruning grows a large tree and then removes branches that do not improve validation performance. CART uses cost-complexity pruning, which adds a penalty alpha per leaf and selects alpha by cross-validation.

HyperparameterTypical rangeEffect when increased
Maximum depth3 to 20More complex boundaries, higher overfitting risk
Minimum samples per leaf1 to 100 or 0.5% to 5% of rowsSmoother predictions, less variance
Minimum samples to split2 to 200Fewer splits on small subsets
Maximum number of leaves8 to 1,000Caps total model size directly
Cost-complexity alpha0 to about 0.05Stronger pruning, simpler tree
Key hyperparameters and their effect

A practical rule is to tune minimum samples per leaf first, because it controls leaf reliability directly, and then tune depth or alpha with cross-validation rather than by inspection.

A single decision tree trades accuracy for transparency, and its neighbors in machine learning resolve that trade-off differently. The comparison below shows where the single tree fits among common tabular models.

ModelInterpretabilityTypical accuracy on tabular dataMain weakness
Single decision treeVery highModerateHigh variance, unstable structure
Random forestLow to moderateHighLarge model, slower prediction
Gradient boostingLowUsually highestSensitive to tuning, can overfit
Logistic regressionHighModerateNeeds manual interactions and nonlinearity
k-nearest neighborsModerateModerateRequires feature scaling, slow at query time
Single tree versus related models

Trees capture feature interactions and nonlinear effects automatically, and they need no feature scaling, because a threshold test is unaffected by monotonic transformations. Their decision boundary, however, is made of axis-aligned rectangles, so a diagonal boundary requires many small steps.

Limitations and common mistakes

Most problems with decision trees come from instability, bias in split selection and misleading importance scores. The following points summarize what experienced practitioners watch for.

  • Instability: removing a few rows can change the root split and therefore the entire tree, so a single tree should not be treated as a stable description of the data.
  • Bias toward many-valued features: impurity-based criteria favor features with many distinct values, such as identifiers, which can create spurious splits.
  • Impurity-based feature importance inherits that bias; permutation importance is a more reliable check.
  • Poor extrapolation: a regression tree predicts a constant beyond the range of the training data, so it cannot follow a trend.
  • Class imbalance: without class weights, leaves tend to predict the majority class and minority recall suffers.

A frequent mistake is to report the accuracy of a fully grown tree evaluated on its own training data, which overstates performance. Always evaluate on held-out data and inspect the depth of the selected model.

A non-technical view

A decision tree works like a game of twenty questions. To decide whether a loan application looks risky, it might first ask whether the income is above a certain level, then whether there were late payments, then how long the person has held the job. Each answer sends the case down a different branch until it reaches a final verdict.

The computer learns which questions to ask, and in which order, by studying many past examples. The key takeaway is simple: a decision tree is easy to read and explain, but a tree that asks too many questions starts memorizing old cases instead of learning general rules.

A concrete example

A regional telecom operator wants to predict which subscribers will cancel their contracts in the next quarter. The analytics team has 120,000 customer records with features such as contract type, monthly charge, number of support calls and tenure in months.

The team trains a classification tree with maximum depth 5 and at least 200 customers per leaf. The root split is contract type, followed by support calls above three and tenure below eight months. The resulting tree reaches slightly lower accuracy than a gradient boosting model on the test set, but it produces a dozen readable rules that the retention department can apply directly.

The outcome is a two-model setup: the boosted model scores customers, while the shallow decision tree explains the main churn segments to managers and guides the design of targeted retention offers.