Синтез ациклических моделей для процессов без повторяющихся событий

В майнинге процессов (process mining) графы непосредственного следования (Directly-Follows Graph, DFG) популярны благодаря своей простоте и наглядности. Однако, если процесс является ациклическим, но содержит параллельные события, стандартные алгоритмы построения DFG-моделей могут генерировать «ложные» циклы, которыe не представлены в журнале событий. Такие циклы мешают анализу информационных процессов, значительно снижая интерпретируемость и точность (precision) модели. Эта проблема рассматривалась в работе Н. Шаимова и др., где было предложено синтезировать DFG-модели без ложных циклов с помощью дублирования вершин графа. Задача эта не имеет единственного или лучшего решения, и предложенное ранее решение является эвристическим. Цель данной статьи – предложить альтернативный алгоритм синтеза ациклических DFG-моделей для процессов без повторяющихся событий и сравнить его с существующим на реальных и искусственных данных. Представленный в этой статье метод позволяет получить модель меньшего размера по сравнению с существующим решением, а также стабильно ведёт себя при построении моделей процессов с высокой степенью параллелизма. Также в работе доказано, что устранение ложных циклов ведет к экспоненциальному увеличению размера моделей для процессов с высокой степенью параллелизма.

1. Berti A., van Zelst S., Schuster D. Pm4py: A process mining library for python. Software Impacts, 2023, vol. 17, p. 100556.

2. Celonis, 2024. Available at: https://www.celonis.com/, accessed 26.07.2026.

3. Günther C., Rozinat A. Disco: discover your processes. In Proc. of the demonstration track of the 10th international conference on business process management (BPM 2012), CEUR Workshop Proceedings, 2012, pp. 40-44.

4. van der Aalst W. Academic View: Development of the Process Mining Discipline. Springer International Publishing, 2020. pp. 181-196.

5. Shaimov N. D., Lomazova I. A., Nesterov R. A. How to Prevent Fake Cycles in DFG Models Discovered from Event Logs? Programming and Computer Software 51 (6), 395-408.

6. 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. International Journal of Cooperative Information Systems, 2014, vol. 23, no. 1, 1440001.

7. van der Aalst W. M. P. Process Mining - Data Science in Action. 2nd ed. Springer, 2016.

8. Glaister I., Shallit J. A lower bound technique for the size of nondeterministic finite automata. Information Processing Letters, 1996, vol. 59, no. 2, pp. 75-77.

9. GitHub acyclic-dfg-synthesis. Available at: https://github.com/ajoulitov/acyclic-dfg-synthesis, accessed 26.07.2026.