Thomas Guyet -Agrocampus

NegPSpan: efficient extraction of negative sequential patterns with embedding constraints

Mining frequent sequential patterns consists in extracting recurrent behaviors, modeled as patterns, in a big sequence dataset. Such patterns inform about which events are frequently observed in sequences, i.e. what does really happen. Sometimes, knowing that some specific event does not happen is more informative than extracting a lot of observed events. Negative sequential patterns (NSP) capture recurrent behaviors by patterns containing both observed events and absent 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, NegPSpan, that extracts NSPs using a PrefixSpan depth-first scheme and enabling maxgap constraints that other approaches do not take into account. The formal framework allows for highlighting 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 NegPSpan can extract meaningful NSPs and that it can process bigger datasets than eNSP thanks to significantly lower memory requirements and better computation times.

Introduction

In many application domains such as diagnosis or marketing, decision makers show a strong interest for rules that associates specific events (a context) to undesirable events to which they are correlated or that are frequently triggered in such a context. Sequential pattern mining algorithms can extract such hidden rules from execution traces or transactions. in the classical setting, sequential patterns contain only positive events, i.e. really observed events. However, the absence of a specific action or event can often better explain the occurrence of an undesirable situation [START_REF] Cao | Nonoccurring behavior analytics: A new area[END_REF]. For example in diagnosis, if some maintenance operations have not been performed, e.g. damaged parts have not been replaced, then a fault will likely occur in a short delay while if these operations were performed in time the fault would not occur. In marketing, if some market-place customer has not received special offers or coupons for a long time then she/he has a high probability of churning while if she/he were provided such special offers she/he should remain loyal to her/his market-place. In these two cases, mining specific events, some present and some absent, to discover under which context some undesirable situation occurs or not may provide interesting so-called actionable information 1 for determining which action should be performed to avoid the undesirable situation, i.e. fault in diagnosis, churn in marketing.

We aim at discovering sequential patterns that take into account the absence of some events called negative events [START_REF] Cao | Nonoccurring behavior analytics: A new area[END_REF]. Moreover, we want to take into account some aspect of the temporal dimension as well, maximal pattern span or maximal gap between the occurrences of pattern events. For example, suppose that from a sequence dataset, we want to mine a sequential pattern p = a b with the additional negative constraint telling that the event c should not appear between events a and b in p. The corresponding negative pattern is represented as p = a ¬c b , where the logical sign ¬ denotes an absent event or set of events. Once the general idea of introducing negative statements in a pattern has been stated, the syntax and semantics of such negative patterns should be clearly formulated since they have a strong impact both on algorithms outcome and their computational efficiency. As we will see, the few algorithms from literature do not use the same syntactical constraints and rely on very different semantics principles (see Section 3). More precisely, the efficiency of eNSP [START_REF] Cao | e-NSP: Efficient negative sequential pattern mining[END_REF], the state-of-the-art algorithm for NSP mining, comes from a negation semantics that enables efficient operations on the sets of supported sequences. The two computational limits of eNSP are memory requirements and the impossibility for eNSP to handle embedding constraints such as the classical maxgap and maxspan constraints. When mining relatively long sequences (above 20 itemsets), such constraints appear semantically sound to consider short pattern occurrences where events are not too distant. In addition, such constraints can efficiently prune the occurrence search space.

This article provides two main contributions:

• we clarify the syntactic definition of negative sequential patterns and we provide different negation semantics with their properties.

• we propose NegPSpan, an algorithm inspired by algorithm PrefixSpan to extract negative sequential patterns with maxgap and maxspan constraints.

Intensive experiments compare, on synthetic and real datasets, the performance of NegPSpan and eNSP as well as the pattern sets extracted by each of them. We show that algorithm NegPSpan is more time-efficient than eNSP for mining long sequences thanks to the maxgap constraint and that its memory requirement is several orders of magnitude lower, enabling to process much larger datasets. In addition, we highlight that eNSP misses interesting patterns on real datasets due to semantic restrictions.

Negative Sequential Patterns

This section introduces sequential patterns and negative sequential pattern mining. First we recall some basic definitions about sequences of itemsets, and classical sequential pattern mining then we introduce some definitions of negative sequential patterns.

In the sequel, [n] = {1, . . . , n} denotes the set of the first n strictly positive integers. Let (I, <) be the set of items (alphabet) associated with a total order (e.g. lexicographic order). An itemset A = {a 1 a 2 ... a m } ⊂ I is a set of ordered items. A sequence s is a set of sequentially ordered itemsets s = s 1 s 2 ... s n . This means that for all i, j ∈ [n], i < j, s i appends before s j in sequence s. This sequence starts by s 1 and finishes by s n . Mining sequential patterns from a dataset of sequences, denoted D, consists in extracting the frequent subsequences (patterns) included in database sequences having a support (i.e., the number of sequences in which the pattern occurs) greater than a given threshold σ. There is a huge literature about sequential pattern mining. We will not go into details and refer the reader to a survey of the literature, such as Mooney et al. [START_REF] Mooney | Sequential pattern mining -approaches and algorithms[END_REF].

Negative sequential patterns (NSP) extend classical sequential patterns by enabling the specification of absent itemsets. For example, p = a b ¬c e f is a negative pattern. The symbol ¬ before c denotes that c is a negative itemset (here reduced to an item). Semantically, p specifies that items a and b happen in a row, then items e and f occur in a row, but item c does not occur between the occurrences of bs and e.

In the field of string matching, negation is classically defined for regular expression. In this case, a pattern is an expression that can hold any kind of negated pattern. The same principle gives the following most generic definition of negative sequential patterns: Let N be the set of negative patterns. A negative pattern p = p 1 . . . p n ∈ N is a sequence where ∀i, p i is a positive itemset (p i ⊂ I) or a negated pattern (p i = ¬{q i }, q i ∈ N ).

Due to its infinite recursive definition, N appears to be too huge to be an interesting and tractable search space for pattern mining. For instance, with I = {a, b, c}, it is possible to express simple patterns like a ¬b c but also complex patterns like a, ¬ b, c . The combinatorics for such patterns is infinite.

We now provide our definition of negative sequential patterns (NSP) which introduces some syntactic restriction compare to the most generic case. These simple restrictions are broadly used in the literature [START_REF] Kamepalli | Frequent Negative Sequential Patterns -a Survey[END_REF] and enable us to propose efficient algorithms.

Definition 1 (Negative sequential patterns (NSP)). A negative pattern

p = p 1 . . . p n is a sequence where ∀i, p i is a positive itemset (p i = {p j i } j∈[m] , p j i ∈ I) or a negated itemset (p i = ¬{q j i } j∈[m ]
, q j i ∈ I) under the two following constraints: consecutive negative itemsets and negative itemsets at the pattern boundaries are forbidden. The positive part1 of pattern p, denoted p + , is the subsequence of p restricted to its positive itemsets.

According to the constraint of non consecutive negative itemsets, a negative pattern p can be denoted by p = p 1 ¬q 1 p 2 ¬q 2 . . . p n-1 ¬q n-1 p n where ∀i, p i ⊆ I \ ∅ and q i ⊆ I. With this notation, p + = p 1 p 2 . . . p n-1 p n .

Let us illustrate our syntactic restrictions by some contra-examples of patterns that our approach does not extract:

• first of all, a pattern is a sequence of positives and negative itemsets. It is not possible to have patterns such as a, ¬ b, c

• then, successive negated itemsets are not allowed: a ¬b ¬cd is not possible.

• finally, a pattern finishing or starting by a negated itemsets is also not allowed ¬b d .

Semantics of Negative Sequential Patterns

The semantics of negative sequential patterns relies on negative containment: a sequence s supports pattern p if s contains a sub-sequence s such that every positive itemset of p is included in some itemset of s in the same order and for any negative itemset ¬i of p, i is not included in any itemset occurring in the sub-sequence of s located between the occurrence of the positive itemset preceding ¬i in p and the occurrence of the positive itemset following ¬i in p.

So far in the literature, the absence or non-inclusion of itemsets (represented here as a negative itemset) has been specified by loose formulations. The authors of PNSP have proposed the set symbol to specify non-inclusion. This symbol is misleading since it does not correspond to the associated semantics given in PNSP: an itemset I is absent from an itemset I if the entire set I is absent from I (as opposed to at least some item from I is absent from I ) which corresponds to I ∩ I = ∅ in standard set notation, and not I ⊆ I . We will call PNSP interpretation total non inclusion. It should be distinguished from partial non inclusion which corresponds (correctly) to the set symbol . The symbol was further used by the authors of Neg-GSP and eNSP. The semantics of non inclusion is not detailed in Neg-GSP and one cannot determine if it means total or partial non inclusion.2 eNSP does not define explicitly the semantics of non inclusion but, from the procedure used to compute the support of patterns, one can deduce that it uses total non inclusion.

Definition 2 (non inclusion). We introduce two operators relating two itemsets P and I:

• partial non inclusion: P I ⇔ ∃e ∈ P , e / ∈ I

• total non inclusion: P I ⇔ ∀e ∈ P, e / ∈ I Choosing one non inclusion interpretation or the other has consequences on extracted patterns as well as on pattern search. Let's illustrate this on related pattern support in the sequence dataset

D =            s 1 = (bc) f a s 2 = (bc) (cf ) a s 3 = (bc) (df ) a s 4 = (bc) (ef ) a s 5 = (bc) (cdef ) a            .
Table 1 compares the support of progressively extended patterns under the two semantics to show whether anti-monotonicity is respected or not. Let's consider pattern p 2 on sequence s 2 . Considering that the positive part of p 2 is in s 2 , p 2 occurs in the sequence iff (cd) ⊆ (cf ). In case of total non inclusion, it is false that (cd) (cf ) because of c that occurs in (cf ), and thus p 2 does not occur in s 2 . But in case of a partial non inclusion, it is true that (cd) (cf ), because of d that does not occurs in (cf ), and thus p 2 occurs in s 2 .

Obviously, partial non inclusion satisfies anti-monotonicity while total non inclusion does not. In the sequel we will denote the general form of itemset non inclusion by the symbol , meaning either or . Now, we formulate the notions of sub-sequence, non inclusion and absence by means of the concept of embedding.

• p i ⊆ s ei if p i is positive • p i s j , ∀j ∈ [e i-1 + 1, e i+1 -1] if p i is negative e = (e i ) i∈[m] ∈ [n]
m is a strict-embedding of pattern p in sequence s iff for all i ∈ [m]:

• p i ⊆ s ei if p i is positive • p i j∈[ei-1+1,ei+1-1] s j if p i is negative
Proposition 1. soft-and strict-embeddings are equivalent when def := .

Proof. see Appendix A.

Let p + = p k1 . . . p k l be the positive part of some pattern p, where l denotes the number of positive itemsets in p. If e is an embedding of pattern p in some sequence s, then e + = e k1 . . . e k l is an embedding of the positive sequential pattern p + in s.

The following examples illustrate the impact of itemset non-inclusion operator and of embedding type. One can notice that each sequence contains a unique occurrence of a d , the positive part of pattern p. Using soft-embeddings and total non-inclusion ( def := ), p occurs in s 1 , s 3 and s 4 but not in s 2 . Using the strict-embedding semantics and partial non-inclusion, p occurs in sequence s 3 and s 4 considering that items b and c occur between occurrences of a and d in sequences 1 and 2. With partial non inclusion ( def := ) and either type of embeddings, the absence of an itemset is satisfied if any of its item is absent. As a consequence, p occurs only in sequence s 4 .

Another point that determines the semantics of negative containment concerns the multiple occurrences of some pattern in a sequence: should every or only one occurrence of the pattern positive part in the sequence satisfy the non inclusion constraints? This point is not discussed in previous propositions for negative sequential pattern mining. Actually, PNSP and Neg-GSP require a weak absence (at least one occurrence should satisfy the non inclusion constraints) while eNSP requires a strong absence (every occurrence should satisfy non inclusion constraints).

Definition 5 (Negative pattern occurrence). Let s be a sequence, p be a negative sequential pattern, and p + the positive part of p.

• Pattern p softly-occurs in sequence s, denoted p s, iff there exists at least one (strict/soft)embedding of p in s.

• Pattern p strictly-occurs in sequence s, denoted p s, iff for any embedding e of p + in s there exists an embedding e of p in s such that e = e + .

Definition 5 allows for formulating two notions of absence semantics for negative sequential patterns depending on the occurrences of the positive part:

• strict occurrence: a negative pattern p occurs in a sequence s iff there exists at least one occurrence of the positive part of pattern p in sequence s and every such occurrence satisfies the negative constraints,

• soft occurrence: a negative pattern p occurs in a sequence s iff there exists at least one occurrence of the positive part of pattern p in sequence s and one of these occurrences satisfies the negative constraints. so there is no difference for occurrences under the two semantics. But, it occurs thrice in s 2 with embeddings (1, 2, 5), [START_REF] Cao | e-NSP: Efficient negative sequential pattern mining[END_REF][START_REF] Cao | Nonoccurring behavior analytics: A new area[END_REF][START_REF] Chun-Wei Lin | FHN: An efficient algorithm for mining high-utility itemsets with negative unit profits[END_REF] and [START_REF] Dong | F-NSP+: A fast negative sequential patterns mining method with self-adaptive data storage[END_REF][START_REF] Kamepalli | Frequent Negative Sequential Patterns -a Survey[END_REF][START_REF] Chun-Wei Lin | FHN: An efficient algorithm for mining high-utility itemsets with negative unit profits[END_REF]. The two first occurrences do not satisfy the negative constraint (¬c) while the second occurrence does. Under the soft occurrence semantics, pattern p occurs in sequence s 2 whereas under the strict occurrence semantics it does not.

We also introduce constrained negative sequential patterns. We consider the two most common anti-monotonic constraints on sequential patterns: maxgap (θ ∈ N) and maxspan (τ ∈ N) constraints. These constraints impact NSP embeddings. An embedding e of a pattern p in some sequence s satisfies the maxgap (resp. maxspan) constraint iff e + = {e i , . . . , e n }, the embedding of the positive part of p satisfies the constraint, i.e. ∀i ∈ [n -1], e i+1e i ≤ θ (resp. e ne 1 ≤ τ ).

The definitions of pattern support, frequent pattern and pattern mining task derives naturally from the notion of occurrence of a negative sequential pattern, no matter the choices for embedding (soft or strict), non inclusion (partial or total) and occurrence (soft or strict). However, these choices concerning the semantics of NSPs impact directly the number of frequent patterns (under the same minimal threshold) and further the computation time. The stronger the negative constraints, the lesser the number of sequences that hold some pattern, and the lesser the number of frequent patterns.

Finally, we introduce a partial order on NSPs that is the foundation of our efficient NSP mining algorithm.

Definition 6 (NSP partial order). Let p

= p 1 ¬q 1 p 2 ¬q 2 . . . p k-1 ¬q k-1 p k and p = p 1 ¬q 1 p 2 ¬q 2 . . . p k -1 ¬q k -1 p k be two NSPs s.t. ∀i ∈ [k], p i = ∅ and ∀i ∈ [k ], p i = ∅. By definition, p p iff k ≤ k and: 1. ∀i ∈ [k -1], p i ⊆ p i and q i ⊆ q i 2. p k ⊆ p k 3. k = k =⇒ p k = p k (non-reflexive)
Intuitively, p p if p is shorter than p and the positive and negative itemsets of p are pairwise included into the itemsets of p , but, in case of extension by additional itemsets. The classical pattern inclusion fails to be anti-monotonic [START_REF] Zheng | Negative-GSP: An efficient method for mining negative sequential patterns[END_REF], since the change of scope of negative itemsets.

We illustrate what's happening on two examples. Let first consider the case of an ending negated itemset illustrated by Zheng et al. . with patterns p = b ¬c a and p = b ¬c : removing the a make the positive pattern less constraint (more frequent), but is extend the scope of the negative constraint. Negation are more constraint and the anti-monotonicity is lost. This specific case does not impact our framework as our definition of NSP (see Definition 1) does not allow ending negated itemsets. But let us now consider the patterns p = b ¬c da and p = b ¬ca , and the sequences s = b e d c a . p occurs in s but not p has the scope of the negated itemset ¬c changed it was restricted to the interval between b and d occurrence for p , but between b and a for p.

What is important in our partial order , is that the embedding of the positive pattern yields an embedding for p that imposes the negative constraints on the exact same scopes than negative constraints of p . Thanks to the anti-monotonicity of , additional itemsets in negative patterns leads to over constraints the sequence. These remarks give some intuition behind the following anti-monotonicity property (Proposition 2). The formal proof of the proposition can be found in Appendix A.

Proposition 2 (Anti-monotonicity of NSP support). The support of NSP is anti-monotonic with respect to when def := and soft-occurrences ( ) are considered.

We can notice that while the strict occurrence semantic ( ) is used, lost the anti-monotonicity. Considering p = a (bc) ¬c d , p = a b ¬c d and s = a b (bc) e d , then it is true that p s, but not that p s. In the second case, there are two possible embeddings and the second one (which does not derived from the embedding of p ) does not satisfy the negative constraint.

A second example illustrates another case that is encountered when a postfixed sequence restricts the set of valid embeddings: p = a ¬b d c , p = a ¬b d and s = a e d c b d . Again, p occurs only once while p occur twice and one of its embeddings does not satisfy the negated itemset. This example shows that a simple postfix extension of NSP leads to loose the monotonicity property while the strict occurrence semantic is considered.

Related Work

Kamepalli et al. provide a survey of the approaches proposed for mining negative patterns [START_REF] Kamepalli | Frequent Negative Sequential Patterns -a Survey[END_REF]. The three most significant algorithms appear to be PNSP, Neg-GSP and eNSP. We briefly review each of them in the following paragraphs.

PNSP (Positive and Negative Sequential Patterns mining) [START_REF] Hsueh | Mining negative sequential patterns for e-commerce recommendations[END_REF] is the first algorithm proposed for mining full negative sequential patterns where negative itemsets are not only located at the end of the pattern. PNSP extends algorithm GSP [START_REF] Srikant | Mining sequential patterns: Generalizations and performance improvements[END_REF] to cope with mining negative sequential patterns. PNSP consists of three steps: i) mine frequent positive sequential patterns, by using algorithm GSP, ii) preselect negative sequential itemsets -for PNSP, negative itemsets must not be too infrequent (should have a support less than a threshold miss freq) -iii) generate candidate negative sequences levelwise and scan the sequence dataset again to compute the support of these candidates and prune the search when the candidate is infrequent. This algorithm is incomplete: the second parameter reduces the set of potential negative itemsets. Moreover, the pruning strategy of PNSP is not correct [START_REF] Zheng | Negative-GSP: An efficient method for mining negative sequential patterns[END_REF] and PNSP misses potentially frequent negative patterns.

Zheng et al. [START_REF] Zheng | Negative-GSP: An efficient method for mining negative sequential patterns[END_REF] also proposed a negative version of algorithm GSP, called Neg-GSP, to extract negative sequential patterns. They showed that traditional Apriori-based negative pattern mining algorithms relying on support anti-monotonicity have two main problems. The first one is that the Apriori principle does not apply to negative sequential patterns. They gave an example of sequence that is frequent even if one of its sub-sequence is not frequent. The second problem has to do with the efficiency and the effectiveness of finding frequent patterns due to a vast candidate space. Their solution was to prune the search space using the support anti-monotonicity over positive parts. This pruning strategy is correct but incomplete and it is not really efficient considering the huge number of remaining candidates whose support has to be evaluated. To improve the efficiency of their approach, the authors proposed an incomplete heuristic search based on Genetic Algorithm to find negative sequential patterns [START_REF] Zheng | An efficient GA-based algorithm for mining negative sequential patterns[END_REF]. We will see in Section 2.1 that anti-monotonicity can be defined considering a partial order relation based on common prefixes that a enable to design a complete, correct and efficient algorithm.

eNSP (efficient NSP) has been recently proposed by Cao et al. [START_REF] Cao | e-NSP: Efficient negative sequential pattern mining[END_REF]. It identifies NSPs by computing only frequent positive sequential patterns and deducing negative sequential patterns from positive patterns. Precisely, Cao et al. showed that the support of some negative pattern can be computed by arithmetic operations on the support of its positive sub-patterns, thus avoiding additional sequence database scans to compute the support of negative patterns. However, this necessitates to store all the (positive) sequential patterns with their set of covered sequences (tidlists) which may be impossible in case of big dense datasets and low minimal support thresholds. This approach makes the algorithm more efficient but it hides some restrictive constraints on the extracted patterns. First, a frequent negative pattern whose so-called positive partner (the pattern where all negative events have been switched to positive) is not frequent will not be extracted. Second, every occurrence of a negative pattern in a sequence should satisfy absence constraints. We call this strong absence semantics (see Section 2.1). These features lead eNSP to extract less patterns than previous approaches. In some practical applications, eNSP may miss potentially interesting negative patterns from the dataset.

The first constraint has been partly tackled by Dong et al. with algorithm eNSPFI, an extension of eNSP which mines NSPs from frequent and some infrequent positive sequential patterns from the negative border [START_REF] Gong | e-NSPFI: Efficient mining negative sequential pattern from both frequent and infrequent positive sequential patterns[END_REF]. E-msNSP [START_REF] Xu | E-msNSP: Efficient negative sequential patterns mining based on multiple minimum supports[END_REF] is another extension of eNSP which uses multiple minimum supports: an NSP is frequent if its support is greater than a local minimal support threshold computed from the content of the pattern and not a global threshold as in classical approaches. A threshold is associated with each item, and the minimal support of a pattern is defined from the most constrained item it contains. Such kind of adaptive support prevents from extracting some useless patterns still keeping the pattern support anti-monotonic. The same authors also proposed high utility negative sequential patterns based on the same principles [START_REF] Xu | Mining high utility sequential patterns with negative item values[END_REF] and applied on smart city data [START_REF] Xu | Efficient high utility negative sequential patterns mining in smart campus[END_REF]. An alternative approach has been proposed by Lin consisting in mining high-utility itemsets with negative unit profits [START_REF] Chun-Wei Lin | FHN: An efficient algorithm for mining high-utility itemsets with negative unit profits[END_REF] but is not applied on sequential patterns. It is worth noting that this algorithm relies basically on the same principle as eNSP and so, present the same drawbacks, heavy memory requirements, strong absence semantics for negation. F-NSP+ [START_REF] Dong | F-NSP+: A fast negative sequential patterns mining method with self-adaptive data storage[END_REF] extends the eNSP algorithm to use bitmap representations of itemsets. Using bitmap representations enable to speed up the eNSP algorithm, thanks to very efficient set operation on bitmaps. The F-NSP algorithm has a poor memory usage, while F-NSP+, which adapts the bitmap size to the dataset, requires slightly less memory. SAPNSP [START_REF] Liu | Sapnsp: Select actionable positive and negative sequential patterns based on a contribution metric[END_REF] tackles the problem of large amount of patterns by selecting frequent negative and positive patterns that are actionable. Patterns are actionable while they conform to special rules.

NegI-NSP [START_REF] Qiu | NegI-NSP: Negative sequential pattern mining based on loose constraints[END_REF] proposes additional syntactic constraints on negative itemsets and uses the same strategy as e-NSP.

To conclude this section on formal aspects of negative pattern mining, we provide in Table 2 a comparison of several negative sequential pattern mining approaches wrt several features investigated in this section. It is also important to precise that not any semantics is "more correct" than another one. Its relevancy depends on the information the data scientists want to capture in its datasets, and the nature of the data at hand. In this work, one of our objective is to provide a sound and insightful framework about negative patterns to enable users to choose the tool to use and to make this choice according to the semantic of the negation they want to use. Execution time is obviously an important choice criteria but it must overtake by semantic choice to first provide interesting, intuitive and sound results.

Algorithm NegPSpan

In this section, we introduce algorithm NegPSpan for mining NSPs from a sequence database under maxgap and maxspan constraints and under a weak absence semantics with def := for itemset inclusion. As stated in proposition 1, no matter the embedding strategy, they are equivalent under strict itemset inclusion. Considering occurrences, NegPSpan uses the soft-occurrence semantic: at least one occurrence of the negative pattern is sufficient to consider that it is supported by the sequence.

For computational reasons, we make an additional assumption on the admissible itemsets as negative itemsets. The negative itemsets are restricted to one element of some language L -in order to cut the combinatorics of negative itemsets. In the algorithm NegPSpan presented below, L -= {I = {i 1 , . . . , i n }|∀k, supp(i k ) ≥ σ} denotes the set of itemsets that can be built from frequent items. But this set could also be user defined when the user is interested in some specific sets of non-occurring events. For instance, L -could be the set of frequent itemsets, which would be more restrictive than the set of itemsets made of frequent itemsets.

Main Algorithm

NegPSpan is based on algorithm PrefixSpan [START_REF] Pei | Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach[END_REF] which implements a depth first search and uses the principle of database projection to reduce the number of sequence scans. NegPSpan adapts the pseudo-projection principle of PrefixSpan which uses a projection pointer to avoid copying the data. For NegPSpan, a projection pointer of some pattern p is a triple sid, ppred, pos where sid is a sequence identifier in the database, pos is the position in sequence sid that matches the last itemset of the pattern (necessarily positive) and ppred is the position of the previous positive pattern.

Algorithm 1 details the main recursive function of NegPSpan for extending a current pattern p. The principle of this function is similar to PrefixSpan. Every pattern p is associated with a pseudoprojected database represented by both the original set of sequences S and a set of projection pointers occs. First, the function evaluates the size of occs to determine whether pattern p is frequent or not. If so, it is outputted, otherwise, the recursion is stopped because no larger patterns are possible (anti-monotonicity property).

Then, the function tries three types of pattern extensions of pattern p into a pattern p :

• the positive sequence composition ( c ) consists in adding one item to the last itemset of p (following the notations of Definition 6, the extension corresponds to the case of p is the extension of

p where k = k, ∀i ∈ [k -1], q i = q i and |p k | = |p k | + 1),
• the positive sequence extension ( s ) consists in adding a new positive singleton itemset at the end of p (k = k + 1, ∀i ∈ [k -1], q i = q i and |p k | = 1),

• the negative sequence extension ( n ) consists in inserting a negative itemset between the positive penultimate itemset of p and the last positive itemset of p

(k = k, ∀i ∈ [k-2], q i = q i , |q k-1 | = |q k-1 | + 1 and p k = p k ).
In addition, NSP are negatively extended iff |p k | = 1 to prevent from redundant pattern generation (see section 4.3).

The negative pattern extension is specific to our algorithm and is detailed in the next section. The first two extensions are identical to PrefixSpan pattern extensions, including their gap constraints management, i.e. maxgap and maxspan constraints between positive patterns. Proposition 3. The proposed algorithm is correct and complete.

Intuitively, the algorithm is complete considering that the three extensions enables to generate any NSP. For instance, pattern a ¬e b (ce) ¬(bd) a would be evaluated after evaluating the following patterns: a

Extension of Patterns with Negated Itemsets

Algorithm 2 extends the current pattern p with negative items. It generates new candidates by inserting an item it ∈ I f , the set of frequent items. Let p[-2] and p[-1] denote respectively the penultimate itemset and the last itemset of p.

If p[-2] is positive, then a new negated itemset is inserted between p[-2] and p[-1]. Otherwise, if p[-2] is negative, item it is added to p[-2].
To prevent redondant enumeration of negative itemsets, only items it (lexicographically) greater than the last item of p[-2] can be added.

Then, lines 10 to 20, evaluate the candidate by computing the pseudo-projection of the current database. According to the selected semantics associated with , i.e. total non inclusion (see Definition 4), it is sufficient to check the absence of it in the subsequence included between the occurrences of positive itemsets surounding it. To achieve this, the algorithm checks the sequence positions in the interval [occ.ppred+1, occ.pos-1]. If it does not occur in itemsets from this interval, then the extended pattern occurs in the sequence occ.sid. Otherwise, to ensure the completeness of the algorithm, another occurrence of the pattern has to be searched in the sequence (cf. Match function that takes into account gap constraints).

For example, the first occurrence of pattern p = abc in sequence abecabc is occ p = sid, 2, 4 . Let's now consider p = ab¬ec , a negative extension of p. The extension of the projection-pointer occ p does not satisfy the absence of e. So a new occurrence of p has to be searched for. sid, 6, 7 , the next occurrence of p, satisfies the negative constraint. Then, NegPSpan is called recursively for extending the new current pattern ab¬ec .

We can note that the gap constraints τ and θ does not explicitly appear in this algorithm (except while a complete matching is required), but it impact indirectly the algorithm by narrowing the possible interval of line 13.

Extracting NSP without surrounding negations

An option restricts negated item to be not surrounded by itemsets containing this item. This alternative is motivated by the objective to simplify pattern understanding. A pattern a¬bbc may be interpreted as "there is exactly one occurrence of b between a and c". But, this may also lead to redundant patterns: ab¬bc matches exactly the same sequences than a¬bbc (see section 4.3). This second restriction can be disabled in our algorithm implementation. If so and for sake of simplicity, we preferred to yield the pattern ab¬bc .

The set of such NSP can be extracted using the same algorithm, simply changing the candidate generation in Algorithm 2, line 2 by it ∈ I f \ (p[-1] ∪ p[-2]). Items to add to a negative itemset are among frequent items except surrounding items.

Extracting NSP with partial non inclusion (

⊆ def := )
Algorithm 3 present the variant of the negative extension algorithm while the partial non-inclusion is used ( ⊆ def := ). The backbone of the algorithm is similar: a candidate pattern with a negated itemset at the penultimate position is generated and it assesses whether this candidate is frequent or not. It is done by checking the absence of the itemset is in the itemsets of the sequence at positions defined by the occurrence. The test of line 7 assesses that it is false that is s occ.sid [sp]: is is not partial non-included in one the itemset of the sequence iff is is a subset of it.

On the contrary to the previous approach, candidate patterns are generated based on L -the list of itemsets. It is not possible to build itemsets from the list of items because, using this non-Algorithm 1: NegPSpan: recursive function for negative sequential pattern extraction input: S: set of sequences, p: current pattern, σ: minimum support threshold, occs: list of occurrences, I f : set of frequent items, θ: maxgap, τ : maxspan inclusion semantic, the support is monotonic (and not anti-monotonic). The combinatorics of this variant is thus significantly higher in practice because all element of L -would be evaluated.

Redundancy avoidance

The NegPSpanalgorithm is syntactically non-redundant but can in practice generates patterns that are semantically redundant.

The semantic redundancy appears for pairs of patterns like a ¬b b c and a b ¬b c : there are syntactically different but match the exact same set of sequences. Semantically, such pattern could be interpreted as "there is not much than one occurrence of b between a and c". For such patterns, it is possible to avoid generating both efficiently. Our solution is to not generate candidate patterns with negative items that are in the last itemset. Thus, only a b ¬b c would be generated. In Algorithm 2 line 2, the list of frequent items I f is then replaced by I f \ p [START_REF] Cao | e-NSP: Efficient negative sequential pattern mining[END_REF]. But, this modification makes loose the completeness of the algorithm. In fact, the pattern a ¬b b is not generated neither its semantically equivalent pattern a b ¬b because of the syntactic constraint on NSP that can not end with a negative itemset. In practice, we do not manage this kind of redundancy or prefer the sound and correct option of not surrounding negative itemsets (see section 4.2.1).

A syntactic redundancy is introduced by adding the extension by negative items. For instance, the pattern a ¬b (cd) may be reached by two distinct paths p 1 : a c c a (cd) n a ¬b (cd) or p 2 : a c n a ¬b c c a ¬b (cd) . To solve this problem, the algorithm first specifies the negative itemsets as a composition of negative items and then to compose the last itemset with new items. This discard the path p 1 . In Algorithm 1, line 8 enables negative extension only if the last (positive) itemset is of size 1.

Execution Example

This section illustrates the execution of the algorithm on a small example. Let us consider the dataset of sequences of Table 3 and the minimal support threshold σ = 2. In this example, we consider the following negative patterns semantic: total non-inclusion and strong absence. No gap constraints are considered (θ = ∞ and τ = ∞). Then, we have L = {a, b, c, d, e}. The f event occurs only once and are thus not frequent according to σ value. a e d f

Figure 1 illustrates the execution of NegPSpan algorithm on the dataset of Table 3 starting from pattern a . The tree illustrates successive patterns explored by the depth-first search strategy. Each node detailed both the pattern and the corresponding projected database. For sake of space, the tree is simplified and some nodes are missing.

For patterns larger than two, projected sequences have two colors corresponding, in green, of the part of the sequence that can be used to make positive extensions and, in red, of the part of the sequence that is used to assess absence of items for negative extension. Two markers locate positions of the projection pointer. The second pointer is the same as the one computed by PrefixSpan.

Let us consider projected sequences of pattern ae . In the first sequence, d is green as the part of the sequence ending the sequence after position of e. cb are in read because this events are inbetween occurrence of a and e. This pattern can be extended in two ways:

• with negative items among L \ {a, e} (a and e are removed if the restriction on second restriction is activated),

• with positive items among items that are frequent in the green parts.

Considering extension of pattern a e with a negative item, e.g. ¬c, each sequence whose red part contains the item is discarded, the others remains identical. Extension by ¬c leads to pattern a¬c e only for sequences s 3 and s 4 .

The extension of pattern a e by a positive item follows the same strategy as PrefixSpan. In this case, the algorithm only explore extension by d item and projected pointers are updated to reduce further scanning.

Adding a new negative item while the penultimate item is negative, append it in the negative itemset. In case of pattern a¬c e , d is the only candidate because e is one of the surrounding events and b is above c is the lexicograpic order. With the total non-inclusion, we again simply have to discard sequences that contain the item d within their red part. We can see in the case of the a¬d e d extension that all combinatorics of itemsets may quickly satisfy all negation constraints. This suggests first to carefully select the appropriate L and second to use a maximum size for negative itemsets to avoid pattern explosion.

Finally, we also notice that extensions with negative items are not terminal recusive steps. Once negative items have been inserted, new positive items can be append to the pattern. We encounter this case with pattern a¬d e which is extended by pattern d.

Experiments

This section presents experiments on synthetic and real data. Experiments on synthetic data aims at exploring and comparing NegPSpan and eNSP for negative sequential pattern mining. The other experiments were conducted on medical care pathways and illustrates results for negative patterns. NegPSpan and eNSP have been implemented in C++. We pay attention on the most significant results. More detailed results can be found in a compagnon website. 3

Benchmark

This section presents experiments on synthetically generated data. The principle of our sequence generator is the following: generate random negative patterns and hide or not some of their occurrences inside randomly generated sequences. The main parameters are the total number of sequences (n, default value is n = 500), the mean length of sequences (l = 20), the number of different items (d = 20), the total number of patterns to hide (3), their mean length (4) and the minimum occurrence frequency of patterns in the dataset (10%).

Generated sequences are sequences of items (not itemsets). For such kind of sequences, patterns extracted by eNSP hold only items because positive partners have to be frequent. For a fair evaluation and preventing NegPSpan from generating more patterns, we restricted L -to the set of frequent items. For both approaches, we limit the pattern length to 5 items.

Figure 2 illustrates the computation time and number of patterns extracted by eNSP and Neg-PSpan on sequences of length 20 and 30, under three minimal thresholds (σ = 10%, 15% and 20%) and with different values for the maxgap constraint (τ = 4, 7, 10 and ∞). For eNSP, the minimal support of positive partners, denoted ς, is set to 70% of the minimal threshold σ. Each boxplot has been obtained with a 20 different sequence datasets. Each run has a timeout of 5 minutes.

The main conclusion from Figure 2 is that NegPSpan is more efficient than eNSP when maxgap constraints are used. As expected, eNSP is more efficient than NegPSpan without any maxgap constraint. This is mainly due to the number of extracted patterns. NegPSpan extracts significantly more patterns than eNSP because of different choices for the semantics of NSPs. First, eNSP uses a stronger negation semantics. Without maxgap constraints, the set of patterns extracted by NegPSpan is a superset of those extracted by eNSP (see proof in Appendix B).

An interesting result is that, for reasonably long sequences (20 or 30), even a weak maxgap constraint (τ = 10) significantly reduces the number of patterns and makes NegPSpan more efficient. τ = 10 is said to be a weak constraint because it does not cut early the search of a next occurring item compare to the length of the sequence (20 or 30). This is of particular interest because the maxgap is a quite natural constraint when mining long sequences. It prevents from taking into account long distance correlations that are more likely irrelevant. Another interesting question raised by this results is the real meaning of extracted patterns by eNSP. In fact, under low frequency thresholds, it extracts numerous patterns that are not frequent when weak maxgap 3. Each node tree represents the pattern on the left and the projected database on the right. Itemsets are in red when the are used to assess future negations while green itemsets are used for sequential ( s ). Dashed arrows represent negative extensions ( n ) while plain arrows are sequential ( s ) or compositional extensions ( c ). Arrow label holds the item that is used in the extension. q q q q q q q q q q q q l=20 l=30 e N S P q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q l=20 l=30 e N S P constraints are considered. As a consequence, the significance of most of the patterns extracted by eNSP seems poor while processing "long" sequences datasets. Figure 2 also illustrates classical results encountered with sequential pattern mining algorithms. We can note that, for both algorithms, the number of patterns and runtime increase exponentially as the minimum support decreases. Also, the number of patterns and the runtime increase notably with sequence length. Figure 3 illustrates computation time and memory consumption with respect to minimum threshold for different settings: eNSP is ran with different values for ς, the minimal frequency of the positive partner of negative patterns (100%, 80% and 20% of the minimal frequency threshold) and NegPSpan is ran with a maxgap of 10 or without. Computation times show similar results as in previous experiments: NegPSpan becomes as efficient as eNSP with a (weak) maxgap constraint. We can also notice that the minimal frequency of the positive partners does not impact eNSP computing times neither memory requirements.

The main result illustrated by this Figure is that NegPSpan consumes significantly less memory than eNSP. This comes from the depth-first search strategy which prevents from memorizing many patterns. On the opposite, eNSP requires to keep in memory all frequent positive patterns and their occurrence list. The lower the threshold is, the more memory is required. This strategy appears to q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q -4 -2 0 2 4 0.1 0.2 0.3

Frequency Threshold log(time) (s) q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 9 10 11 0.1 0.2 0.3

Frequency Threshold log(memory) (kBytes)

q NegPSpan NegPSpan mg=10 eNSP (fp=f) eNSP (fp=0.8 f) eNSP (fp=0.2 f) be practically intractable for large/dense databases.

Experiments on Real Datasets

This section presents experiments on the real datasets from the SPMF repository. 4 These datasets consist of click-streams or texts represented as sequences of items. Datasets features and results are reported in Table 4. For every dataset, we have computed the negative sequential patterns with a maximum length of l = 5 items and a minimal frequency threshold set to σ = 5%. NegPSpan is set with a maxgap τ = 10 and eNSP is set up with ς = .7σ. For each dataset, we provide the computation time, the memory consumption and the numbers of positive and negative extracted patterns. Note that the numbers of positive patterns for eNSP are given for ς threshold, i.e. the support threshold for positive partners used to generate negative patterns.

For the sign dataset, the execution has been stopped after 10 mn to avoid running out of memory. The number of positive patterns extracted by eNSP considering the σ threshold is not equal to NegPSpan simply because of the maxgap constraint.

The results presented in Table 4 confirm the results from experiments on synthetic datasets. First, it highlights that NegPSpan requires significant less memory for mining every dataset. Second, NegPSpan outperforms eNSP for datasets having a long mean sequence length (Sign, Leviathan, and MSNBC ). In case of the Bible dataset, the number of extracted patterns by eNSP is very low compared to NegPSpan due to the constraint on minimal frequency of positive partners.

Case Study: Care Pathway Analysis

This section presents the use of NSPs for analyzing epileptic patient care pathways. Recent studies suggest that medication changes may be associated with epileptic seizures for patients with long term treatment with anti-epileptic (AE) medication [START_REF] Polard | Brand name to generic substitution of antiepileptic drugs does not lead to seizure-related hospitalization: a population-based case-crossover study[END_REF]. NSP mining algorithms are used to extract patterns of drugs deliveries that may inform about the suppression of a drug from a patient treatment. In [START_REF] Dauxais | Discriminant chronicles mining -application to care pathways analytics[END_REF], we studied discriminant temporal patterns but it does not explicitly extract the information about medication absence as a possible explanation of epiletic seizures. Our dataset was obtained from the french insurance database [START_REF] Moulis | French health insurance databases: What interest for medical research[END_REF] called SNIIRAM. 8,379 epileptic patients were identified by their hospitalization identified by their hospitalization related to an epileptic event. For each patient, the sequence of drugs deliveries within the 90 days before the epileptic event was obtained from the SNIIRAM. For each drug delivery, the event id is a tuple m, grp, g where m is the ATC code of the active molecule, g ∈ {0, 1} is the brand-name (0) vs generic (1) status of the drug and grp is the speciality group. The speciality group identifies the drug presentation (international non-proprietary name, strength per unit, number of units per pack and dosage form). The dataset contains 251,872 events over 7,180 different drugs. The mean length of a sequence is 7.89±8.44 itemsets. Length variance is high due to the heterogenous nature of care pathways. Some of them represent complex therapies involving the consumption of many different drugs while others are simple case consisting of few deliveries of anti-epileptic drugs.

Let first compare results obtained by eNSP and NegPSpan to illustrate the differences in the patterns sets extracted by each algorithm. To this end, we set up the algorithms with σ = 14.3% (1, 200 sequences), a maximum pattern length of l = 3, τ = 3 for NegPSpan and ς = .1 × σ the minimal support for positive partners for eNSP. eNSP extracts 1,120 patterns and NegPSpan only 10 patterns (including positive and negative patterns). Due to a very low ς threshold, many positive patterns are extracted by eNSP leading to generate a lot of singleton negative patterns (i.e. a pattern that hold a single negated item). Precisely, we pay attention to the specific specialty of valproic acid which exists in generic form (event 383) or brand-named form (event 114) by selecting patterns that start and finish with event 383. The complete list of these patterns is given in Table 5. Other events correspond to other anti-epileptic drugs (7: levetiracetam, 158: phenobarbital ) or psycholeptic drugs (112: zolpidem, 115: clobazam, 151: zopiclone) except 86 which is paracetamol.

First, it is interesting to note that with this setting, the two algorithms share only 3 patterns p 2 , p 4 and p 5 , which have lower support with NegPSpan because of the maxgap constraint. This constraint also explains that pattern p 3 and p 6 are not extracted by NegPSpan. These patterns illustrate that in some cases, the patterns extracted by eNSP may not be really interesting because they involve distant events in the sequence. Pattern p 1 is not extracted by NegPSpan due to the strict-embedding pattern semantics. With eNSP semantics, p 1 means that there is no delivery of paracetamol and valproic acid at the same time. With NegPSpan semantics, p 1 means that there is no delivery of paracetamol neither valproic acid between two deliveries of valproic acid. The latter is stronger and the pattern support is lower. On the opposite, NegPSpan can extract patterns that are missed by eNSP. For instance, pattern p 8 is not extracted by eNSP because its positive partner, 383, 7, 383 , is not frequent. In this case, it leads eNSP to miss a potentially interesting pattern involving two anti-epileptic drugs. Now, we look at patterns involving a switch from generic form to brand-named form of valproic acid with the following settings σ = 1.2%, l = 3 and τ = 5. Mining only positive patterns extracts the frequent patterns 114, 383, 114 and 114, 114 . It is impossible to conclude about the possible impact of a switch from 114 to 383 as a possible event triggering an epileptic crisis. From negative patterns extracted by NegPSpan, we can observe that the absence of switch 114 ¬383 114 is also frequent in this dataset. Contrary to eNSP semantics which does bring a new information (that can be deduced from frequent patterns), this pattern concerns embeddings corresponding to real interesting cases thanks to gap constraints.

Conclusion and Perspectives

In this article, we investigated negative sequential pattern mining (NSP). It highlights that state of the art algorithms do not extract the same patterns, not only depending on their syntax and algorithms specificities, but also depending on the semantical choices. In this article, we have proposed definitions that clarify the negation semantics encountered in the literature. We have showed that NSP support depends on the semantics of itemset non-inclusion, two possible alternatives for considering negation of itemsets and two manners for considering multiple embeddings in a sequence. This let us point out the limits of the state of the art algorithm eNSP that imposes a minimum support for positive partner and that is not able to deal with embedding constraints, and more especially maxgap constraints.

We have proposed NegPSpan a new algorithm for mining negative sequential patterns that overcomes these limitations. Our experiments show that NegPSpan is more efficient than eNSP on datasets with medium long sequences (more than 20 itemsets) even when weak maxgap constraints are applied and that it prevents from missing possibly interesting patterns.

In addition, NegPSpan is based on theoretical foundations that enable to extend it to the extraction of closed or maximal patterns to reduce the number of extracted patterns even more. Applying recursively this rules we have that for any pattern p there is a path from the empty sequence to it: ∅ * p. We can also notice that there is only one possibility between the three extensions, meaning that these path is unique. This prove that our algorithm is not redundant.

Second, the pruning strategy is correct such that any frequent pattern will be missed. It is given by the anti-monotonicity property.

Let p and p be two patterns such that p p where ∈ { n , s , c }, then is is quite obvious that p p . Let's now consider that p * p from p to p then, by transitivity of , we also have that p p . And then by anti-monotonicity of the support, we have that supp(p) ≥ supp(p ).

Let us now proceed by contradiction and consider that p is a pattern such that supp(p ) ≥ σ but that the algorithm didn't find out. This means that for all paths5 ∅ * p there exist p such that ∅ * p * p with supp(p) < σ. p the pattern that has been used to prune the search exploration of this path to p . This is not possible considering that p * p and thus that supp(p) ≥ supp(p ) ≥ σ. There exists = (e i ) i∈[m] ∈ [n] m s.t. for all i ∈ [n], p i is positive implies p i ∈ s ei and p i is negative implies that for all j ∈ [e i-1 + 1, e e+1 -1], p i / ∈ s j (items only) then p i / ∈ j∈[ei-1+1,ee+1-1] s j i.e. p i ⊆ j∈[ei-1+1,ee+1-1] s j (no matter or ). As a consequence is a strict-embedding of p.

B NegPSpan extracts a superset of eNSP

Proposition 5. Let D be a dataset of sequences of items and p = p 1 , . . . , p m be a sequential pattern extracted by eNSP, then without embedding constraints p is extracted by NegPSpan with the same minimum support.

Proof. If p is extracted by eNSP, it implies that its positive partner is frequent in the dataset D. As a consequence, each p i , i ∈ [m] is a singleton itemset.

According to the search space of NegPSpan defined by if p is frequent then it will be reached by the depth-first search. Then it is sufficient to prove that for any sequence s = s 1 , . . . , s n ∈ D such that p occurs in s according to eNSP semantic (strict-embedding, strong absence), then p also occurs in s according to the NegPSpan semantics (soft-embedding, weak absence). With that and considering the same minimum support threshold, p is frequent according to NegPSpan. Proposition 4 gives this result.

Then we conclude that NegPSpan extracts more patterns than eNSP on sequences of items. In fact, NegPSpan can extract patterns with negative itemsets larger than 2.

eNSP extract patterns that are not extracted by NegPSpan on sequences of itemsets. Practically, NegPSpan uses a size limit for negative itemsets ν ≥ 1. eNSP extracts patterns whose positive partners are frequent. The positive partner, extracted by PrefixSpan may hold itemsets larger than ν, and if the pattern with negated itemset is also frequent, then this pattern will be extract by eNSP, but not by NegPSpan.

Definition 3 (

 3 positive pattern embedding). Let s = s 1 . . . s n be a sequence and p = p 1 . . . p m be a (positive) sequential pattern. e = (e i ) i∈[m] ∈ [n] m is an embedding of pattern p in sequence s iff ∀i ∈ [m], p i ⊆ s ei and ∀i ∈ [m -1], e i < e i+1 Definition 4 (Strict and soft embeddings of negative patterns). Let s = s 1 . . . s n be a sequence and p = p 1 . . . p m be a negative sequential pattern. e = (e i ) i∈[m] ∈ [n] m is a soft-embedding of pattern p in sequence s iff ∀i ∈ [m]:

Example 1 (

 1 Itemset absence semantics). Let p = a ¬(bc) d be a pattern and four sequences: Sequence / strict-embedding / soft-embedding s 1 = a c b e d s 2 = a (bc) e d s 3 = a b e d s 4 = a e d

Example 2 (

 2 Strict vs soft occurrence semantics). Let p = a b ¬c d be a pattern and s 1 = a b e d and s 2 = a b c a d e b d be two sequences. The positive part of p is a b d . It occurs once in s 1

s a b n a ¬e b s a ¬e b c c a ¬e

  b (ce) s a ¬e b (ce) a n a ¬e b (ce) ¬b a n a ¬e b (ce) ¬(bd) a . Secondly, according to proposition 2, the pruning strategy is correct.

Figure 1 :

 1 Figure 1: Example of tree search of the NegPSpan algorithm of dataset of Table3. Each node tree represents the pattern on the left and the projected database on the right. Itemsets are in red when the are used to assess future negations while green itemsets are used for sequential ( s ). Dashed arrows represent negative extensions ( n ) while plain arrows are sequential ( s ) or compositional extensions ( c ). Arrow label holds the item that is used in the extension.

  N e g P S p a n n o c o n s tr a in t N e g P S p a n τ

Figure 2 :

 2 Figure 2: Comparison of number of patterns (left) and computing time (right) between eNSP and NegPSpan, with different values for maxgap (τ ). Top (resp. bottom) figures correspond to database with mean sequence length equal to 20 (resp. 30). Boxplot colors correspond to different values of σ (10%, 15% and 20%).

Figure 3 :

 3 Figure 3: Comparison of computing time (left) and memory consumption (right) between eNSP and NegPSpan wrt minimal support.

•

  if the last itemset of p is such that |p m | == 1 and p m-1 is positive then we define p = p 1 . . . p m-2 p m : then p s p • if the last itemset of p is such that |p m | == 1 and p m-1 is negative (non-empty) then we define p = p 1 . . . p m-1 p m where p m-1 is such that |p m-1 | = |p m-1 | -1 and p m-1 ⊂ p m-1 : then p n p

Proposition 4 .

 4 Soft-embedding =⇒ strict-embedding for patterns consisting of items.Proof. Let s = s 1 , . . . , s n be a sequence and p = p 1 , . . . , p m be a NSP s.t. each ∀i, |p i | = 1 and p occurs in s according to the soft-embedding semantic.

Table 1 :

 1 Lists of supported sequences in D by negative patterns p i , i = 1..4 under the total and partial non inclusion semantics. Every pattern has the shape a ¬q i b where q i are itemsets such that q i ⊂ q i+1 .

		partial	total
		non inclusion	non inclusion
	p 1 = b¬ca	{s1, s3, s4}	{s1, s3, s4}
	p 2 = b¬(cd)a	{s1, s2, s3, s4}	{s1, s4}
	p 3 = b¬(cde)a	{s1, s2, s3, s4}	{s1}
	p 4 = b¬(cdeg)a	{s1, s2, s3, s4, s5}	{s1}
		monotonic	anti monotonic

Table 2 :

 2 Comparison of negative pattern mining proposals. Optional constraints are specified in Italic.

		PNSP [6]	NegGSP	eNSP [1]	NegPSpan
			[19]
	negative elements	itemsets	items?	itemsets	itemsets
	itemsets	?
	embeddings	strict	strict?	strict	strict/soft
	occurrences	soft	soft	strict	soft
	constraints on negative itemsets not too in-	frequent	positive part-	frequent
		frequent	items	ner is fre-	items,
		(supp		quent	bounded size
		less f req)
	global constraints on patterns			positive	maxspan,
				part is fre-	maxgap
				quent (sec-
				ond greater
				threshold)

Table 3 :

 3 Dataset of sequences used in the execution example.

	SID Sequence
	s 1	a c b e d
	s 2	a (bc) e
	s 3	a b e d
	s 4

Table 4 :

 4 Results on real datasets with setting σ = 5%, l = 5, τ = 10, ς = .7σ. Bold faces highlight lowest computation times or memory consumptions.

			Dataset			NegPSpan			eNSP
		|D|	|I|	length	time (s) mem (kb) #pos	#neg	time (s)	mem (kb)	#pos	#neg
	Sign	730	267	51.99	15.51	6,220	348 1,357,278	349.84 (!) 13,901,600 1,190,642 1,257,177
	Leviathan	5,834	9,025	33.81	6.07	19,932	110	39797	28.43	428,916	7,691	17,220
	Bible	36,369 13,905	21.64	38.82	68,944	102	43,701	27.38	552,288	1,364	2,621
	BMS1	59,601	497	2.51	0.16	22,676	5	0	0.18	34,272	8	7
	BMS2	77,512	3,340	4.62	0.37	39,704	1	0	0.35	53,608	3	2
	kosarak25k	25,000	14804	8.04	0.92	24,424	23	409	0.53	43,124	50	51
	MSNBC	31,790	17	13.33	40.97	41,560	613	56,418	41.44	808,744	2,441	5,439

Table 5 :

 5 Patterns involving valproic acid switches with their supports computed by eNSP and NegPSpan.

	pattern	support eNSP	support NegPSpan
	p 1 = 383 ¬(86, 383) 383	1,579
	p 2 = 383 ¬86 383	1,251	1,243
	p 3 = 383 ¬112 383	1,610
	p 4 = 383 ¬114 383	1,543	1,232
	p 5 = 383 ¬115 383	1,568	1,236
	p 6 = 383 ¬151 383	1,611
	p 7 = 383 ¬158 383	1,605
	p 8 = 383 ¬7 383		1,243

Called the maximal positive subsequence in PNSP and Neg-GSP or the positive element id-set in eNSP.

Actually, though not clearly stated, it seems that the negative elements of Neg-GSP patterns consist of items rather than itemsets. In this case, total and partial inclusion are equivalent.

Code, data generator and synthetic benchmark datasets can be downloaded here: http://people.irisa.fr/ Thomas.Guyet/negativepatterns/.

http://www.philippe-fournier-viger.com/spmf/index.php?link=datasets.php

Note that we proved that this path is actually unique.

Acknowledgments

The authors would like to thank REPERES Team from Rennes University Hospital for spending time to discuss our case study results.

A Proofs

Proof of Proposition 1. Let s = s 1 , . . . , s n be a sequence and p = p 1 , . . . , p m be a negative sequential pattern. Let e = (e i ) i∈[m] ∈ [n] m be a soft-embedding of pattern p in sequence s. Then, the definition matches the one for strict-embedding if p i is positive. • ∀i, e i+1 > e i (embedding), e i+1e i ≤ θ (maxgap) and e ke 1 ≤ τ (maxspan),

• ∀i, p i ⊆ s ei ,

To prove that p s, we prove that (e i ) i∈[k] is an embedding of p in s.

Let us first consider that k = k , then by definitions of and the embedding,

], q j s ei , and thus q j s ei (because of anti-monotonicity of and q i ⊆ q i)

In addition, maxgap and maxspan constraints are satisfied by the embedding, i.e. Let us now consider that k > k, (i), (ii) and (iii) still holds, and we have in addition that e k < e k (embedding property), then e ke i < θ. This means that (e i ) i∈[k] is an embedding of p in s.

Proof of proposition 3 (Complete and correct algorithm). The correction of the algorithm is given by lines 2-3 of Algorithm 1. A pattern is outputted only if it is frequent (line 2).

We now prove the completeness of the algorithm. First of all, we have to prove that any pattern can be reached using a path of elementary transformations ( ∈ { n , s , c }). Let p = p 1 . . . p m be a pattern with a total amount of n items, n > 0, then it is possible to define p such that p p where ∈ { n , s , c }, and p will have exactly n -1 items:

• if the last itemset of p is such that |p m | > 1 we define p = p 1 . . .


Modeling of a pragmalinguistics analysis of a discussion forum

Keywords: Traceability, Knowledge Engineering, Humanknowledge Interaction, Interactions analysis, Pragmatics, linguistics

In this paper we present, a modeling of an expertise in pragmatics. We follow knowledge engineering techniques and observe the expert when he analyses a social discussion forum. Then a number of models are defined. These models emphasize the process followed by the expert and a number of criteria used in his analysis. Results can be used as guides that help to understand and annotate discussion forums. We aim at modeling other pragmatics analysis in order to complete the base of guides; criteria, process, etc. of discussion analysis

I. INTRODUCTION

This study is a part of a pluridisciplinary research project driven in the Tech-CICO laboratory1 . Our work meets the ever-increasing need for development of a transdisciplinary methodology of digital corpora 2 management and analysis. In this sense, our main objective is to facilitate sharing and analysis of corpora between specialists in communicative interaction. We are not aiming to create one (too) more hyper interaction model (theory) but to provide an operative framework to an empirical analysis of authentic data by respecting the specificity of each chosen discipline. Our starting point is the description of real practices of constitution and analysis of corpora in interaction disciplines in order to find the appropriate method of human scientists' knowledge capitalization through corpora and corpora interpretation charring.

A. Context of the study

The specific practices of research in human sciences we have observed are mainly characterized as qualitative [START_REF] Miles | Qualitative Data Analysis: An Expanded Sourcebook[END_REF]. (1) We have to deal with descriptive and\or comprehensive practices of analysis in which the process of corpora structures elaborating is a part of the interpretative work of the scholar who made pair evaluation [Have, 1986]. (2) Usually researchers don't make use of big technical equipment and a very large amount of data. On the contrary, detailed handmade analysis often is observed (3) Detailed analysis is made through tools heavily influenced by the culture of the field. (4) Contrary to the practices on corpus linguistics [START_REF] Mcenery | Corpus Linguistics[END_REF], which aims a very strong generalization of results, analysis performed in the Interactional Linguistics field, for example, are local, situated, and dependent on analysts expertise [Mondada, 2006]. Several questions arise about corpus sharing and collaborative analysis: Are these possible? What are the best conditions? And finally, how can we support sharing and circulation of corpora and comments on them between several researchers in these conditions?

For the need of the study we developed a methodology, in order to describe and understand sociological, psychological and linguistic interpretations of verbal interactions and the conditions of theirs exchanges. This methodology combines ethnographic enquiry and knowledge engineering. The stages of our research include: (1) An initial comparative analysis of theoretical pattern of verbal communicative interaction, the chosen criteria being: applied models, aim, granularity of analysis, data approach, etc; (2) A study of real practices of interaction data gathering and analysis which are done in three disciplines: psychology, sociology and pragmatics. Our main approach is internal investigation [START_REF] Atifi | Méthodologie transdisciplinaire de gestion du corpus pour les disciplines de l'interaction : recherche de principes directeurs[END_REF]. These interviews also revealed the tension between the obvious need for cooperation among different researchers around the understanding of the communicative interactions and the difficulties of setting data sharing. (3) We compare the results of the previous investigation with the observations of concrete cases of collaboration between scientists interested in workplace communication: for example we have investigated the complementary work of two researchers, a pragmatic linguist and a sociologist of organizations, both dealing with documents creation, use and circulation in a telecom company. (4) In order to complete the results of this investigation, we used a modeling of analysis practices of communicative interaction [START_REF] Sidoummou | La modélisation d'un savoir faire lors d'une interaction conversationnelle médiatisée[END_REF]. This modelling is based on the approaches related to the knowledge management field.

ICD/Tech-CICO, Université de Technologie de Troyes Goritsa Ninova, Hassan Atifi

In this paper we focus on some results of stage 4. We chose to present our modeling of an analysis whose object is a socially orientated discussion forum3 . We report the choice of models, the protocol of the study and the modeling we are obtaining using CommonKADS methodology. The objective of this modeling is to highlight certain techniques followed in pragmalinguistic analysis of discussion forums. We observed a pragmalinguistics researcher in his work and we modeled the steps to set up script types of interactions in a discussion forum4 . The models defined will be used to provide elements in order to define guides for tags definition and other type of metadata facilitating comprehension of mediated interactions.

B. Pragmatics of interactions

Pragmatics of interactions, also called interactions analysis, is a new multidisciplinary approach, a synthesis of various disciplines whose object of study is primarily language in situations [Kerbrat-Orecchioni 1998]:

 New communication: transdisciplinary Anglo-Saxon approach that developed in the psychosocial sciences: ethnography of communication, ethnomethodology, Palo Alto School, etc.

 Pragmatics: born with the work of Austin and Searle, which made a radical break with Chomskyan linguistics [START_REF] Searle | Expression and Meaning : Structures and Theory of Speech Acts[END_REF]. [START_REF] Austin | How to do things with Words[END_REF].

The beginning of the pragmatics of interactions is recent. It is the result of a double movement which affected psychosocial sciences during the early 1960s, and linguistics from the 1970s:  Progressive breakdown of boundaries between traditional disciplines that deal with language in context (anthropology, sociology, psychology). These American researchers have shown the weakness of autonomous disciplines to properly handle the language in context. "Social scientists asking relevant questions have usually not had the training and insight to deal adequately with the linguistic face of the problem. Linguistics, the discipline central to the study of speech, has been occupied almost wholly with developing analysis of the structure of language as a referential code, neglecting social meaning, diversity, and use." [Hymes, 2003].

 Evolution of traditional linguistics towards a

new oral, pragmatic and communicative linguistics. This change relates primarily to two dimensions of the language: its communicative vocation of exchange and dialogue and its behavioral and pragmatic nature. Pragmatics of interactions values a sociolinguistic perspective of the object of studies by asking the question: Who speaks? With whom? About what? When? Where? How? And Why? This approach develops an ethnographic methodology based on the exchanges observation, description and interpretation of the exchanges. One of the branches of pragmatics of interactions is conversation analysis. This is about producing a thorough study of what happens in verbal interaction with focus on the sequential organization of turns of speech.

C. Our positioning

We are interested in the way the expert applies these theories on his corpora analysis according to research subject. It is important to understand that the applied theories are chosen by a well noun expert of computermediated communication (CMC). We want to know how this expert makes choice of theories according to the corpus specificity, the research topic and his experiential knowledge. We think that the knowledge engineering modeling methods may give us some answers to this question.

The originality of our approach presented in this article is in application of a modeling from knowledge engineering to a scientific work characterized by a qualitative approach. To do this, we needed to apply a top-down method offering a library of templates (models) for modeling analytic tasks. From these models we can interpret the data collected from experts.

CommonKADS is a standard for Knowledge Based Systems (KBS) in Europe. We have chosen to ease it offers in the task of knowledge elicitation and reasoning used.

II. ANALYSIS FRAMEWORK

The pragmalinguistics researcher "Michel Marcoccia" analyzed extracts from the forum Doctissimo 5 were messages requesting social support. This analysis was carried out in collaboration with "Nadia Gauducheau", a cognitive psychology researcher. Michel Marcoccia's aim is to provide corroboration for analysis through psychosocial theories regarding social support request messages. He has as main aims on the one hand, to validate the psychosocial categories on the exchanges of social support and on the other hand, to define standard scripts for each category [START_REF] Gauducheau | Le soutien social dans les forums de discussion : réalisation interactionnelles et contrats de communication[END_REF].

The extracts of exchanges corresponded mainly to a request (the initial post of the thread) and discussions concerning this request (the displayed list of the other posts). As an example of these exchanges, we can quote: exchanges on the addiction to drugs or exchanges about allergies to milk, etc. Titles of these exchanges correspond of threads' titles.

Discussions on addiction to drugs:

Orchidée Noire kikou, Voilà je me lance enfin à ouvrir mon premier post. Ca fait des semaines que j'erre sur le forum, poste des messages par-ci, par-là, mais je n'arrive pas à me poser.

Je ne connais encore que très peu de personnes, donc je vais faire une p'tite présentation : J'ai 33 ans et je suis .... Après avoir consommé pas mal de produits, j'ai fini par trouvé mon bonheur (et mon malheur aussi) dans l'héro... à laquelle je suis dépendante maintenant depuis 8 ans. [ …] Je suis aussi dépressive et hyper-angoissée. Quand j'arrête, je prends conscience de la réalité et ca m'est insupportable.

Je ne demande rien, je me sens seule avec mes problèmes. Vous pouvez venir ici pour me parler, me raconter votre histoire ou juste pour dire ce que vous avez sur le coeur...

Amicalement,

Profil

sup primé Bienvenue Orchidée.

Je ne suis pas très loquace aujourd'hui, mais je connais bien le problème de l'héro.

Je suis encore loin de m'en être "débarrassée", bref ... Si j'ai un peu de courage plus tard, lolll.

5 http://forum.doctissimo.fr/ This forum is part of an extremely popular French website dedicated to health information, Doctissimo. This forum is considered by researcher as a forum where the charring information activity is central: the displayed aim of Doctissimo, the exchange of medical information is announced upon entry into the site.

Encore bienvenue et @+ Marie

DianaC

Bonjour, désolée, je ne connais pas ton problème, mais si c'est un appui ou une écoute que tu cherches, je t'ai lue.

Je te souhaite bon courage, pour moi c'est l'alcool et le shit (en conso excessive et "famélique" ).

Voilà. Psychosocial categories used in this analysis are: requests for emotional support, request for sharing experiences, request for evaluation, and request for informational support and for advice. The categories are derived from psychological and sociological theories about the forms of social support [START_REF] Gauducheau | Le soutien social dans les forums de discussion : réalisation interactionnelles et contrats de communication[END_REF].

Diana

III. OBSERVATION OF THE ANALYSIS

We used knowledge engineering techniques to analyze and model the expertise of forum analysis. Knowledge Engineering (KE) provides essentially a process of analysis and modeling of problem solving [START_REF] Charlet | L'ingénierie des connaissances, Développements, résultats et perspectives pour la gestion des connaissances médicales[END_REF], [START_REF] Aussenac-Gilles | Acquisition et Ingénierie des connaissances, Tendances Actuelles[END_REF]. Methodological guides are given in this discipline. These guides make possible to collect an expertise and to model it in order to highlight the "why", "what" and "how" of a behavior.

4

In our case, we followed knowledge engineering method of collecting and modeling. We observed the analysis activity performed by the pragmalinguistics expert following a well-established scenario based on ergonomics' activity observing techniques. The first step is to clearly identify the objective of the task to be observed, followed by a series of observations, and an analysis of the observations in order to define a set of behavioral patterns, the final stage to be performed being a validation of those observations with the expert in pushing him to explain the reasons of his behavior.. We alternated observations with validation and explanation interviews in order to progressively understand the reasons of the expert's behavior at each stage of analysis IV. MODELING OF THE ANALYSIS The reasoning followed by the researcher expert in pragmalinguistics, is mainly abduction oriented. In fact, he analyses a sample of messages on social support requests, he makes a number of assumptions in the form of scripts of analysis and finally he validates these assumptions' application on other scripts (Figure 2). If we look more closely at researcher's scripts identifying analysis, we find out that he proceeds by a series of assessments based on pragmalinguistics theories [Kerbrat-Orecchioni, 1998], [Hymes, 2003]. These theories serve him as the criteria in his analysis. The generic CommonKADS assessment model [Breuker et al., 1984] defined in knowledge engineering enabled us to identify that the expert establishes classes of decisions (which are scripts relative to each type of request) on the basis of standard models. Once the interactions are cut out into threads (request, replies and replies to replies), he compares the thread with the standard models by using the criteria of analysis (Figure 3.). We note that this analysis is done in a manual way. While analyzing the messages, he seeks at the same time to identify those nonclassable in the identified categories or which are exceptions scripts. That allows him to state new hypotheses on social support message boards. In our modeling we studied the detailed analysis of the messages. After identifying the outline of his reasoning and the criteria he uses, we observed how the researcher proceeds in his analysis for cutting out interactions and establishing scripts. We present in illustrations the traces of the drafts of his analysis in order to show the steps that he follows

D. The used pragmalinguistics criteria

E. Exchanges analysis performed by the expert

The interactions are cut out in the thread of exchanges corresponding to each request. Each thread includes a request and the replies to this request. The thread is then quickly analyzed in order to identify its type: Request for Emotional Support, Request for Information, Request for Advice or Request for Sharing Experiences, etc. The request is then analyzed in order to identify its type and various indices such as: recipients of the request, [START_REF] Gauducheau | Le soutien social dans les forums de discussion : réalisation interactionnelles et contrats de communication[END_REF].

The reactions to the message are then analyzed to identify its canvass: terms of address, greetings and signatures, setting forms (Smiley, etc...) sayings and proverbs. Then, other indices are identified by the expert according to the contents of reactions. For example, some types of reactions were identified as: encouragement and compliments, criticisms and disagreements, advice and contributions to the information, evaluation of the situation and request additional information, evaluation of the expertise and sharing close experience etc.

F. Interactions scripts identification performed by the expert

Once the exchanges trade are analyzed, the expert draws up a cross grid (Fig. 5) in order to identify scripts by request type. This grid allows to first identify recurring indices in each type of request, and then validate the scripts by analyzing some others threads of exchange in order to validate its assumptions.

The researcher notes for example, by analyzing the grid crossed above that the requests of the emotional support type are characterized by a detailed selfpresentation and a description of the anticipated benefits while in the other types of support requests, it is rather the problem which is more detailed in detriment of a personal presentation and benefit. In the same way, the researcher notes that in the experience sharing, a personal presentation and a presentation of the problem are well cared for.

V. STATEMENT OF THE MODELING

The aim of the modeling of this expertise is to highlight, on the one hand, the type of reasoning by the expert and on the other, to observe indices and criteria used in its reasoning. These indices can help thereafter the analysis and the understanding of other interactions of the same type, the mutual aid.

We have found that the followed reasoning is a continuous assessment at several levels:  Cutting out the interactions into sequences of messages.  Identification of the queries types: In this case, types of psychosocial criteria are used: query for assessment, query for information support and for advice, etc.  Definition of scripts: pragma-linguistics indices related to the structure of the messages are used. These indices follow well defined scripts: Greeting, introducing oneself, recipient of the message, presenting the problem, explanation of the request or response, signature and fence.  Classification of the interactions: pragmalinguistics indices related to the contents of the messages are exploited. We can mainly quote: encouragement and compliments, criticisms and disagreements, advice and contributions of information, assessment of the situation and complementary information request, evaluation of the expertise and similar experiences sharing.

VI. CONCLUSION

The researchers in pragmalinguistics study the interactions in order to understand the mechanisms which govern these interactions. They have developed techniques and criteria to guide the analysis of these interactions.

We modeled an analysis of a discussion forum performed by a pragmalinguistics researcher in order to highlight the selection and the use of these criteria. Our goal is to provide guides for analyzing and understanding the interactions in a discussion forum, for example: to help define tags and other metadata to facilitate understanding of the interactions. Answering to three questions -what, how and why, this modeling proves to be very useful for the practices understanding mentioned above, as well as the initiation of reflexive posture from researchers.

We studied the analysis of a precise type of messages which is the social support. The theories mobilized in this analysis also concern social psychology. We showed the specific scripts dedicated to this type of interaction. We modeled another expertise of pragmalinguistics analysis of the interactions concerning the evaluation of an activity of a company. Certain criteria like the personal presentation and the greetings are the same ones, but the contents analysis requested other criteria in direct relationship with the speech acts.

Compared to ethnographic investigation the contribution of the knowledge engineering methodology have played its role -to reveal procedural knowledge, in opposition to prescribed knowledge in manuals that appears in some discourse during interviews. This methodology is also very useful to the aim of supporting knowledge sharing, especially about representing reference knowledge, implemented in each individual analysis. This is only the preliminary stage of our study and we plan to complete and extend to other types of interaction in order to determine the criteria employed and the corresponding scripts for each type of interaction. We plan to consolidate all of these guides in a support tool for the charring analysis and understanding of the interactions in discussion forums. The way we try to explore is to memorize traces of each analyze and follow evolution of these traces replicated by another researcher and applied to another corpus.

Fig. 2 .

 2 Fig. 2. Analyses of interactions.

Fig. 3 .

 3 Fig. 3. Assessment of interactions threads .

Fig. 4 .

 4 Fig. 4. Assessment of interactions threads

Fig. 5 .

 5 Fig.5. Cross grid of initiative messages

  take the plunge and start my first post. I have been lurking on this board for weeks, I have posted replies, without setting my own thread though. I only know a few persons, so I thought I'd introduce myself: I am 33 and I am a… After having consumed loads of different stuff, I finally found happinessand misery toowith heroin, to which I have been addicted for 8 years now.[…] I am depressive and hyper anxious as well. As soon as I stop taking it, I see reality and can't cope with it. I am not asking for anything, I feel I am alone with my problems. You can come here to just have a chat, share you own story or get off your chest whatever you need to… I am not in a talkative mood today, but I do know about heroin problems.Iam myself far from being rid of it, so… See you later, if I get the courage, lolll. Welcome to the forum, see you, Marie DianaC Hello, I am sorry, I am not familiar with such problems, but if it is support or a sympathetic ear you are looking for, I am here to read. I wish you strength, my own problem is alcohol and weed (excessive compulsive consumption). What I mean is that I thought that my diet had to do with the acne I still have in spite I am 22 years of age. Although I don't eat much greasy food, I often have rashes on the forehead, temples, they just come out, with no apparent reason [...] go It is difficult to say whether dairy products are responsible for acne, but that could be easily the case with certain persons […] joely Hello, I am almost convinced that milk, in particular cow milk, is bad for your health. A common misconception, probably diffused by certain influent circles, is that it is rich in calcium […]

	VII. APPENDIX 1: English translation of exchanges Discussions on addiction to drugs: Orchidée Noire Hi all, I decided to Best, Welcome Orchidée, That is for now. Diana Take care! Discussions on milk allergies: Profile deleted cartoon181 Hi all, I wonder whether I have an intolerance to dairy products (no idea which ingredients though).

Tech-CICO is a laboratory who associate humanities and computer scientists, in particular concerning professional organization oriented intervention research. For more information see http://tech-cico.utt.fr/

The research we observed is part of a pluridicsiplinary project of analysis of discussion forum. The common topic of studies is online social support.

In this paper, we use the term "discussion forum "to refer to "message board ".

For a translation, see Appendix 1.