CART
In plain wordsA classic recipe for building decision trees that splits data two ways at every step, works for both categories and numbers, and then trims the tree back so it does not memorize noise.
A decision-tree methodology, named after the 1984 monograph that defined it, for growing binary treesdecision tree, n.: A model that makes a prediction by asking a series of yes-or-no questions about the input, like a flowchart, with each answer leading to the next question until it reaches a final answer. for both classificationclassification, n.: Sorting things into categories — spam or not spam, which animal is in a photo, which language a text is written in — by learning from examples that are already labeled. and regressionregression, n.: Predicting a number rather than a category — a house's price, tomorrow's temperature, a patient's blood pressure — by learning from past examples where the answer is known.. Each internal node splits on one feature (optionally on a linear combination of features) into exactly two children, chosen to maximize the decrease in Gini impurityGini impurity, n.: A score for how mixed a group is: zero when every item belongs to the same category, higher when categories are jumbled together. Decision trees choose splits that make groups purer. or the 'twoing' criterion for classification, or in squared error for regression. CART deliberately grows a large tree and then applies cost-complexity (weakest-link) pruningpruning, n.: Cutting away the parts of an AI model that contribute least, as a gardener trims branches, so the model becomes smaller or faster while still working nearly as well., choosing the subtree size by cross-validationcross-validation, n.: A fair way to test a model when data are limited: split the data into several parts, train on all but one, test on the part left out, and rotate so every part takes a turn.. It handles missing values with surrogate splits that mimic the primary split using other features, and it provides an early measure of variable importance. Its binary splits, regression trees and pruning scheme underlie most modern tree software, including scikit-learn's trees and the base learners of gradient boostinggradient boosting, n.: A method that builds a strong predictor by adding small decision trees one at a time, each trained to correct the errors that remain after all the trees before it. libraries.
We used CART-style cost-complexity pruning and picked the smallest tree within one standard error of the best cross-validated error.
Origin
Defined in the book 'Classification and Regression Trees' (Wadsworth, 1984) by Leo Breiman, Jerome Friedman, Richard Olshen and Charles Stone, which built on the AID (1963) and THAID (1972) survey-analysis programs and added cross-validated pruning. A commercial implementation was sold under the trademarked CART name by Salford Systems, now part of Minitab.
Usage note
R's standard implementation is called rpart ('recursive partitioning') because, as its authors explain, CART is the trademarked name of one commercial implementation and 'tree' was already taken by an S-PLUS routine. Scikit-learn describes its trees as an optimized version of CART.
Related
- decision treedecision tree, n.: A model that makes a prediction by asking a series of yes-or-no questions about the input, like a flowchart, with each answer leading to the next question until it reaches a final answer.
- Gini impurityGini impurity, n.: A score for how mixed a group is: zero when every item belongs to the same category, higher when categories are jumbled together. Decision trees choose splits that make groups purer.
- pruningpruning, n.: Cutting away the parts of an AI model that contribute least, as a gardener trims branches, so the model becomes smaller or faster while still working nearly as well.
- ID3ID3, abbr.: An early, influential method for automatically building a decision tree from examples, choosing at each step the question that most reduces uncertainty about the answer.
- C4.5C4.5, prop. n.: A widely used 1990s program that learns decision trees and rule sets from data; unlike its predecessor, it trims away unhelpful branches, copes with gaps in the data and can split on measured numbers.
- random forestrandom forest, n.: A prediction method that builds hundreds of decision trees, each from a random sample of the data and features, and lets them vote. The crowd is far more reliable than any single tree.
- cross-validationcross-validation, n.: A fair way to test a model when data are limited: split the data into several parts, train on all but one, test on the part left out, and rotate so every part takes a turn.
- C4.5C4.5, prop. n.: A widely used 1990s program that learns decision trees and rule sets from data; unlike its predecessor, it trims away unhelpful branches, copes with gaps in the data and can split on measured numbers.
Sources
- Breiman, L., Friedman, J. H., Olshen, R. A. & Stone, C. J. (1984). Classification and Regression Trees. Belmont, CA: Wadsworth.
- Loh, W.-Y. (2014). Fifty Years of Classification and Regression Trees. International Statistical Review, 82(3), 329–348. pages.stat.wisc.edu/~loh/treeprogs/guide/LohISI14.pdf
Mentioned in
decision treedecision tree, n.: A model that makes a prediction by asking a series of yes-or-no questions about the input, like a flowchart, with each answer leading to the next question until it reaches a final answer., Gini impurityGini impurity, n.: A score for how mixed a group is: zero when every item belongs to the same category, higher when categories are jumbled together. Decision trees choose splits that make groups purer., Leo BreimanLeo Breiman, prop. n.: An American statistician who invented random forests and bagging, decision-tree methods still in wide use, and urged statisticians to judge models by how well they predict., C4.5C4.5, prop. n.: A widely used 1990s program that learns decision trees and rule sets from data; unlike its predecessor, it trims away unhelpful branches, copes with gaps in the data and can split on measured numbers., ID3ID3, abbr.: An early, influential method for automatically building a decision tree from examples, choosing at each step the question that most reduces uncertainty about the answer., Jerome FriedmanJerome Friedman, prop. n.: An American statistician who invented gradient boosting, the method behind XGBoost and other leading tools for spreadsheet-style data, and co-wrote a standard machine-learning textbook., Ross QuinlanRoss Quinlan, prop. n.: An Australian computer scientist who created ID3 and C4.5, influential programs that learn decision trees, flowchart-like rules for classifying examples.