Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

METHOD FOR CONSTRUCTING A HIERARCHICAL PREDICATE PROCESSING MODEL

Rudometkina M.N. 1 Spitsyn V.G. 1 Bolotova Y.A. 1
1 Federal Governmental Autonomous Educational Institution of Higher Education Tomsk Polytechnic University (National Research University)
We develop a method of constructing the predicate model flexible process. The general lack of all considered methods is they are based on the assumption of «planar» nature of the process. The process is represented by a graph reflecting the sequence of actions (an algorithm), that leads to the desired result. In this area, the analogy can be traced to the early stages of programming technologies, when attention was focused on algorithmization. Traditional methods of mining processes need to be improved in relation to the problem of constructing a model of a flexible process. An improved method should take into account an additional aspect of the process – the hierarchy of his actions, and the ability to effectively cut off the excess actions when configuring the process model. As a mathematical framework used machine finite predicates.
predicate
logical network
predicate algebra
graph
flexible process
the log process
process mining
1. Avramchuk V.S., Gerget O.M., Luneva E.E. Razrabotka komponenta vizualizacii biomedicinskih dannyh na osnove tehnologii OPENGL // Izvestija Volgogradskogo gosudarstvennogo tehnicheskogo universiteta. 2013. T. 17. no. 14 (117). рр. 28–31.
2. Repin V., Elifirov V. Processnyj podhod k upravleniju. Modelirovanie biznes-processov //M.: Standarty i kachestvo. 2008. рр. 196.
3. Rudometkina M.N. Predikatnaja model’ gibkogo processa. Mezhdunarodnyj zhurnal prikladnyh i fundamental’nyh issledovanij no. 10, chast’ 2, Rossijskoj Akademii Estestvoznanija, Moskva, 2014. Prinjata k pechati.
4. Rudometkina M.N., Spicyn V.G. Model’ logicheskoj seti s predikatnymi operacijami. Mezhdunarodnyj zhurnal prikladnyh i fundamental’nyh issledovanij no. 10, chast’ 2, Rossijskoj Akademii Estestvoznanija, Moskva, 2014. Prinjata k pechati.
5. Gottschalk F.,W.M.P. van der Aalst, and M.H. Jansen-Vullers. Merging Event-driven Process Chains // OTM 2008, Part I, CoopIS 2008, volume 5331 of Lecture Notes in Computer Science, , Berlin Heidelberg. Springer Verlag. 2008. рр. 418–426.
6. Rosa M. La, Dumas M., Uba R., Dijkman R. Business Process Model Merging: An Approach to Business Process Consolidation. ACM Transactions on Software Engineering and Methodology // no. 22(2), 2012.
7. Li C., Reichert M., Wombacher A. The MINADEPT Clustering Approach for Discovering Reference Process Models Out of Process Variants. International Journal of Cooperative Information Systems, no. 19(3-4):159–203, 2010.
8. Gerget O.M., Devjatyh D.V. Information System for Health State Diagnostics // CSIT’2013 2013. рр. 126–131.
9. Rudometkina M.N., Spitsyn V.G. Detection of processing model basic elements in intellectual analysis of flexible processes // IFOST, The 9th International Forum on Strategic Technology 2014.

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

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

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

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

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

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

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

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

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

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

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

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

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

rudomet01.wmf (1)

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

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

rudomet04.wmf

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

rudomet05.wmf (2)

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

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

rudomet07.wmf (3)

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

rudomet08.wmf (4)

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

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

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

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

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

rudomet09.wmf (5)

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

rudomet10.wmf (6)

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

rudomet11.wmf (7)

если rudomet12.wmf

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

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

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

rudomet13.wmf

rudomet14.wmf

rudomet15.wmf (8)

rudomet16.wmf

rudomet17.wmf

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

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

rudomet18.wmf (9)

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

rudomet19.wmf (10)

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

rudomet20.wmf (11)

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

rudomet21.wmf (12)

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

rudomet22.wmf (13)

что rudomet23.wmf

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

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

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

rudomet24.wmf (14)

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

rudomet25.wmf (15)

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

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

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

rudomet26.wmf (16)

Для нахождения указанной модели целесообразно отдельно выделить ветвление, которое во всех случаях в примере начинается с события s1, а также последовательности событий s2, s3, s3, s2, s4, s5, s3, s6, s4, s5, s7, s8, отражающие параллельное выполнение, простую последовательность и цикл соответственно. Рассматривая каждую из этих групп как единое целое, сворачиваем наш лог к набору простых последовательностей событий, каждое из которых отражается в модели в виде предиката:

rudomet27.wmf (17)

Далее определяется модель для каждой из последовательностей s2, s3, s3, s2, s4, s5, s4, s5, s3, s6, s4, s5, s7, s8. При этом для параллельного выполнения мы разделяем события s2 и s3, для цикла - выделяем отдельно повторяющиеся последовательности s4, s5, а также событие s6, которое предположительно соответствует проверке условия повторения.

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

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

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

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

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

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

rudomet30.wmf (18)

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

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

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

rudomet32.wmf (19)

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

rudomet33.wmf (20)

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

rudomet34.wmf (21)

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

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

rudomet35.wmf; (22)

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

rudomet36.wmf; (23)

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

rudomet37.wmf (24)

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

rudomet38.wmf (25)

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

rudomet39.wmf (26)

Заключение

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

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

Рецензенты:

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

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

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