research-article

Impact-Driven Process Model Repair

Authors:

Artem Polyvyanyy,

Wil M. P. Van Der Aalst,

Arthur H. M. Ter Hofstede,

Moe T. WynnAuthors Info & Claims

ACM Transactions on Software Engineering and Methodology (TOSEM), Volume 25, Issue 4

Article No.: 28, Pages 1 - 60

https://doi.org/10.1145/2980764

Published: 12 October 2016 Publication History

Abstract

The abundance of event data in today’s information systems makes it possible to “confront” process models with the actual observed behavior. Process mining techniques use event logs to discover process models that describe the observed behavior, and to check conformance of process models by diagnosing deviations between models and reality. In many situations, it is desirable to mediate between a preexisting model and observed behavior. Hence, we would like to repair the model while improving the correspondence between model and log as much as possible. The approach presented in this article assigns predefined costs to repair actions (allowing inserting or skipping of activities). Given a maximum degree of change, we search for models that are optimal in terms of fitness—that is, the fraction of behavior in the log not possible according to the model is minimized. To compute fitness, we need to align the model and log, which can be time consuming. Hence, finding an optimal repair may be intractable. We propose different alternative approaches to speed up repair. The number of alignment computations can be reduced dramatically while still returning near-optimal repairs. The different approaches have been implemented using the process mining framework ProM and evaluated using real-life logs.

References

[1]

Arya Adriansyah. 2014. Aligning Observed and Modeled Behavior. Ph.D. Dissertation. Technische Universiteit Eindhoven.

[2]

Arya Adriansyah, Boudewijn F. van Dongen, and Wil M. P. van der Aalst. 2011. Conformance checking using cost-based fitness analysis. In Proceedings of the 15th IEEE International Enterprise Distributed Object Computing Conference (EDOC’11). IEEE, Los Alamitos, CA, 55--64.

Digital Library

[3]

Rumen Andonov, Vincent Poirriez, and Sanjay V. Rajopadhye. 2000. Unbounded knapsack problem: Dynamic programming revisited. European Journal of Operational Research 123, 2, 394--407.

[4]

Thomas Baier, Claudio Di Ciccio, Jan Mendling, and Mathias Weske. 2015a. Matching of events and activities—an approach using declarative modeling constraints. In Enterprise, Business-Process and Information Systems Modeling. Lecture Notes in Business Information Processing, Vol. 214. Springer, 119--134.

[5]

Thomas Baier, Andreas Rogge-Solti, Jan Mendling, and Mathias Weske. 2015b. Matching of events and activities: An approach based on behavioral constraint satisfaction. In Proceedings of the 30th Annual ACM Symposium on Applied Computing. ACM, New York, NY, 1225--1230.

Digital Library

[6]

Joos C. A. M. Buijs, Marcello La Rosa, Hajo A. Reijers, Boudewijn F. van Dongen, and Wil M. P. van der Aalst. 2013. Improving business process models using observed behavior. In Data-Driven Process Discovery and Analysis. Springer, 44--59.

[7]

Joos C. A. M. Buijs, Boudewijn F. van Dongen, and Wil M. P. van der Aalst. 2012. On the role of fitness, precision, generalization and simplicity in process discovery. In On the Move to Meaningful Internet Systems: OTM 2012. Lecture Notes in Computer Science, Vol. 7565. Springer, 305--322.

[8]

Joos C. A. M. Buijs, Boudewijn F. van Dongen, and Wil M. P. van der Aalst. 2013. Discovering and navigating a collection of process models using multiple quality dimensions. In Business Process Management Workshops. Lecture Notes in Business Information Processing, Vol. 171. Springer, 3--14.

[9]

George B. Dantzig. 1957. Discrete-variable extremum problems. Operations Research 5, 2, 266--277.

Digital Library

[10]

Luca de Alfaro, Marco Faella, and Mariëlle Stoelinga. 2009. Linear and branching system metrics. IEEE Transactions on Software Engineering 35, 2, 258--273.

Digital Library

[11]

Massimiliano de Leoni and Wil M. P. van der Aalst. 2013a. Aligning event logs and process models for multi-perspective conformance checking: An approach based on integer linear programming. In Business Process Management. Lecture Notes in Computer Science, Vol. 8094. Springer, 113--129.

Digital Library

[12]

Massimiliano de Leoni and Wil M. P. van der Aalst. 2013b. Data-aware process mining: Discovering decisions in processes using alignments. In Proceedings of the 28th Annual ACM Symposium on Applied Computing (SAC’13). ACM, New York, NY, 1454--1461.

Digital Library

[13]

A. K. A. de Medeiros, W. M. P. van der Aalst, and A. J. M. M. Weijters. 2008. Quantifying process equivalence based on observed behavior. Data and Knowledge Engineering 64, 1, 55--74.

Digital Library

[14]

A. K. A. de Medeiros, A. J. M. M. Weijters, and W. M. P. van der Aalst. 2007. Genetic process mining: An experimental evaluation. Data Mining and Knowledge Discovery 14, 2, 245--304.

Digital Library

[15]

Josee Desharnais, Vineet Gupta, Radha Jagadeesan, and Prakash Panangaden. 2004. Metrics for labelled Markov processes. Theoretical Computer Science 318, 3, 323--354.

Digital Library

[16]

Johann Eder, Juergen Mangler, Enrico Mussi, and Barbara Pernici. 2009. Using stateful activities to facilitate monitoring and repair in workflow choreographies. In Proceeedings of the 2009 IEEE Congress on Services, Part I (SERVICES I’09). IEEE, Los Alamitos, CA, 219--226.

Digital Library

[17]

Dirk Fahland and Wil M. P. van der Aalst. 2015. Model repair—aligning process models to reality. Information Systems, 220--243.

Digital Library

[18]

Didier Fayard and Gérard Plateau. 1975. Resolution of the 0-1 knapsack problem: Comparison of methods. Mathematical Programming 8, 1, 272--307.

Digital Library

[19]

Gerhard Friedrich, Mariagrazia Fugini, Enrico Mussi, Barbara Pernici, and Gaston Tagni. 2010. Exception handling for repair in service-based processes. IEEE Transactions on Software Engineering 36, 2, 198--215.

Digital Library

[20]

Walid Gaaloul, Sami Bhiri, and Mohsen Rouached. 2010. Event-based design and runtime verification of composite service transactional behavior. IEEE Transactions on Services Computing 3, 1, 32--45.

Digital Library

[21]

Walid Gaaloul, Khaled Gaaloul, Sami Bhiri, Armin Haller, and Manfred Hauswirth. 2009. Log-based transactional workflow mining. Distributed and Parallel Databases 25, 3, 193--240.

Digital Library

[22]

E. M. Goldratt, J. Cox, and D. Whitford. 2012. The Goal: A Process of Ongoing Improvement. North River Press, Great Barrington, MA.

[23]

Gianluigi Greco, Antonella Guzzo, Francesco Lupia, and Luigi Pontieri. 2015. Process discovery under precedence constraints. ACM Transactions on Knowledge Discovery from Data 9, 4, 32.

Digital Library

[24]

Christian W. Günther and Wil M. P. van der Aalst. 2007. Fuzzy mining—adaptive process simplification based on multi-perspective metrics. In Business Process Management. Lecture Notes in Computer Science, Vol. 4714. Springer, 328--343.

Digital Library

[25]

Farhana Islam, Meherun Nesa Lucky, and Barbara Pernici. 2010. Business analysis of Web service repairability. In Proceedings of the 4th IEEE International Conference on Research Challenges in Information Science (RCIS’10). IEEE, Los Alamitos, CA, 463--472.

[26]

Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. IBM Research Symposia Series. Plenum Press, New York, NY, 85--103. http://www.cs.berkeley.edu/&sim;luca/cs172/karp.pdf.

[27]

Aline A. S. Leão, Luiz H. Cherri, and Marcos N. Arenales. 2014. Determining the k-best solutions of knapsack problems. Computers and Operations Research 49, 71--82.

[28]

Sander J. J. Leemans, Dirk Fahland, and Wil M. P. van der Aalst. 2013. Discovering block-structured process models from event logs containing infrequent behaviour. In Business Process Management. Lecture Notes in Business Information Processing, Vol. 171. Springer, 66--78.

[29]

Sander J. J. Leemans, Dirk Fahland, and Wil M. P. van der Aalst. 2015. In Enterprise, Business-Process and Information System Modeling. Lecture Notes in Business Information Processing, Vol. 214. Springer, 85--101.

[30]

Chen Li, Manfred Reichert, and Andreas Wombacher. 2009. Discovering reference models by mining process variants using a heuristic approach. In Business Process Management. Lecture Notes in Computer Science, Vol. 5701. Springer, 344--362.

[31]

Chen Li, Manfred Reichert, and Andreas Wombacher. 2010. The minadept clustering approach for discovering reference process models out of process variants. International Journal of Cooperative Information Systems 19, 3--4, 159--203.

[32]

Chen Li, Manfred Reichert, and Andreas Wombacher. 2011. Mining business process variants: Challenges, scenarios, algorithms. Data and Knowledge Engineering 70, 5, 409--434.

Digital Library

[33]

Felix Mannhardt, Massimiliano de Leoni, Hajo A. Reijers, and Wil M. P. van der Aalst. 2015. Balanced multi-perspective checking of process conformance. Computing 98, 4, 407--437.

Digital Library

[34]

Silvano Martello, David Pisinger, and Paolo Toth. 2000. New trends in exact algorithms for the 0-1 knapsack problem. European Journal of Operational Research 123, 2, 325--332.

[35]

Thomas Molka, David Redlich, Marc Drobek, Artur Caetano, Xiao-Jun Zeng, and Wasif Gilani. 2014. Conformance checking for BPMN-based process models. In Proceedings of the 29th Annual ACM Symposium on Applied Computing (SAC’14). ACM, New York, NY, 1406--1413.

Digital Library

[36]

Jorge Munoz-Gama and Josep Carmona. 2011. Enhancing precision in process conformance: Stability, confidence and severity. In Proceedings of the IEEE Symposium on Computational Intelligence and Data Mining (CIDM’11). IEEE, Los Alamitos, CA, 184--191.

[37]

Jorge Munoz-Gama, Josep Carmona, and Wil M. P. van der Aalst. 2013a. Conformance checking in the large: Partitioning and topology. In Business Process Management. Lecture Notes in Computer Science, Vol. 8094. Springer, 130--145.

Digital Library

[38]

Jorge Munoz-Gama, Josep Carmona, and Wil M. P. van der Aalst. 2013b. Hierarchical conformance checking of process models based on event logs. In Application and Theory of Petri Nets and Concurrency. Springer, 291--310.

Digital Library

[39]

Mike P. Papazoglou. 2003. Service-oriented computing: Concepts, characteristics and directions. In Proceedings of the 4th International Conference on Web Information Systems Engineering (WISE’03). IEEE, Los Alamitos, CA, 3--12.

Digital Library

[40]

Artem Polyvyanyy. 2012. Structuring Process Models. Ph.D. Dissertation. University of Potsdam. http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-59024.

[41]

Artem Polyvyanyy and Christoph Bussler. 2013. The structured phase of concurrency. In Seminal Contributions to Information Systems Engineering, 25 Years of CAiSE, J. A. Bubenko Jr., J. Krogstie, O. Pastor, B. Pernici, C. Rolland, and A. Sølvberg (Eds.). Springer, 257--263.

[42]

Artem Polyvyanyy, Jussi Vanhatalo, and Hagen Völzer. 2011. Simplified computation and generalization of the refined process structure tree. In Web Services and Formal Methods. Lecture Notes in Computer Science, Vol. 6551. Springer, 25--41.

Digital Library

[43]

Artem Polyvyanyy, Matthias Weidlich, and Mathias Weske. 2012. Isotactics as a foundation for alignment and abstraction of behavioral models. In Business Process Management. Lecture Notes in Computer Science, Vol. 7481. Springer, 335--351.

Digital Library

[44]

Wolfgang Reisig. 1998. Elements of Distributed Algorithms: Modeling and Analysis with Petri Nets. Springer-Verlag, Berlin, Germany. http://www.springer.com/computer/theoretical+computer+science/book/978-3-540-62752-4.

Digital Library

[45]

Anne Rozinat and Wil M. P. van der Aalst. 2008. Conformance checking of processes based on monitoring real behavior. Information Systems 33, 1, 64--95.

Digital Library

[46]

Wil M. P. van der Aalst. 1997. Verification of workflow nets. In Application and Theory of Petri Nets 1997. Lecture Notes in Computer Science, Vol. 1248. Springer, 407--426.

Digital Library

[47]

Wil M. P. van der Aalst. 2011. Process Mining: Discovery, Conformance and Enhancement of Business Processes. Springer-Verlag, Berlin, Germany. http://www.springer.com/gp/book/9783642193446

[48]

Wil M. P. van der Aalst. 2013. Decomposing Petri nets for process mining: A generic approach. Distributed and Parallel Databases 31, 4, 471--507.

Digital Library

[49]

Wil M. P. van der Aalst, Arya Adriansyah, and Boudewijn F. van Dongen. 2012. Replaying history on process models for conformance checking and performance analysis. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 2, 2, 182--192.

Digital Library

[50]

Wil M. P. van der Aalst, Kees M. van Hee, Jan Martijn E. M. van der Werf, and Marc Verdonk. 2010. Auditing 2.0: Using process mining to support tomorrow’s auditor. IEEE Computer 43, 3, 90--93.

Digital Library

[51]

Wil M. P. van der Aalst, A. J. M. M. Weijters, and Laura Maruster. 2004. Workflow mining: Discovering process models from event logs. IEEE Transactions on Knowledge and Data Engineering 16, 9, 1128--1142.

Digital Library

[52]

Boudewijn F. van Dongen, Ana Karla Alves de Medeiros, H. M. W. Verbeek, A. J. M. M. Weijters, and Wil M. P. van der Aalst. 2005. The ProM framework: A new era in process mining tool support. In Applications and Theory of Petri Nets 2005. Lecture Notes in Computer Science, Vol. 3536. Springer, 444--454.

Digital Library

[53]

Rob J. van Glabbeek. 1990. The linear time-branching time spectrum (extended abstract). In Proceedings on Theories of Concurrency: Unification and Extension (CONCUR’90). 278--297.

Digital Library

[54]

Pamela H. Vance. 1993. Knapsack problems: Algorithms and computer implementations. SIAM Review 35, 4, 684--685. http://dx.doi.org/10.1137/1035174

[55]

Jussi Vanhatalo, Hagen Völzer, and Jana Koehler. 2009. The refined process structure tree. Data and Knowledge Engineering 68, 9, 793--818.

Digital Library

[56]

H. M. W. Verbeek, J. C. A. M. Buijs, B. F. van Dongen, and W. M. P. van der Aalst. 2011. XES, XESame, and ProM 6. In Information Systems Evolution. Lecture Notes in Computer Science, Vol. 72. Springer, 60--75.

[57]

A. J. M. M. Weijters, W. M. P. van der Aalst, and A. K. A. de Medeiros. 2006. Process Mining with the Heuristics Miner-Algorithm. Technical Report WP 166. Technische Universiteit Eindhoven.

[58]

Franz Wotawa. 2001. A variant of Reiter’s hitting-set algorithm. Information Processing Letters 79, 1, 45--51.

Digital Library

Cited By

Genga LRossi FDiamantini CStorti EPotena D(2024)Model repair supported by frequent anomalous local instance graphsInformation Systems10.1016/j.is.2024.102349122:COnline publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1016/j.is.2024.102349
Su ZPolyvyanyy ALipovetzky NSardiña Svan Beest N(2024)Adaptive goal recognition using process mining techniquesEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.108189133(108189)Online publication date: Jul-2024
https://doi.org/10.1016/j.engappai.2024.108189
Chiariello FIelo ATarzariol A(2024)An ILASP-Based Approach to Repair Petri NetsLogic Programming and Nonmonotonic Reasoning10.1007/978-3-031-74209-5_7(85-97)Online publication date: 9-Oct-2024
https://doi.org/10.1007/978-3-031-74209-5_7
Show More Cited By

Index Terms

Impact-Driven Process Model Repair

Recommendations

Interactive and Incremental Business Process Model Repair
On the Move to Meaningful Internet Systems. OTM 2017 Conferences
Abstract
It is common for the observed behavior of a business process to differ from the behavior captured in its corresponding model, as workers devise workarounds to handle special circumstances, which over time become part of the norm. Process model ...
On the use of domain knowledge for process model repair
Abstract
Process models are important for supporting organizations in documenting, understanding and monitoring their business. When these process models become outdated, they need to be revised to accurately describe the new status quo of the processes in ...
Model repair - aligning process models to reality

Process mining techniques relate observed behavior (i.e., event logs) to modeled behavior (e.g., a BPMN model or a Petri net). Process models can be discovered from event logs and conformance checking techniques can be used to detect and diagnose ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Software Engineering and Methodology

ACM Transactions on Software Engineering and Methodology Volume 25, Issue 4

May 2017

183 pages

ISSN:1049-331X

EISSN:1557-7392

DOI:10.1145/3007747

Editor:
David S. Rosenblum
National University of Singapore, Singapore

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 October 2016

Accepted: 01 June 2016

Revised: 01 April 2016

Received: 01 September 2015

Published in TOSEM Volume 25, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Australian Research Council's Discovery

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

56
Total Citations
View Citations
857
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)6

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Genga LRossi FDiamantini CStorti EPotena D(2024)Model repair supported by frequent anomalous local instance graphsInformation Systems10.1016/j.is.2024.102349122:COnline publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1016/j.is.2024.102349
Su ZPolyvyanyy ALipovetzky NSardiña Svan Beest N(2024)Adaptive goal recognition using process mining techniquesEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.108189133(108189)Online publication date: Jul-2024
https://doi.org/10.1016/j.engappai.2024.108189
Chiariello FIelo ATarzariol A(2024)An ILASP-Based Approach to Repair Petri NetsLogic Programming and Nonmonotonic Reasoning10.1007/978-3-031-74209-5_7(85-97)Online publication date: 9-Oct-2024
https://doi.org/10.1007/978-3-031-74209-5_7
Vinci Fde Leoni M(2024)Repairing Process Models Through Simulation and Explainable AIBusiness Process Management10.1007/978-3-031-70396-6_8(129-145)Online publication date: 2-Sep-2024
https://doi.org/10.1007/978-3-031-70396-6_8
Grohs Mvan der Aa HRehse J(2024)Beyond Log and Model Moves in Conformance Checking: Discovering Process-Level Deviation PatternsBusiness Process Management10.1007/978-3-031-70396-6_22(381-399)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70396-6_22
Guan WCao JGu YQian S(2023)AIMED: An automatic and incremental approach for business process model repair under concept driftInformation Systems10.1016/j.is.2023.102285119(102285)Online publication date: Oct-2023
https://doi.org/10.1016/j.is.2023.102285
Schuster DFöcking Nvan Zelst Svan der Aalst W(2023)Incremental Discovery of Process Models Using Trace FragmentsBusiness Process Management10.1007/978-3-031-41620-0_4(55-73)Online publication date: 11-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-41620-0_4
Huang Tvan der Aalst W(2023)Unblocking Inductive MinerEnterprise, Business-Process and Information Systems Modeling10.1007/978-3-031-34241-7_23(327-342)Online publication date: 31-May-2023
https://doi.org/10.1007/978-3-031-34241-7_23
Shahzadi SFang XShahzad UAhmad IBenedict T(2022)Repairing Event Logs to Enhance the Performance of a Process Mining ModelMathematical Problems in Engineering10.1155/2022/47412322022(1-10)Online publication date: 26-Aug-2022
https://doi.org/10.1155/2022/4741232
Song WChang ZJacobsen HZhang P(2022)Discovering Structural Errors From Business Process Event LogsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.305292734:11(5293-5306)Online publication date: 1-Nov-2022
https://doi.org/10.1109/TKDE.2021.3052927
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents