Machine learning
NewTechAudit
109

Alpha Miner. Разбор построения модели для Process Mining

В закладки

Alpha-алгоритм — первый в технологии анализа процессов, который позволял находить так называемые Workflow nets из логов процессов. Алгоритм был разработан в 2013 году самим основателем методологии Process Mining профессором Will M.P. van der Aalst.

Что такое Workflow nets (далее WF)– это сеть, построенная на основе сетей Petri. Про них я рассказывать подробно не буду, о них можно почитать здесь (вставить ссылку на википедию). Для нас важно одно – WF на основе сетей Petri позволяет представлять и в дальнейшем анализировать рабочие процессы.

Отличительными чертами WF являются:

  1. Четкое начало. (Уникальное действие, котороетолькозапускает все цепочки действий)
  2. Четкий конец (Уникальное действие, котороетолькозаканчивает все цепочки действий)
  3. Каждое отдельное действие находится между п.1. и п.2.

Давайте посмотрим на пару примеров:

Данные схемы не являются WF. Почему? В первом случае у нас отсутствует начало и конец цепочки (они обозначаются кругом). Во втором случае действие d не имеет окончания.

Ниже я привел пример правильной WF сети – есть начало и конец, а все действия расположены между ними и завершены.

Немного прояснив, что такое WF, переходим к работе alpha алгоритма:

Для того, чтобы получить WF с использованием alpha алгоритма, нам потребуется навести порядок в нашем логе. Для этого мы определим следующие отношениями между переходами в логе событий (в дальнейшем они понадобятся для построения модели):

  • Прямая последовательность.
    Событие A > Событие B.
    В реальном логе событий это выглядело бы так:
  • Причинно-следственная связь.
    Событие A → Событие B.
    Означает, что в логе событий есть такие переходы

Но нет таких:

Следовательно на схеме мы ставим символ

  • Параллельные события.В логе встречаются оба перехода Событие A → Событие B и Событие B → Событие A.
  • Отсутствие последовательности.Событие A # Событие B и наоборот. Эти события не встречаются в логе.

Общий датасет из всех переходов называется множество L.

Давайте разберем небольшой пример. Ниже приведен лог, состоящий из трех случаев.

Напишем связи из нашего лога, которые используются в alpha алгоритме:

  • Заявка по телефону > Обработка заявки,
    Заявка по телефону > Отправка результата,
    Обработка заявки > Отправка результата,
    Обработка заявки > Завершение заявки,
    Отправка результата > Обработка заявки,
    Отправка результата > Завершение заявки,
    Заявка по почте > Отправка ответа по почте
  • Заявка по телефону → Обработка заявки,
    Заявка по телефону → Отправка результата,
    Обработка заявки → Завершение заявки,
    Отправка результата → Завершение заявки,
    Отправка результата→ Завершение заявки,
    Заявка по почте → Отправка ответа по почте
  • Обработка заявки || Отправка результата

На основании полученных отношений, рисуем WF.

Полученная модель охватывает все действия нашего лога и ее легко анализировать.

Ограничения работы alpha алгоритма

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

Ожидаемая модель будет выглядеть так:

Но alpha алгоритм выдаст нам совершенно другую картину:

В чем причина? Действие «Обработка заявки» не имеет начала и конца. В процессе генерации модели создается множество A ( где есть все начала) и множество B ( окончания процессов) . Так как при многократных повторениях, у нас пропадают данные множества, алгоритм не может их найти. Соответственно данное действие выпадает из общей модели.

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

Как можно решить данную проблему? Нужно максимально учитывать особенности той системы, которую вы анализируете. Если ваша система пишет в лог не только основные моменты, но и действия, которые генерируются автоматически ( например, в случаях рукописного ввода, система может каждые 5 секунд делать автосохранение и записывать это в лог), то есть смысл объединять эти действия в один элемент.

Лайфхаки IT, проверенные AI-решения для стандартных задач
{ "author_name": "NewTechAudit", "author_type": "editor", "tags": [], "comments": 0, "likes": 2, "favorites": 1, "is_advertisement": false, "subsite_label": "ml", "id": 117077, "is_wide": true, "is_ugc": false, "date": "Thu, 02 Apr 2020 10:28:15 +0300", "is_special": false }
0
Комментариев нет
Популярные
По порядку

Прямой эфир