Thomas Guyet

René Quiniou

Mining temporal patterns with quantitative intervals

In this paper we consider the problem of discovering frequent temporal patterns in a database of temporal sequences, where a temporal sequence is a set of items with associated dates and durations. Since the quantitative temporal information appears to be fundamental in many contexts, it is taken into account in the mining processes and returned as part of the extracted knowledge. To this end, we have adapted the classical APriori [1] framework to propose an efficient algorithm based on a hyper-cube representation of temporal sequences. The extraction of quantitative temporal information is performed using a density estimation of the distribution of event intervals from the temporal sequences. An evaluation on synthetic data sets shows that the proposed algorithm can robustly extract frequent temporal patterns with quantitative temporal extents.

Introduction

The classical view of frequent sequential patterns mining (FSPM) [START_REF] Agrawal | Mining sequential patterns[END_REF] considers a large database of sequences D. Each sequence s ∈ D is an ordered set of items with possible duplications. The mining task consists in extracting the longest patterns that are sufficiently frequent, i.e. that can be found in a number of sequence of D above a predefined threshold.

The FSPM is strongly motivated by its application to knowledge extraction from customer purchase database [START_REF] Agrawal | Mining sequential patterns[END_REF], DNA sequences, web logs [START_REF] Masseglia | Efficient mining of sequential patterns with time constraints: Reducing the combinations[END_REF], medical time series [START_REF] Giannotti | Mining sequences with temporal annotations[END_REF][START_REF] Quiniou | Temporal abstraction and inductive logic programming for arrythmia recognition from electrocardiograms[END_REF], etc. Most of these investigations have only considered a linear sequential notion of time. But, in some contexts, the quantitative temporal dimension of data provides fundamental information that should be taken into account in the mining processes and returned as part of the extracted knowledge. For example, in web log analysis, the browsing patterns can be refined by the time spent to explore the web pages. The comparison between the quantitative time spent on a web page and the required time to browse its content may be useful to decide whether some part of the information has not been read. In a medical context, the temporal information is crucial to diagnose the patients accurately. This is obvious in situations ranging from diabetes mellitus to intensive care unit ECG monitoring and artificial ventilation. For example, in [START_REF] Quiniou | Temporal abstraction and inductive logic programming for arrythmia recognition from electrocardiograms[END_REF] different kinds of cardiac arrhythmias could be discriminated thanks to the quantitative temporal intervals between events (chronicles models).

Some authors, e.g. Chiu et al. [START_REF] Chiu | Probabilistic discovery of time series motifs[END_REF], propose to simulate event duration by the repetition of a same event having a fixed atomic duration. However, in some applications it is necessary to distinguish the repetition of events from a single occurrence of this event: for example, two apneas of 30s each should not be confused with a single apnea of 1min. This distinction is only possible with a quantitative representation of the time information.

Unfortunately, discovering the quantitative temporal extents of events is a difficult problem. The construction of the sequence of items should be intertwined with the construction of representative durations. On the one hand, temporal sequence instances are required to construct the representative duration between two events in a temporal sequence. But, on the other hand, the durations are required to identify the temporal sequence instances. To tackle this problem, we propose to enhance the classical APriori algorithm to handle quantitative temporal extents of the items.

In section 2, we define the temporal sequence, the hypercube representation and temporal pattern. Then in section 3, we give some details about temporal pattern extraction task. In section 4, the algorithms are presented and the section 5 presents the evaluations. Finally, we present related work in section 6.

Temporal sequences and temporal patterns

2.1. Temporal sequences Definition 1. (Temporal sequence) A temporal sequence S is a set of temporal items, where a temporal item A, denoted as A = (A, [l, u]), is a symbolic event A associated with a non empty interval [l, u], where l, u ∈ R, l < u, are timestamps:

S = {(s i , [l i , u i ])} i∈Nn
n, the number of temporal items, is called the dimension of the sequence S .

Notice that the delay between two events is indirectly given by the beginning instants of the event intervals, and that there is no assumption on their occurrence. In particular, event-overlapping is possible.

The temporal sequences may represent several runs of a dynamic process that generates these events, or may be extracted from a sliding window over long temporal sequences. In the latter case, the timestamps are translated in order to represent the relative time within the window (and not the absolute time). So, the temporal sequences can be compared with each other. This representation of temporal sequences is used to define the similarity between two temporal sequences S 1 and S 2 as the normalized overlapping volume of their hypercube representations, i.e. the volume of the intersection of the representations of S 1 and S 2 divided by the volume of the biggest hyper-cube. Definition 6. (Temporal sequences similarity) Let S 1 and S 2 be two temporal sequences, then the similarity between S 1 and S 2 , denoted by sim(S 1 , S 2 ), is defined as:

Definition 2. (Temporal sub-sequence) A temporal sub- sequence of S = {(s i , [l i , u i ])} i∈Nn , is a temporal se- quence S ′ of dimension m < n, such that S ′ = {(s j , [l j , u j ])} j∈P (Nn) , where P (N n ) is a subset of N n .
(l i , u i ) i∈N : ∀x ∈ R n , x ∈ H ⇔ ∀i ∈ N, l i ≤ x i ≤ ui.
sim(S 1 , S 2 ) = 8 < : 0 if S 1 = S 2 Q n i=1 max(0,min(u 1 i ,u 2 i )-max(l 1 i ,l 2 i )) max( Q n i=1 u 1 i -l 1 i , Q n i=1 u 2 i -l 2 i ) if S 1 = S 2
where

S 1 = S 2 ⇔ ∀i ∈ N n , s 1 i = s 2 i max 0, min(u 1 i , u 2 i ) -max(l 1 i , l 2 i )
gives the size of the intersection of two intervals. Then, the similarity is the product of these sizes over the maximum product of the interval sizes of S 1 and S 2 , i.e. the normalized volume of the intersection. This function is not a metric, but assuming that intervals cannot be empty, it is easy to prove that the proposed similarity is a positive-definite and symmetric function.

Temporal patterns

Definition 7. (Temporal pattern) A temporal pattern is a temporal sequence (P = {(p i , [l i , u i ])} i∈Nn ) that is the representative of a set of similar temporal sequences.

Similarly to Giannotti et al. [START_REF] Giannotti | Mining sequences with temporal annotations[END_REF], a pattern is a representative. However, in [START_REF] Giannotti | Mining sequences with temporal annotations[END_REF], patterns are rules a t -→ b, meaning that the representative duration between events a and b is t. Our patterns provides the delay between events as well as the duration of events. Chronicles [START_REF] Dousson | Discovering chronicles with numerical time constraints from alarm logs for monitoring dynamic systems[END_REF] or delta patterns [START_REF] Yoshida | Mining sequential patterns including time intervals[END_REF] are not representatives. They just generalize the represented temporal instances. In fact, the interval between two events gives the lower bound and the upper bound of the delay between these two events.

p i , u p i ] ∩ l s f (i) , u s f (i) = ∅.
Definition 9. (Temporal pattern strict-coverage) A temporal pattern P strictly-covers a temporal sequence S, denoted S ≺ P, if S P and cov P (S) = 0.

Temporal pattern extraction

Temporal pattern extraction aims at finding the interesting temporal patterns from a set of temporal sequences (denoted D). In our approach, interesting temporal patterns are the longest patterns such that sequences similar to this pattern can be frequently encountered in D. [START_REF] Bozdogan | Choosing the number of component clusters in the mixture-model using a new informational complexity criterion of the inverse-Fisher information matrix[END_REF][START_REF] Chen | Discovering fuzzy timeinterval sequential patterns in sequence databases[END_REF])

s 1 = (A, [1, 3]) , (B,
s 2 = (A, [1.2, 3.3]) , (B, [3.8, 4.6]) , (C, [5.8, 6.7]) s 3 = (A, [1.1, 3.4]) , (D, [1.5, 5]) , (B, [4.1, 5.3]) s 4 = (A, [0.9, 2.6]) , (B, [4.1, 5.2]) , (C, [6.2, 7.3]) s 5 = (A, [0.1, 0.8]) , (B, [4.2, 5.2])
Given a frequency threshold f = 0.5, there is only one frequent symbolic signature of dimension 2: (A, B). Then, temporal extents must be associated with each event, but several temporal patterns are possible: [START_REF] Bozdogan | Choosing the number of component clusters in the mixture-model using a new informational complexity criterion of the inverse-Fisher information matrix[END_REF][START_REF] Chen | Discovering fuzzy timeinterval sequential patterns in sequence databases[END_REF])) has a better mean coverage (≈ 0.71), but does not strictly-cover s 5 .

• ((A, [0.1, 3.4]), (B, [3.8, 5.3])) strictly-covers all the examples, but the mean coverage is low (≈ 0.36). • ((A, [1.1, 3.1]), (B,
Moreover, several temporal extents that strictly-cover the same set of temporal sequences can be computed for a temporal pattern. Our aim is to define a unique and representative temporal extent for each interval of a temporal pattern. Since, the distributions of temporal intervals can highlight such representative temporal extents, we propose a solution to construct unique and representative temporal extents which relies on the estimation of the interval distributions.

Example Id

Example Id

Figure 3. Interval distribution of A (left) and B (right).

For example, Figure 3 shows the distribution of A intervals and B intervals of the example 4 that can be used to extract the temporal extents. Clearly, temporal sequence s 5 rises a problem: all the sequences seems "similar" with respect to the B-intervals distribution, but s 5 does not seem "similar" to the others with respect to the A-interval distribution. Consequently, the distribution of A-intervals in the pattern having (A, B) as symbolic signature can not be inferred from all A-intervals. More generally, this shows clearly that the interval distributions of a pattern can not be inferred from the interval distributions of its subpatterns. Therefore, interval distribution extraction is intertwined with symbolic signature construction. This is the temporal pattern extraction issue to tackle.

At this point, the hyper-cube representation is helpful. This representation allows to consider the distribution of the intervals for all temporal dimensions globally at the same time. In Figure 4, the frequency of temporal regions is outlined with darkening color: the darker a region is, the more temporal sequences overlap this region. Our proposition is based on hyper-cube distributions which can be approximated using density-based multidimensional clustering (e.g. EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]). Then, extracted clusters are used to compute representative temporal bounds.

In our framework, we approximate distributions with Gaussian mixture models. Once computed, each Gaussian is associated with a possible temporal pattern. The temporal intervals to overlay over the symbolic signature are extracted from a Gaussian of the model by computing the bounds associated with an interval representing some ratio of the whole confidence. This is the temporal extent threshold. In our experiments, we have chosen 95% confidence intervals.

Figure 5 illustrates the Gaussian distribution estimation and the extracted temporal bounds. Two clusters represented by ellipses are computed, so two temporal patterns are extracted. Each ellipsis axis gives the temporal bounds for the item associated with the axis dimension.

Note that it is easy to understand 2-dimensional temporal sequence graphs and their distribution. For higher dimensions, graphical representations are almost impossible to understand but the same reasoning can be done.

Framework and algorithms

Our framework is based on the APriori algorithm [START_REF] Agrawal | Mining sequential patterns[END_REF] to construct the longest frequent symbolic signatures. The main idea of this algorithm is based on the following property: every symbolic signature that covers a frequent symbolic signature is frequent. This property is helpful to prune a lot of candidates of size n knowing the infrequent symbolic signatures of size strictly inferior to n because if a symbolic signature of size n is covered by an infrequent symbolic signature then it is not frequent.

The algorithm, whose pseudo-code is given in Algorithm 1, iterates two stages, namely (1) the selection of frequent temporal patterns of dimension n, and (2) the generation of symbolic signature candidates of dimension n + 1 from those of dimension n. These two stages are detailed in the following sections. The process terminates when there is no more potential longer candidate or when the candidates are no longer sufficiently frequent.

The algorithm has been adapted to process hyper-cube representations of temporal sequences. In particular, the selection of frequent temporal patterns uses the distribution estimation approach to extract the temporal intervals (see section 4.2), and the candidate generation uses a priori constraints enriched by temporal bounds (see section 4.3).

Main algorithm

The first step of the algorithm consists in constructing the frequent symbolic signatures of dimension 1. If an item (e.g. (A)) has less occurrences than f min * |D|, then it is not frequent and according to the APriori algorithm principle, it should not be taken into account. Then we enter in the main selection-generation loop. Assume that L n , the set of symbolic signatures of dimension n, has been constructed. As will be seen later, these symbolic signatures are good candidates to be frequent. The selection phase aims (1) at verifying the frequency of generated candidates and (2) at constructing their associated temporal intervals. Given p ∈ L n , we first verify that the symbolic signature of p is frequent. Then, and only then, we can expect to find out temporal intervals using the density estimation of the interval distribution. The candidate selection function is detailed in the next section. This function returns a set of frequent temporal patterns that are added to M n . Note that a symbolic signature can give rise to several temporal patterns (see Figure 5 for instance).

Once all symbolic signatures have been processed and if M n is empty, then no temporal patterns of size n is frequent. Thus, the result given by the algorithm is the set of frequent temporal patterns of size n -1.

Algorithm 1: Temporal pattern mining algorithm (inspired from the APriori algorithm).

Candidate selection

Algorithm 2 details the candidate selection function. This function aims at identifying the frequent temporal patterns in D that can be associated with some symbolic signature p. There is two main tasks: (1) construct the representative temporal bounds for p, and (2) prune the infrequent temporal patterns.

The main part of the algorithm consists in estimating the density function for the distribution of the hyper-cube representation of p instances. We use a Monte-Carlo approach to estimate the density function. For each sequence s ∈ D that is covered by p, random points (vectors in dimension n) are uniformly generated inside the hyper-cube defined by s p . The number of points is proportional to the volume of the hyper-cube. Moreover, to deal with the curse of dimensionality [START_REF] Bellman | Dynamic Programming[END_REF], this number is exponentially proportional to the dimension of the hyper-cube. The required number of points is given by the following formula:

nb = vol (s p ) * d dim(p) (1)
where d is a parameter of our algorithm that can be easily adjusted depending on the time values expected in intervals. The distribution of generated points, denoted hh in Algorithm 2, represents the distribution of the intervals. Then, algorithm EM [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF] is used to estimate the Gaussian mixture model from these points. In the most general case, the density function is:

f (x) = N k=1 c k (2π) -d/2 |Σ k | -1/2 e -1 2 (x-µ k ) t Σ -1 k (x-µ k )
where N is the number of Gaussians, µ k is the mean vector and Σ k is the variance matrix of the k th Gaussian, and c k is the proportion of the Gaussian in the mixture.

In the EM algorithm the number of Gaussians N must be given, but the correct number of clusters is unknown.

Consequently, the algorithm is executed for several numbers of clusters and the best mixture is selected. In practice, the normalized entropy criterion (NEC) is used to select the number of clusters between 1 and nb 0.3 [START_REF] Bozdogan | Choosing the number of component clusters in the mixture-model using a new informational complexity criterion of the inverse-Fisher information matrix[END_REF].

In addition, we assume that the intervals in a temporal pattern are independent. Consequently, the EM algorithm is constrained to extract Gaussians with diagonal variance matrices. This assumption reduces the computation cost.

Once, the Gaussian mixture model has been computed, the temporal patterns can be extracted. First of all, a Gaussian gm must have a sufficient proportion denoted c k in the mixture formula and denoted gm.prop in Algorithm 2. It means that if a symbolic signature has a frequency of f , then f * gm.prop gives the number of temporal sequences strictly-covered by the temporal pattern associated with an extracted Gaussian gm. Such a temporal pattern is retained only if f * gm.prop ≥ f min .

Finally, the interval bounds are computed by:

µ k - α 2 (2π) -d/2 |Σ k | -1/2 , µ k + α 2 (2π) -d/2 |Σ k | -1/2
where α is a parameter used to adjust the width of the interval (currently fixed to 0.8).

Candidate generation

Now, we present the candidate generation (see Algorithm 3). To generate only the potentially useful candidates, we extend the classical APriori constraint on symbolic signature to a constraint that takes into account the temporal intervals thanks to the hyper-cube representation. Let P = {(s i , [l i , u i ])} Nn+1 be a temporal pattern of dimension n + 1. P may be frequent if every orthogonal projection of its hyper-cube on each subspace of dimension n overlaps with at least one hyper-cube of M n , the set of frequent temporal patterns of dimension n, i.e.:

∀l ∈ [1, n + 1], ∃p ∈ Mn, sim " (si, [li, ui]) N n+1 -{l} , p " = 0
In the first phase of the generation, temporal patterns of dimension n + 1 are generated by concatenating an element of M n and an element of L 1 (the set of frequent items). The element of L 1 is associated with infinite temporal bounds. In a second phase, the a priori infrequent elements are pruned.

Evaluation

The algorithms have been implemented in MatLab v7.6 (R2008a) 1 . We have used the MixMod library [START_REF] Biernacki | Model-based cluster and discriminant analysis with the MIXMOD software[END_REF] to compute Gaussian mixture models. Our experiments were performed on a bi-processor Pentium IV 3.6GHz, 2Go of RAM. To evaluate the properties of our algorithm, we have used synthetic data sets. The simulation process is flexible enough to quantitatively evaluate several properties such as accuracy, computation time and robustness against the noise.

To our knowledge, there is no other algorithms for extracting temporal sequences with quantitative temporal intervals that we could quantitatively compare with. In section 6, we present a qualitative comparison of our temporal pattern extraction method to other temporal sequence mining methods.

Data set simulation

The data simulation process generates random temporal sequences based on a temporal pattern prototype to which is added temporal noise and structural noise.

A temporal pattern prototype is a set of n quintuplets ({(E i , µ bi , σ bi , µ di , σ di )} i∈Nn ) where E n is an event name, µ bn , µ dn (resp. σ bn , σ dn ) are the mean (resp. the standard deviation) of the generated begin instants and durations of E n . This prototype specifies the temporal pattern to discover ({(E i , [µ bi , µ bi + µ di ])} i∈Nn ), and the standard deviation parameters quantifies the Gaussian distribution of the interval bounds. The larger the standard deviation is, the harder the temporal pattern extraction is. For the sake of simplicity, all standard deviations are equal to tN ∈ [0, 1]. This parameter quantifies the temporal noise in the data set.

In addition, some structural noise can be added. A structural modification consists in randomly deleting an event or modifying an event name. sN ∈ [0, 1] is the ratio of structurally modified temporal sequences in the data set. Finally, 1 Source code for the algorithm and the data generator available on-line: http://www.irisa.fr/dream/QTempIntMiner/. Figure 6 illustrates the temporal sequence generation process (nb = 10, sN = 0.1). The fourth sequence has been randomly generated (rP = 0.1), several sequences such as sequence number 8, have been structurally corrupted (sN = 0.1) and time bounds fluctuates due to the temporal noise (tN = 0.2).

In the following, the prototype used to generate the data sets (nb = 20) was {(E k , [3k, 3k + 1])} k∈Nn . When not explicitly given, the parameters take their default values n = 4, nb = 20, sN = 0 and tN = 0.2. For each set of parameters, 10 different data sets were generated to yield statistically significant results.

The accuracy (in [0, 1]) of the temporal pattern extraction process is evaluated by the similarity value between the prototype and the best extracted temporal pattern (see Definition 6). This means that if the temporal pattern and the prototype share the same symbolic signature, then the accuracy is given by the relative common volume. Otherwise the accuracy will be set to 0. A non-zero accuracy points to a correct symbolic signature extraction (this is always the case with the basic parameters), thus the higher the accuracy, the better the extracted temporal bounds.

Experiments and results

The results are organized as follow: first, we present evaluations of the computation time and the accuracy of the algorithm according to the parameters nb, n, tN and sN (linked to the temporal sequence representation). Then we demonstrate the robustness of the algorithm in finding out the interesting temporal patterns in a large amount of temporal sequences. Finally, we highlight some properties on examples.

Computation time and accuracy Short computation time is a strong constraint on sequential pattern mining algorithms. The computation time of APriori is known to increase exponentially with the pattern size (i.e. the prototype dimension n). Moreover temporal bounds extraction in the selection phase is also time consuming. The number of examples for the EM algorithm is proportional to d n , where d is a parameter (see eq. 1). Practically, the maximum dimension of the extracted temporal pattern may be limited to have reasonable computation times. The results (Figure 7, left) show that the computation time increases exponentially with the prototype dimension (n ranges from 2 to 5). For d = 4, the computation time ranges from 2 ′′ to 3 ′ 41 ′′ . Figure 7 right gives the accuracy. The accuracy decreases notably when the dimension increases. This comes from the fact that the accuracy is evaluate from the similarity: by definition the similarity computes the product of the relative sizes (lying in [0, 1]) of the intersection along each dimension of two hyper-cubes. Experiments have been performed with six values of d from 1.5 to 6. We expected that the computation time should increase with d, while the accuracy should become better. Practically, this is the case for d ≤ 3. However, we did not notice any statistically significant improvement of the accuracy for d ≥ 3. Nonetheless, the computation time is significantly higher, so we set d = 3 for the other experiments.

Figure 8 illustrates the computation time and the accuracy with respect to the number of examples (nb ranges from 100 to 1000). On the one hand, the computation time increases linearly, and on the other hand, the accuracy remains quite the same. Thus, this experiment shows that our algorithm is robust with respect to the database size. Finally, Figure 9 illustrates the accuracy with respect to the temporal noise. There is two parts in this graph: at the beginning, the accuracy increases, then it decreases when more temporal noise is added. The second part shows a normal behavior: the higher the temporal noise, the less accurate the temporal intervals. The dashed line highlights failures in pattern extraction (the symbolic signature could not be successfully extracted). This means that when the temporal variances become too high, the algorithm is no more able to reconstruct the symbolic signatures due to the difficulty to identify the correct Gaussian mixture models. For tN = 0.6, it occurs only in 10% of the experiments, but for tN = 1 it occurs in 50% of the experiments.

We expected to obtain a very good accuracy and low variances when the temporal noise is low. But the first part of the Figure 9 shows the opposite. It can be explained by observing that many extracted intervals are shifted compared to the prototype intervals. This behavior is explained below.

We conclude from these experiments that (1) the algorithm extracts temporal patterns with accurate temporal intervals, and (2) in spite of the theoretical drawbacks (confirmed by the experimental results), the computation time is reasonable.

Temporal interval enlargements and shifts For temporal interval extraction, we hypothesize that the interval distribution fits a Gaussian distribution. We identified two cases where this hypothesis is false. The first one occurs when the variance of the lower (or upper) bound of a prototype interval is high compared to the duration of this interval (see Figure 10,left). In this case, the extracted temporal interval is larger than expected.

The second case occurs when the variance of the lower bound of a prototype interval is low compared to the variance of its duration (see Figure 10,right). In this case, the extracted temporal interval is shifted. In fact, the distribution is not Gaussian anymore: it is rather exponential. Knowing these possible behaviors is helpful to determine the assumption under which the extraction algorithm will be efficient. As a consequence, the data set must be such that the variance of interval lower bounds must be low but sufficiently high compared to their respective duration variance.

Robustness to structural and database noises In the previous experiments, database temporal sequences were corrupted with temporal noise only. In the present section, we keep some temporal noise (tN = 0.2) but we introduce structural noise in the temporal sequence generation. The robustness to structural corruption can be assessed by varying the f min parameter of the APriori framework. As-suming that rP = 0, i.e. that there are only positive examples (possibly corrupted) of the temporal pattern and, given f min , we expect that the algorithm will be robust with respect to a structural noise equal to f min .

Figure 11 illustrates the accuracy with respect to the structural noise level and f min = 0.5. Temporal pattern extraction failures occur when sN ≥ 0.35 (only 1 failure out of the 10 trials for sN = 0.35). When sN = 0.5 temporal pattern extraction fails in more than half of the cases (6 failures out of 10 trials). This experiment confirms that when f min is low the robustness of our algorithm against the structural noise is high. However, in real databases, positive examples of a temporal pattern are mixed [START_REF] Agrawal | Mining sequential patterns[END_REF] with positive examples of other temporal patterns and (2) with random irrelevant temporal sequences. Then, f min must be sufficiently low both to find out the few positive examples of a temporal pattern, and to be robust against the structural noise. But, if f min is too low, the computation time may hugely increase and irrelevant patterns could be extracted.

To confirm this hypothesis, we have generated a more realistic data base containing 1000 temporal sequences with 80% of randomly generated sequences (rP = 0.8). Two different prototypes were used to generate relevant temporal sequences (10% each). Consequently, f min must be lower than 0.1 (ratio of positive examples in the database per temporal pattern) to consider relevant temporal sequences as frequent, but due to additional structural noise (sN = 0.2), it must be lower than 0.1 * (1 -sN ). Thus we choose f min = 0.05. The experiment showed that our algorithm is able to find out at least one temporal pattern and the two temporal patterns in 65% of the trials with a mean accuracy of 0.33 and a mean computation time of 9 ′ 07 ′′ .

Additional properties Other experiments have been performed to illustrate interesting additional properties of our algorithm. For example, our algorithm can extract (1) temporal patterns with temporal items that overlap or (2) temporal patterns with twins, i.e. several identical events (associated with different intervals). Contrary to existing approaches, e.g. [START_REF] Dousson | Discovering chronicles with numerical time constraints from alarm logs for monitoring dynamic systems[END_REF], these temporal patterns do not introduce difficulties to our algorithm thanks to the hyper-cube representation that separates the temporal information for each item. In the case of temporal patterns with twins, two dimensions can be separated if two representative temporal extents are extracted. This can be computed from Gaussian mixture models. For example, it can distinguish the two representative Gaussians of Figure 5.

Related work

Temporal sequence mining involves two different kinds of issues: FSPM algorithm with time constraints [START_REF] Lee | Database support for data mining applications : discovering knowledge with inductive queries, chapter Constraint based mining of first order sequences in SeqLog[END_REF][START_REF] Masseglia | Efficient mining of sequential patterns with time constraints: Reducing the combinations[END_REF], and temporal relation discovery [START_REF] Giannotti | Mining sequences with temporal annotations[END_REF][START_REF] Höppner | Learning dependencies in multivariate time series[END_REF][START_REF] Hwang | Discovery of temporal patterns from process instances[END_REF][START_REF] Yoshida | Mining sequential patterns including time intervals[END_REF]. Hirate et al. [START_REF] Hirate | Generalized sequential pattern mining with item intervals[END_REF] propose a generalized FSPM with the capability to handle two kinds of item interval measurements, item gap and time interval.

Time constraints approaches, make use of minimum and maximum gap values that must be defined as the gap constraint by the user. Then the algorithms, such as SeqLog [START_REF] Lee | Database support for data mining applications : discovering knowledge with inductive queries, chapter Constraint based mining of first order sequences in SeqLog[END_REF] or GTC (Graph for Time Constraints) [START_REF] Masseglia | Efficient mining of sequential patterns with time constraints: Reducing the combinations[END_REF], extract ordered sequences of items that respects these gaps. However, the algorithm do not discover the time constraints. The gaps are used to get rid of insignificant patterns and rules so as to reduce the number of generated patterns and rules.

Temporal relation discovery approaches use extended definitions of temporal sequences. In [START_REF] Höppner | Learning dependencies in multivariate time series[END_REF][START_REF] Kam | Discovering temporal patterns for interval-based events[END_REF], qualitative temporal relations on intervals, i.e. Allen temporal relations, are associated with sequence items. Höppner [START_REF] Höppner | Learning dependencies in multivariate time series[END_REF] propose a level-wise algorithm inspired from the APriori algorithm to extract efficiently both event sequences and temporal relations.

Chen et al. [START_REF] Chen | Discovering fuzzy timeinterval sequential patterns in sequence databases[END_REF] or Quiniou et al. [START_REF] Quiniou | Temporal abstraction and inductive logic programming for arrythmia recognition from electrocardiograms[END_REF] propose an intermediate representation of temporal sequences between qualitative temporal relations and quantitative temporal constraints. Chen et al. [START_REF] Chen | Discovering fuzzy timeinterval sequential patterns in sequence databases[END_REF] uses the concept of fuzzy sets to extend the original APriori algorithm and PrefixSpan algorithm so that fuzzy time-interval sequential patterns are discovered from databases. Quiniou et al. [START_REF] Quiniou | Temporal abstraction and inductive logic programming for arrythmia recognition from electrocardiograms[END_REF] uses a first-order relational learning method to construct a graph of temporal constraints called chronicles.

The closest approaches to ours are [START_REF] Dousson | Discovering chronicles with numerical time constraints from alarm logs for monitoring dynamic systems[END_REF][START_REF] Giannotti | Mining sequences with temporal annotations[END_REF][START_REF] Hwang | Discovery of temporal patterns from process instances[END_REF][START_REF] Yoshida | Mining sequential patterns including time intervals[END_REF]. The temporal information associated with temporal sequences is represented by quantitative interval extents. In [START_REF] Giannotti | Mining sequences with temporal annotations[END_REF] --→ B, denoting a sequential pattern A → B that frequently occurs in the data set with transition times from A to B that are contained in [0, 3]. The FACE system [START_REF] Dousson | Discovering chronicles with numerical time constraints from alarm logs for monitoring dynamic systems[END_REF] adapted the APriori framework [START_REF] Agrawal | Mining sequential patterns[END_REF] to extract the temporal extents of the interval between two events as the enveloping interval of the temporal sequence instances intervals. As us, Giannotti et al. and Yoshida et al. [START_REF] Yoshida | Mining sequential patterns including time intervals[END_REF] use a clustering method to extract the representative values of the transitions. Yoshida et al. [START_REF] Yoshida | Mining sequential patterns including time intervals[END_REF] provide an heuristic for finding some frequent Delta-Patterns but their method is not exhaustive. Giannotti et al. [START_REF] Giannotti | Mining sequences with temporal annotations[END_REF] propose to combine a candidate sequence generation step with a clustering step, but do not provide details nor evaluations of their method. In both methods, the main issue of intertwining a pattern growing method with temporal interval generation based on the analysis of interval distributions is not explicitly addressed.

Conclusions

In this paper we introduce a temporal extension of the classical sequential pattern mining which adds quantitative temporal information to patterns. Using a hyper-cube representation of temporal sequences, the temporal extents of pattern events can be globally extracted. We propose an algorithm that solves the issue of intertwining the interval distribution extraction and symbolic signature construction.

Our algorithm is based on the APriori algorithm and an approximation of the interval distribution. On the one hand, a variant of the APriori algorithm enables the extraction of the longest patterns in large temporal sequence database. On the other hand, the use of Gaussian mixture models for approximating the interval distributions enables the extraction of the representative quantitative temporal extents of a pattern.

As APriori our method is exponential with the size of the patterns but it remains linear with the number of sequences in the database. The practical efficiency of the method has been evaluated on synthetic data sets. The results show that while the pattern growth technique makes our algorithm robust against the structural noise, the use of Gaussian mixture models makes it robust against temporal noise.

Definition 3 .

 3 (Symbolic signature) The symbolic signature of a temporal sequence S = {(s i , [l i , u i ])} i∈Nn is the ordered sequence of the symbolic events : S = {s i | l i < l i+1 } i∈Pn , where P n is a permutation of N n . Example 1. (Temporal sequence) Let s = {(A, [1.1, 2.9]) , (B, [4, 7.8]) , (C, [2, 5.3])} be a temporal sequence. s can be graphically represented as in Figure 1. The example indicates that event A occurs at the time unit 1.1 and spans 1.8 time units. Then, B occurs at time unit 4 and spans 3.8 time units. In parallel, event C occurs at the time unit 2 and spans 3.3 time units. C overlaps A and B.The symbolic signature of the s is s = {A, C, B}.

Figure 1 . Representation of the temporal se- quence s from example 1 .

 11 Figure 1. Representation of the temporal sequence s from example 1.

Definition 5 .

 5 (Hyper-cube representation of a temporal sequences) Given a temporal sequence S of dimension n, the temporal bounds of S define a unique hyper-cube in R n . The temporal bounds of the sequence items are determined by the orthogonal projection along each corresponding timeline (axis of R n ).If some symbolic event has several occurrences in a temporal sequence, all the related dimensions are distinguished.Example 2. (Hyper-cube representation of a temporal sequence) Given the temporal sequence of example 1, Figure2shows the hyper-cube representation of s. The dimension of s is 3, then the representation belongs to R 3 . The first, second and third dimensions are the timelines that determine the bounds of A, B and C respectively.

Figure 2 .

 2 Figure 2. Hyper-cube representation of the temporal sequence (dimension 3).

Definition 10 .

 10 (Temporal pattern extraction) Let D = {s i } i∈Nm be a set of m temporal sequences, and f min ∈ [0, 1] be the frequency threshold. Then, temporal pattern extraction consists in finding out the longest (i.e. with the highest dimension) temporal patterns {P i } i∈Np such that for each P i the examples strictly-covered by P i are frequent: |{s ∈ D | s ≺ P i }| m ≥ f min . Example 4. (Temporal pattern extraction) Given the database D that contains the following temporal sequences:

Figure 4 .

 4 Figure 4. Distribution of temporal sequences (A, B) represented by hyper-cubes.

Figure 5 .

 5 Figure 5. On the left, temporal sequences instances and Gaussians iso-density ellipsis. On the right, the density estimation.

Algorithm 2 :

 2 selection(f min , D, p, f , d) Input: fmin: the minimal support, D: temporal sequences database, p: symbolic signature, f : frequency of p, d: random points density Output: M : set of frequent temporal patterns // Generation of representative points for interval distribution for s ∈ D do if p covers s then // nb: number of points to generate nb = vol (s p ) * d dim(p) ; add nb random points inside s p to hh; end end // Extraction of frequent temporal patterns from hh GaussianM ixtureM odel = EM(hh); for gm ∈ GaussianM ixtureM odel do if f * gm.prop ≥ fmin then pnew = temporal pattern(p, gm); M = M ∪ {pnew}; end end return M ;

Algorithm 3 :

 3 generateCandidates(M n ) Input: Mn: set of frequent temporal patterns of dimension n Output: Ln+1: set of candidate temporal patterns of dimension n + 1 // Generation of candidates for s ∈ Mn do for i ∈ L1 do P = {s, (i, [-∞, +∞])}; Ln+1 = Ln+1 + P ; end end // Suppression of a priori infrequent candidates for s ∈ Ln+1 do if s is a priori infrequent then Ln+1 = Ln+1s; end end return Ln+1;

Figure 6 .

 6 Figure 6. Prototype (upper graph) and 10 generated examples.

Figure 7 .

 7 Figure 7. Computation time (on the left) and accuracy (on the right) w.r.t. the prototype size.

Figure 8 .

 8 Figure 8. Computation time (on the left) and accuracy (on the right) w.r.t. the examples number. Boxplots show the variances.

Figure 9 .

 9 Figure 9. Accuracy w.r.t. temporal noise. The dashed line gives the accuracy mean computed with non-zero accuracies.

Figure 10 .

 10 Figure 10. Two cases of inadequate interval extraction. Plain line rectangles show the temporal bounds extracted from the computed Gaussians (ellipsis). Dashed line rectangles show the expected temporal bounds.

Figure 11 .

 11 Figure 11. Accuracy with boxplots w.r.t. structural noise. The dashed line gives the mean of non-zero accuracies.

  , Giannotti et al. propose an extension of the sequence mining paradigm to linear temporally-annotated sequences, where each transition A → B in a sequence is annotated with a typical transition time t, denoted by A t -→ B. The notion of Delta-Pattern, proposed by Yoshida et al. [17] is quite similar to temporally annotated sequential patterns. Delta-Patterns have the form A [0,3]

  N n → N m injective, ∀i ∈ N n , p i = s f (i)

	Definition 8. (Temporal pattern coverage) A temporal pat-tern P = {(p i , [l p i , u p i ])} i∈Nn covers an example S = {(s i , [l s i , u s P, if the symbolic sig-i ])} i∈Nm , denoted S nature of S contains the whole symbolic signature of P,
	i.e.:
	∃f : If S	P, then S	P denotes the longest temporal sub-
	sequence of S such that S	P	P. Finally, the coverage of
	S by P is defined by:
			cov P (S) = sim P, S	P .
	Example 3. If P = (A, [1, 3]), (B, [4, 5]), and S =
	{(A, [1.1, 3.4]) , (D, [1.5, 5]) , (B, [4.1, 5.3])}, then S	P
	and S	P = {(A, [1.1, 3.4]) , (B, [4.1, 5.3])}. The coverage
	is computed by:
			(3 -1.1) * (5 -4.1) max(2 * 1, 2.3 * 1.2)	≈ 0.62
	The temporal pattern coverage is null in two cases: (1)
	if P does not cover S, or (2) if at least one pair of corre-
	sponding temporal items do not overlap, i.e. ∃i, [l


Omar Gaci
email: omar.gaci@univ-lehavre.fr

Stefan Balev
email: stefan.balev@univ-lehavre.fr

Characterization of amino acid interaction networks in proteins

Keywords: protein structure, interaction network, scale-free network

A protein interaction network is a graph whose vertices are the protein's amino acids and whose edges are the interactions between them. Using a graph theory approach, we study the properties of these networks. In particular, we are interested in the degree distribution and mean degree of the vertices. The results presented in this paper constitute the first steps of a new network approach to the protein folding problem.

Proteins have complex, irregular structures [START_REF] Branden | Introduction to protein structure[END_REF]. In their natural environment, they adopt a native compact three-dimensional form. This process is called folding and is not fully understood. The process is a resuslt of interactions between the protein's amino acids which form chemical bonds.

We use the following network model to describe a protein. We define a graph in which each vertex represents an amino acid participating in secondary structure element (SSE). We ignore the rest of the amino acids because the most important structure determining interactions are those between amino acids belonging to the same SSE on local level and between different SSEs on global level. Two vertices are connected by an edge if the corresponding amino acids are in contact. We consider that two amino acids are in contact if the distance between their C α atoms is less than 7 Å. We call this graph SSE interaction network (SSE-IN).

In this paper we study some of the properties of SSE-INs. The main advantage of this model is that it allows to cope with different biological problems related to protein structure using graph theory tools. Ignoring details, such as the type and the exact position of each amino acid, this abstract and compact description allows to focus on the interactions' structure and organization. The characterization we propose constitutes a first step of a new approach to the protein folding problem. The properties identified here, but also other properties we plan to study, can give us an insight on the folding process. They can be used to guide a folding simulation in the topological pathway from unfolded to folded state.

We computed the cumulative degree distribution (P k ) of SSE-IN of all proteins in PDB [START_REF] Berman | The protein data bank[END_REF]. A sample of these results is presented on Fig. 1. For all studied networks we observe a power law regime followed by a sharp cutoff, P k ∼ k -(α-1) e -k/α . A major part of the vertices have relatively homogeneous degrees close to the mean degree. It is interesting to note that the cutoff occurs near the mean degree. In this way, there is only a small fraction of hubs with degree greater than the mean. These properties characterize SSE-IN as truncated scale-free networks [START_REF] Amaral | Classes of small-world networks[END_REF].

Since the mean degree plays the role of a threshold beyond which the cumulative degree distribution decreases exponentially, it is interesting to study its evolution with the size of the network. Fig. 2a shows that the mean degree increases very slightly with the size of the network. Whatever the size of the network is, we observe that the mean degree is always between 5 and 8. This mean degree interval is a common property characterizing all SSE-IN. In order to explain this property, let us consider the structure of our networks. They are composed of densely connected subgraphs corresponding to SSEs. The number of edges connecting different subgraphs is relatively small, but these edges are the most important, since they correspond to interactions determining the tertiary structure. The mean degrees of SSE subgraphs are shown on Fig. 2b andc. We can see that the mean degree evolution at microscopic level is almost the same as at macroscopic level. Independently of the SSE size and type, the mean degree of each SSE subgraph, z SSE is always bounded: z min < z SSE < z max when the size of the network is more than 10. In the general case z min = 5 and z max = 8, but when we consider a specific SSE size and type, finer bounds can be found.

Using the bounds on z SSE , it is not difficult to give more precise bounds on the mean degree z of a SSE-IN by showing that z min /(1 -r) < z < z max /(1 -r), where r is the ratio of inter-SSE edges. Proteins with bigger size have more SSEs and hence more links between different SSEs. This explains the increase of the mean degree with the size of the networks. The ratio of inter-SSE edges is quite variable, but it never exceeds 20%.

Figure 1 .

 1 Figure 1. Cumulative degree distributions. Left: 1ES9 (size 50, mean degree 6.6). Right: 1AON (size 4988, mean degree 7.5).

Figure 2 .

 2 Figure 2. Network size distribution and mean degree as a function of the size: (a) SSE-IN, (b) α-helix subnetworks, (c) β-heet subnetworks.