Learn rules from data

Status

Variants

Learn if-then rules

Learn a set of if-then rules that predict a label, directly or from a trained tree.

Discover unusual subgroups

Search for rules that describe large subgroups whose label distribution is statistically unusual.

What other tools call it

Meridian's classification; an independent blind rating agreed on 86.2% of 312 rows (exact class, version 2).

Background

When to use it

Decision rules are probably the most interpretable prediction models, provided their conditions use intelligible features, stay short and there are not too many rules.^[2] Reach for rule learning when the people who act on a model need to read it, check it against what they know and argue with it, rather than only use its predictions. (Meridian's view) The support, or coverage, of a rule is the share of rows its condition applies to, whatever the rule predicts.^[2] The accuracy, or confidence, of a rule is how often it predicts the correct class among the rows its condition applies to.^[2] A rule usually trades accuracy against support: adding conditions to it can raise its accuracy but loses support.^[2] Read a rule's support beside its accuracy, because a rule that is right every time about a handful of rows says little about the table. (Meridian's view)

The research and literature on IF-THEN rules focus on classification and almost completely neglect regression.^[2] A continuous target can be cut into intervals to turn regression into classification, but information is always lost.^[2] Rule learners often need categorical features, so numeric features have to be cut into intervals, and how to cut them has no clear answer.^[2] In RapidMiner's tutorial for its Rule Induction operator, numerical attributes are first converted to nominal ones, because rule learners usually perform well on nominal attributes.^[5] Choose the bins for a numeric column deliberately and say what they are, since the thresholds in every learned rule are only as meaningful as those bins. (Meridian's view)

Decision rules are bad at describing linear relationships between features and the outcome, because they can only produce step-like prediction functions.^[2]

Many of the older rule-learning algorithms are prone to overfitting.^[2] The single-feature learner OneR (One Rule) can overfit on features with many levels, so its choice of feature should be judged on a separate validation set.^[2] Hold out rows the rules were not learned from and measure them there, however simple the rule set looks. (Meridian's view)

Subgroup discovery is usually seen as different from classification, because it seeks interesting population subgroups rather than the most accurate rule set.^[3][4] In subgroup discovery one can often tolerate many more false positives, negative examples wrongly classed as positive, than in a classification task.^[3] Learn if-then rules when the question is what label a new row will get; look for unusual subgroups when the question is which kinds of rows carry the label unusually often. (Meridian's view)

The method

A decision list orders its rules and returns the prediction of the first rule whose condition applies.^[2] A decision set leaves its rules unordered, so its rules are either mutually exclusive or conflicts are resolved by a strategy such as majority voting.^[2] A default rule applies when no other rule does, and often predicts the most frequent class of the rows the other rules leave uncovered.^[2]

Sequential covering learns one rule, removes all the rows it covers, and repeats on the remaining rows until none are left or another stop condition is met.^[2] Repeated learning of a rule and removal of the rows it covers is called separate-and-conquer, and many rule-learning algorithms belong to the sequential covering family.^[2] For more than two classes, sequential covering orders the classes by increasing prevalence, starts with the least common, and makes the last class the default rule.^[2]

Repeated Incremental Pruning to Produce Error Reduction (RIPPER) is a propositional rule learner proposed by William W. Cohen.^[6][2] Cohen described RIPPER in the paper Fast Effective Rule Induction, in Machine Learning Proceedings 1995.^[2] RIPPER is a variant of sequential covering that adds a post-processing phase of rule pruning, and can produce either a decision list or a decision set.^[2] RapidMiner's Rule Induction operator works similarly to RIPPER, growing and pruning rules starting with the less prevalent classes.^[5] In the growing phase of RapidMiner's Rule Induction, conditions are added to a rule greedily until it is 100% accurate, choosing the condition with the highest information gain.^[5] In the pruning phase of RapidMiner's Rule Induction, any final sequence of a rule's antecedents may be pruned.^[5]

The OneR algorithm, from Holte in 1993, selects the single feature that carries the most information about the outcome and makes its rules from that feature.^[2] OneR makes one rule per value of the chosen feature, each predicting the most frequent class among the rows with that value.^[2]

In RapidMiner, the Tree to Rules operator trains a decision tree with an inner tree learner and determines a set of rules from that tree.^[7] In KNIME, the Fuzzy Rule Learner learns rules from labelled numeric data, each rule holding one fuzzy interval for each numeric column, using Mixed Fuzzy Rule Formation.^[8]

Subgroup discovery was first formulated by Klösgen in 1996 and by Wrobel in 1997 and 2001, and addressed by their rule learners EXPLORA and MIDOS.^[3] Given a population and a property of interest, subgroup discovery looks for subgroups that are as large as possible and most unusual in their distribution of that property.^[3][4] In subgroup discovery, a rule predicts the class of interest from a condition that is a conjunction of attribute-value pairs.^[3][4] Weighted relative accuracy (WRAcc) scores a rule by the relative size of its subgroup times the difference between the rule's accuracy and the default accuracy of its class.^[3] Under WRAcc, a rule is interesting only if it improves on the default accuracy of the rule that assigns every row to the class.^[3] CN2 is an algorithm for inducing propositional classification rules, described by Clark and Niblett in 1989 and by Clark and Boswell in 1991.^[3]

Compared with the alternatives

Decision rules can be as expressive as decision trees while being more compact, since trees often suffer from replicated sub-trees.^[2] A OneR model is a decision tree with only one split, though the split need not be binary.^[2] Fit a one-feature rule first as a baseline, so a longer rule set or a tree has to earn its extra complexity. (Meridian's view)

Classification rule learning is predictive induction, building rules for prediction, while association rule learning is descriptive induction, finding individual interesting patterns.^[3][4] Subgroup discovery sits at the intersection of predictive and descriptive induction.^[3][4] Agrawal, Imieliński and Swami introduced association rules for discovering regularities between products in large-scale transaction data from point-of-sale systems.^[9]

Sources

1. [1]Rule induction - Wikipediasecondary source
2. [2]10 Decision Rules – Interpretable Machine Learningsecondary source
3. [3]Subgroup Discovery with CN2-SDsecondary source
4. [4]Subgroup Discovery - Rapidminer Documentationdocumentation
5. [5]Rule Induction - Rapidminer Documentationdocumentation
6. [6]Rule-based machine learning - Wikipediasecondary source
7. [7]Tree to Rules - Rapidminer Documentationdocumentation
8. [8]Fuzzy Rule Learnerdocumentation
9. [9]Association rule learning - Wikipediasecondary source