Синтез ациклических моделей для процессов без повторяющихся событий
Синтез ациклических моделей для процессов без повторяющихся событий
Аннотация
В майнинге процессов (process mining) графы непосредственного следования (Directly-Follows Graph, DFG) популярны благодаря своей простоте и наглядности. Однако, если процесс является ациклическим, но содержит параллельные события, стандартные алгоритмы построения DFG-моделей могут генерировать «ложные» циклы, которыe не представлены в журнале событий. Такие циклы мешают анализу информационных процессов, значительно снижая интерпретируемость и точность (precision) модели. Эта проблема рассматривалась в работе Н. Шаимова и др., где было предложено синтезировать DFG-модели без ложных циклов с помощью дублирования вершин графа. Задача эта не имеет единственного или лучшего решения, и предложенное ранее решение является эвристическим. Цель данной статьи – предложить альтернативный алгоритм синтеза ациклических DFG-моделей для процессов без повторяющихся событий и сравнить его с существующим на реальных и искусственных данных. Представленный в этой статье метод позволяет получить модель меньшего размера по сравнению с существующим решением, а также стабильно ведёт себя при построении моделей процессов с высокой степенью параллелизма. Также в работе доказано, что устранение ложных циклов ведет к экспоненциальному увеличению размера моделей для процессов с высокой степенью параллелизма.
Ключевые слова
Издание
Труды Института системного программирования РАН, том 38, вып. 4, часть 2, 2026, стр. 215-224.
ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).
DOI: 10.15514/ISPRAS-2026-38(4)-27
Для цитирования
Полный текст статьи в формате pdf (на английском)
Вернуться к содержанию тома