mopdf.com

Process mining using BPMN: relating event logs and process modelsFig. 2 A BPMN model obtained by a conversion from the Petri netFig. 1 A Petri net constructed from the logadditional event properties, such as costs and resources (participants of the process); in this example, they are representedby prices and clients ip addresses.To discover a control flow, an event log is represented asa multiset of traces, each of which is a sequence of events,corresponding to a concrete case identifier: L book f light, get insurance, book hotel, pay, con f ir m 5 , book f light, book hotel, get insurance, pay, con f ir m 4 , book hotel, book f light, get insurance, pay, con f ir m 4 , book hotel, get insurance, book f light, pay, con f ir m 3 , get insurance, book hotel, book f light, pay, con f ir m 1 , get insurance, book f light, book hotel, pay, con f ir m 1 .A Petri net discovered from L by the Alpha mining algorithm [12] is presented in Fig. 1.With the help of a conversion algorithm, we construct aBPMN model from the Petri net, as shown in Fig. 2. ThisBPMN model is more compact than the initial Petri net. Thus,the result of process mining is available in a BPMN notationnow; this BPMN model can be easily imported and executedby any of BPM tools mentioned above.In order to estimate the advantages of using the BPMNnotation for mining, we additionally compare the complexityof the models produced by the existing control flow discoveryalgorithms and the complexity of the corresponding BPMNmodels. We use the various metrics, such as the numberof nodes, density and diameter for this evaluation. Correlations between the process metrics and the quality of processmodels are discussed in [13–16]. We present not only theoretical but also practical evaluations based on real-life eventlogs. Moreover, applied to these event logs, the metrics ofthe discovered BPMN models are compared to the metricsof the models designed manually with a BPMN-editor. Thishelps us to understand structural differences between models,which are created by process analysts and models discoveredfrom event logs.Since not only discovery but also conformance checkingand process enhancement are essential steps in process mining, this paper also shows how to enable them for BPMNmodels. A BPMN model is converted to a Petri net, and thenreplay techniques are applied [17] to retrieve performanceand conformance information. This information is used toenhance BPMN models. Theoretical observations presentedin this paper help us to relate states of a BPMN model withthe states of a corresponding Petri net. Thus, both conformance and performance information obtained for a Petri netcan be visualized using the initial BPMN model.A general scheme of using BPMN for process mining ispresented in Fig. 3. The user discovers a BPMN model byapplying discovery and BPMN conversions plugins. To showperformance and conformance information and to annotatethe BPMN diagram, the BPMN model is converted to a Petrinet, such that replay techniques can be used.The paper is organized as follows. Section 2 overviewsrelated work. Section 3 introduces basic definitions andnotions, including traces, Petri nets, system nets, (weak)Fig. 3 A general scheme of using BPMN for process mining123

A. A. Kalenkova et al.simulation and (weak) bisimulation relations. In Sect. 4,we propose algorithms for conversion from well-known formalisms such as Petri nets to BPMN and prove correctnessof these conversions. In Sect. 5, transformations of causalnets and process trees to BPMN are introduced. Section 6contains a set of BPMN simplification rules. In Sect. 7, atechnique for conformance checking and performance analysis on the basis of BPMN models is presented. A tool, whichimplements the proposed conversion and enhancement techniques, is presented in Sect. 8. Section 9 includes a case study,which shows the results of an application of the algorithmspresented in the paper to real-life event logs. Also the structural business-processes metrics are calculated and presentedin this section. Section 10 concludes the paper.2 Related workThis section surveys previous work on Petri net and workflowgraph conversions and includes an overview of existing discovery and conformance checking techniques dealing with“high-level” process models (e.g., BPMN models and models presented not only by the control flow, but also includingdata and resource perspectives as well).Algorithms for conversion of free-choice workflow nets[18] (a special subset of Petri nets) to workflow graphs (generalization concept for process modeling notations such asBPMN, UML Activity [19], EPC [20,21], etc) were proposedin [22,23]. In our paper, we will deal with arbitrary Petri netsstructures and arbitrary safe initial markings. Moreover, incontrast to the approaches proposed before [22,23], we provethat the target model will simulate (i.e., will be able to mimic)the behavior of the initial net and vice versa. These simulation relations give the possibility to prove important (in thecontext of process mining) propositions on the language relations. Another key result is that having simulation relationsbetween initial and target models allows us to project variousanalysis data (such conformance and performance information) obtained for one model to another.An approach for constructing BPMN models containingsubprocesses was presented in [24]. In contrast to our paper,this technique is mainly focused on deriving subprocessesfrom event logs. We present basic robust conversion algorithms, which help to construct flat control flow skeletons ofthe target BPMN models from the discovered Petri nets andother low-level models. We hope that our approach can be further used as a basis for discovering more advanced constructs.As [24] our approach is generic and can work with multiple discovery algorithms (such as [12,25,26]) in the processmining context. The approach presented in [27] demonstrates the possibility of mining BPMN models covering boththe control flow perspective and the resource perspective.Unfortunately, this approach is rather narrow in scope as it123presents very concrete algorithms for mining BPMN controlflow and resource elements. Algorithms for discovering dataand resources from event logs were proposed in [28–30],respectively. To evaluate the quality of BPMN models andmultiperspective process models obtained from the real eventlogs, an analysis of process quality metrics proposed in various studies, such as [13–16], can be applied. An approachfor finding deviations between an event log and a multiperspective process model was presented in [31].3 PreliminariesIn this section, we introduce basic notions, event logs, Petrinets, system nets and BPMN semantics.Multisets are used to present states of Petri nets and BPMNmodels, and also they are used to define event logs, in whichone trace can appear multiple times.B(A) is the set of all multisets over some set A. For somemultiset b B(A), b(a) denotes the number of times element a A appears in b. By b [a1 2 , a2 3 ] we denotethat elements a1 , a2 A appear in b two and three times,respectively.The sum of two multisets b and b over set A is definedas: (b b )(a) b(a) b (a) for all a from A. We say thatb b iff a A : b(a) b (a). For two multisets b and b over set A, such that b b , the difference function is definedas: (b\b )(a) b(a) b (a). The size of a multiset b over set A is denoted by b and defined as b a A b(a). Setswill be considered as a special case of multisets, where eachelement can appear 0 or 1 times. Thus, operations applicableto multisets can be applied to sets.Function f : X Y is a partial function withdomain dom( f ) X and range defined as r ng( f ) { f (x) x dom( f )} Y . f : X Y is a total function, i.e., dom( f ) X . Let f : X Y be a partialfunction, f can be applied to sequences of X using the recursive definition f ( ) and for some σ X andx X f ( x · σ ) f (x) · f (σ ), if x dom( f ) andf ( x · σ ) f (σ ) otherwise.3.1 Event logs and Petri netsDefinition 1 (Petri Net) A Petri net is a tuple PN (P, T, F) with P the set of places, T the set of transitions,P T , and F (P T ) (T P) the flow relation.Definition 2 (Marking) Let PN (P, T, F) be a Petri net.A marking M is a multiset of places, i.e., M B(P).Definition 3 (Safe Marking) A marking M of a Petri netPN (P, T, F) is safe iff p P : M( p) 1, i.e., eachplace contains not more than 1 token.

Process mining using BPMN: relating event logs and process modelsPictorially, places are represented by circles, transitions byboxes and the flow relation F by directed arcs. Places maycarry tokens represented by filled circles. A current markingM is designated by putting M( p) tokens into each placep P.For a node n P T , the set of input nodes and theset of output nodes are defined as n {x (x, n) F} andn {x (n, x) F}, respectively.A transition t T is enabled in a marking M of net PN,denoted as (PN, M) [t , iff p t : M( p) 1, i.e., eachof its input places contains at least one token.An enabled transition t may fire, i.e., one token is removedfrom each of the input places t and one token produced foreach of the output places t . Formally: M (M\ t) t is the marking resulting from firing enabled transition t inmarking M of Petri net PN. (PN, M) [t (PN, M ) denotesthat t is enabled in M and firing results in marking M .Let σ t1 , . . . , tn T be a sequence of transitions. (PN, M) [σ (PN, M ) denotes that there is a set of markings M0 ,M 1 , , Mn , such that M0 M, Mn M ,and (PN, Mi ) ti 1 (PN, Mi 1 ) for 0 i n. We saythat M is reachable from M if there exists σ , such that(PN, M) [σ (PN, M ).R(PN, M) denotes the set of all markings reachable inPN from the marking M.Definition 4 (Labeled Petri Net) A labeled Petri net PN (P, T, F, l) is a Petri net (P, T, F) with labeling functionl T U A where U A is some universe of activity labels.Let σv a1 , . . . , an U A be a sequence of activity labels.(PN, M)[σv (PN, M ) iff there is a sequence σ T suchthat (PN, M) [σ (PN, M ) and l(σ ) σv .If t / dom(l), transition t is called invisible. An occurrence of visible transition t dom(l) corresponds toobservable activity label l(t).In the context of process mining, we normally considerso-called complete firing sequences, and thus we deal withprocesses, which have well-defined initial and end states.Therefore, let us give a notion of a system net.Definition 5 (System Net) A system net is a triplet SN (PN, Minit , Mfinal ) where PN (P, T, F, l) is a labeled Petrinet, Minit B( p) is the initial marking and Mfinal B( p) isthe final marking.Fig. 4 A fragment of a non-free-choice Petri netDefinition 7 (Trace, Event Log) Let A U A be a set ofactivity labels. A trace σ A is a sequence of activitylabels. L B(A ) is an event log, i.e., a multiset of traces.Note that a trace can appear multiple times in an event log.Some conversion techniques presented in this paper dealwith free-choice nets. Let us define them.Definition 8 (Free-choice Nets) A system net SN (PN,Minit , Mfinal ) and a corresponding labeled Petri net PN (P, T, F, l) are called free-choice iff for any two transitionst1 , t2 T with t1 t2 holds t1 t2 .To illustrate the concept of a free-choice Petri net, let usconsider a fragment of a Petri net presented in Fig. 4. It isnot a free-choice Petri net, and t1 and t2 share an input place,but do not have identical sets of input places. Indeed, if placep1 contains tokens enabling t1 , while p2 is empty, there is“no free choice” between t1 and t2 , only t1 is enabled andmay fire. If an arc is added from p2 to t1 , then the net isfree-choice.3.2 BPMN semanticsIn this subsection, we will present an approach for the formalization of BPMN control flow semantics based on a conceptof token. This formalization will give an ability to justifythe conversion algorithms presented later in this paper. Werestrict ourselves to the core set of BPMN elements, whichincludes activities, start and end events, exclusive and parallelgateways. We hope that these initial results will give a basisfor formal description of more advanced BPMN modelingconstructs.Let us give a formal definition of a BPMN model.Definition 6 (Language of a System Net) Suppose thatSN (PN, Minit , Mfinal ) is a system net. Language L SNof SN will be defined as a set of all visible executionsequencesstarting in Minit and ending in Mfinal , i.e., L SN σv (PN, Minit )[σv (PN, Mfinal ) .Event logs are considered as a starting point in the contextof process mining, so let us give their formal definition.Fig. 5 Core BPMN modeling constructs123

A. A. Kalenkova et al.Fig. 6 Initial markingFig. 8 Firing exclusive gatewayDefinition 9 (BPMN Model) A BPMN model is a tupleBPMNmodel (N , A, G XOR , G AND , estart , E end , SF, λ),where– N is a set of flow nodes,– A N is a set of activities,– G XOR N , G AND N are sets of exclusive and parallelgateways,– estart N is a start event,– E end N is a set of end events,– sets A, G XOR , G AND , {estart }, E end form a partition of N ,– SF N N is a set of sequence flows,– λ : N U A is a labeling function, where U A is someuniverse of activity labels,– start event estart does not have incoming sequence flows,and has not more than one outgoing sequence flow,– end events from E end do not have outgoing sequenceflows.Figure 5 shows the core BPMN constructs used to modelprocesses.Let n N be an arbitrary BPMN model node, the preset n and the postset n are defined as sets of incoming andoutgoing sequence flows for the node n, respectively.To restrict the set of all possible BPMN models, we willconsider and discover well-formed BPMN models, which arerevealed as weakly connected graphs with a source and sinknodes.Definition 10 (Well-formed BPMN Model) A BPMN modelis called well-formed iff every node of this model is on a pathfrom the start event to some end event.Definition 11 (BPMN Model Marking) Let BPMNmodel bea BPMN model with a set of sequence flows SF. A markingM is a multiset over the set sequence flows, i.e., M B(SF).An initial marking Minit is a marking, such that for all sf from , and M (sf) 0, otherwise.SF Minit (sf) 1, if sf estartinitAn illustration for the initial marking is presented in Fig. 6.Each node independently of its type may be enabled, andan enabled node may fire. Let us consider an arbitrary BPMNFig. 7 Firing activity123model BPMNmodel (N , A, G XOR , G AND , estart , E end ,SF, λ) and define its firing rules:1. An activitya A is enabled in a marking M iff sf SF : a(sf) 1) (M sf 1 . Suppose activity ais enabled and this activity may fire, producing a newmarking M , such that M M\ sf 1 a . In otherwords, activity a is enabled in marking M iff it has anincoming sequence flow, which contains at least onetoken. When activity fires, it consumes one token froman incoming sequence flow and produces a token foreach outgoing sequence flow (Fig. 7).2. Exclusive gateways merge alternative paths: The incoming sequence flow token is routed to one of the outgoingsequence flows (Fig. 8).Similar to activities, exclusive gateway gXOR G XOR isenabled in marking M iff there is an incoming sequenceflow, which contains 1 M, at least one token in markingi.e., sf S F : gXOR (sf) 1) (M sf . Incontrast to activities, it produces a token to one of theoutgoing sequence flows. Suppose an exclusive gatewaygXOR consumes a token from an incoming sequence flowsf and produces a token to an outgoing sequence flow sf , and then a new model marking M will be defined as follows: M M\ sf 1 sf 1 .3. A parallel gateway gAND G AND is enabled in marking M iff sf gAND : M(sf) 1, i.e., each incomingsequence flow contains at least one token. An enabledparallel gateway gAND may fire and produce a new mark , i.e., aing: M , such that M M\ gAND gANDparallel gateway consumes a token from each incomingsequence flow and produces a token to each outgoingsequence flow (Fig. 9).4. The unique start event is never enabled, since it does nothave any incoming sequence flow.5. An end event eend E end is enabled in marking M iff sf SF : (sf eend ) (M(sf) 1). When end eventfires, it consumes a token from an incoming sequence flow sf, and yields in a new marking M M\ sf 1(Fig. 10).Fig. 9 Firing parallel gateway

Process mining using BPMN: relating event logs and process modelsexecutions, stopped in markings with tokens on sequenceflows. These sequences of activity labels correspond to theBPMN model deadlocks.Fig. 10 Firing end eventWhen node n N fires, we denote this firing as(BPMNmodel , M) [n (BPMNmodel , M ).We write (BPMNmodel , M) [σ (BPMNmodel , M ) forsome sequence of nodes σ n 1 , . . . , n k N iff thereare markings M0 , . . . , Mk , such that M0 M, Mk M , and for 0 i k the following statement holds(BPMNmodel , Mi ) n i 1 (BPMNmodel , Mi 1 ).Likewise in Petri nets marking M is reachable frommarking M iff there is a sequence σ N , such that(BPMNmodel , M) [σ (BPMNmodel , M ).For some sequence of activity labels σv U A , we write(BPMNmodel , M)[σv (BPMNmodel , M ), if there is σ , suchthat (BPMNmodel , M) [σ (BPMNmodel , M ) and λ(σ ) σv .By R(BPMNmodel , M), we will denote the set of all markings reachable in BPMNmodel from the marking M.To define the notion of language generated by a BPMNmodel, let us first give a definition of a final marking.Definition 12 (Final BPMN Model Marking) LetBPMNmodel be a BPMN model with an initial markingMinit and a set of nodes N . Mfinal is a final markingiff Mfinal R(BPMNmodel , Minit ) and n N M :(BPMNmodel , M) [n (BPMNmodel , M ).As it follows from this definition, the final marking of aBPMN model is the marking, in which no node can fire.Definition 13 (Language of a BPMN Model) Let BPMNmodelbe a BPMN model with an initial marking Minit and a set offinal markings Mfinal . The language of BPMNmodel is a setL BPMNmodel {σv (BPMNmodel , Minit )[σv (BPMNmodel , M) M Mfinal .Thus, we define the language of a BPMN model as a set ofall visible sequences starting in an initial marking and endingin some final marking.According to the BPMN 2.0 specification [6], BPMNmodel gets the status completed iff there is no token remaining. Following the specification, a language of a BPMNmodel can be considered as a union of two disjoint sets:L BPMNmodel VBPMNmodel IBPMNmodel .VBPMNmodel {σv ((BPMNmodel , Minit )[σv BPMNmodel ,M)) ( sf SF : M(sf) 0)} is a set of valid sequences,corresponding to the model executions, which lead to markings with no tokens remaining. Note that according to BPMNsemantics if no tokens remaining, no node is enabled.IBPMNmodel L BPMNmodel \VBPMNmodel stands for a set ofinvalid sequences, which are the traces of the BPMN model3.3 Transition systems, reachability graphs andsimulation relationsIn this subsection, some basic definitions, which are used forthe justification of the conversion algorithms, will be given.Definition 14 (Transition system) Let S and E be two disjoint non-empty sets of states and events, let τ E be aspecial silent event, and let B S E S be a transitionrelation. A transition system is a tuple TS (S, E, B, sin ),where sin S is an initial state. Elements of B are calledtransitions.eWe write s s , when (s, e, s ) B. Assume that s τS : s s, i.e., there is a transition from every state to itself,labeled by τ .A state s is reachable from a

everywhere where BPM is applied. An absolute majority of freeware and commercial BPM tools and Business Suites, like Oracle BPM Suite, IBM Business Process Manager, jBPM, Activiti, Appian BPM Suite, Bizagi BPM Suite, MagicDraw Enterprise Architect (Sparx), Mega Pro