Yann Dauxais
email: yann.dauxais@kuleuven.be

Thomas Guyet
email: thomas.guyet@irisa.fr

Generalized chronicles for temporal sequence classification

Keywords: Temporal patterns, discriminant patterns, sequence classification

 tackles temporal sequence classification by combining machine learning and chronicle mining algorithms. A chronicle is a set of events related by temporal boundaries on the delay between event occurrences. Such temporal constraints are poorly expressive and discriminant chronicles may lack of accuracy. This article generalizes discriminant chronicle mining by modeling complex temporal constraints. We present the generalized model and we instantiate different generalized chronicle models. The accuracy of these models are compared with each other on simulated and real datasets.

Introduction

Temporal sequences, i.e., sequences of timestamped events, are broadly encountered in various applications. They may represent customer purchases, logs of monitoring systems, or patient care pathways and their analysis is highly valuable to support experts 1) to better understand underlying processes and 2) to decide future actions. Face to the large amount of such data, sequence mining techniques have been proposed to extract interesting behaviors. While most sequence mining approaches are dedicated to the extraction of frequent behaviors, few pattern mining approaches deal with discriminant patterns. Discriminant patterns address the task of sequence classification. In a set of labeled sequences, a discriminant pattern associated to a label L occurs more likely in sequence labeled with L than in the other sequences. Discriminant patterns describe the classes of sequences but they can also be used to predict labels of new sequences.

In this work, we assume that temporal information is an important feature to accurately discriminate behaviors. For instance, knowing the delay between two successive visits on a commercial web site may distinguish loyal customers from the others. The sequence of visited pages may be the same, it is the delay between the visit that witnesses the customer loyalty. Dauxais et al. [START_REF] Dauxais | Discriminant chronicles mining -application to care pathways analytics[END_REF] introduced chronicles to discriminate temporal behaviors in temporal sequences. A chronicle is a set of events linked by temporal relations imposing numerical bounds on delays between events. We showed that the temporal information captured by chronicles improves the accuracy of sequence labeling.

Mining discriminant chronicles is similar to a regular classification problem. It consists in finding suitable boundaries on the temporal delay to accurately discriminate classes. But, chronicles express very simple boundaries, i.e., delays belonging to an interval.

In this article, we extend the expressiveness of the temporal constraints discovered in chronicles to study the discriminatory power of different types of temporal constraints. The main contribution is the proposal of the generalized discriminant chronicles (GDC). GDC is a meta-model that enables to represent different types of patterns, characterized by their modeling of temporal relations between events. Our framework includes a unified GDC mining procedure inspired by the DCM algorithm [START_REF] Dauxais | Discriminant chronicles mining -application to care pathways analytics[END_REF] and a unified decision procedure to label new sequences. The experiments compare the accuracy of four instances of GDC on simulated and real datasets.

Related Works

Sequential patterns have been studied since the early stage of the field of pattern mining [START_REF] Srikant | Mining sequential patterns: Generalizations and performance improvements[END_REF]. Mabroukeh et al. [START_REF] Mabroukeh | A taxonomy of sequential pattern mining algorithms[END_REF] review the most efficient sequential pattern approaches. All of them are based on the anti-monotonicity property of the pattern support which states that larger patterns occur fewer times in sequences.

In temporal sequences, events are timestamped and our assumption is that the temporal dimension is a key dimension to accurately characterize interesting behaviors. While sequential patterns capture only information about the order of occurrences of events, temporal patterns capture a more expressive temporal information. Different proposals have been made to enrich sequential patterns with more complex temporal information. Mannila et al. proposed episodes [START_REF] Mannila | Discovery of frequent episodes in event sequences[END_REF] as a pattern type which could combine parallel or serial events. Hoeppner et al. [START_REF] Höppner | Discovery of temporal patterns[END_REF] introduced Allen's temporal logic to specify the temporal relations between interval events. Two events are not necessarily sequentially ordered, they could "overlap" or "be covered". The temporal relations that are discovered are qualitative. In temporally annotated sequences (TAS) [START_REF] Giannotti | Efficient mining of temporally annotated sequences[END_REF] the successive events are constrained by numerical duration extracted by combining a density clustering technique. The chronicle model [START_REF] Cram | A complete chronicle discovery approach: application to activity analysis[END_REF] is at a crossroad between episode and TAS. It is a partial temporal order applied on pattern events constrained by numerical temporal intervals. This pattern model is more general than sequential patterns, TAS and episodes.

Finally, quantitative episodes [START_REF] Nanni | Extracting trees of quantitative serial episodes[END_REF] are tree-based patterns that are graphically similar to chronicles but formally more similar to sets of TAS. Indeed, a quantitative episode represents a set of TAS that are all specifying the same sequential pattern. This set of TAS is represented by a tree rooted on the first event of the sequential pattern for which each path leading to a leaf is a TAS.

Sequence classification has been addressed with statistical approaches such as HMM but also with machine-learning approaches such as recurrent neural networks (LSTM) [START_REF] Lipton | A critical review of recurrent neural networks for sequence learning[END_REF].

Bringmann et al. [START_REF] Bringmann | Pattern-based classification: a unifying perspective[END_REF] reviewed "pattern-based classification" that combines pattern mining algorithms and machine learning algorithms to classify structured data, such as sequences. This problem is quite similar to the subgroup discovery task [START_REF] Atzmueller | Subgroup discovery[END_REF]. The main difference between both approaches is that subgroup discovery is meant in a descriptive way whereas pattern-based classification is meant in a predictive way.

The main steps of pattern-based classification are the following (1) a pattern mining step building a vector representation of sequences based on the presence or absence of some extracted patterns; and (2) a machine learning algorithm building a classifier based on the vector representations of labeled sequences. The use of a final classifier makes the results difficult to interpret. For this reason, we focus our interest on the extraction of discriminant patterns, i.e., patterns that can be interpreted by their own as a discriminant behavior.

The proposed approaches are based on interestingness measures different from frequency and capturing the differences between occurrences with subsets of sequences. The most-used measures are growth rate [START_REF] Dong | Efficient mining of emerging patterns: Discovering trends and differences[END_REF] and disproportionality [START_REF] Asker | Mining candidates for adverse drug interactions in electronic patient records[END_REF]. The BIDE-D algorithm [START_REF] Fradkin | Mining sequential patterns for classification[END_REF] extracts discriminant sequential patterns instead of frequent ones. This technique allows to use a smaller pattern set than the frequent one with a similar accuracy. Recently, the DCM algorithm [START_REF] Dauxais | Discriminant chronicles mining -application to care pathways analytics[END_REF] extended the discriminant sequential pattern mining with chronicles. But temporal constraints of chronicles (i.e., inter-event duration, so-called time gap, within an interval) is maybe too simple to capture complex temporal relationships, and mining patterns with more complex temporal constraints may improve classification accuracy.

Discriminant Chronicle Mining

Let E be a set of event types totally ordered by ≤ E . An event is a pair (e, t) such that e ∈ E and t ∈ R. 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 sequence of events and L ∈ L where L is a label set. Sequence events are ordered by timestamps and by labels if equality.

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 such case ≤ E is the lexicographic order.

A chronicle is a couple (E, T ) such that: E = { {e 1 . . . e n } }, e i ∈ E and e i ≤ E e j for all 1 ≤ i < j ≤ n. E is a multiset, i.e. E can contain several occurrences of a same event type. T is a set of temporal constraints, i.e. expressions of the form (e i , i)[t -, t + ](e j , j) such that i, j ∈ [n], i < j and t -, t + ∈ R ∪ {-∞, +∞}}. A SID Sequence Label s1 (A, 1), (B, 3), (A, 4), (C, 5), (C, 6), (D, 7) + s2 (B, 2), (D, 4), (A, 5), (C, 7) + s3 (A, 1), (B, 4), (C, 5), (B, 6), (C, 8),(D, 9) + s4 (B, 4), (A, 6), (E, 8), (C, 9) -s5 (B, 1), (A, 3), (C, 4) -s6

(C, 4), (B, 5), (A, 6), (C, 7), (D, 10) -Table 1. Sequences labeled with two classes {+, -}.

A B [-1 ,3 ] C [-3 ,5 ] [-2,2] D [4,5] C [1,3] A B [2 ,3 ] C [4 ,5 ] [-2,2] A C [-3 ,1 ] C [2,4]
Fig. 1. Examples of three chronicles occurring in Table 1 (detailed in the text). From left to right, the chronicles C, C1 and C2.

temporal constraint specifies acceptable delays between the occurrences of the multiset events.

A chronicle C = (E = { {e 1 , . . . , e m } }, T ) occurs in a sequence s = (e 1 , t 1 ), . . . , (e n , t n ) , denoted C ∈ s, iff there exists an injective function f : [m] → [n] such that 1) s = (e f (1) , t f (1) ), . . . , (e f (m) , t f (m) ) is a subsequence of s, 2) ∀i, e i = e f (i) and 3) ∀i, j, t f (j) -t f (i) ∈ [t -, t + ] where e f (i

) [t -, t + ]e f (j) ∈ T . An occurrence of C in s is a list of timestamps O = o 1 , . . . , o m where ∀i ∈ [m], o i = t f (i) ∈ R.
The support of a chronicle C in a set of sequences S is the number of sequences in which C occurs: Frequent chronicle mining consists in extracting all chronicles C in a dataset S such that supp(C, S) ≥ σ min [START_REF] Cram | A complete chronicle discovery approach: application to activity analysis[END_REF]. The DCM algorithm extracts discriminant chronicle [START_REF] Dauxais | Discriminant chronicles mining -application to care pathways analytics[END_REF]. A discriminant chronicle occurs at least g min times more in the set of positive sequences, i.e. sequences labeled with +, than in the set of negative sequences (labeled with -). Then, it can be represented as a classification rule C ⇒ + specifying that sequences in which C occurs more likely belongs to class +. In this mining task, the user has to specify two thresholds: the minimum frequency threshold σ min and the minimal growth rate g min ≥ 1.

supp(C, S) = |{s ∈ S | C ∈ s}|.

Generalized Discriminant Chronicles (GDC)

We now introduce the generalized discriminant chronicle (GDC) meta-model. The GDC meta-model defines an abstract pattern model of temporal behaviors. Next section instantiates different concrete approaches within a unified framework of generalized discriminant chronicle, i.e. a GDC model and a mining algorithm (see Sect. 4.2).

Let L be a set of labels and E be a set of event types, a generalized discriminant chronicle (GDC) is a couple (E, µ), where E is a multiset of event types and µ : R |E| → [0, 1] |L| is an occurrence assessment function.

The occurrence assessment function intuitively gives the confidence measure that a multiset witnesses each label. For some occurrence

O ∈ R |E| of multiset E in a sequence, µ (O) = [p 1 , p 2 , . . . , p |L| ] where ∀i, µ i (O) = p i ∈ [0, 1]
gives the confidence measure that O belongs to the i-th class. In case it sum to 1, this vector can be interpreted as a probability distribution.

GDC generalizes the previous definition of chronicles in two manners: 1) the occurrence assessment function is a generalization of the temporal constraints, 2) the weighted vector of decisions [0, 1] |L| is the generalization of the association of a chronicle to a label (C ⇒ L, L ∈ L).

In particular, it is possible to encode the discriminant chronicle (E, T ) ⇒ L l , where L l ∈ L is the l-th sequence class, as a GDC using µ T defined such that for some occurrence

O = {o i } i∈[|E|] of E: µ T (O) = 1 l if ∀e i [a, b]e j ∈ T , a ≤ o j -o i ≤ b 0 otherwise
where 1 l is a vector of zeros except at position l (value 1), and 0 is a vector of zeros. The size of these two vectors is |L|.

Taking Decisions with Generalized Discriminant Chronicles

This section describes how generalized discriminant chronicles are used to automatically classify new sequences. Let C = (E, µ) be a GDC and s be a sequence to classify such that there exists at least one occurrence O ∈ R |E| of multiset E. Then, decision vector is given by µ(O). But the multiset E may occur several times in s. All decisions have to be combined and the final classification decision for sequence s, denoted d C (s) ∈ L, is the class label with the largest confidence value: The class label can also be decided from a set of chronicles C = {C i } 1≤i≤n . In this case, each chronicle yields its own decision, and they are merged into a final decision. The decision procedure we propose, denoted d C (s) -with a collection of chronicles as subscript, is a linear combination of the number of occurrences of a chronicle C i in s labeled with l j ∈ L, more formally:

d C (s) = argmax l∈L max O µ l (O) (1)
d C (s) = argmax j∈L n i=1 α i,j ν j Ci (s) + β j (2)
where α i,j ∈ R and β i,j ∈ R are parameters, and ν j Ci (s) is the number of occurrences of chronicle C i in sequence s that suggests classifying the sequence in class j (i.e. d Ci (s) = j):

ν j Ci (s) = O ∈ R |E| argmax l∈L (µ l (O)) = l j (3)
= {o C 1 , o C 2 , o C 1 , o C 2 , o C 3 }.
The figure illustrates respective decision vectors. In this case, ν C = [0, 0, 2] because the majority class in the two occurrences of chronicle C is the third one, and

ν C = [0, 1, 2]. Assuming β j = 0 and α i,j = 1, ∀i, j, then the predicted class is d C (s) = 3 because n i=1 α i,3 ν 3 Ci (s) + β 3 = 4 is the largest predicted value among possible classes.
The intuition is that the contribution to the final decision of chronicle C i is more important if this chronicle appears several times in the sequence. Combining the numbers of occurrences is preferred to the combination of confidence measures to prevent from bias due to chronicles with low recall (i.e. poorly informative) but with possible high confidence.

In practice, the α i,j and β j parameters are not set up manually but learned from data as explain in next section.

Learning Generalized Discriminant Chronicles Classifiers

The overall procedure dedicated to learn the sequence classifier is given in Fig. 3. This procedure extracts both a set of γ discriminant chronicles, denoted C, and parameters values of decision function (see Equation 2). First of all, the learning dataset is split into two separated bunches of sequences.

One dataset is used to extract a set of discriminant chronicles C = {C i }. A subset of the γ most discriminant chronicles, denoted C, is selected from C. According to BIDE-D [START_REF] Fradkin | Mining sequential patterns for classification[END_REF], reducing the set of chronicles prevents from overfitting. The second dataset is used to learn the decision procedure. In case of a dataset with two classes (L = {+, -}), equation 2 can be seen as a linear classification problem. Then, a linear-SVM classifier learns the α i,j and β j parameters. In practice, a linear-SVM classifier is also used for a multi-class setting parameters and its model serves as decision function that takes the final classification decision.

We now come back to the mining of generalized discriminant chronicles. This algorithm is based on the original DCM algorithm [START_REF] Dauxais | Discriminant chronicles mining -application to care pathways analytics[END_REF]. Algorithm 1 gives the general principle of GDC mining from a dataset of labeled sequences S. The two main parameters are σ min , a minimal support threshold used to prevent from generating too much poorly-representative chronicles and g min , a minimal growth rate threshold. The overall principle from learning multiple-class chronicles is the one class against all. For some class L, the minimal growth rate g min indicates that a GDC occurs at least g min times more in sequences of class L than in all other sequences.

Algorithm 1 extracts GDC for each class L in two main steps. It firstly extracts M, the set of frequent multisets in the sequences of class L. Then, ExtractDTC learns a µ function from the list of occurrences of a frequent multiset. There is a unique µ per multiset. Its principle is first to build a timegap table [START_REF] Yen | Mining non-redundant time-gap sequential patterns[END_REF] from all occurrences of a multiset and, second, to learn a temporal model from the time-gap table. Each time-gap occurrence is labeled by the label of its sequence and any standard machine learning algorithm can learn the µ function.

The DCM algorithm [START_REF] Dauxais | Discriminant chronicles mining -application to care pathways analytics[END_REF] is based on rule induction (e.g. Ripper [START_REF] Cohen | Fast effective rule induction[END_REF]) to learn temporal constraints of a chronicle (T ). It is a specific case of a µ T function that fits the requirements of the original model of chronicle. Next section introduces alternative classes of occurrence assessment functions.

Algorithm 1 Generalized discriminant chronicle mining

Require: S: labeled sequence sets, L: set of labels, σmin: minimal support threshold, gmin: minimal growth threshold 1: C ← ∅ C is the discriminant chronicle set 2: for all L ∈ L do 3:

M ← ExtractMultiSet(S L , σmin) 4:

for all ms ∈ M do 5:

for all µ ∈ ExtractDTC(S, L, ms, gmin, σmin) do 6:

C ← C ∪ {(ms, µ)} Add a new GDC 7: return C

Examples of GDC Instances

This section illustrates several types of patterns that can be represented by GDC: discriminant sequential patterns, discriminant episodes, SVM-DC and DT-DC. The first two types of patterns illustrate the ability of GDC to model existing patterns (less expressive than the original discriminant chronicles) and the last two models illustrate meaningful generalizations of temporal constraints. In the remaining of this section, we briefly present each of these models as instances of the GDC.

Discriminant episodes and sequences An episode is a set of events ordered temporally by a partial order ≤ E . If ≤ E is a total order, the episode is a sequential pattern. Such classical temporal patterns have been used for mining discriminant behaviors respectively by Fabrègue et al. [START_REF] Fabrègue | Discriminant temporal patterns for linking physico-chemistry and biology in hydro-ecosystem assessment[END_REF] and by Fradkin et al. [START_REF] Fradkin | Mining sequential patterns for classification[END_REF]. A discriminant episode is an episode associated to a label L ∈ L. Such discriminant patterns could be represented by a GDC model instance by the following occurrence assessment function:

µ T (o) = 1 L if ∀(i, j), i ≤ E j ⇒ o i ≤ o j 0 otherwise (4)
For example, a multiset E = { {A, B, C} } ordered by ≤ E such that B ≤ E A and B ≤ E C specifies an episode representing sequences where B occurs before events A and C, no matter the order between A and C. While associated to a label, it becomes a discriminant episode. Expressed with chronicle temporal constraints, we have

T = {(A, 1)[-∞, 0](B, 2), (A, 1)[-∞, ∞](C, 3), (B, 2)[0, ∞](C, 3)}.

Decision Tree Discriminant chronicles (DT-DC) A discriminant chronicle is characterized by temporal constraints on the time gaps (T ). A constraint (e, i)

[t -, t + ](e , j) enforces the time gap δ between some occurrences of events e and e to belong to the interval [t -, t + ]. But chronicle does not allow disjunctions of constraints. For instance, it is not possible to specify that δ may belong to

[t -, t + ] ∪ [t -, t + ].
The DT-DC model replaces the conjunctive rule learning algorithm by a decision tree, such as C4.5 [START_REF] Quinlan | Learning decision tree classifiers[END_REF]. For example, let's consider a dataset of positive sequences matching temporal constraints (A, 1)[2, 3](B, 2) and (A, 1)[7, 9](B, 2) and Fig. 4. Illustration of temporal discrimination power of the different instances of GDC. Planes (x, y) represent a pair of temporal constraints for some sequences (A, t0)(B, t0 + x)(C, t0 + x + y). Positive sequences are those with (x, y) values in the green region, negative sequences have (x, y) values in the red region. The bold-green lines represent the separation boundaries learned by a GDC depending on the type of occurrence assessment function, µ. From left to right: discriminant episodes (temporal constraints with shape [0, +∞]), chronicles (three chronicles with temporal constraints represented by rectangles), DT-DC (a single shape combining several rectangles), linear-SVM (a single chronicle, with generalized linear boundaries). a dataset of negative sequences matching the temporal constraint (A, 1)[2, 9](B, 2). In this case, two chronicles would be discriminant (one per interval, [START_REF] Atzmueller | Subgroup discovery[END_REF][START_REF] Bringmann | Pattern-based classification: a unifying perspective[END_REF] and [START_REF] Dong | Efficient mining of emerging patterns: Discovering trends and differences[END_REF][START_REF] Fradkin | Mining sequential patterns for classification[END_REF]). On the opposite, a single DT-DC will capture the disjunction of intervals in the same model. The expected benefit of this model is a better generalization power.

SVM Discriminant chronicles (SVM-DC) SVM Discriminant chronicles illustrate the case of a complex learnable occurrence assessment function µ, i.e. a µ modeled by a multi-class SV M classifier. Compared to the previous types of patterns, SVM-DC is not limited to linear boundaries to separate examples (time gaps of multiset occurrences) and is a good candidate for yielding accurate patterns.

It is worth noticing that any machine learning model yields a new type of discriminant temporal patterns based on the GDC. The above GDC instances show the potential variety of temporal constraints that GDC can model. Fig. 4 illustrates the shape of boundaries defined by occurrence assessment functions of a chronicle learned from a synthetic dataset.

Experiments

In this part, we compare different results in pattern-based classification using discriminant episodes, discriminant chronicles, DT-DC and SVM-DC. The goal of these experiments is to highlight the impact of the GDC model choice on the accuracy of decision functions presented in Sect. The DT-DC and SVM-DC mining algorithms are implemented in Python using scikit-learn library [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF]. The algorithm dedicated to discriminant chronicle mining is implemented in C++. 3

Experimental Setup

The different experiments compare mean accuracy of different GDC models obtains by cross-validation on synthetic and real datasets.

A 5-cross-validation is performed on each dataset for the parameters σ min and g min of the mining step described in Sect. 3 and the parameter γ described in Sect. 4.2. The domains used for σ min , g min and γ are respectively {0.2, 0.3, 0.4, 0.5, 0.6}, {1.4, 1.6, 1.8, 2, 3} and {90, +∞}. γ = +∞ means that all discriminant chronicles are kept. To improve the computation time, a fourth parameter is introduced for the mining step: the maximal size of extracted chronicles max size. This parameter constrains the maximal number of events that a GDC, i.e. its multiset, can contain. The domain of this parameter is {3, 4, 5, 6}.

The real datasets are the UCI datasets presented in the BIDE-D experiments [START_REF] Fradkin | Mining sequential patterns for classification[END_REF]: asl-bu, asl-gt and blocks. These datasets are part of the standard benchmark for pattern-based classification approaches.

We generated two collections of synthetic datasets:

-A first collection of datasets is based on the principle illustrated by Fig. (5, 5), [START_REF] Giannotti | Efficient mining of temporally annotated sequences[END_REF][START_REF] Giannotti | Efficient mining of temporally annotated sequences[END_REF] and [START_REF] Fradkin | Mining sequential patterns for classification[END_REF][START_REF] Fradkin | Mining sequential patterns for classification[END_REF], [START_REF] Mannila | Discovery of frequent episodes in event sequences[END_REF][START_REF] Mannila | Discovery of frequent episodes in event sequences[END_REF]. Each dataset contains 150 positive and 150 negative sequences. -A second collection of datasets is based on random sequences with shape (A, t A ) (B, To ease the comparison between DT-DC and discriminant chronicles as individual patterns, we choose to use each node of the extracted trees as discriminant temporal constraint. This prevents from comparing the classification power of the decision-tree algorithm and the rule learning algorithm (Ripper ). Furthermore, decision trees produce more discriminant chronicles than Ripper because tree nodes are more redundant. 2. The five most accurate parameter sets for discriminant chronicles on the first synthetic dataset. The number attribute is the total number of chronicles extracted in the 5 runs.

t A + x)(C, t C )(D, t C + k × x) where x ∈ [1, 9], t A =

Results

Let us first present results obtained by the GDC instances on the first synthetic datasets. For this experiment, we only consider the extracted chronicles with multiset { {A, B, C} }. Thus, only one DT-DC and one SVM-DC are extracted for each run, but the number of discriminant chronicles depends on the setting (see Table 2). The three squares defining the positive occurrences may be represented by three discriminant chronicles but it is more difficult to represent the negative occurrences because some of them are not included in a frequent rectangle containing only negative occurrences.

The unique DT-DC represents almost perfectly the discriminant behavior used to generate the dataset with a mean accuracy of 0.99(±0.02). This result was expected because of the dataset structure (squares with boundaries orthogonal to the axis) fits the discrimination capabilities of decision trees.

No SVM-DC are extracted for the default parameters of g min . Our explanation is that concavities in the shape containing positive occurrences disadvantage linear SVM. Relaxing the constraint of g min , SVM-DC reaches a mean accuracy of 0.48(±0.05). This shows experimentally that DT-DC can be more accurate than SVM-DC for some datasets. No discriminant episodes are extracted from these datasets. It was expected from their design as each sequence only contains the items A, B and C, and always in the same order. Some discriminant episodes could be extracted from the negative sequences like the one representing A and B occurring at the same time but these patterns are rare and thus they are not extracted using the defined parameters. It is an example of the need to generalize such a simple model in order to catch more complex behaviors.

We compared these results with the discriminant chronicles obtained using DCM. Among the discriminant chronicles extracted using DCM, discriminating positive occurrences from negative ones generates three perfectly discriminant chronicles representing the three squares used to generate the data with parameters σ min = 0.2, g min = 3 and considering only the multiset { {A, B, C} }. Discriminating the negative occurrences from the positive ones with DCM generates two perfectly discriminant chronicles representing the largest rectangles of negative occurrences on the top left and on the bottom right of the Fig. 4. Then, the mean accuracy of discriminant chronicles is 1 and, contrary to DT-DC, some negative occurrences are not covered by these chronicles. This perfect accuracy 3. Five most accurate parameter sets for regular discriminant chronicles on the second synthetic dataset. The attribute number is the total number of chronicles extracted in the 5 runs.

is correlated to the strategy of Ripper that does not reuse covered occurrences to build a new temporal constraint. The remaining occurrences are so considered too few to be used for building a new constraint. The accuracy is better due to the partial coverage of the dataset made by discriminant chronicles.

We present the same experiment on the second collection of datasets. These datasets are generated to favor the SVM-DC model with boundaries that correlates linearly the time gaps. Again, we only considered the extracted chronicles with multiset { {A, B, C, D} }. For the simplest dataset, the single extracted SVM-DC obtained the accuracy of 1 for the 5 runs. The extracted DT-DC obtained an mean accuracy of 0.99(±0.02). Thus, SVM-DC accuracy is not better than DT-DC, but, DT-DC builds a very large decision tree that overfits the boundaries, which is not suitable in real applications.

Table 3 shows the results of regular discriminant chronicles. We observe that the most accurate parameter sets extract chronicles with a small support and the least accurate parameter sets extract chronicles with a bigger support. We do not present results for discriminant episodes because not any discriminant episodes are extracted. This shows the limit of a too simple model.

Let us now present the results obtained by the three GDC models as individual patterns and as pattern sets on real datasets. An overview of the classification power of the individual patterns of DT-DC, discriminant chronicles and discriminant episodes is given by Table 4. It shows that DT-DC patterns are individually less accurate than discriminant chronicles obtained from the same decision trees. Discriminant episodes are also individually more discriminant than discriminant chronicles. The intuition behind these results is that decision trees overfit more the datasets than temporal constraints or sequential orders. Temporal constraints and sequential orders gather only dense sets of occurrences, represented as squares on Fig. 4, but decision trees generalize examples and gather too dissimilar occurrences.

Conversely to the accuracy, the mean support is higher for DT-DC than for discriminant chronicles and discriminant episodes. Each DT-DC covers more examples than the two other types of patterns. Furthermore, the coverage of discriminant episode is worse than DT-DC due to their poor expressiveness of temporal behaviors. These accuracy results are extreme because we did not use the decision tree parameter constraining a leaf to have a minimal support. For example, if this parameter is set to f min , a decision tree can be seen as a set of discriminant chronicles for a unique multiset.

To illustrate the importance of this parameter, we can compare the two accuracy distributions. Fig. 5 at top left shows the accuracy distribution of DT-DC for the most accurate parameter set. The distribution at bottom right is the accuracy distribution of discriminant chronicles for the most accurate parameter set. The distribution at bottom left is the accuracy distribution of DT-DC for the best discriminant chronicle parameter set with a mean accuracy of 0.23(±0.25). The distribution at top right is the accuracy distribution of discriminant chronicles for the best DT-DC parameter set with a mean accuracy of 0.32(±0.39).

We first notice that the accuracy distributions of discriminant chronicles and DT-DC are almost similar. These histograms show three main peaks: patterns that obtained the accuracy of 0, 0.5 and 1. It makes sense considering that both types of patterns were extracted by the same algorithm. The differences between the mean accuracy are mainly in the proportion of patterns with accuracy equals to 0 and equals to 1. Proportionally to the number of 1-accuracy patterns, the peak of 0-accuracy is higher for DT-DC than for discriminant chronicles. This means that the proportion of patterns that always make wrong decisions is higher for DT-DC than for discriminant chronicles and, thus, that DT-DC overfit more the datasets than discriminant chronicles. The same behavior is observed in most of the experiments.

Finally, Table 5 shows the accuracy of SVM-DC and discriminant chronicles for real datasets: asl-bu, asl-gt and blocks. The parameters used for these results were obtained through a grid search. The involved parameters are σ min , g min and γ but also the C parameter of the global linear SVM classifier. Table 5 shows that SVM-DC produces patterns with better accuracy than discriminant chronicles on asl-bu and asl-gt. For blocks, discriminant chronicles are not more accurate than SVM-DC but the discriminant chronicles are discriminant enough to describe such a simple dataset. A classifier based on chronicles is perfect to classify the blocks sequences.

These results show that combining decisions of discriminant chronicles makes discriminant less competitive than SVM-DC, even if discriminant chronicles are individually accurate. Thereby, we cannot conclude from previous results that discriminant chronicles are the most accurate GDC. Indeed, chronicles do not involve all the occurrences of a multiset and represent very specific discriminant behaviors. But in a pattern-based classification context, a set of very discriminant chronicles is not sufficient to cover the whole dataset and so to obtain a good accuracy. This leads to a typical overfitting situation.

Finally, Table 5 also gives the mean computation times for both approaches. These times are strongly related to the computing times of machine algorithms which vary a lot depending on datasets. Discriminant chronicle mining (DCM) is faster in most cases thanks to a particular implementation effort for this approach.

Conclusion and Perspectives

This article presents a generalization of the model of discriminant chronicles. The model of generalized discriminant chronicles (GDC) proposes to combine a multiset pattern and a decision function learned from the temporal duration between occurrences of a multiset pattern. Initially, discriminant chronicles were extracted using a rule learner and their temporal boundaries were intervals. Such a representation may be too restrictive an assumption on how to discriminate temporal sequences and, thus, had to be generalized.

We demonstrate the expressiveness of the framework by showing that it can model classical patterns (episodes, sequential patterns and chronicles) and episodes, sequential patterns and new types of patterns. DT-DC are based on decision tree classifiers and SVM-DC are based on a SVM classifier.

The experiments show that individual chronicles have good accuracy but SVM-DC overtakes the combination of chronicles on real datasets. An interesting perspective of this work is to blend different types of chronicles within the same combination. Furthermore, comparison in terms of interpretability between several GDC instances would be interesting. Indeed, chronicles are attractive for its interpretability, thanks to its graphical representation. However, new temporal patterns like DT-DC or SVM-DC can not be graphically represented so simply. Then it would be possible to suggest GDC instances that would offer a tradeoff between prediction accuracy and interpretability.

Fig. 1

 1 Fig. 1 illustrates three chronicles represented by graphs. Chronicle C = (E, T ) where E = { {A, B, C, C, D} } and T = {(A, 1)[-1, 3](B, 2), (A, 1)[-3, 5](C, 3), (B, 2)[-2, 2](C, 3), (B, 2)[4, 5](D, 5), (C, 3)[1, 3](C, 4)} is illustrated at the top left. Chronicle C (see Fig. 1 on the left), occurs in sequences s 1 , s 3 and s 6 of Table 1. We notice there are two occurrences of C in sequence s 1 . Nonetheless, its support is supp(C, S) = 3. The two other chronicles, denoted C 1 and C 2 , occur respectively in sequences s 1 and s 3 ; and in sequence s 6 . Their supports are supp(C 1 , S) = 2 and supp(C 2 , S) = 1.

Fig. 2 .

 2 Fig.2. Examples of multiple occurrences of two chronicles C and C to be combined to make the final decision. A "rake" illustrates item positions in the sequence of one occurrence of the multiset.

Fig. 2

 2 Fig. 2 illustrates a sequence s classified with a set of two chronicles C and C , and |L| = 3. Chronicle C occurs twice in s and C occurs thrice, O = {o C 1 , o C 2 , o C 1 , o C 2 , o C 3 }. The figure illustrates respective decision vectors. In this case, ν C = [0, 0, 2] because the majority class in the two occurrences of chronicle C is the third one, and ν C = [0, 1, 2]. Assuming β j = 0 and α i,j = 1, ∀i, j, then the predicted class is d C (s) = 3 because

Fig. 3 .

 3 Fig. 3. Overall procedure of sequence classifier learning.

  4.1: d C (s) and d C (s). In the experiments we analyze the classification power of individual GDC (i.e. d C (s)) and of a set of GDC (i.e. d C (s)).

4 .

 4 Random sequences (A, 0)(B, x)(C, x + y) have been generated: the event A occurs at time 0 in each sequence and the time gaps between A and B and between B and C are randomly generated in the interval[0,[START_REF] Nanni | Extracting trees of quantitative serial episodes[END_REF]. The label of the sequence is generated depending on the temporal constraints. According to Fig.4, positive examples having time gaps located in one of the three green squares. Coordinates of the square corners are (1, 1),[START_REF] Dauxais | Discriminant chronicles mining -application to care pathways analytics[END_REF][START_REF] Dauxais | Discriminant chronicles mining -application to care pathways analytics[END_REF];

  [START_REF] Nanni | Extracting trees of quantitative serial episodes[END_REF] and t C ∈[START_REF] Asker | Mining candidates for adverse drug interactions in electronic patient records[END_REF] 29]. The two sequence classes are distinguished by the k factor: k = 2 for positive sequences while k = 1 for negative ones. Each dataset contains 100 positive and 100 negative sequences.

Fig. 5 .

 5 Fig. 5. Accuracy distribution for DT-DC and discriminant chronicles with parameters σmin = 0.5, gmin = 2 and max size = 5 for the first row and σmin = 0.3, gmin = 2 and max size = 3 for the second one.

Table 4 .

 4 Comparison table of DT-DC, discriminant chronicles and discriminant episodes for the 5 best parameter sets in terms of mean accuracy on asl-bu.

		σmin gmin max size accuracy	support
	discriminant 0.3 2.0	3	0.92(±0.14) 5.62(±8.60)
	episodes	0.3 1.8	4	0.86(±0.19) 5.24(±7.65)
		0.6 3.0	3	0.86(±0.20) 2.96(±5.54)
		0.6 1.8	4	0.83(±0.18) 11.41(±9.71)
		0.3 1.6	3	0.83(±0.22) 4.41(±5.94)
	discriminant 0.3 2.0	3	0.64(±0.37) 3.16(±2.91)
	chronicles	0.3 1.8	4	0.60(±0.40) 2.69(±2.68)
		0.6 3.0	3	0.59(±0.33) 5.74(±7.01)
		0.3 1.6	3	0.58(±0.38) 3.67(±3.28)
		0.6 1.8	4	0.57(±0.34) 3.83(±3.37)
	DT-DC	0.5 2.0	5	0.38(±0.28) 8.12(±6.57)
		0.6 3.0	5	0.37(±0.25) 8.61(±6.34)
		0.2 1.6	3	0.36(±0.34) 5.99(±5.68)
		0.5 1.8	3	0.34(±0.21) 13.2(±8.19)
		0.5 1.8	4	0.33(±0.23) 10.0(±7.40)

Acknowledgements

This work has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No [694980] SYNTH: Synthesising Inductive Data Models).