Skip to content
Last Dictionary
Plane
Machine LearningSymbolic & Classical AI

decision tree

nounAlso: classification tree, regression tree, decision tree learning, tree-based model, decision stump

In plain wordsA 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.

  1. 1

    Machine learning

    A predictive model that carves the input space into regions by a nested sequence of single-feature tests (for example, 'age < 40?'): an input starts at the root, follows the branch matching each answer, and receives the prediction stored where its path ends — a class or class distribution in classification trees, a constant such as the mean in regression trees. Trees are grown greedily from the top down: at each node the algorithm picks the split that most reduces an impurity measure such as 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., entropy (information gaininformation gain, n.: How much a question reduces uncertainty about the answer. A decision tree asks first the question that removes the most uncertainty, measured in bits.) or, for regression, variance, and growth is stopped early or prunedpruning, 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. afterward to limit overfittingoverfitting, n.: When a model learns its training examples too well — quirks and noise included — so it does great on data it has seen but poorly on anything new, like a student who memorizes answers without understanding.. Trees handle mixed feature types, need no feature scaling and are readable when small, but single trees are unstable and rarely the most accurate; their main modern role is as base learners in random forestsrandom 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. and 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.. Classic algorithms are 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. and CARTCART, abbr.: A 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 one-split tree is called a decision stump.

    A depth-3 decision tree was accurate enough, and the loan officers could read every rule.

  2. 2

    Decision analysis

    A hand-built diagram of sequential choices, chance events and outcomes, annotated with probabilities and payoffs, used to compare the expected value of alternative courses of action. This operations-research sense predates machine learning; the tree is drawn by analysts rather than learned from data.

Origin

Learned trees began with James Morgan and John Sonquist's AID program for regression on survey data (1963) and Earl Hunt, Janet Marin and Philip Stone's Concept Learning System (1966). Statistics and machine learning then developed the idea largely in parallel: CART (Leo Breiman, Jerome Friedman, Richard Olshen and Charles Stone, 1984) and J. Ross Quinlan's ID3 (1979–1986) and C4.5 (1993).

Usage note

Depth is the main complexity control: deep trees overfit, stumps underfit. Finding the optimal tree is NP-hard, which is why practical algorithms are greedy.

Related

See also
  • CARTCART, abbr.: A 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.
  • 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.
  • 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.
  • information gaininformation gain, n.: How much a question reduces uncertainty about the answer. A decision tree asks first the question that removes the most uncertainty, measured in bits.
  • 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.
  • 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.
  • 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.

Sources

  1. Morgan, J. N. & Sonquist, J. A. (1963). Problems in the Analysis of Survey Data, and a Proposal. Journal of the American Statistical Association, 58, 415–434.
  2. 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

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., machine learningmachine learning, n.: A way of building software that learns from examples instead of following rules written by a programmer. Shown thousands of labeled photos, for instance, a program can learn to recognize cats., modelmodel, n.: A simplified working version of something. In AI it usually means the trained program, a big set of learned numbers, that takes an input and produces an answer, prediction or piece of content., neural networkneural network, n.: A kind of computer program that learns a task from examples by tuning thousands to billions of connections between simple number-crunching units, an arrangement loosely inspired by nerve cells in the brain., training settraining set, n.: The examples a machine-learning model learns from, like the worked problems a student practices on, kept separate from the examples later used to check how well it learned., AdaBoostAdaBoost, prop. n.: One of the first practical boosting methods: it trains simple models in turn, giving extra weight to examples the earlier models got wrong, then lets all the models vote, weighted by accuracy., baggingbagging, n.: Training many copies of a model, each on a different random resample of the data, and averaging their predictions. The averaging cancels out much of each copy's random error., boostingboosting, n.: Building a strong predictor from many weak ones trained one after another, where each new model concentrates on the mistakes the previous ones made., CatBoostCatBoost, prop. n.: A free gradient-boosting library from the tech company Yandex, known for handling categories such as city names or product types directly, without first converting them into numbers by hand., decision boundarydecision boundary, n.: The dividing line, or surface, where a classifier switches from predicting one category to another. Simple models draw straight lines; flexible ones draw curves., entropyentropy, n.: A measure of unpredictability. A fair coin toss has more entropy than a rigged one; an AI that is unsure of its next word has high entropy., 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., 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., inductive biasinductive bias, n.: The assumptions built into a learning method that decide how it fills the gaps between the examples it was shown, such as that similar inputs get similar answers. Every learner needs some to cope with new cases., information gaininformation gain, n.: How much a question reduces uncertainty about the answer. A decision tree asks first the question that removes the most uncertainty, measured in bits., interpretable modelinterpretable model, n.: A model simple or structured enough that a person can follow exactly how it turns inputs into a decision — like a short checklist or a points-based score — with no separate explanation tool needed., isolation forestisolation forest, n.: A method for spotting unusual data points by repeatedly slicing the data at random: odd points get cut off from the rest after only a few slices, while ordinary points take many., 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., LightGBMLightGBM, prop. n.: A widely used tool for making predictions from very large tables of data, quickly and in little memory, by combining many small decision trees. Microsoft released it as free software in 2016., multiclass classificationmulticlass classification, n.: Sorting each item into exactly one of three or more categories — for example, deciding which of the ten digits a handwritten number shows., nonparametric modelnonparametric model, n.: A model that lets the data decide how complex it becomes: the more examples it gets, the more detail it can capture — for instance, one that predicts by comparing a new case with every stored example., 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., 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., rule-based systemrule-based system, n.: A computer system that makes decisions by following a list of 'if… then…' rules written by people, rather than by learning from examples.