граф майнинг что это
Process Mining без PM4PY
Построить граф по логам процесса очень просто. В распоряжении аналитиков в настоящее время достаточное многообразие профессиональных разработок, таких как Celonis, Disco, PM4PY, ProM и т.д., призванных облегчить исследование процессов. Намного сложнее найти отклонения на графах, сделать верные выводы по ним.
Что делать, если некоторые профессиональные разработки, зарекомендовавшие себя и представляющие особый интерес не доступны по тем или иным причинам, или вам хочется больше свободы в расчетах при работе с графами? Насколько сложно самим написать майнер и реализовать некоторые необходимые возможности для работы с графами? Сделаем это на практике с помощью стандартных библиотек Python, реализуем расчеты и дадим с их помощью ответы на детальные вопросы, которые могли бы заинтересовать владельцев процесса.
Сразу хочется оговориться, что решение, приведенное в статье, не является промышленной реализацией. Это некоторая попытка начать работать с логами самостоятельно с помощью простого кода, который понятно работает, а значит, позволяет легко его адаптировать. Это решение не стоит использовать на больших данных, для этого требуется существенная его доработка, например, с применением векторных вычислений или путем изменения подхода к сбору и агрегации информации о событиях.
Перед построением графа, необходимо выполнить расчеты. Собственно расчет графа и будет тем самым майнером, о котором говорилось ранее. Для выполнения расчета необходимо собрать знания о событиях — вершинах графа и связях между ними и записать их, например в справочники. Заполняются справочники с помощью процедуры расчета calc (код на github). Заполненные справочники передаются в качестве параметров процедуре отрисовки графов draw (см. код по ссылке выше). Эта процедура форматирует данные, в представленный ниже вид:
и передает его для отрисовки графическому движку Graphviz.
Приступим к построению и исследованию графов с помощью реализованного майнера. Будем повторять процедуры чтения и сортировки данных, расчета и отрисовки графов, как в приведенных ниже примерах. Для примеров взяты логи событий по международным декларациям из соревнования BPIC2020. Ссылка на соревнование.
Выполним расчет графа.
Выполним отрисовку графа.
После выполнения процедур получим граф процесса:
Так как полученный граф не читаем, упростим его.
Есть несколько подходов к улучшению читаемости или упрощению графа:
Создадим словарь объединения событий:
Выполним группировку событий и отрисуем граф процесса еще раз.
После группировки событий по схожести названия читаемость графа улучшилась. Попробуем найти ответы на вопросы. Ссылка на список вопросов. Например, скольким декларациям не предшествовало предодобренное разрешение?
Для ответа на поставленный вопрос отфильтруем граф по интересующим событиям и отрисуем граф процесса еще раз.
С помощью полученного графа мы легко сможем дать ответ на поставленный вопрос – 116 и 312 декларациям не предшествовало предодобренное разрешение.
Можно дополнительно “провалиться” (отфильтровать по ‘case:concept:name’, участвующих в нужной связи) за связи 116 и 312 и убедиться, что на графах будут отсутствовать события, связанные с разрешениями.
“Провалимся” за связь 116:
“Провалимся” за связь 312:
Так как на полученных графах полностью отсутствуют события, связанные с разрешениями, корректность ответов 116 и 312 подтверждается.
Как видим, написать майнер и реализовать необходимые возможности для работы с графами не сложная задача, с которой успешно справились встроенные функции Python и Graphviz в качестве графического движка.
Простой Graph Mining на PySpark
В практике внутреннего аудита встречаются задачи, в которых необходимо выявить сомнительные операции по перечислению денежных средств между счетами. В данной статье поэтапно рассмотрим, как происходит оборот средств на синтетических данных.
Применение Spark для анализа данных подразумевает большой объем данных, но для наглядности будем использовать небольшой набор данных, который состоит из 4 столбцов и 712 строк. Полный код и вспомогательные материалы можно найти на github странице.
Анализ данных будем проводить в два этапа, а именно, получение статистик и визуализация. В качестве статистик извлечем временной интервал (медианное время между транзакциями для каждого отправителя), а также частота и сумма между отправителем и получателем перевода. Визуализацию будем осуществлять с помощью graphviz, т.к. на данный момент для PySpark нет полноценного инструмента (opensource) для визуализации графов.
В первую очередь запустим спарк сессию и импортируем необходимые модули:
Далее загрузим данные для анализа. Для корректной загрузки опишем схему данных с помощью модуля types, в котором с помощью метода StructType укажем структуру полей (имя столбца, тип данных в столбце):
Загружаем данные с помощью модуля spark.read.csv, в котором указываем имя файла, схему и вид разделителя столбцов. В данном случае данные будут представлены в виде объекта DataFrame:
Для работы со столбцами используется модуль
в котором реализованы различные методы для преобразования данных. С помощью метода to_timestamp преобразуем строковый столбец ‘Date’ для корректного представления временной метки:
Для корректного парсинга временной метки необходимо указывать параметр ‘format’, в котором указывается последовательность даты и времени, а также разделители между ними. Преобразование осуществляется с помощью метода withColumn объекта DataFrame, который первым параметром принимает имя для преобразованного столбца. В данном примере указываем идентичное имя, таким образом, перезаписывается существующий столбец ‘Date’, иначе, создается новый столбец, с преобразованными данными. Вторым параметром метода withColumn является выражение, т.е. действие над столбцом, в данном примере это to_timestamp. В результате получаем таблицу следующего вида:
Приступим к подсчету статистик. Первым делом необходимо найти разность времени между транзакциями для каждой пары отправитель-получатель. Для этого создадим новый столбец даты со сдвигом на одну временную метку вниз. Данную операцию необходимо проводить отдельно для каждого отправителя – получателя, в этом нам поможет метод Window:
Null значения в столбце «prev_time» говорят о том, что данная транзакция для пары отправитель-получатель является первой или единственной. Далее найдем разность между столбцами «Date» и «prev_time»:
Выражение ddiff_expr находит разность между двумя датами в днях. Выражение w_o_expr заменяет null значения на 0. Осталось посчитать необходимую статистику (минимальное, среднее, медианное или максимальное время) между переводами для каждой пары отправитель-получатель. Можно воспользоваться готовым выражением
Но для расчета медианного значения необходимо написать выражение в виде sql-запроса:
В методе expr вызываем ‘percentile_approx’ запрос, который рассчитывает заданный перцентиль, в нашем случае 0.5, что соответствует медиане. Таким образом, получаем таблицу med_val с медианным временем между переводами для каждой пары отправитель-получатель, где 0 говорит о том, что медианное время менее 1 дня:
Далее рассчитаем количество и сумму переводов для каждой пары отправитель-получатель:
Также рассчитаем процент суммы перевода получателю от общей суммы, которую отправитель перевел за всю историю данных:
Код, описанный выше, реализован в модуле. Для предобработки данных нужно лишь вызвать класс Graph_miner:
В методе указываем DataFrame, в котором уже преобразовали столбец с датой, а также имена столбцов с отправителем, получателем, суммой перевода и датой.
получим следующий результат:
Осталось отобразить полученный результат. Также в модуле реализован класс Painter, с помощью которого отобразим наши данные:
Результатом выполнения будет pdf-файл, в котором отображены все обработанные данные. Далее можно детализировать выборку и убрать шумовые данные. Например, убрать те вершины, которые имеют только одного отправителя, сделать это можно с помощью параметра r_count_tresh в методе filtering_df:
Картина стала проще. Далее отфильтруем те ребра, в которых общая сумма переводов меньше 3000:
В результирующем графе остались наиболее весомые ребра, которые можно рассмотреть детальнее. Информация на ребрах приобрела читабельный вид, рассмотрим подробнее. Для примера возьмем ребро
Граф является ориентированным. В данном случае отправитель — account_155, получатель — account_7. Всего было осуществлено 5 переводов (f-5). Медианное время между переводами 3 дня (d-3). Общая сумма переводов за 5 раз составляет 11700 рублей (s-11700). 11700 составляет 18.28 % от общей суммы, которую отправил account_155 всем получателям (p-18.28).
Напоследок отрисуем отдельный связный граф, в который входит конкретная вершина, например account_96:
В отдельный файл сохранился граф, в котором все вершины имеют связь с вершиной account_96.
Таким образом, провели анализ данных на предмет выявления закономерностей движения средств между счетами. Полный пример с кодом можно найти в тетрадке.
Применение технологии graph mining в аудите банковских транзакций
Визуализация с помощью графа может отобразить значительно больше информации чем простая таблица. Одной из библиотек для построения графов в языке программирования Python является networkx.
Библиотека Networkx представляет концепцию сетевых графов, которые показывают взаимосвязи между набором различных объектов. Применение технологии графов позволяет быстро построить и визуализировать набор данных, хранящихся в табличном представлении через небольшое количество строк кода.
Чтобы определить цепочки транзакций между отправителем и получателем были построены графы, состоящие из узлов и ребер. В качестве узлов, в нашем случае, были рассмотрены номера клиентов, а ребрами служили транзакции. Для начала была проведена систематизация данных так, чтобы в столбцах таблицы содержалась только необходимая информация для дальнейшего исследования.
Процесс создания графа состоял из нескольких этапов:
Построенный граф получил следующий вид:
Для определения различных категорий клиентов, были предложены цветовые обозначения. С этой целью был создан массив для записи значений цвета, а затем использован в функции nx.draw.
Граф с измененными цветами вершин выглядит следующим образом:
Рассмотренный пример позволил, при помощи инструмента сетевых графов, выяснить процессы взаимодействия между клиентами банка. Простым набором нескольких строк кода мы смогли отобразить таблицу с банковскими транзакциями между клиентами.
Применение инструментов библиотеки network, позволило ускорить процесс определения взаимодействий клиентов, а графическая визуализация помогла аудитору выяснить участников транзакций — получателей и отправителей денежных средств.
GRAPH MINING для нематематиков
Всем привет! Сначала хотел назвать статью «Graph mining в 1 строчку кода», но это настолько неправдоподобно, что хочется дописать «без регистрации и СМС». Этого я делать, конечно же, не буду, поэтому решил немного переиначить смысл статьи, а заодно затронуть алгоритмы такого пугающего на первый взгляд слова как «графы». Итак, в настоящей статье хочу поделиться инструментом, помогающим выявлять связи между проверяемыми сущностями, но расскажу про него не с точки зрения графового анализа данных, а с точки зрения алгоритма действия и его реализации на Python без использования специализированных библиотек. Согласитесь, реализовывать алгоритмы самостоятельно, пусть даже несложные – полезная практика, и порой для глубокого понимания решения задачи недостаточно использовать питоновский import something и брать готовый метод – куда полезнее понимать на уровне кода, как это работает. Об этом и поговорим ниже. Сразу отмечу, что упора на код не делаю, здесь мы ставим задачу понимания сути решения. Поэтому там, где код неоптимален, скорее всего это сделано в угоду пониманию происходящего. Тем не менее, предложения по оптимизации приветствуются – нет предела совершенству. Также хочу остановиться на упомянутом выше слове «сущности» — я не нашел всеобъемлющего слова, куда бы попали связи между клиентами, организациями, сетевыми устройствами, ну и так далее.
Итак, дано: датасет операций между физическими лицами (ФЛ), выглядит так:
Фиолетовым цветом выделил пример связи, которую мы хотим выявить.
Задача: установить связи между ФЛ, то есть построить цепочки взаимодействия типа: ФЛ1 перечислял ФЛ2, ФЛ2 перечислял ФЛ3, ФЛ3 перечислял ФЛ4, и так далее. То есть на выходе надо получить такую картину:
Поясняю: здесь те же наши клиенты, что и на скрине исходных данных, но выстроенные в цепочку связей, то есть между Людмилой и Натальей был совершен платеж, в свою очередь Наталья финансово хоть раз была связана с Яной, а Яна переводила Светлане.
В качестве инструментов возьму классический Python и его модуль Pandas. Да, в блоке импорта у меня будет одна строчка: import pandas as pd. Перейдем непосредственно к коду:
Считаем данные и посмотрим на них:
Нам из пула данных нужны только 2 столбца, причем в полученном датасете из двух столбцов не должно быть одинаковых строк:
Приступаем к написанию алгоритма. Итак, в моей реализации это выглядит так: мы берем исходный датафрейм и циклично добавляем к нему самого себя, но по определенной связке: каждый раз ищем в атрибуте client_a_XX тех, кто есть в атрибуте client_b_XX, где ХХ – номер (итератор) цикла. Повторение – мать учения, поэтому на примере первой картинки, пока очищенной от лишних связей:
Мы нашли связь Людмила + Наталья, дальше мы ищем Наталью в столбце с Людмилой: вуаля – она нашлась в связке Наталья + Яна, дальше ищем и находим Яну. Ок, возвращаемся к коду. Для того чтобы данные соединять с этими же данными – создадим 2 одинаковых пула: исходный, на который будем накручивать его копии, и саму неизменяемую копию, на каждой итерации которую будем соединять с постоянно растущим исходным датафреймом.
Итак, вот создание копии:
Дальше создадим несколько вспомогательных переменных.
Первая – names_list — список названий столбцов. Его конечно можно получить, например, с помощью
Но нам нужны и будущие названия атрибутов, которые еще не существуют. Поэтому names_list у нас выглядит так:
То есть для каждой пары client_a / client_b создаем их «дочерние» client_a_1 / client_b_1, client_a_2 / client_b_2 и тд.
Здесь, во-первых, для примера умышленно ограничимся 3 итерациями, а во-вторых, создание такого списка с названиями атрибутов легко автоматизируется, код приводить не буду.
На основе первой вспомогательной переменной создадим еще одну, она понадобится для условия выборки данных в дальнейшем:
Третья вспомогательная переменная – i:
Это отправная точка для переходов между атрибутами, то есть:
И это нам позволит перемещаться между атрибутами на каждой итерации. Другими словами, i – это значение «индекса», меняя которое будем задавать нужные в конкретной итерации цикла атрибуты. Согласен, не объяснил, но дальше станет яснее.
Собственно, сама обработка и построение связей реализуется так:
Что мы здесь делаем:
Создаем цикл из 2 итераций, как говорили ранее (range(1,3)). Здесь можно позволить задавать число итераций автоматически, то есть что-то типа «пока последний атрибут датафрейма merged_df непустой» — через конструкцию while;
Соединяем исходный датафрейм (merged_df) с копией исходного (df) таким образом, что:
Где красной стрелкой выделена связь, по которой происходит соединение фреймов данных. Обратите внимание, что в качестве ключей для связи у меня указаны не константы, а значения, которые меняются в зависимости от итерации цикла (это я про left_on и right_on).
То есть Людмила переводила Наталье, Наталья переводила Людмиле, а Людмила снова Наталье. И это при том, что связки у нас уникальные, а значит ошибочно будет предполагать, что это 3 реальных перевода. Избавляемся от этого изъяна. Логика следующая – на каждой итерации присоединения поля, которые не являются ключами в объединении, не должны быть равны. То есть (простите за мой SQL):
На 1 итерации: client_b_1 not in (‘client_a’)
На 2 итерации: client_b_2 not in (‘client_a’, ‘client_a_1’)
На 3 итерации: client_b_3 not in (‘client_a’, ‘client_a_1’, ‘client_a_2’)
На 3 итерации: client_b_4 not in (‘client_a’, ‘client_a_1’, ‘client_a_2’, ‘client_a_3’)
На первый взгляд кажется, что эти условия легко поддаются автоматизации на каждой итерации. Да – поддаются, нет – не легко. Посмотрите на предыдущую картинку, но с указанием индексов атрибутов:
А теперь попробуем по ним пройтись. Для начала просто переберем значения нашего списка names_list:
Хорошо, теперь переберем индексы нашего names_list:
Ок, теперь переберем индексы списка, но вернем значения: [names_list[x] for x in range(8)]
Неплохо. Возвращаемся к требуемому условию – нам надо получить такой динамический список, который на каждой следующей итерации добавлял один атрибут в условие. Что-то типа:
for i in range(0, len(names_list)+1): print(i, names_list[:i])
Но возвращать не все значения, а согласно sql-подобному условию выше, то есть:
Здесь я убрал лишние итерации, красным и синим прямоугольником выделил атрибуты, участвующие в условии на каждой итерации. То есть значение из красного не должно равняться значениям в синих. Также здесь можно сделать вывод, что на каждой итерации нас интересуют те атрибуты, индексы которых делятся нацело на 2. Для понимания сути ниже я привел вывод результата в соответствии с sql-подобным условием:
Как раз то что нам надо!
И последняя строчка цикла i = i + 1. Это сделано для динамической адресации к атрибутам ячейки в рамках цикла. То есть, на примере куска кода:
На первой итерации цикла при i = 2 имеем (внимание, итерация по индексам списка — с нуля):
merged_df[[‘client_a’, ‘client_b_1’, ‘client_b_2’, ‘client_b_3’]]
Наконец, алгоритм поиска связей реализован. Дальше можно выгружать его, допустим в Excel, и накручивать дополнительные другие атрибуты, требуемые для анализа. Дополнительно отмечу, что данный подход (получение графа в виде таблицы, а не его визуализация) многократно снижает время обработки исходного датасета, а в некоторых случаях таблица – чуть ли не единственный выход для, например, анализа такого графа:
Graph mining для нематематиков
Всем привет! Сначала хотел назвать статью «Graph mining в 1 строчку кода», но это настолько неправдоподобно, что хочется дописать «без регистрации и СМС». Этого я делать, конечно же, не буду, поэтому решил немного переиначить смысл статьи, а заодно затронуть алгоритмы такого пугающего на первый взгляд слова как «графы». Итак, в настоящей статье хочу поделиться инструментом, помогающим выявлять связи между проверяемыми сущностями, но расскажу про него не с точки зрения графового анализа данных, а с точки зрения алгоритма действия и его реализации на Python без использования специализированных библиотек. Согласитесь, реализовывать алгоритмы самостоятельно, пусть даже несложные – полезная практика, и порой для глубокого понимания решения задачи недостаточно использовать питоновский import something и брать готовый метод – куда полезнее понимать на уровне кода, как это работает. Об этом и поговорим ниже. Сразу отмечу, что упора на код не делаю, здесь мы ставим задачу понимания сути решения. Поэтому там, где код неоптимален, скорее всего это сделано в угоду пониманию происходящего. Тем не менее, предложения по оптимизации приветствуются – нет предела совершенству. Также хочу остановиться на упомянутом выше слове «сущности» — я не нашел всеобъемлющего слова, куда бы попали связи между клиентами, организациями, сетевыми устройствами, ну и так далее.
Итак, дано: датасет операций между физическими лицами (ФЛ), выглядит так:
Фиолетовым цветом выделил пример связи, которую мы хотим выявить.
Задача: установить связи между ФЛ, то есть построить цепочки взаимодействия типа: ФЛ1 перечислял ФЛ2, ФЛ2 перечислял ФЛ3, ФЛ3 перечислял ФЛ4, и так далее. То есть на выходе надо получить такую картину:
Поясняю: здесь те же наши клиенты, что и на скрине исходных данных, но выстроенные в цепочку связей, то есть между Людмилой и Натальей был совершен платеж, в свою очередь Наталья финансово хоть раз была связана с Яной, а Яна переводила Светлане.
В качестве инструментов возьму классический Python и его модуль Pandas. Да, в блоке импорта у меня будет одна строчка: import pandas as pd. Перейдем непосредственно к коду:
Считаем данные и посмотрим на них:
Нам из пула данных нужны только 2 столбца, причем в полученном датасете из двух столбцов не должно быть одинаковых строк:
Приступаем к написанию алгоритма. Итак, в моей реализации это выглядит так: мы берем исходный датафрейм и циклично добавляем к нему самого себя, но по определенной связке: каждый раз ищем в атрибуте client_a_XX тех, кто есть в атрибуте client_b_XX, где ХХ – номер (итератор) цикла. Повторение – мать учения, поэтому на примере первой картинки, пока очищенной от лишних связей:
Мы нашли связь Людмила + Наталья, дальше мы ищем Наталью в столбце с Людмилой: вуаля – она нашлась в связке Наталья + Яна, дальше ищем и находим Яну. Ок, возвращаемся к коду. Для того чтобы данные соединять с этими же данными – создадим 2 одинаковых пула: исходный, на который будем накручивать его копии, и саму неизменяемую копию, на каждой итерации которую будем соединять с постоянно растущим исходным датафреймом.
Итак, вот создание копии:
Дальше создадим несколько вспомогательных переменных.
Первая – names_list — список названий столбцов. Его конечно можно получить, например, с помощью
Но нам нужны и будущие названия атрибутов, которые еще не существуют. Поэтому names_list у нас выглядит так:
То есть для каждой пары client_a / client_b создаем их «дочерние» client_a_1 / client_b_1, client_a_2 / client_b_2 и тд.
Здесь, во-первых, для примера умышленно ограничимся 3 итерациями, а во-вторых, создание такого списка с названиями атрибутов легко автоматизируется, код приводить не буду.
На основе первой вспомогательной переменной создадим еще одну, она понадобится для условия выборки данных в дальнейшем: