Despite the advent of scalable process mining techniques that can handle both noisy and incomplete real-life event logs, there is a lack of scalable algorithms capable of handling a common cause of model under tting: when the same activity in the log in fact behaves di erently depending on the number of occurrences in a particular trace. This paper proposes a simple scalable technique to identify these cases and successfully mine better process models from event logs. The technique has been implemented and evaluated on well-known benchmarks in the literature.
Process discovery techniques strive to derive models that are expected to be
good under four quality dimensions: tness, precision, generalization and
simplicity [
The techniques from [
Consider the model Figure 1.a, which was discovered by considering the trace = ABCADCBACDACABCADCBACADE. It is hard to notice that the precision of this model could be improved: Activities A, B and D can be found in any ordering and hence the parallel construct is appropriate, and trace hints that the iterative approach might be a good candidate for describing such a process. Nevertheless, a further analysis shows that there is still place for improvement.
In this paper, we propose to unroll iterative parts of a process to check if there are hidden relations between the activities that are hindered by the limitation of only having one single copy of the activity in the model. See Figure 1.b for an example of such unrolling. In this particular case, we have chosen to repeat the iterative structure so we are forcing to execute its subprocess twice in each iteration. A replay of trace on this new process model highlights that activities B and D were never mutually exclusive. And hence, one could discover that the process model of Figure 1.c might be more precise in describing . 1.2
Di erent approaches exist in the literature for the problem of label splitting
in the context of process mining. We will focus here in recent approaches, and
will illustrate the di erent nature of the technique of this paper with respect to
them. The heuristic techniques in [
Alternatively, global approaches can be found in [
De nition 1. A process model, or simply process, N = (A; C; E ) is a directed graph consisting of activities A, control elements C and edges E . Edges connect activities and control elements. Control elements de ne the behavior of the process model, and are of any of the following types start, nish, split-choice, join-choice spilt-parallel, join-parallel. The only condition over the graph structure is that all maximal paths must start and end with a start and a nish control ows. A subprocess of N is any valid process model (A0; C0; E 0), with A A0, C C0, in which E 0 is de ned as all edges in E that connects any pair of elements in A0 and/or C0.
Processes are a graph representation of a potentially in nite set of sequences of events, which is denoted by L(N ). Generally, all paths from the initial start control element to the end traverse a sequence of activities. Such sequences are the elements of L(N ). Although the graphical notation used for representing processes is irrelevant in terms of the results presented in this paper, Business Process Modelling Notation will be used to improve understandability. De nition 2. Structured process imposes extra conditions on the control elements of a process: all split-parallel nodes (resp. split-choice) must have a unique corresponding join-parallel node (resp. join-choice) such that all paths connecting these two nodes must visit zero or two of any other pair of control elements. This correspondence is unique in the sense that if two split nodes u and v have the same corresponding join node, then u and v are the same node.
This de nition allows us to consider structured processes as smaller subprocesses or individual activities that are interconnected via edges or control elements. Due to the soundness of structured processes, some notions can be easily described.
De nition 3. An iterative subprocess or loop l is the combination of two subprocesses that describe a process that can be repeated. The forward path of l (fwd(l)) is the subprocess that must be executed at least once during the execution l. Whereas the backward path of l (back(l)) is the subprocess such that its execution enforces the loop to re-execute fwd(l).
From now on we will consider all process models to be structured. Importantly, structured processes allow us to map particular events in the trace to a subprocess in the process model. Allowing us to de ne the following notions: De nition 4. Given a process model N with a loop l and a trace 2 L(N ), we de ne El( ) as the number of times fwd(l) is executed during the execution of . De nition 5. Let l be a loop of a process model N and a trace accepted by N . We de ne the projection of to l (denoted by jl) as the result of keeping the events that are mapped into activities contained in l after a replay of in N . Moreover, we de ne the projection of to the exit condition of l (denoted by jExit(l)) as keeping the events that are mapped into activities of N that cannot coexist with the execution of l. In particular, all activities contained in l and any other concurrent activity are erased by this projection.
Considering again the process model of Figure 1.a and trace = ABCADCBACDACABCADCBACADE, we have a loop structure l consisting of: as the forward path, activities A, B and D that can be executed concurrently but B and D are mutually exclusive; and activity C as its backward path. The forward path was executed El( ) = 8 times; jl = fEg whereas jExit(l) = E. Any execution of activity E clearly indicates that any event after event E is not part of the loop.
De nition 6. (Fitness and precision) Process mining techniques aim at
extracting from a log L a process model N with the goal to elicit the real unknown process
S. By relating the behaviors of L, L(N ) and S, particular concepts can be
dened [
Unless stated otherwise, we assume we deal with tting process models. In
case this condition is violated, we assume the process models are rst aligned
with current techniques to satisfy the tness condition [
Most discovery algorithms generate processes in which activities are not
duplicated, forcing the algorithm to introduce loops when an activity is consistently
occurring multiple times per trace. Unfortunately, this constraint may
overgeneralize the resulting process model. Consider, for instance, trace = ABCA.
A technique like the ones in [
First we will describe the unrolling algorithm for improving the precision of loops that are not included in any other iterative process. The main idea of this algorithm is to create a process model that forces the re-execution of the loop and then lters out unused elements. Finally, we will extend this algorithm for the case of nested loops. 3.1
The rst process model of Figure 1.a depicts a process describing the log consisting of the trace ABCADCBACDACABCADCBACADE. One may notice that, when replaying the log on the process model, the forward path (Activities A, B and D) is executed a multiple of two. Hence, we may force the process model to repeat the loop as in Figure 1.b. The unroll of a loop is precisely the process of making explicit this transformation.
De nition 7. A k-unroll of a loop l is the process of substituting the loop for the subprocess de ned by a loop structure with: { A sequence of k 1 copies of the sequence fwd(l);back(l) as the forward path of the new loop structure, { nishing the aforementioned sequence with another copy of fwd(l); { The back(l) is maintained as the backward path of the new loop structure.
In Figure 1.b, a 2-unroll of the iterative process is performed. In this case, the subprocess containing activities A, B and D is the forward path, whilst activity C is the backward path. And hence, its 2-unroll produces a loop structure with the sequence AND (A OR(B; D)) C AND (A OR(B; D)) as the forward path and maintains C as the backward path.
Proposition 1. Given a process model N describing the log L, a k-unrolling (k > 1) of a loop l increases the precision of the model.
Besides, if the process model ts log L and k is a divisor of the greatest common divisor (gcd) of the number of executions per trace of the forward path of l, then the k-unrolled process also ts log L.
Proof. Let l be a loop of N and let Nk be a k-unroll of l with k > 1. By construction of the k-unroll, we can ensure that any trace is an element of the language of N such that the forward path of l is executed a multiple of k times. I.e.
L(Nk) = f 2 L(N ) j El( ) is divisible by kg
We will show that L(Nk) ( L(N ) and hence, based on De nition 6, Nk improves the precision of process model N . Let 0 be a trace accepted by the process N that visits exactly once the forward path of the loop l, and hence the backward path of l is never visited. Since 1 is not a multiple of k, we can ensure that 0 is not an element of L(Nk) and hence L(Nk) n L is a non-trivial subset of L(N ) n L and therefore the precision of N 0 is bigger than the precision of N .
Besides, let k be a divisor of the greatest common divisor of the number of executions per trace of the forward path of l, N a process model that ts log L and Nk the k-unroll of the process model N . Let 0 be a trace of the log L. Since N ts log L, the trace 0 is in the language of the process model. Moreover, the number of executions of the forward path of l is a multiple of k and hence the trace 0 is also an element of the language of L. Therefore, Nk ts log L.
Once all loops have been unrolled, some activities and structures of the resulting process model may be redundant or unused and can be removed or simpli ed allowing for further improvement on the precision of the process model. The rst process model of Figure 2 describes traces ACADBCBD, BCBDACBD and BCAD. Such process may bene t from a 2-unroll as shown in the second process model. Besides, a replay of the three traces highlight that split choices between C and D are unnecessary: starting with C, activities C and D alternate in the execution of the process model. The last process model of Figure 2 depicts the process model after pruning unused paths.
Structured subprocesses allow process models to have nested loops structures This poses a problem for deciding the number of unrolls, as the number of executions of the forward path per trace may be interleaved across embedded loops. The process model from Figure 3 depicts a process with a nested loop that accepts trace ABBBABBB. If we follow the count executions of the forward path, then activity B is recommended to be unrolled 6 times, even though it has never been executed 6 times in a row.
Instead of considering the number of executions per trace, we may count the number of consecutive executions of a forward path. In the particular case of trace ABBBABBB, the forward path B is consecutively executed 3 times at two di erent points in the trace, whilst the forward path consisting of activities A and B is consecutively executed 2 times. De nition 8 formalises this concept by counting the number of executions on maximal subtraces contained in the loop subprocess.
De nition 8. Let l be a loop structure of the process model N , and a trace accepted by N . Then we de ne the set of continuous executions of the loop l in the trace as Informally, the set CEl( ) represents a set of numbers, each one denoting continuous executions of l in .
The combination of no exit condition and maximality of subtrace 0 in De nition 8 ensures that we are splitting the trace on chunks such that a continuous execution of the loop l is not separated in two di erent subtraces. Besides, nonconsecutive executions of the loop cannot be included in the same group as this would have shown some activities incompatible with the execution of the loop. Notice that activities that are executed concurrently alongside the iterative subprocess l might be included in the subtrace 0, but they are removed during the projection to the iterative subprocess l and they are not part of the exit condition.
Consider trace = ABBBABBB and the smaller loop, or B-loop, of process model 3. The exit condition of the B-loop is activity A, since any execution of that particular activity clearly shows that the execution is happening outside the B-loop. Hence, we may split in two instances of 0 = BBB. Notice that we cannot extend it since then we would include an exit condition, and 0 is accepted by the B-loop. And therefore, CEB loop( ) = 3.
Similarly to the non-nested case, the language accepted by an unrolled process model can be described as a re nement on the language accepted by the original process model as depicted in Proposition 2.
Proposition 2. Let N be a process model, and l a loop subprocess of N . Let Nk be any k-unroll of l. Then
L(Nk) = f 2 L(N ) j 8n 2 CEl( ); n is divisible by kg Proof. The de nition of the k-unroll of loop l ensures that any execution of the loop l executed a multiply of k times the forward path of l and hence any maximal subtrace 0 such that 0jl 2 L(l), 0jExit(l) = ; must satisfy that k divides El( 0).
On the other hand, let be a trace in L(N ) such that all continuous executions CEl( ) are divisible by k. Then, is also an element of the language L(Nk). Suppose not, then the trace violates any behavioural relation between a set of activities or the iterative process must nish before repeating k times the forward path. Both cases are not possible. The former violates the fact that 2 L(N ) and the latter violates the fact that CEl( ) only contains multiples of k.
Proposition 3 is a direct consequence of Proposition 2, due to the hard constraint that k divides all n 2 CE(t; l).
N describing the log L, a k-unrolling (k > 1) of a loop l increases the precision of the process model. Besides, if the process model ts log L and k is a divisor of CL(l; t) for all t 2 L(N ), then the k-unrolled process model also ts log L.
Revisiting the example of trace ABBBABBB and the process model of Figure
3, which contains a nested loop, a replay of the trace contemplates that the
big loop is executed 2 times and the smaller loop is executed 3 times on each
execution. Hence, we could perform a 3-unroll on the latter and a 2-unroll on the
former. Doing so, we discover the second process model of Figure 3, and a second
replay highlights the possibility of removing the unnecessary loop structures as
illustrated by Figure 3.
To evaluate our duplicate technique, we reuse an existing dataset comprising 15
small logs [
Table 1 contains the precision obtained with the process model discovered
with Inductive Miner (IM), the precision obtained after unrolling these process
models and precision obtained by PNSimpl [
Results indicate that precision gain is similar with both techniques, provided that unrolling is possible. Nevertheless, both approaches treat the initial process model di erently: Our approach enhances the expressive power of the initial process, whilst PNSimpl rediscover the process after each label split and, hence, the nal process might be signi cantly di erent. Besides, the ability of performing unrolls (by losing tness) enables us to highlight interesting properties of the process. For instance, loop unrolling allowed us to check that the nancing organization of the BPI Challenge 2012 usually had to call customers twice for getting the necessary information. Is there any reason one attempt is not enough?
In terms of complexity, the technique of this paper may be a light alternative
for methods like [
In this paper, we presented a method for improving the precision of structural subprocesses based on explicitly repeating iterative subprocesses and pruning unused constructs and activities. We have shown that this approach is applicable to simulations of real-life processes, and also it is applicable to real-life scenarios.
The presented approach is the rst step on considering the unrolling of iterative processes. Results in Table 1 show several examples of how unrolling improve the precision of the process models, with minimal impact on their complexity. Nevertheless, bigger process models might be more di cult to understand and, hence, it remains to conduct expert reviews on readability and understandability of process models after unrolling. Besides, we have experienced on some datasets that some iterative processes can be explained as a few iterations are used for initialization, and then the real loop starts. We would also like to study how the k-unroll operation a ects the precision of the process model for a particular precision metric. In particular, is it possible to establish a lower bound on the increase of the precision?
This work is funded by Secretaria de Universitats i Recerca of Generalitat de Catalunya, under the Industrial Doctorate Program 2013DI062, and the Spanish Ministry for Economy and Competitiveness, the European Union (FEDER funds) under grant COMMAS (ref. TIN2013-46181-C2-1-R).