Transition systems are a powerful formalism, which is widely used for process model representation. A number of approaches were proposed in the process mining field to tackle the problem of constructing transition systems from event logs. Existing approaches discover transition systems that are either too large or too small. In this paper we propose an original approach to discover transition systems that perfectly fit event logs and whose size is adjustable depending on the user's need. The proposed approach allows achieving a required balance between simple and precise models.
Process mining is a relatively new discipline, whose basic research and
practical purpose is to extract process models from data given in the form of event
logs, checking existing models for conformance to actual processes and improving
them. Transition systems are extensively used to formalize processes extracted
from event logs. A transition system can be constructed from an event log by
using prefix-based techniques in a very natural way [
The major weakness of models constructed from real-life event logs is their
size. Despite the fact that there are a number of approaches aimed to reduce
the size of transition systems [
The main goal of our study is to develop an approach for reducing the size of a transition system mined from an event log in a flexible manner. This paper describes an original 3-step algorithm achieving the goal by using a variablesize window based on a state frequency characteristic. The approach preserves (perfect) fitness of a model and balances between its simplicity and precision by introducing a set of adjustable parameters.
Thus, the main contributions are as follows: (1) an original method for reducing transition systems and justification of its applicability; (2) a set of experimental results which show the advantages of the proposed approach as compared with existing methods; an openly available proof of the concept through implementation in a set of ProM plug-ins.
The remaining part of the paper is organized as follows. Section 2 gives an overview of related work in the context of inferring transition systems and their application in the process mining domain. Section 3 introduces basic concepts used further in this paper. A detailed description of the proposed algorithm is given in Section 4. A novel precision calculation algorithm, some significant implementation details, and experimental results are discussed in Section 5. Finally, Section 6 concludes the paper and discusses some directions for future work. 2
A number of works concerning inferring transition systems from event traces
exist. Biermann and Feldman in their work [
Cook and Wolf in their work [
Process discovery along with conformance checking and process enhancement
form the basis of process mining [
The leading role of a transition system as an intermediate representation of
a process is discussed in [
This section introduces basic concepts related to event logs, transition systems and some other notations that are needed for explaining the approach.
P(A) denotes the power set of A — the set of all subsets of A. For a given set A, A∗ is the set of all finite sequences over A.
Definition 1 (Event Trace, Event Log). Let A be a set of activities. The (event) trace is a sequence σ = a1, a2, ..., ai, ..., an ∈ A∗. By σ(i) = ai we denote i-th element (event) of the trace. The [i, k]-subtrace of trace σ ended at i-th event ai is defined as σ[i, k] = ⎧ ⎪⎨ ⎪⎩ σ(1), σ(2), ..., σ(i) ,
if k > i; σ(i − k + 1), ..., σ(i) , if 1 ≤ k ≤ i; , if k = 0. (1)
The complete subtrace of the trace σ ended at i-th event ai is σ[i] = σ[i, i]. By |σ| we denote a trace length. For k ≤ i, k denotes the length of the subtrace. L ∈ P(A∗)is an event log and |L| is a log size that is equal to a number of all traces.
We assume, that event logs do not contain process states explicitly. This way, we need to deduce the desirable states from an event log based on some approach.
In [
Definition 2. A labeled transition system is a tuple TS = (S, E, T, s0, AS), where S is a state space, E is a set of labels, T ⊆ S × E × S is set of transitions, s0 ∈ S is an initial state, and AS ⊆ S is a set of accepting (final) states. We denote the set of output ( input) transitions of a state s ∈ S as s• = {t = (s, e, s ) ∈ T | e ∈ E, s ∈ S} (•s = {t = (s , e, s) ∈ T | e ∈ E, s ∈ S}). Definition 3 (k-window transition system). Let L ∈ P(A∗) be a log over set of activities A and let k ∈ N be a natural number called window size. TS(L, k) = (S, E, T, s0, AS) is a k-window (labeled) transition system built for log L and window size k, where S = {s0} ∪ {σ[i, k] | σ ∈ L, 1 ≤ i ≤ |σ|, k ≤ i} T = {(s0, σ(1), σ[1, k]) | σ ∈ L} ∪ {(σ[i − 1, k], σ(i), σ[i, k]) | σ ∈ L, 2 ≤ i ≤ |σ|}, AS = {s ∈ S | s = σ[|σ|, k], σ ∈ L}, and E = A.
activities. The full transition system TS(L) = (S, E, T, s0, AS) for the log L is
a labeled transition system built for log L, where S = {s0} ∪ {σ[i] | σ ∈ L, 1 ≤
i ≤ |σ|}, T = {(s0, σ(1), σ[
Definition 5. Let TS(L) = (S, E, T, s0, AS) be a transition system over a set of activities E = A, and let σ = a1, ..., an be a trace over A and n = |σ|. We say that trace σ can be replayed in transition system TS(L) if there is a sequence of states s0, ..., sn such that ∃t1 = (s0, a1, s1), t2 = (s1, a2, s2), ..., tn = a1 (sn−1, an, sn) where s0, s1, ..., sn ∈ S, t1, t2, ..., tn ∈ T . We denote this as s0 −→ fis1x −ian→2a..t.ra−a−n→nsitisonn. Wsysetesmay TtShatif tr∃akce<σ nca:n b∃es0pa−ra→t1iallsy1 r−ea→p2lay..e.d−ab→ky istsk parnedsk −a−k−+→1 sk+1 −a−k−+→2 ... −a−→n sn. We denote σ+(TS) = a0, a1, ..., ak and σ−(TS) = ak+1, ..., an . Hence, σ(TS) = σ+(TS) + σ−(TS) where + denotes concatenation of two sequences.
To measure the quality of resulting models, we consider three quality
metrics. We based them primarily on the work [
Definition 6 (Metrics). Let L be an event log and let TS(L) = (S, E, T, s0, AS) be a transition system built for L. Fitness is defined to be the ratio of the number of traces from log L that can be fully replayed in transition system TS(L) to the total number of all traces. Log L perfectly fits transition system TS(L) iff all traces of L can be fully replayed in TS(L).
Simplicity of TS(L) is:
Simpl(TS(L)) = |E| + 1 .
|T | + |S| Precision of TS(L) is: 1 S · | | s∈S Prec(TS(L)) =
Prec(s), Prec(s) =
1 N oV (s) ·
NoV (s) i=1 |s • | − |s•i| , |s • | where Prec(s) is a partial precision for state s, N oV (s) is a number of all visits of state s during a replay of the full transition system. s•i is a set of penalized ۃ a, bۄ
g/1 ۃ a, b, d, gۄ g/1 ۃ a, b, c, d, f, gۄ c/4 output transitions of state s, i.e., transitions that do not have active counterparts as compared to the precise (full TS) model. 4
For the clarification of the approach, the following motivating example is considered. Let L1 be an event log that is defined as follows:
L1 = { a, b, c, d, e, f , a, b, c, d, e, g , a, b, c, d, f, e , a, b, c, d, f, g , a, b, d , a, b, d, g , a, b, d, e, f , a, b, d, e, g } (2)
In addition to the previously discussed flower model, one can build a number of other models that perfectly fit log L1. A model built with unlimited window size is depicted on Figure 1b. This model is a full transition system by the definition. Another model built by an algorithm with a fixed window of size 1 is depicted on Figure 1c. Although all these models perfectly fit log L1, none of them is satisfactory in simplicity and precision at the same time. Thus, we are interested in a trade off between these metrics.
The proposed approach incorporates a 3-steps algorithm sequentially building 3 transition systems. The first transition system, TS1, is built from an event log. The second (TS2) and the third (TS3) transition systems are built from TS1 and TS2, respectively. Finally, TS3 is considered as a desirable result.
The main point of the proposed approach is dynamic variation of the window used for deducing states. For this very purpose, two adjustable parameters are involved into the approach. The first one, Threshold, affects the size of the intermediate transition system (TS2). The second one, Vwsc, is a linear factor used for the dynamic calculation of a variable window size while building the resulting model (TS3). Each step of the algorithm along with both parameters is thoroughly discussed in the following sections. 4.1
The first step of the approach is to construct a full transition system and define a special labeling function mapping every transition to a natural number that determines its frequency characteristic.
of activities A and let TS(L) = (S, E, T, s0, AS) be a full transition system for the L. A frequency characteristic of TS(L) is a function f : T → N defined for t = (σ[j − 1], σ(j), σ[j]) as f (t) = |L |, where L ⊆ L is the maximum subset of L, and ∀σ ∈ L ∃l ∈ N, l > 0 : σ [l − 1] = σ[j − 1], σ (l) = σ(j), σ [l] = σ[j].
Note that for l = 1, σ(0) = = s0 by (1).
Frequency characteristic determines for every transition t a number of traces in log L that start with prefixes σ[j].
The entire procedure of building a full transition system is presented in Algorithm 1.
We denote a full transition system for a given log L as TS1(L) = TS(L). TS1(L1) built for log L1 with function f is depicted on Figure 1b; it is a tree by the construction.
It is easy to see that fitness of the full transition system (TS1(L)) is perfect (equals 1). This is inherent in the algorithm since it builds for each trace in a log a full chain of states following one after another that corresponds to a sequence of events in the trace. 4.2 Constructing a Condensed Transition System (Step 2) c/4 The second step of our approach involves cutting some branches of the full transition system with frequency values less than a cutting threshold parameter; we refer to it as f1. Having f1 set, we can exclude from a model all the states and transitions that correspond to behavior in the event log which is rarely observed. This results in simplifying the tree structure and reduction of the number of states and transitions.
Definition 8 (Condensed Transition System). Let TS1(L) = (S1, E1, T1, s0, AS1) be a full transition system constructed for log L and let f be a frequency characteristic. The Threshold is a real number from [0; 1] determining a cutting threshold f1 as follows: f1 = round(|L| · Threshold) − 1. The value f1 + 1 = round(|L| · Threshold) is a minimum preserved frequency for TS1(L). Algorithm 1: Building a full transition system for a given log L
Input : an event log L Output : a full transition system; TS1(L) = (S, E, T, s0, AS); f is a frequency characteristic; begin
S ← {s0}; for σ ∈ L do s ← s0; for i ← 1 to |σ| do s ← σ[i]; t ← (s, σ(i), s ); if t ∈/ T then
T ← T ∪ {t}; f (t) ← 1; else
f (t) ← f (t) + 1; S ← S ∪ {s }; E ← E ∪ {σ(i)}; if i = |σ| then
AS ← AS ∪ {s};
Note that the frequencies of transitions diminish on the way to the leaves of TS1(L) and TS2(L). Hence, the exclusion of transition tk from a TS1(L) implies the exclusion of a total subtree that has state sk as a root. Thus, TS2(L) obtained as a result of cutting with a given threshold, cannot be disconnected.
The entire procedure of construction a condensed transition system is presented in Algorithm 2. For log L1 with the size |L| = 8 and Threshold = 0.33, we have f1 = 2. A TS2(L) built for the log L1 and f1 = 2 is depicted in Figure 2. It is easy to see that not all the traces from the log can be replayed on TS2(L) as its fitness is not perfect. Therefore, we cannot consider this model as a final result. In this section, we propose an approach to convert TS2(L) to a model with perfect fitness and a size that it less than the size of TS1(L).
Our proposal is to construct a new transition system TS3(L) based on TS2(L) by adding missing states and transitions in order to fully replay all the traces. Unlike building the full transition system, in this case we use partial subtrace σ[i, k] for representing newly added states of TS3(L). The important point here is that parameter k is proportional to the frequency of a corresponding input transition.
The algorithm implementing the proposed approach includes a few steps performed iteratively. Its main part is represented in Algorithm 5. In the beginning, we create a copy of TS2(L), which is denoted as TS3(L).Then, we try to replay all the traces σ from event log L until there is no trace that cannot be fully replayed in the transition system under construction. Along with replay, we build on additional elements of TS3(L) such that an increasing number of traces can be replayed.
Coming back to the example with log L1, we consider transition system TS3(L1) copied from TS2(L1) depicted in Figure 2. We try to replay log L1 on it and perform its transformation. Let σ = a, b, c, d, e, f . The only prefix of σ that can be successfully replayed is σ+(TS3(L1)) = a, b, c, d . Correspondingly, the unreplayable suffix of σ is σ−(TS3(L1)) = e, f .
Algorithm 3 replays a single trace σ and also gets as its input transition system TS3(L) and a frequency characteristic f (discussed above). Moreover, it uses a special function ξ, which maps every trace σ onto number j that determines element σ(j) splitting σ into σ+ and σ−, σ(j) ∈ σ−, and set T T of temporary transitions. The algorithm starts with initial state s0 as a current state s and the first element σ(1) of a trace as a current element σ(i). Then it tries to find an appropriate transition t starting with current state s and marked by symbol σ(i).
We use an example in Figure 3 to illustrate the proposed approach. Next, there are three possible cases. In the first one (for instance, during the replay σ = a, b, d ), t = (s, σ(i), s ) exists with some s ∈ S2 and it is a regular one (t ∈/ T T ). In this case current state s is changed to s and the next element σ(i + 1) is processed. In the second case (if σ = a, b, d, g ), t does not exist. For that case a new temporary transition t = (s, σ(i), s) is added to both the set of transitions and the set of temporary transitions. The end state s is a special temporary state too. It is not marked by any substring and is unique for any temporary transition. For newly added transition t frequency characteristic f is defined to be equal to 1; It means transition t “fired” only once. In the third case, t exists and it is a temporary one (t ∈ T T ). This is the case when transition t “fires” one more time; hence, its frequency should be increased by one.
In both the second and the third cases replaying of the current trace σ is broken and ξ(σ) is set to the position of the first unreplayable element. This is the reason why the temporary state s cannot still be marked with any subtrace and, consequently, one cannot guarantee that s will be preserved in TS3(L).
This way, at each iteration Algorithm 5 tries to replay as many traces from the log as possible. For each state the first unreplayable element is determined and a new temporary transition for the element along with a temporary state are built. TS3(L1) with temporary transitions and states marked by symbols e, f , g and e are depicted in Figure 3a. Note, the total frequency for all temporary transitions is equal to a number of traces that were not able to be replayed at the first iteration.
Trace σ5 = a, b, d from log L1 is an example of a trace that can be replayed at the very first iteration. Once all the traces from the log can be replayed, the reconstruction of TS3(L) is successfully ended.
As long as there is at least one temporary transition/state in TS3(L), it has to be converted to a regular one. It is done by Algorithm 4, which enumerates all uncompleted traces. For each such trace σ, the last regular state s, temporary transition t and temporary state s are obtained; they correspond to the first unplayable element σ(ξ(σ)). Then state s is converted to a regular state by being marked with subtrace σ[ξ(σ), m] of trace σ ended by element σ(ξ(σ)) with length m that is proportional to the frequency of temporary transition t. Furthermore, the dedicated state s0ws is used for the case of zero window size, which accumulates all rare behavior. This results in the shortest subtrace marking such a state than its counterpart in the full transition system. Note that temporary states and transitions are always converted to regular ones.
The latter results in a probability of coinciding numbers of previously distinguishable states. In such a case, all matching states are merged and the total number of states and transitions in the resulting transition system is decreased. Figure 3b shows how two states marked with subtrace d, e are merged to one state.
After the algorithm is finished, no temporary transitions and states are present in TS3(L) anymore. Moreover, all previously unreplayable elements in the traces can now be replayed in TS3(L) as new states for them have been established. At the end of algorithm’s iteration each trace from the log can be replayed at least by one more element than before the iteration. Since the length of each trace is finite, the number of algorithm’s iterations is also finite. Thus, the algorithm finally stops. The resulting TS3(L1) is depicted in Figure 3c.
ReplayTrace of the algorithm of building a reduced transition system TS3(L) Input : trace σ; reduced transition system TS3(L) = (S3, E3, T3, s0, AS3); frequency characteristic f ; set of completely replayed traces CompleteT races ⊆ L; function ξ mapping each trace to a number of the first unreplayable symbol ; set of temporary transitions T T ; Output : true, if a trace
is replayed completely, f alse otherwise Function ReplayTrace(σ, TS3(L), f , CompleteT races, ξ, T T ): Boolean /* Already completed */ if σ ∈ CompleteT races then
return true; s ← s0; for i ← 1 to |σ| do if ∃s : t = (s, σ(i), s ) ∈ T3 then if s = s then f (t) ← f (t) + 1; ξ(σ) = i; return f alse;
of the algorithm of building a reduced transition system TS3(L)
Input : log L; reduced transition system TS3(L) = (S3, E3, T3, s0, AS3); frequency characteristic f ; set of completely replayed traces CompleteT races ⊆ L; function ξ mapping each trace to a number of the first unreplayable symbol; multiplicative factor for fixed window size V wsc ∈ R; set of temporary transitions T T ; /* Converts temporaries Procedure RestateTS(L, TS3(L), f , CompleteT races, ξ, V wsc, T T ) for σ ∈ L do i ← ξ(σ); /* If the trace is already complete if i = |σ| + 1 then return; */ */ s ← σ[i − 1]; t ← (s, σ(i), s); if t ∈/ T T then
return; maxW ndSize ← max(|σ|);
σ wndSize ← round(maxW ndSize · f (t) · V wsc ÷ |L|); /* a special ‘trash’ state */ if wndSize = 0 then else s ← s0ws; s ← σ[i, wndSize]; t ← (s, σ(i), s ); /* Replace the temporary transition and the state by regular ones
*/ S3 ← S3 \ {s} ∪ {s }; T3 ← T3 \ {t} ∪ {t }; T T ← T T \ {t}; f (t ) ← f (t); if i = |σ| then
AS3 ← AS3 ∪ {s }; return; Algorithm 5: Building a reduced transition system TS3(L)
Input : an event log L; a condensed transition system TS2(L) = (S2, E2, T2, s0, AS2); a frequency characteristic f ; a multiplicative factor V wsc ∈ R for fixed window size; Output : a reduced transition system TS3(L) = (S3, E3, T3, s0, AS3); Data: a set of completely replayed traces CompleteT races ⊆ L; a function mapping each trace to a number of first unreplayable symbol ξ; a set of temporary transitions T T ; /* Main part of the algorithm begin
TS3(L) ← TS2(L); repeat unreplayableTraces ← f alse; for σ ∈ L do if ReplayTrace(σ, TS3(L), f , CompleteT races, ξ, T T ) = f alse then
unreplayableTraces ← true; if unreplayableTraces = true then
RestateTS (L, TS3(L), f , CompleteT races, ξ, V wsc, T T ); until unreplayableTraces = f alse; */
In Algorithm 5 Vwsc is an additional parameter used to combine a varying
window size approach with a classical fixed window size approach. It is a real
value from [
Finally, considering fitness of reduced transition system TS3(L) one can postulate the following proposition.
Theorem 1. Let L be a log and let TS3(L) be a reduced transition system based on condensed transition system TS2(L). Then, TS3(L) perfectly fits L. Proof. Let σ = a1, a2, ..., an ∈ A∗ be a trace of log L and σ = σ+(TS2(L)) + σ−(TS2(L)), where σ+(TS2(L)) is a trace prefix that can be “replayed” on TS2(L) and σ−(TS2(L)) is a trace suffix that cannot be “replayed” on TS2(L). σ+(TS2(L)) can be “replayed” on TS3(L) by the construction. Now we need to prove that the entire sequence σ can be “replayed” on TS3(L). We will prove that iteratively for sequences σ(1), ..., σ(i) , where i varies from |σ+(TS2(L))| to |σ|. Basis of induction: the proposition valid for i = |σ+(TS2(L))|, since σ+(TS2(L)) can be “replayed” on TS3(L). Step of induction: the trace σ(1), ..., σ(i) can be “replayed”. Now let us prove that the trace σ(1), ..., σ(i + 1) can be “replayed” as well. According to Algorithms 3 and 4, we “replay” σ(1), ..., σ(i) and add a new state s (if it has not been added previously) and a new edge t = (s, σ(i + 1), s) correspondingly. Thus, trace σ(1), ..., σ(i + 1) now can be replayed, and that proves the step of induction. ۃa, b, d ۄ In this section we evaluate the proposed approach on real-life event logs. In the beginning of the section, an algorithm for precision calculation is introduced. Calculation of metrics for all three transition systems is performed throughout their building.
As we have shown above, fitness of TS1(L) and TS3(L) is perfect. Further, simplicity of a model is easily calculated on the basis of the number of model’s elements.
We propose an algorithm calculating precision metrics for a given transition
system TS(L) based on an idea of simulation [
The approach for calculation of precision is described in Algorithm 6. The algorithm consists of two main steps. First, the algorithm iteratively calculates so-called partial precisions for every state in TS(L) (Algorithm 9). Second, the algorithm sums partial precisions (Algorithm 7) and calculates the average over the number of states.
To get an illustration of this idea, consider a following log:
L2 = { a, b, c , a, b, d , b, c, d , b, d, c }
Full transition system TS1(L2) for the log is depicted in Figure 4c. It is considered to be the most precise reference model. Transition system TSf (L2) in Figure 4a is built with a fixed window size (equal to 1). As a more general model than TS1(L2) it allows more behavior than the reference model. All extra behavior is counted as penalty and influence precision.
Precision calculation invokes simulation routine implemented as a recursive procedure (Algorithm 8). For the example above, TS(L) = TSf (L2) and Algorithm 6: Calculating precision for transition system TS(L)
Input : general (perfectly fit)
transition system TS(L) = (S, E, T, s0, AS) built for log L; reference full transition system TS1(L) = (S1, E1, T1, s01, AS1); Output : value of precision
P rec(TS(L)) for TS(L); Data: partial function η mapping each state of TS(L) to a real number determining the state’s “partial precision”; partial function θ mapping each state s ∈ TS(L) to a natural number determining how many times state s has been visited; /* Main part of the algorithm */ begin
CalcStatePrecision (s0, s01, TS(L), TS1(L), η, θ); P rec(TS(L)) ←SumPartialPrecisions (TS(L), η);
SumPartialPrecisions calculating total precision of TS(L)
Input : general (perfectly fit)
transition system TS(L) = (S, E, T, s0, AS) built for log L; function η mapping each state of TS(L) to a real number determining state’s “partial precision”; Output : value of precision
P rec(TS(L)) for
TS(L); Function SumPartialPrecisions(TS(L), η): Real sum ← 0; for s ∈ S do
sum ← sum + η(s); res ← sum/|S|; return res; TS1(L) = TS1(L2). Initially s = s0 ∈ TS(L) and s1 = s01 ∈ TS1(l) are passed as parameters to the procedure. For each output transition of a current state s, the algorithm tries to find a transition labeled with the same event among output transitions of a current state s1. It is possible to have not more than one transition labeled with the same event, since all transition systems considered in the paper are deterministic by the construction.
For example, consider transition (s0, a, a ) in TSf (L2). It has a matching transition (s0, a, a ) in TS1(L2). The procedure is recursively called with s = a and s1 = a . This step also produces an input edge to vertex a in an unfolding graph depicted on Figure 4b. This step has to be repeated for transitions ( a ), b, b ) and ( a ), b, a, b ) (obtains b1 in the unfolding graph) and transitions ( b ), c, c ) and ( a, b ), c, a, b, c ) (obtains c1 in the unfolding graph). Here, c in TSf (L2) is an accepting state; it contains a virtual output transition (depicted as a gray dashed arrow) to a virtual final state. Similarly, a, b, c from TS1(L2) also has a virtual final transition, which maintains balance (depicted as a dashed output edge in the unfolding graph).
Together with that, c has transition ( c ), d, d ) to state d , which has no counterpart in TS1(L2) (edge (c1, d4) in the graph). The algorithm penalizes this extra transition and calculates partial precision for state c as a difference between a number of output transitions and a number of penalized output transitions divided by a total number of output transitions. Algorithm 8: Procedure CalcStatePrecision calculating “partial precision for entire states” as function η
Input : current state s of TS(L); current state s1 of TS1(L); general (perfectly fit) transition system TS(L) = (S, E, T, s0, AS) built for log L; reference full transition system TS1(L) = (S1, E1, T1, s01, AS1); partial function η mapping each state of TS(L) to a real number determining the state’s “partial precision”; partial function θ mapping each state s ∈ TS(L) to a natural number determining how many times state s has been visited; Procedure CalcStatePrecision(s, s1, TS(L), TS1(L), η, θ) pen ← 0; for t = (s, a, s ) ∈ s• do /* If no matching trans. if ∃t1 = (s1, a, s1) ∈ TS1(L) then
CalcStatePrecision (s , s1, TS(L), TS1(L), η); else
pen ← pen + 1; /* Number of output trans-s otn ← |s • |; if s ∈ AS then otn ← otn + 1 if s1 ∈/ AS1 then
pen ← pen + 1; if otn = 0 then partP artP rec = (otn − pen)/otn;
RecalcStatePrecision (s, partP artP rec); Algorithm 9: Procedure RecalcStatePrecision refines the value of a state’s “partial precision”
Input : state s ∈ S of TS(L) = (S, E, T, s0, AS); function η mapping each state of TS(L) to a real number determining the state’s “partial precision”; partial function θ mapping each state s ∈ S to a natural number determining how many times state s has been visited; new state’s partial precision pprec for refining; Procedure RecalcStatePrecision(s, η, θ, pprec) /* If either η or θ is not defined for this state if η(s) is not defined then
η(s) ← 0; if θ(s) is not defined then
θ(s) ← 0; stP rec ← η(s) · θ(s); θ(s) ← θ(s) + 1; η(s) ← (stP rec + pprec)/θ(s);
Since state a, b, c of TS1(L2) does not allow any further moves, the algorithm leaves the current iteration of the procedure and, thereby, returns to a higher level, to state b of TSf (L2) and a, b of TS1(L2). Then, the algorithm repeats the same steps for all unvisited output transitions.
During its work, the algorithm can normally visit some states of a more general model (TSf (L2) in the example) more than once. For each such visit a value of partial precision for the state is recalculated (Algorithm 9).
Finally, after all states of the reference model have been visited during the simulation, values of ultimate partial precision for each state of TS(L) are represented by η. The last step is to calculate an average value (Algorithm 7), which is the required value of the model’s precision. 5.2
To evaluate the proposed approach, we have developed a number of routines for
the ProM toolkit [
Build and reduce transition systems (xi) plug-in combines routines for building TS1(L), TS2(L), TS3(L) for a given input log L, along with calculation metrics for each transition system built. In the simplest case, the plug-in obtains at its input only event log L and provides ability to configure the settings as follows. (1) Specify a maximum window size for building TS1(L). Default size is unlimited (that is set at a value of -1). By setting the size to a natural number, one can make algorithm act with a fixed window. We use this option for building reference models with fixed windows. (2) Specify a value of Threshold parameter used for building TS2(L). (3) Specify a value of multiplicative factor Vwsc used when building TS3(L).
Once successfully finished, the plug-in produces at its output three transition systems, and, what is the most important for analyzing the results, a hierarchical report. The report represents a set of characteristics organized in a tree structure. They include metrics for each built transition system and additional attributes calculated during the algorithm’s operation. We created a special “view” plugin for browsing such reports, which allows to export information as a JSONstructure or HTML-formatted text.
The both plug-ins are openly available to download on http://pais.hse.ru. 5.3
We evaluated our approach on a set of event logs, both artificial and real-life.
In the following sections we consider “BPI challenge” logs [
Our goal is to compare metrics of models built with an existing fixed window algorithm and models built with the algorithms proposed in this paper.
In our algorithms, there are two parameters affecting a model size: Threshold and Vwsc. Parameter Threshold has a limited impact on the model size. As it is shown in Table 1, dependence of the model size from Threshold is nonlinear in the entire domain of Threshold. For log L4, better simplicity results are in the vicinity of the points 0.2 and 0.8 and worse in the range ends. This is because in the case of dismissive small Threshold model TS2(L) is similar to TS1(L); so, application area of a variable size window lies near the tree leaves. In such a case, noticeable reduction of a model is achievable only for traces with similar suffixes.
Conversely, the closer a value of Threshold to 1, the lesser TS2(L) is built. Consequently, at the stage of building TS3(L) model most of it is to be reconstructed. Preliminary experiments show that selecting Threshold from a range [0.2; 0.8] leads to better results; nevertheless, further elaboration of the parameter’s impact is needed.
By decreasing the value of Vwsc parameter from 1 to 0, significant reduction of a resulting model size is achieved (last two rows of Table 1). For example, for log L3 and a value of Vwsc = 0.05 we have Simpl(TS3(L3)) = 0.3516 and Prec(TS3(L3)) = 0.676 versus Simpl(TSf (L3)) = 0.2479 and Prec(TSf (L3)) = 0.6117 for the case of one window size model. Generally, by adjusting the value of Vwsc, one can obtain a resulting model in a wide range of sizes. Unlike parameter Threshold, parameter Vwsc gives a linear dependence of the model size. Moreover, by varying values both of Threshold and Vwsc it is possible to enhance mutual influence of the parameters on each other. That allows flexible balancing between precision and simplicity. 6
This paper presented a new approach for reducing transition systems, based on an inference algorithm with a varied window size. In contrast to the existing approaches the approach presented in this paper shows advantages of flexible adjustment of a resulting model size. This way, estimation of achievability of the main goal is made on the basis of numerical characteristics of resulting models, both absolute and integral metrics. Future work is aimed at further investigation of impacts of various algorithm coefficients on time costs of a region-based algorithm applied to resulting transition systems. Moreover, we plan to investigate the quality metrics of Petri nets obtained as an outcome of the algorithm.