Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Discovering Stochastic Process Models by Reduction and Abstraction

  • Conference paper
  • First Online:
Application and Theory of Petri Nets and Concurrency (PETRI NETS 2021)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12734))

Abstract

In process mining, extensive data about an organizational process is summarized by a formal mathematical model with well-grounded semantics. In recent years a number of successful algorithms have been developed that output Petri nets, and other related formalisms, from input event logs, as a way of describing process control flows. Such formalisms are inherently constrained when reasoning about the probabilities of the underlying organizational process, as they do not explicitly model probability. Accordingly, this paper introduces a framework for automatically discovering stochastic process models, in the form of Generalized Stochastic Petri Nets. We instantiate this Toothpaste Miner framework and introduce polynomial-time batch and incremental algorithms based on reduction rules. These algorithms do not depend on a preceding control-flow model. We show the algorithms terminate and maintain a deterministic model once found. An implementation and evaluation also demonstrate feasibility.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Source code is accessible at https://github.com/adamburkegh/toothpaste.

  2. 2.

    BPIC2013 and sepsis logs: https://data.4tu.nl/. Teleclaims: http://www.processmining.org/event_logs_and_models_used_in_book.

  3. 3.

    Full results are available at https://github.com/adamburkegh/toothpaste.

References

  1. van der Aalst, W.: Process Mining: Data Science in Action, 2nd edn. Springer-Verlag, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49851-4_1

    Book  Google Scholar 

  2. Anastasiou, N., Horng, T.C., Knottenbelt, W.: Deriving generalised stochastic Petri net performance models from high-precision location tracking data. In: Proceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools, pp. 91–100. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering) (2011)

    Google Scholar 

  3. Baum, L.E., Petrie, T., Soules, G., Weiss, N.: A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains. Ann. Math. Stat. 41(1), 164–171 (1970), publisher: JSTOR

    Google Scholar 

  4. Bause, F., Kritzinger, P.: Stochastic Petri Nets: An Introduction to the Theory. Vieweg+Teubner Verlag (2002)

    Google Scholar 

  5. Bellodi, E., Riguzzi, F., Lamma, E.: Statistical relational learning for workflow mining. Intell. Data Anal. 20(3), 515–541 (2016)

    Article  Google Scholar 

  6. Berti, A., van Zelst, S.J., van der Aalst, W.M.P.: Process mining for python (PM4Py) : bridging the gap between process- and data science. In: ICPMD 2019, ICPM Demo Track 2019 : proceedings of the ICPM Demo Track 2019, co-located with 1st International Conference on Process Mining (ICPM 2019) : Aachen, Germany, 24–26 June 2019 / edited by Andrea Burattin (Technical University of Denmark, Kgs. Lyngby, Denmark), Artem Polyvyanyy (The University of Melbourne, Melbourne, Australia), Sebastiaan van Zelst (Fraunhofer Institute for Applied Information Technology (FIT), Sankt Augustin, Germany). CEUR workshop proceedings, vol. 2374, pp. 13–16. RWTH Aachen, Aachen, Germany (June 2019), backup Publisher: 1st International Conference on Process Mining, Aachen (Germany), 24 June 2019–24 June 2019

    Google Scholar 

  7. Bezem, M., Klop, J., Barendsen, E., de Vrijer, R., Terese: Term Rewriting Systems. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge (2003)

    Google Scholar 

  8. Breuker, D., Matzner, M., Delfmann, P., Becker, J.: Comprehensible Predictive Models for Business Processes. MIS Q. 40(4), 1009–1034 (2016)

    Article  Google Scholar 

  9. Burke, A., Leemans, S.J.J., Wynn, M.T.: Stochastic process discovery by weight estimation. In: 2020 International Conference on Process Mining (ICPM) press (2020)

    Google Scholar 

  10. Carmona, J., Cortadella, J., Kishinevsky, M.: New region-based algorithms for deriving bounded petri nets. IEEE Trans. Comput. 59(3), 371–384 (2010)

    Article  MathSciNet  Google Scholar 

  11. Carrasco, R.C.: Accurate computation of the relative entropy between stochastic regular grammars. RAIRO-Theor. Inform. Appl. 31(5), 437–444 (1997)

    Article  MathSciNet  Google Scholar 

  12. Carrasco, R.C., Oncina, J.: Learning stochastic regular grammars by means of a state merging method. In: Carrasco, R.C., Oncina, J. (eds.) ICGI 1994. LNCS, vol. 862, pp. 139–152. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-58473-0_144

    Chapter  MATH  Google Scholar 

  13. Fünfgeld, S., Holzäpfel, M., Frey, M., Gauterin, F.: Stochastic forecasting of vehicle dynamics using sequential Monte Carlo simulation. IEEE Trans. Intell. Veh. 2(2), 111–122 (2017)

    Google Scholar 

  14. Geman, S., Geman, D.: Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-6(6), 721–741 (1984)

    Google Scholar 

  15. Hu, H., Xie, J., Hu, H.: A novel approach for mining stochastic process model from workflow logs. J. Comput. Inf. Syst. 7(9), 3113–3126 (2011)

    Google Scholar 

  16. Janssenswillen, G., Depaire, B., Faes, C.: Enhancing discovered process models using Bayesian inference and MCMC. In: Proceedings of the 2020 BPI Workshop (2020)

    Google Scholar 

  17. Leclercq, E., Lefebvre, D., El Medhi, S.O.: Identification of timed stochastic petri net models with normal distributions of firing periods. IFAC Proc. 42(4), 948–953 (2009)

    Article  Google Scholar 

  18. Leemans, S.J.J., Fahland, D., van der Aalst, W.M.P.: Scalable process discovery with guarantees. In: Gaaloul, K., Schmidt, R., Nurcan, S., Guerreiro, S., Ma, Q. (eds.) CAISE 2015. LNBIP, vol. 214, pp. 85–101. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-19237-6_6

    Chapter  Google Scholar 

  19. Leemans, S.J.J., Polyvyanyy, A.: Stochastic-aware conformance checking: an entropy-based approach. In: Dustdar, S., Yu, E., Salinesi, C., Rieu, D., Pant, V. (eds.) CAiSE 2020. LNCS, vol. 12127, pp. 217–233. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-49435-3_14

    Chapter  Google Scholar 

  20. Leemans, S.J.J., Fahland, D., van der Aalst, W.M.P.: Discovering block-structured process models from event logs - a constructive approach. In: Colom, J.-M., Desel, J. (eds.) PETRI NETS 2013. LNCS, vol. 7927, pp. 311–329. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38697-8_17

    Chapter  Google Scholar 

  21. Leemans, S.J., Poppe, E., Wynn, M.T.: Directly follows-based process mining: exploration & a case study. In: 2019 International Conference on Process Mining (ICPM), pp. 25–32, June 2019

    Google Scholar 

  22. Leemans, S.J.J., Syring, A.F., van der Aalst, W.M.P.: Earth movers’ stochastic conformance checking. In: Hildebrandt, T., van Dongen, B.F., Röglinger, M., Mendling, J. (eds.) BPM 2019. LNBIP, vol. 360, pp. 127–143. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26643-1_8

    Chapter  Google Scholar 

  23. Liesaputra, V., Yongchareon, S., Chaisiri, S.: Efficient process model discovery using maximal pattern mining. In: Motahari-Nezhad, H.R., Recker, J., Weidlich, M. (eds.) BPM 2015. LNCS, vol. 9253, pp. 441–456. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23063-4_29

    Chapter  Google Scholar 

  24. Maggi, F.M., Montali, M., Peñaloza, R.: Probabilistic conformance checking based on declarative process models. In: Herbaut, N., La Rosa, M. (eds.) CAiSE 2020. LNBIP, vol. 386, pp. 86–99. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-58135-0_8

    Chapter  Google Scholar 

  25. Marsan, M.A., Balbo, G., Bobbio, A., Chiola, G., Conte, G., Cumani, A.: The effect of execution policies on the semantics and analysis of stochastic Petri nets. IEEE Trans. Softw. Eng. 15(7), 832–846 (1989)

    Article  MathSciNet  Google Scholar 

  26. Matsuno, H., Doi, A., Nagasaki, M., Miyano, S.: Hybrid petri net representation of gene regulatory network. In: Biocomputing 2000, pp. 341–352. World Scientific, December 1999

    Google Scholar 

  27. Mokhov, A., Carmona, J., Beaumont, J.: Mining conditional partial order graphs from event logs. In: Koutny, M., Desel, J., Kleijn, J. (eds.) Transactions on Petri Nets and Other Models of Concurrency XI. LNCS, vol. 9930, pp. 114–136. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53401-4_6

    Chapter  Google Scholar 

  28. Moreira, C., Haven, E., Sozzo, S., Wichert, A.: Process mining with real world financial loan applications: improving inference on incomplete event logs. PLOS ONE 13(12), e0207806 (2018)

    Google Scholar 

  29. Polyvyanyy, A., Moffat, A., García-Bañuelos, L.: An Entropic Relevance Measure for Stochastic Conformance Checking in Process Mining. arXiv e-prints 2007. arXiv:2007.09310 (Jul 2020)

  30. 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.) BPM 2013. LNBIP, vol. 171, pp. 15–27. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-06257-0_2

    Chapter  Google Scholar 

  31. Rogge-Solti, A., Weske, M.: Prediction of business process durations using non-Markovian stochastic Petri nets. Inf. Syst. 54, 1–14 (2015)

    Article  Google Scholar 

  32. Secretary, I.C.: Information technology - Z formal specification notation - Syntax, type system and semantics. Standard, International Organization for Standardization, Geneva, CH (March 2002), volume: (2002)

    Google Scholar 

  33. Silva, R., Zhang, J., Shanahan, J.G.: Probabilistic workflow mining. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, pp. 275–284. KDD 2005. Association for Computing Machinery, Chicago, Illinois, USA, August 2005

    Google Scholar 

  34. 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). https://doi.org/10.1016/j.ipl.2018.01.013

  35. Thierry-Mieg, Y.: Structural reductions revisited. In: Janicki, R., Sidorova, N., Chatain, T. (eds.) PETRI NETS 2020. LNCS, vol. 12152, pp. 303–323. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-51831-8_15

    Chapter  Google Scholar 

  36. Thollard, F., Dupont, P., De La Higuera, C.: Probabilistic DFA inference using Kullback-Leibler divergence and minimality, pp. 975–982, June 2000

    Google Scholar 

  37. Verwer, S., Eyraud, R., De La Higuera, C.: PAutomaC: a probabilistic automata and hidden Markov models learning competition. Mach. Learn. 96(1–2), 129–154 (2014)

    Article  MathSciNet  Google Scholar 

  38. Vidal, E., Thollard, F., de la Higuera, C., Casacuberta, F., Carrasco, R.: Probabilistic finite-state machines - part II. IEEE Trans. Pattern Anal. Mach. Intell. 27(7), 1026–1039 (2005)

    Article  Google Scholar 

  39. Vidal, E., Thollard, F., Higuera, C.d.l., Casacuberta, F., Carrasco, R.C.: Probabilistic finite-state machines - part I. IEEE Trans. Pattern Anal. Mach. Intell. 27(7), 1013–1025 (2005)

    Google Scholar 

  40. Wang, X., Chen, G., Zhao, Q., Guo, Z.: Reduction of stochastic petri nets for reliability analysis. In: 2007 8th International Conference on Electronic Measurement and Instruments, pp. 1-222–1-226, August 2007, iSSN: null

    Google Scholar 

  41. Weisberg, M.: Simulation and Similarity : Using Models to Understand the World. Oxford University Press, Oxford (2013)

    Google Scholar 

  42. Zhou, M., Venkatesh, K.: Modeling, Simulation, and Control of Flexible Manufacturing Systems: A Petri Net Approach. World Scientific (1999)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Queensland University of Technology, Brisbane, Australia

    Adam Burke, Sander J. J. Leemans & Moe Thandar Wynn

Authors
  1. Adam Burke
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sander J. J. Leemans
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Moe Thandar Wynn
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Adam Burke .

Editor information

Editors and Affiliations

  1. Université de Genève, Carouge, Switzerland

    Didier Buchs

  2. Universitat Politècnica de Catalunya, Barcelona, Spain

    Josep Carmona

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Burke, A., Leemans, S.J.J., Wynn, M.T. (2021). Discovering Stochastic Process Models by Reduction and Abstraction. In: Buchs, D., Carmona, J. (eds) Application and Theory of Petri Nets and Concurrency. PETRI NETS 2021. Lecture Notes in Computer Science(), vol 12734. Springer, Cham. https://doi.org/10.1007/978-3-030-76983-3_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-76983-3_16

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-76982-6

  • Online ISBN: 978-3-030-76983-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation