Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,074

АЛГОРИТМ ФОРМИРОВАНИЯ ПРЕДИКАТНОЙ МОДЕЛИ ГИБКОГО МНОГОВАРИАНТНОГО ПРОЦЕССА НА ОСНОВЕ АНАЛИЗА ЕГО ЛОГ-ФАЙЛОВ

Рудометкина М.Н. 1
1 ФГАОУ ВПО «Национальный исследовательский Томский политехнический университет»
В статье рассматривается реализация задачи построения иерархической модели гибкого дискретного процесса преобразования ресурсов. Предложен алгоритм формирования предикатной модели гибкого многовариантного процесса на основе анализа его лог-файлов. Данный алгоритм детализует метод построения иерархической предикатной модели гибкого процесса. Предикаты формализуют взаимосвязь между действиями процесса. Поэтому представление модели процесса в виде иерархии действий позволяет сопоставить модель с дополнительными данными из лог-файла, в частности с иерархией исполнителей процесса. По результатам сопоставления выполняется усовершенствование модели. Представление последовательности действий процесса в виде иерархии облегчает конфигурирование модели. Настройка выполняется путем удаления избыточных для конкретного применения ветвей дерева процесса. Разработанный алгоритм последовательно выполняет импорт файла лога, выделение множества базовых элементов процесса на основе анализа лога (последовательность, выбор, цикл, параллельное выполнение), построение иерархии действий процесса из полученного множества базовых элементов, а также экспорт модели по уровням иерархии.
предикат
граф
гибкий процесс
лог процесса
process mining
1. Репин В., Елифиров В. Процессный подход к управлению. Моделирование бизнес-процессов. – М.: Стандарты и качество, 2008. – 196 с.
2. Pудoметкинa М.Н. Метод построения иерархической предикатной модели процесса // Фундаментальные исследования. – 2014. – № 9, Ч. 12.
3. Pудoметкинa М.Н. Предикатная модель гибкого процесса / Международный журнал прикладных и фундаментальных исследований. – 2014. – № 10, Ч. 2.
4. Gottschalk F., van der Aalst W.M.P., Jansen-Vullers M.H. Merging Event-driven Process Chains. OTM 2008, Part I, CoopIS 2008, volume 5331 of Lecture Notes in Computer Science. – Berlin Heidelberg, 2008. Springer Verlag. – Р. 418–426.
5. La Rosa M., Dumas M., Uba R., Dijkman R. Business Process Model Merging: An Approach to Business Process Consolidation. ACM // Transactions on Software Engineering and Methodology. – 2012. – № 22(2).
6. 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. – 2010. – № 19(3-4). – Р. 159–203.
7. Buijs J.C.A.M., van Dongen B.F., van der Aalst W.M.P. On the Role of Fitness, Precision, Generalization and Simplicity in Process Discovery. In Proceedings of Coop IS, LNCS. – Springer, 2012.
8. Rosemann M., W.M.P. van der Aalst. A Configurable Reference Modeling Language // Information Systems. – 2007. – № 32(1). – Р. 1–23.
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.

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

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

Анализ работ области построения моделей гибких процессов

Проведенный анализ работ [1, 4, 5, 6] в области построения моделей гибких процессов как традиционными методами, так и средствами process mining показал, что полная модель такого процесса может быть получена:

– путем реализации традиционного полного цикла разработки модели гибкого многовариантного процесса;

– на основе слияния моделей нескольких «жестких» процессов, которые реализуют идентичную функциональность, но различным способом;

– путем поэтапного дополнения исходной модели процесса новыми возможностями;

– на основе анализа логов, содержащих информацию о нескольких вариантах реализации процесса [9].

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

Автором предложен метод построения иерархической предикатной модели гибкого процесса [2], который при условии полноты лога обеспечивает построение полного адаптируемого описания процесса в форме иерархии предикатов, связывающих его базовые структурные элементы. Изложенное свидетельствует об актуальности реализации метода в виде соответствующего программного обеспечения и, следовательно, о необходимости разработки алгоритма построения иерархической модели гибкого процесса на основе анализа лог-файла.

Формулировка задачи

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

Исходными данными для разрабатываемого алгоритма подхода являются логи событий, отражающие последовательность выполнения действий при реализации процесса. На основе слияния и анализа логов выполняется построение полной многовариантной модели процесса [4].

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

Исходные данные: основные элементы лог-файлов

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

Файлы логов обычно содержат следующую информацию о выполнении процессов (доступа к информации, бухгалтерского учета и т.п.):

– код ситуации; каждая ситуация соответствует однократному выполнению процесса; последовательность действий с одним кодом ситуации представляет собой «след» или траекторию однократного выполнения процесса;

– код события; событие отражает факт выполнения одного из действий процесса;

– метка времени; данная метка фиксирует факт выполнения одного из действий процесса, для которого составлен лог;

– наименование действия процесса;

– ресурс, который используется для выполнения действия процесса.

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

Лог может быть представлен в текстовом формате, в виде таблицы, а также в xml – подобном формате OpenXES. В этом случае лог хранится в файле с расширением «xes».

Основные теги, обеспечивающие структуризацию лога: trace – траектория выполнения (следа) процесса; event – событие, отражающее выполнение действия процесса.

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

Рассмотрим процесс анализа лога. На первом шаге известны начальное и конечное состояние процесса, рис. 1.

pic_6.tif

Рис. 1. Начальное и конечное состояние процесса

Начинаем анализ с первого состояния процесса. Возможны два варианта продолжения процесса – развилка или последовательная цепочка действий. Развилка может быть пяти различных типов. После состояния x1 в логе идет развилка в состояния x2 и x3 со свойством эксклюзивного выбора. Обозначим действия из x1 в x2 и из x1 в x3 соответственно бинарными предикатами R1(x1, x2) и R2(x1, x3), а развилку – предикатной операцией

S1 = R1(x1, x2)⊕R2(x1, x3).

Непроанализированные части лога обозначим буквами А и В, (рис. 2, а).

Продолжаем анализ процесса. Из состояния x2 обнаруживается развилка в состояния x4 и x5 со свойством выбора (логическая операция OR). Из состояния x3 продолжается последовательная цепочка к действию x6.

Обозначим действия из x2 в x4, из x2 в x5 и из x3 в x6 соответственно бинарными предикатами

R3(x2, x4), R4(x2, x5) и R5(x3, x6),

а развилку – предикатной операцией

S2 = R1(x1, x2)?R2(x1, x3).

Непроанализированные части процесса обозначим буквами А, В, С (рис. 2, б).

pic_7.tifа pic_8.tif б

Рис. 2. Непроанализированные части

Проанализируем части процесса А, В и С (рис. 2, б). Из состояния x5 обнаруживается развилка в состояния x7 и x8 со свойством выбора (логическая операция OR). Из состояний x4 и x6 продолжаются последовательные цепочки к действиям x9 и x11 соответственно.

Обозначим действия из x4 в x9, из x5 в x7, из x5 в x8 и из x6 в x11 соответственно бинарными предикатами R6(x4, x9), R7(x5, x7), R8(x5, x8) и R9(x6, x11) а развилку – предикатной операцией

S3 = R7(x5, x7)∨R8(x5, x8).

Непроанализированные части процесса обозначим буквами А, В, С, D (рис. 3, а).

pic_9.tifа pic_10.tif б

Рис. 3. Непроанализированные части процесса

Проанализируем части процесса А, В, С, D (рис. 3, а). Из состояния x7 обнаруживается развилка в состояния x9 и x10 со свойством параллельного выполнения (логическая операция AND). Из состояния x11 обнаруживается развилка в состояния x13 и x15 со свойством цикла. Из состояния x9 продолжается последовательная цепочка к действию x12.

Обозначим действия из x7 в x9, из x7 в x10, из x8 в x11, из x11 в x13 и из x11 в x15 соответственно бинарными предикатами R10(x7, x9), R11(x7, x10), R12(x8, x11), R15(x11, x13) и R16(x11, x15). Развилку из состояния x7 обозначим предикатной операцией

S4 = R10(x7, x9)∧R11(x7, x10),

а развилку из состояния x11 обозначим

S5 = Ω(R15(x11, x13), R16(x11, x15), 3).

Непроанализированные части процесса обозначим буквами А, В, С, D (рис. 3, б).

Проанализируем части процесса А, В, С, D (рис. 3, б). Из состояний x12, x10, x13 и x15 продолжаются последовательные цепочки к действиям x14, x14, x15 и x16 соответственно.

Обозначим действия из x12 в x14, из x10 в x14, из x13 в x15 и из x15 в x16 соответственно бинарными предикатами R17(x12, x14), R14(x10, x14), R18(x13, x15) и R20(x15, x16).

Непроанализированную часть процесса обозначим буквой А (рис. 4).

pic_11.tif

Рис. 4. Непроанализированная часть процесса А

Проанализируем части процесса А (рис. 4). Из состояния x14 продолжается последовательная цепочка к действию конечному x16.

Обозначим действие из x14 в x16 бинарным предикатом R19(x14, x16). На этом анализ процесса завершен, получаем граф логической сети.

Алгоритм формирования предикатной модели

Описание основных функций, реализация которых необходима для построения предикатной модели процесса, приведено в таблице.

Описание функций

Функции

Полное описание

Импорт файла лога

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

Формирование набора базовых элементов процесса

Данные функции предназначены для выделения базовых элементов процесса на основе сравнительного анализа ситуаций (следов процесса). В разработанном алгоритме используются следующие базовые элементы процесса [8, 9]:

– последовательное выполнение действий процесса;

– одновременное (параллельное) выполнение действий;

– циклическое выполнение действий;

– выбор последующих действий

Построение иерархической модели процесса

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

Экспорт модели

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

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

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

Разработанный алгоритм в общем виде приведен на рис. 6. Его отличительная особенность – рекурсивное выполнение этапов построения иерархии процесса.

Отметим, что возможность внесения в модель дополнительных ветвей зависит от наличия различных вариаций лога. Отражение в модели нового лога означает возможное формирование новых ветвей процессного дерева.

pic_12.wmf

Рис. 5. Диаграмма вариантов использования

pic_13.tif

Рис. 6. Алгоритм формирования модели процесса

Заключение

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

Работа выполнялась по тематике госбюджетной НИР № 4.1316.2014 в рамках государственного задания «Наука».

Рецензенты:

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

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

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


Библиографическая ссылка

Рудометкина М.Н. АЛГОРИТМ ФОРМИРОВАНИЯ ПРЕДИКАТНОЙ МОДЕЛИ ГИБКОГО МНОГОВАРИАНТНОГО ПРОЦЕССА НА ОСНОВЕ АНАЛИЗА ЕГО ЛОГ-ФАЙЛОВ // Фундаментальные исследования. – 2014. – № 11-1. – С. 39-45;
URL: http://fundamental-research.ru/ru/article/view?id=35474 (дата обращения: 23.01.2020).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074