Foundations of Process Discovery

Lecture notes in business information processing, pp. 37–75

Abstract

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.

Authors 1

1. Wil M. P. van der Aalst corresponding Aachen Process and Data Science (PADS)

   RWTH Aachen University

   Affiliation as printed

   Process and Data Science (PADS), RWTH Aachen University, Aachen, Germany

   RWTH Aachen, Aachen, Germany