Abstract
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.
| Original language | English |
|---|---|
| Title of host publication | Business Process Management - 16th International Conference, BPM 2018, Proceedings |
| Editors | Marco Montali, Ingo Weber, Mathias Weske, Jan vom Brocke |
| Place of Publication | Cham |
| Publisher | Springer |
| Pages | 233-249 |
| Number of pages | 17 |
| ISBN (Electronic) | 978-3-319-98648-7 |
| ISBN (Print) | 978-3-319-98647-0 |
| DOIs | |
| Publication status | Published - 1 Jan 2018 |
| Event | 16th International Conference on Business Process Management, BPM 2018 - Sydney, Australia Duration: 9 Sep 2018 → 14 Sep 2018 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 11080 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 16th International Conference on Business Process Management, BPM 2018 |
|---|---|
| Country | Australia |
| City | Sydney |
| Period | 9/09/18 → 14/09/18 |
Fingerprint
Cite this
}
Maximizing synchronization for aligning observed and modelled behaviour. / Bloemen, Vincent; van Zelst, Sebastiaan J.; van der Aalst, Wil M.P.; van Dongen, Boudewijn F.; van de Pol, Jaco.
Business Process Management - 16th International Conference, BPM 2018, Proceedings. ed. / Marco Montali; Ingo Weber; Mathias Weske; Jan vom Brocke. Cham : Springer, 2018. p. 233-249 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11080 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
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
ER -