TY - GEN
T1 - Maximizing synchronization for aligning observed and modelled behaviour
AU - Bloemen, Vincent
AU - van Zelst, Sebastiaan J.
AU - van der Aalst, Wil M.P.
AU - van Dongen, Boudewijn F.
AU - van de Pol, Jaco
PY - 2018/1/1
Y1 - 2018/1/1
N2 - Conformance checking is a branch of process mining that aims to assess to what degree event data originating from the execution of a (business) process and a corresponding reference model conform to each other. Alignments have been recently introduced as a solution for conformance checking and have since rapidly developed into becoming the de facto standard. The state-of-the-art method to compute alignments is based on solving a shortest path problem derived from the reference model and the event data. Within such a shortest path problem, a cost function is used to guide the search to an optimal solution. The standard cost-function treats mismatches in the model and log as equal. In this paper, we consider a variant of this standard cost function which maximizes the number of correct matches instead. We study the effects of using this cost-function compared to the standard cost function on both small and large models using over a thousand generated and industrial case studies. We further show that the alignment computation process can be sped up significantly in specific instances. Finally, we present a new algorithm for the computation of alignments on models with many log traces that is an order of magnitude faster (in maximizing synchronous moves) compared to the state-of-the-art A* based solution method, as a result of a preprocessing step on the model.
AB - Conformance checking is a branch of process mining that aims to assess to what degree event data originating from the execution of a (business) process and a corresponding reference model conform to each other. Alignments have been recently introduced as a solution for conformance checking and have since rapidly developed into becoming the de facto standard. The state-of-the-art method to compute alignments is based on solving a shortest path problem derived from the reference model and the event data. Within such a shortest path problem, a cost function is used to guide the search to an optimal solution. The standard cost-function treats mismatches in the model and log as equal. In this paper, we consider a variant of this standard cost function which maximizes the number of correct matches instead. We study the effects of using this cost-function compared to the standard cost function on both small and large models using over a thousand generated and industrial case studies. We further show that the alignment computation process can be sped up significantly in specific instances. Finally, we present a new algorithm for the computation of alignments on models with many log traces that is an order of magnitude faster (in maximizing synchronous moves) compared to the state-of-the-art A* based solution method, as a result of a preprocessing step on the model.
UR - http://www.scopus.com/inward/record.url?scp=85053628175&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-98648-7_14
DO - 10.1007/978-3-319-98648-7_14
M3 - Conference contribution
AN - SCOPUS:85053628175
SN - 978-3-319-98647-0
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 233
EP - 249
BT - Business Process Management - 16th International Conference, BPM 2018, Proceedings
A2 - Montali, Marco
A2 - Weber, Ingo
A2 - Weske, Mathias
A2 - vom Brocke, Jan
PB - Springer
CY - Cham
T2 - 16th International Conference on Business Process Management, BPM 2018
Y2 - 9 September 2018 through 14 September 2018
ER -