Efficient strategies for tough aggregate constraint-based sequential pattern mining

E. Chen, H. Cao, Qing Li, T. Qian

Research output: Journal article publicationJournal articleAcademic researchpeer-review

33 Citations (Scopus)

Abstract

Frequent sequential pattern mining with constraints is the task of discovering patterns by incorporating the user defined constraints into the mining process, thus not only improving mining efficiency but also making the discovered patterns to better meet user requirements. Though many studies have been done, few have been carried out on the "tough aggregate constraints" due to the diffIculty of pushing the constraints into the mining process. In this paper we provide efficient strategies to deal with tough aggregate constraints. Through a theoretical analysis of the tough aggregate constraints based on the concept of total contribution of sequences, we first show that two typical kinds of constraints can be transformed into the same form and thus can be processed in a uniform way. We then propose a novel algorithm called PTAC (sequential frequent Patterns mining with Tough Aggregate Constraints) to reduce the cost of using tough aggregate constraints through incorporating two effective strategies. One avoids checking data items one by one by utilizing the features of promisingness exhibited by some other items and validity of the corresponding prefix. The other avoids constructing an unnecessary projected database through effectively pruning those unpromising new patterns that may, otherwise, serve as new prefixes. With these strategies, our algorithm obtains good performance in speed and space, as demonstrated by experimental studies conducted on the synthetic datasets generated by the IBM sequence generator, in addition to a real dataset. © 2007 Elsevier Inc. All rights reserved.
Original languageEnglish
Pages (from-to)1498-1518
Number of pages21
JournalInformation Sciences
Volume178
Issue number6
DOIs
Publication statusPublished - 15 Mar 2008
Externally publishedYes

Keywords

  • Frequent sequential pattern
  • Tough aggregate constraints

ASJC Scopus subject areas

  • Statistics and Probability
  • Electrical and Electronic Engineering
  • Statistics, Probability and Uncertainty
  • Information Systems and Management
  • Information Systems
  • Computer Science Applications
  • Artificial Intelligence

Cite this