Continuous Post-Mining of Association Rules in a Data Stream Management System

Continuous Post-Mining of Association Rules in a Data Stream Management System

Hetal Thakkar (University of California-Los Angeles, USA), Barzan Mozafari (University of California-Los Angeles, USA) and Carlo Zaniolo (University of California-Los Angeles, USA)
DOI: 10.4018/978-1-60566-404-0.ch007
OnDemand PDF Download:


The real-time (or just-on-time) requirement associated with online association rule mining implies the need to expedite the analysis and validation of the many candidate rules, which are typically created from the discovered frequent patterns. Moreover, the mining process, from data cleaning to post-mining, can no longer be structured as a sequence of steps performed by the analyst, but must be streamlined into a workflow supported by an efficient system providing quality of service guarantees that are expected from modern Data Stream Management Systems (DSMSs). This chapter describes the architecture and techniques used to achieve this advanced functionality in the Stream Mill Miner (SMM) prototype, an SQL-based DSMS designed to support continuous mining queries.
Chapter Preview


Driven by the need to support a variety of applications, such as click stream analysis, intrusion detection, and web-purchase recommendation systems, much of recent research work has focused on the difficult problem of mining data streams for association rules. The paramount concern in previous works was how to devise frequent itemset algorithms that are fast and light enough for mining massive data streams continuously with real-time or quasi real-time response (Jiang, 2006). The problem of post-mining the association rules, so derived from the data streams, has so far received much less attention, although it is rich in practical importance and research challenges. Indeed, the challenge of validating the large number of generated rules is even harder in the time-constrained environment of on-line data mining, than it is in the traditional off-line environment. On the other hand, data stream mining is by nature a continuous and incremental process, which makes it possible to apply application-specific knowledge and meta-knowledge acquired in the past, to accelerate the search for new rules. Therefore, previous post-mining results can be used to prune and expedite both (i) the current search for new frequent patterns and (ii) the post processing of the candidate rules thus derived. These considerations have motivated the introduction of efficient and tightly-coupled primitives for mining and post-mining association rules in Stream Mill Miner (SMM), a DSMS designed for mining applications (Thakkar, 2008). SMM is the first of its kind and thus must address a full gamut of interrelated challenges pertaining to (i) functionality, (ii) performance, and (iii) usability. Toward that goal, SMM supports

  • A rich library of mining methods and operators that are fast and light enough to be used for online mining of massive and often bursty data streams,

  • The management of the complete DM process as a workflow, which (i) begins with the preprocessing of data (e.g., cleaning and normalization), (ii) continues with the core mining task (e.g., frequent pattern extraction), and (iii) completes with post-mining tasks for rule extraction, validation, and historical preservation.

  • Usability based on high-level, user-friendly interfaces, but also customizability and extensibility to meet the specific demands of different classes of users.

Performing these tasks efficiently on data streams has proven difficult for all mining methods, but particularly so, for association rule mining. Indeed, in many applications, such as click stream analysis and intrusion detection, time is of the essence, and new rules must be promptly deployed, while current ones must be revised in a timely manner to adapt to concept shifts and drifts. However, many of the generated rules are either trivial or nonsensical, and thus validation by the analyst is required, before they can be applied in the field. While this human validation step cannot be completely skipped, it can be greatly expedited by the approach taken in SMM where the bulk of the candidate rules are filtered out by the system, so that only a few highly prioritized rules are sent to analyst for validation. Figure 1 shows the architecture used in SMM to support the rule mining and post-mining process.

Figure 1.

Post-mining flow

As shown in Figure 1, the first step consists in mining the data streams for frequent itemsets using an algorithm called SWIM (Mozafari, 2008) that incrementally mines the data stream partitioned into slides. As shown in Figure 1, SWIM can be directed by the analyst to (i) accept/reject interesting and uninteresting items, and (ii) monitor particular patterns of interest while avoiding the generation of others. Once SWIM generates these frequent patterns, a Rule Extractor module derives interesting association rules based on these patterns. Furthermore, SMM supports the following customization options to expedite the process:

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