Classification and Regression Trees (CART) is a framework for supervised learning that predicts categorical outcomes or numerical values by repeatedly dividing a dataset into increasingly homogeneous groups. It is a particular methodology within decision-tree learning, rather than a name for every classification or regression tree. Its defining features include binary recursive partitioning, explicit criteria for choosing splits, and a pruning procedure that balances predictive fit against tree size.
The framework was established by Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone in their 1984 book Classification and Regression Trees. It brought classification and regression into a common statistical treatment and made tree construction a systematic model-selection problem. A fitted CART model can be read as a sequence of conditional rules, while its mathematical interpretation is a piecewise-constant prediction function over the predictor space.
CART is important both as a standalone method and as a foundation for modern ensemble learning. Its strengths include automatic discovery of nonlinear relationships, interactions between variables, and useful thresholds without requiring a prespecified equation. Its limitations—especially instability, selection bias, and coarse predictions—also explain why many contemporary systems combine numerous trees rather than rely on one.
Historical development and scope
Tree-based prediction predates the CART framework. Early statistical work on automatic interaction detection used successive partitions to identify groups with different response values. In parallel, researchers in artificial intelligence developed methods for learning symbolic decision rules from examples. These traditions shared the idea that a complicated prediction problem could be decomposed into a sequence of simpler questions, but they differed in split criteria, treatment of variable types, and methods for deciding when to stop.
The 1984 CART monograph provided an integrated statistical methodology for both classification and regression. Classification assigns observations to discrete categories, such as product types; regression predicts numerical responses, such as manufacturing yield. CART treated both tasks as recursive partitioning problems, while distinguishing their appropriate measures of fit. An especially influential contribution was to separate the construction of a large tree from the selection of its final size. Rather than assume that every locally weak split should be rejected immediately, the method allowed an initially large tree to be simplified afterward.
The name CART therefore has a narrower meaning than “decision tree.” Classical CART uses binary splits: every internal node has exactly two children. A categorical predictor with several levels is handled by dividing its levels into two groups, not necessarily by creating one branch per level. Other tree-learning traditions may use multiway splits, different statistical tests, or different pruning procedures. J. Ross Quinlan’s ID3 and C4.5, for example, belong to a related but distinct family; C4.5 became widely known through his 1993 book on the method.
Terminology in software is less precise than this historical distinction. A library may describe its trees as CART-style because they use binary splits and impurity reduction while omitting features of the original framework, such as surrogate splits. Conversely, a system may preserve cost-complexity pruning while extending the available loss functions or missing-value rules. Whether an implementation supports a particular feature must therefore be established from its actual algorithm rather than inferred from the CART label.
CART also helped connect predictive modeling with exploratory statistics. A tree can expose subgroups and conditional patterns without requiring a global linear relationship. However, the framework is primarily predictive: a branch identified from observational data does not, by itself, establish causation, and a variable selected near the root is not automatically a scientifically fundamental determinant of the response.
Tree structure and prediction regions
A CART model is represented by a rooted binary tree. The root contains the full set of training observations. Each internal node applies a test to one predictor and routes an observation to one of two child nodes. Terminal nodes, also called leaves, contain the final predictions. Prediction consists of following a single path from the root to a leaf, evaluating only the tests encountered along that path.
For a numerical predictor , a typical split has the form , where is a threshold. Observations satisfying the condition enter one child; the others enter the second. For a categorical predictor, the test is membership in a subset of its categories. A split on material type, for instance, might send aluminum and copper to one child and steel and titanium to the other. Classical univariate CART does not ordinarily split on a linear combination such as ; that belongs to the broader family of oblique trees.
Each leaf corresponds to a region formed by intersecting all the conditions on its path. With numerical predictors, these are axis-aligned regions, possibly unbounded in some directions. If the leaves define regions , the prediction function can be written as
where is the prediction assigned to region . The indicator equals one when the observation falls in that region. The model is therefore piecewise constant, even when the relationship being approximated is smooth.
For ordinary squared-error regression, a leaf predicts the mean response among its training observations. For classification, it commonly predicts the most frequent class and stores the empirical class proportions as probability estimates. With observation weights , the estimated probability of class in leaf is
Class weighting, prior probabilities, and unequal error costs can alter the effective proportions or the final class decision.
The structure naturally expresses interactions. A split on machine temperature might occur only within the branch for a particular material, meaning temperature has a different predictive role in that subgroup. Such conditional structure is learned without explicitly constructing product terms. Nevertheless, a short rule is only locally simple: a deep tree may contain hundreds of overlapping conditions across its different paths, and understanding one prediction can be much easier than understanding the entire model.
Split criteria for classification and regression
At each node, CART compares candidate splits by how much they improve the homogeneity of the resulting children. Let be the total observation weight in node , and let measure its impurity. A candidate split producing children and has local impurity reduction
The weighting is essential: a tiny pure child should not receive the same influence as a large child. Subject to minimum-size and other constraints, the algorithm chooses the split with the largest improvement.
For classification, the criterion most closely associated with CART is Gini impurity:
Here is the proportion of class at the node, possibly adjusted by weights or priors. Gini impurity is zero for a node containing only one class. For two equally represented classes it is . Another interpretation is the probability of a mismatch between two independent class draws from the node’s class distribution.
A numerical example shows why child weights matter. Suppose a node contains 50 observations from each of two classes. A split creates two equally sized children, with class counts and . Each child has Gini impurity , so the reduction is . By comparison, a split that isolates only one observation may create a pure leaf but leave almost all the original uncertainty in the other child. Some implementations also support entropy and information gain, although these are not the defining historical criterion of CART.
For regression with squared-error loss, a node’s impurity is its mean squared deviation from the node mean. Minimizing the weighted impurities of the children is equivalent to minimizing their combined residual sum of squares:
The reduction from a split can be expressed as
Thus, a useful regression split separates child means while accounting for their sizes. Alternative loss functions lead to different leaf predictions: absolute-error loss, for example, is minimized by a median rather than a mean. The criterion used to grow a tree, the loss used to prune it, and the metric used for external evaluation need not be identical, but their differences affect which model is selected.
Recursive growth and computational properties
Tree construction is a top-down greedy algorithm. Starting at the root, the procedure searches the available predictors and candidate partitions, selects the best immediate split, and repeats the operation within each child. This process is a form of recursion because the same subproblem—finding a useful division of the observations—is applied to successively smaller datasets. Once a split has been made, ordinary CART growth does not reconsider it in light of the structures found farther down the tree.
For a numerical predictor with distinct values at a node, there are at most distinct threshold partitions. The threshold can be represented by a value between adjacent observations because moving it within that interval leaves the training partition unchanged. Sorting observations by the predictor allows an implementation to scan possible boundaries while updating cumulative class counts, weight totals, or response sums. It need not recompute every candidate’s impurity from the beginning.
Categorical predictors pose a different search problem. A predictor with categories has distinct nontrivial binary partitions when complementary subsets are counted as the same split. Exhaustive search therefore grows exponentially with the number of categories. Under standard binary-classification or squared-error regression settings, categories can be ordered by a response summary and searched along that order, avoiding enumeration of every subset. Multiclass problems and additional constraints can require different strategies or approximations.
The time complexity depends on how sorting and split search are implemented. With efficient reuse of sorted information, numerical split scans cost roughly per tree level for observations and predictors, giving approximately work for a balanced tree, in addition to sorting-related overhead. Repeated sorting, categorical searches, surrogate calculations, and severely unbalanced growth can increase this cost. Prediction usually requires tests for a path of depth , rather than examination of every node.
Growth must eventually stop. Common constraints include maximum depth, minimum observations required to split a node, minimum observations or weight in each leaf, and minimum impurity improvement. These are hyperparameters, not parameters estimated by a single split. They restrict the search and computational burden, but overly strict early stopping can miss useful structure. An interaction may become visible only after an initially modest split. The classic exclusive-or pattern illustrates the issue: either predictor alone may offer no impurity reduction even though a two-level tree can separate the classes perfectly.
Cost-complexity pruning and tree-size selection
A tree that keeps growing can fit accidental details of the training sample. Its leaves become smaller, its rules more specific, and its training error generally lower. This does not guarantee improved generalization to new observations. Classical CART addresses this form of overfitting through cost-complexity pruning, which starts with a sufficiently large tree and considers simpler subtrees obtained by replacing branches with leaves.
The penalized objective is
where is the tree’s empirical risk, is its number of leaves, and is the penalty per leaf. For regression, risk can be based on squared error. For classification, it may be based on misclassification cost, even when Gini impurity was used during growth. Larger values of favor smaller trees. Its numerical scale depends on whether risk is expressed as a sum, average, or another normalized quantity.
The efficient pruning procedure is known as weakest-link pruning. Let denote the branch rooted at internal node , and let be the risk if that whole branch is replaced by a single leaf. Its effective pruning value is
This is the increase in empirical risk per removed leaf. The branch or branches with the smallest effective value are pruned first; the values are then recomputed. Repetition produces a nested sequence of subtrees, ending at the root-only tree. Appropriate handling of ties preserves the cost-complexity characterization.
Selecting among these subtrees requires evidence beyond their training fit. Cross-validation estimates prediction error by repeatedly fitting on part of the data and evaluating on held-out observations. The selected complexity may minimize the estimated error. The commonly used one-standard-error rule instead selects the smallest tree whose estimated error lies within one estimated standard error of the minimum. This is a model-selection convention favoring simplicity, not a guarantee that the smaller tree is statistically equivalent to the larger one.
Valid cross-validation requires rebuilding trees within the training portion of each fold. Growing a tree once on all observations and merely evaluating its pruned versions on those same observations would not reproduce the learning procedure on unseen data. When a final performance estimate is needed, a separate test set or nested cross-validation can separate model selection from evaluation. Cost-complexity pruning is therefore both a computational procedure for generating candidate subtrees and a form of regularization whose strength must be selected independently of the final performance assessment.
Missing values, categorical encoding, and error costs
Classical CART includes an explicit approach to missing predictor values through surrogate splits. After choosing a primary split, the algorithm searches other predictors for tests that reproduce the primary split’s left-versus-right assignments. These alternatives are ranked by their agreement with the primary partition, using observations for which the relevant values are available. Surrogates are intended to imitate the primary routing decision, not simply to identify the next-best independent predictor of the response.
At prediction time, an observation with a missing value for the primary predictor can be routed using the highest-ranked available surrogate. If that surrogate is also unavailable, another can be tried. If no usable surrogate exists, an implementation needs a fallback rule, such as assignment to a designated child. Details of agreement adjustment and fallback behavior matter, especially when the primary split is highly unbalanced: a surrogate that always chooses the larger child can have high raw agreement without providing much information.
This historical mechanism should not be confused with every contemporary missing-value strategy. Some tree systems learn a default child for missing values directly during split search. Others require imputation before training, or support missing values only for certain criteria and configurations. Missingness itself can carry predictive information—for example, whether a measurement was collected may reflect an operational process. That relationship can change when the collection process changes, creating distribution shift even if the underlying physical relationship remains stable.
Categorical representation also affects the trees that can be learned. Native subset splits can group several category levels in one test. With one-hot encoding, each indicator asks whether an observation belongs to one category; expressing a larger grouping may require several splits. Arbitrarily coding categories as integers creates an artificial ordering and permits threshold partitions based on that ordering. Such partitions are appropriate for genuinely ordered categories but need not represent the structure of nominal categories. Large numbers of rare levels can also encourage highly sample-specific partitions.
Unequal error costs and class imbalance introduce another distinction: class frequency is not the same as the consequence of an error. If is the cost of predicting class when the true class is , the minimum-expected-cost action in a leaf is
It need not be the majority class. Priors, class weights, sampling choices, and decision costs can affect splitting and classification in different ways. Reweighting a training sample may improve sensitivity to a rare class while making its raw leaf proportions inappropriate as estimates of prevalence in the deployment population.
Statistical behavior, instability, and interpretation
A small CART tree has a relatively restricted prediction function; a very large one can describe intricate local patterns. This produces a trade-off between approximation error and sampling variability. A shallow tree may miss important structure, while a deep tree may base predictions on only a handful of observations. Because each split partitions the available sample, the amount of evidence supporting later decisions can decline rapidly with depth.
One of CART’s best-known characteristics is instability. Two candidate root splits may have almost identical impurity reductions, yet lead to substantially different descendants. A small change in the training sample can reverse their ranking and alter much of the final tree. Correlated predictors amplify this effect because several variables may provide almost interchangeable partitions. Different fitted structures can consequently deliver similar predictions, and a variable’s absence from one tree does not establish that it contains no useful information.
Interpretability is strongest for compact trees. A root-to-leaf path can be translated into a conjunction of conditions, with each leaf accompanied by its sample size, predicted value, and class composition. This makes trees useful in explainable artificial intelligence, but the interpretation remains predictive rather than causal. The selected threshold is also a sample-dependent estimate. A split at 17.4 units does not necessarily imply that the underlying system has a genuine discontinuity exactly at that value.
Impurity-based feature importance sums the weighted reductions credited to each predictor across the tree. It describes how the fitted model used its variables, but it is not an unbiased measure of scientific relevance. Predictors with many possible cut points can receive more opportunities to produce a favorable split by chance. Strongly correlated predictors can divide importance unevenly, with the variable chosen first receiving credit that another variable could have supplied. Permutation-based assessments ask a different question—how predictive performance changes when a variable’s information is disrupted—but they too are affected by dependence between predictors.
CART also has characteristic geometric limitations. Axis-aligned splits approximate diagonal boundaries or smooth additive functions through stair-step regions, potentially requiring many leaves. Ordinary regression trees cannot extrapolate a continuing trend beyond the observed predictor range: they return a leaf’s constant prediction. Under standard weighted-mean leaves with nonnegative weights, predictions remain within the range of the training responses. Conversely, strictly increasing transformations of a numerical predictor preserve its ordering and the available training partitions, apart from numerical details. This is why standard CART generally does not require feature scaling, although transformations and encoding can still affect implementation behavior.
Evaluation, practical applications, and software
CART is commonly applied to structured, tabular data in which observations are described by numerical and categorical variables. Examples include predicting equipment failure, estimating property values, classifying manufactured parts, and examining ecological habitat patterns. A modest-sized tree can expose operational thresholds and combinations of conditions that are difficult to see in a global linear model. Such applications depend on the representativeness of the observations and the suitability of the recorded variables, not merely on the tree’s ability to fit them.
Evaluation must match the prediction task. For classification, accuracy measures the fraction of correct labels but can conceal poor performance on rare classes. Class-specific error rates, precision and recall, and confusion matrices provide different information. When the outputs are intended as probabilities, metrics such as logarithmic loss or the Brier score assess more than the final label. Regression evaluation often uses mean squared error, root mean squared error, or mean absolute error; these assign different penalties to large residuals and can favor different model sizes.
The structure of the data determines what counts as a valid holdout. Randomly dividing records can be misleading when several records describe the same machine, customer, location, or time-dependent process. Group-based splits evaluate transfer to unseen groups, while chronological splits address prediction into later periods. Data leakage occurs when information unavailable at prediction time enters training or model selection. A tree can make such leakage especially conspicuous by selecting a suspiciously powerful field near the root, but its readable structure does not prevent the problem.
Leaf probability estimates require separate scrutiny. A terminal node with nine positive observations out of ten yields an empirical positive proportion of , but that estimate rests on little evidence and on a region selected using the same data. Small leaves can generate probabilities close to zero or one that perform poorly under probability-sensitive losses. Larger leaf-size constraints, smoothing, pruning, and external probability assessment address different aspects of this issue. Out-of-sample reliability cannot be inferred from apparently pure training leaves.
Widely used implementations include the rpart package in R and decision-tree estimators in scikit-learn. Their interfaces expose controls for depth, leaf size, split criteria, and pruning, but their supported data types and missing-value mechanisms differ. Reproducibility also depends on tie-breaking, random seeds where applicable, numerical precision, and library versions. A saved diagram alone is not always a complete model specification: category encodings, preprocessing steps, treatment of unseen categories, and branch comparison rules are part of the prediction procedure as well.
CART as a foundation for ensemble methods
The weaknesses of individual trees helped motivate methods that combine many of them. Trees are attractive base learners because they can fit nonlinear structure, require relatively little numerical preprocessing, and can be varied by changing the observations or predictors available during training. Their instability becomes useful when aggregation averages away sample-specific fluctuations. The resulting model is no longer a single readable decision hierarchy, even though each component retains the same basic split-and-leaf structure.
Bootstrap aggregating, introduced by Breiman in 1996, fits models to bootstrap samples drawn with replacement from the training data. For regression, their predictions are averaged; for classification, votes or estimated probabilities are combined. Deep trees are particularly responsive to changes in the sampled data, so averaging them can substantially reduce variance. The benefit depends on how correlated their errors are: repeatedly fitting nearly identical trees adds little independent information.
Breiman’s 2001 random forest method adds randomized predictor selection during tree growth. At each node, a randomly chosen subset of predictors is considered for splitting. This reduces the tendency of one highly predictive variable to dominate every tree and can lower correlations among the resulting models. Random forests commonly use deep, unpruned trees rather than the individually optimized, pruned trees typical of standalone CART. Their accuracy therefore arises from the combination of many variable learners, not from selecting one preferred explanatory tree.
Gradient boosting, developed in its influential statistical formulation by Friedman in 2001, combines trees sequentially. Each new tree targets aspects of the loss that the current ensemble has not yet fitted. For squared-error regression, this can be understood as fitting residuals; for more general differentiable losses, it involves negative gradients or related optimization quantities. Tree depth controls interaction complexity, while the number of stages and shrinkage regulate the overall model. These trees are components of an additive function rather than independently complete predictors.
Modern systems such as XGBoost, LightGBM, and CatBoost extend boosted-tree learning with different optimization, regularization, categorical-feature, and computational techniques. Their node objectives can use gradients and second-order information rather than ordinary CART impurity formulas, so they are not simply repeated applications of the entire original CART procedure. Nevertheless, they retain its central representational idea: recursive partitions convert heterogeneous predictor spaces into locally simple prediction regions. Replacing such an ensemble with a compact explanatory tree can make its behavior easier to inspect, but the compact tree is an approximation and need not preserve the ensemble’s predictions.