Резюме (1137086), страница 5
Текст из файла (страница 5)
Данная модель содержит два фрагмента с несоответствиями, которыевыделены на рисунке красным цветом. В данном примере были переставленыместами пометки двух переходов из выделенных фрагментов. Жадный алгоритм начинает работу с одного из фрагментов и выполняет девять итераций,на каждой из которых увеличивается размер заменяемой суб-сети. В конечном итоге вся часть модели, выделенная на рисунке, будет заменена зановосинтезированной моделью.443536759845328546789Iterations:111237234567898These fragments do not fit the logРисунок 11: Пример работы жадного алгоритма исправления модели процессаВо второй части диссертации предлагается семейство алгоритмов исправления модели процесса, которые базируются на общей модульной схеме.Основная идея, лежащая в основе всех этих алгоритмов, состоит в том, чтобы декомпозировать исходную модель, найти суб-сети с несоответствиями, азатем заменить их заново синтезированными моделям, которые бы соответствовали журналу событий.Извлечение и анализ процессов — это практическая дисциплина, а потому новые алгоритмы, как правило, оцениваются в том числе и экспериментально с использованием примеров журналов событий.
Крайней трудноподобрать реальные модели процессов и журналы событий информационныхсистем так, чтобы они обладали характеристиками, необходимыми для их использования при тестировании алгоритмов исправления. Поэтому в даннойдиссертации предлагаются методы генерации синтетических журналов событий, которые позволяют тонко настраивать характеристики получающихсяжурналов событий. Эти методы описываются в третьей части диссертации.С использованием генератора журналов событий был подготовленбольшой набор подходящих журналов событий, которые затем использованы23для экспериментальной оценки модульного подхода исправления. Результатыэтой оценки приводятся в четвёртой части диссертации.В третьей части диссертации описываются вспомогательные инструменты, которые использовались для генерации примеров журналов событий.В данной работе предлагается набор алгоритмов генерации журналов событий посредством симуляции сетей Петри и моделей BPMN 2.0.
Предлагаемые алгоритмы реализованы в виде программных прототипов, которые также описываются в третьей части работы.Данная часть состоит из двух основных разделов. В первом разделеописываются алгоритмы генерации журналов событий в результате симуляции сетей Петри.
Аналогичный подход, применимый для моделей в нотацииBPMN 2.0, описывается во втором разделе.Предлагаемый метод симуляции сети Петри основывается на стандартных правилах срабатывания переходов в сетях Петри. Описываемый генератор обладает следующими основными возможностями:∙ Пользователь имеет возможность задать количество журналов событийдля генерации, а также количество трасс в каждом из журналов.
Такжетребуется задать максимальное количество событий в трассе, что позволяет останавливать алгоритм в случае наличия бесконечных цикловв модели. Все журналы событий генерируются во время одного запускапрограммы. По умолчанию генерируется 5 журналов событий, каждыйиз которых содержит 10 трасс с не более чем 100 событиями.∙ Если в модели присутствует недетерминированный выбор, пользовательимеет возможность задать правила выбора перехода для срабатывания.Инструмент может выбирать случайный переход с равной вероятностью.Кроме того, пользователь может задать приоритеты срабатывания, атакже более и менее предпочтительные переходы для срабатывания сзаданным уровнем вероятности.∙ Кроме того, поддерживается симуляция моделей, имеющих временныехарактеристики. Пользователь может задать время срабатывания длякаждого перехода, а также точность срабатывания путём определенияграниц отклонения времени срабатывания от эталонного.
В таком случаекаждому срабатыванию перехода в журнале событий будут соответствовать два события. Первое из них отмечает начало исполнения действияпроцесса. Второе событие отмечает окончание исполнения действия.24∙ Кроме трасс, точно отражающих варианты исполнения модели, инструмент способен подмешивать в журнал событий шум различного характера.В данной части также описываются алгоритмы, предлагаемые для симуляции моделей в нотации BPMN 2.0. Поддерживаются модели, содержащиебазовые элементы BPMN (задачи, шлюзы AND/XOR), объекты данных, потоки сообщений. Данные алгоритмы также позволяют задавать временныехарактеристики моделей и генерировать журналы событий с указанием времени выполнения действий процесса.Кроме того, в данной части описывается тестирование и оценка алгоритмов генерации.
Сами эти алгоритмы использованы для генерации синтетических журналов событий, которые используются для оценки модульныхалгоритмов исправления моделей процессов. Результаты оценки приводятсяв следующей части диссертации.В четвёртой части диссертации описывается программный прототип, реализующий модульный подход исправления моделей процессов, а также приводятся результаты экспериментальной оценки подхода с использованием данного прототипа.Модульный подход исправления реализован в виде программного прототипа, который выполнен как расширение среды ProM 6 Framework [26],являющейся наиболее распространённым открытым инструментом в сообществе исследователей process mining. В данной части кратко описываются главные особенности этой реализации и её архитектура.
Исходный код прототипа свободно доступен на странице проекта: http://pais.hse.ru/research/projects/iskra.Для оценки алгоритмов исправления была использована экспериментальная схема, показанная на рисунке 12. Цель экспериментальной оценки— применить прототипные реализации алгоритмов к тестовым примерам,а затем измерить характеристики результирующих исправленных моделей.Результаты этих измерений демонстрируют сильные и слабые стороны алгоритмов, когда они применяются для исправления несоответствий различногохарактера.В начале четвёртой части приводится описание нескольких моделейпроцессов, а также соответствующих синтетических журналов событий.
Длякаждого примера модели был сгенерирован журнал событий, идеально соответствующий модели.Естественный способ протестировать и оценить метод исправленияустроен следующим образом. Возьмём корректно функционирующий объ25Sample ModelEvent LogGeneratorEventLogProcess ModelRepairChangedModelRepairedModelEvaluationResultsРисунок 12: Схема экспериментальной оценкиект , внесём в него искусственные несоответствия (получим ), а затем попробуем исправить с использованием метода, который требуетсяоценить/протестировать. Если метод исправления работает в соответствии сожиданиями его разработчика, исправленный объект должен работатьтак же, как и исходный исправный объект . Если это не так, тест провален. При этом характеристики исправленного объекта могут быть измереныс использованием подходящих измерительных инструментов.
Результаты измерений, полученные при проведении различных экспериментов, могут сравниваться между собой и анализироваться.Именно таким образом и была устроена экспериментальная оценкамодульного подхода исправления модели процесса, которая описывается вчетвёртой части диссертации. В нашем случае метод исправления успешнопроходит тест, если он способен реконструировать исходную модель, которая использовалась для генерации нормативного журнала событий. Кромепредложенных в данной работе, оценивались и другие методы исправления,чтобы сравнить результаты работы различных подходов.
В данной части приводятся таблицы и рисунки с результатами исправления моделей процессовразнообразными алгоритмами.Проведённые эксперименты показали работоспособность и применимость подхода исправления, предлагаемого в данной диссертации.Наивный метод позволяет исправить модель по критерию соответствия журналу событий, но существенным образом снижает точность модели.26Более того, после исправления этим методом иногда получаются модели, допускающие очень много вариантов поведения, что не позволяет алгоритму,основанному на использовании выравниваний, успешно вычислить точностьмодели на имеющихся аппаратных средствах. Такое происходит в случаях,когда исправленная модель содержит много невидимых переходов и переходов без входных/выходных дуг.Усовершенствованный метод справился с реконструкцией исходной модели в большинстве экспериментов и может быть признан эффективным поитогам экспериментальной оценки.Рисунок 13: Модель, показанная на рисунке 1, исправленная с помощьюусовершенствованного методаПример исправления модели, показанной на рисунке 1, с помощьюусовершенствованного метода приводится на рисунке 13.
Фрагменты модели,которые были заменены при исправлении, выделены зелёным цветом. Можнозаметить, что алгоритм исправления сохранил структуру исходной модели.Кроме того, оценивалась эффективность методов исправления в техслучаях, когда несоответствия нелокальны. В таких экспериментах лучшесебя показал жадный метод исправления. Тем не менее, этот метод, как правило, вносит больше изменений в модель, чем усовершенствованный алгоритм. Используя данные, приводимые в данной части, нетрудно сравнитьпредложенные в диссертации методы исправления между собой и с другими методами, известными из литературы.
Для рассмотренных примеров точность моделей, исправленных жадным методом, существенно не отличаласьот моделей, синтезированных с нуля.Рисунок 14: Большая модель, исправленная с помощью жадного метода сиспользованием индуктивного алгоритма синтезаМетоды, предложенные в диссертации, также показали свою применимость для моделей существенного размера. Например, на рисунке 14 пока27зана модель, содержащая более тысячи узлов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
