maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2024-3-294-315mais-1879Research ArticleTheory of ComputingСинтез иерархических моделей процессов: подход на основе разбиения событий на множестваDiscovering hierarchical process models: an approach based on events partitioninghttps://orcid.org/0000-0001-6657-1760БегичеваАнтонина КонстантиновнаBegichevaAntonina K.abegicheva@hse.ruhttps://orcid.org/0000-0002-9420-3751ЛомазоваИрина АлександровнаLomazovaIrina A.ilomazova@hse.ruhttps://orcid.org/0000-0002-4162-9070НестеровРоман АлександровичNesterovRoman A.rnesterov@hse.ruНациональный исследовательский университет «Высшая школа экономики»РоссияNational Research University Higher School of EconomicsRussian Federation202413092024313294315Copyright © Бегичева А.К., Ломазова И.А., Нестеров Р.А., 20242024Бегичева А.К., Ломазова И.А., Нестеров Р.А.Begicheva A.K., Lomazova I.A., Nesterov R.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1879

Process mining — это область компьютерных наук, которая занимается синтезом и анализом моделей процессов на основе автоматически генерируемых журналов событий. В настоящее время многие организации используют эту технологию для оптимизации и совершенствования бизнес-процессов. Однако синтезированная модель процесса может быть слишком подробной, сложной и трудной для понимания экспертами. В работе мы рассматриваем задачу синтеза иерархической модели бизнес-процесса из низкоуровневого журнала событий, то есть, задачу автоматического синтеза более удобочитаемых и понятных моделей процессов на основе данных, хранящихся в журналах событий информационных систем. Построение более структурированных и удобочитаемых моделей процессов широко изучается в рамках исследований в области process mining с разных точек зрения. В этой статье мы представляем алгоритм синтеза иерархических моделей процессов, представленных в виде двухуровневых сетей потоков работ. Алгоритм основан на предопределенном разбиении событий на множества, которые определяют подпроцессы, соответствующие высокоуровневым переходам на верхнем уровне двухуровневой сети потоков работ. В отличие от существующих решений, представленный алгоритм не накладывает ограничений на поток управления процессом, а также допускает параллелизм и итерации.

Process mining is a field of computer science that deals with the discovery and analysis of process models based on automatically generated event logs. Currently, many companies are using this technology to optimize and improve their business processes. However, a discovered process model may be too detailed, sophisticated, and difficult for experts to understand. In this paper, we consider a problem of discovering the hierarchical business process model from a low-level event log, i. e., the problem of the automatic synthesis of more readable and understandable process models based on the data stored in the event logs of information systems. The discovery of better-structured and more readable process models is extensively studied in the framework of process mining research from different perspectives. In this paper, we present an algorithm for discovering hierarchical process models represented as two-level workflow Petri nets. The algorithm is based on predefined event partitioning so that this partitioning defines a sub-process corresponding to a high-level transition at the top level of a two-level net. In contrast to existing solutions, our algorithm does not impose restrictions on the process control flow and allows for concurrency and iterations.

синтез моделей процессовсети Петрисети потоков работиерархические модели процессовжурнал событийprocess miningPetri netsworkflow netsprocess discoveryhierarchical process modelevent logПрограмма фундаментальных исследований Национального исследовательского университета «Высшая школа экономики».Basic Research Program at HSE University.ReferencesA. Augusto et al., “Automated discovery of process models from event logs: review and benchmark,” IEEE Transactions on Knowledge and Data Engineering, vol. 31, no. 4, pp. 686–705, 2018.A. Augusto et al., “Automated discovery of process models from event logs: review and benchmark,” IEEE Transactions on Knowledge and Data Engineering, vol. 31, no. 4, pp. 686–705, 2018.W. van der Aalst, “Workflow verification: Finding control-flow errors using Petri-net-based techniques,” in Business process management: models, techniques, and empirical studies, Springer, 2002, pp. 161–183.W. van der Aalst, “Workflow verification: Finding control-flow errors using Petri-net-based techniques,” in Business process management: models, techniques, and empirical studies, Springer, 2002, pp. 161–183.A. K. Begicheva and I. A. Lomazova, “Discovering high-level process models from event logs,” Modeling and Analysis of Information Systems, vol. 24, no. 2, pp. 125–140, 2017.A. K. Begicheva and I. A. Lomazova, “Discovering high-level process models from event logs,” Modeling and Analysis of Information Systems, vol. 24, no. 2, pp. 125–140, 2017.S. J. van Zelst, F. Mannhardt, M. de Leoni, and A. Koschmider, “Event abstraction in process mining: literature review and taxonomy,” Granular Computing, vol. 6, no. 3, pp. 719–736, 2021.S. J. van Zelst, F. Mannhardt, M. de Leoni, and A. Koschmider, “Event abstraction in process mining: literature review and taxonomy,” Granular Computing, vol. 6, no. 3, pp. 719–736, 2021.D. G. J. C. Maneschijn, R. H. Bemthuis, F. A. Bukhsh, and M.-E. Iacob, “A Methodology for Aligning Process Model Abstraction Levels and Stakeholder Needs,” in Proceedings of the 24th International Conference on Enterprise Information Systems - Volume 1, 2022, pp. 137–147.D. G. J. C. Maneschijn, R. H. Bemthuis, F. A. Bukhsh, and M.-E. Iacob, “A Methodology for Aligning Process Model Abstraction Levels and Stakeholder Needs,” in Proceedings of the 24th International Conference on Enterprise Information Systems - Volume 1, 2022, pp. 137–147.F. Mannhardt, M. de Leoni, H. Reijers, W. van der Aalst, and P. Toussaint, “From Low-Level Events to Activities -- A Pattern-Based Approach,” in Business Process Management, 2016, pp. 125–141.F. Mannhardt, M. de Leoni, H. Reijers, W. van der Aalst, and P. Toussaint, “From Low-Level Events to Activities -- A Pattern-Based Approach,” in Business Process Management, 2016, pp. 125–141.N. Tax, N. Sidorova, R. Haakma, and W. van der Aalst, “Event abstraction for process mining using supervised learning techniques,” in Proceedings of SAI Intelligent Systems Conference 2016, 2018, pp. 161–170.N. Tax, N. Sidorova, R. Haakma, and W. van der Aalst, “Event abstraction for process mining using supervised learning techniques,” in Proceedings of SAI Intelligent Systems Conference 2016, 2018, pp. 161–170.C.-Y. Li, S. J. van Zelst, and W. van der Aalst, “A Framework for Automated Abstraction Class Detection for Event Abstraction,” in Intelligent Systems Design and Applications, 2023, pp. 126–136.C.-Y. Li, S. J. van Zelst, and W. van der Aalst, “A Framework for Automated Abstraction Class Detection for Event Abstraction,” in Intelligent Systems Design and Applications, 2023, pp. 126–136.G. van Houdt, M. de Leoni, N. Martin, and B. Depaire, “An empirical evaluation of unsupervised event log abstraction techniques in process mining,” Information Systems, vol. 121, p. 102320, 2024.G. van Houdt, M. de Leoni, N. Martin, and B. Depaire, “An empirical evaluation of unsupervised event log abstraction techniques in process mining,” Information Systems, vol. 121, p. 102320, 2024.A. Rebmann, P. Pfeiffer, P. Fettke, and H. van der Aa, “Multi-perspective Identification of Event Groups for Event Abstraction,” in Process Mining Workshops, 2023, pp. 31–43.A. Rebmann, P. Pfeiffer, P. Fettke, and H. van der Aa, “Multi-perspective Identification of Event Groups for Event Abstraction,” in Process Mining Workshops, 2023, pp. 31–43.S. J. J. Leemans, K. Goel, and S. J. van Zelst, “Using multi-level information in hierarchical process mining: Balancing behavioural quality and model complexity,” in Proceedings of the 2nd International Conference on Process Mining, 2020, pp. 137–144.S. J. J. Leemans, K. Goel, and S. J. van Zelst, “Using multi-level information in hierarchical process mining: Balancing behavioural quality and model complexity,” in Proceedings of the 2nd International Conference on Process Mining, 2020, pp. 137–144.A. Senderovich, A. Shleyfman, M. Weidlich, A. Gal, and A. Mandelbaum, “To aggregate or to eliminate? Optimal model simplification for improved process performance prediction,” Information Systems, vol. 78, pp. 96–111, 2018.A. Senderovich, A. Shleyfman, M. Weidlich, A. Gal, and A. Mandelbaum, “To aggregate or to eliminate? Optimal model simplification for improved process performance prediction,” Information Systems, vol. 78, pp. 96–111, 2018.S. Smirnov, H. Reijers, M. Weske, and T. Nugteren, “Business process model abstraction: a definition, catalog, and survey,” Distributed and Parallel Databases, vol. 30, pp. 63–99, 2012.S. Smirnov, H. Reijers, M. Weske, and T. Nugteren, “Business process model abstraction: a definition, catalog, and survey,” Distributed and Parallel Databases, vol. 30, pp. 63–99, 2012.C. W. G"unther and W. M. P. Van Der Aalst, “Fuzzy mining--adaptive process simplification based on multi-perspective metrics,” in International conference on business process management, 2007, pp. 328–343.C. W. G"unther and W. M. P. Van Der Aalst, “Fuzzy mining--adaptive process simplification based on multi-perspective metrics,” in International conference on business process management, 2007, pp. 328–343.W. Reisig, Understanding Petri nets: Modeling techniques, analysis methods, case studies. Springer, 2013.W. Reisig, Understanding Petri nets: Modeling techniques, analysis methods, case studies. Springer, 2013.K. Jensen and L. Kristensen, Coloured Petri nets: modelling and validation of concurrent systems. Springer, 2009.K. Jensen and L. Kristensen, Coloured Petri nets: modelling and validation of concurrent systems. Springer, 2009.S. Leemans, D. Fahland, and W. van der Aalst, “Discovering Block-Structured Process Models from Event Logs -- A Constructive Approach,” in Application and Theory of Petri Nets and Concurrency, 2013, pp. 311–329.S. Leemans, D. Fahland, and W. van der Aalst, “Discovering Block-Structured Process Models from Event Logs -- A Constructive Approach,” in Application and Theory of Petri Nets and Concurrency, 2013, pp. 311–329.G. Greco, A. Guzzo, and L. Pontieri, “Mining taxonomies of process models,” Data & Knowledge Engineering, vol. 67, no. 1, pp. 74–102, 2008.G. Greco, A. Guzzo, and L. Pontieri, “Mining taxonomies of process models,” Data & Knowledge Engineering, vol. 67, no. 1, pp. 74–102, 2008.J. Li, R. Bose, and W. van der Aalst, “Mining context-dependent and interactive business process maps using execution patterns,” in Business Process Management Workshops. BPM 2010, 2010, pp. 109–121.J. Li, R. Bose, and W. van der Aalst, “Mining context-dependent and interactive business process maps using execution patterns,” in Business Process Management Workshops. BPM 2010, 2010, pp. 109–121.X. Lu, A. Gal, and H. A. Reijers, “Discovering hierarchical processes using flexible activity trees for event abstraction,” in Proceedings of the 2nd International Conference on Process Mining, 2020, pp. 145–152.X. Lu, A. Gal, and H. A. Reijers, “Discovering hierarchical processes using flexible activity trees for event abstraction,” in Proceedings of the 2nd International Conference on Process Mining, 2020, pp. 145–152.W. van der Aalst and C. Gunther, “Finding Structure in Unstructured Processes: The Case for Process Mining,” in Seventh International Conference on Application of Concurrency to System Design (ACSD 2007), 2007, pp. 3–12, doi: 10.1109/ACSD.2007.50.W. van der Aalst and C. Gunther, “Finding Structure in Unstructured Processes: The Case for Process Mining,” in Seventh International Conference on Application of Concurrency to System Design (ACSD 2007), 2007, pp. 3–12, doi: 10.1109/ACSD.2007.50.J. De Smedt, J. De Weerdt, and J. Vanthienen, “Multi-paradigm Process Mining: Retrieving Better Models by Combining Rules and Sequences,” in On the Move to Meaningful Internet Systems: OTM 2014 Conferences, 2014, pp. 446–453, doi: 10.1007/978-3-662-45563-0_26.J. De Smedt, J. De Weerdt, and J. Vanthienen, “Multi-paradigm Process Mining: Retrieving Better Models by Combining Rules and Sequences,” in On the Move to Meaningful Internet Systems: OTM 2014 Conferences, 2014, pp. 446–453, doi: 10.1007/978-3-662-45563-0_26.J. de San Pedro and J. Cortadella, “Mining Structured Petri Nets for the Visualization of Process Behavior,” in Proceedings of the 31st Annual ACM Symposium on Applied Computing, 2016, pp. 839–846, doi: 10.1145/2851613.2851645.J. de San Pedro and J. Cortadella, “Mining Structured Petri Nets for the Visualization of Process Behavior,” in Proceedings of the 31st Annual ACM Symposium on Applied Computing, 2016, pp. 839–846, doi: 10.1145/2851613.2851645.W. van der Aalst, A. Kalenkova, V. Rubin, and E. Verbeek, “Process Discovery Using Localized Events,” in Application and Theory of Petri Nets and Concurrency, 2015, pp. 287–308, doi: 10.1007/978-3-319-19488-2_15.W. van der Aalst, A. Kalenkova, V. Rubin, and E. Verbeek, “Process Discovery Using Localized Events,” in Application and Theory of Petri Nets and Concurrency, 2015, pp. 287–308, doi: 10.1007/978-3-319-19488-2_15.A. Kalenkova and I. Lomazova, “Discovery of Cancellation Regions within Process Mining Techniques,” Fundamenta Informaticae, vol. 133, no. 2-3, pp. 197–209, 2014, doi: 10.3233/FI-2014-1071.A. Kalenkova and I. Lomazova, “Discovery of Cancellation Regions within Process Mining Techniques,” Fundamenta Informaticae, vol. 133, no. 2-3, pp. 197–209, 2014, doi: 10.3233/FI-2014-1071.A. Kalenkova, I. Lomazova, and W. van der Aalst, “Process Model Discovery: A Method Based on Transition System Decomposition,” in Application and Theory of Petri Nets and Concurrency, 2014, pp. 71–90, doi: 10.1007/978-3-319-07734-5_5.A. Kalenkova, I. Lomazova, and W. van der Aalst, “Process Model Discovery: A Method Based on Transition System Decomposition,” in Application and Theory of Petri Nets and Concurrency, 2014, pp. 71–90, doi: 10.1007/978-3-319-07734-5_5.C.-Y. Li, S. J. van Zelst, and W. M. P. van der Aalst, “An Activity Instance Based Hierarchical Framework for Event Abstraction,” in Proceedings of the 3rd International Conference on Process Mining, 2021, pp. 160–167, doi: 10.1109/ICPM53251.2021.9576868.C.-Y. Li, S. J. van Zelst, and W. M. P. van der Aalst, “An Activity Instance Based Hierarchical Framework for Event Abstraction,” in Proceedings of the 3rd International Conference on Process Mining, 2021, pp. 160–167, doi: 10.1109/ICPM53251.2021.9576868.T. Tapia-Flores, E. L'opez-Mellado, A. P. Estrada-Vargas, and J.-J. Lesage, “Discovering Petri net models of discrete-event processes by computing T-invariants,” IEEE Transactions on Automation Science and Engineering, vol. 15, no. 3, pp. 992–1003, 2017.T. Tapia-Flores, E. L'opez-Mellado, A. P. Estrada-Vargas, and J.-J. Lesage, “Discovering Petri net models of discrete-event processes by computing T-invariants,” IEEE Transactions on Automation Science and Engineering, vol. 15, no. 3, pp. 992–1003, 2017.T. Tapia-Flores and E. Lopez-Mellado, “Discovering workflow nets of concurrent iterative processes,” Acta Informatica, vol. 61, Sep. 2023, doi: 10.1007/s00236-023-00445-5.T. Tapia-Flores and E. Lopez-Mellado, “Discovering workflow nets of concurrent iterative processes,” Acta Informatica, vol. 61, Sep. 2023, doi: 10.1007/s00236-023-00445-5.W. van der Aalst, Process Mining: Discovery, Conformance and Enhancement of Business Processes. Springer, Heidelberg, 2011.W. van der Aalst, Process Mining: Discovery, Conformance and Enhancement of Business Processes. Springer, Heidelberg, 2011.K. Lautenbach, “Linear Algebraic Techniques for Place/Transition Nets,” in Petri Nets: Central Models and Their Properties. ACPN 1986, 1987, pp. 142–167.K. Lautenbach, “Linear Algebraic Techniques for Place/Transition Nets,” in Petri Nets: Central Models and Their Properties. ACPN 1986, 1987, pp. 142–167.A. Berti, S. Van Zelst, and W. van der Aalst, “Process mining for Python (PM4Py): bridging the gap between process- and data science,” in Proceedings of the ICPM Demo Track 2019, 2019, pp. 13–16.A. Berti, S. Van Zelst, and W. van der Aalst, “Process mining for Python (PM4Py): bridging the gap between process- and data science,” in Proceedings of the ICPM Demo Track 2019, 2019, pp. 13–16.A. Begicheva, “Hierarchical process model discovery -- hldiscovery.” 2022, [Online]. Available: https://github.com/gingerabsurdity/hldiscovery.A. Begicheva, “Hierarchical process model discovery -- hldiscovery.” 2022, [Online]. Available: https://github.com/gingerabsurdity/hldiscovery.J. Carmona, B. van Dongen, A. Solti, and M. Weidlich, Conformance Checking: Relating Processes and Models. Springer, 2018.J. Carmona, B. van Dongen, A. Solti, and M. Weidlich, Conformance Checking: Relating Processes and Models. Springer, 2018.A. Adriansyah, B. F. van Dongen, and W. M. P. van der Aalst, “Conformance checking using cost-based fitness analysis,” in 2011 ieee 15th international enterprise distributed object computing conference, 2011, pp. 55–64.A. Adriansyah, B. F. van Dongen, and W. M. P. van der Aalst, “Conformance checking using cost-based fitness analysis,” in 2011 ieee 15th international enterprise distributed object computing conference, 2011, pp. 55–64.J. Munoz-Gama and J. Carmona, “A fresh look at precision in process conformance,” in International Conference on Business Process Management, 2010, pp. 211–226.J. Munoz-Gama and J. Carmona, “A fresh look at precision in process conformance,” in International Conference on Business Process Management, 2010, pp. 211–226.I. Shugurov and A. Mitsyuk, “Generation of a Set of Event Logs with Noise,” in Proceedings of the 8th Spring/Summer Young Researchers Colloquium on Software Engineering, 2014, pp. 88–95.I. Shugurov and A. Mitsyuk, “Generation of a Set of Event Logs with Noise,” in Proceedings of the 8th Spring/Summer Young Researchers Colloquium on Software Engineering, 2014, pp. 88–95.A. Augusto et al., “Data underlying the paper: Automated Discovery of Process Models from Event Logs: Review and Benchmark (Version 1).” 2019, doi: 10.4121/uuid:adc42403-9a38-48dc-9f0a-a0a49bfb6371.A. Augusto et al., “Data underlying the paper: Automated Discovery of Process Models from Event Logs: Review and Benchmark (Version 1).” 2019, doi: 10.4121/uuid:adc42403-9a38-48dc-9f0a-a0a49bfb6371.

The authors declare that there are no conflicts of interest present.