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



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

• провести интервью с сотрудниками;
  
• проанализировать доступные отчеты и документацию.
  

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

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

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

Впоследствии у наших заказчиков возникла потребность не только качественно определять текущее состояние процесса, но и прогнозировать его будущее.
Далее мы расскажем об апробации методов машинного обучения и пошагово опишем, как мы решали задачу предсказания длительности процесса закупки (на примере датасета BPI Challenge 2019) по набору известных событии? с использованием высокопроизводительной станции DGX Station, любезно предоставленной нам для проведения исследования компанией NVIDIA.

Применение машинного обучения для Process Mining

Для решения задачи мы строили baseline с использованием CatBoostRegressor, а затем разрабатывали решение с неи?роннои? сетью и эмбеддингами категориальных переменных.
Из-за наличия в исходных данных категориальных и вещественных признаков было принято решение использовать бустинг, который смог бы обрабатывать категориальные признаки без кодирования, а также решать задачу на дискретном и вещественном входе.

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

Описание данных

Мы решили использовать внешние данные, которые подходили бы нам по бизнес-области и обладали схожим набором признаков. Используемый датасет BPI Challenge 2019 включает 250 тыс. кеи?сов — это 1,5 млн событии?. Исходные данные описываются набором из 21 признака: 18 категориальных (есть индексовые признаки), два булевых и один вещественный. В качестве целевой переменной было выбрано время исполнения закупочного процесса, что соответствовало реальным потребностям бизнеса. Для детального описания признаков можно обратиться к описанию датасета.

Baseline

Прежде чем обучать модели, данные разделили на обучающую (train) и тестовую (test) выборки в соотношении 0,8/0,2. При этом разделение происходило не по событиям, а по кейсам.

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

• Время с прошлого события: считаем время, прошедшее между двумя событиями, с одним лишь нюансом: мы не хотим нулей между событиями. То есть, если два события идут друг за другом, но с одинаковым временным штампом, для последнего из них мы считаем время до события, идущего до него, но обязательно с отличным временным штампом.
  
• Exponential Moving Average на времени с прошлого события: EMA считаем для каждого кейса отдельно для того, чтобы зафиксировать тренд по временным промежуткам для разных кейсов.
  
• По традиции добавляем характеристики даты (месяц, день, день недели).
  

После обучения CatBoostRegressor на обучающей выборке мы получили следующий результат: MAE (Mean Absolute Error) = 17,5 дня (то есть значение предсказанной целевой переменной в среднем отличается от истинного значения на 17,5 дня). Этот результат был использован для проверки эффективности нейронной сети. 

Одна из важных деталей здесь — это разработка целевой переменной для baseline. 

Скажем, у нас есть кеи?с. Обозначим его c_i из множества C (множества всех кеи?сов в нашем датасете). Каждыи? кеи?с — это упорядоченная последовательность событии?, то есть c_i = (e_0, ..., e_ni ), где ni — длина i-го кеи?са. Для каждого события у нас есть временнои? штамп — точное время его начала. По этим временным штампам можно посчитать длительность кеи?са без последнего события. Однако присваивать такои? таргет каждому событию, то есть сделать соответствие ek ? ci, ek > ti (ti ? длительность i-го кеи?са), не очень хорошо, потому что, во-первых, в разных по длительности кеи?сах могут встречаться похожие события (типовые), а во-вторых, мы хотим предсказывать длительность кеи?са по некоторои? подпоследовательности (упорядоченнои? во времени) событии? (это мотивировано тем, что мы как бы не знаем целую последовательность событии?, то есть не знаем кеи?с до того, как он произошел, но хотим сделать оценку длительности целого кеи?са по некоторым известным (произошедшим) событиям из этого кеи?са).

Поэтому нужно разбить каждыи? кеи?с на подпоследовательности длины от единицы до длины кеи?са упорядоченных по времени событии? и каждои? такои? последовательности назначить целевую переменную, равную длительности кеи?са, из которого эти подпоследовательности получаются, то есть соответствия ci ? C, ci > {sub_cj}ni (ni, как и раньше, длина i-го кеи?са), j=1 и len(sub_cj ) = j.

Таким образом, каждыи? кеи?с мы разбиваем на подпоследовательности и каждои? такои? подпоследовательности присваиваем длительность всего кеи?са.

Подробнее о подпоследовательностях

Мы собираемся использовать бустинг, который требователен к размеру входных данных. Так, сейчас у нас есть X = {{sub_c^k_i } ⁿⁱ _k=1}_{t=1 N}, где sub_c _ik — k-ая подпоследовательность i-го кейса, t_i — длина i-го кейса, N — количество кейсов. То есть размерность [?^N _t=1 n_i, sc, 17], sc —переменная величина, равная длине подпоследовательности соответствующего кейса.

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

После усреднения sc по размерности получаем следующую размерность: [?^N _t=1 n_i, 17] (точнее можно посмотреть в ноутбуке).

Построение модели

На основании кейсов делим train на еще один train и валидационную выборку, берем CatBoostRegressor c дефолтными параметрами, передаем ему обучающую выборку, валидируемся на валидационной выборке, берем лучшую итерацию, используем MAE как валидационную метрику. Получаем на тесте следующее (отдельно готовим тест по тому же pipeline’у, по которому строили train, все признаки основаны на данных, которые есть в тесте, то есть у нас нет признаков, которые ориентированы на целевую переменную; единственный нюанс: если в категориальных признаках в тесте не встречается значение, которое мы видели в train, то считаем частоту этого значения на тесте и обновляем словарь для кодирования).

Результаты baseline

• Iterations: 500.
• Learning rate: 0.1.
• Параметры обучения:
• Время на обучение: меньше 2 минут.
• Железо: Tesla k80 (из colab)

.
Результаты:

• Test MAE: 17,5 дня.
• Средняя продолжительность кеи?са в тесте: 66,3 дня.

Нейронная сеть

Setup

Для обучения нейронной сети данные были усовершенствованы: были построены эмбеддинги для категориальных переменных, а также скорректировано распределение целевой переменной. Далее нейронная сеть была обучена на NVIDIA Tesla K80 (Google Colab) и на NVIDIA DGX Station.

Были получены следующие результаты:

• Время на обучение на NVIDIA K80 (Google Colab): 20 минут.
  
• Время на обучение на NVIDIA DGX Station: 8 минут.
  

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

Препроцессинг

Новые признаки

• EMA на стоимости события: хотим уловить тренд по стоимости активностеи? для каждого кеи?са.
  

• Type of flaw: в описании датасета можно наи?ти информацию про четыре типа некоторои? описательнои? статистики закупки (события) — эти типы разбиты на значения двух переменных в изначальном датасете. Мы это просто агрегируем обратно (если посмотреть описание датасета, будет понятно, о чем здесь речь).
  

Категориальные признаки

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

Эмбеддинги для категориальных переменных

Определяем размерность эмбеддингов для каждой категориальнои? переменнои?:

• Смотрим, сколько уникальных значении? в категориальнои? переменнои?: выбираем минимум из некоторои? константы, которая обозначает минимум по размерности эмбеддингов для категориальных фичеи? с высокои? кардинальностью, и количества уникальных значении?, поделенного пополам. Другими словами: MUi  = min(CAT_EMBEDDING_DIM; (len(uniquei) + 1) // 2), где CAT_EMBEDDING_DIM — константа, uniquei — уникальные значения i-ой категориальной фичи.
  
• Не хотим, чтобы размерность эмбеддингов была меньше 3, поэтому в итоге выбираем размерность для i-и? категориальнои? фичи как max(3;MUi)+1, добавляем 1, потому что можем увидеть в тестовых данных значение, которое не видели на train, то есть это как бы unk-токен.
  

Корректируем распределение таргета на train выборке

Изначальное распределение получилось очень сильно смещенным влево за счет выбросов (кеи?сов, которые длились 250 тыс. днеи?) и большого количества коротких кеи?сов, поэтому считаем 0,05 и 0,95 перцентили и оставляем данные из train с таргетом между этими порогами.
После этого у нас все равно есть кеи?сы, которые длятся около одного и около 100 днеи?, то есть целевая переменная проходит несколько порядков. Поэтому предположение о постоянстве дисперсии в распределении целевои? переменнои? вокруг решающего алгоритма вряд ли выполняется, то есть распределение целевой переменной близко к нормальному, но дисперсия не постоянная ввиду того, что целевая переменная может быть как меньше 1, так и больше 100. Поэтому, чтобы хоть как-то нивелировать этот эффект, отнормируем данные.

Результат представлен на графике ниже (черная линия — нормальное распределение).



Потом делим по кеи?сам наши данные на train и валидацию. Здесь есть тоже очевидныи? нюанс: мы нормируем таргет со средним и отклонением, посчитанными по всем данным, а потом уже делим на train и валидацию, то есть здесь получается как бы лик в train, но, поскольку мы здесь решаем вспомогательную задачу, этот лик кажется не критичным.

Строим признаки

Идея

• Мы берем только категориальные признаки из нашего train, кодированные натуральными числами.
  
• Берем не подстроки из кеи?сов, а просто события, то есть одна строка в наших данных для эмбеддингов — это одно событие, характеризующееся закодированными категориальными признаками.
  
• Целевая переменная: каждому событию присваиваем целевую переменную, равную длительности кеи?са, из которого мы взяли это событие, исходя из того, что мы хотим выучить такие эмбеддинги категориальных переменных, которые хорошо улавливали бы соответствие между набором категориальных переменных в подпоследовательности событии? в кеи?се и длительностью этого кеи?са. Из-за того, что большинство категориальных переменных принимает одинаковое значение внутри кеи?са, каждое событие, в принципе, не сильно отличается от кеи?са (так как отсутствуют вещественные признаки), тем более для обучения эмбеддингов (а вообще пока просто не понятно, как по-другому дизаи?нить целевую переменную).
  
• Каждую категориальную переменную в строке заменяем на соответствующии? эмбеддинг и конкатенируем эти эмбеддинги в одну строку.
  
• Целевая переменная на такую строку есть, поэтому подаем это в 8-слои?ныи? персептрон с elu в качестве активации?, считаем ошибку (мы подкорректировали таргет, поэтому можем считать, что мы находим хорошие веса, минимизируя L2-функционал) и делаем коррекцию для весов.
  
• Матрицы, из которых мы берем эмбеддинги для категориальных переменных на каждом шаге, — обучаемые переменные в графе, поэтому градиенты считаются и на них, и так они учатся.
  
• Summary: просто берем эмбеддинг (слои? для каждои? категориальнои? переменнои?) и прогоняем это через персептрон с таргетом — длительностью кеи?са.
  

Архитектура графа вычислений эмбеддингов

Batch size = 1000
• Learning rate = 3e-04.
• Количество эпох = 15.
• Железо: Tesla k80 (colab) + Nvidia DGX Station.
• Время (colab) – 50 минут.
• Время (Nvidia DGX Station) — 18 минут.

Архитектура модели

Подготовка данных

Теперь у нас есть эмбеддинги для категориальных переменных (здесь есть нюанс: мы по-честному брали уникальные значения категориальных переменных на нашем train (не на том, которыи? мы выделили для обучения эмбеддингов, а на том, которыи? мы в самом начале выделили для обучения), поэтому есть шанс, что на тестовых данных встретится значение категориальных переменных, которые мы не видели на train, то есть у нас нет обученного эмбеддинга для этого значения.

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

В том, как обучать этот вектор, кроется направление для улучшения модели. Идея состоит в том, что очень редкие значения в train можно кодировать этим вектором, потому что если мы увидим новое значение уже только в тесте, которыи? условно составляет 20% от всеи? исходнои? выборки, то это значение является редким и, наверное, ведет себя так же, как и редкие значения в train.

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

Осуществляем группировку событии? в подпоследовательности (как делали ранее). Целевая переменная для подпоследовательности — длительность кеи?са, из которого была получена подпоследовательность. Добавляем в вектор подпоследовательности количество событии? и сумму стоимостеи? событии? в этои? подпоследовательности.

Теперь у нас есть матрица фиксированного размера — можно подавать в модель (перед этим нормируем матрицу).

Метод распараллеливания

• Делаем по башне на каждую gpu.
  
• На каждом шаге делим параметры между башнями.
  
• На каждом шаге делим батч данных между башнями.
  
• На каждои? башне считаем логиты, ошибку и градиенты.
  
• Агрегируем градиенты с башен на сервере параметров (по факту это может быть просто функция, которая усредняет градиенты по башням на каждои? переменнои? и возвращает эти усредненные градиенты для шага обновления параметров).
  
• Делаем шаг обновления параметров по агрегированным градиентам с сервера.
  
• Применяем подобную схему во всех случаях, где обучаем что-то нейросетевое (эмбеддинги для категориальных переменных, эмбеддинги word2vec-style, сама модель и так далее).
  

Проблемы

• К градиентному спуску добавляется еще стохастики за счет распиливания батча (сначала) и агрегирования (усреднения) градиентов (потом).
  
• Очевидныи? нюанс: сервер параметров — это точка синхронизации, то есть если одна gpu тормозит с вычислением ее градиентов, то остальные будут простаивать, пока тормозящая gpu не справится со своими градиентами.
  

Обучение

• Архитектура: 7-слои?ныи? персептрон с активациями elu.
  
• Таргет по распределению такои? же, как при обучении эмбеддингов.
  
• Batch size = 1000.
  
• Learning rate = 3e-04.
  
• Количество эпох = 15.
  
• Железо: Tesla k80 (colab) + Nvidia DGX Station.
  
• Время (colab) = 20 минут.
  
• Время (Nvidia DGX Station) = 8 минут.
  

Кусочек графа модели



Потребление ресурсов и распараллеливание

Обучение нейронных сетей на CPU занимает приблизительно в четыре раза больше времени, чем на NVIDIA DGX Station. В данном случае разница кажется незначительной — восемь минут на NVIDIA DGX Station и 32 минуты на CPU. Однако это небольшая модель с маленьким количеством данных. При реализации реальных проектов, где будет в несколько раз больше кейсов и событий, обучение на CPU будет занимать минимум неделю. В таком случае использование NVIDIA DGX Station уменьшит время обучения до двух дней, что сильно увеличит эффективность работы. 

Также было выявлено, что скорость процесса обучения сильно зависит от количества используемых GPU, что показывает преимущество NVIDIA DGX Station.

Кроме того, это подтверждается проведенными ранее экспериментами на CPU и GPU NVIDIA DGX Station с использованием исходного набора данных без какой-либо предварительной обработки:

• Время на обучение на CPU: 6 минут 18 секунд.
  
• Время на обучение на GPU: 34 секунды.
  

Визуализация загрузки GPU:



Визуализация загрузки CPU:

Результаты нейросети

• Test MAE = 10 днеи?.
  
• Средняя продолжительность кеи?са на тесте = 67 днеи?.
  
• Inference time = 20 секунд.
  

Выводы

• Мы реализовали пилот для оценки методов машинного обучения в контексте задач Process Mining.
  
• Апробировали и расширили перечень наших инструментов, которыми будем решать задачи, важные для бизнеса.
  
• Одним из интересных результатов стало написание собственной реализации параллельных вычислений на 4 картах Тesla v100, которыми укомплектована DGX station: использование нескольких gpu ускоряет обучение почти в линию от количества gpu (код распараллелен).
  
• Переход на полностью непрерывныи? вход и использование нейросети позволил снять с baseline’a неделю.
  
• Время увеличивается с нескольких минут до полутора часов (обучение финальнои? архитектуры и эмбеддингов, но эмбеддинги можно использовать предобученные, поэтому время сокращается до 20 минут).
  

Описанные эксперименты показывают, что в области Process mining можно успешно применять алгоритмы машинного и глубокого обучения. Кроме этого, было выявлено, что скорость процесса обучения сильно зависит от количества используемых GPU,  что показывает преимущество NVIDIA DGX Station.

Что и как можно улучшить

Word2vec-style эмбеддинги для событии?

Когда мы делали нашу модель, включая эмбеддинги для категориальных переменных, мы не учитывали порядок следования событии? друг относительно друга, то есть своеобразную семантику событии? внутри кеи?сов. Чтобы извлечь что-то полезное из порядка событии? внутри кеи?сов, нужно обучить эмбеддинги для этих событии?.

Идея:

• Берем одну категориальную фичу и одну вещественную, делим вещественную на бакеты, тогда каждая транзакция будет характеризоваться значением категориальнои? переменнои? и бакетом, в которыи? попадает значение вещественнои? переменнои?. Объединяем эти два значения, получаем как бы аналог слова для события.
  
• Кеи?с рассматриваем как предложение (набор слов в предложении соответствует набору событий в кейсе).
  
• Выбрать категориальныи? признак и посчитать бакеты нужно так, чтобы мощность получившегося словаря была намного меньше количества всех событии? во всех кеи?сах, иначе может получиться так, что почти все предложения состоят из уникальных слов и здесь будет мало информации.
  
• Когда получим корпус предложении?, сформируем датасет для обучения Skipgram или CBOW и обучим эмбеддинги.
  
• Когда обучим эмбединги, добавляем их к другим признакам транзакции?, усредняем их по подпоследовательности вместе с остальными и так подаем в модель.
  

Что получилось:

• Использовали архитектуру Skipgram.
  
• Размер окна — 5.
  

• Batch size = 1000.
  
• Learning rate = 3e-04.
  
• Количество эпох = 10.
  
• Железо: Tesla k80 (colab) + Nvidia DGX Station.
  
• Время (colab) — 20 минут.
  
• Время (Nvidia DGX Station) — 8 минут.
  
• Test MAE вместе с семантическими фичами: 10 днеи?. 
  

Граф:



Использование фичеи? из эмбеддингов дает прибавку в пару десятых дня.

В итоге:

• Эмбеддинги получились, конечно, недообученные, потому что обучались мало.
  
• Фичеи? из категориальных эмбедингов — около 290, а фичеи? из семантических эмбеддингов — 20 (делать больше не имеет смысла, потому что размер словаря небольшои?), поэтому влияние этих семантических фичеи? может быть снивелированно из-за дисбаланса в пропорции фичеи?.
  
• Семантику между событиями нужно как-то добавлять в обучающую выборку, ведь из-за того, что последовательности событии? (кеи?сы) упорядоченные, порядок имеет значение, и из этого можно извлекать информацию.
  
• Можно использовать более изощренные архитектуры для эмбеддингов.
  
• Если решить проблему с дисбалансом и придумать, как лучше добавлять фичи из семантических эмбеддингов, может получиться здорово — это направление для улучшения модели.