{ "id": "epexanjc2s", "slug": "cart-algorithm", "title": "CART algorithm", "updated": "2026-09-30", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.ml_computation" }, { "id": "technology.computing.ai.ml_methods", "label": "Machine learning methods", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.ml_methods" }, { "id": "technology.computing.ai.supervised_unsupervised", "label": "Supervised, unsupervised, and semi-supervised learning", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.supervised_unsupervised" }, { "id": "technology.computing.ai.supervised_unsupervised.statistical_classification", "label": "Classification algorithms", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.supervised_unsupervised.statistical_classification" } ], "geo": [ { "id": "geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised", "label": "Non-geographic · 1946 to 2000: Supervised, unsupervised, and semi-supervised learning", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" }, { "id": "geo.nongeo.t1946.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai" }, { "id": "geo.nongeo.t1946.technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.ml_computation" }, { "id": "geo.nongeo.t1946.technology.computing.ai.ml_methods", "label": "Machine learning methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.ml_methods" }, { "id": "geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised", "label": "Supervised, unsupervised, and semi-supervised learning", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised" } ] } ], "excerpt": "CART (Classification And Regression Trees) is a decision-tree algorithm in machine learning that builds binary trees predicting class labels or numeric values, described in a 1984 monograph.", "snippet": "CART (Classification And Regression Trees) is a decision-tree algorithm in machine learning that builds binary trees predicting class labels or numeric values, described in a 1984 monograph.", "node": "technology.computing.ai.supervised_unsupervised.statistical_classification", "markdown": "# CART algorithm\n\nCART (Classification And Regression Trees) is a decision-tree method in machine learning that recursively partitions a dataset with binary splits to build trees that predict either a class label or a numeric value. It was described in the monograph *Classification and Regression Trees*, a 368-page work focused on constructing tree-structured prediction rules.[1](https://books.google.com/books/about/Classification_and_Regression_Trees.html?id=8k1DvQEACAAJ) Because CART is a registered trademark of the software company Salford Systems, associated with both the methodology and its commercial implementation, open implementations carry other names, such as rpart in R.[24](http://www.math.uchicago.edu/~may/VIGRE/VIGRE2011/REUPapers/McDiarmid.pdf) • [2](https://cran.r-project.org/web/packages/rpart/vignettes/longintro.pdf) The method remains a foundation of supervised learning, both as a standalone interpretable model and as the base learner of ensemble methods.[3](https://link.springer.com/article/10.1007/s42081-024-00258-x)\n\n| Key fact | Detail |\n|---|---|\n| Output | Binary trees for classification (class labels) and regression (numeric leaf values)[4](https://ai.stanford.edu/~ronnyk/treesHB.pdf) |\n| Classification criterion | Gini impurity; ID3 and C4.5 use entropy-based information gain instead[5](https://proceedings.neurips.cc/paper_files/paper/2020/file/6b5617315c9ac918215fc7514bef514b-Paper.pdf) |\n| Regression criterion | Sum of squared residuals; each leaf predicts the training sample mean[6](https://pages.stat.wisc.edu/~loh/treeprogs/guide/eqr.pdf) |\n| Training complexity | Average-case \\( O(pN \\log^{2} N) \\) for \\( p \\) features and \\( N \\) samples[7](https://klusowski.princeton.edu/sites/g/files/toruqf5901/files/documents/klusowski2024large.pdf) |\n| Missing values | Surrogate splits on alternate variables, chosen to maximize predictive association with the preferred split[4](https://ai.stanford.edu/~ronnyk/treesHB.pdf) |\n| Tree selection | Grow a large tree, prune by minimal cost-complexity, choose size by 10-fold cross-validation with the 1-SE rule[4](https://ai.stanford.edu/~ronnyk/treesHB.pdf) |\n| Known weaknesses | Overfitting without pruning, instability of deep splits, bias toward many-valued features, axis-parallel boundaries[7](https://klusowski.princeton.edu/sites/g/files/toruqf5901/files/documents/klusowski2024large.pdf) • [6](https://pages.stat.wisc.edu/~loh/treeprogs/guide/eqr.pdf) |\n\n## How it works\n\nCART performs greedy recursive partitioning: at each node it searches over features and candidate cut points and selects the split that maximizes the decrease in impurity, \\( i(t) - p_{L} \\cdot i(t_{L}) - p_{R} \\cdot i(t_{R}) \\), where \\( i(t) \\) is the impurity of node \\( t \\), \\( t_{L} \\) and \\( t_{R} \\) are the children, and \\( p_{L} \\), \\( p_{R} \\) are the proportions of cases going left and right.[6](https://pages.stat.wisc.edu/~loh/treeprogs/guide/eqr.pdf) For classification the impurity is the Gini index, \\( i(t) = 1 - \\sum_{j} p^{2}(j \\mid t) \\), written for the two-class case as \\( G(p) = 2p \\cdot (1-p) \\).[6](https://pages.stat.wisc.edu/~loh/treeprogs/guide/eqr.pdf) • [5](https://proceedings.neurips.cc/paper_files/paper/2020/file/6b5617315c9ac918215fc7514bef514b-Paper.pdf) A node is impure when classes have equal frequency and maximally pure when only one class is present.[8](https://christophm.github.io/interpretable-ml-book/tree.html) The Gini index can be read as the implied probability of a classification error if the predicted class is chosen with probability proportional to its marginal probability within the node.[9](https://stat154.berkeley.edu/fall-2025/lectures/unit4/unit4_cart.html) Entropy, used by ID3 and C4.5 as \"information gain\", is a different function of the same class proportions; no published head-to-head comparison of the two criteria beyond their formulas has been given.\n\nFor regression, CART uses the sum of squared residuals as the impurity function and builds a piecewise-constant model in which each leaf is fitted by the training sample mean.[6](https://pages.stat.wisc.edu/~loh/treeprogs/guide/eqr.pdf) CART constructs trees with only binary splits; for a binary label this allows optimal partitioning of a categorical attribute into two subsets in time linear in the number of attribute values.[4](https://ai.stanford.edu/~ronnyk/treesHB.pdf) CART and C4.5 operate greedily top-down with average-case complexity \\( O(pN \\log^{2} N) \\) for \\( p \\) features and \\( N \\) samples.[7](https://klusowski.princeton.edu/sites/g/files/toruqf5901/files/documents/klusowski2024large.pdf)\n\n## How it is done\n\nCART does not use stopping rules to control tree size. Instead it grows a large tree, prunes it back until only the root remains, uses cross-validation to estimate the prediction cost of each subtree (misclassification cost for classification trees, squared error for regression trees), and chooses the minimum-cost subtree, with the final size then selected by the 1-SE rule described below.[6](https://pages.stat.wisc.edu/~loh/treeprogs/guide/eqr.pdf) Pruning proceeds by weakest-link cutting indexed by a cost-complexity parameter: for each subtree a cost-benefit ratio \\( (E(X) - \\sum_{L_{i} \\in L_{X}} E(L_{i})) / (|L_{X}| - 1) \\) is computed, the node with the smallest value is converted to a leaf, and the process repeats.[10](https://www.odbms.org/wp-content/uploads/2014/07/DecisionTrees.pdf) In the minimal cost-complexity formulation the subtree cost is the resubstitution error plus the number of leaves times the complexity parameter, and for every parameter value there exists a unique smallest minimizing tree.[4](https://ai.stanford.edu/~ronnyk/treesHB.pdf) The pruning uses resubstitution estimates, which are inferior to honest estimates, but the procedure is quicker than exhaustively comparing all subtrees.[11](https://mason.gmu.edu/~csutton/vt6.pdf)\n\nFinal size is chosen by 10-fold cross-validation and the 1-SE rule: pick the smallest tree whose estimated mean error rate is within one standard error of the best tree's, where \\( \\mathrm{SE} = \\sqrt{E(T_{0}) \\cdot (1 - E(T_{0})) / N} \\).[4](https://ai.stanford.edu/~ronnyk/treesHB.pdf) • [10](https://www.odbms.org/wp-content/uploads/2014/07/DecisionTrees.pdf)\n\nWhen a case lacks the value of the preferred splitting variable, CART does not penalize the splitting criterion (as C4.5 does). Instead it finds a series of surrogate splits on alternate variables, chosen to maximize predictive association with the original split, and uses them to pass the case through the node.[4](https://ai.stanford.edu/~ronnyk/treesHB.pdf) • [12](https://pages.stat.wisc.edu/~loh/treeprogs/guide/LohISI14.pdf) The surrogate variables double as variable importance scores and can detect masking, the situation where a weaker variable hides the influence of a stronger one.[12](https://pages.stat.wisc.edu/~loh/treeprogs/guide/LohISI14.pdf) Simpler alternatives include treating \"missing\" as a new category for categorical predictors or splitting only on observed data, which are better than discarding rows or mean-filling.[13](https://sites.stat.washington.edu/courses/stat527/s13/slides/CART-classification-annotated.pdf)\n\n## Origin\n\nTree methods in statistics predate CART. AID (Automatic Interaction Detection) split nodes by minimizing the sum of child-node impurities measured as squared deviations, with terminal nodes predicting sample means; THAID extended these ideas to classification, and [12](https://pages.stat.wisc.edu/~loh/treeprogs/guide/LohISI14.pdf) [CHAID](https://www.edgepedia.org/chaid) followed in 1980.[14](https://washstat.org/presentations/20150604/loh_slides.pdf) CART itself follows the greedy search of AID and THAID but adds grow-then-prune with weakest-link cutting and cross-validated size selection.[12](https://pages.stat.wisc.edu/~loh/treeprogs/guide/LohISI14.pdf)\n\nIn parallel, the ID3 lineage was developed: C4.5 is an extension of ID3, splits a node into one child per distinct categorical value, uses an entropy-based gain ratio, and prunes with a heuristic formula rather than cross-validation.[12](https://pages.stat.wisc.edu/~loh/treeprogs/guide/LohISI14.pdf) A review of the field describes CART and C4.5 as the two most popular tree algorithms.[15](https://www.eecis.udel.edu/~shatkay/Course/papers/RandomForestGentleIntro2009.pdf)\n\n## Variants\n\nThe R package rpart implements the ideas of the 1984 book and its companion programs; because CART is trademarked and \"tree\" was already used for the S-Plus routines of Clark and Pregibon, the acronym Recursive PARTitioning was chosen.[2](https://cran.r-project.org/web/packages/rpart/vignettes/longintro.pdf) • [16](https://www.mayo.edu/research/documents/biostat-61pdf/doc-10026699%EF%BB%BF) CHAID uses a stepwise-regression-like split search with Bonferroni-adjusted significance tests, and is available in commercial software as well as open-source implementations, such as the Python 'CHAID' package on PyPI and the R package 'chaidr'.[12](https://pages.stat.wisc.edu/~loh/treeprogs/guide/LohISI14.pdf) Quinlan's line continued with the See5/C5.0 system.[11](https://mason.gmu.edu/~csutton/vt6.pdf)\n\nCART's default splits are axis-parallel, but the 1984 book also describes mechanisms for splits on linear combinations of variables, and Murthy, Kasif, and Salzberg described an induction system for oblique decision trees in 1994.[4](https://ai.stanford.edu/~ronnyk/treesHB.pdf) Recent work extends this family: CART-ELC (2025) exhaustively searches candidate hyperplanes, with a single hyperparameter \\( r \\) controlling both the minimum samples per hyperplane and the maximum number of non-zero coefficients, and uses Gini as its default criterion because twoing and Gini often give equal accuracy at higher computational cost for twoing.[17](https://arxiv.org/html/2505.05402v1) SPLIT (SParse Lookahead for Interpretable Trees, 2025) finds high-quality sparse trees by solving sub-problems greedily near the leaves rather than to full optimality.[18](https://proceedings.mlr.press/v267/babbar25a.html)\n\n## Applications\n\nCART's main role in practice is as the base learner of ensembles. Bagging (Breiman, 1996) is an ensemble method that aggregates classification trees for prediction,[19](https://doi.org/10.1023/a:1018054314350) • [15](https://www.eecis.udel.edu/~shatkay/Course/papers/RandomForestGentleIntro2009.pdf) random forests build on bagging and use CART methodology for their constituent trees,[20](https://doi.org/10.1023/a:1010933404324) • [7](https://klusowski.princeton.edu/sites/g/files/toruqf5901/files/documents/klusowski2024large.pdf) and gradient boosting also builds on decision trees.[21](https://ar5iv.labs.arxiv.org/html/2310.17114) A 2024 user guide applies CART and random forests in FinTech and InsurTech.[3](https://link.springer.com/article/10.1007/s42081-024-00258-x)\n\n## Limitations and alternatives\n\nGreedy splitting can cause overfitting, where training error falls but test error rises; pruning algorithms affect the final tree more than the splitting rule does, and Mingers (1989) lists five different pruning algorithms, most requiring a separate pruning sample.[10](https://www.odbms.org/wp-content/uploads/2014/07/DecisionTrees.pdf) CART trees are not guaranteed optimal: at each stage the split selected is the one that immediately reduces impurity or variation the most, and a look-ahead search would be much slower.[11](https://mason.gmu.edu/~csutton/vt6.pdf) Splits can be unstable, particularly in deeper nodes where less data is available, which compromises the oft-cited interpretability.[7](https://klusowski.princeton.edu/sites/g/files/toruqf5901/files/documents/klusowski2024large.pdf) The splitting method is biased toward variables with more distinct values, because a variable with \\( m \\) distinct values allows \\( m - 1 \\) candidate splits if non-categorical and \\( 2^{m-1} - 1 \\) if categorical.[6](https://pages.stat.wisc.edu/~loh/treeprogs/guide/eqr.pdf) Axis-parallel boundaries limit the shapes of the partition, which oblique-tree variants address.[17](https://arxiv.org/html/2505.05402v1) For regression, a single CART tree typically has lower prediction accuracy than even the classical multiple linear model.[6](https://pages.stat.wisc.edu/~loh/treeprogs/guide/eqr.pdf) In a published benchmark of thirty-three algorithms on thirty-two datasets, C4.5, IND-CART, and QUEST had the best accuracy among decision-tree algorithms with univariate splits, and the most accurate tree overall was QUEST with linear splits.[22](https://link.springer.com/content/pdf/10.1023/A:1007608224229.pdf)\n\nAs alternatives, recent advances in mixed-integer optimization and dynamic programming, with increased computing power, have made it feasible to search directly over the space of optimal decision trees rather than accept greedy local choices.[23](https://arxiv.org/html/2409.12788v2)\n\n## References\n\n1. [Classification and Regression Trees (Breiman, Friedman, Stone, Olshen), CRC Press, 1984, 368 pages](https://books.google.com/books/about/Classification_and_Regression_Trees.html?id=8k1DvQEACAAJ)\n2. [rpart: An Introduction to Recursive Partitioning (CRAN vignette)](https://cran.r-project.org/web/packages/rpart/vignettes/longintro.pdf)\n3. [A user guide of CART and random forests with applications in FinTech and InsurTech (2024)](https://link.springer.com/article/10.1007/s42081-024-00258-x)\n4. [C5.1.3 Decision Tree Discovery (Kohavi, Handbook of Data Mining and Knowledge Discovery)](https://ai.stanford.edu/~ronnyk/treesHB.pdf)\n5. [Universal guarantees for decision tree induction via a higher-order splitting criterion (NeurIPS 2020)](https://proceedings.neurips.cc/paper_files/paper/2020/file/6b5617315c9ac918215fc7514bef514b-Paper.pdf)\n6. [Classification and Regression Tree Methods (Loh, Encyclopedia of Statistics chapter)](https://pages.stat.wisc.edu/~loh/treeprogs/guide/eqr.pdf)\n7. [Large Scale Prediction with Decision Trees (Klusowski)](https://klusowski.princeton.edu/sites/g/files/toruqf5901/files/documents/klusowski2024large.pdf)\n8. [Decision Tree – Interpretable Machine Learning (Molnar)](https://christophm.github.io/interpretable-ml-book/tree.html)\n9. [Classification and Regression Trees (CART) – Stat 154 Berkeley lecture notes](https://stat154.berkeley.edu/fall-2025/lectures/unit4/unit4_cart.html)\n10. [Decision Trees (K20307 textbook chapter)](https://www.odbms.org/wp-content/uploads/2014/07/DecisionTrees.pdf)\n11. [Handbook of Statistics chapter on CART (doi:10.1016/S0169-7161(04)24011-1)](https://mason.gmu.edu/~csutton/vt6.pdf)\n12. [Fifty Years of Classification and Regression Trees (Loh, ISI review)](https://pages.stat.wisc.edu/~loh/treeprogs/guide/LohISI14.pdf)\n13. [Recursive Binary Partitions – CART classification slides (UW STAT 527)](https://sites.stat.washington.edu/courses/stat527/s13/slides/CART-classification-annotated.pdf)\n14. [A Brief History of Classification and Regression Trees (Loh slides)](https://washstat.org/presentations/20150604/loh_slides.pdf)\n15. [An Introduction to Recursive Partitioning: Rationale, Application, and Characteristics of Classification and Regression Trees, Bagging, and Random Forests (Strohl et al., 2009)](https://www.eecis.udel.edu/~shatkay/Course/papers/RandomForestGentleIntro2009.pdf)\n16. [Mayo Clinic Biostatistics note on rpart](https://www.mayo.edu/research/documents/biostat-61pdf/doc-10026699%EF%BB%BF)\n17. [CART-ELC: Oblique Decision Tree Induction via Exhaustive Search](https://arxiv.org/html/2505.05402v1)\n18. [Near-Optimal Decision Trees in a SPLIT Second (PMLR v267, 2025)](https://proceedings.mlr.press/v267/babbar25a.html)\n19. [Leo Breiman (1996). Bagging Predictors. Machine Learning.](https://doi.org/10.1023/a:1018054314350)\n20. [Leo Breiman (2001). Random Forests. Machine Learning.](https://doi.org/10.1023/a:1010933404324)\n21. [On the Convergence of CART under Sufficient Impurity Decrease Condition](https://ar5iv.labs.arxiv.org/html/2310.17114)\n22. [A Comparison of Prediction Accuracy, Complexity, and Training Time of Thirty-Three Old and New Classification Algorithms](https://link.springer.com/content/pdf/10.1023/A:1007608224229.pdf)\n23. [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://arxiv.org/html/2409.12788v2)\n24. [McDiarmid (math.uchicago.edu)](http://www.math.uchicago.edu/~may/VIGRE/VIGRE2011/REUPapers/McDiarmid.pdf)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Machine learning and neural computation › Machine learning methods › Supervised, unsupervised, and semi-supervised learning › Classification algorithms*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Sep 30, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://ai.stanford.edu/~ronnyk/treesHB.pdf", "https://pages.stat.wisc.edu/~loh/treeprogs/guide/eqr.pdf", "https://mason.gmu.edu/~csutton/vt6.pdf", "https://pages.stat.wisc.edu/~loh/treeprogs/guide/LohISI14.pdf", "https://www.eecis.udel.edu/~shatkay/Course/papers/RandomForestGentleIntro2009.pdf", "http://www.math.uchicago.edu/~may/VIGRE/VIGRE2011/REUPapers/McDiarmid.pdf" ], "url": "https://www.edgepedia.org/cart-algorithm", "markdown_url": "https://www.edgepedia.org/cart-algorithm.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"CART algorithm\", Edgepedia (EdgeChat), https://www.edgepedia.org/cart-algorithm. Edgepedia Community License 1.0.", "credit_md": "\"[CART algorithm](https://www.edgepedia.org/cart-algorithm)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/cart-algorithm](https://www.edgepedia.org/cart-algorithm). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"CART algorithm\", Edgepedia (EdgeChat), https://www.edgepedia.org/cart-algorithm. Edgepedia Community License 1.0.", "speakable": "CART is a decision-tree algorithm in machine learning that builds binary trees predicting class labels or numeric values, described in a 1984 monograph." }