Foundations of Process Discovery
Authors:
- van der Aalstvan der Aalst
- Wil M. P.WPWil M. P.
Open Access
- 27 June 2022
- book chapter
- Published by Springer Nature
- p. 37-75
Abstract
Process discovery is probably the most interesting, but also most challenging, process mining task. The goal is to take an event log containing example behaviors and create a process model that adequately describes the underlying process. This chapter introduces the baseline approach used in most commercial process mining tools. A simplified event log is used to create a so-called Directly-Follows Graph (DFG). This baseline is used to explain the challenges one faces when trying to discover a process model. After introducing DFG discovery, we focus on techniques that are able to discover models allowing for concurrency (e.g., Petri nets, process trees, and BPMN models). The chapter distinguishes two types of approaches able to discover such models: (1) bottom-up process discovery and (2) top-down process discovery. The Alpha algorithm is presented as an example of a bottom-up technique. The approach has many limitations, but nicely introduces the idea of discovering local constraints. The basic inductive mining algorithm is presented as an example of a top-down technique. This approach, combined with frequency-based filtering, works well on most event logs. These example algorithms are used to illustrate the foundations of process discovery.Keywords
This publication has 34 references indexed in Scilit:
- Discovering Block-Structured Process Models from Event Logs - A Constructive Approach2013
- Replaying history on process models for conformance checking and performance analysisWIREs Data Mining and Knowledge Discovery, 2012
- Mining process models with prime invisible tasksData & Knowledge Engineering, 2010
- Soundness of workflow nets: classification, decidability, and analysisFormal Aspects of Computing, 2010
- Process mining: a two-step approach to balance between underfitting and overfittingSoftware and Systems Modeling, 2008
- A Region-Based Algorithm for Discovering Petri Nets from Event Logs2008
- Mining process models with non-free-choice constructsData Mining and Knowledge Discovery, 2007
- Workflow mining: discovering process models from event logsIEEE Transactions on Knowledge and Data Engineering, 2004
- Deriving Petri nets from finite transition systemsIEEE Transactions on Computers, 1998
- Partial (set) 2-structuresActa Informatica, 1990