Measuring Fitness and Precision of Automatically Discovered Process Models: A Principled and Scalable Approach

Abstract

Automated process discovery techniques allow us to generate a process model from an event log consisting of a collection of business process execution traces. The quality of process models generated by these techniques can be assessed with respect to several criteria, including <i>fitness</i> , which captures the degree to which the generated process model is able to recognize the traces in the event log, and <i>precision</i> , which captures the extent to which the behavior allowed by the process model is observed in the event log. A range of fitness and precision measures have been proposed in the literature. However, existing measures in this field do not fulfil basic monotonicity properties and/or they suffer from scalability issues when applied to models discovered from real-life event logs. This article presents a family of fitness and precision measures based on the idea of comparing the <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> th order Markovian abstraction of a process model against that of an event log. The article shows that this family of measures fulfils the aforementioned properties for suitably chosen values of <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> . An empirical evaluation shows that representative exemplars of this family of measures yield intuitive results on a synthetic dataset of model-log pairs, while outperforming existing measures of fitness and precision in terms of execution times on real-life event logs.