Extracting Temporal Patterns from Interval-Based Sequences

1 Introduction

In many application domains data mining methods are used to extract sequential patterns from data (e.g. medicine, agronomy, e-commerce, industry, man-machine interaction). Classical sequential data mining aims mainly at extracting patterns where the temporal dimension lies on a simple ordering of items (occurrences in time of items in patterns). However, such an ordering is often insufficient: a quantitative characterization of event durations or delays between event occurrences is needed to refine extracted patterns and produce knowledge enabling the distinction between specific behaviors. For example, transactions separated by a day, a month or a year are not similarly correlated.

Our goal is to propose a method for mining temporal sequences made of events, stamped with date and duration, and for extracting frequent sequential patterns with temporal intervals characterizing event duration and relative event position in time. In this paper, we present an efficient algorithm, QTIPrefixSpan, intertwining sequential pattern extraction and temporal interval characterization by clustering. We compare its computation time with existing algorithms. We also compare the efficiency and quality of several distance measures from symbolic data analysis for extracting the representative temporal features of a sequence.

2 Related work

Many efficient methods have been proposed for extracting interesting sequences from large sequential databases. Most of them deal with instantaneous events represented as points on the time axis and linked by symbolic temporal relations based on simple precedence [Srikant and Agrawal, 1996; Pei et al., 2001; Zaki, 2001]. Sometimes, global constraints, on temporal extents or gaps, can be specified to prune the pattern search space [Lee and De Raedt, 2004; Pei et al., 2007; Masseglia et al., 2009].

To cope with events having a non null duration, one must enrich the representation of patterns with temporal relations, either symbolic or numeric, on intervals. Symbolic temporal relations, such as Allen's temporal relations [Allen, 1983], have been widely used to extend "classical" algorithms. Kam and Fu [Kam and Fu, 2000] or H¨oppner [H¨oppner, 2002] extends GSP [Srikant and Agrawal, 1996] to take into account symbolic temporal relations. The main difference lies in the candidate pattern generation phase which handles some Allen's temporal relations among interval-based events. Wu and Chen [Wu and Chen, 2007] pointed out that the major drawback of these algorithms is the ambiguity of the representation of pattern temporal relations and proposed algorithm TPrefixSpan to fix it.

Concerning quantitative temporal pattern extraction, several methods have been proposed for processing point-based time stamped event sequences. Most of these methods extract temporal patterns whose constraints correspond to the envelope, the smallest temporal interval, covering all their instantaneous occurrences. In [Dousson and Duong, 1999], Dousson and Duong have proposed to extract temporal patterns called chronicles - graph patterns constrained by quantitative temporal constraints on the delay between point-based events - from time stamped events. The methods in [Giannotti et al., 2006] and [Yoshida et al., 2000] extract delta-patterns, i.e. rules having the form a [tl,tu] ----→ b meaning that the delay between a and b lies between tl and tu. Characterizing sets of instants with intervals enables the anti-monotonicity property over the pattern lattice. So, this property can be used to prune candidate patterns as early as possible.

However, these methods cannot extract quantitative temporal patterns from interval-based time stamped event sequences. QTempIntMiner [Guyet and Quiniou, 2008] and QTPSpan [Nakagaito et al., 2009] solve this problem by considering the quantitative duration of events during temporal pattern mining. QTempIntMiner represents temporal interval sequences by hyper-cubes and extends GSP with a temporal sequence clustering algorithm for extracting typical temporal intervals. But QTempIntMiner uses the EM algorithm for clustering which makes it inefficient. QTPSpan is based on QFIMiner [Washio et al., 2007]. This algorithm mines sets of items with attached interval-based quantitative attributes. Extracted patterns are itemsets with associated quantitative constraints elaborated by clustering the quantitative attribute values linked to the itemsets that support the pattern.

3 Notations

In this section we detail the formal notations and definitions used in the paper for representing the temporal pattern extraction problem introduced above.

3.1 Temporal sequence

Definition 1 (Temporal sequence). A temporal sequence S is an ordered set of events, where an event A = (A, [l, u]) is composed of a symbol A and a non empty interval [l, u], where l, u ∈ R, l < u are dates.

The size of a sequence S is the number of events in S: |S| = n. ⊕ denotes the concatenation operation on temporal sequences.

li (resp. ui) is the beginning (resp. end) occurrence date of the interval-based event in the temporal sequence. Events in a sequence are ordered by beginning dates and then by lexicographic order. In contrast to a representation using delay between events, the definition of the values li et ui requires a reference instant for each temporal sequence.

Definition 2 (Symbolic signature). The symbolic signature of a temporal sequence S = {(si, [li, ui])}i∈Nn , noted S, is the sequence of its symbols: S = {si}i∈Nn . The order of symbols in the symbolic sequence is the same as in the temporal sequence.

Definition 3 (Multi-dimensional interval). A multidimensional interval of dimension n is a tuple of n intervals I = ([li, ui])i∈Nn .

Definition 4 (Projection over a symbolic signature, π). The projection of a temporal sequence S = {(sj, [lj, uj])}j∈Nn over a symbolic pattern signature M = {mi}i∈Nk of size k is a multi-dimensional interval of dimension k.

If M is not a subsequence of S then πM(S) = ∅.

π(S) denotes the projection of the whole sequence over its proper signature: πS(S) = ([li, ui])i∈Nn .

Example 1. Let E be the sequence {(A, [1, 2]) , (C, [1.5, 4]) , (B, [3, 4]) , (C, [5, 6])} depicted in Figure 1. Then E = {A,C,B,C}, π{A,B}(E) = ([1, 2], [3, 4]) and π(E) = ([1, 2], [1.5, 4], [3, 4], [5, 6]).

Definition 5 (Temporal sequence dissimilarity). Let S 1 and S 2 be two temporal sequences. d(S 1 , S 2 ), the dissimilarity between S 1 and S 2 , is defined by:

where δ is a distance measure on multi-dimensional intervals (cf. Section 4.3).

3.2 Frequent temporal pattern extraction

Definition 6 (Temporal pattern). A temporal pattern is a representative temporal sequence of a set of temporal sequences (instances of the pattern).

As [Giannotti et al., 2006], our pattern definition relies on the notion of sub-sequence representativity. A temporal pattern statistically represents a set of temporal sequences, but the notion of representativity is not given explicitly. This should be distinguished from patterns such as chronicles or delta-patterns whose temporal information is built from the temporal enveloppe of covered events in the sequence.

Exact matching of temporal intervals is too constraining to extract interesting patterns from a sequence. ϵ-covering relaxes the matching operation between intervals.

Definition 7 (Temporal pattern ϵ-covering). A temporal pattern P = {(pi, [lp i , upi ])}i∈Nn ϵ-covers a sequence S = {(si, [ls i , usi ])}i∈Nm , noted S ≺ϵ P, if and only if there exists a projection of S over P such that its dissimilarity with P is less than ϵ:

Example 2. Let consider the three patterns p1 = {(C, [1, 2]) , (A, [2, 4])}, p2 = {(A, [1, 2]) , (C, [2, 4])} and p3 = {(A, [1, 2]) , (C, [4, 5])}). Let ϵ = 1 and δ be the interval distance CityBlock (sum of absolute difference values between corresponding interval bounds, cf. Section 4.3). p1 does not ϵ-cover E (cf. Example 1) because E does not contain the sub-sequence {C,A}. p2 ϵ-covers E because δ ( ([1, 2], [2, 4]), ([1, 2], [1.5, 4]) ) = 0.5 < ϵ. p3 does not ϵcover E becauses the dissimilarity of each occurrence of p3 in E is greater than ϵ: δ ( ([1, 2], [4, 5]), ([1, 2], [1.5, 4]) ) = 3.5 and δ ( ([1, 2], [4, 5]), ([1, 2], [5, 6]) ) = 2.

Definition 8 (Frequent temporal pattern extraction). Given a frequency threshold fmin ∈ [0, 1], a maximal dissimilarity ϵ ∈ R+ and a database of temporal sequences D, the frequent temporal pattern extraction consists in building temporal patterns (Pi) such that the frequency of sequences that ϵ-cover a temporal pattern Pi is greater than fmin.

A temporal pattern is representative of a set of ϵ-covered temporal sequences. ϵ represents the acceptable temporal distance between a sequence and its representative. This is an additional parameter compared to the classical setting of sequential pattern mining.

4 Algorithm presentation

In this section we will detail algorithm QTIPrefixSpan for extracting interval-based sequential patterns. First of all, we introduce a data structure used by this algorithm.

4.1 Data structure

In frequent itemset or sequence mining, the computation of the support or frequency is very time consuming. To avoid systematic scans of the sequence database [Srikant and Agrawal, 1996] have proposed to use a data structure that associates a pattern to the set of its supporting sequences. We have adapted this data structure for counting the sequences which support a temporal pattern m.

For every m, L(m) = {stidi} gathers the set of its representative instances. Each element of L(m) is a 3-tuple stid = 〈tid, pos, is〉 where tid is the identifier of a temporal sequence of D, is is a representative instance of pattern m, i.e. a sub-sequence of the sequence tid ϵ-covered by m (is ≺ϵ m), and pos is the position of the last symbol of is in sequence tid.

L(m) represents the sequence database projected on m in the sense of PrefixSpan, i.e. the set of suffixes (located by pos) of every sequence tid having an instance of m as prefix.

Example 3. Let ϵ = 4 and tid = 1 be the identifier of E in D). The temporal pattern p3 (cf. Example 2) ϵ-covers two sub-sequences of E (cf. Example 1):

4.2 Algorithm

QTIPrefixSpan (see Algorithm 1) is a recursive depthfirst algorithm based on PrefixSpan [Pei et al., 2001]. It explores the extensions of a temporal pattern p, given as input. It makes successive projections of the sequence database to reduce the complexity of computing the support and of clustering the extended temporal patterns.

In the first step (lines 3-5), the algorithm extends the prefix p with one symbol e from S1 (S1 is built in a preliminary step). Next, the algorithm performs the projection of the sequence database on the pattern np = p ⊕ e (lines 6-10). As the list L(np) represents the projected database (cf. Section 4.1), this step just builds the stid list associated to np. At this stage, the temporal dimension of e is ignored.

In the second step (lines 11-18), the function TemporalPatternConstruction is called to build a list of temporal patterns {Mr} having the same signature as np and whose temporal features are computed by classifying multi-dimensional intervals (cf. Section 4.3). In addition,

Algorithm 1: QTIPrefixSpan

input : D: temporal sequence database, fmin: frequency threshold, ϵ: pattern similarity threshold, p : temporal pattern output: FP: set of frequent temporal patterns 1 Construction of S1 // Frequent symbols in D 2 foreach e ∈ S1 do 3 //Extension of temporal pattern p 4 np = p⊕ e 5 L(np) = ∅ 6 //Projection over the sequence database 7 foreach stid ∈ L(p) do 8 s = D(stid.tid) 9 foreach i: i < stid.pos + 1 ∧ si = e do 10 L(np) = L(np) ∪ 〈stid.tid, i, stid.is ⊕ si〉 11 //Construction of temporal constraints and recursion 12 {Mr} = TemporalPatternConstruction(np) 13 foreach q ∈ {Mr} do 14 if q /∈ already explored then 15 already explored = already explored ∪ q 16 if |L(q)| > fmin ∗ |D| then 17 ExtentedP atterns = QTIPrefixSpan( D, fmin, ϵ, q ) 18 FP = FP ∪ ExtentedPatterns

this function updates the data structure for each built pattern. Next, the non-frequent temporal patterns are pruned (line 16). Each frequent pattern q ∈ Mr that has not been already explored is added to the list of explored patterns and QTIPrefixSpan is called recursively to extend q.

4.3 Multi-dimensional interval clustering

The algorithm TemporalPatternConstruction (cf. Algorithm 2) is used in algorithm QTIPrefixSpan (line 12) for building the representative temporal patterns of a set of temporal sub-sequences having the same symbolic signature. The method consists in 1) clustering the set of multi-dimensional intervals resulting from the projection of stid.is contained in L(p), 2) building, for each obtained cluster, a new pattern q having the same symbolic signature as p and the characteristic temporal intervals of the multidimensional intervals in the cluster, 3) building L(q) from L(p).

For the clustering, line 5, we choose to evaluate two methods: KMeans and Affinity Propagation (AP) [Frey and Dueck, 2007] which we have adapted to the clustering of multi-dimensional intervals. For this purpose, we have selected two similarity measures for clustering objects, here n-dimensional intervals: the Haussdorf distance, noted dH, the CityBlock distance, noted dCB. Other distance measures between multi-dimensional intervals are given in [Irpino and Verde, 2008]. Given I = ([lIk , uIk ])k∈Nn and J = ([lJ k , uJk ])k∈Nn , we have:

Algorithm 2: TemporalPatternConstruction

input : p: temporal pattern, L(p): p sub-pattern instances output: {Mr}: set of temporal pattern with symbolic signature p temporally representative of instances in L(p)

1 //Construction of the set of temporal intervals to be clustered 2 Ex = ∅ 3 foreach stid ∈ L(p) do 4 Ex = Ex ∪ π(stid.is) 5 C = clustering(Ex) 6 //Construction of temporal patterns 7 {Mr} = ∅ 8 foreach C ∈ C do 9 q = {(pi , ci)}i 10 L(q) = {stid ∈ L(p), d (stid.is, q) < ϵ} 11 {Mr} = {Mr} ∪ q

In line 10, the list of instances of the temporal pattern q is updated. As with projected databases in PrefixSpan, we avoid an exhaustive scan of the sequence database by searching the instances of the temporal pattern q starting only from its subpatterns instances. As a precondition of the algorithm, we notice that L(p) contains the instances of sub-patterns of p: p(1..|p| - 1). Thus we build L(q) from this stid list.

To find the optimal number of clusters for the interval distribution, we test different values of the parameter k for KMeans or s for AP, and choose the most adequate to the data using the Bayesian Information Criterion (BIC).

5 Experiments

In the following experiments, we evaluate the computing performances of the proposed algorithm and assess the quality of extracted patterns on simulated data. We compare the results with those of QTempIntMiner [Guyet and Quiniou, 2008] and of a GSP-like algorithm, so called QTIAPriori. This last algorithm uses the same principles as QTIPrefixSpan (intertwining sequence mining and interval clustering) but uses an APriori-based breadth-first exploration of the sequence lattice. The algorithms have been implemented in Matlab 1 .

5.1 Simulated data generation

We have implemented a temporal sequence generator for producing datasets that can be tuned with respect to the particular features of patterns to be searched (particularly their numerical temporal features) and of the sequence database (number of sequences, noise level). The principle used to generate a temporal sequence database consists in building sequences from temporal pattern prototypes and, next, in adding random sequences (noise) in the sequence database at a rate rP, 0 ≤ rP ≤ 1.

A temporal pattern prototype is a set of 5-tuples {(Ei, μbi , σbi , μdi , σdi )}i∈Nn where Ei is a symbol, μbi , μdi

1 The experiments were done on a PC with a Xeon processor (only one core was used), with 8Go of RAM. The source code of the algorithms and of the data generator can be downloaded from http://www.irisa.fr/dream/QTempIntMiner

(resp. σbi , σdi ) are the means (resp. standard deviation) of the beginning date and of the duration of Ei. A prototype specifies a temporal pattern ({(Ei, [μbi , μbi + μdi ])}i∈Nn ) to be discovered. The instances of such a pattern are generated from a gaussian distribution of dates (resp. durations) centered on μb (resp. μd) with a standard deviation σb (resp. σd). More the standard deviation is large, more the temporal variations are important and more the extraction of the original pattern will be difficult. To simplify the result presentation, we fix a unique parameter tN ∈ R+ for quantifying all the standard deviation values. This parameter quantifies the temporal noise of a dataset.

5.2 Results

All the curves presented in the sequel were obtained by averaging the results on several (from 5 to 10) different datasets generated from the same parameters. Where not stated otherwise, the following default parameter values were used: |D| = 100, rP = 0.4, tN = 0.2, fmin = 0.1 and ϵ = ∞. We used the Hausdorff distance and looked for the temporal pattern {(A, [2, 3]) , (B, [5, 5.5]) , (C, [8, 10]) , (B, [12, 12.5])} .

Figures 2-(a) and 2-(b) compare the computation time of algorithms QTempIntMiner, QTIAPriori and QTIPrefixSpan with respect to the size of the sequence database, on the one hand, and to the size of searched patterns, on the other hand. In both case, we can see that the computation times are exponential. In addition, QTIAPriori and QTIPrefixSpan are significantly faster than QTempIntMiner.

More precisely (cf. Figure 2-(c)), QTIPrefixSpan runs twice as fast as QTIAPriori, whether it is associated to KMeans or to AP. The KMeans clustering leads to better performances than the AP clustering. QTIAPriori-KMeans is even faster than QTIPrefixSpan-AP for patterns of size greater than 4. Figure 2-(d) illustrates the ability of QTIPrefixSpan-KMeans to cope with complexity. The computation time rises exponentially with respect to the number of sequences but the rate is equal to 1.26, so it is quite close to 1. The mean time for extracting temporal patterns of size 4 from a database of 100000 sequences, corresponding to 600000 symbols, is about 15 min.

The quality of patterns extracted by QTIAPriori and QTIPrefixSpan can be evaluated with respect to several criteria: i) the presence or absence among the extracted patterns of some pattern that ϵ-covers the prototype; ii) the dissimilarity between the temporal intervals in the prototype and in the extracted patterns, i.e. the precision of temporal intervals associated to extracted patterns; iii) the number of extracted patterns having the same symbolic signature as the prototype's, so called "clones" 2 . This last criterion concerns the results readibility: the lower the number of clones, the easier the results analysis will be to the user.

The main factors that impact these criteria are the temporal noise level tN, the dissimilarity threshold ϵ and the minimal frequency threshold fmin. These factors are related: if the data are very noisy then a high ϵ will be needed to insure that noisy instances are classified in the same cluster. But if ϵ is too high (with respect to tN) then the clusters will be larger and pruning using fmin will be less efficient and this will affect the overall algorithm performance.

2 Our method may extract several frequent patterns with the same symbolic signature but with discriminative temporal intervals.

For sufficiently high values of ϵ and low values of fmin the three algorithms can extract the prototype pattern from the sequence dataset. Moreover, when we add a second prototype having the same symbolic signature but different temporal intervals the two patterns are still correctly extracted. In the latter case, GSP or PrefixSpan can extract only one pattern.

Figure 3 illustrates the quality of patterns that are extracted by the algorithms from simulated data that contains only one prototype among random sequences. Figure 3-(a) gives, for QTIPrefixSpan, the number of patterns FP (line 18 of algorithm 1) and the number of prototype clones, with respect to ϵ. When ϵ is small (ϵ < .1), few patterns having the size of the prototype are generated: the expected similarity of pattern instances imposes a too strong constraint with respect to noise. For .1 < ϵ < .8, the number of generated patterns grows very much. Due to the strong similarity that is still required by the value of ϵ, the temporal clustering induces many clusters but with a number of instances that remains below fmin. For .8 < ϵ < 1.7, several frequent patterns are extracted. For 1.7 < ϵ, the number of extracted frequent patterns stabilizes to 1: ϵ is sufficiently large for considering that the dissimilarity between temporal intervals is quite reasonable.

We can see on Figure 3-(b) that even with noise, the best temporal pattern extracted by the three algorithms is close to the searched prototype. A Hausdorff distance equal to 1 is very low for a temporal pattern where temporal intervals may last 12 time units. For QTIAPriori and QTIPrefixSpan, when the temporal noise moves up, the precision logically moves down. We can see also, that the choice of the clustering method has more impact on the quality of results than the choice of the search method (GSP or PrefixSpan). KMeans can cope with harder temporal noise than AP: the mean dissimilarity obtained with KMeans is less than that obtained with AP. To finish, QTempIntMiner is as precise, even more precise, than the two other algorithms for big patterns: the quality induced by the clustering based on EM is better than that of KMeans or AP.

6 Conclusion

We have presented the problem of quantitative temporal pattern extraction from temporal interval sequences where events are qualified by a type and a numerical date and duration, i.e. associated with numerical temporal intervals. Such patterns are particularly expressive: they can discriminate input sequences not only on the succession of events but also on their relative position in time and on their respective duration. We have proposed the algorithm QTIPrefixSpan for extracting temporal patterns that contains quantitative temporal information from temporal interval sequences. The comparison with QTempIntMiner shows that our algorithm is more efficient in runtime and can extract more precise temporal patterns on simulated datasets.

The improvements brought to interval-based sequence mining enable an efficient computation of large datasets. Applications, such as the characterization of cardiac diseases from electrocardiograms or faults in monitored industrial plants from time series, are investigated now to illustrate the practical interest of mining such temporal patterns. The clustering step is the major source of complexity of the proposed

(a)

algorithms. We are investigating different ways to improve its efficiency such as defining heuristics to choose the number of clusters a priori or introducing incrementality into clustering methods.