Measuring precision of modeled behavior

Measuring Precision of Modeled Behavior A. Adriansyah ·J. Munoz-Gama ·J. Carmona ·B.F. van Dongen · W.M.P. van der Aalst Abstract Conformance checking techniques compare observed behavior (i.e., event logs) with modeled behavior for a variety of reasons. For example, discrepancies between a normative process model and recorded behavior may point to fraud or inefficiencies. The resulting diagnostics can be used for auditing and compliance management. Conformance checking can also be used to judge a process model automatically discovered from an event log. Models discovered using different process discovery techniques need to be compared objectively. These examples illustrate just a few of the many use cases for aligning observed and modeled behavior. Thus far, most conformance checking techniques focused on replay fitness, i.e., the ability to reproduce the event log. However, it is easy to construct models that allow for lots of behavior (including the observed behavior) without being precise. In this paper, we propose a method to measure precision of process models, given their event logs by first aligning the logs to the models. This way, the measurement is not sensitive to non-fitting executions and more accurate values can be obtained for non-fitting logs. Furthermore, we introduce several variants of the technique to deal better with incomplete logs and reduce possible bias due to behavioral property of process models. The approach has been implemented in the ProM 6 framework and tested against both artificial and real-life cases. Experiments show that the approach is robust to noise and applicable to handle logs and models of real-life complexity. A. Adriansyah ·B.F. van Dongen ·W.M.P. van der Aalst Department of Mathematics and Computer Science Eindhoven University of Technology P.O. Box 513, 5600 MB Eindhoven, The Netherlands E-mail: {a.adriansyah,b.f.v.dongen,w.m.p.v.d.aalst}@tue.nl J. Munoz-Gama ·J. Carmona Universitat Politecnica de Catalunya Barcelona, Spain E-mail: {jmunoz,jcarmona}@lsi.upc.edu 2 Adriansyah, Munoz-Gama, Carmona, van Dongen and van der Aalst Examination Radiology Therapy Update record Allergy test Chemotherapy Post-chemo Home care Operation start A “flower” model (F)An overfitting (precise) model (P) Event Log abcd acbe afgh abibcd 1,230 1,442 435 1,893 Trace Frequency ab c d e f g h i Therapy Update record Allergy test Chemotherapy Post-chemo Examination Radiology Operation Radiology Update record Therapy Update record Radiology Home care start end ab cd ibcd cbe fgh Fig. 1: Example of an extremely imprecise (underfitting) and precise model (overfitting) for a given log. Keywords Precision measurement ·Log-model alignment ·Conformance checking ·Process mining 1 Introduction The starting point for most Business Process Management (BPM) activities are process models, as they provide insights into possible scenarios [21]. Process models are used for analysis (e.g., simulation [5]), enactment [21], redesign [18], and process improvement [28,29]. Therefore, they should reflect the dominant behavior accurately. The increasing availability of event data enables the application of conformance checking [2,4,30]. Conformance checking techniques compare recorded process executions in the form of event logs with process models to quantify how “good” are the models with respect to their executions. Conformance can be viewed along multiple orthogonal dimensions: (1) fitness, (2) precision, (3) generalization, and (4) simplicity [2,14]. In this paper, we focus on the precision dimension. Given an event log and a process model, precision penalizes the model for allowing behavior that is unlikely given the observed behavior in the log. Take for example the two models and the event log in Figure 1. Both models show a cancer patient handling process in a hospital and are shown using Petri net formalism [27].1All traces in the log can be reproduced by both models, i.e., the traces perfectly fit the models. However, notice that the “flower” model (F) may provide misleading insights, as it also allows for much more behavior not appearing in the log. In contrast, the other model (P) only allows traces that occur in the log. Hence, the precision of model Pis better than model Fwith respect to the log. Many existing precision metrics (e.g., [25, 30, 34]) do not explicitly take into account possible deviations between the behavior observed in the event log with the behavior modeled in the models, while many case studies show 1For the reader not familiar with Petri nets, a Petri net is a bipartite graph that contains two types of nodes: places (circles) and transitions (boxes). A place may contain tokens (black dots), and a transition can fire if its predecessor places contain a token. When fired, a transition removes a token from each input place and adds a token to each successor place. Measuring Precision of Modeled Behavior 3 that such deviations often occur in practice (e.g., [11,16,19,20,23,31,35,36]). Thus, these metrics might be biased due to unfitting logs and models. In this paper, we explicitly take deviations between the observed behavior in event logs and the modeled behavior in process models into account and propose a robust approach to measure the precision between a (possibly non-fitting) event log and a model. First, we align the log and the model to find, for each trace, those complete activity sequences in the model that are most similar to the trace. Then we use these alignments to measure precision between the original log and the model. In this paper, we generalize the approach presented in [9] by introducing various possible ways of computing precisions based on alignments, their log completeness requirements, and their issues in order to obtain accurate precision values. The remainder of this paper is organized as follows: Section 2 shows the notations and preliminary concepts that are used throughout this paper. Alignments between event logs and models are explained in Section 3. The alignmentbased precision approach is presented in Section 4. In Section 5 we propose a series of extensions for the basic precision approach. Experimental results are given in Section 6. Section 7 concludes the paper. 2 Preliminaries Conformance checking requires as input both a process model and an event log. Therefore, we first formalize process models and logs after introducing a set of notations that is used in the remainder of this paper. 2.1 Sequence and Multiset Let Wbe a set. For (finite) sequences of elements over a set W, we use to denote an empty sequence. A concatenation of sequences σ1and σ2is denoted with σ1·σ2.W∗denotes the set of all finite sequences over W. We refer to the i-th element of a sequence σas σ[i] and we use |σ|to represent the length of sequence σ. We say that any x∈(W×W) is a pair. We use π1(x) and π2(x) to refer to the first and the second element of pair xrespectively. We generalize this notation to sequences: πi(σ) = hπi(σ[1]), . . . , πi(σ[|σ|])i. For example, π1(h(a, b),(b, c),(b, d)i) = hπ1((a, b)), π1((b, c)), π1((b, d))i=ha, b, bi. For all Q⊆W,σ↓Qdenotes the projection of σ∈W∗on Q, e.g., ha, a, b, ci↓{a,c}= ha, a, ci.P(Q) denotes the powerset of Q, e.g., P({a, b}) = {{},{a},{b},{a, b}}. Amultiset mover Wis a mapping m:W→IN. We overload the set notation, using ∅for the empty multiset and ∈for the element inclusion. We write e.g., m= [p2, q] or m= [p, p, q] for a multiset mwith m(p) = 2, m(q) = 1, and m(x) = 0 for all x6∈ {p, q}. We use |m|to indicate the total number of elements in multiset m(e.g., |[p2, q]|= 3). 4 Adriansyah, Munoz-Gama, Carmona, van Dongen and van der Aalst 2.2 Event Log and Process Model The starting point for conformance checking is an event log. An event log records the execution of all cases (i.e., process instances). Each case is described by a trace, i.e., an activity sequence. Different cases may have exactly the same trace. In reality, not all activities performed in a process are logged. We define the set of all logged activities from the universe of activities Aas AL⊆A. An event log over ALis a multiset L:AL∗→IN. For example, the log in Figure 1 is formalized as [ha, b, c, di1230,ha, c, b, ei1442,ha,f,g,hi435,ha, b, i, b, c, di1893]. Note that for simplicity, we omit brackets for sequences of activities in Figure 1. Similarly, a process model defines a set of sequences of activities that leads to proper termination of the process. Furthermore, some activities in a process may not appear in its model. Thus, we define a set of modeled activities over the set of all activities Aas AM⊆A. A process model is a (possibly infinite) set of complete activity sequences M⊆AM∗, i.e., executions from the initial state to some final state. Consider for example the precise model (P) in Figure 1. Assuming that the end state is reached when the “end” place contains exactly one token, the model is formalized by the finite set {ha, b, c, di,ha, c, b, ei,ha,f,g,hi,ha, b, i, b, c, di}. Note that the set of modeled activities and the set of logged activities may be disjoint, i.e., AM∩ALcan be the empty set. We consider activities that appear in event logs but not modeled in process models as activities that are allowed to occur anytime. Furthermore, modeled activities in process models that never occur in event logs are considered as unlogged activities. Thus, their absence in the logs is not counted as violations to the models. 3 Cost-Optimal Alignment An alignment between an event log and a process model relates the occurrences of activities in the log to the execution steps of the model. As the execution of a case is often performed independently of the execution of another case, aligning is performed on the basis of traces. For each trace in an event log that fits a process model, each “move” in the trace (i.e., an event observed in the log) can be mimicked by a “move” in the model (i.e., an action executed in the model). However, this is not the case if the trace does not fit the model perfectly. We use the symbol to denote “no move” in either the log or the model. Hence, we introduce the set A L=AL∪ {} where any x∈A Lrefers to a “move in log” and the set A M=AM∪ {} where any y∈A Mrefers to a “move in model”. Formally, amove is represented by a pair (x, y)∈A L×A Msuch that: –(x, y) is a move in log if x∈ALand y=, –(x, y) is a move in model if x=and y∈AM, –(x, y) is a synchronous move/move in both if x∈AL,y∈AM, and x=y, –(x, y) is a illegal move in all other cases. Measuring Precision of Modeled Behavior 5 Examination Radiology Therapy Update record Allergy test Chemotherapy Post-chemo Home care Operation p0 p1 p3 p2 p4 p5 p6 p7 ab c d e i fgh Fig. 2: Process model that is neither overfitting nor imprecise for the log in Figure 1. γ1=ab d e a c b eγ2=a b d e a b c eγ3=ab d e a c b d  γ4=a b d e a b c d γ5=a b d e a b c e γ6=a   b d e a f g h  Fig. 3: Some alignments between trace σL=ha, b, d, eiand the model in Figure 2. We use ALM to denote the set of all pairs of legal moves, i.e., all possible pairs of move in log, move in model, and move in both. Along this section, let Lbe a log over AL, let σL∈Lbe a trace, and let M be a model. An alignment between σLand Mis a sequence γ∈ALM ∗where the projection of the first element (ignoring ) yields σL(i.e., π1(γ)↓AL=σL) and projection of the second element (ignoring ) yields a complete sequence of M(i.e., π2(γ)↓AM∈M). Take for example an unfitting trace σL=ha, b, d, eiand the model in Figure 2. Assuming that the end state of the model is reached when place p5in the model contains exactly one token, the model has an infinite set of complete activity sequences (i.e., {ha, b, c, di,ha, c, b, di,ha, b, c, ei,ha, c, b, ei,ha,f,g,hi, ha, b, i, c, b, ei, . . .}). Some possible alignments between σLand the model are shown in Figure 3. The moves are represented vertically in Figure 3, e.g., the second move of γ1is (, c), indicating that the model moves cwhile the log does not make any move. Note that the projection of an alignment between a trace and a model to all of its movements on model yields a complete activity sequence allowed by the model. This property is not always ensured by other conformance checking approaches. For example, given a trace and a process model, when using the approach in [30], the so-called “missing tokens” are added to allow the activities that occur in the trace but not supposed to occur according to the model. The addition of such missing tokens introduces extra behavior that is not allowed in the original process model. To measure the cost of an alignment, we define a distance function δ: ALM →IN where for all (aL, aM)∈ALM , δ((aL, aM)) = 0 if aL=aM 6 Adriansyah, Munoz-Gama, Carmona, van Dongen and van der Aalst and δ(aL, aM) = 1 otherwise.2The distance function can be generalized to alignments γ∈ALM ∗by taking the sum of the costs of all individual moves: δ(γ) = P(aL,aM)∈γδ((aL, aM)). Using this function, the cost of alignment γ1 is δ(γ1) = δ((a, a))+δ((, c))+δ((b, b))+δ((d, ))+δ((e, e)) = 0+1+0+1+0 = 2. Note that the function returns the number of mismatches in the alignment. Given a trace from an event log and a process model, we are interested in an activity sequence from the model that is similar to the trace. Therefore, we define the set of alignments ΓσL,M ={γ∈ALM ∗|γis an alignment between σLand M}to be all possible alignments between σLand M. Accordingly, we define the set of optimal alignments as the set of all alignments with minimum cost, i.e., Γo σL,M ={γ∈ΓσL,M | ∀γ0∈ΓσL,M δ(γ)≤δ(γ0)}. It is easy to see that there can be more than one optimal alignment between a trace and a model. For example, {γ1, γ2, γ3, γ4, γ5}is the set of optimal alignments between the trace σL=ha, b, d, eiand the model in Figure 2. For all alignments γ∈ALM ∗,¯ λM(γ) = π2(γ)↓AMdenotes the projection of γto modeled activities. By definition, the bottom part of all alignments yields a complete activity sequence of the model. Thus, given an optimal alignment γbetween σLand M, the projection ¯ λM(γ) provides an activity sequence that both perfectly fits Mand closest to σL. In the example shown in Figure 2, ¯ λM(γ1) = ha, c, b, eiis one of the complete activity sequences of Mthat is most similar to trace ha, b, d, ei. Given a log and a model, constructing all optimal alignments between all traces in the log and the model is computationally expensive [7,8]. Thus, computing all optimal alignments between traces and process models with real-life complexity may not always be feasible in practice. Thus, instead of computing all optimal alignments between traces in the log and the model to obtain insights into deviations, one may also compute just some representative optimal alignments for each trace. In this paper, we investigate both approaches. We define three functions that provide optimal alignments between traces in the log and the model: –Λ∗ M:A∗ L→ P(ALM ∗) returns all optimal alignments between traces of L and M, such that for all σL∈L, Λ∗ M(σL) = Γo σL,M , –Λ1 M:A∗ L→ALM ∗returns one optimal alignment between traces of Land M, such that for all σL∈L, Λ1 M(σL)∈Γo σL,M , and –ΛR M:A∗ L→ P(ALM ∗) returns representatives of optimal alignments between traces of Land M, such that for all σL∈L, ΛR M(σL)⊆Γo σL,M . In [7, 8, 10] various approaches to obtain an optimal alignment between a trace and a model with respect to different cost functions are investigated. Given a trace σLof Land a model M, if there are multiple optimal alignments, Λ1 Mchooses one of them according to other external criteria. With our previous example, suppose that Λ1 Mselects an alignment that has the longest consecutive occurrence of synchronous moves in the beginning, Λ1 M(σL) = γ4. 2The distance function can be user-defined, but for simplicity we use a default distance function that assigns unit costs to moves in log/model only. Measuring Precision of Modeled Behavior 7 In [7,8], an A?-based algorithm is proposed to compute one optimal alignment between a trace and a model. The same algorithm can be extended to provide more than one optimal alignment between them. Given a trace σLof Land a model M, the algorithm constructs one optimal alignment by computing a shortest path from the initial to the final state of the state space of the synchronous product between σLand M. It is shown in [8] that all shortest paths from the initial to the final state of the state space yields an optimal alignment. For each state in the state space, the algorithm records a shortest path from the initial state to reach this state and thus, becomes the representative of all other shortest paths from the initial state to the state. An optimal alignment is constructed from a shortest path from the initial state to the final state that is also representing all other shortest paths that connect the same pair of states. By recording all represented shortest paths during state space exploration for each state, we can obtain all shortest paths from the initial to the final state of the state space (i.e., obtain all optimal alignments). Furthermore, we can form groups of all shortest paths from the initial to the final state according to some criteria and take one representative path for each group. This way, we can get a number of representatives of all shortest paths between one up to the total number of all shortest paths from the initial to the final state. There are many possible ways of grouping shortest paths (i.e., grouping optimal alignments). One possibility is to group them based on their sub-path similarity (i.e., the followed sub-path in the state space). For example, one may group them based on the last step taken in the paths before they reach the final state. Such a grouping can be easily performed without much extra computation using the constructed state space. Moreover, this way of grouping allows computation of the exact number of represented optimal alignments for each representative by iterating through the state space. The interested reader is referred to [7,8] for details on the constructed state space with the A?-based algorithm approach. Note that to minimize the number of states that need to be explored, some optimizations can be performed to avoid visiting “similar” states more than once (e.g., pruning, prioritization of states [22, 32]). In such cases, the constructed state space may be pruned. Thus, the number of represented shortest paths computed using the approach proposed before may only provide a lower bound to the actual number of represented shortest paths. Given a set of representatives of all optimal alignments, each representative may represent a different number of optimal alignments. For all representatives γ∈ΛR M(σL), repM(γ) denotes the number of optimal alignments represented by γ. Furthermore, due to possible pruning of state space, for all γ1, γ2∈ΛR M(σL) : Pγ0∈ΛR M(σL)repM(γ0)≤ |Γo σL,M |, i.e., the total number of represented optimal alignments by the representatives is a lower bound of the total number of all optimal alignments. Take for example a trace σL=hai. All optimal alignments between the trace and the model in Figure 2 are shown in Figure 4. Suppose that we define function ΛRaccording to the extension to the A?algorithm we described before, ΛR(σL) = {γ7, γ9, γ10}where repM(γ7) = 1 (γ7represents 8 Adriansyah, Munoz-Gama, Carmona, van Dongen and van der Aalst γ7=a a f g h γ8=a a b c d γ9=a a c b d γ10 =a   a c b e γ11 =a a b c e Fig. 4: All optimal alignments between trace σL=haiand the model in Figure 2. {γ7}), rep(γ9) = 2 (γ9represents {γ8, γ9}), and rep(γ10) = 2 (γ10 represents {γ10, γ11}). In this example, ¯ λ(γ7),¯ λ(γ9),¯ λ(γ10) are ha,f,g,hi,ha, c, b, di, and ha, c, b, eirespectively. For simplicity, in the remainder we omit the model notation Min functions Λ∗ M, Λ1 M, ΛR M,¯ λM, and repMif the context is clear. Note that in cases where a process model has duplicate tasks (more than one task to represent an activity) or invisible tasks (tasks whose execution are not logged), approaches to construct alignments (e.g., [7,10]) keep the mapping from all model moves to the tasks they correspond to. Hence, given an alignment of a trace and such models, we know exactly which task is executed for each model move. We refer to [7,10] for further details on how such mapping is constructed. 4 Computing Precision Given an event log and a model, the technique described in the previous section provides a set of optimal alignments for each trace in the log. This section presents a technique to compute precision based on the use of these optimal alignments per trace. The technique considers ’one’ or ’all’ optimal alignments, and is based on the methods described in [24–26]. However, there is a fundamental difference: whereas in [24–26] precision is measured based on log-based model replay, the approach in this section is based on alignments [9]. The advantages are manifold. First of all, traces in the log do not need to be completely fitting. In [24–26] the non-fitting parts are simply ignored. For most real-life situations, this implies that only a fraction of the event log can be used for computing precision. Second, the existence of indeterminism in the model poses no problems when using the alignments. In [24–26], ad-hoc heuristics were used to deal with indeterminism. Finally, the use of alignments instead of log-based model replay improves the robustness of conformance checking. The remainder of this section is devoted to explain how precision can be calculated from the alignments. Precision is estimated by confronting model and log behavior: imprecisions between the model and the log (i.e., situations where the model allows more behavior than the one reflected in the log) are detected by juxtaposing behavior allowed by the log and the one allowed by the model. This juxtaposition is done in terms of an automaton: first, an automaton is built from the alignments. Then, the automaton is enhanced with behavioral information of the model. Finally, the enhanced automaton is used to compute the precision. In the Measuring Precision of Modeled Behavior 9 L trace freq ¯ λ(Λ1)L¯ λ(Λ∗)L σ1=hai1ha, f, g, hi ha, f, g, hi ha, c, b, ei ha, c, b, di ha, b, c, di ha, b, c, ei σ2=ha, b, c, di1ha, b, c, di ha, b, c, di σ3=ha, c, b, ei1ha, c, b, ei ha, c, b, ei σ4=ha, f, g, hi1ha, f, g, hi ha, f, g, hi σ5=ha, b, i, b, c, di1ha, b, i, b, c, di ha, b, i, b, c, di Table 1: Model perspective of the alignments (’one’ and ’all’) for the model in Figure 2 and the log [σ1, σ2, σ3, σ4, σ5]. remainder of the section we will use the following running example: the model shown in Figure 2 and the log L= [σ1, σ2, σ3, σ4, σ5], containing the 5 traces that appear in in Table 1. In order to build the automaton, log behavior must be determined in terms of model perspective, i.e., we consider the optimal alignments (Λ1or Λ∗) of each trace in the log for this purpose. For example, given the running example log L= [σ1, σ2, σ3, σ4, σ5] and the model in Figure 2, the trace σ1has 5 optimal alignments, Λ∗(σ1) = {γ7, γ8, γ9, γ10, γ11}, shown in Figure 4. For this example, we assume that the alignment assigned to σ1by Λ1based on an external criterion corresponds to γ7, i.e., Λ1(σ1) = γ7. On the other hand, traces σ2. . . σ5are perfectly fitting, and therefore, each trace has only one optimal alignment containing only synchronous moves. In particular, given an alignment γ, in order to build the automaton, we only consider the projection of model moves, i.e., ¯ λ(γ). Table 1 shows all the projection of model moves for the alignments of log L= [σ1, σ2, σ3, σ4, σ5]. We use ¯ λ(Λ1)Land ¯ λ(Λ∗)L to denote the application of function ¯ λon all the alignments provided by the functions Λ1and Λ∗respectively for the traces in log L. We can omit the subindex Lwhenever the context is clear. Note that, by definition, any alignment projection ¯ λ(γ) is a valid complete activity sequence of the model. Using Λ1(or Λ∗), the automaton is built considering all the prefixes for the sequences in ¯ λ(Λ1) (or ¯ λ(Λ∗)) as the states. For instance, given a sequence ha, b, c, diresulting of ¯ λ(Λ1)(σ2), the states considered are ,hai,ha, bi,ha, b, ci and ha, b, c, di. Formally, the alignment automaton AA= (Q, Σ, δ, , ω) is defined such that: –The set of states Qcorresponds to all prefixes. –The set of labels Σcorresponds to the activities. –The arcs δ:Q×Σ→Qdefine the concatenation between prefixes and activities, e.g., states ha, b, ciand ha, b, c, diare connected by arc labeled d. –The state corresponding with the empty sequence is the initial state. –The function ω:Q→IR determines the weight of each state according to its importance for the precision computation. 16 Adriansyah, Munoz-Gama, Carmona, van Dongen and van der Aalst Examination Radiology Therapy Update record Allergy test Chemotherapy Post-chemo Home care Operation p0 p1 p3 p2 p4 p5 p6 p7 ab c d e i fgh Representatives Process Model Fig. 10: Process model, traces, and representatives of all optimal alignments of all traces. a ac ab af acb abc afg abi acbd afgh abib abcd acbe abibc abibcd 2 f c i e i i i 551.8 1.8 1.4 0.4 1 1 1 1 1 1 1.2 1.2 1.2 ac b fgh b d e d c ibcd e LEGEND Imprecision State <label> Fig. 11: Automaton using ΛR(ordered state representation) and the model of Figure 2. Mbe a model, and let γ∈ΛR(σL) be a representative alignment for trace σL. In such case, the weight of the alignment ω(γ) needs to be proportional to the number of alignments represented by γ, i.e., rep(γ). Thus, we define ω(γ) = L(σL)·rep(γ)/Pγ0∈ΛR(σL)rep(γ0). For instance, given the trace σ1in Figure 10, let γ1be the representative alignment such that ¯ λ(γ1) = ha, c, b, di. The number of alignments represented by γ1is rep(γ1) = 2. The total number of optimal alignments represented by the representative alignments associated with σ1is Pγ0∈ΛR(σ1)rep(γ0) = 5. Hence, the weight ω(γ1)=1·2/5 = 0.4. As another example in Figure 10, let γ2be the only representative alignment associated with σ5, such that ¯ λ(γ2) = ha, b, i, b, c, di. The representative alignment γ2represents 1 optimal alignment. Since the number of all optimal alignments represented is Pγ0∈ΛR(σ5)rep(γ0) = 1, the weight of γ2is ω(γ2)=1·1/1 = 1. Figures 11 and 12 reflect the automata for the running example of the previous section, when representative alignments and different state representations are used. Note that there can be more than one ways to compute representative alignments from a given model and a trace. Given an event log and a model, the selection of representative alignments between each trace in the log and the model obviously influences the automata that can be constructed between the log and the model. Measuring Precision of Modeled Behavior 17 [a] [a,c] [a,b] [a,f] [a,b,c] [a,f,g] [a,b,i] [a,f,g,h] [a,b 2 ,i] [a,b,c,e] [a,b 2 ,i,c] [a,b 2 ,i,c,d] 2 f c i e i i 55 1.8 2.8 1.4 111 1 1.2 1.2 1.2 ac b fgh b e c ibcd [a,b,c,d] d 1.4 LEGEND Imprecision State <label> Fig. 12: Automaton using ΛR(unordered state representation) and the model of Figure 2. 5.3 Forward and Backward Precision In the approach presented in Section 4, the prefixes of the complete activity sequences are used to build the automaton. For example, given a complete activity sequence ha, b, c, di, the states constructed from the sequence are the empty sequence (corresponding with h•a, b, c, di, where •indicates a point of interest in the sequence), hai(for ha•b, c, di), ha, bi(for ha, b •c, di), ha, b, ci (for ha, b, c •di) and finally ha, b, c, di(for ha, b, c, d•i). In other words, only the activities in the past are used and we move forward on the complete activity sequences. This approach is used by all existing precision checking techniques [24–26]. In [6], the authors show that any point in the sequence (represented as •) may represent two complementary visions: the past activities seen until that point (as it has been shown above), but also the future activities to come until the ending of the case. For instance, given ha, b •c, di,ha, biare the activities occurred, while hc, diare the activities to happen. Both ha, bi and hc, diare used in [6] as two different states that can be derived from the same point in the sequence. In this section, we use the same idea to present abackward precision measurement, that complements the forward approach presented before. The combination of both metrics will lead to a measurement unbiased by the direction of the precision checking. For the sake of clarity we will use ordered state representation to illustrate the remainder of the section, although the analogous procedure is applicable for unordered representation. Let Λbe the option chosen to compute precision, i.e., Λ1,Λ∗or ΛR. In order to build the automaton for the backward precision measurement, we consider the prefixes of the reversed complete activity sequences in ¯ λ(Λ). In other words, given ¯ λ(γ) = ha, b, c, diof the alignment γ∈Λ, we use ¯ λ0(γ) = hd, c, b, aito determine the states, resulting in the following 5 states: (corresponding with h•d, c, b, ai), hdi(for hd•c, b, ai), hd, ci(for hd, c •b, ai), hd, c, bi(for hd, c, b • ai) and finally hd, c, b, ai(for hd, c, b, a•i). Analogously, the set of complete activity sequences of Mis also reversed.4The rest of the precision checking is performed as it is described in Section 4. 4Notice that, for the case of Petri nets with one unique initial and final markings, the set of all reversed complete activity sequences can be generated by simulating the behavior of a net obtained from the original net by reversing its arcs and swapping their initial with final marking. 18 Adriansyah, Munoz-Gama, Carmona, van Dongen and van der Aalst d dc dcb b a 1 1 1 1 cbdcba 1 a a b d a ab abc b c a b 1 1 1 1 abc abcd 1 d a c a b cd Model and Automaton Reversed Model and Automaton start end a b cd start end Fig. 13: Example of model and resulting automaton for both forward and backwards approaches. Figure 13 shows an example of two automata constructed by moving in forward direction (left) and by moving backward (right). Notice the difference of identified imprecisions shown by the two automata. Finally, precision values obtained using forward and backward-constructed automaton can be combined (e.g., the average), resulting in a balanced precision metric unbiased by the direction of the automaton constructed. Note that more sophisticated and flexible combinations of both metrics are also possible. In Section 6, we investigate the differences in precision values produced by the various approaches using a variety of even logs and models. 6 Experiments We have implemented the proposed precision calculation as a ProM 6 plugin named “Check Precision based on Align-ETConformance” in the “ETConformance” package, publicly available from www.processmining.org. We used it to perform a range of experiments to test the robustness of our proposed approach using both synthetic and real-life models (Petri nets) and logs. 6.1 Evaluating Unidimensionality of Metrics The first set of experiments was performed to evaluate the precision measurements provided by the proposed metrics. In particular, we measured whether the proposed precision metrics are unidimensional [33], i.e., not sensitive to non-fittingness of event logs. We measured precision between various logs and models whose expected values are known. Furthermore, we compared the values obtained against existing state-of-the-art metrics for precision: etcP[24], behavioral precision [34], and weighted behavioral precision [12]. By combining the models and log in Figure 1 in various ways, we created new models whose expected precision values are between the two extremes. Two models were combined by merging the end place of one with the initially marked place of another. The merged models were named according to the name of their original models, e.g., PF model is the result of merging the end place of Pwith the initially marked place of F. The activity names in the original models and logs were renamed before the models and logs were Measuring Precision of Modeled Behavior 19 Fig. 14: Precision values of the logs/models in Figure 1 and their combinations provided by alignment-based approach (i.e., computed using all optimal alignments, ordered, and forward-constructed automata). If all behavior are observed in the original logs, all measurements are insensitive to non-fitting traces. merged such that the original models and logs can be easily distinguished from the merged results. Precision values were measured 30 times using 30 event logs, each consists of 5,000 traces, generated by simulating the precise model (i.e., PP). For sake of completeness, we also measured the precision of the overfitting model (P) and the flower model (F) using 30 logs of 5,000 traces generated by simulating the Pmodel. This way, each log contains all the possible behavior of the model that generates it (i.e., all directly follow relations between two activities that are allowed according to the model are recorded in the log). The top part of Figure 14 shows the alignment-based precision values, measured using all optimal alignments per trace of the logs. The experiment with one and representative alignments per trace yields identical results. This result shows that by observing sufficiently enough behavior in the event logs, all alignment-based metrics provide similar intuition about precision of models, i.e., overfitting models have high precision values and “flower” models have low precision values. Note that there are slight differences between various configurations of metrics, i.e., states (ordered/unordered) and forward/backward constructed automata. To evaluate the robustness of the metrics against non-fitting logs, we took the models and logs from the previous experiments and created unfitting logs by removing nrandom events per trace from the fitting logs. To ensure that the logs are unfitting, only activities that belong to the precise part (i.e., mapped to Ppart) are removed. Furthermore, the measurements are compared against existing metrics. We use the CoBeFra tool [13] to measure behavioral precision [34] and weighted behavioral precision [12]) and use ProM 6 to measure etcP. The bottom part of Figure 14, Figures 15–16, and Table 2 show some of the results. 20 Adriansyah, Munoz-Gama, Carmona, van Dongen and van der Aalst Fig. 15: Comparison between precision values obtained using alignment-based approach (i.e., computed using all optimal alignments, ordered, and forward-constructed automata) and other metrics (etcP[24], behavioral precision [34], and weighted behavioral precision [12]). Only the alignment-based approach is not sensitive to non-fitting logs/models. The bottom part of Figure 14 shows that the metrics proposed in this paper are robust to fitness problems. Even in cases where almost half of the events in all traces are removed, all alignment-based metrics provide similar value as the ones provided for perfectly fitting traces. Figure 15 shows a comparison between the precision values provided by alignment-based metrics and other existing metrics. For readability, we only show one alignment-based metric: the one computed using all-optimal alignments and forward-constructed automata whose states are constructed by taking into account activity ordering. Note that in cases where logs are perfectly fitting the models, all metrics provide similar precision intuition. In fact, the alignment-based precision values shown in Figure 15 are the same as the etcPvalues. However, in cases where logs are non-fitting, other metrics may show misleading precision insights. The etcP metric provides low precision for model PF with respect to perfectly fitting logs (i.e., 0.25). However, the value rises to 0.82 when 3 events are removed from the logs, because for all non-fitting traces it ignores the rest of the traces after the first non-fitting event occur. Similarly, both weighted and unweighted behavioral precision metrics provide lower precision values for non-fitting logs than the ones provided for perfectly fitting logs. Even for overly fitting models Pand PP, both metrics provide precision values below half (i.e., indicating the models are imprecise). This occurs because both metrics mixed both perfectlyfitting and non-fitting traces in construction of artificial negative events, which leads to misleading construction of artificial negative events. Figure 16 shows the influence of noise by removing some events in the logs. As shown in the figure, other than the alignment-based precision metric, precision values of all metrics may change significantly even with only one event removed from all traces. Due to the randomness of the location of removed events, the etcPmetric may both increases or decreases with the presence of non-fitting traces. Both weighted and unweighted behavioral precision metrics decreases when more events are removed because incorrect artificial negative events are introduced. Note that the number of negative events tends to decrease when traces in the log gets more vary because of the removal of events. The set of experiments also shows some interesting insights into differences between alignment-based metrics. Table 2 reports the results for model PF. In Measuring Precision of Modeled Behavior 21 Fig. 16: Precision values of different metrics for perfectly fitting logs and non-fitting logs created by removing some events in the logs. Only the alignment-based approach metric (i.e., computed using all optimal alignments, ordered, and forward-constructed automata) is insensitive to non-fitting logs. Table 2: Precision values of the PF model, measured using different state representations (ordered/unordered) and direction (forward/backward). If all behavior are observed, both 1-alignment and representative alignment provide good approximation of all-alignments. Automata Construction Direction Forward Backward Combined #Removed 0 1 2 3 0 1 2 3 0 1 2 3 Ord. one 0.25 0.24 0.24 0.24 0.19 0.19 0.19 0.18 0.22 0.22 0.21 0.21 rep 0.25 0.25 0.24 0.24 0.19 0.19 0.19 0.19 0.22 0.22 0.22 0.21 all 0.25 0.25 0.24 0.24 0.19 0.19 0.19 0.19 0.22 0.22 0.22 0.21 Unord. one 0.26 0.25 0.25 0.25 0.19 0.19 0.19 0.18 0.22 0.22 0.22 0.22 rep 0.26 0.26 0.25 0.25 0.19 0.19 0.19 0.19 0.22 0.22 0.22 0.22 all 0.26 0.25 0.25 0.25 0.19 0.19 0.19 0.19 0.22 0.22 0.22 0.22 LEGEND Ord./Unord : ordered/unordered state representations One/rep/all : one/representative/all alignments cases where the whole behavior is recorded in event logs, precision values only depend on the state representation of the automaton (ordered/non-ordered) and the direction for the automata construction. When all possible behavior are observed, the automata constructed using 1-alignment and all-alignments per trace are identical. Similar results are obtained from the experiments using the other models (P,F,FP,PP,FF). Table 2 shows slight differences between precision values that are measured using different state representations or different directions in the automata construction. Figure 17 shows a comparison between precision values provided by the two metrics for models PF and FP. As shown in the figure, precision values of alignment-based metrics provided by forward-constructed automata for model PF is higher than the values provided by backward-constructed automata for the same model, regardless of the noise level and the state representation (ordered/unordered). In contrast, the values provided by the latter is higher than the former for the FP model. This shows that the position of the precise part of the models influences precision values. Precision values are higher when the direction of constructed automata starts with precise part of process models. In this case, we clearly see the influence of forward/backward direction of constructed automata to precision values. To balance the influence, one of the simplest way is to take the average between the values provided by both 22 Adriansyah, Munoz-Gama, Carmona, van Dongen and van der Aalst Fig. 17: Precision values of the PF and FP using all-alignments per trace, with different state representations (ordered/non-ordered) and direction (forward/backward). Higher precision is obtained when the direction of automata construction starts with precise part of the models. a1 a2 an ... b1 b2 bn ... start end (i) (ii) “Parallel” model“Choice” model Fig. 18: (i) A model that only allows one activity per trace, and (ii) A model that allows interleaving between all activities. directions. Figure 17 shows that the precision values obtained by combining both values are almost similar between model PF and FP. In this section, non-fitting logs are created by removing activities randomly. Given a process model and a fitting trace, there are other ways to make the trace non-fitting, such as swapping some activities and add extra activities to the trace randomly. Regardless of the approach to introduce noise, an optimal alignment between a non-fitting trace and the model provides a good “guess” of a complete activity sequences allowed by the model that should have occurred instead of the trace. This way, precision is measured independently from other conformance metrics, i.e., the fitness metric. Other approaches investigated in this section do not explicitly handle such non-fittingness. Hence, they are not unidimensional and may yield misleading results as shown by the experiment results. 6.2 Observed Behavior Requirements The second set of experiments were conducted to investigate how much behavior must be observed in the event logs in order to measure perfect precision accurately. We use two models that, despite having the same number of activities, have totally different number of complete activity sequences. The first model only allows choice among activities (i.e., is named “Choice” model) and the second model allows the interleaving of all activities (i.e., is named “Parallel” model) (see Figure 18). For our experiments, we used models that consist of 9 activities (with invisible task “start” and “end” for the “Parallel” model). Measuring Precision of Modeled Behavior 23 Fig. 19: Alignment-based precision values for “Parallel”,“Choice”,“Parallel- Parallel”, and “Choice-Choice” models. The values provided using unordered representation of states automata provide perfect precision without having to observe all interleaving behavior. Missing values on weighted/unweighted behavioral precision indicate that no result was obtained after 1 hour computation. Similar to the set of experiments in Section 6.1, we randomly generated perfectly fitting logs for both models with various number of traces per log and then measured their precision values. Experiments are repeated 30 times for each combination of models and number of traces per log. We conducted the same experiments with models constructed by merging the two models in various order (“Choice-Choice”,“Choice-Parallel”,“Parallel-Choice”, “Parallel-Parallel”). The results of the experiments are shown in Figure 19 and Figure 20. Both Figure 19 and Figure 20 reveal that even if logs are generated from models, all alignment-metrics require some degree of log completeness before they provide perfect precision value of 1.00. As expected, a perfect precision value for a “Choice” and a “Choice-Choice” models can be obtained after observing much fewer traces than the ones required to obtain the same precision value for both “Parallel” and “Parallel-Parallel” models. In theory, the minimum number of traces in an event log required to see all possible behavior of a “Choice” model with 9 activities is 9, while the minimum number of traces to see all possible interleaving of activities in a “Parallel” model is 9! = 362,880 traces. In all experiments, alignment-based precision metrics with unordered automata state representation provide perfect precision values with less number of observed traces than the one with ordered automata. This shows that in conditions where not all behavior are observed in event logs, precision values computed using unordered automata state representation provides an upper-bound for the ones computed using ordered automata. The figure also shows that in all experiments, the etcPvalues are the same as the alignment-based precision values computed using ordered automata state representation because all traces perfectly fit their models. Interestingly, in the experiments with model “Choice” and “Choice-Choice”, both the weighted and unweighted behavioral precision metrics provide a perfect value (1.00) for logs with only one trace but provide very low values (below 0.2) for other logs that contain more than one trace (i.e., logs with 10, 100, 1,000, to 5,000 traces). The reason the (un)weighted behavioral precision values is so high is that the artificial negative events construction only take into account logged activities. When an activity in a trace of the logs is replayed to construct ar- 24 Adriansyah, Munoz-Gama, Carmona, van Dongen and van der Aalst Fig. 20: Precision values of models with combination of choice and parallel control-flow patterns. Higher precision values are obtained when automata are constructed from the direction where the parallel part of the models exists (the first three figures). Missing values indicate that no result was obtained after 1 hour computation. tificial negative events, other than the logged activity both models allow only unlogged activities (invisible tasks). Thus, no negative artificial events were constructed and therefore the precision of the models with respect to the logs are 1.00. Furthermore, the results also show that the time spent to compute alignment-based metrics is not necessarily higher than the time required to compute other existing metrics such as the (un)weighted behavioral precision. In some of the experiments with models “Parallel” and “Parallel-Parallel”, no result was obtained after 1 hour computation for (un)weighted behavioral precision while the alignment-based precision metrics were computed in less than 1 minute for each pair of model and log. Figure 20 shows the precision values obtained from experiments with models “Choice-Parallel” and “Parallel-Choice”. Interestingly, the results of the experiment with “Choice-Parallel” model performed using forward automata construction (i.e., top-left-most of Figure 20) is identical to the one given by the experiment with “Parallel-Choice” model using backward automata construction (bottom-second from left of Figure 20). Similarly, the results of experiment with “Parallel-Choice” model performed using forward automata construction (i.e., bottom-left of Figure 20) is identical to the one given by the experiment with “Choice-Parallel” model using backward automata construction (top-second from left of Figure 20). These results show that precision values are influenced by the location of parallelchoice constructs: precision values are higher when automata are constructed from the direction where parallel construction lies. The combined precision value computed by averaging the precision values obtained from both forward and backward-constructed automata is less influenced by such construction as shown in the third figures from the left side of Figure 20. As shown in the figures, the measured precision values for both “Choice-Parallel” and Measuring Precision of Modeled Behavior 25 Table 3: Real-life logs and models used for experiments Log #Cases #Events Process Model #Deviation/trace #Place #Trans Bouw-1 139 3,364 33 34 9.75 Bouw-4 109 2,331 31 31 7.27 MLog1 3,181 20,491 15 12 5.33 MLog2 1,861 15,708 16 19 1.45 MLog3 10,271 85,548 24 21 14.50 MLog4 4,852 29,737 16 27 2.09 MLog5 25,846 141,755 14 24 1.21 IsalaLog 77 459 26 39 0.68 Fig. 21: Precision values of real-life logs and models. Only the 1-alignment approach manages to provide precision results for all logs/models. “Parallel-Choice” models using the combined precision values are identical. None of non-alignment-based approaches in this set of experiments managed to provide perfect precision values. Note that no result was obtained after 1 hour of computation for both weighted and unweighted behavioral precision metric calculations and logs of size of 1,000 traces and larger. 6.3 Real-life Logs and Models To evaluate the applicability of the approach to handle real life logs, we used 8 pairs of process models and logs from two different domains (see Table 3), where 7 logs and models were obtained from municipalities in the Netherlands. In particular, we took the collections of logs and models from the CoSeLoG project [1,15]. The remaining pair of log and model is obtained from a hospital in the Netherlands5. The logs and models from municipalities are related to different types of building permission applications, while the hospital log is related to patient handling procedure. All processes have unlogged tasks, and some of the models allow loops. Table 3 shows an overview of the logs and models used in the experiments. #Deviations/trace column indicates the number of asynchronous moves after aligning all traces in the logs with their corresponding models. As shown in Table 3, all logs are not perfectly fitting to the corresponding models. We measure the precision values for all logs and the computation time required. The results are shown in Figure 21 and Figure 22. 5see http://www.healthcare-analytics-process-mining.org/