Граф майнинг что это
Применение технологии graph mining в аудите банковских транзакций
Визуализация с помощью графа может отобразить значительно больше информации чем простая таблица. Одной из библиотек для построения графов в языке программирования Python является networkx.
Библиотека Networkx представляет концепцию сетевых графов, которые показывают взаимосвязи между набором различных объектов. Применение технологии графов позволяет быстро построить и визуализировать набор данных, хранящихся в табличном представлении через небольшое количество строк кода.
Чтобы определить цепочки транзакций между отправителем и получателем были построены графы, состоящие из узлов и ребер. В качестве узлов, в нашем случае, были рассмотрены номера клиентов, а ребрами служили транзакции. Для начала была проведена систематизация данных так, чтобы в столбцах таблицы содержалась только необходимая информация для дальнейшего исследования.
Процесс создания графа состоял из нескольких этапов:
Построенный граф получил следующий вид:
Для определения различных категорий клиентов, были предложены цветовые обозначения. С этой целью был создан массив для записи значений цвета, а затем использован в функции nx.draw.
Граф с измененными цветами вершин выглядит следующим образом:
Рассмотренный пример позволил, при помощи инструмента сетевых графов, выяснить процессы взаимодействия между клиентами банка. Простым набором нескольких строк кода мы смогли отобразить таблицу с банковскими транзакциями между клиентами.
Применение инструментов библиотеки network, позволило ускорить процесс определения взаимодействий клиентов, а графическая визуализация помогла аудитору выяснить участников транзакций — получателей и отправителей денежных средств.
«Секреты Process Mining» или «PM: Просто о сложном»
Еще раз, «Что такое Process Mining?»
Традиционный подход к анализу бизнес-процессов состоит в интерпретации модели процессов со слов непосредственных участников этих бизнес-процессов и анализа множества бумажных документов и оперативных отчетов. Недостаток такого подхода в трудозатратах. Учитывая рост объема данных и скорость изменений в бизнесе, подобные методы уже не позволяют эффективно исследовать процессы. Кроме того, такой подход может дать ложные результаты из-за неполноты информации и субъективности участников процесса. Уровень автоматизации растет, поэтому совершенно логично рассматривать процессы на основании логов информационных систем (ИС). В этом и заключается хитрость инструментария Process Mining, который может на основании факта работы людей в той или иной ИС восстановить фактическую модель бизнес-процесса, что позволит увидеть, как же этот процесс выглядит в действительности. Иллюстрация приведенная ниже хорошо отражает основную задачу Process Mining – найти нестандартные пути или исключительные ситуации — «тропинки», которыми ходят сотрудники, и возможно ходят массово.
«С чего начать?»
Многие, отвечая на этот вопрос допускают ошибку. Ответ, казалось бы, очевидный – подготовка логов, но это не совсем так. Перед тем как приступить к подготовке данных лога ИС, необходимо понимать сам анализируемый процесс. Это не менее важный этап, т.к. без понимания и погружения в регламентируемый процесс не удастся корректно структурировать данные для создания таблицы и дать оценку реальному процессу. Итак, условно можно выделить несколько этапов в процессной аналитике:
«Везде говорится о каких-то логах… Да что это вообще такое?» или «Какие они, исходные данные?»
Поиск, сбор логов ИС и подготовка исходных данных занимает более 50% от всего времени, затраченного на процессную аналитику, этот этап по праву можно назвать самым важным и ответственным. Давайте разберемся что такое лог ИС. Лог, он же журнал событий — это подробный протокол, содержащий системную информацию о действиях пользователей в хронологическом порядке. Лог содержит огромное множество записей, каждая строка которой — это одно взаимодействие с программой. Для использования инструментов Process Mining необходимо в логе ИС выделить следующие обязательные столбцы:
Настоятельно рекомендуется не ограничивать себя только минимальным набором колонок. Граф процесса можно будет успешно восстановить и по трем обязательным столбцам, но избавиться от ощущения, что чего-то не хватает, будет сложно. Дополнительные колонки – это любая интересная вам информация, которая изменяется с течением процесса или связана с конкретным событием. Например, имя сотрудника, который совершил событие, рабочая группа, текущий приоритет заявки.
Рассмотрим всем понятный процесс – процесс подбора персонала. Каждый, как минимум, один раз принимал в нем непосредственное участие. Представим, что по регламенту процесс (activity) выглядит так:
И имеет три варианта завершения:
«Лог готов, что дальше?»
А дальше выбираем инструмент для визуализации нашего процесса. Среди наиболее популярных готовых инструментов можно выделить Fluxicon Disco, ProM и Celonis (обзор на данные инструменты в сообществе NTA можно посмотреть по ссылкам раз и два). И конечно же нельзя не упомянуть библиотеку с открытым исходным кодом PM4PY для Python, более подробно о которой уже рассказали здесь. Подход к выбору инструмента субъективен и остаётся за Вами. Для получения графа реального процесса подаём на вход инструменту лог файл и определяем сущности (case id, activity, timestamp).
Для построения графа нами использован популярный инструмент — онлайн-платформа Celonis и готовый лог в формате *.csv, содержащий ключевые сущности:
«И что мне делать с этой лапшой?»
На выходе мы получили весьма сложный и запутанный граф.
Используя стандартные возможности онлайн-платформы Celonis для начала отфильтруем незавершенные (не «зависшие», а именно незавершенные по времени) экземпляры в бизнес-процессе.
Далее убираем вероятности самых сложных бизнес-процессов, т.е. самых длинных и маловероятностных экземпляров, для этого в большинстве готовых инструментов уже реализована возможность добавлять либо убирать связи-переходы между действиями (событиями), а также сами действия (события), что позволяет увидеть наиболее частотные действия и наиболее частотные переходы и управлять этой визуализацией. Таким образом добиваемся читабельности реального процесса.
Слева изображен регламентируемый процесс, справа – процесс на основании лога ИС.
Фактически на данном этапе мы разобрались какие экземпляры у нас «нормальные», т.е. какой основной поток в рамках бизнес-процесса; разобрались почему возникли исключительные случаи и отклонения от основного потока. Здесь нам помогли встроенные инструменты фильтрации: временные фильтры, фильтры экземпляров процессов по производительности, фильтры неполных экземпляров процессов и фильтры событий по атрибутам.
Что искать?
Анализируем незаконченные экземпляры в процессе. Накладываем фильтр тех экземпляров бизнес-процесса, которые не завершились отказом кандидату, отказом от кандидата или передачей документов на оформление и получаем представление о том, как выглядят не дошедшие до конца или зацикленные экземпляры бизнес-процесса.
Здесь мы акцентировали свое внимание на следующих ситуациях:
— цикл на этапе поиска резюме – это значит, что операция поиска резюме была повторена несколько раз;
— цикл на этапе «Организация встречи с руководителем» – вполне возможно, что руководитель не назначает встречу, поэтому экземпляр процесса никак не может закончится;
— цикл на этапе «Организация встречи с ГД».
Еще одним вариантом анализа является поиск «петель согласования». Это те места, или элементы, в процессе, с которых поток работ часто возвращается обратно – на доработку, тем самым увеличивается общее время исполнения бизнес-процесса и возрастает его стоимость.
Мы выделили на общей модели возврат и обнаружили, что у нас есть некий цикл между этапами «Согласование резюме» и «Поиск резюме».
Таким образом мы видим зацикливание («пинг-понг») в процессе и выделяем те экземпляры, которые сопровождают данный «пинг-понг». Для более детального анализа мы «ныряем вниз» непосредственно к самим экземплярам процесса и видим какие именно это вакансии, кто исполнитель, когда это произошло и т.д.
Следующий вариант – анализ завершенных процессов. Рассматриваем экземпляры, которые завершились успехом — накладываем фильтр на финальное действие «Передача документов на оформление». Ищем те случаи, когда финальный результат получен в нарушение регламента. Выделяем на общей схеме прыжок от этапа «Собеседование с руководителем» на финальный этап «Прием документов на оформление». Таким образом находим кандидатов, принятых минуя этап согласования с ГД.
Еще пример, видим, что процесс начался с этапа «Уведомление о решении ГД», т.е. фактически кандидат принят в обход HR одним только решением ГД.
Еще одна попытка обойти процедуру – процесс начинается сразу с финального этапа «Прием документов на оформление».
Среди прочего, готовые инструменты с легкостью позволяют произвести оценку процесса с точки зрения производительности и временных затрат. Выделяем и анализируем те экземпляры процесса, выполнение которых длится намного дольше остальных, а также сверяем регламентные и фактические сроки исполнения процесса.
Итак, проанализировав модель восстановленного бизнес-процесса (ту самую «лапшу»), можно обнаружить: излишние циклы согласования, отмену ранее совершенных действий, «пинг-понг» исполнителей, задержки по времени выполнения функций, лишние действия в процессе, лишних или не эффективных исполнителей и главное исключительные ситуации в процессах, которые возникают из-за ошибок исполнителей и исправление которых требует серьезных ресурсов.
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 на 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.
Таким образом, провели анализ данных на предмет выявления закономерностей движения средств между счетами. Полный пример с кодом можно найти в тетрадке.