C4.5
In plain wordsA 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.
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 system, successor to 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., that extends entropy-based induction to practical data. It chooses splits by gain ratio — 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. divided by the entropy of the split itself, which counters ID3's bias toward many-valued attributes — cuts numeric attributes at learned thresholds, and sends an example with a missing value down every branch with fractional weights. After growing the tree it prunes it with a pessimistic, confidence-based estimate of error computed on the training data, so no held-out set is needed, and it can convert trees into ordered rule sets. Its commercial successor C5.0 (See5 on Windows) added 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., misclassification costs and faster, smaller trees; the Weka toolkit's free Java version goes by the name J48.
As a quick interpretable baseline, we ran J48, Weka's version of C4.5, with default pruning.
Origin
Developed by J. Ross Quinlan and described in his book 'C4.5: Programs for Machine Learning' (Morgan Kaufmann, 1993). Among algorithms nominated and voted on at the 2006 IEEE International Conference on Data Mining, it was listed first in the resulting paper 'Top 10 Algorithms in Data Mining' (2008).
Related
- 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.
- 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.
- 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.
- 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.
- 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.
- 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. (1993). C4.5: Programs for Machine Learning. San Mateo, CA: Morgan Kaufmann.
- Wu, X., Kumar, V., Quinlan, J. R. et al. (2008). Top 10 Algorithms in Data Mining. Knowledge and Information Systems, 14, 1–37.
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., 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., 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.