Behavioural Quotients for Precision and Recall in Process Mining

Abstract

The comparison of the languages of software systems, i.e., their behaviours in terms of specified executions, is a prerequisite for many applications, reaching from system validation through management of a system's evolution to conformance checking of observed and expected behaviour. If two systems are not language-equivalent, the quantification of behavioural differences enables conclusions on the extent of deviation. Such quantifications are commonly done in a relative manner: A quotient is defined over some measure of two languages, which have potentially been derived via algebraic operations. However, there exists no systematic approach for defining quotients and it is unclear which measures enable meaningful comparisons of systems having infinite behaviours. This paper introduces a framework for defining language quotients. We instantiate the framework with cardinality-based and entropy-based measures to handle finite and infinite behaviours, and prove important properties of the quotients. We demonstrate application of quotients in the field of process mining to capture precision and recall between a log of recorded system executions and a model of expected system executions. An experimental evaluation of the quotients using our open-source implementation demonstrates their feasibility and indicates that the quotients enable a monotonic assessment, unlike state-of-the-art measures in process mining.