Abstract
Process discovery is the problem of automatically constructing a process model from an event log of an information system that supports the execution of a business process in an organisation. In this paper, we study how to construct models that, in addition to the control flow of the process, capture the importance, in terms of probabilities, of various execution scenarios of the process. Such probabilistic aspects of the process are instrumental in understanding the process and to predict aspects of its future. We formally define the problem of stochastic process discovery, which aims to describe the processes captured in the event log. We study several implications of this definition, and introduce two discovery techniques that return optimal solutions in the presence and absence of a model of the control flow of the process. The proposed discovery techniques have been implemented and are publicly available. Finally, we evaluate the feasibility and applicability of the new techniques and show that their models outperform models constructed using existing stochastic discovery techniques.
M. Montali—This work is partially supported by the UNIBZ project ADAPTERS and the PRIN MIUR project PINPOINT Prot. 2020FNEB27.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We use entropic relevance that relies on the uniform background coding model [2].
- 2.
- 3.
References
van der Aalst, W.M.P.: Process Mining - Data Science in Action, 2nd edn. Springer, Cham (2016)
Alkhammash, H., Polyvyanyy, A., Moffat, A., García-Bañuelos, L.: Entropic relevance: a mechanism for measuring stochastic process models discovered from event data. Inf. Syst. 107, 101922 (2022)
Bause, F., Kritzinger, P.S.: Stochastic Petri Nets - An Introduction to the Theory, 2nd edn. Vieweg, Braunschweig (2002)
Bergami, G., Maggi, F.M., Montali, M., Peñaloza, R.: Probabilistic trace alignment. In: ICPM. IEEE (2021)
Brockhoff, T., Uysal, M.S., van der Aalst, W.M.P.: Time-aware concept drift detection using the earth mover’s distance. In: ICPM. IEEE (2020)
Burke, A., Leemans, S.J.J., Wynn, M.T.: Stochastic process discovery by weight estimation. In: Leemans, S., Leopold, H. (eds.) Process Mining Workshops. Lecture Notes in Business Information Processing, vol. 406, pp. 260–272. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-72693-5_20
Burke, A., Leemans, S.J.J., Wynn, M.T.: Discovering stochastic process models by reduction and abstraction. In: Buchs, D., Carmona, J. (eds.) Application and Theory of Petri Nets and Concurrency. Lecture Notes in Computer Science(), vol. 12734, pp. 312–336. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-76983-3_16
Jansen, N., Junges, S., Katoen, J.: Parameter synthesis in Markov models: a gentle survey. In: Raskin, J.F., Chatterjee, K., Doyen, L., Majumdar, R. (eds.) Principles of Systems Design. Lecture Notes in Computer Science, vol. 13660, pp. 407–437. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22337-2_20
Leemans, S.J.J., Fahland, D., van der Aalst, W.M.P.: Discovering block-structured process models from incomplete event logs. In: Ciardo, G., Kindler, E. (eds.) Application and Theory of Petri Nets and Concurrency. Lecture Notes in Computer Science, vol. 8489, pp. 91–110. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07734-5_6
Leemans, S.J.J., Maggi, F.M., Montali, M.: Reasoning on labelled Petri nets and their dynamics in a stochastic setting. In: Di Ciccio, C., Dijkman, R., del Rio Ortega, A., Rinderle-Ma, S. (eds.) Business Process Management. Lecture Notes in Computer Science, vol. 13420, pp. 324–342. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-16103-2_22
Leemans, S.J.J., Maggi, F.M., Montali, M.: Enjoy the silence: analysis of stochastic Petri nets with silent transitions. CoRR abs/2306.06376 (2023)
Leemans, S.J.J., Mannel, L.L., Sidorova, N.: Significant stochastic dependencies in process models. Inf. Syst. 118, 102223 (2023)
Leemans, S.J.J., Poppe, E., Wynn, M.T.: Directly follows-based process mining: exploration & a case study. In: ICPM. IEEE (2019)
Leemans, S.J.J., Syring, A.F., van der Aalst, W.M.P.: Earth movers’ stochastic conformance checking. In: Hildebrandt, T., van Dongen, B., Roglinger, M., Mendling, J. (eds.) Business Process Management Forum. Lecture Notes in Business Information Processing, vol. 360, pp. 127–143. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26643-1_8
Marsan, M.A., Conte, G., Balbo, G.: A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems. ACM Trans. Comput. Syst. 2(2), 93–122 (1984)
Mazak, A., Wolny, S., Wimmer, M.: On the need for data-based model-driven engineering. In: Biffl, S., Eckhart, M., Luder, A., Weippl, E. (eds.) Security and Quality in Cyber-Physical Systems Engineering, pp. 103–127. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25312-7_5
Molloy, M.K.: Performance analysis using stochastic Petri nets. IEEE Trans. Comput. 31(9) (1982)
Polyvyanyy, A., Moffat, A., García-Bañuelos, L.: An entropic relevance measure for stochastic conformance checking in process mining. In: ICPM. IEEE (2020)
Rogge-Solti, A., van der Aalst, W.M.P., Weske, M.: Discovering stochastic Petri nets with arbitrary delay distributions from event logs. In: Lohmann, N., Song, M., Wohed, P. (eds.) Business Process Management Workshops. Lecture Notes in Business Information Processing, vol. 171, pp. 15–27. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-06257-0_2
Tax, N., Lu, X., Sidorova, N., Fahland, D., van der Aalst, W.M.P.: The imprecisions of precision measures in process mining. Inf. Process. Lett. 135, 1–8 (2018)
van der Werf, J.M.E.M., van Dongen, B.F., Hurkens, C.A.J., Serebrenik, A.: Process discovery using integer linear programming. Fundam. Inform. 94(3-4) (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Leemans, S.J.J., Li, T., Montali, M., Polyvyanyy, A. (2024). Stochastic Process Discovery: Can It Be Done Optimally?. In: Guizzardi, G., Santoro, F., Mouratidis, H., Soffer, P. (eds) Advanced Information Systems Engineering. CAiSE 2024. Lecture Notes in Computer Science, vol 14663. Springer, Cham. https://doi.org/10.1007/978-3-031-61057-8_3
Download citation
DOI: https://doi.org/10.1007/978-3-031-61057-8_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-61056-1
Online ISBN: 978-3-031-61057-8
eBook Packages: Computer ScienceComputer Science (R0)