Filter techniques for region-based process discovery


Zelst, van, S.J., Dongen, van, B.F. & Aalst, van der, W.M.P. (2015). Filter techniques for region-based process discovery. (BPM reports, No. 1504)., 21 pp. Read more: Medialink/Full text



The goal of process discovery is to learn a process model based on example behavior recorded in an event log. Region-based process discovery techniques are able to uncover complex process structures (e.g., milestones) and, at the same time, provide formal guarantees w.r.t. the model discovered. For example, it is possible to ensure that the discovered model is able to replay the event log and that there are bounds on the amount of additional behavior allowed by the model that is not present in the event log. Unfortunately, region-based discovery techniques cannot handle exceptional behavior. The presence of a few exceptional traces may result in an incomprehensible model concealing the dominant behavior observed. Hence, despite their promise, region-based approaches cannot be applied in everyday process mining practice. This paper addresses the problem by proposing two filtering techniques tailored towards ILP-based process discovery (an approach based on integer linear programming and language-based region theory). Both techniques help to produce models that are less over-fitting w.r.t. the event log and have been implemented in ProM. One of the techniques is also feasible in real-life settings as it, in most cases, reduces computation time compared to conventional region-based techniques. Additionally the technique is able to produce understandable process models that better capture the dominant behavior present in the event log.

Keywords: Process mining, process discovery, integer linear programming, filtering