Yann Dauxais
email: yann.dauxais@irisa.fr

David Gross-Amblard

Thomas Guyet
email: thomas.guyet@irisa.fr

André Happe
email: andre.happe@chu-brest.fr

Discriminant chronicle mining

Sequential pattern mining attempts to extract frequent behaviors from a sequential dataset. When sequences are labeled, it is interesting to extract behaviors that characterize each sequence class. This task is called discriminant pattern mining. In this paper, we introduce discriminant chronicle mining. Conceptually, a chronicle is a temporal graph whose vertices are events and whose edges represent numerical temporal constraints between these events. We propose DCM, an algorithm that mines discriminant chronicles. It is based on rule learning methods that extract the temporal constraints. Computational performances and discriminant power of extracted chronicles are evaluated on synthetic and real data. Finally, we apply this algorithm to the case study consisting in analyzing care pathways of epileptic patients.

Introduction

Discriminant pattern mining is dedicated to the mining of patterns in structured and labeled examples. Discriminant patterns can be used to label new examples and also inform about the specific characteristics of examples with a given label. In this work, examples are labeled temporal sequences. A temporal sequence is made of timestamped events and the label is assigned to sequence itself. Our objective is not to predict future events but to assign a label to a sequence. This latter task is also called sequence classification: each label can be seen as a class of sequences, and predicting the label is determining to which class a new sequence belongs.

Sequence classification can be encountered in numerous application fields: comparing groups of clients (e.g., large family vs single child family), analyzing data related to supermarket purchases, identifying behavior of customers (who churns vs loyal customers), etc. Our application field is the analysis of care pathways, i.e. sequences of medical events of a patient (drug deliveries, hospital stays, etc.): we would like to characterize care pathways specificities for patients who have a disease. The objective is to identify therapeutic sequences that may foster diseases or to retrieve these patients in large unlabeled datasets. In all these contexts, the temporal dimension may hold the key information to discriminate sequences from one class to the other. For instance, a short delay between the delivery of two adverse drugs may help discriminate patients, sick from healthy patients. This is especially important for clinicians. By taking quantitative temporal constraints into account, we aim at improving classification accuracy, but discriminant patterns will also provide better insights about the therapeutic sequences.

Discovering such patterns raises important challenges both in the fields of pattern mining and machine learning. On the one hand, pattern mining approaches are based on a (exhaustive) search strategy in a structured version space. Our objective is to discover quantitative temporal information. This generates too large a search space for applying classical approaches. On the other hand, machine learning algorithms have difficulties to handle structured data such as sequences. As a consequence, we propose a specific pattern model and a new approach that combines solutions from these two research fields.

In this article, we explore temporal patterns called chronicles [START_REF] Dousson | Discovering chronicles with numerical time constraints from alarm logs for monitoring dynamic systems[END_REF]. A chronicle is a set of events linked by quantitative temporal constraints. In constraint satisfaction domain, chronicle can be seen as temporal constraint network [START_REF] Dechter | Temporal constraint networks[END_REF]. These complex but highly expressive patterns enable to take into account the quantitative temporal dimension of the data contrary to classical sequential patterns.

The contribution of this article is threefold:

1. We propose a new setting of mining discriminant chronicle from labeled sequences of timestamped events. 2. We propose the DCM algorithm, which relies on a rule learning algorithm to extract discriminant temporal constraints. To the best of our knowledge, this is the first approach that extracts discriminant patterns with quantitative temporal information. 3. We evaluate the DCM algorithm with a real case study, which consists in analyzing care pathways to answer a pharmaco-epidemiological question.

The remaining of the article is organized as follows. Next section presents related works. The section 3 introduces the discriminant chronicle mining task, while section 4 presents the DCM algorithm, our solution for this task. Section 5 presents how to take decision from a set of chronicles. Sections 6 and 7 evaluate the DCM algorithm. After a first round of experiments on synthetic data, we compare the results of discriminant chronicles in classification context with those of the discriminant sequential patterns [START_REF] Fradkin | Mining sequential patterns for classification[END_REF] on UCI datasets. Finally, we apply the DCM algorithm in order to extend the analysis of [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]. It aims at identifying possible associations between hospitalizations for a seizure and anti-epileptic drug switches from care pathways of epileptic patients.

Related work

Temporal pattern mining is a research field that proposes, and studies, algorithms to extract interesting patterns from temporal data. Such techniques have been mostly used in the medical application field.

Since the early articles on pattern mining [START_REF] Agrawal | Mining sequential patterns[END_REF], most temporal pattern mining approaches have been focused on mining frequent patterns. Such method can be organized according to the temporal nature of the patterns they extract. Sequential patterns only takes the order of the events into account. Numerous works are based on this type of pattern and we refer the reader to existing reviews to have a wide scope of this field [START_REF] Mabroukeh | [END_REF]Ezeife, 2010, Mooney and[START_REF] Mooney | [END_REF]. Sequential pattern mining has been used in [START_REF] Wright | The use of sequential pattern mining to predict next prescribed medications[END_REF] to identify temporal relationships between drugs. These relationships help to predict which medication a prescriber is likely to choose next. The total sequential order defined on the itemset of a sequential pattern may be too constrained to extract some recurrences in a sequence set. Some patterns like episodes ( [START_REF] Mannila | Discovery of frequent episodes in event sequences[END_REF] when extracted from data streams) or partially ordered patterns [START_REF] Fabrègue | Orderspan: Mining closed partially ordered patterns[END_REF] (when extracted from sequence set) were proposed to relieve this constraint. In [START_REF] Achar | A unified view of the apriori-based algorithms for frequent episode discovery[END_REF], a framework is proposed to generalize and unify the different algorithms dedicated to frequent episodes mining based on the Apriori framework. Temporal rules [START_REF] Concaro | Mining healthcare data with temporal association rules: Improvements and assessment for a practical use[END_REF], Berlingerio et al., 2007], or more complex patterns like chronicles [START_REF] Dousson | Discovering chronicles with numerical time constraints from alarm logs for monitoring dynamic systems[END_REF], Cram et al., 2012, Huang et al., 2012, Alvarez et al., 2013], model inter-event duration based on the event timestamps. Chronicles have been originally introduced by Dousson and Duong [START_REF] Dousson | Discovering chronicles with numerical time constraints from alarm logs for monitoring dynamic systems[END_REF]. [START_REF] Cram | A complete chronicle discovery approach: application to activity analysis[END_REF] proposed a complete algorithm to extract chronicles. These patterns have been used in the medical field [START_REF] Huang | On mining clinical pathway patterns from medical behaviors[END_REF], Alvarez et al., 2013]. Finally, time interval patterns [Moskovitch andShahar, 2015, Guyet andQuiniou, 2011] capture patterns with typical timestamps and duration of events. Unlike the previous types of patterns, the search space size of such classes of pattern and the notion of a typical pattern does not allow to define complete algorithms. Unlike sequential patterns with numerical temporal constraints, such as maxgap ou maxspan [START_REF] Pei | Mining sequential patterns with constraints in large databases[END_REF], these approaches discover the numerical temporal characteristics of a pattern.

For large datasets, the number of temporal patterns may be huge and many of them not interesting. Extracting fewer but more significant patterns, becomes the goal in this case. The first research directions specified additional constraints on the expected sequential patterns [START_REF] Pei | Mining sequential patterns with constraints in large databases[END_REF] including constraints on patterns (e.g., pattern length constraints), on their occurrences (e.g., area constraints) or on the pattern set (e.g., the closed pattern constraint). More recent approaches try to use soft constraints, such as preferences, instead of hard constraints. For example, in [START_REF] Lakshmanan | Investigating clinical care pathways correlated with outcomes[END_REF], the temporal patterns are ranked according to their correlation with a particular patient outcome. It enables the expert to identify the potentially most interesting patterns easily. Nonetheless, they are not less numerous.

Mining discriminant sequential pattern can be seen as an additional hard constraint on the expected patterns. Several definitions, related to the notion of discrimination, have been proposed. [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF] gathered these approaches, including emerging patterns [START_REF] Dong | Efficient mining of emerging patterns: Discovering trends and differences[END_REF], contrast patterns [START_REF] Bay | Detecting group differences: Mining contrast sets[END_REF], subgroup discovery [START_REF] Herrera | An overview on subgroup discovery: foundations and applications[END_REF] and more recently Exceptional Model Mining [START_REF] Duivesteijn | Exceptional model mining[END_REF]. All these approaches have been explored for itemset mining and can be easily extended to sequential pattern mining. But extracting quantitative temporal constraints becomes too complex when applying the same complete strategy. In our framework, the discrimination constraint is based on the growth rate of pattern frequency, which is similar to the emerging pattern approach.

Compared to all studies on frequent temporal data mining, there are only few proposals to mine discriminant temporal patterns. The early but solely approach uses inductive logic to extract patterns with quantified inter-event duration [START_REF] Quiniou | Application of ILP to cardiac arrhythmia characterization for chronicle recognition[END_REF]. This approach requires expert knowledge to bound the search space. Indeed, the event types and a qualitative description of the boundaries (e.g., short, normal or long) are specified by the user.

An alternative approach for learning how to label sequences is pattern-based classification [START_REF] Bringmann | Pattern-based classification: a unifying perspective[END_REF]. In this approach, patterns are extracted and then used as features to create a dataset representing sequences by pattern occurrences. The correlation between sequence labels and pattern occurrences is learned by a (standard) classifier, such as a SV M classifier. Uninteresting (e.g., redundant) patterns may be removed before the classification task in order to improve the prediction accuracy. [START_REF] Batal | A temporal pattern mining approach for classifying electronic health record data[END_REF] proposed to use discriminant temporal pattern as potentially interesting subset of frequent patterns. Their temporal patterns, called minimal predictive temporal patterns, are couples made of an itemset and Allen's temporal relations constraining the itemset occurrences [Allen, 1984]. The principle of minimal predictive temporal pattern selection is to compare a pattern P with those included in it to prune the search tree if P is predictive enough. In [START_REF] Fradkin | Mining sequential patterns for classification[END_REF], timestamped event sequences are described by vectors of binary features encoding the presence/absence of patterns. Feature vectors are then classified by a SV M classifier. Their most accurate approach extracts all frequent sequential patterns and uses them all as features. The large number of extracted patterns and their redundancy is a problem for the efficiency of the SV M classifier. Fradkin et al. proposed several strategies to reduce the number of patterns to use in SV M. Different approaches (BIDE-D, BIDE-DC, SMBT and SMBT -FS) dedicated to discriminant pattern mining are developed and tested to reduce this number while keeping the accuracy as high as possible.

Contrary to pattern mining approaches, the main drawback of these approaches is their interpretability (see for instance [Lipton, 2016] for a definition of interpretability). Interpretability is an essential property in our application field, but black-box classifier make hard to understand the association of patterns to behaviors. Our approach consists in extracting patterns that hold the discrimination information such that they can be individually interpreted: one discriminant chronicle describes an interpretable behavior encountered in the data, that is related to a specific sequence label.

Discriminant temporal patterns are finally used to present a few number of patterns to the experts [START_REF] Fabrègue | Discriminant temporal patterns for linking physico-chemistry and biology in hydro-ecosystem assessment[END_REF]. In this paper, discriminant patterns are extracted from hydro-ecological data to assist analysts with the extraction of knowledge. This approach does not extract discriminant patterns, but it selects those that satisfy a discrimination constraint among the frequent patterns.

Because of the great expressiveness of chronicles and their algorithmic properties, we are interested in frequent and discriminant chronicles mining. As in [START_REF] Fabrègue | Discriminant temporal patterns for linking physico-chemistry and biology in hydro-ecosystem assessment[END_REF], our goal is to support clinicians in extracting knowledge from data. Thus, our patterns must be interpretable rules instead of a black-box classifier. Mining discriminant chronicles offers a trade-off between interpretability and accuracy.

Discriminant chronicles

This section introduces more formally the basic definitions related to the discriminant chronicle mining task. In this paper, we address the task of mining sequences with timestamped events. More specifically, we have a supervised mining task. Each sequence of the dataset is labeled. From another point of view, we can say that sequences are categorized in several classes. We are interested in discovering patterns that are more frequent in one class than in the others. To take time into account, we search for patterns called chronicles [START_REF] Dousson | Discovering chronicles with numerical time constraints from alarm logs for monitoring dynamic systems[END_REF]. Briefly described, a chronicle is a set of events linked by temporal constraints.

Sequences and chronicles

Let E be a set of event types and T be a temporal domain where T ⊆ R. We assume that E is totally ordered by ≤ E . An event is a pair (e,t) such that e ∈ E and t ∈ T. A sequence is a tuple SID, (e 1 ,t 1 ), (e 2 ,t 2 ), . . . , (e n ,t n ) , L where SID is the sequence index, (e 1 ,t 1 ), (e 2 ,t 2 ), . . . , (e n ,t n ) a finite event sequence and L ∈ L where L is a label set. Sequence items are ordered by ≤ T defined as ∀i, j ∈ [1, n], (e i ,t i ) ≤ T (e j ,t j ) ⇔ t i < t j ∨ (t i = t j ∧ e i < E e j ).

SID

Sequence Label 1 (A, 1), (B, 3), (A, 4), (C, 5), (C, 6), (D, 7) + 2 (B, 2), (D, 4), (A, 5), (C, 7) + 3 (A, 1), (B, 4), (C, 5), (B, 6) A chronicle is a pair (E , T ): Intuitively, two similar events can always be ordered: one is the earliest of their type in the sequence and the other is the latest. The positive temporal constraint represents this order.

• The set E = { {e 1 . . . e n } }, e i ∈ E and ∀i, j, 1 ≤ i < j ≤ n,
Example 2.

C A B [ -1 ,3 ] C [ -3 ,5 ] [-2,2] D [4,5] C [1,3] C 1 A B [ 2 ,3 ] C [ 4 ,5 ] [-2,2] C 2 A C [ -3 ,1 ] C [2,4]
Fig. 1 Examples of three chronicles occurring in Table 1 (cf. Examples 2 and 5). No edge between two events is equivalent to the temporal constraint ] -∞, ∞[. lower bound -1, it can be read as B occurs between 1 temporal unit before A and 3 units after A. Thus, the order ≤ E defines a reading order on the constraints and not a sequential order on the events.

It can be noticed that chronicles are temporal constraint networks [START_REF] Dechter | Temporal constraint networks[END_REF]. Temporal constraints are interdependent in such a way that we have to take care of, on the one side, their inconsistency and, on the other side, of their redundancy. Dechter et al. proposed an algorithm to reduce temporal constraints of a chronicle to an equivalent minimal chronicle, i.e. a chronicle with minimal interval lengths. Such reduction is useful to compare chronicles that seem different but share a same reduced form. Sahuguède et al. also proposed a distance to compare chronicles [START_REF] Sahuguède | Mapping Chronicles to a k-dimensional Euclidean Space via Random Projections[END_REF]. The reasoning is similar for C 2 except that the interval between A and the second C is initially ] -∞, +∞[. By adding the lower bounds of the temporal constraints between A and the first C (-3) and between the two C (2) we obtain the lower bound between A and the second C (-1) and by adding the upper bounds (1 and 4) we obtain the upper bound (5).

Given two chronicles C

1 = (E 1 , T 1 ) and C 2 = (E 2 , T 2 ), we define the partial order where C 1 C 2 if E 2 ⊆ E 1
and there is a strictly increasing function f where ∀i, j,

1 ≤ i < j ≤ |E 2 |, 1 ≤ f (i) < f ( j) ≤ |E 1 |, e i , e j ∈ E 2 , e f (i) , e f ( j) ∈ E 1 , e f (i) [a, b]e f ( j) ∈ T 1 , e i [a , b ]e j ∈ T 2 , e f (i) [a, b]e f ( j) ⊆ e i [a , b ]e j . If C 1 C 2 and C 1 A B [ 2 ,3 ] C [ 4 ,5 ] [1,2] C 2 A C [ -3 ,1 ] C [2,4] [-1 ,5 ]
Fig. 2 The chronicles C 1 and C 2 are respectively the reduced chronicles of C 1 and C 2 of Fig. 1.

C 3 A B [ -3 ,2 ] C C 4 A B [-3,2] C 5 A B C
C 1 = C 2 , we say that C 1 is more specific than C 2 . On the contrary, C 2 is more general than C 1 . Example 4. Fig. 3 illustrates a chronicle C 3 = (E 3 , T 3 ) and two more general chron- icles C 4 = (E 4 , T 4 ) and C 5 = (E 5 , T 5 ). We have C 3 C 4 because E 4 ⊂ E 3 and T 3 = T 4 .
In the other hand we have C 3 C 5 because E 3 = E 5 , but T 3 has a more specific constraint than T 5 . In fact, T 5 having non constraint, any additional constraint is more specific.

Chronicle support

Let s = (e 1 ,t 1 ), . . . , (e n ,t n ) be a sequence and a, b] where e i [a, b]e j ∈ T . It is worth noting that f is not necessarily increasing. In fact, there is a difference between (i) the order of the chronicle multiset defined on items, ≤ E , and (ii) the order of events in sequences, ≤ T , defined on the temporal domain. The chronicle C occurs in s, denoted C ∈ s, if and only if there is at least one occurrence of C in s. The support of a chronicle C in a sequence set S is the number of sequences in which C occurs:

C = (E = { {e 1 , . . . e m } }, T ) be a chronicle. An occurrence of C in s is a subsequence s = (e f (1) ,t f (1) ), . . . , (e f (m) ,t f (m) ) such that 1) f : [1, m] → [1, n] is an injective function, 2) ∀i, e i = e f (i) and 3) ∀i, j, t f ( j) -t f (i) ∈ [
supp(C , S ) = |{s ∈ S | C ∈ s}|. Given a minimal support threshold σ min , a chronicle is frequent if and only if supp(C , S ) ≥ σ min .
Example 5. Chronicle C (see Fig. 1 at the top left), occurs in sequences 1, 3 and 6 of Table 1. On the one hand, C does not occur in the other sequences because there is no matching of E = { {A, B,C,C, D} }, the multiset of C , i.e., there is strictly less than one occurrence of A or one of B or two of C or one of D. On the other hand, C occurs in sequences 1, 3 and 6 because they contain at least one matching of E satisfying the temporal constraints. For example in sequence 6, the only matching of E is the whole sequence. Then, B occurs 1 unit before A which satisfies the temporal constraint A[-1, 3]B because it corresponds to the lower bound of the interval. The first event C occurs 2 units before A which satisfies the constraint A[- 3, 5]C because -2 ∈ [-3, 5]. And the three other constraints B[-2, 2]C, C[1, 3]C andB[4, 5]D are satisfied by the first C occurring 1 unit before B, the second C occurring 3 units after the first C and D occurring 5 units after B respectively.

We notice that there are two occurrences of C in sequence 1. Nonetheless, its support is supp(C , S ) = 3. This chronicle is frequent in S for any minimal support threshold σ min lower or equal to 3. The two other chronicles, denoted C 1 and C 2 , occur respectively in sequences 1 and 3; and in sequence 6. Their supports are

supp(C 1 , S ) = 2 and supp(C 2 , S ) = 1.
The support of chronicles is anti-monotonic using the previously defined partial order . Indeed, for two chronicles C 1 and C 2 and a sequence set S , C 1 C 2 implies supp(C 1 , S ) ≤ supp(C 2 , S ). This property derives from the fact that the most specific chronicle C 1 cannot occur in more sequences than C 2 because it is more constrained. This property has been formally proved and used in previous works on chronicles [START_REF] Dousson | Discovering chronicles with numerical time constraints from alarm logs for monitoring dynamic systems[END_REF], Cram et al., 2012, Huang et al., 2012, Alvarez et al., 2013].

Discriminant chronicles mining

Let S + and S -be two sets of sequences, and σ min ∈ N + , g min ∈ [1, ∞[ be two userdefined parameters. A chronicle C is discriminant for S + iff supp(C , S + ) ≥ σ min and supp(C , S + ) ≥ g min × supp(C , S -). In other words, a chronicle is discriminant iff its growth rate g(C , S ) is above the given threshold g min . To take into account the special case of a null support in the negative sequence set, the growth rate is defined as follows:

g(C , S ) = supp(C ,S + ) supp(C ,S -) , if supp(C , S -) > 0 +∞ , otherwise.
Contrary to the minimal support constraint which is anti-monotone, the minimal growth constraint is not.

Example 6. With chronicle C of Fig. 1, supp(C , S + ) = 2, supp(C , S -) = 1, where S + (resp. S -) is the sequence set of Table 1 labeled with + (resp. -). Considering that g(C , S ) = 2, C is discriminant if g min ≤ 2. For chronicles C 1 and C 2 , supp(C 1 , S + ) = 2 and supp(C 1 , S -) = 0 so g(C 1 , S ) = +∞ and supp(C 2 , S + ) = 0 and supp(C 2 , S -) = 1 so g(C 2 , S ) = 0. C 2 is not discrimi- nant, but C 1 is for any g min value.
Algorithme 1 Algorithm DCM for discriminant chronicles mining Require: S + , S -: sets of sequences, σ min : minimal support threshold, g min : minimal growth rate threshold 1: M ← EXTRACTMULTISETS(S + , σ min )

M is the set of frequent multisets 2: C ← / 0 C is the set of discriminant chronicles 3: for all ms ∈ M do 4:

if supp (S + , (ms, T ∞ )) > g min × supp (S -, (ms, T ∞ )) then 5:

C ← C ∪ {(ms, T ∞ )} Discriminant chronicle without temporal constraints 6: else 7:
for all T ∈ EXTRACTDISCRCONSTRAINTS(S + , S -, ms, g min , σ min ) do 8:

C ← C ∪ {(ms, T )} Add a new discriminant chronicle 9: return C
The support constraint, using σ min , prunes the infrequent, and so insignificant, chronicles. For example, a chronicle like C 1 such that g(C 1 , S ) = +∞ but supp(C 1 , S + ) = 2 is discriminant but would not be interesting for a bigger sequence set because it generalizes only two sequences. Pruning can be done efficiently thanks to the anti-monotonicity of the support. More specifically, if a chronicle2 (E , T ∞ ) is not frequent, then no chronicle of the form (E , T ) will be frequent. This means that temporal constraints may be extracted only for frequent multisets.

Extracting the complete set of discriminant chronicles is not interesting because it may contain discriminant chronicles with same multiset and similar temporal constraints. Such chronicles could match an almost similar set of sequences and could be considered as redundant by the analyst. It is preferable to extract chronicles whose temporal constraints are the most generalized. The approach proposed in the next section efficiently extracts a set of meaningful discriminant chronicles above given support and growth rate thresholds.

DCM algorithm

In this section, we present the algorithm DCM (Discriminant Chronicle Mining). We first present the overall algorithm and then detail its main steps.

The DCM algorithm (see Algorithm 1) extracts discriminant chronicles in two steps: First, it extracts the frequent multisets, which are chronicles without temporal constraints, and then it mines discriminant temporal constraints from these multisets.

At first, line 1 (EXTRACTMULTISETS) extracts M, the frequent multiset set in S + . This task is described in Section 4.1. In a second step, lines 3 to 8 extract discriminant temporal constraints for each multiset. The naive approach would be to extract discriminant temporal constraints for all frequent multisets. A multiset E (i.e. a chronicle (E , T ∞ )), which is discriminant, may yield numerous similar discriminant chronicles with most specific temporal constraints. We consider them as useless and, as a consequence, line 4 tests whether the multiset ms is discriminant. If so, (ms, T ∞ ) is added to the discriminant patterns set without more specification of the temporal constraints. Otherwise, lines 7-8 generate chronicles from discriminant temporal constraints identified by the routine EXTRACTDISCRCONSTRAINTS. This routine is detailed in Section 4.2.

Multiset mining

This section elaborates on the frequent multiset mining. Compared to frequent itemset mining, it takes care of the cardinality of items i.e. its number of repetitions.

This task can be easily solved by applying a frequent regular itemset mining algorithm on a transaction set encoding multiple occurrences of a same item as several items. Such dataset used for multiset mining contains a transaction for each positive sequence in the initial temporal sequence set. For each transaction, an item a ∈ E occurring n times in a sequence is encoded by n items: I a 1 , . . . , I a n .

SID Sequence Items

1 (A, 1), (B, 3), (A, 4), (C, 5), (C, 6), (D, 7) I A 1 I A 2 I B 1 I C 1 I C 2 I D 1 2 (B, 2), (D, 4), (A, 5), (C, 7) I A 1 I B 1 I C 1 I D 1 3 (A, 1), (B, 4), (C, 5), (B, 6), (C, 8), (D, 9) I A 1 I B 1 I B 2 I C 1 I C 2 I D 1
Table 2 The transaction set (last column of the table) obtained from the positive sequences of the dataset of Table 1 to extract frequent multisets.

Example 7. Table 2 shows the transaction set obtained for the set of temporal sequences of Table 1 (page 6). The transactions correspond only to the positive sequences. Each transaction contains the same number of items as the number of events in the corresponding sequence. In first transaction, the two occurrences of the events of type A became two distinct items I A 1 and I A 2 . A frequent itemset of size m, (I e k i k ) 1≤k≤m , extracted from this dataset is transformed into the multiset containing, i k occurrences of the event e k . Frequent itemsets with two items I e k i k , I e l i l such that e k = e l and i k = i l are redundant and, thus, these itemsets are ignored to avoid generating several times the same multiset. This could be tackled by adding pattern constraints into the itemset mining algorithm. Practically, we implemented a post-processing step.

Example 8. For σ min = 2, the itemset {I A 1 , I B 1 , I C 1 } is frequent in the dataset of the
, I B 1 , I C 2 }. This itemset is frequent for σ min = 2 because it occurs in the SID A A→B A B→C A A→C Label 1 2 2 4 + 1 2 3 5 + 1 -1 2 1 + 1 -1 3 2 + 2 -3 5 2 + 3 3 1 4 + 3 3 4 7 + 3 5 2 7 + 3 5 -1 4 + 5 -2 3 1 - 6 -1 -1 -2 - 6 -1 2 1 -
Table 3 Relational dataset for the multiset { {A, B,C} } corresponding to its occurrences in Table 1.

two transactions 1 and 3. It can be translated as the multiset { {A, B,C,C} } because I C 2 corresponds to two occurrences of C. To avoid redundancy, itemsets containing two items referring to the same event will be ignored. An example of such itemsets is

{I A 1 , I B 1 , I C 1 , I C 2 }. This itemset is ignored because it is equivalent to {I A 1 , I B 1 , I C 2 }: containing I C
1 and I C 2 together is equivalent to containing I C 2 alone.

Temporal constraints mining

The general idea of EXTRACTDISCCONSTRAINTS is to extract discriminant temporal constraints using a standard numerical rule learning algorithm [Cohen, 1995].

Let E = { {e 1 . . . e n } } be a frequent multiset. A relational3 dataset, denoted D, is generated with all occurrences of E in S . As C = (E , T ) (E , T ∞ ), D is sufficient to describe the entire occurrences set of C . The numerical attributes of D are interevent duration between each pair (e i , e j ) where e i , e j ∈ E and e i ≤ E e j , denoted by A e i →e j . An example is labeled by its sequence label (L ∈ L). If a sequence has several occurrences of E , then each occurrence yields one example.

A rule learning algorithm induces numerical rules from D. A rule has a label in the conclusion and its premise is a conjunction of conditions on attribute values. Conditions are inequalities in the form: A e i →e j ≥ x ∧ A e i →e j ≤ y, where (x, y) ∈ R 2 . Such a rule is translated as a temporal constraint set, T = {e i [x, y]e j }. The couple (E , T ) is then a potential discriminant chronicle. At this stage, we are not sure that the chronicle is discriminant. In fact, the rule learning algorithm extracts discriminant temporal constraints based on the dataset D, but multiple instances of the multiset in a sequence may bias the support evaluation. This limitation is discussed in section 4.2.2.

Example 9. 3 i.e., these constraints cover less positive occurrences, but it discriminates perfectly the sequences, as it occurs in all positive sequences (at least for one multiset instance) but it occurs in none of the negative sequences. This illustrates the possible biases due to multiple instances.

Rule learning

The rule learning task is done in practice by the Ripper k algorithm [Cohen, 1995], a relational rule learning algorithm. This algorithm was selected because of its high accuracy and because it allows the extraction of unordered rules. An unordered rule is independent from the others. Thereby, each rule of an unordered rule set is still true if read alone. It is not true for ordered rules. The problem with ordered rules learners (e.g., CN2, C4.5) comes with the validity of a rule at position n. This rule is valid only if the previous n -1 rules are not valid. Thereby if a chronicle set is based on ordered rules, some chronicles may not be discriminant if read alone.

Ripper k splits the dataset in two parts: Grow and Prune. Grow is used to construct the conjunction of conditions discriminating examples of one class with respect to the others. Growing stops when it is no longer possible to add a condition to the conjunction that improves accuracy. Prune is used to prune the constructed rule. If the conjunction is more discriminating without its last condition, this rule is removed from the conjunction and the last new condition is tested until the accuracy can no longer be improved. This approach allows to manage the overfitting made on Grow. If the accuracy is not satisfied for this conjunction of conditions, the search stops for that label. Otherwise the conjunction is returned as a rule, the examples associated with it are removed from Grow and the search starts again. The aforementioned steps are repeated for each label of the dataset.

The choice of using a rule learning algorithm based on an incomplete heuristic, in this case a heuristic based on the MDL principle (Minimum Description Length), is required for computational reasons. However, Ripper k combines (1) a reasonable algorithmic complexity -the computation times remain reasonable, (2) good classification performance -the chronicles extracted are therefore well representative of the dataset -and (3) reduced rule sets -retrieved chains remain easily interpretable [START_REF] Lattner | Experimental comparison of symbolic learning programs for the classification of gene network topology models[END_REF].

In the following section, we detailed two limitations of the proposed algorithm.

Multiple instance limit

The multiple instance problem [START_REF] Foulds | A review of multi-instance learning assumptions[END_REF] generally refers to the counting problems, which happen when a pattern appears multiple times in an object. In our case, an object is a sequence. This situation is encountered when building the dataset (cf. Our solution is to post-process the conjunctions of Ripper k rules and to retain only those that effectively validate the minimum support and growth rate constraints. This solution does not ensure that discriminant chronicles are extracted i.e., all extracted chronicles could be pruned but does not add computational heaviness.

A second solution to this problem would be to modify the counting system of Ripper k so that it evaluates a conjunction of conditions by counting the distinct SID.

But the heuristic of Ripper k is not made to exclude examples after having selected others, so it is not efficient for datasets containing many examples with same SID.

The third solution would be to use methods adapted to a multiple instance setting. For example, the miSVM approach [START_REF] Doran | A theoretical and empirical analysis of support vector machine methods for multiple-instance classification[END_REF] identifies for each object which instance has to be used by the classifier. This instance is seen as a witness of the object class. One possible approach for our algorithm would be to preprocess the dataset using the miSVM in order to identify the witness instances. In such a case, Ripper k would be applied on a mono-instance dataset. This solution seems to be the most reliable but it adds an important complexity to the process. Besides, our first experiments shown that it removes too many patterns.

Taking into account multiple instances directly in the rule learning step would therefore necessarily be done with adding computational complexity. Since multiple instances are rarely encountered in our applications, we have focused on computational efficiency by correcting the results with the post-processing strategy.

Minimal growth rate constraint satisfaction

During the post-processing of the rules for the previous problem, the algorithm prunes the rules according to the growth rate threshold. Indeed, the use of the g min parameter as growth rate threshold in Ripper k may prune interesting rules. Errors can occur when the Grow and Prune sets are not balanced and the proportion of the examples in a dataset is not representative of the set. On the other hand, the iterative process of rule conjunction generation removes positive and negative examples from Grow. Thereby, too many negative examples are removed from Grow, the growth rate of a rule is true for Prune but not for Grow. However, this problem remains marginal since it was already taken into account in the Ripper k development.

To conclude this section, the implementation of DCM based on Ripper k is correct because of the pruning step, but it is not complete. The algorithm benefits from its incompleteness since the extracted pattern set is smaller and then easier to present to a user and is extracted quicker.

Decision based on discriminant chronicle sets

Once discriminant chronicles have been extracted, they can be used to label new sequences. This section introduces this decision process.

The decision based on the extracted discriminant chronicles is not the main idea of this paper, however, we need to describe the general principles since we use it as evaluation. A discriminant chronicle extracted for a class can be seen as a rule for which an occurrence of this chronicle implies the associated label. We can so extract rules of the form µ(C , s) =⇒ l i for each class where C is a chronicle, s a sequence, µ the mapping function determining if C occurs in s and l i the label of the i th class. The discriminant chronicle mining task extracts patterns that occur also in other classes that those which are initially discriminated. Moreover, two extracted discriminant chronicles could have been extracted for different growth rates and supports. Therefore it is possible to have to predict the label of a sequence s, the two rules µ(C , s) =⇒ l i and µ(C , s) =⇒ l j where l i = l j and µ(C , s) = µ(C , s) = 1. In such case we have to apply an order on the extracted rule set to take a decision.

To rank the chronicles, we choose to use a measure based on the same growth rate definition that we use to extract them. Discriminant chronicles can have different supports and in the case of two discriminant chronicles C 1 and C 2 extracted for l 1 and l 2 respectively, supp(C 1 , l 1 ) = 10, supp(C 1 , l 1 ) = 0, supp(C 2 , l 2 ) = 100 and supp(C 2 , l 2 ) = 1, we prefer to give more confidence to C 2 than to C 1 even if C 1 has a better growth rate. The reason for this preference is due to a wider covering of C 2 and, thereby, a lower sensibility to the false positive rate. We choose to recompute the growth rate of each chronicle with adding a virtual sequence to the negative support. This measure is actually used in the subgroup discovery domain and is presented in [START_REF] Herrera | An overview on subgroup discovery: foundations and applications[END_REF] as the precision measure Q g (R) = T P FP+g where, in our case, T P = supp(C , l i ), FP = supp(C , l i ) and g is set up to 1.

Benchmark

This section is dedicated to evaluate the efficiency of our algorithm on synthetic and real data. The real datasets have been used for other pattern-based classification approaches [Fradkin andMörchen, 2015, Bornemann et al., 2016] and are different from our case study. The DCM implementation is written in C++ and relies on preexisting implementations of LCM [START_REF] Uno | LCM ver. 2: Efficient mining algorithms for frequent/closed/maximal itemsets[END_REF] and Ripper k [Cohen, 1995].

Synthetic data

In this section, we show the results of the evaluation of DCM on synthetic data.

Dataset generation

The general principle of the simulator is to generate sequences based on two different chronicles C + and C -. In a first step, one of these chronicles is assigned to every sequence of the two datasets S + and S -such that C + (resp. C -) is introduced mainly in the dataset S + (resp. S -) (see figure 4). In a second step, the chronicle assigned to the sequence is used as a "template": the sequence holds the items of the chronicle with timestamps randomly drawn but satisfying the temporal constraints, and additional random items. The dataset S = S + ∪ S -contains labeled sequences (L = {+, -}). Sequences labeled with + (resp. -) are then characterized by C + (resp. C -). Two parameters manage the introduction of these chronicles: f min and g min .

C + C - S + C - C + S -
• The parameter f min is the percentage of sequences in the majority class in which a chronicle appears. • The parameter g min is the ratio between the sequence numbers of the two classes in which this chronicle appears.

The objective of the experiment is to evaluate the ability of DCM to extract correct discriminant temporal constraints. To this end, we use chronicles for C + and C -that differ only on one temporal constraints. The more similar the chronicles, the harder the mining task.

More precisely, the Base N datasets have been created from chronicles based on the same multiset { {A, B} } of size 2. Therefore each chronicle has a unique time interval. For each dataset, the intervals of C -and C + overlap more or less. For all these datasets, we C + = ({ {A, B} }, {A[3, 10]B}); we set C -= ({ {A, B} }, {A[7, 8]B}) to generate Base 1 . Base 2 , Base 3 , Base 4 and Base 5 are generated using similar constraints for chronicles C -: respectively, A[6, 8]B, A[4, 8]B, A[4, 9]B and A[4, 10]B. These chronicles are illustrated in the Table 4.

Dataset C + C - Expected discriminant chronicles Base 1 A B [3,10] A B [7,8] A B [-∞,6] A B [9,+∞] Base 2 A B [3,10] A B [6,8] A B [-∞,5] A B [9,+∞] Base 3 A B [3,10] A B [4,8] A B [-∞,3] A B [9,+∞] Base 4 A B [3,10] A B [4,9] A B [-∞,3] A B [10,+∞] Base 5 A B [3,10] A B [4,10] A B [-∞,3]
Table 4 Chronicles introduced in each dataset type and expected discriminant chronicles for S + in these datasets for each pair of introduced chronicles. As discriminant chronicles of Base 1 are more general than those of Base 5 , Base 1 sequences are easier to discriminate than those of Base 5 .

It is important to notice that the discriminant mining task does not aim at extracting C + and C -from S . Its goal is to extract patterns describing the maximum number of occurrences of C + and the minimum number of occurrences of C -. The third column of Table 4 gives the expected discriminant chronicles to extract.

For each dataset type Base N , the results are averaged over 20 datasets generated independently. The simulator is set to generate by default datasets containing 800 sequences. The average length of sequences is 10. The size of the vocabulary is set at 50 items and f min and g min are respectively set to 80% and 10%.

The ability of DCM to extract the correct patterns is evaluated by comparing the sets of extracted patterns with the expected patterns. Two measures are used: ∆ c (m, m) the coverage ratio and ∆ g (m, m) the growth ratio. The variable m and m denote extracted and expected patterns respectively.

• ∆ c (m, m) = |{s ∈ S + | m ∈ s} ∩ {s ∈ S + | m ∈ s}| |{s ∈ S + | m ∈ s}| is a coverage ratio similar to
the unilateral Jaccard similarity [START_REF] Santisteban | Unilateral jaccard similarity coefficient[END_REF]] coefficient. It represents the ratio between the number of sequences of the S + class containing one occurrence shared by m and m; and the number of sequences in S + containing m. This measure determines how much similar are the sets of sequences labeled as positive by the two patterns. It is a recall measure.

• ∆ g (m, m) =          min g (m,S ) g ( m,S ) , 1 , if g ( m,S ) < +∞ 1 , if g (m,S ) = g ( m,S ) = +∞ 0
otherwise is the growth ratio. It represents the ratio of the growth rates of m to m.

For each expected patterns m, a single pair (∆ c (m, m) , ∆ g (m, m) ) is retained such that ∆ c (m, m) is the highest for any extracted pattern m and that ∆ g (m, m) is the highest if there are several maximal ∆ c (m, m) . To simplify the notations, (∆ c, ∆ g) is used to denote this pair. In addition to the previous measure used as recall, we use this measure as accuracy.

Results

Figure 5 shows the extraction results of DCM on the 20 datasets generated for each Base N . The coverage ratio is given in abscissa and the growth ratio in ordinates. Given a coverage ratio ∆ g and a growth ratio ∆ g, the dot size gives the number of chronicles similar to one of the expected chronicles (see Table 4). This number is the sum of patterns for the 20 datasets, meaning that the maximal dot size is 40 for database 1 to 4 (20 datasets with 2 expected patterns) and 20 for database 5.

The biggest dots per database, from 1 to 5, represent respectively 31, 40, 30, 30 and 15 extracted chronicles that was expected.

We notice on Figure 5 that DCM extracts at least 75% of the expected discriminant patterns in each dataset a discriminant pattern whose coverage and growth ratios are perfect (∆ c = 1 and ∆ g = 1). In addition, for the Base 4 and Base 5 datasets, DCM does not extract any patterns for certain introduced discriminant patterns, but only 1 out of 40 for Base 4 and 2 on 20 for Base 5 .

To explain these errors, we extract chronicles from the same dataset with a minimum growth rate g min = 1.1. With this setting, all expected Base 4 patterns match with at least extracted pattern (with at least ∆ c = 1 and ∆ g = 0.83). It is worth noting that the extracted pattern corresponding to ∆ c = 0.47 for the first extraction of the Base4 patterns reaches the same ∆ c and ∆ g ratios (∆ c = 1 and ∆ g = 0.83).

These results on simple synthetic data show that DCM actually extracts the discriminating patterns with robustness. For datasets that can only be discriminated through the temporal dimension, DCM extracts the useful discriminant temporal constraints representing the expected discriminant patterns.

BIDE-D comparison

We compare DCM to the BIDE-D algorithms on datasets from [START_REF] Fradkin | Mining sequential patterns for classification[END_REF]. These datasets come from a variety of applications. In order to compare DCM with BIDE-D because these datasets are neither as simple as blocks nor as Auslan2, we chose to focus on asl-bu, asl-gt and context.

• asl-bu: The intervals are transcriptions from videos of American Sign Language expressions provided by Boston University [START_REF] Papapetrou | Discovering frequent arrangements of temporal intervals[END_REF]. It consists of observation interval sequences with labels such as head mvmt: nod rapid or shoulders forward that belong to one of 7 classes like yes-no question or rhetorical question.

• asl-gt: The intervals are derived from 16-dimensional numerical time series with features derived from videos of American Sign Language expressions [START_REF] Starner | Real-time american sign language recognition using desk and wearable computer based video[END_REF]]. The numerical time series are discretized into 2 -4 states. Each sequence represents one of the 40 words such as brown or fish. • context: The intervals are derived from categoric and numeric data describing the context of a mobile device carried by humans in different situations [START_REF] Mäntyjärvi | Sensor signal data set for exploring context recognition of mobile devices[END_REF]. Numeric sensors are discretized using 2 -3 bins chosen manually based on exploratory data analysis. Each sequence represents one of five scenarios such as street or meeting.

These datasets are databases of intervals interpreted as sequential databases by considering begin and end boundaries of an interval as two distinct events.

The couple C , L of discriminant chronicles, where L ∈ L, is used to predict the label of a sequence. A label L will be predicted for a sequence in case this sequence contains the chronicle C . In the case of several chronicles appearing in the sequence, we label the sequence with the predicted label by the chronicle with the highest growth rate. This simple classification method is more accurate than the use of a standard machine learning classifier to evaluate the extracted chronicles. On the other hand, discriminant chronicle accuracy would not be overrated in comparison to BIDE-D approaches. Indeed, the BIDE-D approaches use a SV M classifier and SV M is generally more accurate than a simple rule-based classifier.

The results discussed below are presented in Table 5. We set a size limit of 6 items per chronicle in order to limit the number of patterns. The results presented in [START_REF] Fradkin | Mining sequential patterns for classification[END_REF] On asl-gt BIDE-D outperforms DCM. Where accuracy ranges from 27.31% for σ min = 0.6 to 82.94% for σ min = 0.2 for BIDE-D. But it hardly exceeds 30% for discriminant chronicles. The standard deviation of BIDE-D and DCM are similar. Many patterns are extracted but are poorly distributed among the dataset labels. While discriminant chronicles can represent discriminant sequential patterns, these poor results on asl-gt are due to a lack of discriminant patterns. This lack is due to the large number of classes that are 40 for asl-gt. As a result, a single pattern is difficulty discriminant. The results obtained for BIDE-D are due to the selection of the best discriminant patterns and not to a minimal growth rate threshold. Thereby, even if there is no discriminant sequential patterns in asl-gt, the BIDE-D approaches extract some patterns to use in the classifier. On asl-bu DCM performs slightly worse than BIDE-D. The accuracy using g min = 2 is equivalent from σ min = 0.4 to σ min = 0.6, whereas the number of extracted patterns is reduced from more than 30, 000 to 1, 600. DCM's accuracy exhibits better performances than BIDE-D in terms of standard deviation. We can notice that asl-bu is a difficult type of dataset for chronicle mining due to multiple occurrences of the same event types. As a result DCM did not extract any discriminant patterns for σ min = 0.2 or σ min = 0.3. It takes too much time and does not finish for these parameters within the 12 hour timeout.

Finally, on context, DCM outperforms BIDE-D in accuracy. The accuracy standard deviation is higher than for the two other datasets but is, however, similar to the one of BIDE-D. We note that the low results of BIDE-D approaches may be due to the use of a different minimum support threshold strategy for this dataset. The difference in the number of patterns extracted by the σ min = 0.2 or σ min = 0.6 parameters is much smaller than for asl-bu. The count goes from 360 patterns for σ min = 0.2 and g min = 2 to 145 for σ min = 0.6 and g min = 4.

We conclude from these results that discriminant chronicles as rules can produce similar and sometimes better accuracy than sequential patterns as features. Furthermore, our results show that it seems easier to obtain a good accuracy for datasets containing few classes (e.g., context: 5 classes) than datasets for which the sequences are distributed in a large set of classes (e.g., asl-gt: 40 classes). Indeed, a large class number implies a generalization problem. A pattern discriminating a class against 39 other classes has to be more specific than a pattern discriminating a class against 4 other classes. This generalization problem comes from the unbalanced distribution between positive and negative sequences that requires to be very specific to obtain discriminant patterns. This problem is less important for the BIDE-D approaches because the SV M classifier learns combinations between discriminant patterns extracted for a subset of classes to generalize it for all classes. Thereby, the SV M classifier can predict a class without using discriminant pattern for this class but it is not possible with discriminant chronicles used as rules. The definition of an extracted discriminant pattern is also different for DCM and BIDE-D and affects this generalization problem. A pattern is extracted by DCM if its growth rate is greater than a threshold. In this case, it is possible to extract no patterns for a threshold. A pattern is extracted by BIDE-D if its growth rate is one of the highest. Thereby, it is ensured that some patterns will be extracted and used as features by the classifier. Finally, DCM is easy to set up while a cross-validation is needed to obtain the parameters of the SV M that use the sequential patterns as features (the standard SV M parameter C is a power of 10 and is tested from 10 -3 to 10 3 ).

Case study of care pathway analytics

A care pathway designates the sequences of interactions of a patient with the healthcare system (medical procedures, biology analysis, drug deliveries, etc.). Healthcare systems collect longitudinal data about patients to manage their reimbursements. Such data are now readily available in medico-administrative databases. Huge databases, such as the SNIIRAM [START_REF] Moulis | French health insurance databases: What interest for medical research[END_REF] in France, have a better population coverage than ad hoc cohorts and Electronic Medical Records (EMR). Moreover it covers cares in real life situations over a long period of several years.

Medico-administrative databases are useful to answer questions about care quality improvement (e.g., care practice analysis), care costs cutting and prediction, or epidemiological studies. Among epidemiological studies, pharmaco-epidemiological studies answer questions about the uses of health products, drugs or medical devices, on a real population.

The main difficulties encountered by pharmaco-epidemiology studies are that 1) epidemiologists often have to provide an hypothesis to assess, 2) they cannot handle sequences with more than two events and 3) the temporal dimension of pathways is poorly exploited.

Care pathway analytics aim at supporting epidemiologists to explore such complex information sources. It consists of using data analytics tools (visualization, data abstraction, machine learning algorithms, etc.) applied on healthcare data. More specifically, temporal pattern mining algorithms can extract interesting sequences of care events that would suggest candidate hypotheses. As the pharmaco-epidemiological studies of studying care pathways with respect to the patient outcome, discriminant temporal patterns are appropriate for such analyses. This section4 presents the use of DCM to study care pathways of epileptic patients. Recent studies suggested that medication substitution (so called switch) may be associated with epileptic seizures for patients with long-term treatment with antiepileptic medication. In [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], the authors did not find significant statistical relationship between brand-to-generic substitution and seizure-related hospitalization. The DCM algorithm is used to extract patterns of drug deliveries that discriminate occurrences of recent seizures. These patterns may be interesting for further investigations by statistical analysis.

Positive and negative datasets construction

This section presents the transformation of medical database into a dataset of labeled sequences. This transformation is required to apply the DCM algorithm and can impact the results as well as their interpretability. In fact, depending on the input data (event types, sequence lengths, etc.), the extracted patterns may change a lot. We tested several sequence encodings and the one proposed below appears to be the most interesting.

Our dataset was obtained from the SNIIRAM [START_REF] Moulis | French health insurance databases: What interest for medical research[END_REF] database which contains a lot of tables with large numbers of attributes. Two important choices are required to obtain datasets of labeled sequences: 1) the choice of the set of events on which sequences will be built and 2) the sequence labeling.

The care pathway of a patient is a collection of timestamped drugs deliveries from 2009 to 2011. All other care events have been ignored in this study. For each drug delivery, an event id is a tuple m, grp, g where m is the ATC5 code of the active molecule, g ∈ {0, 1} where g = 1 means generic drug and g = 0 brand-named 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).

A case-crossover protocol has been adapted to label sequences. This protocol is often used in pharmaco-epidemilogical studies. It studies the possible causes of an outcome using a patient as his/her own control. In our case, the patient outcomes are seizure events of epileptic patients. According to the study of [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], we selected epileptic patients with stable treatments, i.e., patients who had at least 10 anti-epileptic drugs deliveries within a year without any seizure. Epileptics seizures have been identified by hospitalization related to an epileptic event, coded G40.x or G41.x with ICD-106 . The total number of such patients is 8,379.

Then, each patient generates two sequences: one positive and one negative. Drugs delivered within the 90 days before induction periods yield the positive sequences and those delivered within the 90 days before the positive sequence, i.e., the 90 to 180 days before induction, yield the negative sequences. A three-day induction period is defined before the first seizure of each patient.

At the end of the data preparation, the dataset has two sets of 8,379 labeled sequences, and contains 127,191 events corresponding to 1,716 different drugs.

Experiments and results

Set up with σ min = 5.10 -3 , i.e. 42 patients7 , and g min = 1.4, we generated 777 discriminant chronicles that discriminate the case sequences from the control sequences of 90 days. Chronicles involved 510 different multisets and 128 different event types. Similar results were obtained with sequence duration of 60, 120 and 150 days. For comparison, 535 chronicles were extracted for the dataset containing sequences of 150 days with the same parameters. The main difference between those two datasets is that chronicles are discriminant in the 150 days dataset for higher g min . For example, 487 chronicles are discriminant for g min = 1.8. Our intuition is that regular treatments are more easily discriminated from punctual deliveries when the sequences are larger. Larger discriminant chronicles are extracted from the 150 days dataset than from the 90 days dataset and these chronicles describe more accurately the underlying discriminant behavior.

Three types of pattern are of specific interest for clinicians: (1) sequences of anti-epileptic generic and brand-named drug deliveries, (2) sequences of same antiepileptic drug deliveries, (3) sequences with anti-epileptic drug deliveries and other drug types deliveries. According to these criteria, we selected 55 discriminant chronicles involving 16 different multisets to be discussed with clinicians. The remaining of this section focuses on chronicles related to valproic acid (N03AG01 ATC code, with different presentations) because it is the most frequent anti-epileptic drug occurring in the dataset but our results contain similar chronicles related to other antiepileptic drugs like levetiracetam or lamotrigine.

Taking into account time in brand-to-generic substitution

We start with patterns representing switches between different presentation of N03AG01. Fig. 6 illustrates all discriminant patterns that have been extracted. It is noteworthy that all chronicles have temporal constraints; this means that multisets without temporal constraints are not discriminant. These results are consistent with Polard et al. [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] which concluded that brand-name-to-generic antiepileptic drug substitution was not associated with an elevated risk of seizure-related hospitalization. But temporal constraints were not taken into account in the latter study. The four extracted chronicles suggest that for some small patient groups, drug switches with specific temporal constraints are more likely associated with seizures.

The first two chronicles represent delivery intervals lower than 30 days, from brand-to-generic and generic-to-brand-names respectively. The third one represents an interval between the two events that are greater than 30 days but lower than 60 days. The discriminant temporal constraints of the last one could be interpreted as [67,90] because of the bounded duration of the study period (90 days). This chronicle represents a switch occurring more than 60 days but most of the time less than 90 days.

These behaviors may correspond to unstable treatments. In fact, anti-epileptic deliveries have to be renewed regularly in intervals of a few months, thus, a regular treatment corresponds to a delay of approximately 30 days between two antiepileptic drug deliveries.

We next present in Figure 7 an example of a discriminant chronicle that involves three deliveries of N03AG01 (no chronicle involves more deliveries of this antiepileptic drug). The growth rate of this chronicle is high (2.94). It is easy to understand and, with their discriminant temporal constraints, it can be represented on a timeline (see Figure 7, below). It is noteworthy that the timeline representation loses some information about the constraints. The first delivery is used as a starting point (t 0 ), but it clearly illustrates that the last delivery occurs too late after the second one (more than 30 days after). As well as previous patterns, this chronicle describes an irregularity in deliveries. More precisely, the irregularity occurs between the second and the third deliveries as described by the discriminant temporal constraints [42,53] and [72,83].

We conclude from observations on the previous two types of patterns that the precise numerical temporal information discovered by DCM is useful to identify discriminant behaviors. Analyzing pure sequential patterns does not provide enough expression power to associate switch of anti-epileptic drugs deliveries with seizures. Chronicles, specifying temporal constraints, allow us to describe the conditions under which temporal delays between anti-epileptic drugs deliveries are discriminant for epileptic seizures.

Example of a complex chronicle

Clinicians found the chronicle presented in Figure 8 interesting, as it does not match expert knowledge prima facie. The chronicle illustrates a potential adverse drug interaction between an anti-epileptic drug and a drug non-directly related to epilepsy, more especially aspirin (B01AC06), prescribed as an anti-thrombotic treatment. The discriminant temporal constraints imply that aspirin and paracetamol (N02BE01) are delivered within a short period (less than 28 days). There is no temporal relations between these deliveries and the deliveries of valproic acid. But their co-occurrence within the period of 90 days is part of the discriminatory factor.

After a deeper analysis of patient care pathways supporting this chronicle, clinicians made the hypothesis that these patients were treated for brain stroke. It is known for seriously exacerbating epilepsy and increasing seizure risk.

Conclusion

Chronicles mining was already studied but there was not previous work on discriminant chronicles mining, nor patterns with quantitative temporal information. The DCM algorithm has been proposed to solve this problem. It allows, on the one hand, to take into account temporal information and, on the other hand, to constrain the extracted chronicles with a growth rate constraint. This algorithm relies on rule learning domain which has proved to be efficient for discovering discriminant rules from quantitative attributes.

The experiments using the Ripper k algorithm showed that DCM is able to extract discriminant chronicles efficiently. Comparisons in terms of accuracy between DCM and the BIDE-D [START_REF] Fradkin | Mining sequential patterns for classification[END_REF] algorithms showed that discriminant chronicles extracted with DCM are able to compete with state-of-the-art approaches without the need of classifiers. Thus, the patterns extracted by DCM can be interpreted by experts.

Experimental results on our case study show that DCM extracts a reduced number of patterns. Discriminant patterns have been presented to clinicians who conclude to their potential interestingness to explore care pathways supported by chronicles. The main interest of this experiment is to show that some interesting patterns are extracted and that clinicians do actually understand them. Contrary to black-box approaches such as BIDE-D, this approach provides insights to the expert about large data at hand.

At this stage of the work, our main perspective is to integrate DCM in a care pathway analytic tool such that extracted chronicles can easily be contextualized in care pathways and manually modified to progressively build a care sequence of interest.

An improvement perspective would be to extract temporal constraints with an approach managing multiple instances [START_REF] Foulds | A review of multi-instance learning assumptions[END_REF]. In fact, in our twostep algorithm, temporal constraints are extracted from instances of a given multiset. In sequences, a multiset may occur several times due to event repetitions. As a consequence, one sequence generates several instances of temporal constraints for the same multiset. Assuming that only one instance is significant for our problem, all other instances confuse the dataset.

From the interpretability point of view, extracted pattern set remains too large. Condensed representations of chronicles mining, e.g., minimal chronicles, or a posttreatment identifying similar chronicles would allow a better reading of the results.

  where e i ≤ E e j is a multiset, i.e. E can contain several occurrences of a same event type. • The set T is a temporal constraint set: T = {e[a, b]e | e, e ∈ E , e ≤ E e }. As the constraint e[a, b]e is equivalent to e [-b, -a]e, we impose the order on items, ≤ E , to desambiguate which one is graphically represented in the chronicle. Moreover, when e = e , we can obtain two different chronicles which are equivalent: one based on e[a, b]e where a ≥ 0 1 and one other based on e [-b, -a]e. In such a case we choose the positive one because it is a more natural representation.

  Fig. 1 illustrates three chronicles represented by directed graphs. Chronicle C = (E , T ) where E = { {e 1 = A, e 2 = B, e 3 = C, e 4 = C, e 5 = D} } and T = {e 1 [-

Example 3 .

 3 Fig. 2 illustrates reduced chronicles equivalent to C 1 and C 2 from Fig. 1. We see that the difference between C 1 and C 1 is the temporal constraint B[-2, 2]C for C 1 and the temporal constraint B[1, 2]C for C 1 . Indeed, as we have A[4, 5]C and A[2, 3]B, it is not possible to observe C 2 time units before B. If B occurs 2 time units after A, C must occur 2 or 3 time units after B to satisfy A[4, 5]C. If B occurs 3 time units after A, C must occur 1 or 2 time units after B to satisfy A[4, 5]C. As 3 was not in the original temporal interval [-2, 2], we obtained with this reasoning the new temporal constraint B[1, 2]C.

Fig. 3

 3 Fig. 3 Example of a chronicle specialization/generalization. C 4 and C 5 are generalizations of C 3 . C 4 has a more general multiset and C 5 has more general temporal constraints.

Fig. 4

 4 Fig. 4 Distribution of chronicles C + and C -in sequence datasets S + and S -.

Fig. 5

 5 Fig. 5 Scatter plots of the extracted patterns represented by (∆ c, ∆ g) for each dataset. For each expected discriminant pattern m only the best extracted pattern m according to (∆ c (m, m) , ∆ g (m, m) ) is used in these plots. The dot size represents the number of extracted patterns.

Fig. 6

 6 Fig.6Four discriminant chronicles describing switches between same type of valproic acid (N03AG01) generic (G 438) and brand-named (R 438). supp(C i , S + ) respectively for i = 1 to 4 equals 43, 78, 71 and 43 and supp(C i , S -) equals 23, 53, 39 and 30.

Fig. 7

 7 Fig. 7 Above, a chronicle describing repetitions of valproic acid (N03AG01) generic (G 438) and, below, its timeline representation. The chronicle is more likely related to epileptic seizures: supp(C , S + ) = 50, supp(C , S -) = 17.

Fig. 8

 8 Fig.8A chronicle describing co-occurrences between anti-thrombosis drugs (B01AC06) and valproic acid which is more likely associated to seizures: supp(C , S + ) = 42, supp(C , S -) = 20.

Table 1

 1 Set of six sequences labeled with two classes {+, -}. temporal constraint is a tuple (e 1 , e 2 ,t -,t + ), also noted e 1 [t -,t + ]e 2 , where e 1 , e 2 ∈ E, e 1 ≤ E e 2 and t -,t + ∈ T ∪ {-∞, +∞}, t -≤ t + . A temporal constraint e 1 [t -,t + ]e 2 is satisfied by a couple of events ((e,t) , (e ,t )) iff e = e 1 , e = e 2 and tt ∈ [t -,t + ]. We define the inclusion of two temporal constraints as the inclusion of their intervals if their event types are identical. More formally, e 1 [a, b]e 2 ⊆ e 1 [a , b ]e 2 iff e 1 = e 1 , e 2 = e 2 and [a, b] ⊆ [a , b ].

		, (C, 8), (D, 9)	+
	4	(B, 4), (A, 6), (E, 8), (C, 9)	-
	5	(B, 1), (A, 3), (C, 4)	-
	6	(C, 4), (B, 5), (A, 6), (C, 7), (D, 10)	-
	Example 1. Table 1 represents a set of six sequences containing five event types (A,
	B, C, D and E) and labeled with two different labels L = {+, -}. In this example
	≤ E is the lexicographic order.

A

  Table 2 since it occurs in each transaction. Then, the extracted itemset is translated into the multiset { {A, B,C} } because I A

	1 , I B 1 and I C 1 correspond to one occurrence
	of A, one occurrence of B and one occurrence of C respectively. Another frequent
	itemset is {I A 1

  Table3is the relational dataset obtained from the occurrences of { {A, B,C} } containing by the dataset of Table1. The attribute A A→B denotes the duration between A and B. We can see on Table3that an example contains the SID of the sequence, the duration for each pair of events and the label of the sequence. It is worth noticing that several examples may come from the same sequence. The rule A A→C ≥ 2 =⇒ + characterizes almost all the examples labeled by + in Table3 and characterizesall the different SID labeled by +. It is translated into the discriminant temporal constraints {A[2, +∞[C} which gives the discriminant chronicle C = ({ {e 1 = A, e 2 = B, e 3 = C} }, {e 1 [2, +∞[e 3 }). It is interesting to notice that the discriminant temporal constraints {A[-1, +∞[B, B[3, +∞[C} is less discriminant from the point of view of the dataset of Table

  Table 3) and distorts the count of the number of objects validating a conjunction of rules made by Ripper k . When examples with the same SID (e.g., first four sequences of the table 3) are covered by a rule, they must only count for one object (i.e. a SID). This specific setting in not handled by Ripper k .

  are given in Table6.

			g min
	dataset σ min	2	3	4	5
	asl-bu 0.4 52.64 (±2.21)	49.20 (±0.51)	52.41 (±3.51)	48.28 (±1.99)
	0.5 51.26 (±1.31)	51.72 (±1.99)	49.66 (±6.82)	48.51 (±5.60)
	0.6 51.72 (±3.35)	50.34 (±3.58)	44.14 (±3.31)	39.08 (±3.72)
	asl-gt 0.2 31.55 (±0.91)	31.61 (±0.92)	30.20 (±1.82)	30.15 (±0.92)
	0.3 31.17 (±0.44)	29.18 (±1.53)	27.75 (±1.58)	26.96 (±1.89)
	0.4 27.34 (±2.10)	25.82 (±0.42)	25.91 (±0.12)	25.32 (±0.19)
	0.5 25.44 (±0.34)	25.20 (±0.13)	24.68 (±0.50)	24.12 (±0.41)
	0.6 24.30 (±0.42)	23.92 (±0.53)	23.89 (±0.52)	23.13 (±0.44)
	context 0.2 64.78 (±2.83)	57.39 (±4.76)	46.09 (±3.89)	53.48 (±6.07)
	0.3 56.09 (±5.83)	42.61 (±7.62)	52.61 (±3.22)	36.96 (±7.53)
	0.4 47.83 (±4.07)	39.57 (±3.57)	50.43 (±5.41)	47.39 (±4.96)
	0.5 53.91 (±4.46)	38.70 (±0.97)	30.43 (±5.10)	47.83 (±7.37)
	0.6 50.87 (±2.48)	34.78 (±4.35)	30.87 (±4.18)	28.70 (±4.46)

Table 5

 5 Mean accuracy (in %) with respect to σ min (minimal support threshold), g min (minimal growth rate threshold) for different datasets.

Table 6

 6 Mean accuracy (in %) with respect to σ min (minimal support threshold) and the different methods proposed in[START_REF] Fradkin | Mining sequential patterns for classification[END_REF] for different datasets. The methods BIDE-D and BIDE-DC extract discriminant sequential patterns. BIDE and BIDE-C extract frequent sequential patterns. Support thresholds used to obtain results from context are much higher than for the other datasets.

T ∞ denotes the set of temporal constraints {e] -∞, +∞[e | e, e ∈ E }.

In some context, relational dataset designates a dataset whose organization is based on a relational data model. In our context, the relational model designed an attribute-value dataset by opposition to a sequence dataset. It can be seen as a single relation dataset.

The results presented in this section have been published in the AIME conference[START_REF] Dauxais | Discriminant chronicles mining: Application to care pathways analytics[END_REF].

ATC: Anatomical Therapeutic Chemical Classification System

ICD-10: International Classification of Diseases 10th Revision

This number of patients has been initially estimated important by epidemiologists to define a population of patients with similar care sequences associated to seizures.

Acknowledgements This project has been founded by the French Agency of Medicines and Health Products Safety (ANSM). We would like to thank Pr. E. Oger and Pharm.D E. Polard for agreeing to study the patterns extracted from the real dataset.