Efficiently Summarising Event Sequences with Rich Interleaving Patterns
Apratim Bhattacharyya Jilles Vreeken










    Apratim BhattacharyyaMax-Planck Institute for Informatics and Saarland University, Saarland Informatics Campus, Saarbrücken, Germany.  
Jilles Vreeken[1]
    
=============================================================================================================================================================





Discovering the key structure of a database is one of the main goals of data mining. In pattern set mining we do so by discovering a small set of patterns that together describe the data well. The richer the class of patterns we consider, and the more powerful our description language, the better we will be able to summarise the data. In this paper we propose , a novel greedy MDL-based method for summarising sequential data using rich patterns that are allowed to interleave. Experiments show is orders of magnitude faster than the state of the art, results in better models, as well as discovers meaningful semantics in the form patterns that identify multiple choices of values.




§ INTRODUCTION


Discovering the key patterns from a database is one of the main goals of data mining. Modern approaches do not to ask for all patterns that satisfy a local interestingness constraint, such as frequency <cit.>, but instead ask for that set of patterns that is optimal for the data at hand. 
There are different ways to define this optimum. The Minimum Description Length (MDL) principle <cit.> has proven to be particularly successful <cit.>. 
Loosely speaking, by MDL we say that the best set of patterns is the set that compresses the data best. How well we can compress, or better, describe the data depends on the description language we use. The richer this language, the more relevant structure we can identify. At the same time, a richer language means a larger search space, and hence requires more efficient search.

In this paper we consider databases of event sequences, and are after that set of sequential patterns that together describe the data best—as we did previously with  <cit.>. Like we describe a database with occurrences of patterns. Whereas requires these occurrences to be disjoint, however, we allow patterns to interleave. This leads to more succinct descriptions as well as better pattern recall. Moreover, we use a richer class of patterns. That is, we do not only allow for gaps in occurrences, but also allow patterns to emit one out of multiple events at a certain location. For example, the pattern `paper [proposes | presents] new' discovered in the JMLR abstract database matches two common forms of expressing that a paper presents or proposes something new. 

With this richer language, we can obtain much better compression rates with much fewer patterns. To discover good models we propose , a highly efficient and versatile search algorithm. Its efficiency stems from re-use of information, partitioning the data, and in particular from considering only the currently relevant occurrences of patterns in the data. It is a natural any-time algorithm, and can be ran for any time budget that is opportune.




Extensive experimental evaluation shows that performs very well in practice. It is much better at retrieving interleaving patterns than the very recent proposal by Fowkes and Sutton <cit.>, and obtains much better compression rates than  <cit.>, while being orders of magnitude faster than both. 
The choice-patterns it discovers give insight in the data beyond the state of the art, identifying semantically coherent patterns.
Moreover, is highly extendable, allowing for richer pattern classes to be considered in the future.




§ PRELIMINARIES


Here we introduce basic notation, and give short introductions to the MDL principle. 



 §.§ Notation

We consider databases of event sequences. Such a database D is composed of |D| sequences. A sequence S ∈ D consists of |S| events drawn from an alphabet Ω. 

The total number of events occurring in the database, denoted by ||D||, is simply the sum of lengths of all sequences ∑_S ∈ D |S|. We write S[j] to refer to the j^th event in sequence S. The support of an event e ∈Ω in a sequence S is simply the number of occurrences of e in S, i.e. (e | S) = |{j | S[j] = e}|. The support of e in a database D is defined as (e | D) = ∑_i = 1^|D| supp(e | S_i). 

We consider two types of sequential patterns. A serial episode X ∈Ω^|X| is
a sequence of |X| events, and we say that a sequence S contains X if
there is a subsequence in S equal to X. We allow noise, or
gap events, within an occurrence of X.


We also consider choice episodes, or choicisodes. These are serial episodes with positions matching one out of multiple events. For example, serial episode ac matches an a followed by c, whereas choicisode [ a , b ] c matches occurrences of a or b followed by c.



 §.§ Brief introduction to MDL

The Minimum Description Length principle (MDL) <cit.> is a practical version of Kolmogorov Complexity <cit.>. Both embrace the slogan Induction by Compression. We use the MDL principle for model selection.
 
By MDL, the best model is the model that gives the best lossless compression. More specifically, given a set of models ℳ, the best model M ∈ℳ is the one that minimizes L(M) + L(D | M), in which L(M) is the length in bits of the description of M, and L(D | M) is the length of the data when encoded with model M. Simply put, we are interested in that model that best compresses the data without loss.
MDL as describe above is known as two-part MDL, or crude MDL; as opposed to refined MDL. In refined MDL model and data are encoded together <cit.>. We use two-part MDL because we are specifically interested in the model: the patterns that give the best description. 

In MDL we are only concerned with code lengths, not actual code words.

Next, we formalise our problem in terms of MDL.




§ MDL FOR EVENT SEQUENCES





To use MDL we need to define a model class ℳ, and how to encode a model M ∈ℳ and data D in bits.

As models we will consider code tables <cit.>. A code table  is a dictionary between patterns and associated codes. A code table consists of the singleton patterns e ∈Ω, as well as a set 𝒫 of non-singleton patterns. We write _p(X) to denote the pattern code that identifies a pattern X ∈. 
Similarly, we write _f(X) and _g(X) for the codes resp. identifying 

a fill resp. a gap in the occurrence of a pattern X. 

We can encode a sequence database D using the patterns in a code table , which generates a cover C of the database. A cover C uniquely defines a pattern code stream C_p and a meta code stream C_m. The pattern stream is simply the concatenation of the codes corresponding to the patterns in the cover, in the order of their appearance. Likewise, the meta stream C_m is the concatenation of the gap and fill codes corresponding to the cover. In Fig. <ref>, we illustrate two example covers and corresponding code tables, the first using only singletons and the second cover with interleaving using patterns from a richer code table with choicisodes.



Before formalising our score, it is helpful to know how to decode a database given a code table and the code streams. 



 §.§ Decoding a database


To decode a database, we start by reading a _p(X) from the pattern stream . If the corresponding pattern X is a singleton, we append it to our reconstruction of the database D. If it is a non-singleton, we append its first event, X[1], D. To allow for interleaving, we have to add a new context to context list Λ. A context is a tuple (X,i) consisting of a pattern X, and a pointer i to the next event to be read from the pattern. For an example, let us consider Cover 2 in Fig. <ref>. We read _p(p) from _p, append p[1]=a to D, and add (p,2) to the context list.

Next, if the context list is non-empty, we read as many meta codes from C_m as there are contexts in Λ. 
If we read a fill code _f(X) corresponding to one of the contexts (X,i) ∈Λ, we append the next event from X, X[i] to the data D, and increment the pointer. If after this step we have finished reading the pattern, we remove its context from the list. If we only read gap codes _g(X) for every pattern X in the context list, we read again from the pattern stream. We do this until we reach the end of the pattern stream .

Continuing our example, we read _g(p) from C_m, which corresponds to a gap in the occurrence of pattern p. We read _p(q) from C_p, write q[1]=b to D, and insert context (q,2) to Λ. Next, Λ contains two contexts, and we read two meta codes from C_m, viz. _g(p) and _f(q). As for context (q,2) we read a fill code, we write q[2]=d to D, and increment its pointer to 3. Etc.



 §.§ Calculating Encoded Lengths

Given the above scheme we know which codes to expect when, and can now formalise our score. We build upon and extend the encoding on Tatti & Vreeken <cit.> for richer covers and patterns.



  §.§.§ Encoded Length of the Database

We encode the pattern stream  using Shannon optimal prefix codes. The length of the pattern code  L(_p(X)) for a pattern X depends on how often it is used in the pattern stream. We write (X) to denote the number of times _p(X) occurs in . The length of the optimal pattern code for X then is

    L(_p(X))    = - log((X)/∑_Y ∈(Y)) .

The encoded length of the whole pattern stream C_p is then simply L(C_p) = ∑_X ∈(X) L(_p(X)).

To avoid arbitrary choices in the model encoding, we use prequential codes <cit.> to encode the meta stream. Prequential codes are asymptotically optimal without knowing the distribution beforehand. The idea is that we start with an uniform distribution over the events in the stream and update the counts after every received event. This means we have a valid probability distribution at every point in time, and can hence send optimal prefix codes. The total encoded length of the meta stream pattern is

    L() =   ∑_X ∈ CT( -∑_i=1^(X)log(ϵ + i/ 2 ϵ + i ) 
        -∑_i=1^(X)log(ϵ + i/ 2 ϵ  + (X) + i ) )  .
 
where ϵ=0.5 is a constant by which we initialize the distribution <cit.>, (X) and (X) are the number of times _f(X) resp. _g(X) occurs in C_m. 

For lossless decoding of database D, the number of sequences |D| and the length of each sequence S ∈ D should also be encoded. We do this using , the MDL optimal code for integers n ≥ 1 <cit.>. 

Combining the above, for the total encoded length of a database, given a code table  and cover C, we have

    L(D |) = (| D |) + ∑_S ∈ D(| S |)  + L() + L()  .

Next we discuss how to encode a model.



  §.§.§ Encoded Length of the Code Table

Note that the simplest valid code table consists of only the singletons Ω. We refer to this code table as , or, the standard code table. We use  to encode the non-singleton patterns 𝒫 of a code table . 
The usage of a singleton e ∈ is simply its support in D, and hence the code length _p(e) =  - log( (e | D)/||D||).
To use these codes the recipient needs to know the supports of the singletons. We encode these using a data to model code—an index over a canonically ordered enumeration of all possibilities <cit.>; here it is the number of possible supports of | Ω | alphabets over a database length of || D ||, || D |||Ω |. The length of the code is now simply the logarithm over the number of possibilities.

Given the standard code table , we can now encode the patterns in the code table. We first encode the length |X| of the  pattern, and then number of choice spots in the pattern, ||X|| - |X|. We encode how many choices we have per location using a data to model code. We finally encode the events X[i] using the standard code table, . That is, 

    L(X |)    = (|X|) + ( || X || - |X| + 1)
       + log()0pt||X||-1|X| - 1 + ∑_i = 1^|| X || L(X[i] |)   .

Note that if we do not consider choicisodes, we can simplify the above as we only need to transmit the first and last part of this code. That is, the length and the events in the pattern.

Recall that, pattern codes in the pattern stream  are optimal prefix codes. The occurrences of the non-singleton patterns need to be transmitted with the model. We do this again using a data to model code. We encode the sum of pattern usages, (𝒫) = ∑_X ∈∖Ω(X), by the MDL optimal code for integers. It is equivalent to use a pattern code per choicisode and then identify the choice-events, or to use a separate pattern code for each instantiation of the choicisode. For simplicity we make the latter choice. 

The total encoded size of code table  given a cover C of database D is then given by

    L(| D, C) =   (| Ω |) + log||D||  |Ω|
       + (| 𝒫 | + 1) + ((𝒫) + 1) 
       + L((𝒫),| 𝒫 |) + ∑_X ∈ CTL(X,)  .


We are interested in the set of patterns and a corresponding cover C which minimizes the total encoded length of the code table and the database, which is,

    L(,D)    = L(| C) + L(D |)  .

We can now formally define our problem as follows. 


Minimal Code Table Problem Let Ω be a set of events and let D be a sequence database over Ω, find the minimal set of serial (choice) episodes 𝒫 such that for the optimal cover C of D using 𝒫 and Ω, the total encoded cost L( , D) is minimal, where  is the code-optimal code table for C.



For a given database D, we would like to find its optimal pattern set in polynomial time. However, there are exponentially many possible pattern sets, and given a pattern set, there are exponentially many possible covers. 
For neither problem there exists trivial structure such as monotonicity or sub-modularity that would allow for an optimal polynomial time solution. 

Hence, we resort to heuristics. In particular, we split our problem into two parts. We first explain our greedy algorithm to find a good cover given a set of patterns. We describe how to find a set of good patterns in Sec. <ref>.



§ COVERING A DATABASE

Given a pattern set 𝒫 and database D, we are after a cover C with interleaving and nesting, that minimises L(, D). 

Each occurrence of a pattern X in database D, possibly with gaps, defines a window. We denote by S[ a,b ] a window in sequence S that extends from the position a to b. Two windows are non-overlapping if they do not have any events in common which belong to their respective patterns. Two interleaving or nesting windows might have common events, which, as we do not allow overlap, leads to gap events for one of the two windows. Two windows are disjoint if they do not have any events in common. For every event in the database D, there can be many windows with which we can choose to cover it. The optimal cover depends upon the pattern, fill, gap codes of the patterns. The choices grow exponentially with sequence length, with no trivial sub-structure. 

To find good disjoint covers, Tatti & Vreeken <cit.> use an EM-style approach. At each step until convergence, given the pattern, gap and fill codes, the authors use the dynamic programming based algorithm  to find a cover.  takes a set of possibly overlapping minimal windows and returns a subset of disjoint minimal windows (i.e. a cover) which maximizes the sum of  (a heuristic measure) of each window. Then, the lengths of the codes are reset based upon the found cover. It is unclear if this scheme can be extended to return a cover with interleaved or nested windows efficiently. Moreover if we extend our model with a new pattern, we have to rerun  from scratch. 

We propose an efficient and easily extendible heuristic for good covers with interleaved and nested windows. 



 §.§ Window Lengths

For a given pattern, as we consider windows with gaps, the length of an window in the database can be arbitrarily long. Tatti & Vreeken therefore consider only minimal windows. A window w = S[ i, j ] is a minimal window of a pattern X if w contains X but no other proper sub-windows of w contain X. If no interleaving or nesting is allowed, it is optimal to consider only minimal windows. Otherwise, it is easy to construct examples where the optimal cover consists of non-minimal windows.

Consider the sequence abdccdc and a code table with the pattern abc, dc and the singletons a, b, c and d. Two possible covers are: (ab d c) c dc using only minimal windows and (ab(dc)c) dc where a non-minimal window of abc is used and is nested with a window of dc. It is easy to see that the second cover leads to lower encoded length L(abdccdc, { abc, dc, a, b, c, d} ) (see Fig <ref>) of about 2.9 bits.



Ideally, we should consider all possible windows. The number of possible windows of a pattern, however, is quadratic in the length of the database. This means that even a search for all windows is computationally inefficient. Therefore, we first search for only the shortest window from each starting position in the database. We consider longer windows when necessary. We do so as follows.



 §.§ Window Search


Given a pattern X, we use the pseudo-code  presented as Algorithm <ref> to search for its windows in the a sequence or sub-sequence S of database D. It returns us (X) which is a set of candidate windows of the pattern X. It considers only the first window from each starting position in the sequence S. We later choose a subset of these windows (along with those of patterns other than X in ) to create a cover of the database L(D |). To control the ratio of gaps and fills, we maintain a budget variable. This is the number of extra allowed overall gaps. Ideally we would like to have more fills than gaps as it leads to better compression.

To search for windows efficiently in , we use an inverted index: 𝑖𝑛𝑑𝑒𝑥^-1(x) which gives us a list of positions of the event x ∈Ω in the database. We use a priority queue  to store potential windows sorted by length. Shorter windows means more fills than gaps. We initialize  (line 3) by creating potential windows at all the positions where the first alphabet of pattern X occurs in the sequence S_i and pushing these potential windows to . Each window w in  contains the starting position in S_i, its length, and a pointer w_i. This pointer points to a certain event in pattern X which we are search for in S_i. At every step of  (line 7) we look at the potential window at the top of the queue . We check if the next event in the database equals the character of the pattern X pointed to by w_i and increment the length of the window w. There are now two possibilities i) (line 10) The next database event is the same as the event in X pointed to by w_i.  If we have found the full pattern X in the database, we add this window to (X). We can now update our budget if we used more fills than gaps. Using less gaps in one window allows us to use more gaps in another. ii) (line 15) The next database event does not equal the event of X pointed to by w_e. This means that the potential window w has one extra gap. We check if this extra gap is allowed by our budget (line 16). Otherwise, we drop the window.

[t]
sequence S and a pattern X
 set of windows for X
 ←∅ 
 p in 𝑖𝑛𝑑𝑒𝑥^-1(x)
 w ← (𝑠𝑡𝑎𝑟𝑡, 𝑙𝑒𝑛𝑔𝑡ℎ, w_i = 1) 
 𝑝𝑢𝑠ℎ(w,) 
 
 T is not empty
 w ←𝑡𝑜𝑝() 
 (𝑠𝑡𝑎𝑟𝑡, 𝑙𝑒𝑛𝑔𝑡ℎ, w_i) ← w 
 𝑙𝑒𝑛𝑔𝑡ℎ = 𝑙𝑒𝑛𝑔𝑡ℎ + 1 
 S_i[ start + length ] equals X[w_i]
	w_i points to the end of X
	append w to  
	b ← b + 2 ×(X) - 𝑙𝑒𝑛𝑔𝑡ℎ - 1 
	
 

 b + 2 ×(X) - 𝑙𝑒𝑛𝑔𝑡ℎ - 1 < 0
	delete w from  
	
 
 
 (S_i,X,budget)


Now that we can search for windows of patterns, we describe how to choose a subset which generates a good cover C of the database D.



 §.§ Candidate Order
  
In the first step of our greedy strategy, we sort the set of patterns in a fixed order, similar to <cit.>. We call this order the Candidate Order. We cover the database using windows of patterns in this order. This order is designed to minimize the code length. This is achieved by putting longer and more frequently occurring patterns higher up in the candidate order. This means we can cover more events while minimizing the code length.

We consider the patterns X ∈ in the order,


  * Decreasing ↓ in length | X |

  * Decreasing ↓ in support support(X | D)

  * Decreasing ↓ in length of encoding it with the standard table.

  * Increasing ↑ lexicographically.




 §.§ Greedy Cover

We now describe our greedy algorithm  which we use incrementally build a good cover as pseudo-code in Algorithm <ref>. We consider patterns in the candidate order. We maintain a set of selected windows .  takes this set of selected windows  and extends it with a subset of candidate windows of pattern X, (X), found with  and possibly with (longer, interleaved) windows found on the fly. We assume that both  and  are sorted.

We refer to a block of windows which are interleaved or nested with each other as an window extend. For ease of notation, we refer to windows which are not interleaved or nested also as window extends (containing a single window). We begin  by dividing the set  into a set of window extends  by a linear sweep (if  is sorted). For patterns at the top of the candidate order  is empty, so we can select all candidate windows (X). For any other pattern, we iterate though the list of window extends  (line 4). All the windows of the pattern occurring between any two extends in  can be potentially chosen. These are put in  (line 5), a temporary list. It is possible that some windows of X in  overlap. We consider these windows in order of decreasing length (line 6) and discard any window that overlaps with a previously chosen window. We additionally search (on the fly) for interleaved windows occurring within the window extends  (line 9). 

For example consider the sequence abcdacbd which we want to cover with the patterns ac and bd. Using  we get two windows each for the two patterns. If ac is higher up in the candidate order, we first select the two windows of ac; abcdacbd. We now have two window extends in . We search for windows of bd within the first window extend of ac to find one interleaved window: abcdacbd and we select the second window of bd as it is between the  two window extends of ac.


[t]
set of selected windows  and a set of candidate windows (X) for pattern X.
 set of selected windows  combined with those in (X) not overlapping with .
 ←∅ 
 ← create window extends from  and (X) 
 𝑙𝑎𝑠𝑡←∅ 
 window w ∈
 ← all windows of X between 𝑙𝑎𝑠𝑡 and v  
 v in , in order of decreasing length
 v does not overlap with 
 append v to  
 
 
 ←∪{ windows of X inside 𝑤 in D} 
 𝑙𝑎𝑠𝑡←𝑤 
 
 Merge  and  
 (,)
 

Note that,  now takes time O(|| + ||D|| + || log(||)), in the worst case. Where, || is the number of windows in  and || is the number of candidate windows. Let, W_max(𝒫) be the maximum number of candidate windows of any pattern in 𝒫. Then  takes time O( |𝒫|   ( W_max(𝒫)log(W_max(𝒫)) + ||D|| )) to construct a cover C of the database D using the patterns 𝒫 in the code table  in the worst case. The maximum number of candidate windows of any pattern W_max(𝒫) is bounded by the size of the database O(||D||). However,  makes it computationally more efficient to extend the code table with a new pattern X. We can discard windows of patterns in 𝒫 below X in the candidate order from the cover and run  for (X) and the patterns in the code table below X in candidate order. This means that we do not have to recompute the cover from scratch. This is very efficient if the pattern X is near the bottom of the candidate order. As we shall see  is very competitive in its execution time compared to  <cit.>.

Having presented our greedy approach of covering a database given a set of patterns, we now turn our attention to the task of mining good set patterns.



§ MINING GOOD CODE TABLES

Given a pattern set 𝒫 we have a greedy algorithm to cover the database D and obtain the encoded length of the model and data L(,D). To solve the Minimal Code Table Problem we want to find that set 𝒫 of patterns which minimizes the total encoded length L(,D) of the database. As discussed before, there does not seem to be any trivial sub-structure in the problem which we can exploit to obtain an optimal set of patterns 𝒫 in polynomial time. So, we resort to heuristics. We build upon and extend  <cit.>.



 §.§ Generating Candidates

We build a pattern set 𝒫 incrementally. Given a set of patterns 𝒫 and a cover C, we aim to find a pattern X and an extension Y, such that X,Y ∈𝒫∪Ω, whose combination XY would decrease the encoded length L(𝒫∪ XY,D). We do this until we cannot find any XY that when added to 𝒫 reduces the total encode size. Doing is exactly, however, is computationally prohibitive. At every iteration, there would be O((|𝒫| + |Ω|)^2) possible candidates. Thus, we again resort to heuristics. We use the heuristic algorithm  from <cit.> that can find good candidates, with likely decrease in code length if added, in O(| 𝒫 | + | Ω| + ||D||)  time. 
For readability and succinctness, we 
describe algorithm  in
Appendix <ref>.

Candidates are accepted or rejected based on the compression gain. As we can now find richer covers with interleaving and nesting, candidates are potentially more likely to be accepted. However, we want to find a succinct set of patterns which describe the data well. Choicisodes can help in this search for a succinct summary of the data.  



 §.§ Choicisodes

Recall from Sec. <ref> that we can encode patterns as choicisodes. We have the possibility of combining a newly discovered non-singleton pattern with a previously discovered non-singleton pattern or choicisode to create or expand a choicisode. Combining non-singleton patterns into a single choisisode may hence lead to savings in the encoded length of the code table L(| C) while providing a more succinct representation of the pattern set.

We use a greedy strategy based on MDL for discovering choicisodes. For each newly discovered non-singleton pattern, we consider all previously discovered non-singleton patterns or choicisodes which differ with it at one position. Then, we calculate the increase in code length (of the model) if we encode it as a choicisode with each of these non-singleton patterns or choicisodes. We also consider the increase in code length if we encode it as independently. We choose whichever option with leads to the minimum increase in code length.

Next we present our algorithm  for mining a succinct and representative pattern set.



 §.§ The SQUISH algorithm

The present the complete algorithm  as pseudo-code in Algorithm <ref>. At each iteration, it considers each pattern X ∈. It creates potential extensions XY, with Y ∈, based on estimated change in the encoded length using  (line 6).  then considers each of these patterns in the order of the estimated decrease in gain if added to  (line 7).  is used to find the candidate windows of each of these extensions (line 9).  is used to cover the data with this candidate pattern XY added to . We simultaneously consider the possibility of encoding XY as a choicisode. If XY leads to a decrease in the encoded length of the database D then, we add XY to . If XY is to be added, we  
(see Appendix <ref>) the code table to remove redundant patterns. Consider, for example if we decide to add abcd, the pattern ab and cd may not be required to construct an effective cover of the database. We also consider the singletons occurring in the gaps of XY, by constructing new extended patterns by using these gap alphabets as intermediate alphabets.

[t]
database D
 pattern set 𝒫 with low L(,D)
 𝒫←ϕ 
 C ←(𝒫,D) 
 changes
 ℱ←ϕ 
 X ∈ add (X, A, D) to ℱ  
  Z ∈ℱ ordered by estimated gain
    Sort 𝒫∪ Z in candidate order 
    (Z) ←(D, Z, 𝑏𝑢𝑑𝑔𝑒𝑡) 
    C ←(𝒫∪ Z,D) 
 	 L(D, 𝒫∪ Z) < L(D, 𝒫)   
 	𝒫←(𝒫∪ Z, D) 
 	
 
 (D)
  



§ RELATED WORK

Discovering sequential patterns is an active research topic. Traditionally there was a focus on mining frequent sequential patterns, with different definitions of how to count occurrences <cit.>. Mining general patterns, patterns where the order of events are specified by a DAG is surprisingly hard. Even testing whether a sequence contains a pattern is NP-complete <cit.>. Consequently, research has focused on mining subclasses of episodes, such as, episodes with unique labels <cit.>, strict episodes <cit.>, and injective episodes <cit.>.

Traditional pattern mining typically results in overly many and highly redundant results. Once approach to counter this is mining statistically significant patterns. Computing the expected frequency of a sequential pattern under a null hypothesis is very complex, however <cit.>. 

builds upon and extends  <cit.>. Both draw inspiration from the  <cit.> and  <cit.> algorithms. pioneered the use of MDL for mining good patterns from transaction databases. Encoding sequential data with serial episodes is much more complicated, and hence uses a much more elaborate encoding scheme. Here, we extend it to discover richer structure in the data. 
The algorithm <cit.> mines code table directly from data. iteratively seeks to improve the current model by considering as candidates joins XY of patterns X,Y ∈. Whereas considers the full Cartesian product and ranks on the basis of estimated gain, and take a batch based approach.

Lam et al. introduced <cit.> for mining sets of serial episodes. As opposed to the MDL principle, they use fixed length codes, and do not punish gaps within patterns. This means, their goal is essentially to cover the sequence with as few patterns as possible, which is different from our goal of finding patterns that succinctly summarize the data. 

Recently, Fowkes and Sutton proposed the  algorithm <cit.>. is based on a generative probabilistic model of the sequence database, and uses EM to search for that set of patterns that is most likely to generate the database. does not explicitly consider model complexity. Like , can handle interleaving and nesting of sequences. We will empirically compare to in the experiments.







§ EXPERIMENTS

Next we empirically evaluate on synthetic and real world data. We compare against  <cit.> and  <cit.>. 
All algorithms were implemented in C++. We provide the code for research purposes.[] 

We evaluate quantitatively on the basis of achieved compression, pattern recall, and execution times. Specifically, we consider the compression gain Δ L = L(D,) - L(D,). That is, the gain in compression using discovered patterns versus using the singleton-only code table. Higher scores are better. 
All experiments were executed single threaded on quad-core Intel Xeon machines with 32GB of memory, running Linux.



 §.§ Databases

We consider four synthetic, and five real databases. We give their base statistics in Table <ref>. 



Indep, Plant-10, and Plant-50 are synthetic data consisting of a single sequence of 10 000 events, over an alphabet of 1000 events. For Indep, all events are independent. For Plant-10, and Plant-50 we plant resp. 10 and 50 patterns of 5 events long 10 times each over an otherwise independent sequence, with a 10% probability of having a gap between consecutive events. To evaluate the ability of to discover interleaved and nested patterns, we consider the Parallel database <cit.>. Each event in this database is generated by five independent parallel processes chosen at random. Each process i generates the events { a_i, b_i, c_i, d_i, e_i} in sequence. 







We further consider five real data sets. Gazelle is click-stream data from an e-commerce website <cit.>. The Sign database is a list of American sign language utterances <cit.>. To allow for interpretability we also consider text data. Here the events are the (stemmed) words in the text, with stop words removed. Addresses contains speeches of American presidents. JMLR contains abstracts from the Journal of Machine Learning research, and Moby is the famous novel Moby Dick by Herman Melville. 







  §.§.§ Synthethic Data

As a sanity check we first compare to considering only serial episodes and not allowing interleaving or nesting. We find that in this setting performs on par with in terms of recovering non-interleaving patterns from synthetic data; like it correctly discovers no patterns from Indep, it recovers all patterns from Plant-10, and recovers 45 patterns exactly from Plant-50 and fragments of the remaining 5, but does so approximately ten times faster than . 



To investigate how well retrieves interleaving patterns, we consider the Parallel dataset, and compare to . (We also considered but found it did not finish within a day.) To make the comparison fair, we restrict ourselves again to serial episodes, but now do allow for interleaving and nesting. We measure success in terms of pattern recall. That is, given a set of patterns 𝒫 and a set of target patterns 𝒯, we consider the set 𝒯 as the data and cover it with 𝒫 (not allowing for gaps). The pattern recall is the ratio of the total number covered events in 𝒯  to the maximum of the total number of events in 𝒯 or 𝒫. 

We give the results in Fig. <ref>. We find that obtains much higher recall scores than . Inspecting the results, we see that discovers large fragments of each pattern, whereas retrieves only eight small patterns, most of length 2, and hence does not reconstruct the generating set of patterns well. 




  §.§.§ Real data


Next we evaluate on real data. We compare to in terms of number of patterns, achieved compression, and runtime. 

We consider three different configurations, 1) disjoint covers of only serial episodes, 2) allowing interleaving and nesting of serial episodes, and 3) allowing interleaving and nesting of serial episodes and choicisodes.
We give the results in Table <ref>.

First of all, the -t columns show that in all setups needs only a fraction of the time—up to three orders of magnitude less—to discover a model that is at least good as what returns. To fully converge, and take roughly the same amount of time for the disjoint setting, as well as when we do allow interleaving. 
However, when converged discovers models with much better compression rates, i.e. with much higher Δ L, than does.  is also significantly faster than , taking only 87 minutes instead of 259 on the JMLR database, and on Gazelle requires only 96 instead of 680 minutes.

performs best when we consider our richest description language, allowing both interleaving and choicisodes, discovering much more succinct models that obtain much better scores than if we restrict ourselves. For example, for Gazelle, with choicisodes enabled needs only 605 instead of 901 patterns to achieve a Δ L of 165.7k instead of 161.6k. Overall, we observe that many choicisodes form semantically coherent groups. We present a number of exemplar choisisode patterns in Table <ref>. Interesting examples include: data-set and training-set from JMLR, god-bless and god-help from Address, cape-horn and cape-cod from Moby. 

Last, but not least, we report on the convergence of L(,D), the encoded length of the database, over time for both and in Fig. <ref>. Both algorithms estimate batches of candidates, and test them one by one tests. We see that the initial candidates are highly effective on increasing compression gain. Candidates generated in the latter iterations lead to only little increase in compression gain. This leads to the possibility of executing  based upon a time budget, as an any-time algorithm. 




§ CONCLUSION

We considered summarising event sequences. Specifically, we aimed at discovering sets of patterns that capture rich structure in the data. We considered interleaved, nested, and partial pattern occurrences. We proposed the algorithm  to efficiently search for pattern occurrences and the greedy algorithm   for efficiently covering the data. Experiments show that works well in practice, outperforming the state of the art by a wide margin in terms of scores and speed, while discovering pattern sets that are both more succinct and easier to interpret.

As future work we are considering parallel episodes, patterns where certain events are un-ordered e.g. a { b,c } d <cit.>. 

Discovering such structure presents a significant computational challenges and requires novel scores and algorithms.




§ ACKNOWLEDGEMENTS

Apratim Bhattacharyya and Jilles Vreeken are supported by the Cluster of Excellence “Multimodal Computing and Interaction” within the Excellence Initiative of the German Federal Government.


10

achar2012discovering
A. Achar, S. Laxman, R. Viswanathan, and P. Sastry.
Discovering injective episodes with general partial orders.
Data Min. Knowl. Disc., 25(1):67–108, 2012.

agrawal:94:fast
R. Agrawal and R. Srikant.
Fast algorithms for mining association rules.
In VLDB, pages 487–499, 1994.

bertens:16:ditto
R. Bertens, J. Vreeken, and A. Siebes.
Keeping it short and simple: Summarising complex event sequences with
  multivariate patterns.
In KDD, pages 735–744, 2016.

fowkes:16:ism
J. Fowkes and C. Sutton.
A subsequence interleaving model for sequential pattern mining.
In KDD, 2016.

grunwald:07:book
P. Grünwald.
The Minimum Description Length Principle.
MIT Press, 2007.

kohavi:00:kddcup
R. Kohavi, C. Brodley, B. Frasca, L. Mason, and Z. Zheng.
KDD-Cup 2000 organizers' report: Peeling the onion.
SIGKDD Explor., 2(2):86–98, 2000.
http://www.ecn.purdue.edu/KDDCUP.

lam:12:gokrimp
H. T. Lam, F. Mörchen, D. Fradkin, and T. Calders.
Mining compressing sequential patterns.
In SDM, 2012.

laxman2007fast
S. Laxman, P. Sastry, and K. Unnikrishnan.
A fast algorithm for finding frequent episodes in event streams.
In KDD, pages 410–419. ACM, 2007.

vitanyi:93:book
M. Li and P. Vitányi.
An Introduction to Kolmogorov Complexity and its Applications.
Springer, 1993.

mannila:97:discovery
H. Mannila, H. Toivonen, and A. I. Verkamo.
Discovery of frequent episodes in event sequences.
Data Min. Knowl. Disc., 1(3):259–289, 1997.

papapetrou2005discovering
P. Papapetrou, G. Kollios, S. Sclaroff, and D. Gunopulos.
Discovering frequent arrangements of temporal intervals.
In ICDM, pages 354–361. IEEE, 2005.

pei2006discovering
J. Pei, H. Wang, J. Liu, K. Wang, J. Wang, and P. S. Yu.
Discovering frequent closed partial orders from strings.
IEEE TKDE, 18(11):1467–1481, 2006.

petitjean:16:skopus
F. Petitjean, T. Li, N. Tatti, and G. I. Webb.
Skopus: Mining top-k sequential patterns under leverage.
Data Min. Knowl. Disc., 30(5):1086–1111, 2016.

rissanen:78:mdl
J. Rissanen.
Modeling by shortest data description.
Automatica, 14(1):465–471, 1978.

rissanen:83:integers
J. Rissanen.
A universal prior for integers and estimation by minimum description
  length.
Annals Stat., 11(2):416–431, 1983.

smets:12:slim
K. Smets and J. Vreeken.
Slim: Directly mining descriptive patterns.
In SDM, pages 236–247. SIAM, 2012.

tatti:15:epirank
N. Tatti.
Ranking episodes using a partition model.
Data Min. Knowl. Disc., 29(5):1312–1342, 2015.

tatti:11:multievent
N. Tatti and B. Cule.
Mining closed episodes with simultaneous events.
In KDD, pages 1172–1180, 2011.

tatti:12:clsepi
N. Tatti and B. Cule.
Mining closed strict episodes.
Data Min. Knowl. Disc., 25(1):34–66, 2012.

tatti:12:sqs
N. Tatti and J. Vreeken.
The long and the short of it: Summarizing event sequences with serial
  episodes.
In KDD, pages 462–470. ACM, 2012.

vereshchagin:03:kolmo
N. Vereshchagin and P. Vitanyi.
Kolmogorov's structure functions and model selection.
IEEE TIT, 50(12):3265– 3290, 2004.

vreeken:11:krimp
J. Vreeken, M. van Leeuwen, and A. Siebes.
Krimp: Mining itemsets that compress.
Data Min. Knowl. Disc., 23(1):169–214, 2011.

wang:04:bide
J. Wang and J. Han.
Bide: Efficient mining of frequent closed sequences.
ICDE, 0:79, 2004.







§ APPENDIX



 §.§ Estimating Candidates

Here we describe our heuristic strategy for finding new candidates of the form XY as in Sec. <ref>.
First, we need two crucial observations.



Constant Time Difference Estimation Given a database D and an cover C. Let P and Q be two patterns. Let V = {v_1,...,v_N} and W = { w_1,...,w_N} be two set of windows for P and Q, respectively. Both V and W occur in C. Each of these windows v_i and w_i occur in the same sequence. Given the start positions and end positions of the pattern in sequence k_i,  we can write them as v_i = (a_i, b_i, P, k_i) and w_i = (c_i, d_i, Q, k_i). Let U be the set of windows produced by combining them, U = (a_1,d_1,R,k_1),...,(a_N,d_N,R,k_N). Let the windows in U be disjoint and the windows in U be disjoint with the windows in C ∖ (V ∪ W ). Then the difference L(D,C ∪ U ∖ (V ∪ W)) - L(D,C) depends only N, gaps(V), gaps(W), and gaps(U) and can be computed in constant time from these values.





Shorter Windows in Optimal Cover Given a database D and an cover C. Let v = (i, j, X, k) ∈ C. Assume that there exists a window S[a, b] containing X such that w = (a, b, X, l) does not overlap with any window in C and b - a < j - i. Then C is not an optimal cover.



We refer the reader to <cit.> for detailed proofs.

[t]
database D, cover C, and pattern X
pattern 𝑋𝑌 with low L(D, ∪𝑋𝑌)

Y ∈ 
	V_Y ←∅;
	W_Y ←∅;
	U_Y ←∅;
	d_Y ← 0 


T ←∅ 
window v of X in cover C 
	(a, b, X, k) ← v 
	d ← end index of window following v in C 
	𝑡← (v, d, 0); l(t) ← d - a 
	add t into T 


T is not empty 

	t ←min_u ∈ T l(u) 

	(v, d, s) ← t; a ← first index of v 

	w = (c, d, Y, k) ← active w of Y ending at d 
	Y = X (event at a or d is marked) 
		delete t from T 
		 
	

	S_k[a, d] is a minimal window of 𝑋𝑌 
		add v into V_Y 
		add w into W_Y 
		add (a, d, 𝑋𝑌, k) into U_Y 

		d_Y ←min((V, W, U; A) + s, d_Y) 
		|Y| > 1  s ← s + (w) 
		Y = X 
			mark the events at a and d 
			delete t from T 
			 
		
	
	w is the last window in the sequence 
		delete t from T 
	
		d ← end index of the active w' following w 
		update t to (v, d, s) and l(t) to d - a 
	

(X,C,D). Heuristic for finding pattern 𝑋𝑌 with low L(D,∪𝑋𝑌)


We present our heuristic procedure  as pseudo-code in Algorithm <ref>. In this algorithm, given pattern X and a cover C, for a possible extension Y, we enumerate the windows of XY from the shortest to the longest. These windows are constructed by combining two windows in the cover C. We maintain the sets V_Y, W_Y and U_Y (line 1), containing windows of X, windows of Y (to be combined together), and new windows of XY (resulting from the combination) respectively. We do this for every possible extension Y in the code table. At each step we compute the difference in code length of using these windows instead. We maintain d_Y to store this difference. By the observation Constant Time Difference Estimation, this can be done in constant time. We prefer patterns XY which are frequently occurring, with more fills than other meta stream characters. Thus, we want to find shorter windows of XY first. Such a set of windows U could potentially lead to a estimated decrease in code length. Therefore, to ensure that we find shorter windows first and efficiency, we search for all windows (all possible Y) simultaneously using a priority queue T and look only at windows in the cover C. For each window of X in the cover C, we look at windows after it to construct windows XY (Y is the pattern of the window following the window of X). We initialize the priority queue T with these windows (line 4-9), sorted based on length. At each step of the candidate generation algorithm, we retrieve once such window of XY from the priority queue T (line 11) add it to our list U_Y of windows of XY and estimate the change in code length (line 22). As we do not allow overlaps, we need to ensure that windows in U_Y are not overlapping. If a window of XY overlaps with any other window in C, we cannot use both of these windows at the same time. We take this into account by subtracting the gain(w) of this window w overlapping with the window of XY (line 23) <cit.>. The gain(w) of a window w if a upper bound on the bits gained by encoding the events in the database with this window vs. encoding them as singletons. We define the gain as in <cit.> for a window w of the pattern Y (S_k[i,j]),


    (w) =     -L(_p(X)) - (j - i - X)L(_g(X)) 
         - (X - 1)L(_f(X)) + ∑_x ∈ X L(_p(x))  .


Overlapping could also happen if Y = X. So we simply check if the adjacent scans have already used these two instances of X for creating a window for pattern XX (line 25). We now extend our search by looking at the window following the currently considered window of Y in the cover C (line 34). As we allow interleaving and nesting in our covers, we also look at possible windows Y occurring inside or interleaved with windows of other patterns. That is, we look at singletons inside gaps of windows. For each window X in the cover C, we look at all windows following it, until we reach the window of X or the end of the cover.



 §.§ Pruning the Code Table

Here, we present the algorithm we use to prune the code table , used at line 12 of  as pseudo-code in Algorithm <ref>.

[ht]
pattern set 𝒫, database D
pruned pattern set 𝒫 

X ∈𝒫 
	← code table corresponding to (D, 𝒫) 
	' ← code table obtained from  by deleting X 
	g ←∑_w = (i, j, X, k) ∈ C(w) 

	g < L() - L(') 
		L(D, 𝒫∖ X) < L(D, 𝒫) 
			𝒫←𝒫∖ X 
		
	

(𝒫,D)
  



