CPAR: Classification based on Predictive Association Rules

By Xiaoxin Yin, Jiawei Han. 2003

1,001 citations recorded by the source corpus.

Recent studies in data mining have proposed a new classification approach, called associative classification, which, according to several reports, such as [7, 6], achieves higher classification accuracy than traditional classification approaches such as C4.5. However, the approach also suffers from two major deficiencies: (1) it generates a very large number of association rules, which leads to high processing overhead; and (2) its confidence-based rule evaluation measure may lead to overfitting. In comparison with associative classification, traditional rule-based classifiers, such as C4.5, FOIL and RIPPER, are substantially faster but their accuracy, in most cases, may not be as high. In this paper, we propose a new classification approach, CPAR (Classification based on Predictive Association Rules), which combines the advantages of both associative classification and traditional rule-based classification. Instead of generating a large number of candidate rules as in associative classification, CPAR adopts a greedy algorithm to generate rules directly from training data. Moreover, CPAR generates and tests more rules than traditional rule-based classifiers to avoid missing important rules. To avoid overfitting, CPAR uses expected accuracy to evaluate each rule and uses the best k rules in prediction.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems, 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 Artificial Intelligence

In Computational Theory and Mathematics

In Information Systems

In Algorithms & Complexity

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, methodology): “…set, where each rule is scored separately according to a scoring function (Rivest, 1987; Clark and Niblett, 1989; Liu et al., 1998; Li et al., 2001; Yin and Han, 2003; Sokolova et al., 2003; Marchand and Sokolova, 2005; Vanhoof and Depaire, 2010; Rudin et al., 2013; Clark and Boswell, 1991;…”
Learning Certifiably Optimal Rule Lists (2017, background): “In associative classiﬁcation (Vanhoof and Depaire, 2010; Liu et al., 1998; Li et al., 2001; Yin and Han, 2003), classiﬁers are often formed greedily from the top down as rule lists, or they are formed by taking the simple union of pre-mined rules, whereby any observation that ﬁts into any of the…”
Learning customized and optimized lists of rules with mathematical programming (2018, background): “[38], Yin and Han [74], Friedman and Popescu [23], Meinshausen [45].”
Boolean Decision Rules via Column Generation (2018, background): “see also the survey [30]) of learning rules one by one and removing “covered” examples, a bottomup strategy of combining more specific rules into more general ones [45, 22, 41], and associative classification in which association rule mining is followed by rule selection using various criteria [38, ”
Interpretable Decision Sets: A Joint Framework for Description and Prediction (2016, background): “The resulting ordered rules are instances of decision lists [10, 11, 13, 45, 52, 56].”
Scalable Bayesian Rule Lists (2016, neutral): “…2005; Marchand & Sokolova, 2005; Rudin, Letham, & Madigan, 2013; Goessling & Kang, 2015), associative classiﬁcation (Vanhoof & Depaire, 2010; Liu et al., 1998; Li, Han, & Pei, 2001; Yin & Han, 2003) and its Bayesian counterparts (McCormick, Rudin, & Madigan, 2012) all fall into this category.”
Learning Optimized Or's of And's (2015, methodology): “…Lavrac and Dzeroski, 1994), the associative classification algorithms (Ma, Liu, and Hsu, 1998; Han, Pei, and Yin, 2000; Li, Han, and Pei, 2001; Yin and Han, 2003; Chen et al., 2006; Cheng et al., 2007), and rule induction methods (e.g., Cohen, 1995), there has been little in the way of…”
Finding a short and accurate decision rule in disjunctive normal form by exhaustive search (2010, methodology): “, association rules whose right-hand-side is restricted to the class attribute (Yin and Han 2003; Liu et al. 1998).”
Directional decision lists (2015, methodology): “We end with an experiment on real data from a manufacturing process and determine indicators for problem cases.”
Frequent pattern mining: current status and future directions (2007, methodology): “Frequent itemsets have been demonstrated to be useful for classiﬁcation, where association rules are generated and analyzed for use in classiﬁcation (Liu et al. 1998; Dong and Li 1999; Li et al. 2000; Li et al. 2001; Yin and Han 2003; Cong et al. 2005;Wang and Karypis 2005).”
On The Stability of Interpretable Models (2018, methodology): “In this work, we consider the FOIL (First Order Inductive Learner) [23] and CPAR (Classification based on Predictive Association Rules) [24] algorithms, as implemented by the LUCS-KDD library5.”
A Bayesian Framework for Learning Rule Sets for Interpretable Classification (2017, methodology): “Associative classification and rule learning methods (e.g., Ma et al., 1998; Li et al., 2001; Yin and Han, 2003; Chen et al., 2006; Cheng et al., 2007; McCormick et al., 2012; Rudin et al., 2013; Dong et al., 1999; Michalski, 1969; Clark and Niblett, 1989; Frank and Witten, 1998) mine for frequent…”
Krimp: mining itemsets that compress (2011, background): “We also looked at the performance of FOIL, PRM and CPAR (Quinlan 1993b; Yin and Han 2003) reported in Coenen (2004).”
Learning theory analysis for association rules and sequential event prediction (2013, methodology): “Usually decision lists are formed the same way as decision trees are formed, which is by greedily splitting on each nodes to form the tree, and then pruning (as in for instance, Li et al., 2001; Yin and Han, 2003; Simon et al., 2011; Marchand and Sokolova, 2005).”