Selection of High Quality Rules in Associative Classification

Selection of High Quality Rules in Associative Classification

Silvia Chiusano (Politecnico di Torino, Italy) and Paolo Garza (Politecnico di Torino, Italy)
DOI: 10.4018/978-1-60566-404-0.ch010
OnDemand PDF Download:


In this chapter the authors make a comparative study of five well-known classification rule pruning methods with the aim of understanding their theoretical foundations and their impact on classification accuracy, percentage of pruned rules, model size, and number of wrongly and not classified data. Moreover, they analyze the characteristics of both the selected and pruned rule sets in terms of information content. A large set of experiments has been run in order to empirically evaluate the effect of the pruning methods when applied individually as well as when combined.
Chapter Preview


Given a set of labeled data objects, denoted as training data set, classification rule mining aims at discovering a small set of rules to form a model, the classifier, which is then used to classify new data with unknown class label (Quinlan, 1993). The classification accuracy is evaluated on a different data set, the test data set.

Recently, associative classification methods have been proposed, which exploit association rule mining techniques to generate classification models for structured data (Arunasalam & Chawla, 2006; Baralis & Paolo, 2002; Baralis, Chiusano, & Garza, 2008; Dong, Zhang, Wong, & Li, 1999; Li, Han, & Pei, 2001; Liu, Hsu, & Ma, 1998; Liu, Ma, & Wong, 2000; Thabtah, Cowling, & Peng, 2004; Wang & Karypis, 2005; Wang, Zhou, & He, 2000; Yin & Han, 2003). Associative classification generates highly accurate classifiers, since, differently from decision trees (Quinlan, 1993), it considers the simultaneous correspondence of values of different attributes.

The generation of an associative classifier usually consists of two steps. First, a large set of classification rules is extracted from the training data to allow a wide selection of rules and the generation of accurate classifiers. Then, pruning techniques are applied to select a small subset of high quality rules and build an accurate model of the training data.

Similarly to decision tree based approaches, associative classification exploits pruning techniques (a) to deal with the problem of combinatorial explosion of the solution set and (b) to improve the accuracy in classification. While a pruning technique in case (a) aims at reducing the size of the rule set without affecting its accuracy, in case (b) pruning aims at removing those rules that can decrease classification accuracy, because introducing noise and overfitting.

So far, associative classification mainly exploited ad hoc versions of pruning methods previously proposed in decision tree based classification (Esposito, Malerba, & Semeraro, 1997) or high quality measures proposed for association rule selection (Tan, Kumar, & Srivastava, 2002). Significant improvements in classification accuracy have been obtained by slight modifications of the same pruning methods, and different combinations of them (Arunasalam & Chawla, 2006; Baralis & Paolo, 2002; Baralis, Chiusano, & Garza, 2008; Dong, Zhang, Wong, & Li, 1999; Li, Han, & Pei, 2001; Liu, Hsu, & Ma, 1998; Liu, Ma, & Wong, 2000; Thabtah, Cowling, & Peng, 2004; Wang & Karypis, 2005; Wang, Zhou, & He, 2000; Yin & Han, 2003). However, to the best of our knowledge, the specific contribution of the different techniques has never been investigated. Thabtah (2007) surveys the existing associative classification methods and the pruning techniques used by them. Differently from (Thabtah, 2007), this chapter focuses on the pruning methods used in associative classification, and deeply investigates their theoretical properties and experimentally evaluates their effects. Because of the increasing relevance of associative classification, we believe that a systematic and experimental analysis of the effects of rule pruning in this context can be beneficial. A similar analysis concerning the effects of pruning in decision tree based classification was presented in (Esposito, Malerba, & Semeraro, 1997).

Complete Chapter List

Search this Book:
Editorial Advisory Board
Table of Contents
David Bell
Yanchang Zhao, Chengqi Zhang, Longbing Cao
Chapter 1
Paul D. McNicholas, Yanchang Zhao
Association rules present one of the most versatile techniques for the analysis of binary data, with applications in areas as diverse as retail... Sample PDF
Association Rules: An Overview
Chapter 2
Mirko Boettcher, Georg Ruß, Detlef Nauck, Rudolf Kruse
Association rule mining typically produces large numbers of rules, thereby creating a second-order data mining problem: which of the generated rules... Sample PDF
From Change Mining to Relevance Feedback: A Unified View on Assessing Rule Interestingness
Chapter 3
Solange Oliveira Rezende, Edson Augusto Melanda, Magaly Lika Fujimoto, Roberta Akemi Sinoara, Veronica Oliveira de Carvalho
Association rule mining is a data mining task that is applied in several real problems. However, due to the huge number of association rules that... Sample PDF
Combining Data-Driven and User-Driven Evaluation Measures to Identify Interesting Rules
Chapter 4
Julien Blanchard, Fabrice Guillet, Pascale Kuntz
Assessing rules with interestingness measures is the cornerstone of successful applications of association rule discovery. However, as numerous... Sample PDF
Semantics-Based Classification of Rule Interestingness Measures
Chapter 5
Huawen Liu, Jigui Sun, Huijie Zhang
In data mining, rule management is getting more and more important. Usually, a large number of rules will be induced from large databases in many... Sample PDF
Post-Processing for Rule Reduction Using Closed Set
Chapter 6
Hacène Cherfi, Amedeo Napoli, Yannick Toussaint
A text mining process using association rules generates a very large number of rules. According to experts of the domain, most of these rules... Sample PDF
A Conformity Measure Using Background Knowledge for Association Rules: Application to Text Mining
Chapter 7
Hetal Thakkar, Barzan Mozafari, Carlo Zaniolo
The real-time (or just-on-time) requirement associated with online association rule mining implies the need to expedite the analysis and validation... Sample PDF
Continuous Post-Mining of Association Rules in a Data Stream Management System
Chapter 8
Ronaldo Cristiano Prati
Receiver Operating Characteristics (ROC) graph is a popular way of assessing the performance of classification rules. However, as such graphs are... Sample PDF
QROC: A Variation of ROC Space to Analyze Item Set Costs/Benefits in Association Rules
Chapter 9
Maria-Luiza Antonie, David Chodos, Osmar Zaïane
The chapter introduces the associative classifier, a classification model based on association rules, and describes the three phases of the model... Sample PDF
Variations on Associative Classifiers and Classification Results Analyses
Chapter 10
Silvia Chiusano, Paolo Garza
In this chapter the authors make a comparative study of five well-known classification rule pruning methods with the aim of understanding their... Sample PDF
Selection of High Quality Rules in Associative Classification
Chapter 11
Sadok Ben Yahia, Olivier Couturier, Tarek Hamrouni, Engelbert Mephu Nguifo
Providing efficient and easy-to-use graphical tools to users is a promising challenge of data mining, especially in the case of association rules.... Sample PDF
Meta-Knowledge Based Approach for an Interactive Visualization of Large Amounts of Association Rules
Chapter 12
Claudio Haruo Yamamoto, Maria Cristina Ferreira de Oliveira, Solange Oliveira Rezende
Miners face many challenges when dealing with association rule mining tasks, such as defining proper parameters for the algorithm, handling sets of... Sample PDF
Visualization to Assist the Generation and Exploration of Association Rules
Chapter 13
Nicolas Pasquier
After more than one decade of researches on association rule mining, efficient and scalable techniques for the discovery of relevant association... Sample PDF
Frequent Closed Itemsets Based Condensed Representations for Association Rules
Chapter 14
Mengling Feng, Jinyan Li, Guozhu Dong, Limsoon Wong
This chapter surveys the maintenance of frequent patterns in transaction datasets. It is written to be accessible to researchers familiar with the... Sample PDF
Maintenance of Frequent Patterns: A Survey
Chapter 15
Guozhu Dong, Jinyan Li, Guimei Liu, Limsoon Wong
This chapter considers the problem of “conditional contrast pattern mining.” It is related to contrast mining, where one considers the mining of... Sample PDF
Mining Conditional Contrast Patterns
Chapter 16
Qinrong Feng, Duoqian Miao, Ruizhi Wang
Decision rules mining is an important technique in machine learning and data mining, it has been studied intensively during the past few years.... Sample PDF
Multidimensional Model-Based Decision Rules Mining
About the Contributors