WIXLIB

Noname manuscript No.(will be inserted by the editor)Process Mining Using BPMN:Relating Event Logs and Process ModelsAnna A. Kalenkova · W. M. P. van der Aalst · Irina A. Lomazova ·Vladimir A. RubinReceived: 03.2015 / Accepted: dateAbstract Process-aware information systems (PAIS) aresystems relying on processes, which involve human andsoftware resources to achieve concrete goals. There is a needto develop approaches for modeling, analysis, improvementand monitoring processes within PAIS. These approachesinclude process mining techniques used to discover processmodels from event logs, find log and model deviations, andanalyze performance characteristics of processes. The representational bias (a way to model processes) plays an important role in process mining. The BPMN 2.0 (BusinessProcess Model and Notation) standard is widely used and allows to build conventional and understandable process models. In addition to the flat control flow perspective, subprocesses, data flows, resources can be integrated within oneBPMN diagram. This makes BPMN very attractive for bothprocess miners and business users. In this paper, we describeand justify robust control flow conversion algorithms, whichprovide the basis for more advanced BPMN-based discovThis work is supported by the Basic Research Program of the NationalResearch University Higher School of Economics.Anna A. Kalenkova · Irina A. Lomazova · Vladimir A. RubinNational Research University Higher School of Economics, Moscow,RussiaE-mail: akalenkova@hse.ruW. M. P. van der AalstDepartment of Mathematics and Computer Science, EindhovenUniversity of Technology, Eindhoven, The NetherlandsBusiness Process Management Discipline, Queensland University ofTechnology, Brisbane, AustraliaE-mail: w.m.p.v.d.aalst@tue.nlIrina A. LomazovaE-mail: ilomazova@hse.ruVladimir A. RubinE-mail: vrubin@hse.ruery and conformance checking algorithms. We believe thatthe results presented in this paper can be used for a widevariety of BPMN mining and conformance checking algorithms. We also provide metrics for the processes discoveredbefore and after the conversion to BPMN structures. Casesfor which conversion algorithms produce more compact ormore involved BPMN models in comparison with the initialmodels are identified.Keywords Process mining · Process discovery · Conformance checking · BPMN (Business Process Model andNotation) · Petri nets · Bisimulation1 IntroductionProcess-aware information systems (PAIS) are the systemsdesigned to manage processes, operating in various domainsof human activity. There is a natural requirement to monitortheir work and analyze executed processes. For that purposeone of the promising approaches - process mining can beapplied.Process mining is a discipline connecting data miningand process modeling approaches. Process mining offerstechniques for automatic discovery of process models fromevent logs, checking compatibility of process models andevent logs (conformance checking) and enhancing discovered processes with additional data [4, 5]. Process mininghas been successfully applied in a variety of application domains such as healthcare, transportation, tourism and education. There is a IEEE process mining community, includingmore than 60 organizations [21]. Moreover, there is a widerange of research and commercial tools available in thisarea: ProM [35], Disco (Fluxicon), ARIS Process Performance Manager (Software AG), Perceptive Process Mining(Perceptive Software), ProcessAnalyzer (QPR) and Celonis.

2Anna A. Kalenkova et al.Case IDEventTimestampPriceClient IP1121311.book flightget insurancebook flightbook hotelbook flightpayconfirm.2014-12-24 08:30:00:2322014-12-24 08:31:05:1712014-12-24 08:31:08:5432014-12-24 08:32:08:7032014-12-24 08:32:11:5342014-12-24 08:34:17:4562014-12-24 42.45188.44.42.45.Table 1: An event log of a booking process.Today, BPMN 2.0 (Business Process Model and Notation) [30] is the de facto standard notation for modeling business processes understandable by a wide audienceof people. Business analysts and product managers, technical designers and developers, system and enterprise architects effectively use this notation in their everyday job almost everywhere where BPM is applied. An absolute majority of freeware and commercial BPM tools and Business Suites, like Oracle BPM Suite, IBM Business ProcessManager, jBPM, Activiti, Appian BPM Suite, Bizagi BPMSuite, MagicDraw Enterprise Architect (Sparx), Mega Process (MEGA), Signavio Process Editor and others, either natively support BPMN or provide conversion in order to staycompatible and up to date.The representational bias used for process mining isnot only relevant for the understandability of the results:it is also vital to guide process discovery by setting a suitable class of target models. Using the BPMN notation as arepresentational bias within process mining opens excellentperspectives for applicability of process mining: discoveredprocess models become available and understandable bythe majority of users, the models can be imported/exportedfrom/to any BPMN-aware modeling tool and executed, process mining techniques can be easily integrated to the existing suites (BPMN serves as an interface in this case). Moreover, BPMN models allow for the combination of differentperspectives varying from control flow to the perspective ofresources, thus a holistic view on a process model can beobtained.In this paper we present methods for discovering thecontrol flow perspective of a process in terms of BPMN.It should be noted that process mining offers plenty of algorithms for the control flow discovery, each of them hasits own characteristics. The goal is not to invent new algorithms, but to benefit from the existing ones and to makethem BPMN-compatible. Thus the discovery of the controlflow relies on conversion algorithms and existing processmining techniques. To that end we firstly formalize the semantics for a subset of BPMN models and then present theconversion algorithms from well-known control flow modeling formalisms such as Petri nets (including non-free-choicePetri nets), causal nets [6] and process trees [8] to BPMN.The conversion algorithms presented in the paper are alsogiven the justifications in order to show that behavioral properties of process models discovered from an event log arepreserved. Moreover, we show relations between languagesof Petri nets and corresponding BPMN models, tacking intoaccount properties of the initial Petri nets.As a short introductory example, let us consider an eventlog reflecting a small portion of the history of a ticket booking process, which is presented in Tab. 1. In this process,people use a web site to book a flight, a hotel, get insuranceand pay for the ticket. Different people in different cases execute these activities in a different order.Beside case identifiers, event names, and timestamps, anevent log can contain additional event properties, such ascosts and resources (participants of the process), in this example they are represented by prices and clients ip addresses(Tab. 1).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 hbook f light, get insurance, book hotel, pay, conf irmi5 , hbook f light, book hotel, get insurance, pay, conf irmi4 ,hbook hotel, book f light, get insurance, pay, conf irmi4 ,hbook hotel, get insurance, book f light, pay, conf irmi3 ,hget insurance, book hotel, book f light, pay, conf irmi1 ,hget insurance, book f light, book hotel, pay, conf irmi1 . A Petri net discovered from L by the Alpha mining algorithm [10] is presented in Fig. 1.book hotelbook flightpayconfirmget insuranceFig. 1: A Petri net constructed from the log

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