An A*-Algorithm for Computing Discounted Anti-Alignments in Process Mining

Mathilde Boltenhagen (1, 2, 3, 4, 5, 6) , Thomas Chatain (1, 3, 5, 6, 2, 4) , Josep Carmona (7)

1 Université Paris-Saclay
2 ENS Paris Saclay - Ecole Normale Supérieure Paris-Saclay
3 CNRS - Centre National de la Recherche Scientifique
4 Inria - Institut National de Recherche en Informatique et en Automatique
5 LMF - Laboratoire Méthodes Formelles
6 MEXICO - Modeling and Exploitation of Interaction and Concurrency
7 UPC - Universitat Politècnica de Catalunya = Université polytechnique de Catalogne [Barcelona]

Process mining techniques aim at analyzing and monitoring processes through event data. Formal models like Petri nets serve as an effective representation of the processes. A central question in the field is to assess the conformance of a process model with respect to the real process executions. The notion of anti-alignment, which represents a model run that is as distant as possible to the process executions, has been demonstrated to be crucial to measure precision of models. However, the only known algorithm for computing anti-alignments has a high complexity, which prevents it from being applied on real-life problem instances. In this paper we propose a novel algorithm for computing anti-alignments, based on the well-known graphbased A * scheme. By introducing a discount factor in the edit distance used for the search of anti-alignments, we obtain the first efficient algorithm to approximate them. We show how this approximation is quite accurate in practice, by comparing it with the optimal results for small instances where the optimal algorithm can also compute anti-alignments. Finally, we compare the obtained precision metric with respect to the state-of-the-art metrics in the literature for real-life examples.

Domains: Computer Science [cs]

Mathilde Boltenhagen, Thomas Chatain, Josep Carmona. An A*-Algorithm for Computing Discounted Anti-Alignments in Process Mining. 2021. ⟨hal-03229744v1⟩