Резюме (1137086), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Журналом событий (или просто журналом) будем называть конечное мультимножество трасс, то есть ∈ ℬ(* ). Например,[︀]︀ = ⟨,,,,⟩3 , ⟨,,,,⟩5 , ⟨,,,,⟩ — это журнал событий с действиями из того же множества, что и модель, изображённая на рисунке 3.11В-третьих, описываются три составляющие дисциплины анализа процессов.

Анализ и извлечение моделей процессов (Process mining) — это область исследований на стыке формальных методов и наук о данных [5]. Врамках данной дисциплины разрабатываются методы анализа процессов винформационных системах на базе журналов событий, записываемых в ходе жизненного цикла системы. Рассматривают алгоритмы трёх основныхтипов: для автоматического синтеза модели процесса по журналу событий(process discovery), для проверки согласованности модели и журнала событий (conformance checking), для усовершенствования или улучшения моделипроцесса (process enhancement).

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

Методы и техники усовершенствования моделей процессов обычно более формальны. Алгоритмыисправления моделей процессов (или просто исправления моделей) относятсяк этой последней категории методов [5].Далее в данной части рассмотрены четыре основных численных критерия качества модели процесса: соответствие (fitness), точность (precision),обобщённость (generalization), простота (simplicity). Эти критерии используются повсеместно в ходе анализа моделей процессов [5].Первые два применяются для проверки согласованности модели ижурнала событий. Соответствие показывает в какой степени трассы журнала событий могут быть воспроизведены моделью.

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

В диссертации для подсчёта согласованности модели и логаприменяется подход, основанный на применении так называемых выравни12ваний [22], который является общепринятым среди специалистов по анализумоделей процессов в настоящий момент.Кроме того, в данной части описываются различные алгоритмы автоматического синтеза модели процесса [5]. Для использования в данной работеотобраны два таких алгоритма: индуктивный алгоритм Inductive miner [23]и алгоритм ILP miner [24], сводящий задачу синтеза к задаче целочисленноголинейного программирования. Выбор этих двух алгоритмов обуславливаетсятем, что они оба, если используются с верно заданными настройками, обеспечивают синтез моделей, идеально соответствующих журналам событий, использованным в качестве исходных для синтеза.В-четвёртых, в данной части приводится обзор методов исправлениямоделей процессов, предложенных ранее.

Рассматриваются конкретные постановки задач, способы решения и их особенности.Предлагаемый в данной диссертации подход также имеет ряд специфических свойств. Наиболее схожим из известных является способ, предложенный Д. Фаландом (D. Fahland) и В. ван дер Аалстом (W. van der Aalst) [25].Тем не менее, отличием является тот факт, что в данной диссертации применяются техники декомпозиции модели, что позволяет затем заменить фрагменты модели с несоответствиями. Таким образом, исправленная модель отличается от исходной только в пределах заменённых (исправленных) фрагментов.

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

Сеть потоков работ = (, , , ) с пометками переходов из — это исходная модельпроцесса. Также в данной сети могут быть невидимые переходы, помеченныес помощью специальной пометки . Таким образом, функция пометки имеетследующий вид: : → ∪ { }.13Журнал событий — это мультимножество трасс в соответствии сопределением из раздела 1.1.3. Имена событий выбираются из того же множества действий , то есть ∈ ℬ(* ). Заметим, что имена событий журнала и пометки переходов модели берутся из одного множества , то есть() = . Это означает, что среди действий процесса нет новых или устаревших, а метод исправления не добавляет новых переходов в модель процесса и не удаляет из неё старых, кроме, может быть, помеченных меткой .Кроме того, предполагается, что все переходы модели имеют уникальные пометки.

Это правило очевидным образом не распространяетсяна невидимые переходы, помеченные меткой . Таким образом, в модели = (, , , ), ∀1 , 2 ∈ : если (1 ) = (2 ), то 1 = 2 . Заметим, что данноепредположение потребуется на этапе декомпозиции модели процесса.

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

Это строгое условие, которое обязательно должно выполняться дляуспешности исправления модели.Кроме того, имеются два мягких условия, выполнение которых желательно, но не всегда достижимо.Во-первых, желательно, чтобы исправленная модель была точнойпо отношению к журналу событий . не должна допускать «слишкоммного» вариантов исполнения, которые не представлены в . По меньшеймере модель должна быть насколько же точна, насколько точна былаисходная модель , то есть ( ) ≈ ( ). Другими словами,желательно, чтобы исправленная и исходная модели были приблизительноодинаково точными.

В лучшем случае ( ) = ( ).Во-вторых, желательно, чтобы модели и имели сходную структуру. Алгоритм исправления тем лучше, чем меньше изменений он вноситв исправляемую модель. Именно поэтому в разделе 4.3, где описываютсярезультаты экспериментальной оценки предложенных методов исправления,приводятся результаты подсчёта числа элементов модели, затронутых проце14дурой исправления. Это число демонстрирует, насколько метод исправленияизменяет исходную модель.Далее во второй части представлены основные результаты диссертации. Во-первых, описана модульная схема предлагаемого подхода исправления модели процесса. Во-вторых, представлены алгоритмы, реализующиеобобщённую модульную схему для конкретных вариантов исправления.Модульная схема, предлагаемая в данной диссертации, основана наидее использования заплаток. Алгоритм отыскивает в исходной моделифрагменты с несоответствиями, которые затем заменяются фрагментами, соответствующими поведению, записанному в журнале событий.

Подход является модульным. Это означает, что обобщённая схема конструируется изнескольких составляющих блоков. В качестве каждого из таких блоков могутвыступать разнообразные конкретные алгоритмы. Таким образом, обобщённая схема может быть материализована в виде многих различных алгоритмовисправления. Для этого необходимо осуществить выбор конкретных алгоритмов, для использования в качестве процедурных аргументов схемы.EventLogInputInitialWorkflow netDecompositionProjectionSelectionSub-netsConformingSub-netsSub-logsNon-conformingSub-netsCompositionSub-logs forNon-conformingSub-netsCorrectedSub-netsRepairEvaluationEvaluationResultOutputCorrectedWorkflow netРисунок 4: Модульная схема исправленияКаждый составляющий блок модульной схемы выполняет один из шагов исправления. Графическое изображение модульной схемы приводится на15рисунке 4.

На этом рисунке составляющие строительные блоки показаны спомощью ярких цветных прямоугольников.На вход схемы подаётся пара (, ), где — корректный (нормативный, доверенный) журнал событий, а — исходная модель с несоответствиями. Модель декомпозируется на фрагментов 1 , 2 , . . . , с использованием одного из алгоритмов декомпозиции модели. В блоке проецированияалгоритм разделяет журнал событий на суб-журналов 1 , 2 , .

. . , , каждый из которых соответствует одному фрагменту модели (суб-сети). В блокевыбора помещается алгоритм проверки согласованности модели и журналасобытий. Этот алгоритм применяется для вычисления степени согласованности каждой пары ( , ), где = 1, 2, . . .

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

Пусть — это универсальное множество действий, а N — множество всех сетей потоков работ с пометками переходов из .Определим модульную схему исправления как процедуру, принимающую на вход журнал событий ∈ ℬ(* ) и помеченную сеть потоковработ N ∈ N , и возвращающую в качестве результата своей работы сетьПетри N r = ModularRepair (, N ), идеально соответствующую журналусобытий , то есть (,N r ) = 1.Модульная схема исправления имеет следующие процедурные параметры:∙ eval ∈ (ℬ(* ) × N ) → [0; 1] — это функция оценки,∙ repair ∈ (ℬ(* ) × N ) → N — это алгоритм исправления,∙ split ∈ N → (N ) — это алгоритм декомпозиции,∙ compose ∈ (N ) → N — это алгоритм композиции.Как правило, соответствие модели журналу событий рассматривается в качестве основного критерия качества модели.

Характеристики

Список файлов диссертации