ID3
In plain wordsAn early, influential method for automatically building a decision tree from examples, choosing at each step the question that most reduces uncertainty about the answer.
A 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. learning algorithm that builds a tree top-down, at each node selecting the categorical attribute with the highest 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. — the largest expected reduction in the 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. of the class labels — and creating one branch per attribute value, recursing until the examples at a node share a class or no attributes remain. It handles only categorical attributes, does not prune (so it overfits noisy data) and favors attributes with many values. To cope with training sets too large for memory, the original version induced a tree from a subset, or 'window', of examples and repeatedly added the examples it misclassified. Its successor 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. removed most of these limitations; ID3 remains the standard teaching example of greedy, entropy-based tree induction.
In the lab you will implement ID3 by hand on the classic play-tennis weather data.
Origin
Developed by J. Ross Quinlan in the late 1970s from Earl Hunt's Concept Learning System, prompted by a chess task posed by Donald Michie: deciding whether King–Rook versus King–Knight endgame positions are lost. First published in 1979 and described definitively in 'Induction of Decision Trees' (Machine Learning, 1986); the information-based selection criterion followed a suggestion of Peter Gács.
Usage note
Despite 'Dichotomiser' in its usual expansion, ID3 makes one branch per attribute value rather than only two-way splits. Quinlan's 1986 paper does not spell out the acronym.
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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
Sources
- Quinlan, J. R. (1986). Induction of Decision Trees. Machine Learning, 1, 81–106. rd.springer.com/article/10.1007/BF00116251
- Quinlan, J. R. (1979). Discovering Rules by Induction from Large Collections of Examples. In D. Michie (ed.), Expert Systems in the Micro-electronic Age. Edinburgh University Press.
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., 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., 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., 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., Donald MichieDonald Michie, prop. n.: A British codebreaker turned AI pioneer who built a game-playing learning machine out of matchboxes and founded Edinburgh's influential machine-intelligence research group., 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.