Skip to Main content Skip to Navigation
Journal articles

NegPSpan: efficient extraction of negative sequential patterns with embedding constraints

Thomas Guyet 1, 2 • René Quiniou 2
2 LACODAM - Large Scale Collaborative Data Mining
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : Mining frequent sequential patterns consists in extracting recurrent behaviors, modeled as subsequences, in a big sequence dataset. Such patterns inform about which events are frequently observed in sequences, i.e. events that really happen. Sometimes, knowing that some specific event does not happen is more informative than extracting observed events. Negative sequential patterns (NSPs) capture recurrent behaviors by patterns having the form of sequences mentioning both observed events and the absence of events. Few approaches have been proposed to mine such NSPs. In addition, the syntax and semantics of NSPs differ in the different methods which makes it difficult to compare them. This article provides a unified framework for the formulation of the syntax and the semantics of NSPs. Then, we introduce a new algorithm, N PS , that extracts NSPs using a PrefixSpan depth-first scheme, enabling maxgap constraints that other approaches do not take into account. The formal framework highlights the differences between the proposed approach and the methods from the literature, especially with the state of the art approach eNSP. Intensive experiments on synthetic and real datasets show that N PS can extract meaningful NSPs and that it can process bigger datasets than eNSP thanks to significantly lower memory requirements and better computation times.
Complete list of metadatas

https://hal.inria.fr/hal-03025572
Contributor : Thomas Guyet <>
Submitted on : Thursday, November 26, 2020 - 12:30:16 PM
Last modification on : Friday, December 4, 2020 - 3:30:27 AM

File

article_DMKD_NegPSpan.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03025572, version 1

Citation

Thomas Guyet, • René Quiniou. NegPSpan: efficient extraction of negative sequential patterns with embedding constraints. Data Mining and Knowledge Discovery, Springer, 2020. ⟨hal-03025572⟩

Share

Metrics

Record views

20

Files downloads

96