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

Актуальность данной задачи объясняется следующими положениями:

1) появление моделей гибких процессов обеспечивает дополнительные возможности;

2) иерархическое представление модели гибкого процесса облегчает понимание модели, позволяет использовать в качестве элементов модели существующие формализованные подпроцессы;

3) построение моделей реально выполняющихся процессов обработки ресурсов на основе логов осуществляется методами интеллектуального анализа процессов;

4) существующие методы process mining основаны на использовании аппарата сетей Петри и ориентированы преимущественно на построение моделей дискретных процессов с жестко заданной структурой;

5) перспективным в рамках искусственного интеллекта представляется развитие аппарата алгебры конечных предикатов как средства для идентификации структур для решения задачи построения моделей гибких процессов.

Анализ базовых исследований в данной области

Выполненный анализ базовых исследований в области построения моделей гибких процессов [2, 5, 6, 7, 8] показал, что полная модель такого процесса может быть получена с помощью традиционного полного цикла разработки модели гибкого многовариантного процесса; слияния моделей нескольких «жестких» процессов, которые реализуют идентичную функциональность, но различным способом. Модель строится на основе анализа логов, содержащих информацию о нескольких вариантах реализации процесса [9]. В данной области прослеживается аналогия с ранними стадиями развития технологий программирования, когда основное внимание уделялось алгоритмизации. В дальнейшем произошел переход к объектно-ориентированным технологиям разработки [1].

Предикатная модель гибкого процесса

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

Предлагаемый автором метод основан на алгоритме построения блок-структурированного процесса и использует свойство рекурсивности процессного дерева. Как было показано в [3], с каждым узлом данного дерева связано либо конкретное действие процесса, либо один из базовых операторов, задающих взаимосвязи между действиями процесса. Указанные операторы реализованы в виде предикатов АКП.

Действия процесса в предлагаемой модели могут быть описаны как переменной, так и предикатом. Представление действия в виде переменной выполняется для простых действий, которые могут описываться конечным количеством состояний:

(1)

где a1 = «ожидание»; a2 = «готовность»; a3 = «выполнение»; a4 = «приостановка»; a5 = «завершено».

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

можно заменить на составной предикат

(2)

Взаимосвязь действий выполняется с помощью предикатов, реализующих базовые структурные элементы процессной модели, как было показано в [3, 4].

Пусть  – N моделей дерева процессов, каждая из которых представлена в виде иерархии предикатов на конечном множестве действий i-го процесса и конечном множестве базовых структурных элементов:

(3)

Определим предикат M по правилам АКП, аргументами которого являются модели Mi.

(4)

Тогда предикат (4) также является деревом процессов, а входящие в его состав модели можно рассматривать как подпроцессы текущего процесса.

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

Следовательно, предикат M будет истинным в том случае, если истинными будут все его аргументы – модели процессов Mi, что и показывает выполнимость интегрального процесса M.

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

Очевидно, что слияние фрагментов предикатной модели осуществляется путем использования предиката более высокого уровня, аргументами которого являются предикаты, формализующие сливаемые фрагменты:

(5)

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

(6)

Будем рассматривать две предикатные модели гибкого процесса в качестве изоморфных в том случае, если из обеих могут быть получены идентичные логические сети:

(7)

если

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

В качестве исходных данных выступает лог гибкого процесса L, полученный слиянием k традиционных логов.

Этап 1. При анализе полного лога L выполняется поиск возможностей его разбиения на более мелкие фрагменты Li, которые в дальнейшем могут быть объединены последовательно, параллельно, циклически или через выбор согласно заданным предикатным операциям [4]:

(8)

Основные, достаточно очевидные ограничения, которые учитываются при разбиении лога на составляющие:

1. Объединение (обратная к разбиению операция) полученных в результате разбиения логов составляет исходный лог либо является надмножеством для исходного лога L;

(9)

2. Длина Length любого полученного фрагмента Li должна быть не больше длины исходного лога:

(10)

Общий подход к разбиению заключается в выделении последовательностей событий, либо входит в состав более сложных конструкций – выбор, параллельное выполнение, цикл:

(11)

Этап 2. Построение предикатной модели на текущем уровне, когда аргументами предиката являются выделенные на этапе 1 фрагменты. Сами выделенные фрагменты еще не формализованы:

(12)

Этап 3. Проверка текущего фрагмента лога: может ли он быть разделен на более мелкие фрагменты:

(13)

что

Этап 4. Если фрагмент лога разделен быть не может, то выбор следующей составляющей модели согласно выражению (10), после чего выполняется переход к этапу 1.

Этап 5. Проверка: все ли доступные фрагменты разделены на составляющие. Если результат положительный, то модель процесса в виде предикатного дерева построена.

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

(14)

Рассмотрим лог, который представлен в виде следующего набора последовательностей событий («следов» выполнения процесса):

(15)

Данный лог отражает следующие возможные элементы процесса:

• ветвление начиная от события s1, поскольку за данным событием в каждом из следов возникают события s2 либо s3, либо s4, либо s7;
• параллельное выполнение действий, которые отражены событиями s2 и s3, поскольку в первой строке событие s2 предшествует событию s3, а во второй – наоборот;
• цикл, поскольку в последней строке пара событий s4, s3 повторяется после события s6;
• последовательности событий s7, s8.

Модель процесса, позволяющая получить рассмотренный выше лог, представляется в виде такого набора предикатов:

(16)

Для нахождения указанной модели целесообразно отдельно выделить ветвление, которое во всех случаях в примере начинается с события s₁, а также последовательности событий s₂, s₃, s₃, s₂, s₄, s₅, s₃, s₆, s₄, s₅, s₇, s₈, отражающие параллельное выполнение, простую последовательность и цикл соответственно. Рассматривая каждую из этих групп как единое целое, сворачиваем наш лог к набору простых последовательностей событий, каждое из которых отражается в модели в виде предиката:

(17)

Далее определяется модель для каждой из последовательностей s₂, s₃, s₃, s₂, s₄, s₅, s₄, s₅, s₃, s₆, s₄, s₅, s₇, s₈. При этом для параллельного выполнения мы разделяем события s₂ и s₃, для цикла - выделяем отдельно повторяющиеся последовательности s₄, s₅, а также событие s₆, которое предположительно соответствует проверке условия повторения.

Обобщив рассмотренный пример, получаем, что для выделения типовых фрагментов необходимо выполнить следующие основные шаги:

1) разделить лог на последовательности событий, которые не содержат ветвлений;

2) разделить фрагменты лога на последовательности событий, которые не содержат циклов и параллельного выполнения;

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

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

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

(18)

где знак ≤ задает отношение упорядоченности событий во времени (т.е. порядок записи событий в логе).

Теперь определим последовательность, состоящую из произвольного количества событий и отражающую различные версии реализации процесса. Пусть имеем набор упорядоченных последовательностей событий ∧ = {∧i}, . Каждая из указанных последовательностей отражает одну из реализаций процесса.

Тогда последовательность действий для процесса выявляется следующим образом. Во-первых, существует выделенный набор последовательностей событий лога ∧ = {∧i}, имеющих идентичные начальные и конечные события. Во-вторых, порядок событий не нарушается в каждой из последовательностей ∧i:

(19)

Параллельное выполнение действий процесса является антиподом для последовательности и потому выявляется в том случае, если порядок для пар событий в различных последовательностях из множества ∧ отличается:

(20)

Выбор (ветвление) определим следующим образом. Пусть имеем набор упорядоченных последовательностей событий ∧ = {∧i}, которые имеют общее начальное событие s*. Набор ∧ отражает ветвление в том и только в том случае, если последовательности ∧i не имеют общих событий за исключением начального s*:

(21)

Теперь определим цикл. Последовательность событий ∧i отражает выполнение цикла в модели процесса при выполнении следующих условий:

1) последовательность ∧i не имеет общих событий с другими последовательностями множества ∧:

; (22)

2) начальное событие текущей последовательности ∧i может иметь последовательную связь с событием из другой последовательности ∧j:

; (23)

3) конечное событие текущей последовательности ∧i может иметь последовательную связь с событием из другой последовательности ∧j:

(24)

4) существует повторяющаяся не менее 2-х раз последовательность событий, являющаяся подмножеством исходной последовательности ∧i:

(25)

Приведенное в начале параграфа ограничение на полноту лога после описания метода можно задать следующим образом: каждое действие каждого варианта процесса должно быть представлено в логе L = {lk} (т.е. в каждом варианте) хотя бы один раз:

(26)

Заключение

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

Исследование выполнено при поддержке РФФИ в рамках научного проекта № 12-08-00296.

Рецензенты:

Кочегуров В.А., д.т.н., профессор, ФГАОУ ВПО «Национальный исследовательский Томский политехнический университет» Министерства образования и науки РФ, г. Томск;

Кориков А.М., д.т.н., профессор, заведующий кафедрой АСУ факультета систем управления, ФГБОУ ВПО «Томский государственный университет систем управления и радиоэлектроники», г. Томск.

Работа поступила в редакцию 23.09.2014.