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

Introduction

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: