Thomas Guyet

Yves Moinard

René Quiniou

Using Answer Set Programming for pattern mining

Serial pattern mining consists in extracting the frequent sequential patterns from a unique sequence of itemsets. This paper explores the ability of a declarative language, such as Answer Set Programming (ASP), to solve this issue efficiently. We propose several ASP implementations of the frequent sequential pattern mining task: a non-incremental and an incremental resolution. The results show that the incremental resolution is more efficient than the non-incremental one, but both ASP programs are less efficient than dedicated algorithms. Nonetheless, this approach can be seen as a first step toward a generic framework for sequential pattern mining with constraints.

Introduction

Sequential pattern mining aims at analysing ordered or timed data to extract interesting patterns the elements. Broadly, a pattern is considered interesting if it occurs frequently in the data, i.e. the number of its occurrences is greater than a fixed given threshold.

As non informed mining methods tend to generate massive results, there is more and more interest in pattern mining algorithms able to mine data considering some expert knowledge. Though a generic pattern mining tool that could be tailored to the specific task of a data-scientist is still a holy grail for pattern mining software designers, some recent attempts have proposed generic pattern mining tools [START_REF] Guns | MiningZinc: A modeling language for constraint-based mining[END_REF][START_REF] Negrevergne | Dominance programming for itemset mining[END_REF] for itemset mining tasks.

One way to introduce expert knowledge in pattern mining algorithms is to define constraints on the expected patterns. Motivated by the use of constraints in sequential pattern mining. Pei et al. [START_REF] Pei | Mining sequential patterns with constraints in large databases[END_REF][START_REF] Pei | Constraint-based sequential pattern mining: The pattern-growth methods[END_REF] defined seven types of generic constraints that a data scientist would like to express. However, beyond generic constraints, a data scientist would like to express a lot of domain-specific constraints reflecting his own knowledge and preferences.

ASP (Answer Set Programming) is a declarative language that enables an easy expression of constraints as well as domain knowledge and associated formal reasoning tools. To engage in the generic way sketched before, this paper proposes to implement a classical sequential pattern mining algorithm in ASP with the future objective of letting the data scientist define constraints on its patterns and associated domain knowledge.

We show how to encode sequential pattern mining tasks in ASP. The first intuitive and naive encoding is next improved with the incremental resolution facilities of the clingo ASP solver [START_REF] Gebser | Potassco: The Potsdam answer set solving collection[END_REF]. The performance of the method is evaluated on simulated data and compared with the dedicated algorithm MinEpi [START_REF] Mannila | Discovering frequent episodes in event sequences[END_REF].

State of the art

Designing pattern mining languages based on pattern constraints has developed recent interest in the literature [START_REF] Guns | MiningZinc: A modeling language for constraint-based mining[END_REF][START_REF] Negrevergne | Dominance programming for itemset mining[END_REF][START_REF] Bonchi | Extending the state-of-the-art of constraint-based pattern discovery[END_REF][START_REF] Boulicaut | Constraint-based data mining[END_REF]. The aim of these proposals is to obtain a declarative constraint-based language even at the cost of degraded runtime performance compared to a specialized algorithm.

All these approaches have been conducted on itemset mining in transaction databases, which is much simpler than sequential pattern mining in a sequence database, which in turn is simpler than sequential pattern mining in a unique long sequence.

Sequential pattern mining in a sequence database have been addressed by numerous algorithms inspired by algorithms for mining frequent itemsets. The most known algorithms are GSP [START_REF] Srikant | Mining sequential patterns: Generalizations and performance improvements[END_REF], SPIRIT [START_REF] Minos N Garofalakis | SPIRIT: Sequential pattern mining with regular expression constraints[END_REF], SPADE [START_REF] Zaki | SPADE: An efficient algorithm for mining frequent sequences[END_REF], PrefixSpan [START_REF] Pei | Mining sequential patterns by pattern-growth: the PrefixSpan approach[END_REF], and CloSpan [START_REF] Yan | Clospan: Mining closed sequential patterns in large datasets[END_REF] or BIDE [START_REF] Wang | Bide: Efficient mining of frequent closed sequences[END_REF] for closed sequential patterns. To determine the support of a pattern, these algorithms count the number of sequences in the database that contain the pattern without taking into account repetitions of the pattern in the sequences. Deciding if a sequence contains a pattern is generally simple. It is worth-noting that all these algorithms satisfy the antimonotonicity property which is essential to obtain good mining performances. The anti-monotonicity property says that if some pattern is frequent then all its sub-patterns are also frequent. And reciprocally, if some pattern is notfrequent then all its super-patterns are non-frequent. This property enables the algorithm to prune efficiently the search space and thus reduces its exploration.

Counting the number of occurrences of a pattern, or of patterns, in a long sequence introduces some complexity compared to previous approaches as two occurrences of a pattern can overlap. Defining how to enumerate the occurrences of a pattern is important to ensure the anti-monotonicity property. The MinEpi and WinEpi algorithms [START_REF] Mannila | Discovering frequent episodes in event sequences[END_REF] extract frequent episodes. An episode is a directed acyclic graph where edges express the temporal relations between events. A proper edge from node v to node w in the pattern graph implies that the events of v must occur before the events of w, while a weak edge from v to w implies that the events of w may occur either at the same time as those of v or later. Testing whether an episode occurs in the sequence is an NP-complete problem [START_REF] Tatti | Mining closed episodes with simultaneous events[END_REF].

The frequency measure used by MinEpi relies on minimal occurrences of patterns and is anti-monotonic. Other counting methods have been proposed to solve similar problems while preserving the anti-monotonicity property required for the effectiveness of pattern occurrences search (see [START_REF] Achar | A unified view of automata-based algorithms for frequent episode discovery[END_REF] for a unified formulation of sequential pattern counting methods).

Integrating constraints in sequential pattern mining is often limited to the use of simple anti-monotonic temporal constraints such as mingap constraints. In addition to the classical support constraint, Pei et al. [START_REF] Pei | Mining sequential patterns with constraints in large databases[END_REF] defined seven types of constraints on patterns. SPIRIT [START_REF] Minos N Garofalakis | SPIRIT: Sequential pattern mining with regular expression constraints[END_REF] is one of the rare algorithm that considers complex constraints on patterns such as regular expressions.

In [START_REF] Guns | Itemset mining: A constraint programming perspective[END_REF], Guns et al. proposed a new perspective on data mining based on constraint programming. Their aim is to separate modelling and solving in data mining in order to gain more flexibility for elaborating new mining models. They chose to illustrate the approach on itemset mining. Only few recent works have proposed to explore constraint programming for sequential pattern mining. Métivier, Loudni et al. [START_REF] Métivier | A constraint programming approach for mining sequential patterns in a sequence database[END_REF] have developed a constraint programming method for mining sequential patterns with constraints in a sequence database. The constraints are based on amongst and regular expression constraints and expressed by automata. Coquery et al. [START_REF] Coquery | A SAT-Based approach for discovering frequent, closed and maximal patterns in a sequence[END_REF] have proposed a SAT based approach for sequential pattern mining. The patterns are of the form ab?c and an occurrence corresponds to an exact substring (without gap) with joker (the character ? replaces exactly one item different from b and c).

To the best of our knowledge, Järvisalo's work [START_REF] Järvisalo | Itemset mining as a challenge application for answer set enumeration[END_REF] is the unique application of ASP to pattern mining. Following Guns et al. 's proposal, Järvisalo designed an ASP program to extract frequent itemsets in a transaction database. A main feature of Järvisalo is that each answer set (AS) contains only one frequent itemset associated with the identifiers of the transactions where it occurs. Järvisalo addressed this problem as a new challenge for the ASP solver, but did not highlight the potential benefit of this approach to improve the expressiveness of pattern mining tools.

In this paper, we explore the use of ASP to extract frequent string patterns (i.e. patterns without parallel events) in a unique long sequence of itemsets where the occurrences of a string pattern are the minimal occurrences. In addition, we implemented the following simple anti-monotonic constraints to improve the algorithm efficiency:

1. an item constraint states which particular items should not be present in the patterns.

2. a length constraint fixes the maximal length of patterns (number of items).

3. a duration constraint sets the maximal duration of patterns (time elapsed between the occurrence of the first itemset and the occurrence of the last one -difference between timestamps).

4. a gap constraint sets the maximal time delay between the respective timestamps of two successive itemsets.

3 Sequential pattern mining

Items, itemsets and sequences

From now on, [n] denotes the set of the n first integers, i.e.

[n] = {1, . . . , n}.

Let E be the set of items and a total (reflexive) order on this set (e.g. lexicographical). An itemset A = (a1 , a 2 , . . . , a n ), a i ∈ E is an ordered set of distinct items, i.e. ∀i ∈ [n -1], a i a i+1 and i = j ⇒ a i = a j . The size of an itemset α, denoted |α| is the number of items it contains. An itemset

β = (b 1 , . . . , b m ) is a sub-itemset of α = (a 1 , . . . , a n ), denoted β ⊑ α, iff β is a subset of α.
A sequence S = s 1 , s 2 , . . . , s n is an ordered series of itemsets s i . The length of a sequence S, denoted |S|, is the number of itemsets that make up the sequence. The size of a sequence S, denoted S , is the total number of items it contains:

S = |S| i=1 |s i |. T = t 1 , t 2 , . . . , t m is a sub-sequence of S = s 1 , s 2 , . . . , s n , denoted T S, iff there exists a sequence of integers 1 ≤ i 1 < i 2 < . . . < i m ≤ n such that ∀k ∈ [m], t k ⊑ s i k . T = t 1 , t 2 , . . . , t m is a prefix of S = s 1 , s 2 , . . . , s n , denoted T b S 1 , iff ∀k ∈ [m -1], t k = s k and t m ⊑ s m , t m = s m .
Example 1. Let E = {a, b, c} with the lexicographical order (a b, b c) and the sequence S = a(bc)c(abc)cb . To simplify the notation, we omit the parentheses around itemsets containing a single item, and comas inside itemsets. The size of S is 9 and its length is 6. For instance, sequence (bc)(ac) is a subsequence of S and a(bc)c(ac) is a prefix of S.

The relations and b define partial orders on sets of sequences.

Mining string patterns in a long sequence

A long sequence F = {f i } i∈N is a single sequence of itemsets. A string pattern P = p 1 , . . . , p n is a sequence of items (p k ) (all itemsets are singleton). In the sequel, we use the term pattern to refer to our notion of string pattern. Our notion of pattern is more specific than the one defined by Mannila et al. [START_REF] Mannila | Discovering frequent episodes in event sequences[END_REF].

Definition 1 (Occurrences of a pattern, minimal occurrences). An occurrence of the pattern P = p 1 , . . . , p n of length n in a long sequence S = (s 1 , . . . , s m ) is noted by the n-tuple T = (t 1 , . . . , t n ), where

t k , k ∈ [n] is the position of the occurrence of element p k ∈ s t k in S. P is said to occur at interval [t 1 , t n ] in S. Let T = (t 1 , . . . , t n ) and T ′ = (t ′ 1 , . . . , t ′ n ), T ⊳ T ′ ⇔    [t 1 , t n ] ⊂ [t ′ 1 , t ′ n ], or n > 1 ∧ t 1 = t ′ 1 ∧ t n = t ′ n ∧ (t 1 , . . . , t n-1 ) ⊳ (t ′ 1 , . . . , t ′ n-1 )
An occurrence T of a pattern P is minimal if it is minimal for ⊳. I S (P ) denotes the set of all minimal occurrences of P in S.

Example 2. Let S = a(bc)(ac)cd be a long sequence and P = abc be a pattern. Finding occurrences of pattern P in S means to locate items of P in S: a appears only at positions 1 and 3, b appears at position 2, c appears at positions 2, 3 and 4. Pattern P could has two occurrences: (1, 2, 3) and (1, 2, 4). The minimal occurrence condition eliminates occurrence (1, 2, 4) because [START_REF] Achar | A unified view of automata-based algorithms for frequent episode discovery[END_REF][START_REF] Bonchi | Extending the state-of-the-art of constraint-based pattern discovery[END_REF] is (strictly) included in [START_REF] Achar | A unified view of automata-based algorithms for frequent episode discovery[END_REF][START_REF] Coquery | A SAT-Based approach for discovering frequent, closed and maximal patterns in a sequence[END_REF].

Thus I S ( abc ) = {(1, 2, 3)}.
We now consider the pattern P = acd in order to illustrate the second (recursive) minimal occurrence condition. The occurrences of the pattern would be {(1, 2, 5), (1, 3, 5)}. The occurrence [START_REF] Achar | A unified view of automata-based algorithms for frequent episode discovery[END_REF][START_REF] Boulicaut | Constraint-based data mining[END_REF][START_REF] Minos N Garofalakis | SPIRIT: Sequential pattern mining with regular expression constraints[END_REF] is not minimal because the occurrences bounds are equivalents but [START_REF] Achar | A unified view of automata-based algorithms for frequent episode discovery[END_REF][START_REF] Bonchi | Extending the state-of-the-art of constraint-based pattern discovery[END_REF]

is (strictly) included in [1, 3], thus (1, 2, 5) ⊳ (1, 3, 5).
Let S = aaaa be the long sequence.

I S ( aa ) = {(1, 2), (2, 3), (3, 4)
} and

I S ( aaa ) = {(1, 3), (2, 4)}.
Let S be a long sequence and P a pattern. The support of pattern P , denoted by supp(P ), is the cardinality of I S (P ), i.e. supp(P ) = card (I S (P )).

Note that the support function supp(• ) is not anti-monotonic on the set of patterns with associated partial order (see [START_REF] Tatti | Mining closed strict episodes[END_REF]). Considering order b , supp(• ) is anti-monotonic.

Definition 2 (Mining a long sequence). Given a threshold σ, a pattern P is frequent in a long sequence S iff supp(P ) ≥ σ. Mining a long sequence consists in extracting all frequent patterns.

Example 3. Let σ = 2. The set of frequent patterns in S = a(bc)(abc)c(bc) is { a , b , c , ab , ac , bb , bc , cb , cc , acb , acc bcc ccc }.

Mining serial patterns with ASP

This section shows a first way of specifying serial pattern mining in classical ASP programming style. After presenting how to model the data in ASP, we give an intuitive algorithm, then we show how to improve its resolution using clingo control abilities.

Our proposal is borrowed from Järvisalo's [START_REF] Järvisalo | Itemset mining as a challenge application for answer set enumeration[END_REF]: a solution of the ASP program is an answer set (AS) that contains a single frequent pattern as well as its occurrences. The resolution relies on the "generate and test principle": generate combinatorially all the possible patterns, one at a time, associated with their minimal occurrences and test whether they satisfy the specified constraints.

Modelling the long sequence, patterns and occurrences

A long sequence is modelled by the predicate seq/2. For example, the atom seq [START_REF] Boulicaut | Constraint-based data mining[END_REF][START_REF] Minos N Garofalakis | SPIRIT: Sequential pattern mining with regular expression constraints[END_REF] declares that an item 5 occurs at timestamp 3. Similarly, the current pattern is modelled by the predicate pattern/2.

Example 4. Let S = aca(ac)bc be a long sequence and P = acc be a pattern.

%sequence description : a=1, b=2, c=3 seq(1,1) . seq [START_REF] Bonchi | Extending the state-of-the-art of constraint-based pattern discovery[END_REF][START_REF] Boulicaut | Constraint-based data mining[END_REF] . seq [START_REF] Boulicaut | Constraint-based data mining[END_REF][START_REF] Achar | A unified view of automata-based algorithms for frequent episode discovery[END_REF] . seq(4,1) . seq(4,3) . seq [START_REF] Minos N Garofalakis | SPIRIT: Sequential pattern mining with regular expression constraints[END_REF][START_REF] Bonchi | Extending the state-of-the-art of constraint-based pattern discovery[END_REF] . seq [START_REF] Gebser | Potassco: The Potsdam answer set solving collection[END_REF][START_REF] Boulicaut | Constraint-based data mining[END_REF] . %pattern description pattern [START_REF] Achar | A unified view of automata-based algorithms for frequent episode discovery[END_REF][START_REF] Achar | A unified view of automata-based algorithms for frequent episode discovery[END_REF] . pattern [START_REF] Bonchi | Extending the state-of-the-art of constraint-based pattern discovery[END_REF][START_REF] Boulicaut | Constraint-based data mining[END_REF] . pattern [START_REF] Boulicaut | Constraint-based data mining[END_REF][START_REF] Boulicaut | Constraint-based data mining[END_REF] .

An occurrence of some pattern P is described by a set of atoms occ(I ,P,S) where I is the identifier of the occurrence, (an AS describes all the occurrences of its pattern), P is the item position in the pattern and S is the timestamp of a matching itemset in the sequence. Example 5. Continuing example above, the occurrences of pattern P are I S (P ) = {(1, 2, 4), [START_REF] Boulicaut | Constraint-based data mining[END_REF][START_REF] Coquery | A SAT-Based approach for discovering frequent, closed and maximal patterns in a sequence[END_REF][START_REF] Gebser | Potassco: The Potsdam answer set solving collection[END_REF]}. The AS for the program above should contain:

%occurrences occ(1,1,1) . occ(1,2,2) . occ(1,3,4) . occ(2,1,3) . occ(2,2,4) . occ(2,3,6) .

An ASP program for extracting frequent patterns of length n

In this section, we detail an ASP program that generates all the frequent patterns of length n. According to the ASP programming principle, the program contains a generation part and a constraint part. The generation part specifies the pattern structure as a set of pattern atoms and their related occurrences as a set of occ atoms. The constraints eliminate pattern candidates that are not frequent. First, we introduce some additional predicates and constants:

• constant th represents the minimum frequency threshold,

• predicate patlen/1 sets the length of patterns,

• predicate symb/1 specifies the items that can appear in a pattern.

Generating patterns and occurrences

The program below gives the rules for generating occurrences of patterns and their occurrences. The rule in line 6 generates patterns containing exactly L pattern atoms, expressed combinatorially on the vocabulary specified by symb/1 atoms. As only minimal models are solutions of ASP programs, every AS will contain L pattern atoms defining only one pattern.

Next, at line 9, predicate instid /1 is used to enumerate exactly th occurrences of the specified pattern. All the occurrences of a pattern could be generated, but only th are kept in the solution, i.e. the minimal number of occurrences for a pattern to be frequent.

Finally, at line 12, for each of the th pattern occurrences, a set of exactly L occ atoms is generated. In this combinatorial step, every possible association between a pattern item and a sequence timestamp P is blindly considered.

Minimal occurrences constraints

The loose specification above generates many solutions, some being correct but redundant, e.g. with different occurrence identifiers, some being incorrect, e.g. with non minimal occurrences. Now, we add some constraints to keep only the required models.

The first constraint expresses that the item at position N in the pattern must correspond to one of the items at timestamp P in the given sequence. Constraints are expressed by negations. The following constraint requires that for any occurrence atom occ(I ,N,P) of a pattern having item S at position N, it is impossible to not have the same item S at timestamp P in the sequence.

:occ(I , N, P), pattern(N, S), not seq(P, S).

The next constraint expresses that the occurrences must respect the ordering of pattern items: it is not possible to have 2 items ordered in some way in the pattern and the 2 items they are mapped with ordered in the other way in the sequence.

:occ(I , N, P), occ(I , M, Q), N<M, P>=Q.

The next constraint imposes that the N -th item of the pattern maps with a single timestamp in the sequence.

:occ(I , N, P), occ(I , N, Q), P<Q.

Notice that here P < Q is equivalent to P!=Q (meaning P = Q in ASP) since P and Q play symmetric roles in the two atoms in occ. This "trick" is often used in ASP (cf. also lines 16 and 17 in next listing), since it has the advantage of reducing the size of the grounding of the program.

The final constraints are related to minimal occurrences. The first constraint forbids solutions with two occurrences starting at the same timestamp. The second constraint forbids solutions with two occurrences ending at the same timestamp. The third constraint forbids solutions with two occurrences such that one "contains" the other.

:occ(I , 1, P), occ(J, 1, Q), P=Q, I<J. :occ(I , L, P), occ(J, L, Q), patlen(L), P=Q, I<J. :occ(I , 1, SI) , occ(J, 1, SJ), occ(I , L, EI) , occ(J, L, EJ), patlen(L), SI<SJ, EJ<EI, I !=J.

Constraints 16 to 18 could be summed up by the single constraint below. However, the single constraint is significantly less computationally efficient than the three elementary constraints.

:occ(I , 1, SI) , occ(J, 1, SJ), occ(I , L, EI) , occ(J, L, EJ), patlen(L), SI<=SJ, EJ<= EI, I!=J.

Reducing the combinatorics of the solution space

At this step, all the ASs are correct answers to the sequence mining problem, but many of them represents the same solution due to the combinatorial nature of the generation step. For instance, extracting patterns of length 4 in a sequence of 20 items yields 2448 answer sets, but there are only 24 different answer sets2 .

To improve the program efficiency, we add the following constraint on occurrence identifiers imposing that occurrences are ordered by their beginning timestamps. This constraint reduces the number of answer sets to 408. It is better but not perfect.

:occ(I , 1, P), occ(J, 1, Q), I<J, P>Q.

Illustration of constraint effectiveness

Let W = abab be a sequence and th = 2 the support threshold. We consider only the models generated with pattern (1,1) and pattern (2,2) , i.e. that evaluates the occurrences of ab . The models that contain at least two occurrences of ab contain atoms of the form occ(1, w, α), occ(1, x, β) for occurrence 1 and occ(2, y, γ), occ(2, z, δ) for occurrence 2, with α, β, γ, δ ∈ [4] and w, x, y, z ∈ [START_REF] Bonchi | Extending the state-of-the-art of constraint-based pattern discovery[END_REF].

Taking into account the unicity constraint, there are 256 models of the form occ(1, 1, α), occ(1, 2, β), occ(2, 1, γ), occ(2, 2, δ), with α, β, γ, δ ∈ [START_REF] Coquery | A SAT-Based approach for discovering frequent, closed and maximal patterns in a sequence[END_REF]. Adding the mapping constraint, the valid models are the following (the 4-tuples below give the related values for α, β, γ, δ):

(1, 2, 1, 2) (1, 4, 1, 2) (1, 2, 1, 4) (1, 4, 1, 4) (3, 2, 1, 2) (3, 4, 1, 2) (3, 2, 1, 4) (3, 4, 1, 4) (1, 2, 3, 2) (1, 4, 3, 2) (1, 2, 3, 4) (1, 4, 3, 4) (3, 2, 3, 2) (3, 4, 3, 2) (3, 2, 3, 4) (3, 4, 3, 4)
The constraint stating that two occurrences cannot start on the same timestamp, eliminates 8 models:

(

1, 2, 1, 2) (1, 4, 1, 2) (1, 2, 1, 4) (1, 4, 1, 4) (3, 2, 1, 2) (3, 4, 1, 2) (3, 2, 1, 4) (3, 4, 1, 4) (1, 2, 3, 2) (1, 4, 3, 2) (1, 2, 3, 4) (1, 4, 3, 4) (3, 2, 3, 2) (3, 4, 3, 2) (3, 2, 3, 4) (3, 4, 3, 4)
The constraint about the same end of occurrences eliminates 4 additional models:

(1, 2, 1, 2)

(1, 4, 1, 2) (1, 2, 1, 4) (1, 4, 1, 4) (3, 2, 1, 2) (3, 4, 1, 2) (3, 2, 1, 4) (3, 4, 1, 4) (1, 2, 3, 2) (1, 4, 3, 2) (1, 2, 3, 4) (1, 4, 3, 4) (3, 2, 3, 2) (3, 4, 3, 2) (3, 2, 3, 4) (3, 4, 3, 4)
The constraint about the sequentiality of occurrences eliminates 2 additional models:

(

1, 2, 1, 2) (1, 4, 1, 2) (1, 2, 1, 4) (1, 4, 1, 4) (3, 2, 1, 2) (3, 4, 1, 2) (3, 2, 1, 4) (3, 4, 1, 4) (1, 2, 3, 2) (1, 4, 3, 2) (1, 2, 3, 4) (1, 4, 3, 4) (3, 2, 3, 2) (3, 4, 3, 2) (3, 2, 3, 4) (3, 4, 3, 4)
The final constraint (line 19) eliminates the model (3, 4, 1, 2) which is a symmetric solution of the remaining model [START_REF] Achar | A unified view of automata-based algorithms for frequent episode discovery[END_REF][START_REF] Bonchi | Extending the state-of-the-art of constraint-based pattern discovery[END_REF][START_REF] Boulicaut | Constraint-based data mining[END_REF][START_REF] Coquery | A SAT-Based approach for discovering frequent, closed and maximal patterns in a sequence[END_REF].

In this case, the resolution constructs a single answer set: {pattern(1,1) . pattern (2,2) . occ (1,1,1) . occ (1,2,2) . occ (2,1,3) . occ(2,2,4) .}.

This example gives an illustration of successive constraint propagations. This illustration does not correspond to the actual resolution method that uses constraint satisfaction on the grounded program (an intermediary boolean representation of logical rules and facts in the program).

Extracting all frequent patterns

So far, we have seen how to generate patterns of a given length. To extract all the patterns, the program will proceed level-wise: generate patterns of length 1, then patterns of length 2, . . . , then patterns of length n, then patterns of length n+1, etc. To this end, we use the control facilities introduced in recent releases of clingo. The control part of an ASP program is specified by a python program whose main parts are given below. The program begins with an initial grounding step which is followed by successive resolution steps. At each resolution step, the argument value of the patlen(k) atom is incremented to solve the problem for patterns of size k. prg.ground("base",[]) for k in range(1,maxsize):

prg. assignExternal (Fun("patlen", [k]), True) prg. solve () prg. releaseExternal (Fun("patlen", [k]))

Discussion

One of the interest of this program is that it generates only a part of all the occurrences of a pattern in a single AS. The program can be seen as an efficient approach for extracting very frequent patterns, i.e. supp(P ) ≫ σ (small patterns for instance). We break down (a part of) the algorithmic complexity by extracting only the number of pattern occurrences required by the support threshold: browsing the whole dataset is not required. Nonetheless, practically, all the occurrences are actually generated but in different answer sets. If a pattern is very frequent, it would be frequent several times with different subsets of its occurrences. The efficiency to compute an AS is lost by the large number of AS generated within this solution.

In addition, the solution does not enforce the anti-monotonicity property since patterns of size n are computed independently of patterns of size m < n.

To improve this first solution, we explore the incremental resolution facilities of clingo.

5 An incremental ASP program for extracting frequent patterns

General principle of incremental extraction of frequent patterns

We use the incremental control facilities of ASP to implement a level-wise extraction of the frequent patterns: patterns of size n are computed from the patterns of size n -1.

Frequent pattern incremental discovery

Let P be a frequent pattern of length n (n ≥ 2) and I(P ) the set of its occurrences. The "incremental" discovery of frequent patterns is based on browsing the pattern space level-wise: for each item s in the vocabulary, we would like to know if Q = P ⊕ r is a frequent pattern (Q is a right extension of P ). The most difficult part of this problem is to build the occurrences of Q incrementally from the occurrences of P . The following property will be useful to solve this problem: any valid (minimal) occurrence of the extension Q of a pattern P can be obtained by extending some occurrence of pattern P and only one such occurrence can be extended (other extensions will not be minimal).

Property 1. Let n > 1 and Q = P ⊕ r = p 1 , . . . p n , r be a pattern of size n + 1 extending P and let S = (s k ) be a long sequence., we have:

∀I = (i 1 , . . . , i n ) ∈ I S (P ), (∃i ′ , s i ′ = r ∧ ∄J, J = (j 1 , . . . , j n+1 ) ∈ I S (Q), [j 1 , j n+1 ] ⊂ [i 1 , i ′ ] ⇒ I ′ = (i 1 , . . . , i n , i ′ ) ∈ I S (Q)).

Incremental ASP program

The program will be organized in three main parts:

1. the base part of the program generates all frequent singleton-patterns (i.e. patterns of length 1), 2. the incr (n) part of the program generates all frequent patterns of length n from patterns of length n -1 (extension), 3. the control part defines the global strategy.

To benefit from the backward anti-monotonicity of frequent pattern mining, items are added at the end of a pattern. The set of occurrences of some pattern can be computed incrementally thanks to property 1. Contrasting with the previous approach, the complete list of occurrences of the pattern is computed because any occurrence of length n could be useful to compute an occurrence of length n + 1.

prg.ground("base",[]) prg. solve () for n in range(2,maxsize):

prg.ground("incr",[n]) prg. solve ()

This program instantiates the constraints incrementally and solves a partial problem at each step. Moreover, the resolution of incr (n+1) depends on the AS solved from incr (n).

Generating patterns of length 1

The base part of the incremental program is given below. % generate all first elements of occurrences occ(P, 1, P) :pattern(1,S), seq(P, S).

Line 2 generates the list of the frequent symbols. The symbols identifiers are supposed to be between 1 and nbs. nbs is a program constant. Line 5 generates the singleton-patterns, consisting of a single symbol, and line 8 generates the occurrences. This rule enforces to have all the occurrences in the pattern.

Note that the identifier of an occurrence is the timestamp of the first item (see line 8).

There is no frequency constraints on occ atoms because this kind of constraint is satisfied by rule in line 2 which selects frequent symbols only.

Generating patterns of length n from patterns of length n -1

Extending patterns means to add an item at the end of a (frequent) pattern of length n -1 previously extracted. The generation of occurrences is based on Property 1. To obtain the occurrences of an extended pattern, the rule in line 15 attempts to complete each occurrence of the sub-pattern by an occ(I ,n,p)

atom. All combinations of occ atoms that associate the last item of the pattern with a timestamp of the sequence (containing the item) are generated. We assess, line 18 to 20, that generated occurrences are minimals, and thus we eliminate a large number of AS.

#program incr(n).

% pattern extension 1{ pattern(n, P) : symb(P) } 1.

% occurrences extension 0{ occ(I ,n,Q) : seq(Q,S), pattern(n,S), Q>P } 1 :occ(I, n-1, P).

% minimal occurrences constraints :occ(I , n-1, P), occ(I , n, Q), seq(PP,S), pattern(n,S), P<PP, PP<Q. :occ(I , n, P), occ(J, n, P), I<J. :occ(I , 1, P), occ(J, 1, PP), occ(I , n, Q), occ(J, n, QQ), P<PP, QQ<Q, I!=J.

% frequency constraint :-{ occ(I ,n, ) } th-1.

Listing 1: Incremental part of the ASP pattern discovery program

Discussion

The main interest of this solution is the ability to use the anti-monotonicity property to prune the search space and to a priori avoid the evaluation of many models. The incremental program is correct and complete (due to space limitation, the proof is omitted).

This second program shows that, in ASP, it is simple to generate incrementally the candidate patterns of size n from frequent patterns of size n -1. The main difficulty was to rely on pattern occurrences of size n -1 to efficiently compute the pattern occurrences of size n. This is achieved thanks to Property 1. This ASP program remains simple (only 9 useful lines) and intuitive: the incremental part contains 2 rules, one for extending patterns, one for extending occurrences and 4 constraints for verifying the minimality of occurrences and minimum frequency.

Contrarily to the first program, all the occurrences of a pattern are collected in a single model. The evaluation of a model is a bit more complex due to more occurrences, but there is much less models to evaluate.

All possible extensions of an occurrence are generated but only the lowest position will generate a minimal occurrence. A more efficient way would be to use directive #min to select the correct occurrence extension or to order possible extensions and select the minimal ones.

Adding sequential patterns constraints

In this section, we show how to include some popular constraints on sequential patterns, e.g. max occurrence duration, mingap, maxgap, referring to global constant values. Such constant values may be defined by #const directives or be specified in the control part of the program (python part).

#const maxlength = 20. % maximum duration of an occurrence #const maxgap = 7. % maximum delay between two items in an occurrence #const mingap = 0. % minimum delay between two items in an occurrence

The generation rules of program 1 are modified accordingly. It is better to modify the generation rules than to modify the constraint rules. In the first case, unsatisfiable models are not generated a priori. In the second case, the search space related to the AS is pruned according to the result of evaluating constraint rules.

In the incremental part of the program, the generation of occ(I , n, Q) atoms is modified as follows:

0{ occ(I ,n,Q) : seq(Q,S), pattern(n,S), Q<=maxgap+P, Q>mingap+P, Q<=maxlength+P } 1 :occ(I, n-1, P).

Q is a valid timestamp for a pattern extension occurrence if it stands within the limits defined by the constraints:

• gap constraints: Q ∈ [mingap+P, maxgap+P ], where P is the timestamp of the first item

• duration constraint: Q ≤ maxlength + P , where P is the timestamp of the first item 7 Evaluation

Experimentations details

The ASP programs presented above have been evaluated on computation time. All ASP programs were run using the clingo solver (version 4.3). The clingo processes were limited to a memory space of up to 6 GB. The ASP programs were also compared to the dedicated sequential pattern mining algorithm MinEpi [START_REF] Mannila | Discovering frequent episodes in event sequences[END_REF] through the implementation provided by the tool DMT4SP [16]. As mentioned in the state of the art, we could not find another generic sequential pattern approach to which we could compare the proposed ASP programs. The dataset were generated by a random itemset sequence generator. The size of itemsets in the sequence was reduced to 1 and the items were equiprobable. ql denotes the number of different items in the generated sequence.

Incremental vs non-incremental version

We briefly compare the non-incremental version with the incremental version on short sequence (20 items). In fact, the non-incremental version quickly overflows the memory.

Method

ASP resolution vs dedicated algorithm

In this section, we compare the incremental ASP program and the DMT4SP implementation of MinEpi. For both programs, the frequency threshold is set to 10%, the number of different items is set to ql = 10 and the maximal pattern length is set to 10. For each configuration, the resolution was repeated several times with different sequences. If an execution requires more than the maximal amount of memory allowed then it is not taken into account in the final evaluation. Figure 1 illustrates the computation time and memory usage for the ASP program. The computation time increases exponentially with length. We can note that the memory allocation is strongly related to the computation time. Both time and memory of ASP are several orders of magnitude higher than MinEpi. The computation time by MinEpi is constantly less than 0.01 second for all the sequences of length fewer than 130 items.

Computing efficiency improvement "with constraints"

In this experiment, we first compared the two incremental ASP programs, without constraints (see section 5) and with sequential pattern constraints (see section 6). The frequency threshold was still set to 10% but the size of the vocabulary was set to ql = 7 (to augment the number of frequent patterns). The constraints were those defined in the program of section 6.

Adding constraints reduces the combinatorics of the search space and, especially, the combinatorics of occurrences extensions. As a consequence, the number of generated models is considerably reduced as well as the computation time. For instance, the mean computation time for a sequence of 70 items is 166s ± 34s without constraints while with constraints it is 37s ± 27s. Using constraints, the ASP program becomes computationally more competitive with the dedicated algorithm.

Conclusion

To the best of our knowledge, this is the first proposed ASP program for frequent pattern mining that implements the anti-monotonicity constraint to prune the search space. It takes advantage of the control facilities of a recent release of clingo [START_REF] Gebser | Potassco: The Potsdam answer set solving collection[END_REF] to design an incremental ASP program. The results show that our proposal is very slow compared to dedicated algorithms such as MinEpi, but our main objective was to demonstrate the feasability of a declarative and generic approach. ASP solutions are known to be competitive on hard problems. Maybe, enumerating occurrences of a string pattern is not sufficiently hard to be competitive with dedicated algorithms. To assess this assumption, we are working on mining frequent episodes (sequential patterns as sequences of itemsets).

There is room for improving our solution. An immediate improvement would be to use an ordered list of possible extensions. Another classical challenge in pattern mining would be for ASP to tackle the extraction of closed patterns which can considerably improve the performance of data mining algorithms. The closure definition involves evaluating several patterns together, so the current approach (one model = one pattern) does not seem to be relevant to cope with such constraints. The use of the #external directive could be explored to achieve this goal.

Another perspective is to investigate how this framework can be extended to deal with other classical pattern mining problems such as tree mining, subgraph mining, etc. Finally, we would like to explore how to let the user express his own constraints on patterns. A meta-language that could automatically generate constraints in ASP is a midterm objective.

  %generating all the patterns L { pattern (1.. L, P) : symb(P) } L :patlen(L).

  %list of occurrences instid (1.. th) . % I: occurrence id , L: pattern length ,P: sequence position L{ occ(I , 1.. L, P): seq(P, S) }L :instid (I ) , patlen(L).

  %generate all frequent symbols between 1 and nbs symb(S) :th { seq(P,S) }, S=1..nbs.% generate patterns of length 11{ pattern (1, P) : symb(P) } 1.

Figure 1 :

 1 Figure 1: Computation time (in seconds) and memory usage (in bytes) of the incremental ASP program wrt to the length of the sequence.

Figure 2 :

 2 Figure 2: Computation time (in seconds) of the incremental ASP program "with constraints" wrt to the length of the sequence.

Figure 2

 2 Figure 2 illustrates the computation time for the ASP program. The computation times are lower than those of the figure 1. Nonetheless, computation time still increases exponentially with the length of the sequence.

The b in b stands for backward subsequence.

This can be easily tested using the project option of clingo.