Declarative mining of negative sequential patterns

Abstract : Declarative pattern mining consists in using declarative frameworks to solve pattern mining tasks. In this article, we address the task of mining negative sequential patterns in Answer Set Programming (ASP). A negative sequential pattern is specified by means of a sequence consisting of events to occur and of other events, called negative events, to be absent. For instance, containment of the pattern a ¬b c arises with an occurrence of a and a subsequent occurrence of c but no occurrence of b in between. Recent results shed light on the ambiguity of such a seemingly intuitive notation, exhibited three semantics of the negative events and proposed alternative notations for them. In this article, we propose Answer Set Programming encodings of these three semantics in order to extract frequent negative sequential patterns from a set of sequences. It relies on previous encodings of frequent sequential pattern mining. We experiment with our encoding on synthetic data and compare the numbers of extracted patterns and the computing time obtained for each kind of negation. Surprisingly, the semantics that has the best algorithmic properties for pattern mining is not associated to an encoding that is the most efficient.