Lion's share of process mining research focuses on the discovery of end-to-end process models describing the characteristic behavior of observed cases. The notion of a process instance (i.e., the case) plays an important role in process mining. Pattern mining techniques (such as frequent itemset mining, association rule learning, sequence mining, and traditional episode mining) do not consider process instances. An episode is a collection of partially ordered events. In this paper, we present a new technique (and corresponding implementation) that discovers frequently occurring episodes in event logs thereby exploiting the fact that events are associated with cases. Hence, the work can be positioned in-between process mining and pattern mining. Episode discovery has its applications in, amongst others, discovering local patterns in complex processes and conformance checking based on partial orders. We also discover episode rules to predict behavior and discover correlated behaviors in processes. We have developed a ProM plug-in that exploits e cient algorithms for the discovery of frequent episodes and episode rules. Experimental results based on real-life event logs demonstrate the feasibility and usefulness of the approach.
Process mining provides a powerful way to analyze operational processes based on event data. Unlike classical purely model-based approaches (e.g., simulation and veri cation), process mining is driven by \raw" observed behavior instead of assumptions or aggregate data. Unlike classical data-driven approaches, process mining is truly process-oriented and relates events to high-level end-to-end process models [1].
In this paper, we use ideas inspired by episode mining [2] and apply these to the discovery of partially ordered sets of activities in event logs. Event logs serve as the starting point for process mining. An event log can be viewed as a multiset of traces [1]. Each trace describes the life-cycle of a particular case (i.e., a process instance) in terms of the activities executed. Often event logs store additional information about events, e.g., the resource (i.e., person or device) executing or initiating the activity, the timestamp of the event, or data elements (e.g., cost or involved products) recorded with the event.
Each trace in the event log describes the life-cycle of a case from start to completion. Hence, process discovery techniques aim to transform these event logs into end-to-end process models. Often the overall end-to-end process model is rather complicated because of the variability of real life processes. This results in \Spaghetti-like" diagrams. Therefore, it is interesting to also search for more local patterns in the event log { using episode discovery { while still exploiting the notion of process instances. Another useful application of episode discovery is conformance checking based on partial orders [3].
Since the seminal papers related to the Apriori algorithm [4, 5, 6], many pattern mining techniques have been proposed. These techniques do not consider the ordering of events [4] or assume an unbounded stream of events [5, 6] without considering process instances. Mannila et al. [2] proposed an extension of sequence mining [5, 6] allowing for partially ordered events. An episode is a partially ordered set of activities and it is frequent if it is \embedded" in many sliding time windows. Unlike in [2], our episode discovery technique does not use an arbitrary sliding window. Instead, we exploit the notion of process instances. Although the idea is fairly straightforward, as far as we know, this notion of frequent episodes was never applied to event logs.
Numerous applications of process mining to real-life event logs illustrate that concurrency is a key notion in process discovery [1, 7, 8]. One should avoid showing all observed interleavings in a process model. First of all, the model gets too complex (think of the classical \state-explosion problem"). Second, the resulting model will be over tting (typically one sees only a fraction of the possible interleavings). This makes the idea of episode mining particularly attractive.
The remainder of this paper is organized as follows. Section 2 positions the work in existing literature. The novel notion of episodes and the corresponding rules are de ned in Section 3. Section 4 describes the algorithms and corresponding implementation in the process mining framework ProM. The approach and implementation are evaluated in Section 5 using several publicly available event logs. Section 6 concludes the paper. 2
The notion of frequent episode mining was rst de ned by Mannila et al. [2]. In their paper, they applied the notion of frequent episodes to (large) event sequences. The basic pruning technique employed in [2] is based on the frequency of episodes in an event sequence. Mannila et al. considered the mining of serial and parallel episodes separately, each discovered by a distinct algorithm. Laxman and Sastry improved on the episode discovery algorithm of Mannila by employing new frequency calculation and pruning techniques [9]. Experiments suggest that the improvement of Laxman and Sastry yields a 7 times speedup factor on both real and synthetic datasets.
Related to the discovery of episodes or partial orders is the discovery of end-to-end process models able to capture concurrency explicitly. The algorithm [10] was the rst process discovery algorithm adequately handling concurrency. Many other discovery techniques followed, e.g., heuristic mining [11] able to deal with noise and low-frequent behavior. The HeuristicsMiner is based on the notion of causal nets (C-nets). Several variants of the algorithm have been proposed [12, 13]. Moreover, completely di erent approaches have been proposed, e.g., the di erent types of genetic process mining [14, 15], techniques based on state-based regions [16, 17], and techniques based on language-based regions [18, 19]. Another, more recent, approach is inductive process mining where the event log is split recursively [20]. The latter technique always produces a block-structured and sound process model. All the discovery techniques mentioned are able to uncover concurrency based on example behavior in the log. Additional feature comparisons are summarised in Table 1.
The episode mining technique presented in this paper is based on the discovery of frequent item sets. A well-known algorithm for mining frequent item sets and association rules is the Apriori algorithm by Agrawal and Srikant [4]. One of the pitfalls in association rule mining is the huge number of solutions. One way of dealing with this problem is the notion of representative association rules, as described by Kryszkiewicz [21]. This notion uses user speci ed constraints to reduce the number of `similar' results. Both sequence mining [5, 6] and episode mining [2] can be viewed as extensions of frequent item set mining. This section de nes basic notions such as event logs, episodes and rules. Note that our notion of episodes is di erent from the notion in [2] which does not consider process instances.
T = hA1; : : : ; Ani of activities Ai 2 A occurring at time index i relative to the other activities in T .
Event log An event log L = [T1; : : : ; Tm] is a multiset of traces Ti. Note that the same trace may appear multiple times in an event log. Each trace corresponds to an execution of a process, i.e., a case or process instance. In this simple de nition of an event log, an event refers to just an activity. Often event logs store additional information about events, such as timestamps. 3.2
Episode An episode is a partial ordered collection of events. Episodes are depicted using the transitive reduction of directed acyclic graphs, where the nodes represent events, and the edges imply the partial order on events. Note that the presence of an edge implies serial behavior. Figure 1 shows the transitive reduction of an example episode.
Formally, an episode = (V; ; g) is a triple, where V is a set of events (nodes), is a partial order on V , and g : V 7! A is a left-total function from events to activities, thereby labelling the nodes/events [2]. For two vertices u; v 2 V we have u < v i u v and u 6= v. In addition, we de ne G to be the multiset of activities/labels used: G = [ g(v) j v 2 V ]. Note that if jV j 1, then we got an singleton or empty episode. For the rest of this paper, we ignore empty episodes. We call an episode parallel when = ;.
Subepisode and Equality An episode = (V 0; 0; g0) is a subepisode of denoted , i there is an injective mapping f : V 0 7! V such that: = (V; ; g), (8v 2 V 0 : g0(v) = g(f (v))) ^ (8v; w 2 V 0 ^ v 0 w : f (v) f (w))
An episode equals episode , denoted is a strict subepisode of , denoted , i = i
^ ^ 6= .
. An episode Episode construction Two episodes = (V; ; g) and = (V 0; 0; g0) can be `merged' to construct a new episode = (V ; ; g ). is the smallest (i.e., smallest sets V and ) such that and . As shown below, such an episode always exists.
G = G [ G0 = f (f (v); f (w)) j (v; w) 2 g [ f (f 0(v); f 0(w)) j (v; w) 2 0 g activity witness order witness Occurrence An episode = (V; ; g) occurs in an event trace T = hA1; : : : ; Ani, denoted v T , i there exists an injective mapping h : V 7! f1; : : ; ng such that: (8v 2 V : g(v) = Ah(v)) ^ (8v; w 2 V ^ v w : h(v) h(w)) In Figure 2 an example of an \event to trace map" h for occurrence checking is given. Event indices:
Trace: A B A C A D A B A C A D (A1) A
A (A2) (A1) A Episode:
B (B)
C (C) Mapping 1
D (D)
B (B)
C (C) Mapping 2
A (A2) D (D)
event log L, then all subepisodes with are also frequent in L. Formally, we have for a given : (8 : freq ( ) freq ( ))
event log L = [T1; : : : ; Tm] is de ned as:
ActFreq (A) = j [ Ti j Ti 2 L ^ A 2 Ti ] j jLj Given a frequency threshold minActFreq , an activity A is frequent i ActFreq (A) minActFreq .
Trace Distance Given episode = (V; ; g) occurring in an event trace T = hA1; : : : ; Ani, as indicated by the event to trace map h : V 7! f1; : : ; ng. Then the trace distance traceDist ( ; T ) is de ned as: traceDist ( ; T ) = max f h(v) j v 2 V g min f h(v) j v 2 V g In Figure 2, the left mapping yields traceDist ( ; T ) = 6 mapping yields traceDist ( ; T ) = 6 2 = 4. 1 = 5, and the right
Given a trace distance interval [minTraceDist ; maxTraceDist ], an episode is accepted in trace T with respect to the trace distance interval i minTraceDist traceDist ( ; T ) maxTraceDist .
Informally, the conceptual idea behind a trace distance interval is that we are interested in a partial order on events occurring relatively close in time. 3.3
after seeing , then likely the larger episode will occur as well.
The con dence of the episode rule is given by: stating that conf ( ) ) ) = freq ( ) freq ( )
Lemma 2 (Con dence and subepisodes). If an episode rule ) is valid in an event log L, then for all episodes 0 with 0 the event rule 0 ) is also valid in L. Formally: (8 0 : conf ( ) ) conf ( 0 ) )) Episode rule magnitude Let the graph size size( ) of an episode be denoted as the sum of the nodes and edges in the transitive reduction of the episode. The magnitude of an episode rule is de ned as: mag ( ) ) = size( ) size( )
`adds to' or `magni es' episode . The magnitude of an Episode rule allows smart ltering on generated rules. Typically, an extremely low (approaching zero) or high (approaching one) magnitude indicates a trivial episode rule. 4
The de nitions and insights provided in the previous section have been used to implement a episode (rule) discovery plug-in in ProM. To be able to analyze real-life event logs, we need e cient algorithms. These are described next.
Notation: in the listed algorithms, we will reference to the elements of an episode = (V; ; g) as :V , : and :g. 4.1
Discovering frequent episodes is done in two phases. The rst phase discovers parallel episodes (i.e., nodes only), the second phase discovers partial orders (i.e., adding the edges). The main routine for discovering frequent episodes is given in Algorithm 1.
Algorithm 1: Episodes discovery Input: An event log L, an activity alphabet A, a frequency threshold minFreq.
Output: A set of frequent episodes Description: Two-phase episode discovery. Each phase alternates by generating new candidate episodes (Cl), and recognizing frequent candidates in the event log (Fl).
Proof of termination: Note that candidate episode generation with Fl = ; will yield Cl = ;. Since each iteration the generated episodes become strictly larger (in terms of V and ), eventually the generated episodes cannot occur in any trace. Therefore, always eventually Fl = ;, and thus we will always terminate.
EpisodeDiscovery(L; A; minFreq)
(
The generation of candidate episodes for each phase is an adaptation of the well-known Apriori algorithm over an event log. Given a set of frequent episodes Fl, we can construct a candidate episode by combining two partially overlapping episodes and from Fl. Note that this implements the episode construction operation = .
For phase 1, we have Fl contains frequent episodes with l nodes and no edges. A candidate episode overlap on the rst l will have l + 1 nodes, resulting from episodes and that 1 nodes. This generation is implemented by Algorithm 2.
For phase 2, we have Fl contains frequent episodes with l edges. A candidate episode rst l will have l + 1 edges, resulting from episodes and that overlap on the 1 edges and have the same set of nodes. This generation is implemented by Algorithm 3. Note that, formally, the partial order is the transitive closure of the set of edges being constructed, and that the edges are really only the transitive reduction of this partial order.
Algorithm 2: Candidate episode generation { Parallel Input: A set of frequent episodes Fl with l nodes.
Output: A set of candidate episodes Cl+1 with l + 1 nodes.
Description: Generates candidate episodes by merging overlapping episodes = ). For parallel episodes, overlapping means: sharing l 1 nodes.
GenerateCandidateParallel(l; Fl)
(
Algorithm 3: Candidate episode generation { Partial order
In order to check if a candidate episode is frequent, we check if freq ( )
The computation of freq ( ) boils down to counting the number of traces T with
v T . Algorithm 4 recognizes all frequent episodes from a set of candidate episodes
using the above described approach. Note that for both parallel and partial order
episodes we can use the same recognition algorithm.
minFreq .
(
Algorithm 4: Recognize frequent episodes Input: An event log L, a set of candidate episodes Cl, a frequency threshold minFreq. Output: A set of frequent episodes Fl Description: Recognizes frequent episodes, by ltering out candidate episodes that do not occur frequently in the log. Note: If Fl = ;, then Cl = ;.
RecognizeFrequentEpisodes(L; Cl; minFreq)
(
minFreq then Fl = Fl [ fCl[i]g
Checking whether an episode occurs in a trace T = hA1; : : : ; Ani is done via checking the existence of the mapping h : :V 7! f1; : : ; ng. This results in checking the two propositions shown below. Algorithm 5 implements these checks. { Checking whether each node v 2 :V has a unique witness in trace T . { Checking whether the (injective) mapping h respects the partial order indicated by : .
For the discovery of an injective mapping h for a speci c episode and trace T we use the following recipe. First, we declare the class of models H : A 7! P(N) such that for each activity a 2 A we get the set of indices i at which a = Ai 2 T .
is derived from H by choosing an index i 2 H(f (v)) for each node v 2 :V . With such a model h, we can perform the actual partial order check against : .
Algorithm 5: This algorithm implements occurrence checking via recursive discovery of the injective mapping h as per the occurrence de nition. Input: An episode , a trace T .
Output: True i v T Description: Implements occurrence checking based on nding an occurrence proof in the form of a mapping h : :V 7! f1; : : ; ng.
Occurs( = (V; ; g); T )
(
Output: True i there is a mapping h, as per the occurrence de nition, derivable from H
Description: Recursive implementation for nding h based on the following induction principle: Base
sctaespe (biyf -apdadritn)g:Eavmeraypvpi2ngVfoirs mavaeprpteedx (vv2=2ddoommhh.)(.IS.et.e,pincdausect(ieolnset-optahrte)n:u(ImHb)enr voefrmtiacpespaedrevmeratpicpeesd.),
checkModel( = (V; ; g); H; h)
(
Using the pruning techniques described below, we reduce the number of generated episodes (and thereby computation time and memory requirements) and lter out uninteresting results. These techniques eliminate less interesting episodes by ignoring infrequent activities and skipping partial orders on activities with low temporal locality. Activity Pruning Based on the frequency of an activity, uninteresting episodes can be pruned in an early stage. This is achieved by replacing the activity alphabet
(8A 2 A : ActFreq (A) minActFreq ), on line 4 in Algorithm 1. This pruning technique allows the episode discovery algorithm to be more resistant to logs with many infrequent activities, which are indicative of exceptions or noise. Trace Distance Pruning The pruning of episodes based on a trace distance interval can be achieved by adding the trace distance interval check to line 2 of Algorithm 5. Note that if there are two or more interpretations for h, with one passing and one rejected by the interval check, then we will nd the correct interpretation thanks to the 9 on line 5. 4.5
The discovery of episode rules is done after discovering all the frequent episodes. For all frequent episodes , we consider all frequent subepisodes with for the episode rule ) .
For e ciently nding potential frequent subepisodes , we use the notion of \discovery tree", based on episode construction. Each time we recognize a frequent episode created from combining frequent episodes and ", we recognize as a child of and ". Similarly, and " are the parents of . See Figure 3 for an example of a discovery tree.
B A
C C "
A B A
C C
A B
C
Using the discovery tree we can walk from an episode along the discovery parents of . Each time we nd a parent with , we can consider the parents and children of . As result of Lemma 2, we cannot apply pruning in either direction of the parent-child relation based on the con dence conf ( ) ). This is easy to see for the child direction. For the parent direction, observe the discovery tree in Figure 3 and . If for episode we would stop before visiting the parents of , we would never consider (which has ). 4.6
We implemented the episode discovery algorithm as a ProM 6 plug-in (see also
Figure 4), written in Java. Since the Occurs() algorithm (
5.1
This section reviews the feasibility of the approach using both synthetic and real-life event data.
We ran a series of experiments on two type of event logs. The rst event log, bigger-example.xes, is an arti cial event log from the Chapter 5 of [1] and available via http://www.processmining.org/event_logs_and_models_used_in_book. The second event log, BPI Challenge 2012.xes, is a real life event log available via doi:10.4121/uuid:3926db30-f712-4394-aebc-75976070e91f. For these experiments we used a laptop with a Core i5-3570K CPU, 8 GB RAM and Java SE Runtime Environment 1.7.0 07-b11 (32 bit). 5.2
(a) Event log: bigger-example.xes { minFreq = 0:05, minActFreq = 0:05, maxTraceDist = 3 (b) Event log: BPI Challenge 2012 { minFreq = 0:55, minActFreq = 0:55, maxTraceDist = 5
As can be seen in all the experiments in Figure 5, we see that the running time is strongly related to the discovered number of episodes. Note that if some parameters are poorly chosen, like high maxTraceDist in Figure 5(f), then a relatively large class of episodes seems to become frequent, thus increasing the running time drastically.
For a reasonably low number of frequent episodes (< 500, more will a human not inspect), the algorithm turns out to be quite fast (at most a few seconds for the Challenge log). We noted a virtual nonexistent contribution of the parallel episode mining phase to the total running time. This can be explained by a simple combinatorial argument: there are far more partial orders to be considered than there are parallel episodes.
An analysis of the e ects of changing the minFreq parameter (Figure 5(a), 5(b)) shows that a poorly chosen value results in many episodes. In addition, the minFreq parameter gives us ne-grained control of the number of results. It gradually increases the total number of episodes for lower values. Note that, especially for the Challenge event log, low values for minFreq can dramatically increase the running time. This is due to the large number of candidate episodes being generated.
Secondly, note that for the minActFreq parameter (Figure 5(c), 5(d)), there seems to be a cuto point that separates frequent from infrequent activities. Small changes around this cuto point may have a dramatic e ect on the number of episodes discovered.
Finally, for the maxTraceDist parameter (Figure 5(e), 5(f)), we see that this parameter seems to have a sweet-spot where a low { but not too low { number of episodes are discovered. Chosen a value for maxTraceDist just after this sweet-spot yields a huge number of episodes.
When comparing the arti cial and real life event logs, we see a remarkable pattern. The arti cial event log (bigger-example.xes ), shown in Figure 5(a) appears to be far more ne-grained than the real life event log (BPI Challenge 2012.xes ) shown in Figure 5(b). In the real life event log there appears to be a clear distinction between frequent and infrequent episodes. In the arti cial event log a more exponential pattern occurs. Most of the increase in frequent episodes, for decreasing minF req, is again in the partial order discovery phase. 5.3
As noted in the introduction, often the overall end-to-end process models are rather complicated. Therefore, the search for local patterns (i.e., episodes) is interesting. A good example of a complicated process is the BPI Challenge 2012 log. In Figure 6 part of the \spaghetti-like" process models are shown, as an indication of the complexity. The episodes discovered over same log, depicted in Figure 4(b) gives us a simple and clear insight into important local patterns in the BPI Challenge 2012 log. Hence, in these \spaghetti-like" process models, the episode discovery technique allows us to quickly understand the main patterns. 6
In this paper, we considered the problem of discovering frequently occurring episodes in an event log. An episode is a collection of events that occur in a given partial order. We presented e cient algorithms for the discovery of frequent episodes and episode rules occurring in an event log, and presented experimental results.
Our experimental evaluation shows that the running time is strongly related to the discovered number of episodes. For a reasonably low number of frequent episodes (< 500, more will a human not inspect), the algorithm turns out to be quite fast (at most a few seconds). The main problem is the correct setting of the episode pruning parameters minFreq , minActFreq , and maxTraceDist .
During the development of the algorithm for ProM 6, special attention was paid to optimizing the Occurs() algorithm (Algorithm 5) implementation, which proved to be the main bottleneck. Future work could be to prune occurrence checking based on the parents of an episode, leveraging the fact that an episode cannot occur in a trace if a parent also did occur in that trace.
Another approach to improve the algorithm is to apply the generic divide and conquer approach for process mining, as de ned in [22]. This approach splits the set of activities into a collection of partly overlapping activity sets. For each activity set, the log is projected onto the relevant events, and the regular episode discovery algorithm is applied. In essence, the same trick is applied as used by the minActFreq (a) Event log: BPI Challenge 2012 { Discovery algorithm: -algorithm [10].
(b) Event log: BPI Challenge 2012 { Discovery algorithm: [11]. parameter (using an alphabet subset), which is to create a di erent set of initial 1-node parallel episodes to start discovering with.
The main bottleneck is the frequency computation by checking the occurrence of each episode in each trace. Typically, we have a small amount of episodes to check, but many traces to check against. Using the MapReduce programming model developed by Dean and Ghemawat, we can easily parallelize the episode discovery algorithm and execute it on a large cluster of commodity machines [23]. The MapReduce programming model requires us to de ne map and reduce functions. The map function, in our case, accepts a trace and produces [episode, trace] pairs for each episode occurring in the given trace. The reduce function accepts an episode plus a list of traces in which that episode occurs, and outputs a singleton list if the episode is frequent, and an empty list otherwise. This way, the main bottleneck of the algorithm is e ectively parallelized.