Automated Repair of Process Models with Non-local Constraints Using State-Based Region Theory

• Autorzy: Kalenkova Anna , Polyvyanyy Artem , Carmona Josep , La Rosa Marcello

Identyfikatory

DOI

10.3233/FI-2021-2089

• Języki publikacji: EN

Abstrakty

EN

State-of-the-art process discovery methods construct free-choice process models from event logs. Consequently, the constructed models do not take into account indirect dependencies between events. Whenever the input behaviour is not free-choice, these methods fail to provide a precise model. In this paper, we propose a novel approach for enhancing free-choice process models by adding non-free-choice constructs discovered a-posteriori via region-based techniques. This allows us to benefit from the performance of existing process discovery methods and the accuracy of the employed fundamental synthesis techniques. We prove that the proposed approach preserves fitness with respect to the event log while improving the precision when indirect dependencies exist. The approach has been implemented and tested on both synthetic and real-life datasets. The results show its effectiveness in repairing models discovered from event logs.

Słowa kluczowe

EN

free-choice Petri nets; region state-based synthesis; event logs; transition systems; process mining; process enhancement

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 183, nr 3-4
• Strony: 293--317
• Opis fizyczny: Bibliogr 44 poz., rys., tab.

Twórcy

autor

Kalenkova Anna

• School of Computing and Information Systems The University of Melbourne, Australia

autor

Polyvyanyy Artem

• School of Computing and Information Systems The University of Melbourne, Australia

autor

Carmona Josep

• Department of Computer Science Polytechnic University of Catalonia, Spain

autor

La Rosa Marcello

• School of Computing and Information Systems The University of Melbourne, Australia

Bibliografia

• [1] van der Aalst W. Process mining: data science in action. Springer, 2016. ISBN 978-3-662-49850-7.
• [2] Carmona J, van Dongen B, Solti A, Weidlich M. Conformance checking - relating processes and models. Springer, 2018. ISBN:978-3-319-99413-0.
• [3] OMG. Business Process Model and Notation (BPMN), Version 2.0.2, 2013. URL http://www.omg.org/spec/BPMN/2.0.2.
• [4] Leemans S, Fahland D, van der Aalst W. Discovering block-structured process models from incomplete event logs. In: ATPN’2014, volume 8489 of LNCS, pp. 91-110. Springer, 2014. doi:10.1007/978-3-319-07734-5 6.
• [5] Augusto A, Conforti R, Dumas M, La Rosa M, Polyvyanyy A. Split Miner: Automated discovery of accurate and simple business process models from event logs. Knowl. Inf. Syst., 2019. 59(2):251-284. doi:10.1007/s10115-018-1214-x.
• [6] Desel J, Esparza J. Free choice Petri nets. Cambridge University Press, USA, 1995. ISBN:0521465192.
• [7] Kalenkova A, van der Aalst W, Lomazova I, Rubin V. Process mining using BPMN: Relating event logs and process models process mining using BPMN. Software and Systems Modeling, 2017. 16:1019-1048. doi:10.1007/s10270-015-0502-0.
• [8] Wen L, Aalst W, Wang J, Sun J. Mining process models with non-free-choice constructs. Data Min. Knowl. Discov., 2007. 15(2):145-180. doi:10.1007/s10618-007-0065-y.
• [9] Carmona J, Cortadella J, Kishinevsky M. A region-based algorithm for discovering Petri nets from event logs. In: Business Process Management. Springer Berlin Heidelberg, Berlin, Heidelberg. 2008 pp. 358-373. ISBN:978-3-540-85758-7.
• [10] van der Aalst W, Rubin V, Verbeek H, van Dongen B, Kindler E, G¨unther C. Process mining: a two-step approach to balance between underfitting and overfitting. Software & Systems Modeling, 2010. 9(1):87. doi:10.1007/s10270-008-0106-z.
• [11] Solé M, Carmona J. Process mining from a basis of state regions. In: Proceedings of the 31st International Conference on Applications and Theory of Petri Nets, PETRI NETS’10. Springer-Verlag, Berlin, Heidelberg. 2010 p. 226-245. ISBN:3642136745.
• [12] van der Werf J, van Dongen B, Hurkens C, Serebrenik A. Process discovery using integer linear programming. In: Applications and Theory of Petri Nets. Springer Berlin Heidelberg, Berlin, Heidelberg. 2008 pp. 368-387. ISBN:978-3-540-68746-7.
• [13] Bergenthum R. Prime miner - process discovery using prime event structures. In: 2019 International Conference on Process Mining (ICPM). 2019 pp. 41-48. doi:10.1109/ICPM.2019.00017.
• [14] van Zelst S, van Dongen B, van der Aalst W, Verbeek H. Discovering workflow nets using integer linear programming. Computing, 2018. 100(5):529-556. doi:10.1007/s00607-017-0582-5.
• [15] Mannel L, van der Aalst W. Finding uniwired Petri nets using eST-Miner. In: Business Process Management Workshops. Springer International Publishing, Cham. 2019 pp. 224-237. ISBN:978-3-030-37453-2.
• [16] Mannel L, van der Aalst W. Finding complex process-structures by exploiting the token-game. In: 40th International Conference, PETRI NETS’19, Proceedings, volume 11522 of Lecture Notes in Computer Science. Springer, 2019 pp. 258-278. doi:10.1007/978-3-030-21571-2_15.
• [17] Badouel E, Bernardinello L, Darondeau P. Petri net synthesis. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2015. ISBN:978-3-662-47966-7.
• [18] Bergenthum R, Desel J, Lorenz R, Mauser S. Synthesis of Petri nets from finite partial languages. Fundam. Inform., 2008. 88(4):437-468.
• [19] Best E, Devillers R, Schlachter U. A graph-theoretical characterisation of state separation. In: SOFSEM - 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. 2017 pp. 163-175. doi:10.1007/978-3-319-51963-0_13.
• [20] Schlachter U, Wimmel H. A geometric characterisation of event/state separation. In: Application and Theory of Petri Nets and Concurrency - 39th International Conference, PETRI NETS’18, Proceedings. 2018 pp. 99-116.
• [21] Polyvyanyy A, van der Aalst W, ter Hofstede A, Wynn M. Impact-driven process model repair. ACM Trans. Softw. Eng. Methodol., 2016. 25(4). doi:10.1145/2980764.
• [22] Armas-Cervantes A, van Beest N, La Rosa M, Dumas M, Garc´ıa-Ba˜nuelos L. Interactive and incremental business process model repair. In: On the Move to Meaningful Internet Systems. OTM 2017 Conferences. Springer International Publishing, Cham. 2017 pp. 53-74. ISBN:978-3-319-69462-7. doi:10.1007/978-3-319-69462-7_5.
• [23] Fahland D, van der Aalst W. Model repair — aligning process models to reality. Information Systems, 2015. 47:220-243. doi:10.1016/j.is.2013.12.007.
• [24] Mitsyuk A, Lomazova I, Shugurov I, van der Aalst W. Process model repair by detecting unfitting fragments. In: AIST 2017, CEUR Workshop Proceedings. 2017 pp. 301-313. doi:d429471f542a45f09a62131cf704e730.
• [25] La Rosa M, Reijers H, van Der Aalst W, Dijkman R, Mendling J, Dumas M, Garcıa-Banuelos L. APROMORE: An advanced process model repository. Expert Systems with Applications, 2011. 38(6):7029-7040. doi:10.1016/j.eswa.2010.12.012.
• [26] Kalenkova A, Carmona J, Polyvyanyy A, La Rosa M. Automated repair of process models using non-local constraints. In: 41st International Conference, PETRI NETS’20, Proceedings, volume 12152 of Lecture Notes in Computer Science. Springer, 2020 pp. 280-300.
• [27] Cortadella J, Kishinevsky M, Lavagno L, Yakovlev A. Deriving Petri nets from finite transition systems. IEEE Transactions on Computers, 1998. 47(8):859-882. doi:10.1109/12.707587.
• [28] Carmona J, Cortadella J, Kishinevsky M. New region-based algorithms for deriving bounded Petri nets. IEEE Trans. Computers, 2010. 59(3):371-384. doi:10.1109/TC.2009.131.
• [29] Hopcroft J, Ullman J. An n log n algorithm for detecting reducible graphs. In: Proe. 6th Annual Princeton Conf. on Inf. Sciences and Systems. 1972 pp. 119-122.
• [30] van der Aalst W, Hirnschall A, Verbeek H. An alternative way to analyze workflow graphs. In: Advanced Information Systems Engineering. Springer Berlin Heidelberg. 2002 pp. 535-552. ISBN:978-3-540-47961-1. doi:10.1007/3-540-47961-9 37.
• [31] Desel J, Reisig W. The synthesis problem of Petri nets. Acta Inf., 1996. 33(4):297-315. doi:10.1007/s002360050046.
• [32] Cortadella J, Kishinevsky M, Lavagno L, Yakovlev A. Deriving Petri nets from finite transition systems. IEEE Transactions on Computers, 1998. 47(8):859-882.
• [33] Reisig W. Petri nets: An introduction. Springer-Verlag, Berlin, Heidelberg, 1985. ISBN:0387137238. doi:10.5555/3405.
• [34] Favre C, Fahland D, V¨olzer H. The relationship between workflow graphs and free-choice work-flow nets. Information Systems, 2015. 47:197 – 219.
• [35] Meyer A, Pufahl L, Fahland D, Weske M. Modeling and enacting complex data dependencies in business processes. 2013 pp. 171-186. In: Business Process Management. Springer Berlin Heidelberg. ISBN:978-3-642-40176-3. doi:10.1007/978-3-642-40176-3 14.
• [36] Kalenkova A, Burattin A, de Leoni M, van der Aalst W, Sperduti A. Discovering high-level BPMN process models from event data. Business Process Management Journal, 2019. 25(5):995-1019. doi:10.1108/BPMJ-02-2018-0051.
• [37] Polyvyanyy A, Solti A, Weidlich M, Di Ciccio C, Mendling J. Monotone precision and recall measures for comparing executions and specifications of dynamic systems. ACM Trans. Softw. Eng. Methodol., 2020. 29(3):1-41. doi:10.1145/3387909.
• [38] van Dongen B. BPI challenge 2020: Domestic declarations, 2020. doi:10.4121/uuid:3f422315-ed9d-4882-891f-e180b5b4feb5.
• [39] van Dongen B. BPI challenge 2020: Prepaid travel costs, 2020. doi:10.4121/uuid:5d2fe5e1-f91f-4a3b-ad9b-9e4126870165.
• [40] van Dongen B. BPI challenge 2020: Request for payment, 2020. doi:10.4121/uuid:895b26fb-6f25-46eb-9e48-0dca26fcd030.
• [41] Mannhardt F. Hospital billing - event log, 2017. doi:10.4121/uuid:76c46b83- c930-4798-a1c9-4be94dfeb741. A. Kalenkova et al. / Automated Repair of Proc. Models Using Non-local Constr. 317
• [42] de Leoni M, Mannhardt F. Road traffic fine management process, 2015. doi:10.4121/uuid:270fd440-1057-4fb9-89a9-b699b47990f5.
• [43] Buijs J. Receipt phase of an environmental permit application process (‘WABO’), CoSeLoG project, 2014. doi:10.4121/uuid:a07386a5-7be3-4367-9535-70bc9e77dbe6.
• [44] van Dongen B. BPI challenge 2014: Activity log for incidents, 2014. doi:10.4121/uuid:86977bac-f874-49cf-8337-80f26bf5d2ef.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)