Rule Induction with CN2: Some Recent Improvements

By Peter Clark, Robin Boswell. 1991

Subfields: Knowledge Graphs & Representation, Algorithms & Complexity

How researchers see this paper

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

In Knowledge Graphs & Representation

In Algorithms & Complexity

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, methodology): “Associative classification methods assemble decision lists or decision sets from a set of pre-mined rules, generally either by greedily adding rules to the model one by one, or simply including all “top-scoring” rules into a decision set, where each rule is scored separately according to a scoring f”
How to See Hidden Patterns in Metamaterials with Interpretable Machine Learning (2021, background): “A decision set (e.g., [5, 10, 33, 17, 34]), is a logical model comprised of an unordered collection of rules, where each rule is a conjunction of conditions.”
Optimal Decision Lists using SAT (2020, methodology): “Decision lists were introduced by Rivest (1987) and heuristic methods for decision lists also date back to the late 80s (Clark and Niblett 1989; Clark and Boswell 1991).”
Computing Optimal Decision Sets with SAT (2020, methodology): “h rule). Note how rules can overlap, both the ﬁrst and third rule classify items 4 and 6. tu 3Related Work Interpretable decision sets are a rule-based predictive model that can be traced at least to [11,12]. To the best of our knowledge, the ﬁrst logic-based approach to the problem of decision set ”
Boolean Decision Rules via Column Generation (2018, background): “Predominant practical approaches include a covering or separate-and-conquer strategy ([15, 14, 16, 26, 28, 40],”
Interpretable Decision Sets: A Joint Framework for Description and Prediction (2016, neutral): “In contrast, previous work on learning rule sets [9] used simple heuristics to incrementally grow the set.”
CPAR: Classification based on Predictive Association Rules (2003, methodology): “We use the Laplace expected error estimate [2] to estimate the accuracy of rules, which is defined as follows.”
How do Humans Understand Explanations from Machine Learning Systems? An Evaluation of the Human-Interpretability of Explanation (2018, neutral): “Decision sets (also known as rule sets) also enjoy a long history of optimization techniques, ranging from Frank and Witten [1998], Cohen [1995], Clark and Boswell [1991] to Lakkaraju et al. [2016].”
Finding a short and accurate decision rule in disjunctive normal form by exhaustive search (2010, methodology): “The method used by CN2 to induce an unordered rule set can possibly be applied (Clark and Boswell 1991).”
STATLOG: COMPARISON OF CLASSIFICATION ALGORITHMS ON LARGE REAL-WORLD PROBLEMS (1995, background): “Many comparisons have been intra-subject comparisons, e.g., within symbolic learning Clark and Boswell, 1991, Sammut, 1988, Quinlan et al., 1986, Aha, 1992], within statistics Cherkaoui and Cleroux, 1991, Remme et al., 1980], and within neural networks Huang et al., 1991, Fahlman, 1991, Xu et al.,…”
Selecting the right objective measure for association analysis (2004, unknown): “Other variants of the confidence measure include the Laplace function [20] and conviction [21].”
Round Robin Classification (2002, methodology): “The name “unordered” originates from Clark and Boswell (1991), who proposed this approach as an alternative to the decision-list learning approach that was originally used in CN2 (Clark and Niblett, 1989; Rivest, 1987).”
Improving the interpretability of classification rules discovered by an ant colony algorithm (2013, methodology): “A simple example of this eﬀect was given by [1]: If feathers = yes then class = bird else if legs = two then class = human else ...”
Machine Learning for Information Extraction in Informal Domains (2000, methodology): “In order to meet this requirement, we look to the family of symbolic inductive learners, which includes decision tree learners, such as C4.5 (Quinlan, 1993), covering algorithms, such as AQ (Michalski, 1983) and CN2 (Clark & Boswell, 1991), and inductive logic programming (ILP) or relational learner”
Evaluation Measures for Multi-class Subgroup Discovery (2009, methodology): “CN2 is a rule induction algorithm that can be applied to propositional data sets for inducing classification rules [5, 6].”
Mining the optimal class association rule set (2002, background): “Clearly, a relational database can be mapped to a transaction database when an attribute and attribute value pair is considered as an item.”
Detection of malicious code by applying machine learning classifiers on static features: A state-of-the-art survey (2009, methodology): “The idea of Distribution Summation combining method is to sum up the conditional probability vector obtained from each classifier (Clark and Boswell, 1991).”
Scaling Up: Distributed Machine Learning with Cooperation (1996, methodology): “…accuracy estimate; the rule certainty factor used by Quinlan (1987) is a frequency-based accuracy estimate adjusted for small samples, and several rulelearning programs use the Laplace accuracy estimate (Clark & Boswell, 1991; Segal & Etzioni, 1994; Webb, 1995; Quinlan & Cameron-Jones, 1995).”
Separate-and-Conquer Rule Learning (1999, methodology): “However, it suffers from similar deficiencies as purity and information content and has later been replaced by the Laplace estimate (Clark and Boswell 1991).”