Anti-alignments—Measuring the precision of process models and event logs. Issue 98 (May 2021) - Chatain, Thomas; Boltenhagen, Mathilde; Carmona, Josep
Abstract: Processes are a crucial artifact in organizations, since they coordinate the execution of activities so that products and services are provided. The use of models to analyze the underlying processes is a well-known practice. However, due to the complexity and continuous evolution of their processes, organizations need an effective way of analyzing the relation between processes and models. Conformance checking techniques assess the suitability of a process model in representing an underlying process, observed through a collection of real executions. One important metric in conformance checking is to assess the precision of the model with respect to the observed executions, i.e., characterize the ability of the model to produce behavior unrelated to the one observed. In this paper we present the notion of anti-alignment as a concept to help unveiling runs in the model that may deviate significantly from the observed behavior. Using anti-alignments, a new metric for precision is proposed. The proposed anti-alignment based precision metric satisfies most of the required axioms highlighted in a recent publication. Moreover, a complexity analysis of the problem of computing anti-alignments is provided, which sheds light into the practicability of using anti-alignment to estimate precision. Experiments are provided that witness the validity of the concepts introduced in this paper. Highlights: Anti-alignments for can be computed optimaly for the Levenshtein distance. Complexity analysis of several variations of the problem of computing anti-alignments. Length agnostic estimation of precision based on anti-alignments. Adherence of the properties required for precision metrics. New implementation and empirical evaluation with state-of-the-art approach.