Наши клиенты-магазины хотят делать крутой маркетинг. Чтобы люди больше покупали, они регулярно шлют им email-рассылки. И каждый раз думают: “Что же написать в письме?”.
Можно писать просто: “Покупайте у нас почаще!”, но это не очень-то работает. Идея получше — вставлять в письмо рекламу товаров. Желательно, рекламу товаров, которые заинтересуют покупателей.
Дальше расскажу о том, как мы с нуля делали настоящие персональные рекомендации.
Выбираем, что рекомендовать
Рекомендовать можно что угодно.
Можно рекомендовать самые покупаемые товары. Например, в магазине электроники это жесткие диски и мобильные телефоны. Но что делать тем, у кого они уже есть? Получается, что всем рекомендуется одно и то же — не очень круто.
Можно рекомендовать что-то похожее на то, что человек смотрел на сайте — например, посмотрел туфли, порекомендуем… другие туфли! Как бы странно не звучало, это используется на практике и даже работает.
Но мы все же хотели сделать что-то особенное, чтобы каждый видел в письме что-то личное, что ему действительно нужно, чтобы у него было желание возвращаться в магазин снова и снова. Задача усложнялась тем, что у нас почти 300 клиентов-магазинов в самых разных областях. И рекомендации должны работать хорошо для каждого из них, подстраиваясь под специфику конкретного магазина автоматически. Так мы начали делать универсальные персональные рекомендации.
Делаем базовую модель
Начитавшись статей от Амазона, решили сделать самую базовую модель персональных рекомендаций и посмотреть, как она себя покажет.
Для начала скачиваем таблицу покупок и разворачиваем ее в разреженную матрицу клиент-продукт.
Преобразование списка покупок в матрицу клиент-продукт
Дальше используем коллаборативную фильтрацию. Интуиция здесь проста: клиент №1 купил продукт №1 и два продукта №3; клиент №2 также купил продукт №1 — вероятно, он захочет купить продукт №3.
Коллаборативная фильтрация предполагает разложение одной большой разреженной матрицы на две плотные вытянутые матрицы латентных признаков существенно меньшего размера. Для разложения мы использовали готовую реализацию AlternatingLeastSquares из библиотеки implicit.
После обучения модели получаем латентные признаки для всех клиентов и всех продуктов. Они представлены в виде матриц (количество клиентов х количество признаков) и (количество продуктов х количество признаков) соответственно.
Латентные признаки — признаки, нигде не заданные явно, как, скажем, рост человека или площадь квартиры. Обычно они получаются вследствие каких-то математических преобразований над исходными данными.
Матрицы латентных признаков устроены так, что если их перемножить, получится матрица того же размера, что и исходная. С высокой долей условности можно сказать, что там, где были числа побольше, будут числа побольше — около единицы. Где поменьше — там поменьше. Там, где были нули, будут числа небольшие, около нуля, возможно, отрицательные. Но важно то, что в некоторых местах, где были нули, появятся довольно большие числа — наши будущие рекомендации.
Одинаковым цветом выделены покупки, которые сильно влияют друг на друга. Рамкой выделены некоторые будущие рекомендации
Теперь, если взять вектор признаков для конкретного клиента и умножить его на матрицу признаков продуктов, получим вектор скоров всех продуктов для этого клиента. Останется лишь выбрать из него несколько продуктов с максимальным скором.
Небольшой нюанс — среди рекомендуемых продуктов с высокой вероятностью будут те, что уже были куплены клиентом, — их нужно исключать.
Как ни странно, но такая простая схема оказалась рабочей и клиенты с удовольствием тестировали наши рекомендации. Мы делали AB тесты, где сравнивали персональные рекомендации с хитами продаж. В некоторых случаях разницы не было никакой, но в некоторых видели статистически значимый прирост конверсий в заказы до 10%. В основном это были магазины с высокой частотой покупок, и, соответственно, большим количеством данных.
Используем больше данных
Было понятно, что информации об одних покупках недостаточно, чтобы сделать хорошие рекомендации. Хотя бы потому, что многие клиенты вообще не имеют покупок. Поэтому мы решили улучшать наши рекомендации.
Добавляем информацию о всех действиях
Помимо покупок, мы стали учитывать просмотры продуктов, а также добавление их в различные списки: в корзину, в “избранное” и т.п.
Для каждого типа действия мы выбирали вес и добавляли его в нашу разреженную матрицу с этим весом.
Учитываем время действия
Мы подумали, что вчерашняя покупка и покупка годовой давности не должны оказывать на рекомендации одинаковый эффект. Поэтому мы ввели экспоненциальный коэффициент забывания на все действия.
Кроме того, для некоторых магазинов, например, одежды, важна сезонность: если сейчас лето, то нужно больше обращать внимание на то, что человек купил летом год назад, чем на то, что он купил полгода назад зимой.
Учитываем явные признаки
В нашей базе данных есть самая разнообразная информация. Мы решили, что использовать нужно все.
Для продуктов мы стали использовать цену, производителя, категорию продукта и всевозможные дополнительные поля, которые указывает магазин (размер одежды, цвет мебели, наличие ГМО в собачьем корме и т.п.).
Для клиентов взяли пол, возраст, домен почтового ящика, операционную систему в последней сессии и канал, через который он попал в базу (онлайн, оффлайн, соц. сеть и т.п.).
Чтобы все это присоединить к модели, мы:
- Делаем матрицы признаков (отдельно для клиентов и продуктов), предварительно их обработав стандартными методами: scaling, one-hot encoding.
- На основе признаков продуктов и имеющейся матрицы клиент-продукт восстанавливаем парные дополнительные признаки для клиентов. Восстановление делается таким образом, чтобы произведение признаков продуктов на парные к ним признаки клиентов как можно лучше приближало исходную матрицу. Эти дополнительные признаки приклеиваем к уже имеющимся латентным.
- Аналогично делаем с признаками клиентов.
Дополнение латентных признаков явными
Теперь у нас уже больше признаков и мы можем делать более точные рекомендации. С этого момента количество тестов, которые показывали статистически значимый результат в пользу персональных рекомендаций, стало расти. Помимо тестов, субъективная оценка экспертами также улучшилась.
Настраиваем гиперпараметры
Сначала о метриках
Конечно же, мы все время тестировали наши рекомендации. Мы проводили как офлайн тесты, так и онлайн.
Безусловно, онлайн AB-тесты — это более надежный способ проверить, насколько хороши рекомендации. И тесты эти показывали неплохие результаты.
Однако, онлайн тесты это жутко неудобно:
Нужно найти магазин, который захочет рисковать своими клиентами и тестировать новую версию алгоритма.
Потом нужно подождать день/неделю/две, чтобы получить какие-то статистически значимые результаты.
Нужно повторить это 100 раз, чтобы протестировать 100 различных вариантов.
Поэтому без офлайн тестов не обойтись. И здесь будет не лишним упомянуть о том, как мы их проводили.
В качестве офлайн метрики выбрали популярную и простую — nDCG@K (Normalized Discounted Cumulative Gain at K), точнее ее среднее для нескольких тысяч клиентов.
Эта метрика качества ранжирования. Она принимает значения от 0 до 1 и показывает, насколько хороши выдаваемые рекомендации.
Чтобы посчитать значение метрики нужен эталон — идеальные рекомендации. Такого эталона у нас нет. Но мы нашли выход: считали рекомендации на момент времени в прошлом — месяц назад — и смотрели, что человек купил за этот месяц — это и было нашим эталоном.
Здесь есть небольшая хитрость: если бы мы что-то порекомендовали клиенту месяц назад, он мог бы это купить, а так не купил. Но об этом мы никогда не узнаем.
Еще один момент: мы могли порекомендовать синюю шапку с помпоном, а клиент купил синюю шапку без помпона. Товары вроде-бы похожи, но разные — метрика проседает. Поэтому при расчете метрики мы стали учитывать похожесть товаров.
А вот теперь о гиперпараметрах
Поскольку у нас есть офлайн метрика, мы можем смело тестировать самые разные варианты наших рекомендаций и не переживать, что кто-то может пострадать.
Неделю напрягая фантазию, мы перепробовали 2-3 десятка различных модификаций нашего алгоритма, среди которых были простые, такие как разные коэффициенты забывания, и более сложные, такие как использование другого алгоритма приклеивания явных признаков клиентов и продуктов.
Некоторые модификации не дали эффекта нигде. Некоторые показали улучшения на всех проектах — их мы зафиксировали. А некоторые на ряде проектов улучшали метрику, а на других ухудшали. Так у нас появилась настройка гиперпараметров.
Сейчас у нас 11 гиперпараметров. Чтобы найти оптимальные значения каждого из них для всех проектов понадобилось несколько суток.
После настройки оказалось, что в среднем метрика по всем проектам выросла в 6 раз, а самый сильный прирост — в 35 раз!
Улучшаем функционал
Мы умеем делать неплохие персональные рекомендации. Круто.
Но как они работают? Примерно так: ежедневно ночью, когда на нагрузка на серверы спадает, мы запускаем пересчет рекомендаций для всех проектов. Потребление оперативки и CPU взлетает, проходит несколько часов, и рекомендации готовы. Они ложатся в специальное хранилище и ждут, пока их оттуда возьмут.
Зачем возьмут? Например, чтобы отправить в письме. Звучит неплохо.
Или чтобы показать на сайте. Представьте, вы заходите на сайт, выбираете себе мобильник, а там персональные рекомендации в окошке, и предлагают вам… чайник! Почему чайник? Да потому что вы месяц назад купили микроволновку, а алгоритм вычислил, что тем, кто купил микроволновку, часто нужен чайник.
Но вам-то нужен мобильник! Как же быть?
Пришел черед делать рекомендации, которые работают в режиме реального времени.
С точки зрения математики ничего нового: мы просто разделили этап обучения модели и этап выдачи рекомендаций.
Обучаем модель мы по-прежнему раз в сутки.
А рекомендации теперь умеем выдавать в режиме онлайн. Как только человек совершает какое-то действие на сайте, например, просматривает товар или добавляет его в корзину, формируется запрос. В запросе указывается, кто, что и с каким продуктом сделал. Алгоритм рекомендаций обрабатывает этот запрос и в ответ формирует список рекомендаций для этого клиента.
Чтобы это стало возможным, нам потребовалось:
- Сделать хранилище, куда после обучения складываются модели.
- Организовать key-value хранилище для хранения ранее совершенных клиентом действий, потому что загружать их каждый раз из базы очень долго.
- Существенно ускорить наши рекомендации. Основной точкой ускорения стало использование библиотеки приближенного поиска ближайших соседей nmslib для выбора наиболее релевантных человеку продуктов. Хитрые ребята из Microsoft придумали, как свести задачу перемножения матриц и выбора топа элементов с наибольшим значением к задаче поиска ближайших соседей.
- Сделать микросервис, который отслеживает действия человека на сайте, присылает запрос на рекомендации, забирает эти рекомендации и показывает человеку.
И эта адская машина заработала. И заработала быстро. Как только вы посмотрели мобильник, за доли секунды рекомендации пересчитываются, и вот вам уже рекомендуются мобильники, чехлы, стекла и тому подобное.
Чтобы было понятнее, что есть быстро: мы выдерживаем нагрузку 7000 rpm (запросов в минуту), используя лишь 3 ядра CPU Intel Xeon 2.6 GHz. Такую нагрузку дают в пики активности 2 наиболее крупных наших клиента.
Что дальше
Кажется, что из текущей модели мы выжали все, что можно.
Дальнейшее улучшение потребует кардинальных изменений.
Один из вариантов улучшения — предварительная сегментация покупателей на группы.
Люди ведут себя по разному: кто-то покупает часто и понемногу, кто-то редко, но большими партиями, кто-то дорогие товары, кто-то дешевые. Вообще-то модель должна сама находить такие группы и рекомендовать им то, что нужно.
Но это может быть сложно, например, если группы небольшие. Например, немногочисленная группа юридических лиц. Или группа мужчин в женском магазине. Их не всегда можно определить по формальному признаку “пол”, потому что жена может пользоваться картой лояльности, оформленной на мужа, и наоборот.
Можно попробовать помочь модели, если сначала выделить эти группы, а затем строить модель для каждой из них отдельно.
Другим, более серьезным подходом к улучшению, может стать учет истории действий.
Сейчас мы учитываем только давность действия, и это не позволяет нам выявлять закономерности в поведении. Например, модель не может понять, что, если сначала покупали одежду для беременных, а потом подгузники, то пора рекомендовать детское питание.
Вообще, работа над улучшением рекомендаций, на наш взгляд, может длиться почти бесконечно. С каждым новым клиентом, использующим их, появляются новые кейсы и новые гипотезы для улучшения.
Так что мы продолжаем улучшаться, и будем стараться писать о том, что делаем. Не прощаемся :)