Методы и инструменты повышения эффективности алгоритмов майнинга процессов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Шершаков Сергей Андреевич

• Шершаков Сергей Андреевич
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Шершаков Сергей Андреевич

Введение

Глава 1. Синтез моделей процессов по журналам событий

1.1 Обзор существующих работ и инструментов

1.2 Основные определения и понятия

1.2.1 Журнал событий и модели процессов

1.2.2 Метрики качества моделей процессов

Глава 2. Метод параметрической частотной редукции систем переходов

2.1 Алгоритм частотной редукции систем переходов

2.1.1 Построение полной системы переходов (шаг 1)

2.1.2 Построение конденсированной системы переходов (шаг 2)

2.1.3 Построение редуцированной системы переходов (шаг 3)

2.2 Алгоритм расчета метрики «точность» (precision) для систем переходов

2.3 Сравнение эффективности метода частотной редукции с методом простой редукции

2.4 Адаптивная редукция промежуточной модели в виде системы переходов

2.5 Выводы по главе

Глава 3. Повышение эффективности синтеза сетей Петри по журналам событий с

применением метода регионов

3.1 Сети Петри и теория регионов

3.1.1 Регионы

3.2 Схема синтеза сетей Петри алгоритмом регионов

3.2.1 Алгоритм регионов

3.3 Повышение эффективности синтеза сетей Петри алгоритмом регионов с применением частотной редукции промежуточной системы переходов

3.4 Применение метода регионов для синтеза сетей потоков задач по системам переходов с петлями

3.4.1 Синтез сетей потоков работ

3.4.2 Системы переходов с петлями

3.5 Выводы по главе

Глава 4. Повышение эффективности программной реализации методов майнинга

процессов

4.1 Существующие решения

4.1.1 Программные инструменты process mining

4.2 Выделение требований для программного обеспечения майнинга процессов

4.2.1 Сценарии использования программных инструментов process mining

4.2.2 Требования к дизайну библиотеки алгоритмов process mining

4.3 Библиотека LDOPA

4.3.1 Специальные подходы к разработке структур данных и управлением памятью

4.4 Применение реляционных баз данных для изучения свойств ПОИС

4.4.1 Компонентные ПОИС и сервис-ориентированная архитектура

4.4.2 Абстрактный журнал событий и БД-журнал событий

4.4.3 Подготовка данных для исследования процессов с использованием РСУБД

4.4.4 Метод построения отношения между событиями/DFR с помощью SQL-запросов

4.4.5 Применение РСУБД для выявления анти-паттернов в ПОИС

4.5 Метод представления больших журналов событий с помощью реляционных баз данных

4.5.1 Представление журналов событий с помощью РСУБД

4.5.2 Реализация в библиотеке LDOPA

4.6 Выводы по главе

Глава 5. Автоматизация экспериментов в области майнинга процессов

5.1 Структура разработанного программного обеспечения

5.2 Графический язык DPMine для моделирования экспериментов в области Process Mining

5.2.1 Основные компоненты языка DPMine

5.2.2 Исполнение модели, схемы, блока

5.3 Инструмент графического моделирования VTMine for Visio

5.3.1 Объектная модель Visio

5.3.2 Семантические атрибуты

5.3.3 Разработка архитектуры приложения: задачи и особенности

5.3.4 Подсистема моделирования DPMine

5.3.5 Примеры моделей экспериментов process mining

5.4 Автоматизация комплексных экспериментов с помощью сценариев Python

5.4.1 Схема эксперимента

5.5 Выводы по главе

Глава 6. Экспериментальное исследование эффективности разработанных

алгоритмов и программных инструментов

6.1 Экспериментальная оценка качественных характеристик редуцированных систем

переходов

6.1.1 Журнал событий ri

6.1.2 Журнал событий r2

6.1.3 Журнал событий r3

6.1.4 Журналы событий ai и a2

6.1.5 Интерпретация результатов экспериментов

6.2 Оценка влияния параметров алгоритма частотной редукции на время синтеза

сетей Петри

6.3 Сравнительная оценка эффективности реализации алгоритмов по времени и по памяти

6.4 Выводы по главе

Заключение

Список сокращений и условных обозначений

Словарь терминов

Список литературы

Список рисунков

Список таблиц

Введение диссертации (часть автореферата) на тему «Методы и инструменты повышения эффективности алгоритмов майнинга процессов»

Введение

Последние два десятилетия обозначились бурным развитием информационных технологий. Возросли мощности оборудования, сократился его размер и вес. Вкупе с понижением энергопотребления современной электроникой все это дало мощный толчок к развитию мобильной потребительской цифровой техники (субкомпактные лэптопы, планшеты и смартфоны), а также носимых устройств (например, умные часы). Другим аспектом стало широкое повсеместное проникновение сетей передачи данных, в первую очередь, интернета. Развиваются новые поколения беспроводных сетей. Стоимость 1 Мб переданной информации неуклонно падает, а скорости передачи информации — повышаются.

Два этих обстоятельства существенно изменили структуру и потоки передачи информации. Интернет как глобальная коммуникационная структура все чаще рассматривается не только как технологический феномен, но и в различных проекциях: традиционная проекция интернета контента; в виде интернета сервисов для бизнес-проекции; в виде интернета людей и интернета мест в социальной проекции; наконец, даже вещи получили свой интернет вещей. Все вместе они порождают новую большую сущность — интернет событий.

Цифровизация общества также происходит в разных направлениях. Это проявляется не только в появлении новых цифровых инструментов, но и в перемещении традиционных оффлайновых сервисов с их очередями и длительным ожиданием в онлайн с доступом 24/7 и быстрым получением результата. Интернет-магазины, интернет-банки, заказ билетов, госуслуги, онлайн-образование — все эти сервисы нашли свое отражение в виртуальном пространстве. Даже такие классические услуги, как такси, стремительно переносят в интернет функционал, не связанный непосредственно с движением автомобиля. Бизнесы, сделавшие ставку на классические оффлайновые бизнес-процессы, в одночасье оказались неконкурентоспособными; этот феномен, по примеру тех же такси, стали называть уберификацией.

Разумеется, одного только скоростного интернета и быстрых телефонов недостаточно для того, чтобы перевести бизнес в цифру. Огромная задача ложится на специальный класс систем поддержки бизнес-процессов, называемых процессно-ориентированными информационными системами (ПОИС). Они представляют собой сложные распределенные программные комплексы, берущие на себя большое число функций по инициализации, сквозной поддержке и завершению бизнес-процессов. Функционируя, такие системы накапливают большое число побочных данных, записываемых в логах. Логи могут рассматриваться с технической точки зрения (системные ло-ги) или с точки зрения следов поведения системы относительно событий бизнес-процесса (логи событий). Последние являются ценным источником знаний о реальном поведении системы. Сравнивая реальное поведение с ожидаемым, можно обнаружить массу полезной информации, как-то: несоответствие реального и желаемого поведения системы (что особенно актуально при наличии человеческого фактора); узкие места и проблемы с производительностью; анти-паттерны построения бизнес-системы и т.д.

Изучением этих задач занимается дисциплина «извлечение и анализ моделей процессов» (англ. process mining, PM) [1]. Субъектами этой дисциплины являются бизнес-аналитики,

владельцы процессов, исследователи данных. Ее основными объектами являются бизнес-процессы. Процессы представляются различными абстракциями в виде статистических, графических и других видов моделей, а также конкретными выполненными экземплярами процессов, записанными в логах событий.

Извлечение процессов тесно связано с добычей данных (data mining), машинным обучением (machine learning), моделированием и анализом моделей процессов. Основные задачи и цели этого направления исследований изложены в Манифесте (Process Mining Manifesto) [2] и могут быть кратко представлены тремя ключевыми проблемами: 1) извлечение модели процесса из журнала событий (process discovery), 2) проверка соответствия некоторой модели реальным данным, записанным в журнале событий (conformance checking), и 3) исправление и улучшение процесса с учетом изменяющихся данных (process enhancement).

Для описания моделей процессов используются различные средства — языковые нотации (workflow notations) и программные инструменты (workflow engines/systems). В настоящий момент известно значительное число нотаций для описания процессов, потоков работ (в основе большинства из них лежат сети Петри) и систем, реализующих эти нотации в программных инструментах для конечного пользователя. В качестве примера можно привести нотацию для описания бизнес-процессов BPMN [3], язык исполнения бизнес-процессов BPEL [4], язык моделирования процессов YAWL [5].

Системы переходов (transition systems, TS) являются одной из наиболее естественных нотаций для представления журналов событий. Они могут рассматриваться и как самостоятельная модель представления журнала событий, и в качестве промежуточной модели, на основании которой с помощью специальных алгоритмов можно получать другие модели, учитывающие, например, явления параллелизма (сети Петри).

Сети Петри являются низкоуровневым формализмом с хорошей теоретической базой и позволяют проверять такие свойства моделируемых систем, как безопасность, ограниченность, достижимость и др. По причине своей низкоуровневости сети Петри не всегда используются в качестве конечной модели для анализа процессов; однако они являются базовыми моделями для построения на их основе таких высокоуровневых моделей, как BPMN, которые используются для описания бизнес-процессов, или UML Activity Diagram [6], которые используются для описания поведения информационных систем.

Несмотря на то, что извлечение процессов является относительно новым направлением, оно уже активно применяется при моделировании и анализе бизнес-процессов [7] в менеджменте, при разработке программного обеспечения [8; 9], в управлении технологическими процессами, в медицине [10; 11].

Одна из ключевых проблем, с которыми сталкивается дисциплина process mining, — большое количество данных для анализа, генерируемых ПОИС. Данная проблема известна как проблема больших данных (Big Data) [12] и включает несколько аспектов (четыре «V» больших данных): размер (volume), скорость генерирования (velocity), разнообразие (variety) и достоверность (veracity). К настоящему моменту уже разработано и продолжает разрабатываться большое число алгоритмов синтеза и анализа моделей процессов. Они основаны на разных концепциях,

различаются сложностью по времени/памяти, а так же точностью и достоверностью получаемых с их помощью результатов.

В контексте больших данных лишь немногие алгоритмы способны выдавать какой-либо результат за приемлемое время. Еще меньше алгоритмов способны выдавать результат, удовлетворяющий критериям точности и достоверности. Например, алгоритм построения нечетких карт (fuzzy maps) [13] широко используется в большинстве существующих инструментов process mining, причем во многих он является основным, если не единственным. Это определяется скоростью его работы и простотой получаемых результатов. Позволяя получать первичную модель для больших входных данных, он, тем не менее, не дает возможности для представления и анализа многих важных аспектов сложных процессов, таких как параллелизм и наличие дедлоков. Противоположным примером является алгоритм на основе теории регионов, который позволяет получить точную и теоретически обоснованную модель в виде сети Петри. Однако временная сложность работы этого алгоритма существенно выше.

Проблема процессных моделей и алгоритмов, которые с ними работают, заключается в предельном размере журнала событий, который может быть обработан такими алгоритмами. Сложность некоторых важных алгоритмов, имеющая от размера входных данных полиномиальную или экспоненциальную зависимость, не позволяет обрабатывать журналы событий реальных систем с большим количеством сохраненной информации, сохраняемой в этих журналах.

В случае с алгоритмом регионов основной проблемой, ограничивающей его широкое практическое применение, является временная сложность этого алгоритма. Доказано, что задача синтеза некоторых разновидностей сетей Петри алгоритмом регионов относится к классу NP-полных задач [14]. Это означает, что временная сложность этого алгоритма имеет экспоненциальную зависимость от размера системы переходов, являющейся входной моделью для этого алгоритма. Для других классов сетей Петри алгоритм регионов имеет полиномиальную временную сложность от размера входной модели с высокой степенью полинома [15]. Система переходов строится на основе журнала событий, и, в худшем случае, ее размер линейно связан с размером самого журнала, что в случае реальных журналов событий существенно ограничивает практическую применимость алгоритма.

Таким образом, актуальной становится задача редукции систем переходов, синтезированных по логам реальных систем, до таких размеров, при которых, с одной стороны, они становятся обозримыми и подходящими для использования со сложными алгоритмами (например, алгоритмом регионов), а с другой, — не искажают поведение реальной системы или делают это в наименьшей степени. Для оценки качественных характеристик синтезируемых моделей, способной показать, насколько модель соответствует реальному поведению процесса, используются метрики качества модели: степень соответствия (fitness), сложность (simplicity) и точность (precision) [16].

Несмотря на то, что теоретическую сложность алгоритма регионов невозможно «улучшить», тем не менее, возможно существенно повысить применимость алгоритма за счет его эффективной реализации, а это накладывает специальные требования и ограничения на программные инструменты. Таким образом, эффективная реализация программных инструментов для process mining также является важной и актуальной задачей.

Целью данной работы является разработка методов, алгоритмов и инструментов редукции систем переходов с контролем качественных характеристик (метрик), таких как степень соответствия (fitness), сложность (simplicity) и точность (precision).

Для достижения поставленной цели необходимо было решить следующие задачи:

1. Исследовать существующие подходы к задаче редукции систем переходов и других похожих моделей.

2. Разработать алгоритм редукции систем переходов, основанный на частотной характеристике появления индивидуальных активностей в журнале событий.

3. Разработать алгоритм вычисления метрики «точность» (precision) для систем переходов.

4. Разработать критерии адаптивной вариации параметров алгоритма сокращения исходной системы переходов.

5. Разработать расширение метода регионов для синтеза сетей Петри по системам переходов с петлями.

6. Исследовать влияние параметров алгоритма сокращения системы переходов на качественные характеристики модели в виде сети Петри, построенной на основе сокращенной системы переходов с помощью алгоритма регионов.

7. Выработать архитектурные принципы проектирования программного инструментария для PM в контексте работы с большими логами событий реальных информационных систем.

8. Спроектировать и разработать на основе выработанных архитектурных принципов программный инструмент, реализующий: а) алгоритм сокращения системы переходов, б) алгоритм расчета метрик соответствия заданной системы переходов исходному журналу событий, в) алгоритм конвертации системы переходов в сеть Петри, г) алгоритмы визуализации моделей.

9. Провести комплексные эксперименты на журналах событий реальных информационных систем, позволяющие оценить качественные характеристики полученных моделей при различных вариациях параметров алгоритмов.

10. Оценить эффективность — по времени и по памяти — реализации указанных алгоритмов в спроектированном инструменте по сравнению с реализацией тех же алгоритмов в других существующих инструментах для PM.

Научная новизна:

1. Разработан новый параметрический алгоритм редукции систем переходов, основанный на частотных характеристиках активностей журнала событий. По сравнению с существующими подходами «простой» редукции, новый алгоритм показал лучшие результаты как по уменьшению сложности модели, так и по увеличению ее точности. Эксперименты проводились на синтетических и реальных журналах событий.

2. Впервые для задач дисциплины process mining было выполнено исследование влияния размера и качественных характеристик промежуточной модели в виде системы переходов на размер и качественные характеристики целевой модели в виде сети Петри при конвертации с помощью алгоритма регионов.

3. Был разработан подход к представлению больших журналов событий с применением технологии встраиваемых СУРБД, позволяющий эффективно извлекать данные из журналов с возможностью мультиперспективного обращения без перестраивания журнала событий.

Практическая значимость. Данная работа позволит повысить эффективность обработки больших наборов данных алгоритмами process mining с целью построения моделей процессов. Это позволит улучшить применимость алгоритмов, чувствительных к размеру входных данных, к большим журналам событий реальных информационных систем. Использование таких алгоритмов с моделями, которые получены на основе реальных журналов событий, дает возможность более комплексного изучения поведения систем, для которых выполняется построение процессных моделей.

Методология и методы исследования. Методологическую основу исследования составляют теория множеств, теория графов, теория автоматов, теория алгоритмов и математическая логика, теория формальных языков и грамматик, принципы машинного обучения, моделирование, синтез и анализ.

Основные положения, выносимые на защиту:

1. Метод параметрической редукции систем переходов с сохранением качественных характеристик моделей.

2. Алгоритм частотной редукции систем переходов.

3. Алгоритм вычисления метрики «точность» (precision) для систем переходов.

4. Метод представления больших журналов событий с помощью реляционных баз данных с мультиперспективным извлечением данных.

5. Расширение метода регионов для систем переходов с петлями.

6. Архитектурные принципы, архитектура и реализация расширяемого программного комплекса, использующего предложенные метод адаптивной параметрической редукции систем переходов и синтеза конечных моделей в виде сетей Петри.

Достоверность полученных результатов обеспечивается сравнением с результатами смежных алгоритмов и методов. Результаты находятся в соответствии с результатами, полученными другими авторами.

Апробация работы. Основные результаты работы докладывались на:

- конференции Conference on Software Testing, Machine Learning and Complex process Analysis (TMPA-2019) (Грузия). Доклад: «Multi-Perspective Process Mining with Embedding Configurations into DB-based Event Logs»;

- 207-м заседании Московской секции ACM SIGMOD. Доклад: «РСУБД в Process Mining»;

- конференции Algorithms & Theories for the Analysis of Event Data (ATAED 2016) (Польша). Доклад: «Transition Systems Reduction: Balancing between Precision and Simplicity»;

- конференции 5th International Conference on Networking and Information Technology (ICNIT 2014) (Сингапур). Доклад: «VTMine Framework as Applied to Process Mining Modeling»;

- конференции Spring/Summer Young Researchers' Colloquium on Software Engineering 2014 (Санкт-Петербург). Доклады: «DPMine/C: C++ Library and Graphical Frontend for DPMine Workflow Language» и «Component-based VTMine/C Framework: Not Only Modelling»;

- семинаре «Unleashing Operational Process Mining» (2013) международной рабочей группы IEEE Task Force on Process Mining (Германия);

- конференции «Разработка ПО» CEE-SECR2013 (Москва). Доклад: «DPMine/P: modeling and process mining language and ProM plug-ins»;

- конференции Spring/Summer Young Researchers' Colloquium on Software Engineering 2013 (Казань). Доклад: «DPMine: modeling and process mining tool».

Публикации. Основные результаты по теме диссертации изложены в 11 печатных изданиях, 5 из которых индексируются в Scopus/WoS (из них 2 журналы), 1 издано в журнале, рекомендованном ВАК, 5 изданы в трудах конференций.

Объем и структура работы. Диссертация состоит из введения, шести глав, заключения и двух приложений. Полный объём диссертации составляет 205 страниц, включая 96 рисунков и 19 таблиц. Список литературы содержит 105 наименований.

Краткое содержание диссертации

Во введении обозначается предметная область работы, дается обоснование актуальности ее темы, определяются цели и задачи, а также раскрывается теоретическая и практическая значимость работы.

В первой главе дается необходимый обзор работ по связанным тематикам, вводятся основные определения и понятия, используемые в настоящей работе.

Глава вторая содержит описание разработанного метода параметрической частотной редукции систем переходов. Представляется новый параметрический алгоритм частотной редукции систем переходов и доказывается его корректность. Далее дается описание нового алгоритма расчета метрики «точность» для систем переходов. Приводится первичный анализ эффективности разработанного метода частотной редукции в сравнении с методом простой редукции. В заключении главы определяется подход к адаптивной редукции промежуточной системы переходов для построения результирующей модели (сети Петри) с заданными характеристиками.

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

Четвертая глава посвящена вопросам эффективности программной реализации инструментария для process mining. На основе анализа типичных сценариев использования программных

инструментов для решения задач синтеза и анализа моделей процессов выделяется набор требований, предъявляемых к производительному ПО для process mining. Определяются архитектурные принципы, лежащие в основе высокоутилитарной библиотеки LDOPA для process mining. Обозначаются специальные подходы к управлению памятью и разработке специализированных структур данных, отражающих специфику моделей в данной предметной области.

Отдельное внимание уделяется вопросам применения реляционных СУБД для работы с большими журналами событий на примере исследования поведения реальных информационных систем. Представляется подход к детектированию поведения специального типа (паттернов и анти-паттернов) в ПОИС с помощью РСУБД. Наконец, описывается новый метод представления больших журналов событий с помощью СУБД с мультиперспективным извлечением данных.

Пятая глава описывает методы и инструменты повышения эффективности проведения экспериментов в области process mining. На основе подготовленного стека программного обеспечения приводится описание разработанного графического языка DPMine моделирования экспериментов; инструмента графического моделирования VTMine for Visio; набора моделей экспериментов. Описывается подход к автоматизации комплексных экспериментов с помощью сценариев Python и компонента доступа к библиотеке LDOPA, даются примеры сценариев.

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

В заключении приводятся основные результаты работы.

Глава 1. Синтез моделей процессов по журналам событий 1.1 Обзор существующих работ и инструментов

Дисциплина process mining сформировалась недавно и получила свое развитие в последние годы. К трем основным задачам process mining относятся задача отыскания модели (process discovery), проверка соответствия модели журналу событий (conformance checking) и улучшение моделей процессов на основе информации, представленной в журналах событий [1; 17].

Сам термин «майнинг» применительно к моделям процессов и журналам событий впервые был введен Agrawal и др. в [18].

Существует ряд работ, посвященных выведению (синтезу) систем переходов из потоков (трасс) событий. Biermann and Feldman в своей работе [19] предложили алгоритм k-хвостов, который осуществляет «склеивание» состояний синтезируемого конечного автомата, основанный на подобии поведения состояний. Предложенный подход породил большой класс методов «склеивания хвостов» префиксных деревьев. Angluin [20] предложила метод «склеивания» состояний префиксного дерева, основанный на понятии k-обратимости. В работе [21], Lorenzoli и соавт. предложили подход GK-хвостов, являющийся расширением метода k-хвостов и работающий с параметризованными конечными автоматами.

Cook и Wolf в своей работе [22] ввели понятие отыскания процесса (process discovery) — новую технику анализа данных в контексте процессов программной инженерии. Они рассматривали автоматический синтез формальной модели, описывающей непрерывный процесс, — на основе извлеченных данных о событиях. Новый метод, основанный на марковских процессах, был специально разработан ими для этой цели. Кроме этого, два существующих метода — k-хвостов и основанный на нейронных сетях RNet — были адаптированы авторами для задачи отыскания процессов.

Задачи извлечения процессов, проверка соответствия и улучшение процессов формируют основу извлечения и анализа моделей процессов [1]. Они используют различные модели процессов, включающие сети Петри, системы переходов, нечеткие карты, каузальные сети, BPMN, UML и др. В контексте process mining системы переходов используются как самостоятельные модели, так и промежуточные, на основе которых выполняется построение других типов моделей. В последнем случае применяются подходы, основанные на теории регионов, рассматриваемые в работах [23—26].

Важную роль систем переходов как промежуточного представления процесса освещают работы [27]. В работе [27] предлагается несколько стратегий конструирования систем переходов, дающих желаемые качественные характеристики конечных моделей в виде сетей Петри. Тем не менее, все предложенные стратегии основаны на алгоритмах синтеза с конечной пред- или постисторией (фиксированным «окном» состояний).

Помимо оговоренных выше стратегий, был предложен ряд других подходов для редукции систем переходов. Большинство из них основаны на «склеивании» связанных состояний.

В работе [28] авторы предлагают технику абстракции, которая была названа общая конечная разметка (common final marking, CFM). Техника включает «склеивание» всех состояний без выходных дуг в единственное состояние. В работе [26] авторы предлагают подход по сокращению размеров системы переходов, основанный на технике агрессивной свертки. Предложенная техника позволяет получить редукцию пространства состояний посредством обнаружения разверток циклов в ациклической системе переходов с последущей их сверткой.

Наконец, ряд работ по извлечению моделей процессов основан на методе языковых регионов, применяющемся непосредственно к журналам событий без построения промежуточных моделей [29; 30]. В настоящей работе эти методы не рассматриваются.

Process mining является дисциплиной с большим практическим уклоном. Для решения задач process mining доступны свободные и коммерческие программные инструменты. ProM [31] является наиболее известным таким инструментом с открытым исходном кодом (на языке программирования Java). Функциональность ProM расширяется с помощью модулей расширения. ProM является фреймворком, содержащим большое число пакетов, сильно связанных друг с другом. ProM является академическим ПО в том смысле, что он позиционируется как инструмент для апробации новых подходов: практически все существующие алгоритмы для process mining имеют свою реализацию в ProM.

Существуют также коммерческие инструменты, связанные с областью process mining и настроенные специально для задач бизнес-аналитики. Disco [32] был одним из первых инструментов, основанных на нечетком алгоритме (fuzzy miner) [13], который для заданного лога конструирует т. н. процессную карту в виде направленного графа активностей. Позже подобный подход был реализован в таких инструментах, как Celonis [33] и Minit [34]. Другой класс инструментов представлен в виде пакетов расширения для таких скриптовых языков/платформ, как Python: это PMLab [35], PM4Py [36]; и R: Bupar [37].

Среди всех существующих инструментов для process mining только ProM предоставляет широкий набор реализованных алгоритмов, представленных в виде исходного кода. Это позволяет расценивать его как референсный инструмент при сравнении программных инструментов и реализаций алгоритмов.

Следующие главы, там где это необходимо, предваряются дополнительным обзором работ, релевантных тематике главы.

1.2 Основные определения и понятия

В данном разделе приводятся основные понятия, определения и концепции, используемые в работе.

Список литературы диссертационного исследования кандидат наук Шершаков Сергей Андреевич, 2020 год

Список литературы

1. Aalst W. M. P. van der Process Mining - Discovery, Conformance and Enhancement of Business Processes. — Springer, 2011. — С. I—XVI, 1—352.

2. IEEE Task Force on Process Mining Process Mining Manifesto // BPM 2011 Workshops. Т. 99 / под ред. F. Daniel, S. Dustdar, K. Barkaoui. — Springer-Verlag, Berlin, 2011. — С. 169—194. — (Lecture Notes in Business Information Processing).

3. (OMG) O. M. G. Business Process Model and Notation (BPMN) Version 2.0: тех. отч. — 01.2011. — URL: http://taval.de/publications/BPMN20.

4. Web Services Business Process Execution Language Version 2.0 (OASIS Standard) / A. Alves [и др.]. — 2007. — WS-BPEL TC OASIS, http://docs.oasis-open.org/wsbpel/2.0/wsbpel-v2.0.html.

5. Aalst W. M. P. van der, Hofstede A. H. M. ter YAWL: Yet Another Workflow Language // Inf. Syst. — Oxford, UK, UK, 2005. — Июнь. — Т. 30, № 4. — С. 245—275. — URL: http://dx. doi.org/10.1016/j.is.2004.02.002.

6. (OMG) O. M. G. OMG Unified Modeling Language (OMG UML), Superstructure, ver. 2.4.1: тех. отч. —2011.

7. Using process mining for the analysis of an e-trade system: A case study / A. Mitsyuk [и др.] // Business Informatics. — 2014. — Т. 29, № 3. — С. 15—27.

8. Rubin V, Lomazova I., Aalst W. M. van der Agile Development with Software Process Mining // In proceedings: ICSSP 2014, Nanjing, Jiangsu, China. — ACM, 2014. — С. 70—74.

9. Process Mining Can Be Applied to Software Too! / V. Rubin [и др.] // Proceedings of the 8th ACM/IEEE International Symposium on Empirical Software Engineering and Measurement. — NY: ACM, 2014.

10. Application of Process Mining in Healthcare - A Case Study in a Dutch Hospital / R. S. Mans [и др.] // Biomedical Engineering Systems and Technologies / под ред. A. Fred, J. Filipe, H. Gamboa. —Berlin, Heidelberg : Springer Berlin Heidelberg, 2009. — С. 425—438.

11. Process Mining in Healthcare: Data Challenges When Answering Frequently Posed Questions. / R. Mans [и др.] // ProHealth/KR4HC. Т. 7738 / под ред. R. Lenz [и др.]. — Springer, 2012. — С. 140—153. — (Lecture Notes in Computer Science). — URL: http://dblp.uni-trier.de/db/conf/ bpm/kr4hc2012.html#MansAVM12.

12. Big data: The next frontier for innovation, competition, and productivity: тех. отч. / J. Manyika [и др.].—2011.

13. Günther C. W., Van Der Aalst W. M. P. Fuzzy Mining: Adaptive Process Simplification Based on Multi-perspective Metrics // Proceedings ofthe 5th International Conference on Business Process Management. — Brisbane, Australia : Springer-Verlag, 2007. — С. 328—343. — (BPM'07). — URL: http://dl.acm.org/citation.cfm?id=1793114.1793145.

14. BadouelE., Bernardinello L., Darondeau P. The synthesis problem for elementary net systems is NP-complete // Theoretical Computer Science. — 1997. — Окт. — Т. 186. — С. 107—134. — URL: https://doi.org/10.1016/S0304-3975(96)00219-8.

15. Badouel E., Bernardinello L., Darondeau P. Polynomial algorithms for the synthesis of bounded nets // TAPSOFT '95: Theory and Practice of Software Development: 6th International Joint Conference CAAP/FASE Aarhus, Denmark, May 22-26, 1995 Proceedings / под ред. P. D. Mosses, M. Nielsen, M. I. Schwartzbach. — Berlin, Heidelberg : Springer Berlin Heidelberg, 1995. — С. 364—378. — URL: http://dx.doi.org/10.1007/3-540-59293-8_207.

16. Buijs J., Dongen B., Aalst W. On the Role of Fitness, Precision, Generalization and Simplicity in Process Discovery // OTM Federated Conferences, 20th International Conference on Cooperative Information Systems (CoopIS 2012). Т. 7565 / под ред. R. Meersman [и др.]. — Springer-Verlag, Berlin, 2012. — С. 305—322. — (Lecture Notes in Computer Science).

17. Process Mining Manifesto / W. M. P. v. d. Aalst [и др.] // BPM 2011 Workshops, Part I. Т. 99. — Springer-Verlag, 2012. — С. 169—194.

18. Agrawal R, Gunopulos D., LeymannF. Mining process models from workflow logs// Advances in Database Technology — EDBT'98 / под ред. H.-J. Schek [и др.]. —Berlin, Heidelberg : Springer Berlin Heidelberg, 1998. — С. 467—483.

19. Biermann A. W, FeldmanJ. A. On the Synthesis of Finite-State Machines from Samples of Their Behavior // IEEE Trans. Comput. — Washington, DC, USA, 1972. — Июнь. — Т. 21, № 6. — С. 592—597. — URL: http://dx.doi.org/10.1109/TC.1972.5009015.

20. Angluin D. Inference of Reversible Languages // J. ACM. — New York, NY, USA, 1982. — Июль. — Т. 29, № 3. — С. 741—765. — URL: http://doi.acm.org/10.1145/322326.322334.

21. Lorenzoli D., Mariani L., Pezze M. Inferring state-based behavior models // 4th International Workshop on Dynamic Analysis (WODA 2006) co-located with the 28th International Conference on Software Engineering (ICSE 2006). — Shanghai, China : ACM Press, 2006. — С. 25—32.

22. Cook J.E., Wolf A. L. Discovering Models of Software Processes from Event-based Data // ACM Trans. Softw. Eng. Methodol. — New York, NY, USA, 1998. —Июль. — Т. 7, №3. — С. 215— 249. — URL: http://doi.acm.org/10.1145/287000.287001.

23. Badouel E., Darondeau P. Lectures on Petri Nets I: Basic Models: Advances in Petri Nets // / под ред. W. Reisig, G. Rozenberg. — Berlin, Heidelberg : Springer Berlin Heidelberg, 1998. — Гл. Theory of regions. С. 529—586. — URL: http://dx.doi.org/10.1007/3-540-65306-6_22.

24. Deriving Petri Nets from Finite Transition Systems / J. Cortadella [и др.] // IEEE Trans. Comput. — Washington, DC, USA, 1998. — Авг. — Т. 47, № 8. — С. 859—882. — URL: http://dx.doi.org/10.1109/12.707587.

26. Sole M., Carmona /.Region-Based Foldings in Process Discovery // IEEE Transactions on Knowledge and Data Engineering. — Los Alamitos, CA, USA, 2013. — Т. 25, № 1. — С. 192— 205.

27. Process mining: a two-step approach to balance between underletting and overfitting / W. M. P. van der Aalst [и др.] // Software & Systems Modeling. — 2008. — Т. 9, № 1. — С. 87—111. — URL: http://dx.doi.org/10.1007/s10270-008-0106-z.

28. Solé M., Carmona J. Process Mining from a Basis of State Regions // Applications and Theory of Petri Nets: 31st International Conference, PETRI NETS 2010, Braga, Portugal, June 21-25, 2010. Proceedings / под ред. J. Lilius, W. Penczek. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2010. — С. 226—245. — URL: http://dx.doi.org/10.1007/978-3-642-13675-7_14.

29. Process Mining Based on Regions of Languages / R. Bergenthum [и др.] // Business Process Management: 5th International Conference, BPM 2007, Brisbane, Australia, September 24-28, 2007. Proceedings / под ред. G. Alonso, P. Dadam, M. Rosemann. —Berlin, Heidelberg : Springer Berlin Heidelberg, 2007. — С. 375—383. — URL: http://dx.doi.org/10.1007/978-3-540-75183-0_27.

30. Process Discovery Using Integer Linear Programming / J. M. E. M. van der Werf [и др.] // Applications and Theory of Petri Nets: 29th International Conference, PETRI NETS 2008, Xi'an, China, June 23-27, 2008. Proceedings / под ред. K. M. van Hee, R. Valk. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2008. — С. 368—387. — URL: http://dx.doi.org/10.1007/978-3-540-68746-7_24.

31. ProM 6: The Process Mining Toolkit / H. Verbeek [и др.] // Proc. of BPM Demonstration Track 2010. Т. 615 / под ред. M. L. Rosa. — 2010. — С. 34—39. — (CEUR Workshop Proceedings).

32. Fluxicon. —URL: http://fluxicon.com/disco.

33. URL: www.celonis.com.

34. URL: www.minit.io.

35. Carmona J., Solé M.PMLAB: An Scripting Environment for Process Mining // BPM (Demos)'14. — 2014. — С. 16—16.

36. Berti A., Zelst S. J. van, Aalst W. M. van der Process Mining for Python (PM4Py): Bridging the Gap Between Process- and Data Science: тех. отч. / arXiv.org. — 2019.

37. Janssenswillen G., Depaire B. bupaR: Business Process Analysis in R // BPM. — 2017.

38. Shershakov S. A., Kalenkova A. A., Lomazova I. A. Transition Systems Reduction: Balancing between Precision and Simplicity // CEUR Workshop Proceedings. Т. 1592 / под ред. W. van der Aalst, R. Bergenthum, J. Carmona. — 2016. — С. 78—95. — (Algorithms & Theories for the Analysis of Event Data).

39. Shershakov S. A., Kalenkova A. A., Lomazova I. A. Transition Systems Reduction: Balancing Between Precision and Simplicity // Transactions on Petri Nets and Other Models of Concurrency XII / под ред. M. Koutny, J. Kleijn, W. Penczek. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2017. — С. 119—139. — URL: https://doi.org/10.1007/978-3-662-55862-1_6.

40. ParkD. M.R. Concurrency and Automata on Infinite Sequences // Theoretical Computer Science, 5th GI-Conference, Karlsruhe, Germany, March 23-25, 1981, Proceedings. — 1981. — С. 167— 183. — URL: http://dx.doi.org/10.1007/BFb0017309.

41. URL: http://fluxicon.com/blog/2015/05/bpi-challenge-2015/.

42. Aalst W. van der, Weijter A., Maruster L. Workflow Mining: Discovering process models from event logs // IEEE Transactions on Knowledge and Data Engineering. — 2003. — Т. 16. — С. 2004.

43. Alves de Medeiros A. K. Genetic Process Mining: дис. ... канд. / Alves de Medeiros Ana Karla.— Technische Universiteit Eindhoven, 2006.

44. Leemans S. J. J., Fahland D., Aalst W. M. P. van der Discovering Block-Structured Process Models from Incomplete Event Logs // Application and Theory of Petri Nets and Concurrency: 35th International Conference, PETRI NETS 2014, Tunis, Tunisia, June 23-27, 2014. Proceedings / под ред. G. Ciardo, E. Kindler. — Cham : Springer International Publishing, 2014. — С. 91—110. — URL: https://doi.org/10.1007/978-3-319-07734-5_6.

45. A Symbolic Algorithm for the Synthesis of Bounded Petri Nets / J. Carmona [и др.] // Applications and Theory of Petri Nets / под ред. K. M. van Hee, R. Valk. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2008. — С. 92—111.

46. Carmona J., Cortadella J., Kishinevsky M. New Region-Based Algorithms for Deriving Bounded Petri Nets // IEEE Transactions on Computers. — 2010. — Т. 59, № 3. — С. 371—384.

47. Discovering Relaxed Sound Workflow Nets using Integer Linear Programming / S. J. van Zelst [и др.]. — URL: https://arxiv.org/pdf/1703.06733.pdf.

48. Kindler E., Rubin V, Schäfer W. Activity Mining for Discovering Software Process Models. // Software Engineering. Т. 79 / под ред. B. Biel, M. Book, V. Gruhn. — GI, 2006. — С. 175— 180. — (LNI). — URL: http://dblp.uni-trier.de/db/conf/se/se2006.html#KindlerRS06.

49. Nielsen M., G.Rozenberg, Thiagarajan P. Elementary transition systems // Theoretical Computer Science. — 1992. — Т. 96, № 1. — С. 3—33.

50. Properties of Plain, Pure, and Safe Petri Nets - with some Applications to Petri Net Synthesis / K. Barylska [и др.] // ATAED@Petri Nets/ACSD. — 2016.

51. Shershakov S. Multi-Perspective Process Mining with Embedding Cofigurations into DB-based Event Logs // Communications in Computer and Information Science. — Springer, 2020. — In Press.

52. Shershakov S. Enhancing Efficiency of Process Mining Algorithms with a Tailored Library: Design Principles and Performance Assessment: тех. отч. / National Research University Higher School of Economics. —2018. —URL: https://www.researchgate.net/publication/332869308_ Enhancing_Efficiency_of_Process_Mining_Algorithms_with_a_Tailored_Library_Design_ Principles_and_Performance_Assessment_Technical_Report.

54. Shershakov S. A. VTMine Framework as Applied to Process Mining Modeling // International Journal of Computer and Communication Engineering. — 2015. — Май. — Т. 4, № 3. — С. 166— 179.

55. Generating event logs for high-level process models / A. A. Mitsyuk [и др.] // Simulation Modelling Practice and Theory. — 2017. — Т. 74. — С. 1—16.

56. URL: https://ieeexplore.ieee.org/document/7740858.

57. Kim P, Bulanov O., Shershakov S. Component-based VTMine/C Framework: Not Only Modelling // Proceedings of the 8th Spring/Summer Young Researchers' Colloquium on Software Engineering, SYRCoSE 2014 / под ред. A. Kamkin, A. Petrenko, A. Terekhov. — ISP RAS, 2014. — С. 102—107. — URL: http://syrcose.ispras.ru/2014/files/SYRCoSE2014_Proceedings. pdf.

58. Shershakov S. DPMine/C: C++ Library and Graphical Frontend for DPMine Workflow Language // Proceedings ofthe 8th Spring/Summer Young Researchers' Colloquium on Software Engineering, SYRCoSE 2014 / под ред. A. Kamkin, A. Petrenko, A. Terekhov. — ISP RAS, 2014. — С. 96—101. — URL: http://syrcose.ispras.ru/2014/files/SYRCoSE2014_Proceedings. pdf.

59. Shershakov S. A. DPMine graphical language for automation of experiments in process mining // Automatic Control and Computer Sciences. — 2016. — Т. 50, № 7. — С. 477—485. — URL: http://dx.doi.org/10.3103/S014641161607018X.

60. Aalst W.M. P. van der Extracting Event Data from Databases to Unleash Process Mining // BPM -Driving Innovation in a Digital World / под ред. J. vom Brocke, T. Schmiedel. — Cham : Springer International Publishing, 2015. — С. 105—128. — URL: https://doi.org/10.1007/978-3-319-14430-6_8.

61. MurillasE. G. L. de, Aalst W.M.P. van der, ReijersH. A. Process Mining on Databases: Unearthing Historical Data from Redo Logs // Business Process Management / под ред. H. R. Motahari-Nezhad, J. Recker, M. Weidlich. — Cham : Springer International Publishing, 2015. — С. 367— 385.

62. González López de Murillas E., Reijers H. A., Aalst W. M. P. van der Connecting Databases with Process Mining: A Meta Model and Toolset // Enterprise, Business-Process and Information Systems Modeling / под ред. R. Schmidt [и др.]. — Cham : Springer International Publishing, 2016. — С. 231—249.

63. Dongen B. F. van, Shabani S. Relational XES: Data Management for Process Mining //. — С. 169—176. —URL: http://ceur-ws.org/Vol-1367/#paper-22.

64. Günther C. W., VerbeekE. XES. Standard Definition / TU/e. — 2.0-е изд. — Den Dolech 2, 5612 AZ Eindhoven, P.O. Box 513, 5600 MB Eindhoven, 03.2014.

66. Enabling efficient process mining on large data sets: realizing an in-database process mining operator / R. Dijkman [и др.] // Distributed and Parallel Databases. — 2019. — Май. — URL: https://doi.org/10.1007/s10619-019-07270-1.

67. H2 Database Engine. — URL: https://www.h2database.com/html/main.html.

68. Kebede M., Dumas M. Comparative Evaluation of Process Mining Tools //. — 2015.

69. Celik U., Akgetin E. Process Mining Tools Comparison: тех. отч. — 2018.

70. Mans R, Aalst W. van der, Verbeek H. Supporting Process Mining Workflows with RapidProM // Proceedings of the BPM Demo Sessions 2014 / под ред. L. Limonad, B. Weber. — 2014.

71. Shershakov S. DPMine/P: modeling and process mining language and ProM plug-ins // Proceedings of the 9th Central & Eastern European Software Engineering Conference in Russia / под ред. A. N. Terekhov, M. Tsepkov. — ACM New York, NY, USA, 2013. — URL: http: //dl.acm.org/citation.cfm?id=2556622&CFID=415147702&CFT0KEN=35395117.

72. Petrify: a tool for manipulating concurrent specifications and synthesis of asynchronous controllers / J. Cortadella [и др.] // IEICE Transactions on Information and Systems. — 1997. — Т. E80—D, № 3. — С. 315—325.

73. Introduction to asynchronous circuit design: specification and synthesis (tutorial). / J. Cortadella [и др.] // Proceedings of 6th. Int. Symp. on Advanced Research in Asynchronous Circuits and Systems, Eilat (Israel). — 2000.

74. Solé M., Carmona J. Rbminer: A Tool for Discovering Petri Nets from Transition Systems // Automated Technology for Verification and Analysis / под ред. A. Bouajjani, W.-N. Chin. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2010. — С. 396—402.

75. Carmona J., Cortadella J., Kishinevsky M. Genet: A Tool for the Synthesis and Mining of Petri Nets // 2009 Ninth International Conference on Application of Concurrency to System Design. — 2009. — С. 181—185.

76. Wilson M. Extended STL, Volume 1: collections and iterators. — 2007.

77. URL: https://www.boost.org/.

78. URL: http://www.sqlite.org/.

79. URL: https://github.com/google/googletest.

80. Design Patterns: Elements of Reusable Object-Oriented Software / E. Gamma [и др.]. — 1-е изд. — Addison-Wesley Professional, 1994.

81. Boost Graph Library ver. 1.72. — URL: https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/ index.html.

82. Enterprise Service Oriented Architectures: Concepts, Challenges, Recommendations / J. McGovern [и др.]. — Springer, 2006.

84. Davydova K. V., Shershakov S. A. Mining Hierarchical UML Sequence Diagrams from Event Logs of SOA Systems while Balancing between Abstracted and Detailed Models // Proceedings of the Institute for System Programming of the RAS / под ред. V. P. Ivannikov. — 2016. — Т. 28, № 3. — С. 85—102.

85. Davydova K. V., Shershakov S. A. Mining Hybrid UML Models from Event Logs of SOA Systems // Proceedings of the Institute for System Programming of the RAS / под ред. A. Avetisyan. — 2017. — Т. 29, № 4. — С. 155—174.

86. Mannhardt F. Multi-perspective process mining: дис. ... канд. / Mannhardt F. — Department of Mathematics, Computer Science, 02.2018. —Proefschrift.

87. Shershakov S. Multi-Perspective Process Mining with Embedding Cofigurations into DB-based Event Logs // Communications in Computer and Information Science. — Springer, 2019. — In Press.

88. LDOPA Official Website. — URL: https://prj.xiart.ru/projects/ldopa.

89. Rigin A., Shershakov S. SQLite RDBMS Extension for Data Indexing Using B-tree Modifications // Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). — 2019. — Т. 31, № 3. — С. 203—216. — URL: https://ispranproceedings.elpub. ru/jour/article/view/1188/948.

90. Mitsyuk A. A., Shugurov I. S. On Process Model Synthesis Based on Event Logs with Noise // MAIS. — 2014. — Т. 21, № 4.

91. Shugurov I., Mitsyuk A. A. Generation of a Set of Event Logs with Noise // Proceedings of the 8th Spring/Summer Young Researchers Colloquium on Software Engineering, SYRCoSE 2014 / под ред. A. Kamkin, A. Petrenko, A. Terekhov. — ISP RAS, 2014. —URL: http://syrcose.ispras. ru/2014/files/SYRCoSE2014_Proceedings.pdf.

92. URL: https://products.office.com/en-us/visio/flowchart-software.

93. Шершаков С. А. Графический язык DPMine для автоматизации экспериментов в области автоматического построения и анализа процессов // Моделирование и анализ информационных систем. — 2014. — Т. 21, № 5. — С. 102—115.

94. Shershakov S. DPMine: modeling and process mining tool // Proceedings of the 7th Spring/Summer Young Researchers' Colloquium on Software Engineering, SYRCoSE 2013. — 2013.

95. Матюшенко А., Якимчук С. Visio 2010. Визуализация данных и работа с диаграммами в различных индустриях: Microsoft tech-ed 2011 / Microsoft. — 2011. — URL: https://channel9. msdn.com/Blogs/TechDays-Russia/OFS210-Visio-2010--20111205090000.

96. Aalst W. van der, NetjesM., ReijersH. Supporting the Full BPM Life-Cycle Using Process Mining and Intelligent Redesign // Contemporary Issues in Database Design and Information Systems Development / под ред. K. Siau. — 2007. — С. 100—132.

98. URL: https://docs.microsoft.com/ru-ru/windows/win32/com/component-object-model--com--portal.

99. DijkstraE. Cooperating Sequential Processes // TR EWD-123. — 1965.

100. Reisig W. Understanding Petri Nets: Modeling Techniques, Analysis Methods, Case Studies. — Springer, 2010.

101. URL: https://docs.microsoft.com/en-us/office/dev/add-ins/visio/.

102. DPModel Official Website. — URL: https://prj.xiart.ru/projects/dpmodel.

103. Boost Python Library ver. 1.72. — URL: https://www.boost.org/doc/libs/1_72_0/libs/python/ doc/html/tutorial/index.html.

104. Anaconda Data Science Platform. — URL: https://www.anaconda.com/.

105. On Global Completeness of Event Logs: тех. отч. / H. Yang [и др.]; BPM Center. — 2010.

Список рисунков

1.1 а) «Цветочная» модель в виде системы переходов с одним состоянием, построенная для журнала Ь\, б) Полная система переходов (префиксное дерево) TSi(Li), построенная для лога Li; везде дуги помечены событиями и частотой их появления в

логе в соответствии с определением функции частоты................... 15

1.2 Связь между метриками модели: степень соответствия (fitness), точность (precision), сложность (simplicity).............................. 16

2.1 Система переходов с 1-окном, построенная для журнала Li................ 20

2.2 Схема трехэтапного построения-редукции полной системы переходов для журнала событий. Прямоугольники в нижней трети изображения — графические исполняемые блоки языка DPMine (см. раздел 5.2), входящие в схему эксперимента по редукции системы переходов с последующим измерением метрик редуцированной модели .... 21

2.3 Алгоритм построения полной системы переходов (префиксного дерева) для журнала событий L ........................................... 22

2.4 Алгоритм построения конденсированной системы переходов TS2(L)........... 23

2.5 Система переходов TS2(Li) (конденсированная), построенная на основе TSi(Li) с параметром Threshold =0.33................................. 24

2.6 Алгоритм построения редуцированной системы переходов TS3(L)............ 25

2.7 Процедура (функция) ReplayTrace алгоритма построения редуцированой системы переходов TS3(L)........................................ 26

2.8 (а) TS3 восстанавливается алгоритмом: помечены временные состояния и переходы, полученные после первого этапа; (б) восстановленные состояния и переходы после второго этапа; (в) (редуцированная) система переходов TS3(Li), построенная на

основе TS2(Li) с Threshold = 0,33 для журнала Li..................... 28

2.9 Процедура RestateTS алгоритма построения редуцированной системы переходов TS3(L).............................................. 29

2.10 Редуцированная система переходов TS3(Li), построенная для журнала событий Li (1.2) с параметрами Threshold = 0,5 и Vwsc = 0,3. Символом «*» отмечено состояние-ловушка ...................................... 30

2.11 Системы переходов, построенные для журнала L2: (а) TSf (L2) с фиксированным окном размера 1; (б) полная TSi(L2); (в) граф развертки, полученный после

симуляции системой переходов TSi(L2) полной системы переходов TSf (L2) ...... 33

2.12 Последовательность шагов при симуляции генерализованной системой переходов (слева) точной системы переходов (справа) при выполнении расчета метрики точность: (а) шаг события a в обеих моделях; (б) шаг события b в обеих моделях; (в) шаг события c в обеих моделях; (г) переход в заключительное (принимающее) состояние в обеих моделях; (д) генерализованная модель допускает событие d,

которое не допускает точная модель: начисление штрафного очка ............ 34

2.13 Подпрограмма CalcStatePrecision, вычисляющая «частичную точность» всех состояний в виде функции п ................................. 36

2.14 Подпрограмма RecalcStatePrecision обновляет значение «частичной точности» состояния ............................................ 37

2.15 Алгоритм расчета метрики precision для системы переходов TS(L)............ 37

2.16 Подпрограмма (функция) SumPartialPrecisions, вычисляющая точность всей системы переходов TS(L)................................... 38

2.17 Графики изменения метрик сложность (Simpl) и точность (Prec) для систем переходов, построенных для журнала L3: (а) методом простой редукции — зависимость от параметра k; (б) методом частотной редукции — зависимость от параметра Vwsc при фиксированном Threshold =0,33................... 40

2.18 Графики изменения метрик сложность (Simpl) и точность (Prec) для систем переходов, построенных для журнала L4: (а) методом простой редукции — зависимость от параметра k; (б) методом частотной редукции — зависимость от параметра Vwsc при фиксированном Threshold = 0,33 ................... 40

3.1 Двухшаговый подход к синтезу сети Петри через промежуточную модель в виде системы переходов, которая построена по журналу событий ............... 48

3.2 Алгоритм синтеза сети Петри по системе переходов с использованием теории регионов, допускающий наличие петель в системе переходов ............... 50

3.3 Функция GenPreRegionsAndSplit алгоритма синтеза сети Петри........... 51

3.4 Функция GenMinPreRegions алгоритма синтеза сети Петри............... 51

3.5 Функция ExpandState алгоритма синтеза сети Петри .................. 52

3.6 Функция SplitLabels алгоритма синтеза сети Петри .................. 54

3.7 Трехшаговый подход к синтезу сети Петри: на втором шаге после конструирования системы переходов осуществляется ее параметрическая редукция до размеров, практически пригодных для использования с алгоритмом регионов ........... 55

3.8 Система переходов (а) и сеть Петри (б), построенные для журнала событий L. Двойной обводкой в системе переходов обозначены конечные или принимающие состояния. В сети Петри маркерами • обозначено наличие фишек в позициях начальной разметки; в фигурных скобка обозначены состояния, входящие в состав региона для данной позиции ................................. 59

3.9 Преобразованная система переходов (а) с единственным принимающим состоянием

sfin и соответствующая ей WF-сеть (б) с начальной позицией i и конечной позицией o 61

3.10 Система переходов TS1 с петлей x (а) и покрытие этой системы регионами (б)..... 62

3.11 Система переходов TSl с петлей х (а); синтезированная сеть Петри с восстановленной петлей (б) — вторая политика работы с петлями; синтезированная сеть Петри с

обработкой петель модифицированным алгоритмом регионов (в) — третья

политика работы с петлями................................. 63

3.12 Система переходов TS1 с петлей x (а); эквивалентная система переходов TS1 с развернутой петлей (б); система переходов TS1, покрытая регионами (в); синтезированная по системе переходов TS1 сеть Петри с обработкой петель модифицированным алгоритмом регионов (г)........................ 65

3.13 Система переходов TS (а); покрытие этой системы регионами при отыскании пререгионов для события a (б); сеть Петри, синтезированная при неверном определении пререгионов для события a (в); сеть Петри, синтезированная при правильном определении пререгионов для события a (г) ................. 66

4.1 Компонентный подход: библиотека LDOPA алгоритмов и структур данных для

process mining и два ее клиента................................ 74

4.2 Уровни абстракции четырех языков программирования.................. 75

4.3 Модульная схема библиотеки LDOPA............................ 77

4.4 Два различных подхода к организации иерархии типов моделей: (а) глубокая

иерархия типов с преимущественным наследованием; (б) неглубокая (плоская) иерархия типов с преимущественной декомпозицией с применением паттерна адаптер 80 4.5 Фрагмент ЦМЪ-диаграммы классов, представляющей графовые типы для систем

переходов. Верхняя прямоугольная область объединяет типы со встраиваемыми

атрибутами, нижняя — типы с ассоциированными атрибутами............................82

4.6 Архитектурная схема "Домены — Процессы — Сервисы" ................................84

4.7 Структурная схема обработки журнала событий с использованием РСУБД..............87

4.8 Фрагмент реляционной диаграммы БД-журнала событий..................................90

4.9 Результирующее отношение следования между всеми парами событий, принадлежащих одинаковым трассам........................................................95

4.10 DFR-граф, построенный по отношению (таблица 11) для журнала событий Lsi..........98

4.11 Нечеткая карта, отображающая связи между процессами с параметрами AP(1,1). . . . 100

4.12 Связь между доменами search, bocamo и content.....................100

4.13 UML диаграмма последовательности для трассы 190248972438317148..........101

4.14 Подсистема EventLog библиотеки LDOPA..........................110

5.1 Общая структурная схема разработанного программного обеспечения..........115

5.2 Уровни представления модели................................117

5.3 Схема иерархии блоков....................................118

5.4 Пример (а) схемы модели DPMine и (б) сети Петри, моделирующей исполнение этой схемы ............................................................................................118

5.5 UML-диаграмма объектов Visio ...............................121

5.6 Графическое представление сети Петри, моделирующей задачу об обедающих философах...........................................124

5.7 Ключевые компоненты VTMine for Visio..........................125

5.8 Лента панели меню/инструментов VTMine for Visio ...................126

5.9 Основные VTMine for Visio-плагины, созданные в рамках данной работы.......129

5.10 Элементы управления, настраиваемые через менеджер пользовательского интерфейса 131

5.11 Компоненты базового плагина DPMine и их взаимодействие с библиотеками и другими плагинами (внешние зависимости представлены пунктирными прямоугольниками с прямыми или скругленными углами) ..................................134

5.12 Элементы графического блока расчета метрик систем переходов............139

5.13 Параметры графического блока расчета метрик систем переходов...........139

5.14 Модель синтеза системы переходов по журналу событий и визуализация модели . . . . 139

5.15 Параметры блока SQLite-журнала событий (а) и блока параметрического синтеза систем переходов (б) ..........................................................................139

5.16 Аннотация с информацией об источнике модели......................141

5.17 Модель синтеза системы переходов с последующей редукцией и расчетом метрик ... 142

5.18 Параметры блока построения конденсированной системы (а) и блока восстановления конденсированной системы переходов (б)..........................143

5.19 Параметры порта блока логированиярезультатов эксперимента (а) и параметры

самого блока (б)........................................143

5.20 Модель синтеза сети Петри по журналу событий методом регионов через промежуточную систему переходов.............................146

5.21 Параметры блока синтеза сети Петри алгоритмом регионов................146

5.22 Сеть Петри, синтезированная для журнала событий a1 (раздел 6.1.4)..........147

5.23 Модель синтеза сети Петри по журналу событий методом регионов через промежуточную систему переходов.............................147

5.24 Схема проведение массовых экспериментов с помощью сценариев Python .......149

6.1 Фрагмент префиксного дерева, построенного для журнала событий r1 с помощью инструмента VTMine for Visio.................................155

6.2 Семейство графиков зависимости метрик для журнала событий r1 от переменной Vwsc с параметром Threshold. Оранжевым с маркерами в виде звездочек — метрика precision, синим с маркерами в виде точек — метрика simplicity .............156

6.3 Семейство графиков зависимости метрик для журнала событий r1 от переменной Threshold с параметром Vwsc. Оранжевым с маркерами в виде звездочек — метрика precision, синим с маркерами в виде точек — метрика simplicity .............157

6.4 Графики изменения метрик точность (а) и сложность (б) систем переходов, построенных для журнала событий r1 методом частотной редукции...........158

6.5 Семейство графиков метрик для журнала событий r2 от переменной Vwsc с параметром Threshold. Оранжевым с маркерами в виде звездочек — метрика

precision, синим с маркерами в виде точек — метрика simplicity ............. 161

6.6 Семейство графиков метрик для журнала событий r2 от переменной Threshold с параметром Vwsc. Оранжевым с маркерами в виде звездочек — метрика precision,

синим с маркерами в виде точек — метрика simplicity...................162

6.7 Графики изменения метрик точность (а) и сложность (б) систем переходов, построенных для журнала событий r2 методом частотной редукции ..........163

6.8 Фрагмент префиксного дерева, построенного для журнала событий r2 с помощью инструмента VTMine for Visio.................................164

6.9 Конденсированные системы переходов, построенные для журнала r2, с параметром Threshold, равным: (а) 0,1; (б) 0,2; (в) 0,4 ..........................165

6.10 Кластеры в префиксном дереве, построенном для журнала событий r2.........166

6.11 Конденсированная часть префиксного дерева, построенного для журнала r3 с параметрами Threshold =0.1 (а) и Threshold =0.25 (б) ..................167

6.12 Семейство графиков метрик для журнала событий r3 от переменной Vwsc с параметром Threshold. Оранжевым с маркерами в виде звездочек — метрика

precision, синим с маркерами в виде точек — метрика simplicity .............168

6.13 Семейство графиков метрик для журнала событий r3 от переменной Threshold с параметром Vwsc. Оранжевым с маркерами в виде звездочек — метрика precision,

синим с маркерами в виде точек — метрика simplicity...................169

6.14 Графики изменения метрик точность (а) и сложность (б) систем переходов, построенных для журнала событий r3 методом частотной редукции ..........170

6.15 Префиксные деревья, построенные с помощью инструмента VTMine for Visio, для журналов событий: (а) — a1; (б) — a2 ...........................171

6.16 Семейство графиков метрик для журнала событий a1 от переменной Vwsc с параметром Threshold. Оранжевым с маркерами в виде звездочек — метрика

precision, синим с маркерами в виде точек — метрика simplicity .............172

6.17 Семейство графиков метрик для журнала событий a1 от переменной Threshold с параметром Vwsc. Оранжевым с маркерами в виде звездочек — метрика precision,

синим с маркерами в виде точек — метрика simplicity...................173

6.18 Графики изменения метрик точность (а) и сложность (б) систем переходов, построенных для журнала событий a1 методом частотной редукции ..........174

6.19 Графики метрик для журнала событий a1 от переменной Vwsc с параметром Threshold, изменяющихся в диапазоне Vwsc £ (0,005; 0,015), Threshold £ (0,02; 0,03). Оранжевым с маркерами в виде звездочек — метрика precision, синим с маркерами в

виде точек — метрика simplicity...............................175

6.20 Семейство графиков метрик для журнала событий a2 от переменной Vwsc с параметром Threshold. Оранжевым с маркерами в виде звездочек — метрика

precision, синим с маркерами в виде точек — метрика simplicity .............176

6.21 Семейство графиков метрик для журнала событий a2 от переменной Threshold с параметром Vwsc. Оранжевым с маркерами в виде звездочек — метрика precision,

синим с маркерами в виде точек — метрика simplicity...................177

6.22 Графики изменения метрик точность (а) и сложность (б) систем переходов, построенных для журнала событий a2 методом частотной редукции ..........178

6.23 «Двухкомпонентная» модель, реализующая частые поведения в виде части префиксного дерева («конденсированная» компонента), а редкие поведения в виде «цветочной» компоненты...................................179

6.24 Сравнение производительности реализаций РяоМ и LDOPA по времени (а) и по

памяти (б)............................................185

6.25 Профилирование памяти экземпляра процесса LDOPA-реализации алгоритма построения префиксного дерева для журнала г3......................186

Список таблиц

1 Метрики системы переходов, построенных методом простой редукции (фиксированный размер окна) для журнала событий L3 при различных значениях k . . 39

2 Метрики системы переходов, построенных методом частотной редукции для журнала событий L3 при разных значениях Vwsc и Threshold.................... 39

3 Метрики системы переходов, построенных методом простой редукции (фиксированный размер окна) для журнала событий L4 при различных значениях k . . 41

4 Метрики системы переходов, построенных методом частотной редукции для журнала событий L4 при различных значениях Vwsc и Threshold .................. 41

5 Инструменты для process mining............................... 72

6 Интерфейсы (БД-таблица Interfaces)........................... 91

7 События (БД-таблица TracingEvents)........................... 91

8 Представление журнала событий Ls1 в виде таблицы events базы данных....... 96

9 Фрагмент таблицы отношения следования между событиями для журнала событий Ls1 97

10 Таблица отношения прямого следования между событиями для журнала событий Ls1 . 97

11 Таблица отношения прямого следования между сгруппированными событиями с

учетом частотности ...................................... 98

12 Статистика используемых операций по доменам (результирующий набор данных для SQL-запроса)..........................................103

13 Фрагмент журнала событий..................................107

14 Конфигурационная таблица Config.............................112

15 Блоки DPModel........................................140

16 Фрагмент БД с логированными результатами экспериментов ............... 145

17 Свойства журналов событий, используемых в экспериментах по изучению влияния параметров Vwsc и Threshold.................................153

18 Результаты экспериментов по синтезу сетей Петри по редуцированным системам переходов для различных значений алгоритма редукции .................. 181

19 Результаты экспериментов по сравнению производительности реализаций ProM и LDOPA.............................................185