Практическая демонстрация концепции Map-Reduce (в стиле Hadoop) на реальных данных

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

Данные о конверсии ограничены и неоднородны: некоторые конверсии отслеживаются, некоторые – нет; некоторые являются нестрогими, то есть подразумевают просто переход  (при этом коэффициент конверсии выше 10%); другие — строгими, то есть подразумевают, например, покупку с помощью кредитной карты (при этом коэффициент конверсии ниже 1%).

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

mapreduce

Мы будем работать с набором данных о кликах, собранным за 7 суток. Предположим, что в нем содержится информация о 50 миллионах кликов. Полагаться только на часть этих данных рискованно, потому что основной объем мошеннических кликов распределен по большому количеству партнерских ресурсов и множеству IP-адресов, при этом на один IP-адрес приходится всего несколько кликов в день (низкая частота).

Файл набора данных в идеале представляет собой текстовый файл с табуляцией в качестве разделителя, поскольку при использовании CSV-файла может произойти смещение полей в результате того, что некоторые текстовые поля могут содержать в себе запятые. Набор данных содержит 60 полей: Keyword (ключевые слова, т.е. запрос пользователя или ключевые слова рекламодателя); Referral (ресурс, с которого был выполнен переход, т.е. фактический домен ресурса или домен рекламной биржи); UA ID (user agent ID, идентификатор клиента пользователя; клиентом обычно является браузер, но может быть и бот); Affiliate ID (идентификатор филиала); Partner ID (идентификатор партнера; партнер может иметь в своем составе несколько филиалов); IP (IP-адрес); Day (дата); Time (время); City (город) и др.

Первым шагом является отбор полей для анализа. Опираясь на опыт в предметной области, мы будем использовать следующие поля:

  • IP
  • Day
  • UA ID. Создадим таблицу поиска (lookup table) для клиентов.
  • Partner ID
  • Affiliate ID

На основе перечисленных выше базовых параметров сформируем сводную таблицу. Каждая комбинация значений (IP, Day, UA ID, Partner ID, Affiliate ID) представляет собой атомарную подгруппу данных, так называемый «бакет» (bucket).

Создание сводной таблицы. Шаг Map

Сводная таблица будет создана в форме текстового файла (так же, как и в Hadoop). Ключом (для соединений и группировок) будет: (IP, Day, UA ID, Partner ID, Affiliate ID). Для каждого атомарного бакета (IP, Day, UA ID, Partner ID, Affiliate ID) мы также вычислим следующие параметры:

  • Количество кликов
  • Количество уникальных клиентов
  • Список клиентов

Список клиентов для данного бакета выглядит следующим образом: ~6723|9~45|1~784|2. Эта запись означает следующее: в рамках данного бакета мы имеем 3 браузера (с идентификаторами 6723, 45 и 784), 12 кликов (9 + 1 + 2), и, например, браузер с идентификатором 6723 сгенерировал 9 кликов.

На Perl необходимые вычисления легко выполняются при последовательном проходе по данным. Следующий код рассчитывает количество кликов:

$hash_clicks{«IP\tDay\tUA_ID\tPartner_ID\tAffiliate_ID»};

Формирование списка клиентов для данного бакета выполняется чуть сложнее, но также почти тривиально.

Проблема заключается в том, что в какой-то момент хеш-таблица становится слишком большой, и выполнение скрипта существенно замедляется. Чтобы решить эту проблему, необходимо разбить исходные данные на несколько подмножеств и выполнить эту операцию для каждого из них отдельно. В рамках концепции Map-Reduce эта процедура называется шагом Map. Необходимо решить, какое поле следует использовать для разделения данных. В нашем случае хорошим вариантом является поле IP-адреса, потому что это самый важный параметр. Кроме того, он обеспечит равномерную нагрузку. Мы можем разбить IP-адрес на 20 диапазонов на основании значения первого байта. В результате получим 20 подмножеств. Разбиение исходных данных на подмножества легко выполняется с помощью Perl-скрипта, который последовательно перебирает все записи и распределяет их по подмножествам на основании IP адреса.

Создание сводной таблицы. Шаг Reduce

После того, как мы создали 20 сводных таблиц (по одной для каждого подмножества данных), необходимо объединить их вместе. Мы не можем использовать для этого хеш-таблицу по той же причине, по которой нам пришлось применить шаг Map на предыдущем этапе.

Для решения этой задачи применим следующий подход. Отсортируем каждое из 20-ти подмножеств по IP-адресу. Объединим отсортированные подмножества, чтобы получить общую сводную таблицу T. Объединение отсортированных данных эффективно выполняется следующим образом: перебираем в цикле 20 отсортированных подмножеств и в пределах каждого из них во вложенном цикле проходим все записи; используем 20 указателей (по одному на каждое подмножество), чтобы отслеживать текущее положение.

Теперь у нас есть общая сводная таблица T с многочисленными вхождениями одинаковых атомарных бакетов. Все одинаковые бакеты необходимо агрегировать. Для этого последовательно проходим по таблице T и применяем хеш-таблицы, но на этот раз малого размера. Допустим, мы находимся в середине блока данных, относящегося к одному IP-адресу, например, 231.54.86.109 (мы помним, что таблица T отсортирована по IP-адресу). Чтобы агрегировать количество кликов, соответствующее бакету (231.54.86.109, Day, UA ID, Partner ID, Affiliate ID), применяем следующий код:

$hash_clicks_small{«Day\tUA_ID\tPartner_ID\tAffiliate_ID»};

Обратите внимание, большая разница между $hash_clicks и $hash_clicks_small заключается в том, что во втором случае IP-адрес не является частью ключа, в результате чего хеш-таблицы имеют в миллионы раз меньший размер. Когда мы достигаем нового IP-адреса при проходе таблицы T, необходимо просто сохранить информацию, находящуюся в $hash_clicks_small и малых хеш-таблицах для предыдущего IP-адреса, освободить память, занимаемую этими хеш-таблицами, и повторно использовать их для следующего IP-адреса. Процедура повторяется, пока не будет достигнут конец таблицы T.

Таким образом, мы получили сводную таблицу, которая и была нашей целью. Давайте назовем ее S. Исходный набор данных содержит 50 миллионов записей и десятки полей, некоторые из которых имеют значительный объем. Сводная таблица намного более удобна и компактна, хотя она по-прежнему слишком большая, чтобы поместиться в Excel.

Создание правил

Набор правил для выявления мошенничества будет создан только на основе данных, присутствующих в сводной таблице S (и в дополнительных сводных таблицах высокого уровня, полученных из таблицы S). Пример правила: «IP-адрес активен более 3-х суток за последние 7 суток». Благодаря таблице S, вычисление количества кликов и анализ данного агрегированного бакета – простая задача. И действительно, таблица S может рассматриваться, как «куб» (с точки зрения базы данных), а создаваемые нами правила просто уменьшают размеры этого куба по некоторым из осей. Во многих случаях создание набора правил сводится к созданию менее гранулированных сводных таблиц на основе таблицы S и последующему тестированию.

Усовершенствования

IP-адреса можно разбить на категории и сделать IP-категорию базовым параметром в системе правил. Также можно рассчитать сводную статистику по IP-категориям. Более подробную информацию вы можете найти в статье «Отображение топологии Интернета» (Internet topology mapping). Наконец, необходимо выполнить автоматизированные запросы nslookup для тысяч тестируемых IP-адресов (как плохих, так и хороших).

Аналогичным образом можно разбить на категории клиенты, что само по себе является интересной задачей таксономии. Рационально использовать по меньшей мере три категории клиентов: мобильный клиент; «честный» бот, который идентифицирует себя, как бота; другой. Списки клиентов вида ~6723|9~45|1~784|2 (см. выше) для каждого атомарного бакета применяются для выявления мошенничества на основе ситуации, когда на один IP-адрес приходится несколько разных клиентов, а также на основе типа прокси (хороший или плохой).

Заключение

В этой статье был представлен подход Map-Reduce и продемонстрировано его применение для извлечения и обобщения данных, содержащихся в лог-файлах большого объема. Мы рассмотрели процесс создания иерархической базы данных со многими иерархическими уровнями обобщения, начиная с гранулированной сводной таблицы S, содержащей всю необходимую информацию на атомарном уровне (атомарные бакеты), до обобщений высокого уровня, относящихся к правилам. В процессе были использованы только текстовые файлы. Можно назвать это иерархической NoSQL базой данных (NoSQL Hierarchical Database). Таблица S и способ ее создания подобны архитектуре Hadoop.

По материалам: DataScienceCentral 

Добавить комментарий

Ваш e-mail не будет опубликован.

закрыть

Поделиться

Отправить на почту
закрыть

Вход

закрыть

Регистрация

+ =