From Change Mining to Relevance Feedback: A Unified View on Assessing Rule Interestingness

From Change Mining to Relevance Feedback: A Unified View on Assessing Rule Interestingness

Mirko Boettcher (University of Magdeburg, Germany), Georg Ruß (University of Magdeburg, Germany), Detlef Nauck (BT Group plc, UK) and Rudolf Kruse (University of Magdeburg, Germany)
DOI: 10.4018/978-1-60566-404-0.ch002
OnDemand PDF Download:
$37.50

Abstract

Association rule mining typically produces large numbers of rules, thereby creating a second-order data mining problem: which of the generated rules are the most interesting? And: should interestingness be measured objectively or subjectively? To tackle the amount of rules that are created during the mining step, the authors propose the combination of two novel ideas: first, there is rule change mining, which is a novel extension to standard association rule mining which generates potentially interesting time-dependent features for an association rule. It does not require changes in the existing rule mining algorithms and can therefore be applied during post-mining of association rules. Second, the authors make use of the existing textual description of a rule and those newly derived objective features and combine them with a novel approach towards subjective interestingness by using relevance feedback methods from information retrieval. The combination of these two new approaches yields a powerful, intuitive way of exploring the typically vast set of association rules. It is able to combine objective and subjective measures of interestingness and will incorporate user feedback. Hence, it increases the probability of finding the most interesting rules given a large set of association rules.
Chapter Preview
Top

Introduction

Nowadays, the discovery of association rules is a relatively mature and well-researched topic. Many algorithms have been proposed to ever faster discover and maintain association rules. However, one of the biggest problems of association rules still remains unresolved. Usually, the number of discovered associations will be immense, easily in the thousands or even tens of thousands. Clearly, the large numbers make rules difficult to examine by a user. Moreover, many of the discovered rules will be obvious, already known, or not relevant.

For this reason a considerable amount of methods have been proposed to assist a user in detecting the most interesting or relevant ones. Studies about interestingness measures can roughly be divided into two classes: objective and subjective measures. Objective (data-driven) measures are usually derived from statistics, information theory or machine learning and assess numerical or structural properties of a rule and the data to produce a ranking. In contrast to objective measures, subjective (user-driven) measures incorporate a user’s background knowledge and mostly rank rules based on some notion of actionability and unexpectedness.

In spite of a multitude of available publications the problem of interestingness assessment still is regarded as one of the unsolved problems in data mining and still experiencing slow progress (Piatetsky-Shapiro, 2000). The search for a general solution is one of the big challenges of today’s data mining research (Fayyad et al., 2003). Existing approaches for interestingness assessment have several shortcomings which render them inadequate for many real-world applications.

Nonetheless, objective and subjective measures both have their justification to be used within the process of interestingness assessment. Objective measures help a user to get a first impression at what has been discovered and to obtain a starting point for further exploration of the rule set. This exploration step can then be accomplished by methods for subjective interestingness assessment. Ideally, the interestingness assessment of association rules should therefore be seen as a two step process. It is clear that for this process to be optimal it is necessary that both, the calculus used for the objective and the subjective rating, are based on the same notion of interestingness. Nevertheless, most approaches for objective and subjective ratings have been developed independently from each other with no interaction in mind such that the information utilized for the objective is neglected for the subjective rating. In fact, approaches rarely do fit together.

In this article we discuss a framework which combines objective and subjective interestingness measures to a powerful tool for interestingness assessment and addresses the problems mentioned above. Our framework incorporates several concepts which only recently have been introduced to the area of interestingness assessment: rule change mining and user dynamics. In particular, we show how to analyse association rules for changes and how information about change can be used to derive meaningful and interpretable objective interestingness measures. Based on the notion of change, we discuss a novel relevance feedback approach for association rules. We relate the problem of subjective interestingness to the field of Information Retrieval where relevance estimation is a rather mature and well-researched field. By using a vector-based representation of rules and by utilizing concepts from information retrieval we provide the necessary tool set to incorporate the knowledge about change into the relevance feedback process.

Complete Chapter List

Search this Book:
Reset
Editorial Advisory Board
Table of Contents
Foreword
David Bell
Acknowledgment
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
$37.50
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
$37.50
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
$37.50
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
$37.50
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
$37.50
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
$37.50
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
$37.50
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
$37.50
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
$37.50
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
$37.50
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
$37.50
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
$37.50
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
$37.50
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
$37.50
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
$37.50
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
$37.50
About the Contributors