Discovering Process Models with Long-Term Dependencies while Providing Guarantees and Filtering Infrequent Behavior Patterns

• Autorzy: Mannel, Lisa L , van der Aalst, Wil M. P.
• Języki publikacji: EN

Abstrakty

EN

In process discovery, the goal is to find, for a given event log, the model describing the underlying process. While process models can be represented in a variety of ways, Petri nets form a theoretically well-explored description language and are therefore often used. In this paper, we extend the eST-Miner process discovery algorithm. The eST-Miner computes a set of Petri net places which are considered to be fitting with respect to a certain fraction of the behavior described by the given event log as indicated by a given noise threshold. It evaluates all possible candidate places using token-based replay. The set of replayable traces is determined for each place in isolation, i.e., these sets do not need to be consistent. This allows the algorithm to abstract from infrequent behavioral patterns occurring only in some traces. However, when combining places into a Petri net by connecting them to the corresponding uniquely labeled transitions, the resulting net can replay exactly those traces from the event log that are allowed by the combination of all inserted places. Thus, inserting places one-by-one without considering their combined effect may result in deadlocks and low fitness of the Petri net. In this paper, we explore adaptions of the eST-Miner, that aim to select a subset of places such that the resulting Petri net guarantees a definable minimal fitness while maintaining high precision with respect to the input event log. Furthermore, current place evaluation techniques tend to block the execution of infrequent activity labels. Thus, a refined place fitness metric is introduced and thoroughly investigated. In our experiments we use real and artificial event logs to evaluate and compare the impact of the various place selection strategies and place fitness evaluation metrics on the returned Petri net

Słowa kluczowe

EN

eST-Miner; long-term dependencies; non-free choice; Petri Nets; Process Discovery

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2024
• Tom: Vol. 190, nr 2-4
• Strony: 109--158
• Opis fizyczny: Bibliogr. 36 poz., rys., tab., wykr.

Twórcy

autor

Mannel, Lisa L

• Process and Data Science (PADS), RWTH Aachen University, Aachen, Germany.,

autor

van der Aalst, Wil M. P.

• Process and Data Science (PADS) RWTH Aachen University Aachen, Germany,

Bibliografia

• [1] Reisig W. Understanding Petri Nets: Modeling Techniques, Analysis Methods, Case Studies. Springer Berlin Heidelberg, 2013. ISBN:9783642332784.
• [2] Desel J, Oberweis A, Reisig W, Rozenberg G. Petri nets and business process management. Saarbr¨ucken: Gesch¨aftsstelle Schloss Dagstuhl, 1998.
• [3] Desel J, Esparza J. Free-Choice Petri Nets. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1995. ISBN:9780521465199.
• [4] Berthelot G. Transformations and Decompositions of Nets. In: Petri Nets: Central Models and Their Properties. Springer, Berlin, Heidelberg, 1987 pp. 359-376.
• [5] van der Aalst W. Process Mining: Data Science in Action. Springer, Heidelberg, 2 edition, 2016. doi:10.1007/978-3-662-49851-4.
• [6] Wen L, van der Aalst WMP, Wang J, Sun J. Mining process models with non-free-choice constructs. Data Mining and Knowledge Discovery, 2007. 15(2):145-180. doi:10.1007/s10618-007-0065-y.
• [7] Leemans S, Fahland D, van der Aalst W. Discovering Block-Structured Process Models from Event Logs - A Constructive Approach. Application and Theory of Petri Nets and Concurrency, 2013. Lecture Notes in Computer Science, vol 7927. doi:10.1007/978-3-642-38697-8 17.
• [8] Weijters AJMM, Ribeiro JTS. Flexible Heuristics Miner (FHM). In: Proceedings of the IEEE Symposium on Computational Intelligence and Data Mining, CIDM 2011, part of the IEEE Symposium Series on Computational Intelligence 2011, April 11-15, 2011, Paris, France. IEEE, 2011 pp. 310-317. doi:10.1109/CIDM.2011.5949453.
• [9] Badouel E, Bernardinello L, Darondeau P. Petri Net Synthesis. Text in Theoretical Computer Science, EATCS Series. Springer, 2015. doi:10.1007/978-3-662-47967-4.
• [10] Lorenz R, Mauser S, Juh´as G. How to Synthesize Nets from Languages: A Survey. In: Proceedings of the 39th Conference on Winter Simulation: 40 Years! The Best is Yet to Come, WSC ’07. IEEE Press, Piscataway, NJ, USA, 2007 pp. 637-647. doi:10.1109/WSC.2007.4419657.
• [11] Bergenthum R, Desel J, Lorenz R, Mauser S. Process mining based on regions of languages. Proc. 5th Int. Conf. on Business Process Management, 2007. pp. 375-383. doi:10.1007/978-3-540-75183-0 27.
• [12] van der Werf JM, van Dongen B, Hurkens C, Serebrenik A. Process Discovery Using Integer Linear Programming. In: Applications and Theory of Petri Nets. Springer, Berlin, Heidelberg, 2008. doi:10.1007/978-3-540-68746-7 24.
• [13] van Zelst S, van Dongen B, van der Aalst W. Avoiding Over-Fitting in ILP-Based Process Discovery. In: Business Process Management. Springer International Publishing, Cham, 2015 pp. 163-171. doi:10.1007/978-3-319-23063-4 10.
• [14] van Zelst S, van Dongen B, van der Aalst W. ILP-Based Process Discovery Using Hybrid Regions. In: ATAED@Petri Nets/ACSD. 2015.
• [15] Carmona J, Cortadella J, Kishinevsky M. A region-based algorithm for discovering Petri nets from event logs. In: Business Process Management. Springer, 2008 p. 358-373.
• [16] Darondeau P. Deriving unbounded Petri nets from formal languages. In: CONCUR’98 Concurrency Theory. Springer, Berlin, Heidelberg. 1998 pp. 533-548. ISBN:978-3-540-68455-8.
• [17] Bergenthum R, Desel J, Lorenz R, Mauser S. Synthesis of Petri Nets from Finite Partial Languages. Fundam. Informaticae, 2008. 88(4):437-468.
• [18] Ehrenfeucht A, Rozenberg G. Partial (set) 2-structures. Acta Informatica, 1990. 27(4):343-368.
• [19] Carmona J, Cortadella J, Kishinevsky M, Kondratyev A, Lavagno L, Yakovlev A. A Symbolic Algorithm for the Synthesis of Bounded Petri Nets. In: van Hee KM, Valk R (eds.), Applications and Theory of Petri Nets. Springer Berlin Heidelberg, Berlin, Heidelberg. 2008 pp. 92-111. ISBN:978-3-540-68746-7.
• [20] Kalenkova A, Carmona J, Polyvyanyy A, La Rosa M. Automated Repair of Process Models Using Non-Local Constraints. In: Application and Theory of Petri Nets and Concurrency. Springer-Verlag, Berlin, Heidelberg. 2020 p. 280-300. ISBN:978-3-030-51830-1.
• [21] Mannel LL, van der Aalst WMP. Finding Complex Process-Structures by Exploiting the Token-Game. In: Donatelli S, Haar S (eds.), Application and Theory of Petri Nets and Concurrency - 40th International Conference, PETRI NETS 2019, Aachen, Germany, June 23-28, 2019, Proceedings, volume 11522 of Lecture Notes in Computer Science. Springer, 2019 pp. 258-278. doi:10.1007/978-3-030-21571-2 1
• [22] Mannel LL, van der Aalst WMP. Discovering Process Models with Long-Term Dependencies While Providing Guarantees and Handling Infrequent Behavior. In: Bernardinello L, Petrucci L (eds.), Application and Theory of Petri Nets and Concurrency - 43rd International Conference, PETRI NETS 2022, Bergen, Norway, June 19-24, 2022, Proceedings, volume 13288 of Lecture Notes in Computer Science. Springer, 2022 pp. 303-324. doi:10.1007/978-3-031-06653-5 16.
• [23] Garcia-Valles F, Colom J. Implicit places in net systems. Proceedings 8th International Workshop on Petri Nets and Performance Models, 1999. pp. 104-113. doi:10.1109/PNPM.1999.796557.
• [24] Berthomieu B, Botlan DL, Dal-Zilio S. Petri Net Reductions for Counting Markings. In: Gallardo M, Merino P (eds.), Model Checking Software - 25th International Symposium, SPIN 2018, Malaga, Spain, June 20-22, 2018, Proceedings, volume 10869 of LNCS. Springer, 2018 pp. 65-84.
• [25] Colom J, Silva M. Improving the linearly based characterization of P/T nets. In: Advances in Petri Nets 1990. Springer, Berlin, Heidelberg, 1991 pp. 113-145. doi:10.1007/3-540-53863-1 23.
• [26] Mannel LL, Bergenthum R, van der Aalst WMP. Removing Implicit Places Using Regions for Process Discovery. In: Proceedings of the International Workshop on Algorithms & Theories for the Analysis of Event Data (ATAED) 2020, volume 2625. CEUR-WS.org pp. 20-32.
• [27] van der Aalst WMP. Discovering the ”Glue” Connecting Activities - Exploiting Monotonicity to Learn Places Faster. In: It’s All About Coordination - Essays to Celebrate the Lifelong Scientific Achievements of Farhad Arbab. 2018 pp. 1-20. doi:10.1007/978-3-319-90089-6 1.
• [28] Carmona J, van Dongen B, Solti A, Weidlich M. Conformance Checking - Relating Processes and Models. Springer, Cham, 2018. doi:10.1007/978-3-319-99414-7.
• [29] Mannhardt, F. Sepsis Cases - Event Log, 2016. doi:10.4121/UUID:915D2BFB-7E84-49AD-A286-DC35F063A460.
• [30] De Leoni, M, Mannhardt, F. Road Traffic Fine Management Process, 2015.
• [31] van der Aalst WMP. Spreadsheets for BPM. Business Process Management Journal, 2010. 24:105-127.
• [32] Adriansyah A. Aligning observed and modeled behavior. Ph.D. thesis, Mathematics and Computer Science, 2014. doi:10.6100/IR770080.
• [33] Munoz-Gama J, Carmona J. A Fresh Look at Precision in Process Conformance. In: BPM, volume 6336. 2010 pp. 211-226. ISBN:978-3-642-15617-5.
• [34] van Dongen B, de Medeiros A, Verbeek H, Weijters A, van der Aalst W. The ProM Framework: A New Era in Process Mining Tool Support. In: Applications and Theory of Petri Nets 2005. Springer, Berlin, Heidelberg, 2005 pp. 444-454. doi:10.1007/11494744 25.
• [35] Mendling J, Reijers HA, Cardoso J. What Makes Process Models Understandable? In: Alonso G, Dadam P, Rosemann M (eds.), Business Process Management. Springer Berlin Heidelberg, 2007 pp. 48-63. doi:10.1007/978-3-540-75183-0 4.
• [36] Tax N, Sidorova N, van der Aalst WMP. Discovering more precise process models from event logs by filtering out chaotic activities. J. Intell. Inf. Syst., 2019. 52(1):107-139. doi:10.1007/s10844-018-0507-6

Identyfikatory

DOI

10.3233/FI-242168