C4.5: Programs for Machine Learning

By J. Ross Quinlan. 1992

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, methodology): “…tree optimization is known to be an NP-complete problem (Laurent and Rivest, 1976), and heuristic greedy splitting and pruning procedures have been the major type of approach since the 1980s to grow decision trees (Breiman et al., 1984; Quinlan, 1993; Loh and Shih, 1997; Mehta et al., 1996).”
Hacking smart machines with smarter ones: How to extract meaningful data from machine learning classifiers (2013, background): “5 [52] algorithm, which is an extended version of the ID 3 algorithm [51]. top-down, greedy search through the space of all possible decision trees.”
Please Stop Explaining Black Box Models for High Stakes Decisions (2018, background): “…or uninterpretable because they do not choose a globally best choice (or approximately best choice) for the logical conditions [C4.5 and CART decision trees are an example, Quinlan, 1993, Breiman et al., 1984, as well as a vast number of models from the associative classification literature].”
Learning Optimal Decision Trees with SAT (2018, background): “Decision trees have been actively investigated since the early 80s [Breiman et al. , 1984; Quinlan, 1986; Quinlan, 1993; Mitchell, 1997; Cockett and Hierrera, 1990], and ﬁnd important practical applications in a wide range of domains, including ML and DM [Quinlan, 1993; Murthy, 1998; Rokach and…”
A Survey of Methods for Explaining Black Box Models (2018, neutral): “Each branch represents a possible outcome [92].”
Auditing black-box models for indirect influence (2016, background): “The classic example of such models are decision trees [19], while recently supersparse linear integer models (SLIMs) have been developed as an alternative interpretable model for classiﬁcation [26].”
Learning Certifiably Optimal Rule Lists (2017, methodology): “Constructing rule lists, or more generally, decision trees, has been a challenge for more than 30 years; most approaches use greedy splitting techniques (Rivest, 1987; Breiman et al., 1984; Quinlan, 1993).”
Interpretable classification models for recidivism prediction (2015, background): “0 is an updated version of the popular C4.5 algorithm (Quinlan 2014, Kuhn and Johnson 2013) that can create decision trees and rule sets.”
Mathematical optimization in classification and regression trees (2021, methodology): “These are recursive partitioning methods that build the tree model in a forward stepwise search implementing orthogonal cuts, yielding binary trees, e.g., CART (Breiman et al. 1984) and QUEST (Loh and Shih 1997), or nonbinary trees, a.k.a. multi-way trees (Kim and Loh 2001), e.g., CHAID (Kass 1980) ”
Computing Optimal Decision Sets with SAT (2020, background): “an error of 1.) The objective of classiﬁcation in machine learning is to devise a function ˚^ that matches the actual function ˚on the training data Eand generalizes suitably well on unseen test data [19,25,40,47]. In many settings (including sparse decision sets), function ˚^ is not required to mat”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “Examples of these algorithms include CART, originally proposed by Breiman et al. (1984), and C4.5 by Quinlan (1993).”
Learning Optimal Decision Trees with MaxSAT and its Integration in AdaBoost (2020, methodology): “The most widely used techniques for computing decision trees (e.g. CART [Breiman et al. , 1984], ID3 [Quinlan, 1986] and C4.5 [Quinlan, 1993]) are greedy heuristics, typically build trees from top to bottom selecting the feature yielding the highest information gain.”
Generalized and Scalable Optimal Sparse Decision Trees (2020, methodology): “The major approach since the 1980’s has been decision tree induction, where heuristic splitting and pruning procedures grow a tree from the top down and prune it back afterwards (Quinlan, 1993; Breiman et al., 1984).”
Learning Optimal Decision Trees Using Caching Branch-and-Bound Search (2020, background): “5 (Quinlan 1993), are greedy in nature: they grow the decision tree top-down, iteratively splitting the data into subsets.”
Learning Optimal Classification Trees: Strong Max-Flow Formulations (2020, methodology): “For example, CART uses the Gini Index to decide on the splitting, see Breiman (1984); ID3 employs entropy, see Quinlan (1986); and C4.5 leverages normalized information gain, see Quinlan (2014).”
Optimal Decision Trees for the Algorithm Selection Problem: Integer Programming Based Approaches (2019, methodology): “ew instances. The production of compact and accurate decision trees is an NP-Hard problem (Hyal and Rivest, 1976). Thus, many greedy heuristics have been proposed, such as ID3 (Quinlan, 1986), C4.5 (Quinlan, 1993) and CART (Breiman et al., 1984). These heuristics recursively analyze each split in is”
Optimal Sparse Decision Trees (2019, methodology): “5 [19] decision tree algorithms (and other greedy tree-growing variants) have remained as dominant methods in practice for decision trees.”
IMLI: An Incremental Framework for MaxSAT-Based Learning of Interpretable Classification Rules (2019, background): “The study of designing interpretable machine learning clas-siﬁers can ﬁnd its root in the development of popular models such as decision trees (Bessiere, Hebrard, and OSullivan 2009; Quinlan 2014), decision lists (Rivest 1987), classiﬁ-cation rules (Cohen 1995) etc.”