Discovering workflow nets using integer linear programming

Process mining is concerned with the analysis, understanding and improvement of business processes. Process discovery, i.e. discovering a process model based on an event log, is considered the most challenging process mining task. State-of-the-art process discovery algorithms only discover local con...

Full description

Saved in:
Bibliographic Details
Published in:Computing 2018-05, Vol.100 (5), p.529-556
Main Authors: van Zelst, S. J., van Dongen, B. F., van der Aalst, W. M. P., Verbeek, H. M. W.
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Computer Appl. in Administrative Data Processing
Computer Communication Networks
Computer Science
Data mining
Filtration
Information Systems Applications (incl.Internet)
Integer programming
Linear programming
Software Engineering
Source code
State of the art
Workflow
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Process mining is concerned with the analysis, understanding and improvement of business processes. Process discovery, i.e. discovering a process model based on an event log, is considered the most challenging process mining task. State-of-the-art process discovery algorithms only discover local control flow patterns and are unable to discover complex, non-local patterns. Region theory based techniques, i.e. an established class of process discovery techniques, do allow for discovering such patterns. However, applying region theory directly results in complex, overfitting models, which is less desirable. Moreover, region theory does not cope with guarantees provided by state-of-the-art process discovery algorithms, both w.r.t. structural and behavioural properties of the discovered process models. In this paper we present an ILP-based process discovery approach, based on region theory, that guarantees to discover relaxed sound workflow nets. Moreover, we devise a filtering algorithm, based on the internal working of the ILP-formulation, that is able to cope with the presence of infrequent, exceptional behaviour. We have extensively evaluated the technique using different event logs with different levels of exceptional behaviour. Our experiments show that the presented approach allows us to leverage the inherent shortcomings of existing region-based approaches. The techniques presented are implemented and readily available in the HybridILPMiner package in the open-source process mining tool-kits ProM ( http://promtools.org ) and RapidProM ( http://rapidprom.org ).
ISSN:0010-485X
1436-5057
DOI:10.1007/s00607-017-0582-5