nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

A Tour in Process Mining: From Practice to Algorithmic Challenges

verfasst von : Wil van der Aalst, Josep Carmona, Thomas Chatain, Boudewijn van Dongen

Erschienen in: Transactions on Petri Nets and Other Models of Concurrency XIV

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Process mining seeks the confrontation between modeled behavior and observed behavior. In recent years, process mining techniques managed to bridge the gap between traditional model-based process analysis (e.g., simulation and other business process management techniques) and data-centric analysis techniques such as machine learning and data mining. Process mining is used by many data-driven organizations as a means to improve performance or to ensure compliance. Traditionally, the focus was on the discovery of process models from event logs describing real process executions. However, process mining is not limited to process discovery and also includes conformance checking. Process models (discovered or hand-made) may deviate from reality. Therefore, we need powerful means to analyze discrepancies between models and logs. These are provided by conformance checking techniques that first align modeled and observed behavior, and then compare both. The resulting alignments are also used to enrich process models with performance related information extracted from the event log. This tutorial paper focuses on the control-flow perspective and describes a range of process discovery and conformance checking techniques. The goal of the paper is to show the algorithmic challenges in process mining. We will show that process mining provides a wealth of opportunities for people doing research on Petri nets and related models of concurrency.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nächstes Kapitel How Petri Net Theory Serves Petri Net Model Checking: A Survey

\(a >_L b\) if and only if there is a trace \(\sigma = \langle t_1, t_2, t_3, \ldots t_{n} \rangle \) and \(i\in \{1, \ldots , n-1\}\) such that \(\sigma \in L\) and \(t_i = a\) and \(t_{i+1} = b\).

In this paper we will use region to denote a 1-bounded region. However, when needed we will use k-bounded region to extend the notion, necessary to account for k-bounded Petri nets.

Remember that we are assuming the standard cost function that assigns cost 1 to synchronous moves and cost 0 to asynchronous moves.

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

Carmona, J., van Dongen, B.F., Solti, A., Weidlich, M.: Conformance Checking - Relating Processes and Models. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-319-99414-7CrossRef

Pearl, J.: Reasoning under uncertainty. Ann. Rev. Comput. Sci. 4(1), 37–72 (1990)MathSciNetCrossRef

Badouel, E., Bernardinello, L., Darondeau, P.: Petri Net Synthesis. Texts in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47967-4CrossRefMATH

Kerremans, M.: Gartner Market Guide for Process Mining, Research Note G00353970 (2018). www.gartner.com

Koplowitz, R., Mines, C., Vizgaitis, A., Reese, A.: Process Mining: Your Compass for Digital Transformation: The Customer Journey Is The Destination (2019). www.forrester.com

TFPM: Process Mining Case Studies (2017). http://www.win.tue.nl/ieeetfpm/doku.php?id=shared:process_mining_case_studies

Celonis: Process Mining Success Story: Innovation is an Alliance with the Future (2017). http://www.win.tue.nl/ieeetfpm/lib/exe/fetch.php?media=:casestudies:siemens_celonis_story_english.pdf

Leemans, S., Fahland, D., van der Aalst, W.: Scalable process discovery and conformance checking. Softw. Syst. Modeling 17, 599–631 (2016)CrossRef

10.

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_17CrossRef

11.

Aalst, W.: Discovering the “glue” connecting activities - exploiting monotonicity to learn places faster. In: Boer, F., Bonsangue, M., Rutten, J. (eds.) It’s All About Coordination, pp. 1–20 (2018)

12.

Murata, T.: Petri nets: properties, analysis and applications. Proc. IEEE 77(4), 541–574 (1989)CrossRef

13.

Aalst, W.: Relating process models and event logs: 21 conformance propositions. In: Proceedings of the International Workshop on Algorithms and Theories for the Analysis of Event Data (ATAED 2018), vol. 2115, pp. 56–74. CEUR Workshop Proceedings, CEUR-WS.org (2018)

14.

Buijs, J.C.A.M., van Dongen, B.F., van der Aalst, W.M.P.: Quality dimensions in process discovery: the importance of fitness, precision, generalization and simplicity. Int. J. Coop. Inf. Syst. 23(1), 1440001 (2014)CrossRef

15.

van der Aalst, W.M.P., et al.: Soundness of workflow nets: classification, decidability, and analysis. Formal Asp. Comput. 23(3), 333–363 (2011)MathSciNetCrossRef

16.

Leemans, S.J.J., Fahland, D., van der Aalst, W.M.P.: Discovering block-structured process models from event logs containing infrequent behaviour. In: Lohmann, N., Song, M., Wohed, P. (eds.) BPM 2013. LNBIP, vol. 171, pp. 66–78. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-06257-0_6CrossRef

17.

Leemans, S.: Robust process mining with guarantees. Ph.D thesis, Eindhoven University of Technology (2017)

18.

Ehrenfeucht, A., Rozenberg, G.: Partial (set) 2-structures. Part I, II. Acta Informatica 27, 315–368 (1990)MathSciNetCrossRef

19.

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

20.

van der Aalst, W.M.P., Rubin, V., Verbeek, H.M.W.E., van Dongen, B.F., Kindler, E., Günther, C.W.: Process mining: a two-step approach to balance between underfitting and overfitting. Softw. Syst. Modeling 9, 87 (2009)

21.

Desel, J., Reisig, W.: The synthesis problem of Petri nets. Acta Inf. 33(4), 297–315 (1996)MathSciNetCrossRef

22.

Carmona, J.: Projection approaches to process mining using region-based techniques. Data Min. Knowl. Discov. 24(1), 218–246 (2012)MathSciNetCrossRef

23.

Solé, M., Carmona, J.: Light region-based techniques for process discovery. Fundam. Inform. 113(3–4), 343–376 (2011)MathSciNetMATH

24.

Solé, M., Carmona, J.: Incremental process discovery. In: Jensen, K., Donatelli, S., Kleijn, J. (eds.) Transactions on Petri Nets and Other Models of Concurrency V. LNCS, vol. 6900, pp. 221–242. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29072-5_10CrossRef

25.

Solé, M., Carmona, J.: Region-based foldings in process discovery. IEEE Trans. Knowl. Data Eng. 25(1), 192–205 (2013)CrossRef

26.

Darondeau, P.: Deriving unbounded Petri nets from formal languages. In: Sangiorgi, D., de Simone, R. (eds.) CONCUR 1998. LNCS, vol. 1466, pp. 533–548. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055646CrossRef

27.

Badouel, E., Bernardinello, L., Darondeau, P.: Polynomial algorithms for the synthesis of bounded nets. In: Mosses, P.D., Nielsen, M., Schwartzbach, M.I. (eds.) CAAP 1995. LNCS, vol. 915, pp. 364–378. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-59293-8_207CrossRef

28.

Lorenz, R., Juhás, R.: How to synthesize nets from languages - a survey. In: Proceedings of the Winter Simulation Conference, WSC 2007 (2007)

29.

Bergenthum, R., Desel, J., Lorenz, R., Mauser, S.: Synthesis of petri nets from infinite partial languages. In: ACSD, pp. 170–179 (2008)

30.

Lorenz, R.: Towards synthesis of petri nets from general partial languages. In: AWPN, pp. 55–62 (2008)

31.

Bergenthum, R., Desel, J., Mauser, S., Lorenz, R.: Synthesis of petri nets from term based representations of infinite partial languages. Fundam. Inform. 95(1), 187–217 (2009)MathSciNetMATH

32.

Mauser, S., Lorenz, R.: Variants of the language based synthesis problem for petri nets. In: ACSD, pp. 89–98 (2009)

33.

van der Aalst, W.M.P., van Dongen, B.F.: Discovering petri nets from event logs. In: Jensen, K., van der Aalst, W.M.P., Balbo, G., Koutny, M., Wolf, K. (eds.) Transactions on Petri Nets and Other Models of Concurrency VII. LNCS, vol. 7480, pp. 372–422. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38143-0_10CrossRef

34.

Bergenthum, R., Desel, J., Lorenz, R., Mauser, S.: Process mining based on regions of languages. In: Alonso, G., Dadam, P., Rosemann, M. (eds.) BPM 2007. LNCS, vol. 4714, pp. 375–383. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75183-0_27CrossRef

35.

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), 387–412 (2009)MathSciNetMATH

36.

van Zelst, S.J., van Dongen, B.F., van der Aalst, W.M.P., Verbeek, H.M.W.: Discovering workflow nets using integer linear programming. Computing 100(5), 529–556 (2018)MathSciNetCrossRef

37.

van Zelst, S.J., van Dongen, B.F., van der Aalst, W.M.P.: ILP-based process discovery using hybrid regions. In: van der Aalst, W.M.P., Bergenthum, R., Carmona, J. (eds.) Proceedings of the International Workshop on Algorithms & Theories for the Analysis of Event Data, ATAED 2015, Satellite event of the conferences: 36th International Conference on Application and Theory of Petri Nets and Concurrency Petri Nets 2015 and 15th International Conference on Application of Concurrency to System Design, ACSD 2015, 22–23 June 2015, Brussels, Belgium, vol. 1371, pp. 47–61. CEUR Workshop Proceedings. CEUR-WS.org (2015)

38.

Adriansyah, A.: Aligning observed and modeled behavior. Ph.D. thesis, Technische Universiteit Eindhoven (2014)

39.

de Leoni, M., Marrella, A.: Aligning real process executions and prescriptive process models through automated planning. Expert Syst. Appl. 82, 162–183 (2017)CrossRef

40.

Reißner, D., Conforti, R., Dumas, M., Rosa, M.L., Armas-Cervantes, A.: Scalable conformance checking of business processes. In: Panetto, H., et al. (eds.) OTM 2017. LNCS, vol. 10573, pp. 607–627. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-69462-7_38CrossRef

41.

Leemans, S.J.J., Fahland, D., van der Aalst, W.M.P.: Scalable process discovery and conformance checking. Softw. Syst. Modeling 17(2), 599–631 (2018)CrossRef

42.

Taymouri, F., Carmona, J.: A recursive paradigm for aligning observed behavior of large structured process models. In: La Rosa, M., Loos, P., Pastor, O. (eds.) BPM 2016. LNCS, vol. 9850, pp. 197–214. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45348-4_12CrossRef

43.

van Dongen, B., Carmona, J., Chatain, T., Taymouri, F.: Aligning modeled and observed behavior: a compromise between computation complexity and quality. In: Dubois, E., Pohl, K. (eds.) CAiSE 2017. LNCS, vol. 10253, pp. 94–109. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59536-8_7CrossRef

44.

Taymouri, F., Carmona, J.: Model and event log reductions to boost the computation of alignments. In: Ceravolo, P., Guetl, C., Rinderle-Ma, S. (eds.) SIMPDA 2016. LNBIP, vol. 307, pp. 1–21. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-74161-1_1CrossRef

45.

Munoz-Gama, J., Carmona, J., Van Der Aalst, W.M.P.: Single-entry single-exit decomposed conformance checking. Inf. Syst. 46, 102–122 (2014)CrossRef

46.

van der Aalst, W.M.P.: Decomposing petri nets for process mining: a generic approach. Distrib. Parallel Databases 31(4), 471–507 (2013)CrossRef

47.

Bloemen, V., van de Pol, J., van der Aalst, W.M.P.: Symbolically aligning observed and modelled behaviour. In: 18th International Conference on Application of Concurrency to System Design, ACSD, Bratislava, Slovakia, 25–29 June, pp. 50–59 (2018)

48.

Bloemen, V., van Zelst, S.J., van der Aalst, W.M.P., van Dongen, B.F., van de Pol, J.: Maximizing synchronization for aligning observed and modelled behaviour. In: Weske, M., Montali, M., Weber, I., vom Brocke, J. (eds.) BPM 2018. LNCS, vol. 11080, pp. 233–249. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98648-7_14CrossRef

49.

Fahland, D., van der Aalst, W.M.P.: Model repair - aligning process models to reality. Inf. Syst. 47, 220–243 (2015)CrossRef

50.

Rozinat, A., van der Aalst, W.M.P.: Conformance checking of processes based on monitoring real behavior. Inf. Syst. 33(1), 64–95 (2008)CrossRef

51.

Munoz-Gama, J.: Conformance Checking and Diagnosis in Process Mining - Comparing Observed and Modeled Processes. LNBIP. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-319-49451-7CrossRefMATH

52.

Adriansyah, A., Munoz-Gama, J., Carmona, J., van Dongen, B.F., van der Aalst, W.M.P.: Measuring precision of modeled behavior. Inf. Syst. E-Business Manag. 13(1), 37–67 (2015)CrossRef

53.

Chatain, T., Carmona, J.: Anti-alignments in conformance checking – the dark side of process models. In: Kordon, F., Moldt, D. (eds.) PETRI NETS 2016. LNCS, vol. 9698, pp. 240–258. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-39086-4_15CrossRefMATH

54.

van Dongen, B.F., Carmona, J., Chatain, T.: A unified approach for measuring precision and generalization based on anti-alignments. In: La Rosa, M., Loos, P., Pastor, O. (eds.) BPM 2016. LNCS, vol. 9850, pp. 39–56. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45348-4_3CrossRef

55.

Dumas, M., Rosa, M.L., Mendling, J., Reijers, H.A.: Fundamentals of Business Process Management, 2nd edn. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-662-56509-4CrossRef

56.

vanden Broucke, S.K.L.M., Weerdt, J.D., Vanthienen, J., Baesens, B.: Determining process model precision and generalization with weighted artificial negative events. IEEE Trans. Knowl. Data Eng. 26(8), 1877–1889 (2014)CrossRef

57.

Mendling, J., Neumann, G., van der Aalst, W.: Understanding the occurrence of errors in process models based on metrics. In: Meersman, R., Tari, Z. (eds.) OTM 2007. LNCS, vol. 4803, pp. 113–130. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-76848-7_9CrossRef

Titel: A Tour in Process Mining: From Practice to Algorithmic Challenges
verfasst von: Wil van der Aalst
Josep Carmona
Thomas Chatain
Boudewijn van Dongen
Verlag: Springer Berlin Heidelberg
Buch: Transactions on Petri Nets and Other Models of Concurrency XIV
Print ISBN: 978-3-662-60650-6

Electronic ISBN: 978-3-662-60651-3

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-662-60651-3_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"