ERMiner: Sequential rule mining using equivalence classes

Philippe Fournier-Viger*, Ted Gueniche, Souleymane Zida, Vincent Shin-Mu Tseng

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

22 Scopus citations

Abstract

Sequential rule mining is an important data mining task with wide applications. The current state-of-the-art algorithm (RuleGrowth) for this task relies on a pattern-growth approach to discover sequential rules. A drawback of this approach is that it repeatedly performs a costly database projection operation, which deteriorates performance for datasets containing dense or long sequences. In this paper, we address this issue by proposing an algorithm named ERMiner (Equivalence class based sequential Rule Miner) for mining sequential rules. It relies on the novel idea of searching using equivalence classes of rules having the same antecedent or consequent. Furthermore, it includes a data structure named SCM (Sparse Count Matrix) to prune the search space. An extensive experimental study with five real-life datasets shows that ERMiner is up to five times faster than RuleGrowth but consumes more memory.

Original languageEnglish
Title of host publicationAdvances in Intelligent DataAnalysis XIII - 13th International Symposium, IDA 2014, Proceedings
EditorsHendrik Blockeel, Matthijs van Leeuwen, Veronica Vinciotti
PublisherSpringer Verlag
Pages108-119
Number of pages12
ISBN (Electronic)9783319125701
DOIs
StatePublished - 1 Jan 2014
EventPAKDD 2006 International Workshop on Knowledge Discovery in Life Science Literature, KDLL 2006 - Singapore, Singapore
Duration: 9 Apr 20069 Apr 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8819
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferencePAKDD 2006 International Workshop on Knowledge Discovery in Life Science Literature, KDLL 2006
CountrySingapore
CitySingapore
Period9/04/069/04/06

Keywords

  • Equivalence classes
  • Sequential rule mining
  • Sparse count matrix
  • Vertical database format

Fingerprint Dive into the research topics of 'ERMiner: Sequential rule mining using equivalence classes'. Together they form a unique fingerprint.

Cite this