mopdf.com

Process Mining Using BPMN: Relating Event Logs and Process ModelsWith 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 BPMNnotation now; this BPMN model can be easily imported andexecuted by any of BPM tools mentioned above.3Event logProcess discovery algorithmsPetri netCausal netProcesstreeConversions to BPMN(Section 3, Section 4)bookhotelbookflightBPMNpayconfirmBPMN to a Petri netconversion (Section 6)getinsurancePetri netFig. 2: A BPMN model obtained by a conversion from the Petri netIn order to estimate the advantages of using the BPMNnotation for mining, we additionally compare the complexity of the models produced by the existing control flow discovery algorithms and the complexity of the correspondingBPMN models. We use the various metrics, such as the number of nodes, density, and diameter [34] for this evaluation.We present not only theoretical but also practical evaluationsbased on real-life event logs. Moreover, applied to theseevent logs, the metrics of the discovered BPMN models arecompared to the metrics of the models designed manuallywith a BPMN-editor. This helps us to understand structuraldifferences between models, which are created by processanalysts and models discovered from 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 [7] 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 miningis presented in Fig. 3. The user discovers a BPMN modelby applying discovery and BPMN conversions plugins. Toshow performance and conformance information and to annotate the BPMN diagram the BPMN model is converted toa Petri net, such that replay techniques can be used.The paper is organized as follows. Section 2 introducesbasic definitions and notions, including traces, Petri nets,system nets, (weak) simulation and (weak) bisimulation relations. In Section 3 we propose algorithms for conversionfrom well-known formalisms such as Petri nets to BPMNand prove correctness of these conversions. In Section 4Evaluation of performanceand conformance infoPerformance andconformance infoEnhancement of theBPMN diagram(Section 6)AnnotatedBPMNFig. 3: A general scheme of using BPMN for process miningtransformations of causal nets and process trees to BPMNare introduced. Section 5 contains a set of BPMN simplification rules. In Section 6 a technique for conformance checking and performance analysis on the basis of BPMN modelsis presented. A tool, which implements the proposed conversion and enhancement techniques, is presented in Section 7.Section 8 includes a case study, which shows the results ofan application of the algorithms presented in the paper toreal-life event logs. Also the structural business-processesmetrics are calculated and presented in this section. Section9 concludes the paper.2 PreliminariesIn this section we introduce basic notions, event logs, Petrinets, system nets and BPMN semantics.Multisets are used to present states of Petri nets andBPMN models, also they are used to define event logs, inwhich one trace can appear multiple times.B(A) is the set of all multisets over some set A. Forsome multiset b B(A), b(a) denotes the number of timeselement a A appears in b. By b [a1 2 , a2 3 ] we denote

4Anna A. Kalenkova et al.that elements a1 , a2 A appear in b two and three timesrespectively.The sum of two multisets b and b0 over set A is definedas: (b ] b0 )(a) b(a) b0 (a) for all a from A. We say thatb b0 iff a A : b(a) b0 (a). For two multisets b andb0 over set A, such that b b0 , the difference function isdefined as: (b\b0 )(a) b(a) b0 (a). The size of aPmultisetb over set A is denoted by b and defined as b b(a).a ASets will be considered as a special case of multisets, whereeach element can appear 0 or 1 times. Thus, operations applicable to multisets can be applied to sets.Function f : X 9 Y is a partial function withdomain dom(f ) X and range defined as rng(f ) {f (x) x dom(f )} Y . f : X Y is a total function, i.e., dom(f ) X. Let f : X 9 Y be a partialfunction, f can be applied to sequences of X using the recursive definition f (hi) hi and for some σ X andx X f (hx · σi) hf (x)i · f (σ), if x dom(f ) andf (hx · σi) f (σ) otherwise.2.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.Pictorially, places are represented by circles, transitionsby boxes, and the flow relation F by directed arcs. Placesmay carry tokens represented by filled circles. A currentmarking M is designated by putting M (p) tokens into eachplace p 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 ) [ti, 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 isremoved from each of the input places t and one token produced for each of the output places t . Formally:M 0 (M \ t) ] t is the marking resulting from firing enabled transition t in marking M of Petri net PN.(PN, M ) [ti (PN, M 0 ) denotes that t is enabled in M andfiring results in marking M 0 .Let σ ht1 , ., tn i T be a sequence of transitions. (PN, M ) [σi (PN, M 0 ) denotes that there is a set ofmarkings M0 ,M1 ,.,Mn , such that M0 M , Mn M 0 ,and (PN, Mi ) [ti 1 i (PN, Mi 1 ) for 0 i n. We saythat M 0 is reachable from M if there exists σ, such that(PN, M ) [σi (PN, M 0 ).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 function l T 9 UA where UA is some universe of activity labels. Letσv ha1 , ., an i UA be a sequence of activity labels.(PN, M )[σv . (PN, M 0 ) iff there is a sequence σ T suchthat (PN, M ) [σi (PN, M 0 ) and l(σ) σv .If t / dom(l), transition t is called invisible. An occurrence of visible transition t dom(l) corresponds to observable activity label l(t).In the context of process mining we normally consider so-called complete firing sequences, 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.Definition 6 (Language of a System Net) Suppose thatSN (PN, Minit , Mfinal ) is a system net. Language LSNof SN will be defined as a set of all visible execution sequences starting in Minit and ending in Mfinal , i.e., LSN {σv (PN, Minit )[σv . (PN, Mfinal )}.Event logs are considered as a starting point in the context of process mining, so let us give their formal definition.Definition 7 (Trace, Event log) Let A UA 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 eventlog.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 netPN (P, T, F, l) are called free-choice iff for any two transitions t1 , t2 T with t1 t2 6 holds t1 t2 .2.2 BPMN semanticsIn this subsection we will present an approach for the formalization of BPMN control flow semantics based on a concept of token. This formalization will give an ability to justify the conversion algorithms presented later in this paper.

Process Mining Using BPMN: Relating Event Logs and Process Models5We restrict ourselves to the core set of BPMN elements,which includes activities, start and end events, exclusiveand parallel gateways. We hope that these initial results willgive a basis for formal description of more advanced BPMNmodeling constructs.Let us give a formal definition of a BPMN model.Definition 11 (BPMN Model Marking)Let BPMNmodel be a BPMN model with a set of sequenceflows SF. A marking M is a multiset over the set sequenceflows, i.e., M B(SF). An initial marking Minit is a marking, such that for all sf from SF Minit (sf) 1, if sf e start ,and Minit (sf) 0, otherwise.Definition 9 (BPMN Model)A BPMN model is a tuple BPMNmodel (N, A,GXOR , GAND , estart , Eend , SF, λ), whereAn illustration for the initial marking is presented inFig. 5.– N is a set of flow nodes,– A N is a set of activities,– GXOR N , GAND N are sets of exclusive and parallelgateways,– estart N is a start event,– Eend N is a set of end events,– sets A, GXOR , GAND , {estart }, Eend form a partition of N ,– SF N N is a set of sequence flows,– λ : N 9 UA is a labeling function, where UA is someuniverse of activity labels,– start event estart doesn’t have incoming sequence flows,and has not more than one outgoing sequence flow,– end events from Eend don’t have outgoing sequenceflows.Figure 4 shows the core BPMN constructs used tomodel . 5: Initial markingEach node independently of its type may be enabled, anenabled node may fire. Let us consider an arbitrary BPMNmodel BPMNmodel (N, A, GXOR , GAND , estart , Eend , SF, λ)and define its firing rules:1. An activity a A is enabled in a marking M iff sf SF : ( a(sf) 1) (M sf 1 ). Suppose activity a is enabled, this activity may fire,a new producing marking M 0 , such that M 0 M \ sf 1 ] a . In otherwords activity a is enabled in marking M iff it has anincoming sequence flow, which contains at least one token. When activity fires it consumes one token from anincoming sequence flow and produces a token for eachoutgoing sequence flow (Fig. 6).activitysequence flowastart eventaend eventFig. 6: Firing activityFig. 4: Core BPMN modeling constructsLet n N be an arbitrary BPMN model node, the presetn 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, whichare revealed as weakly connected graphs with a source andsink nodes. Definition 10 (Well-formed BPMN Model)A BPMN model is called well-formed iff every node of thismodel is on a path from the start event to some end event.2. Exclusive gateways merge alternative paths: the incoming sequence flow token is routed to one of theoutgoing sequence flows (Fig. 7). Similar to activities exclusive gateway gXOR GXOR is enabled inmarking M iff there is an incoming sequence flow,which contains at least one token in marking M , i.e., sf SF : ( gXOR (sf) 1) (M sf 1 ). Incontrast to activities it produces a token to one ofthe outgoing sequence flows. Suppose an exclusivegateway gXOR consumes a token from an incomingsequence flow sf and produces a token to an outgoing sequence flow sf', then a new model 1 marking 00M will be defined as follows: M M \ sf ] sf'1 .

6Anna A. Kalenkova et al.gXORgXORFig. 7: Firing exclusive gateway3. A parallel gateway gAND GAND is enabled in markingM 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 marking: M 0 , such that M 0 M \ gAND ] gAND, i.e., aparallel gateway consumes a token from each incomingsequence flow and produces a token to each outgoingsequence flow (Fig. 8).gANDgANDFig. 8: Firing parallel gateway4. The unique start event is never enabled, since it doesn’thave any incoming sequence flow.5. An end event eend Eend 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 0 M \ sf 1(Fig. 9).eendeend For some sequence of activity labels σv UAwe write(BPMNmodel , M )[σv . (BPMNmodel , M 0 ), if there is σ, suchthat (BPMNmodel , M ) [σi (BPMNmodel , M 0 ) and λ(σ) σv .By R(BPMNmodel , M ) we will denote the set of allmarkings 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 marking Minit and a set of nodes N . Mfinal is a final marking iff Mfinal R(BPMNmodel , Minit ) and n N @M 0 : (BPMNmodel , M ) [ni (BPMNmodel , M 0 ).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) LetBPMNmodel be a BPMN model with an initial markingMinit and a set of final markings Mfinal . The languageof BPMNmodel is a set LBPMNmodel {σv (BPMNmodel ,Minit )[σv . (BPMNmodel , M ) M Mfinal }.Thus, we define the language of a BPMN model as aset of all visible sequences starting in an initial marking andending in some final marking.According to the BPMN 2.0 specification [30] 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:LBPMNmodel 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 toBPMN semantics if no tokens remaining, no node is enabled.IBPMNmodel LBPMNmodel \VBPMNmodel stands for a set of invalid sequences, which are the traces of the BPMN modelexecutions, stopped in markings with tokens on sequenceflows. These sequences of activity labels correspond to theBPMN model deadlocks.Fig. 9: Firing end eventWhen node n N fires we denote this firing as(BPMNmodel , M ) [ni (BPMNmodel , M 0 ).We write (BPMNmodel , M ) [σi (BPMNmodel , M 0 ) forsome sequence of nodes σ hn1 , ., nk i N iff thereare markings M0 , ., Mk , such that M0 M , Mk M 0 , and for 0 i k the following statement holds(BPMNmodel , Mi ) [ni 1 i (BPMNmodel , Mi 1 ).Likewise in Petri nets marking M 0 is reachable frommarking M iff there is a sequence σ N , such that(BPMNmodel , M ) [σi (BPMNmodel , M 0 ).2.3 Transition systems, reachability graphs and simulationrelationsIn 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.

Process Mining Using BPMN: Relating Event Logs and Process ModelseWe write s s0 , when (s, e, s0 ) B. Assume thatτ s S : s s, i.e., there is a transition from every state toitself, labeled by τ .A state s is reachable from a state s0 iff there is a (possibly empty) sequence of transitions leading from s to s0 (de τnoted by s s0 ). The reflexive transitive closure of wille000 e000be denoted as . By s s we denote s s s s0 ,0i.e., s can be reached from s via e preceded and followedby zero or more τ transitions.A transition system must satisfy the following basic axiom: every state is reachable from the initial state: s S : sin s.Definition 15 (Simulation) For transition systems: TS (S, E, B, sin ) and TS' (S 0 , E, B 0 , s0in ) relation R S S 0is called a simulation iff:– (sin , s0in ) R,ee– (u, v) R e E: if u0 : u u0 then v 0 : v v 0and (u0 , v 0 ) R.Definition 16 (Weak simulation) Let us consider twotransition systems: TS (S, E, B, sin ) and TS' (S 0 , E, B 0 , s0in ). Relation R S S 0 is called a weak simulation iff:– (sin , s0in ) R,ee– (u, v) R e E: if u0 : u u0 then v 0 : v v0and (u0 , v 0 ) R.Definition 17 (Bisimulation) If R is a (weak) simulationrelation and R 1 is a (weak) simulation relation as well, thenrelation R is called a (weak) bisimulation.Definition 18 (Reachability Graph for a System Net) Areachability graph for a system net SN (PN,Minit , Mfinal ), where PN (P, T, F, l), and l T 9 UA , isa transition system TS (S, E, B, sin ), such that:– S R(SN, Minit ), i.e., the set of states is defined as aset of markings reachable from Minit ,– E rng(l) {τ }, i.e., the set of events is defined as aunion of the range of l and a silent event τ ,– B contains a transition (M, e, M 0 ) iff at least one thefollowing conditions holds:– t T : (SN, M ) [ti (SN, M 0 ), such that l(t) e, ift dom(l), or e τ , otherwise,– M M 0 and e τ , this holds for silent transitionsfrom states to itself.– sin Minit , i.e., the initial state in TS is the initial marking of SN.Definition 19 (Reachability graph for a BPMN model) Areachability graph for a BPMN modelBPMNmodel (N, SF, A, GXOR , GAND , estart , Eend , λ) withan initial marking Minit is defined as a transition systemTS (S, E, B, sin ), such that:7– S R(BPMNmodel , Minit ),– E rng(λ) {τ }, where τ is a special silent event,– (M, e, M 0 ) B iff at least one of the following conditions holds:– there exists n N , such that (BPMNmodel , M ) [ni(BPMNmodel , M 0 ), where λ(n) e, if n dom(λ),or e τ , otherwise,– M M 0 and e τ .– sin Minit .3 Converting process models into BPMNIn this section we will propose algorithms for the conversionfrom well-known formalisms such as Petri nets, causal netsand process trees to BPMN. These formalisms are widelyused within process mining as results of application of process discovery algorithms [9, 10, 12, 16, 20, 26, 36]. Having conversion algorithms to BPMN format will give an opportunity to discover control flow models, which could beintegrated with other process perspectives. The correctnessof the proposed system nets conversion algorithm will beproven.Algorithms for conversion of free-choice workflow nets[3] (a special subset of Petri nets) to workflow graphs (generalization concept for process modeling notations such asBPMN, UML Activity [31], EPC [25, 28], etc) were proposed earlier in [2] and [19]. In our paper we will deal witharbitrary system nets, which have arbitrary Petri nets structures and arbitrary safe initial markings. Also we prove thatthe target model will simulate the behavior of the initial netand vice versa, thus important (in the context of processmining) propositions on the language preservation will beproven.First, let us show that every system net with a safe initial marking can be transformed to an equivalent system net,which contains a unique source place.3.1 Adding a source place to an arbitrary system net with asafe initial markingIn most cases models discovered from event logs arearbitrary system

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