NegPSpan: efficient extraction of negative sequential patterns with embedding constraints

Abstract

Mining frequent sequential patterns consists in extracting recurrent\nbehaviors, modeled as patterns, in a big sequence dataset. Such patterns inform\nabout which events are frequently observed in sequences, i.e. what does really\nhappen. Sometimes, knowing that some specific event does not happen is more\ninformative than extracting a lot of observed events. Negative sequential\npatterns (NSP) formulate recurrent behaviors by patterns containing both\nobserved events and absent events. Few approaches have been proposed to mine\nsuch NSPs. In addition, the syntax and semantics of NSPs differ in the\ndifferent methods which makes it difficult to compare them. This article\nprovides a unified framework for the formulation of the syntax and the\nsemantics of NSPs. Then, we introduce a new algorithm, NegPSpan, that extracts\nNSPs using a PrefixSpan depth-first scheme and enabling maxgap constraints that\nother approaches do not take into account. The formal framework allows for\nhighlighting the differences between the proposed approach wrt to the methods\nfrom the literature, especially wrt the state of the art approach eNSP.\nIntensive experiments on synthetic and real datasets show that NegPSpan can\nextract meaningful NSPs and that it can process bigger datasets than eNSP\nthanks to significantly lower memory requirements and better computation times.\n