Регистрация / Вход
Прислать материал

РЕШЕНИЕ ПРОБЛЕМЫ ПРОВЕРКИ СООТВЕТСТВИЯ МЕЖДУ АБСТРАКТНОЙ МОДЕЛЬЮ ПРОЦЕССА И ДЕТАЛЬНЫМ ЖУРНАЛОМ СОБЫТИЙ

Сведения об участнике
ФИО
Бегичева Антонина Константиновна
Вуз
Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Национальный исследовательский университет "Высшая школа экономики"
Тезисы (информация о проекте)
Область наук
Информационные технологии и вычислительные системы
Раздел области наук
Информатика
Тема
РЕШЕНИЕ ПРОБЛЕМЫ ПРОВЕРКИ СООТВЕТСТВИЯ МЕЖДУ АБСТРАКТНОЙ МОДЕЛЬЮ ПРОЦЕССА И ДЕТАЛЬНЫМ ЖУРНАЛОМ СОБЫТИЙ
Резюме
Process mining – это технология, которая посредством извлечения данных из журнала событий предоставляет различные методы для исследования реального процесса, его улучшения и контроля над ним. В работе мы рассматриваем проблему проверки соответствия между высокоуровневой моделью процесса и журналом событий. Проверка соответствия интенсивно изучается, но в литературе можно найти только методы, позволяющие измерить этот показатель между логом и моделью одного уровня. В работе предложен алгоритм проверки соответствия между высокоуровневой моделью процесса (построенной экспертами) и низкоуровневым журналом событий (сгенерированным системой), а также доказана его применимость.
Ключевые слова
Process mining, проверка соответствия, высокоуровневые модели, модели процессов, логи событий, абстрактные модели, сети петри, алгоритм проверки соответствия
Цели и задачи
Цель работы: предложить алгоритм проверки соответствия между высокоуровневой моделью бизнес-процесса и низкоуровневым логом событий и предоставить экспериментальное подтверждение справедливости работы алгоритма.
Задачи: 1. разработать алгоритм проверки соответствия между абстрактной моделью и детальным логом событий;
2. доказать правильность работы алгоритма в случае идеального соответствия;
3. реализовать алгоритм в среде ProM;
4. выполнить эксперименты по проверке алгоритма на специально сгенерированных логах с шумами разных видов и на моделях с различными шумами;
5. провести анализ экспериментов по проверке алгоритма.
Введение

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

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

 

Методы и материалы

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

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

Методы проверки соответствия для одноуровневых данных (например, детальной модели и детального лога) так или иначе основываются на одной из двух техник: сравнение следов действий модели и лога, либо "проигрывание" событий из лога на модели (оба метода были предложены Анне Розинат). Мы в своей работе опираемся на метод "проигрывания", так как он дает более полную иинформацию о согласованности лога и модели. 

Описание и обсуждение результатов

Потоки работ можно моделировать с разной степенью детализации. Соответствие между моделями разного уровня, описывающими один и тот же процесс, естественно задавать при помощи уточнений. Когда переход из модели является ссылкой на подпроцесс, такой переход является абстрактным (высокоуровневым). В таком случае, при подстановке вместо каждого перехода модели его подпроцесса получается детальная (низкоуровневая) модель. Такой принцип иерархии используется, в частности, в раскрашенных сетях Петри (CPN). Уточнения позволяют разрабатывать более компактные модели с композиционной сетевой структурой.

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

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

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

Используемые источники
1. W. M. P. Van der Aalst, Process Mining: Discovery, Conformance and Enhancement of Business Processes. Berlin: Springer-Verlag, 2011.
2. A. Rozinat, W. M. P. Van der Aalst, Conformance Testing: Measuring the Alignment Between Event Logs and Process Models. BETA Working Paper Series, Eindhoven University of Technology, 2005, vol.144, pp 203-210.
3. A. Rozinat, Process mining: conformance and extension. Technische Universiteit Eindhoven, PhD thesis, 2010.
4. K. Jensen, L. M. Kristensen, Coloured Petri Nets: Modelling and Validation of Concurrent Systems. Berlin: Springer Verlag, 2009.
5. A. Rozinat, W. M. P. van der Aalst, Conformance Checking of Processes Based on Monitoring Real Behavior.
6. T. Murata, Petri Nets: Properties, Analysis, and Applications. Proceedings of IEEE, 1989
Information about the project
Surname Name
Begicheva Antonina
Project title
Solution to the Problem of Checking Conformance of High-level Process Model Behavior with Event Log
Summary of the project
Process mining is a relatively new field of computer science, which deals with process discovery and analysis based on event logs. In this paper we consider the problem of models and event logs conformance checking. Conformance checking is intensively studied in the frame of process mining research, but only models and event logs of the same granularity were considered in the literature. Here we present
and justify the method of checking conformance between a high-level model (e.g. built by an expert) and a low-level log (generated by a system).
Keywords
Petri nets, high-level process models, event logs, process mining, conformance checking