Главная » Хабрахабр » Анатомия рекомендательных систем. Часть первая

Анатомия рекомендательных систем. Часть первая

Я работаю дата-саентистом в компании CleverDATA. Мы занимаемся проектами в области машинного обучения, и один из наиболее частых запросов на разработку основанных на машинном обучении маркетинговых решений — это разработка рекомендательных моделей.

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

Источник

Обзор и постановка задачи

Задача рекомендательной системы – проинформировать пользователя о товаре, который ему может быть наиболее интересен в данный момент времени. Клиент получает информацию, а сервис зарабатывает на предоставлении качественных услуг. Услуги — это не обязательно прямые продажи предлагаемого товара. Сервис также может зарабатывать на комиссионных или просто увеличивать лояльность пользователей, которая потом выливается в рекламные и иные доходы.

В зависимости от модели бизнеса рекомендации могут быть его основой, как, например, у TripAdvisor, а могут быть просто удобным дополнительным сервисом (как, например, в каком-нибудь интернет-магазине одежды), призванным улучшить Customer Experience и сделать навигацию по каталогу более удобной.

По оценкам McKinsey, 35% выручки Amazon или 75% Netflix приходится именно на рекомендованные товары и процент этот, вероятно, будет расти. Персонализация онлайн-маркетинга – очевидный тренд последнего десятилетия. Рекомендательные системы – это про то, что предложить клиенту, чтобы сделать его счастливым.

Чтобы проиллюстрировать всё многообразие рекомендательных сервисов, приведу список основных характеристик, с помощью которых можно описать любую рекомендательную систему.

  1. Предмет рекомендации – что рекомендуется.

    В целом, рекомендовать можно что угодно.
    Здесь большое разнообразие – это могут быть товары (Amazon, Ozon), статьи (Arxiv.org), новости (Surfingbird, Яндекс.Дзен), изображения (500px), видео (YouTube, Netflix), люди (Linkedin, LonelyPlanet), музыка (Last.fm, Pandora), плейлисты и прочее.

  2. Цель рекомендации – зачем рекомендуется.

    Например: покупка, информирование, обучение, заведение контактов.

  3. Контекст рекомендации  – что пользователь в этот момент делает.

    Например: смотрит товары, слушает музыку, общается с людьми.

  4. Источник рекомендации – кто рекомендует:

    – аудитория (средний рейтинг ресторана в TripAdvisor),
    – схожие по интересам пользователи,
    – экспертное сообщество (бывает, когда речь о сложном товаре, таком, как, например, вино).

  5. Степень персонализации.

    Они допускают таргетинг по региону или времени, но не учитывают ваши личные предпочтения. Неперсональные рекомендации – когда вам рекомендуют то же самое, что всем остальным.

    Вы посмотрели несколько товаров, и внизу страницы вам предлагаются похожие. Более продвинутый вариант – когда рекомендации используют данные из вашей текущей сессии.

    Персональные же рекомендации используют всю доступную информацию о клиенте, в том числе историю его покупок.

  6. Прозрачность.

    Так меньше риск нарваться на «недобросовестные» системы, продвигающие проплаченный товар или ставящие более дорогие товары выше в рейтинге. Люди больше доверяют рекомендации, если понимают, как именно она была получена. Кроме того, хорошая рекомендательная система сама должна уметь бороться с купленными отзывами и накрутками продавцов.

    Например, когда выходит новый блокбастер, первым делом на него идут фанаты, соответственно, первую пару месяцев рейтинг может быть сильно завышен.
    Манипуляции кстати бывают и непреднамеренными.

  7. Формат рекомендации.

    Это может быть всплывающее окошко, появляющийся в определенном разделе сайта отсортированный список, лента внизу экрана или что-то еще.

  8. Алгоритмы.

    К наиболее классическим относятся алгоритмы Summary-based (неперсональные), Content-based (модели основанные на описании товара), Collaborative Filtering (коллаборативная фильтрация), Matrix Factorization (методы основанные на матричном разложении) и некоторые другие.
    Несмотря на множество существующих алгоритмов, все они сводятся к нескольким базовым подходам, которые будут описаны далее.

Источник

Это матрица, по одной из осей которой отложены все клиенты сервиса (Users), а по другой – объекты рекомендации (Items). В центре любой рекомендательной системы находится так называемая матрица предпочтений. На пересечении некоторых пар (user, item) данная матрица заполнена оценками (Ratings) – это известный нам показатель заинтересованности пользователя в данном товаре, выраженный по заданной шкале (например от 1 до 5).

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

Можно показывать повторные позиции, например, для пополнения запаса. Шаблоны потребления у людей разные, и не обязательно должны рекомендоваться новые товары. По этому принципу выделяют две группы товаров.

  • Повторяемые. Например, шампуни или бритвенные станки, которые нужны всегда.
  • Неповторямые. Например, книги или фильмы, которые редко приобретают повторно.

Если продукт нельзя явно отнести к одному из классов, имеет смысл определять допустимость повторных покупок индивидуально (кто-то ходит в магазин только ради арахисового масла определенной марки, а кому-то важно попробовать все, что есть в каталоге).

Некоторым пользователям нужны вещи только из их любимой категории (conservative recommendations), а кто-то, наоборот, больше откликается на нестандартные товары или группы товаров (risky recommendations). Понятие «интересности» тоже субъективное. В идеале стоит выбирать стратегию показа рекомендаций под каждого клиента отдельно, с помощью моделирования категории клиента. Например, видеохостинг может рекомендовать пользователю только новые серии любимого сериала, а может периодически закидывать ему новые шоу или вообще новые жанры.

Пользовательские оценки можно получить двумя способами:

  • явно (explicit ratings) – пользователь сам ставит рейтинг товару, оставляет отзыв, лайкает страницу,
  • неявно (implicit ratings) – пользователь явно свое отношение не выражает, но можно сделать косвенный вывод из его действий: купил товар – значит он ему нравится, долго читал описание – значит есть интерес и т.п.

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

Что и как показывать – это отдельная задача, которая использует полученные на шаге Prediction оценки, но может быть реализована по-разному. Также важно отличать термины Prediction (предсказание степени интереса) и собственно Recommendation (показ рекомендации).

В статье я ограничусь классическим определением данного термина, обозначающего выбор наиболее интересного товара для клиента. Иногда термин “рекомендация” употребляют в более широком смысле и имеют в виду любую оптимизацию, будь то выборка клиентов для рекламной рассылки, определение оптимальной цены предложения или просто выбор наилучшей стратегии коммуникаций с клиентом.

Неперсонализированные рекомендации

Начнем с неперсонализированных рекомендаций, поскольку они самые простые в реализации. В них потенциальный интерес пользователя определяется просто средним рейтингом товара: «Всем нравится – значит понравится и вам». По этому принципу работает большинство сервисов, когда пользователь не авторизуется в системе, например, тот же TripAdvisor.

Показываться рекомендации могут по-разному – как баннер сбоку от описания товара (Amazon), как результат запроса, отсортированный по определенному параметру (TripAdvisor), или как-то еще.

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

Проблема холодного старта

Холодный старт – это типичная ситуация, когда ещё не накоплено достаточное количество данных для корректной работы рекомендательной системы (например, когда товар новый или просто его очень редко покупают). Если средний рейтинг посчитан по оценкам всего трёх пользователей (igor92, xyz_111 и oleg_s), такая оценка явно не будет достоверной, и пользователи это понимают. Часто в таких ситуациях рейтинги искусственно корректируют.

Смысл таков: при малом количестве оценок отображаемый рейтинг больше тяготеет к некому безопасному «среднему» показателю, а как только набирается достаточное количество новых оценок, «усредняющая» корректировка перестает действовать. Первый способ – показывать не среднее значение, а сглаженное среднее (Damped Mean).

Математически, чем больше оценок, тем меньше вариация среднего и, значит, больше уверенность в его корректности. Другой подход – рассчитывать по каждому рейтингу интервалы достоверности (confidence Intervals). При этом понятно, что такая система будет достаточно консервативной, с тенденцией к занижению оценок по новым товарам (если, конечно, это не хит). А в качестве рейтинга можно выводить, например, нижнюю границу интервала (Low CI Bound).

Есть альтернативный и более точный способ его посчитать — Wilson Confidence Interval. Поскольку оценки ограничены определенной шкалой (например от 0 до 1), обычный способ расчета интервала достоверности здесь плохо применим: из-за хвостов распределения, уходящих на бесконечность и симметричности самого интервала. При этом получаются несимметричные интервалы примерно такого вида.

На картинке выше по горизонтали отложена оценка среднего значения рейтинга, по вертикали — разброс вокруг среднего значения. Цветом выделены различные размеры выборки (очевидно, чем выборка больше, тем меньше интервал достоверности).

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

Актуальность рекомендаций

В некоторых случаях также важно учитывать «свежесть» рекомендации. Это особенно актуально для статей или постов на форумах. Свежие записи должны чаще попадать в топ. Для этого используются корректирующие коэффициенты (damping factors). Ниже пара формул для расчета рейтинга статей на медиа сайтах.

Пример расчета рейтинга в журнале Hacker news:

где U = upvotes, D = downvotes, а P (Penalty) — дополнительная корректировка для имплементации иных бизнес-правил

Расчет рейтинга в Reddit:

где U = число голосов «за», D = число голосов «против», T = время записи. Первое слагаемое оценивает «качество записи», а второе делает поправку на время.

Очевидно, что универсальной формулы не существует, и каждый сервис изобретает ту формулу, которая лучше всего решает его задачу – проверяется это эмпирически.

Content-based рекомендации

Персональные рекомендации предполагают максимальное использование информации о самом пользователе, в первую очередь о его предыдущих покупках. Одним из первых появился подход content-based filtering. В рамках данного подхода описание товара (content) сопоставляется с интересами пользователя, полученными из его предыдущих оценок. Чем больше товар этим интересам соответствует, тем выше оценивается потенциальная заинтересованность пользователя. Очевидное требование здесь — у всех товаров в каталоге должно быть описание.

Такими признаками могут быть, например, текстовые описания, рецензии, состав актеров и прочее. Исторически предметом Content-based рекомендаций чаще были товары с неструктурированным описанием: фильмы, книги, статьи. Однако ничто не мешает использовать и обычные числовые или категориальные признаки.

Каждый элемент такого вектора – признак, потенциально характеризующий интерес пользователя. Неструктурированные признаки описываются типичным для текста способом – векторами в пространстве слов (Vector-Space model). Аналогично, продукт – вектор в том же пространстве.

Далее достаточно найти товар, описание которого наиболее близко к вектору интересов, т.е. По мере взаимодействия пользователя с системой (скажем, он покупает фильмы), векторные описания приобретенных им товаров объединяются (суммируются и нормализуются) в единый вектор и, таким образом, формируется вектор его интересов. решить задачу поиска n ближайших соседей.

Поэтому при определении числа совпадающих элементов в двух векторах все измерения нужно предварительно взвешивать по их значимости. Не все элементы одинаково значимы: например, союзные слова, очевидно, не несут никакой полезной нагрузки. Совпадение таких интересов имеет большее значение при определении близости двух векторов, чем совпадение популярных. Данную задачу решает хорошо известное в Text Mining преобразование TF-IDF, которое назначает больший вес более редким интересам.

Принцип TF-IDF здесь в той же мере применим и к обычным номинальным атрибутам, таким, как например, жанр, режиссер, язык. TF — мера значимости атрибута для пользователя, IDF — мера «редкости» атрибута.

Картинка ниже иллюстрирует, как именно зависит вес TF-IDF от показателей TF и IDF. Существует целое семейство похожих преобразований (например, BM25 и аналогичные), но содержательно все они повторяют ту же логику, что TF-IDF: редкие атрибуты должны иметь больший вес при сравнении товаров. Ближняя горизонтальная ось — это DF: частота атрибута среди всех товаров, дальняя горизонтальная ось — TF: логарифм частоты атрибута у пользователя.

Некоторые моменты которые можно учесть при реализации.

  • При формировании vector-space представления товара вместо отдельных слов можно использовать шинглы или n-граммы (последовательные пары слов, тройки и т.д.). Это сделает модель более детализированной, однако потребуется больше данных для обучения.
  • В разных местах описания товара вес ключевых слов может отличаться (например описание фильма может состоять из заголовка, краткого описания и детального описания).
  • Описания товара от разных пользователей можно взвешивать по-разному. Например, можем давать больший вес активным пользователям, у которых много оценок.
  • Аналогично можно взвешивать и по товару. Чем больше средний рейтинг объекта, тем больше его вес (аналог PageRank).
  • Если описание товара допускает ссылки на внешние источники, то можно заморочиться и анализировать также всю связанную с товаром стороннюю информацию.

Видно, что content-based фильтрация почти полностью повторяет механизм query-document matching, используемый в поисковых системах типа Яндекс и Google. Отличие лишь в форме поискового запроса — здесь это вектор, описывающий интересы пользователя, а там — ключевые слова запрашиваемого документа. Когда поисковики стали добавлять персонализацию, различие стерлось еще больше.

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

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

Коллаборативная фильтрация (User-based вариант)

Данный класс систем начал активно развиваться в 90-е годы. В рамках подхода рекомендации генерируются на основании интересов других похожих пользователей. Такие рекомендации являются результатом «коллаборации» множества пользователей. Отсюда и название метода.

На пальцах – для каждого пользователя ищем k наиболее похожих на него (в терминах предпочтений) и дополняем информацию о пользователе известными данными по его соседям. Классическая реализация алгоритма основана на принципе k ближайших соседей. Так, например, если известно, что ваши соседи по интересам в восторге от фильма «Кровь и бетон», а вы его по какой-то причине еще не смотрели, это отличный повод предложить вам данный фильм для субботнего просмотра.

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

«Похожесть» – в данном случае синоним «корреляции» интересов и может считаться множеством способов (помимо корреляции Пирсона, есть еще косинусное расстояние, есть расстояние Жаккара, расстояние Хэмминга и пр.).

Действительно, как любой метод ближайшего соседа, он требует расчета всех попарных расстояний между пользователями (а пользователей могут быть миллионы). У классической реализации алгоритма есть один явный минус – он плохо применим на практике из-за квадратичной сложности. При миллионе пользователей для хранения матрицы расстояний в сыром виде, потребуется минимум 4TB. Нетрудно посчитать, что сложность расчета матрицы расстояний будет $O(n^2m)$, где n — число пользователей, а m — число товаров.

Но если подходить с умом, то лучше ввести корректировки в алгоритм: Данная проблема отчасти может быть решена покупкой высокопроизводительного железа.

  • обновлять расстояния не при каждой покупке, а батчами (например, раз в день),
  • не пересчитывать матрицу расстояний полностью, а обновлять ее инкрементально,
  • сделать выбор в пользу итеративных и приближенных алгоритмов (например ALS).

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

  • Вкусы людей не меняются временем (или меняются, но для всех одинаково).
  • Если вкусы людей совпадают, то они совпадают во всем.

    Так часто бывает, когда рекомендуемые товары однородны (например, только фильмы). Например, если два клиента предпочитают одни фильмы, то книги им тоже нравятся одинаковые. Если это же не так, то у пары клиентов вполне могут совпадать предпочтения в еде, а политические взгляды быть прямо противоположными — здесь алгоритм будет менее эффективным.

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

Здесь понятно, что если возьмем слишком много соседей, то получим больше вероятность случайного шума И наоборот, если возьмем слишком мало, то получим более точные рекомендации, но меньшее количество товаров можно рекомендовать. Авторы из MovieLens в качестве оптимального количества соседей приводят цифры в 30-50 соседей для фильмов и 25-100 для произвольных рекомендаций.

Важный этап подготовки данных — нормализация оценок.

Стандартизация данных (scaling)

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

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

Нормализовать можно несколькими способами:

  • центрированием (mean-centering) — из оценок пользователя просто вычитаем его среднюю оценку,

    * актуально только для небинарных матриц

  • стандартизацией (z-score) — в добавок к центрированию делим оценку ее на стандартное отклонение у пользователя,

    например, 6 по пятибальной шкале), но такие ситуации довольно редки и решаются просто округлением в сторону ближайшей допустимой оценки.
    * здесь после обратного преобразования рейтинг может выйти за пределы шкалы (т.е.

  • двойной стандартизацией — первый раз нормируем оценками пользователя, второй раз — оценками товара.

    5, а пользователь ей ставит 5, то это сильный фактор, говорящий о том, что такие фильмы ему явно по вкусу.
    Если у фильма «Самый лучший фильм» средняя оценка 2.

«Похожесть» или корреляцию предпочтений двух пользователей можно считать разными способами. По сути нам надо просто сравнить два вектора. Перечислим несколько наиболее популярных.

  1. Корреляция Пирсона — классический коэффициент, который вполне применим и при сравнении векторов.

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

    Для борьбы со случайно завышенной корреляцией можно домножить на коэффициент 50 / min(50, Rating intersection) или любой другой damping factor, влияние которого уменьшается с ростом числа оценок.

  2. Корреляция Спирмана

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

  3. Косинусное расстояние

    Если приглядеться, косинус угла между стандартизированными векторами — это и есть корреляция Пирсона, одна и та же формула. Еще один классический коэффициент.

    угол между ними нулевой), то косинус угла между ними равен единице. Почему косинусное — потому что, если два вектора сонаправлены (т.е. И наоборот, косинус угла между перпендикулярными векторами равен нулю.

Интересное развитие коллаборативного подхода — так называемые Trust-based recommendations, в которых учитывается не только близость людей по интересам, но также их «социальная» близость и степень доверия между ними. Если например видим, что на фейсбуке девушка периодически заходит на страницу с аудиозаписями подруги, значит доверяет её музыкальному вкусу. Следовательно в рекомендации девушке можно вполне подмешивать новые песни из плейлиста подруги.

Обоснования рекомендаций

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

Чтобы не перегружать интерфейс, можно всю эту информацию вынести в кнопку «Tell me more». В рамках объяснения неплохо показывать оценку товара соседями, по какому именно атрибуту (например, актер или режиссер) было совпадение, а также выводить уверенность системы в оценке (confidence).

Например:

  • «Вам может понравиться фильм… поскольку там играет… и ...».
  • «Пользователи с похожими на ваш музыкальными вкусами оценили альбом… на 4.5 из 5».

Резюме

На этом закончу первую часть статьи. Мы рассмотрели общую постановку задачи, поговорили про неперсональные рекомендации, описали два классических подхода (content-based и коллаборативную фильтрацию), а также затронули тему обоснования рекомендаций. В целом двух этих подходов вполне достаточно для построения production-ready рекомендательной системы. В следующей части я продолжу обзор и расскажу о более современных методах, в том числе задействующих нейросети и глубокое обучение, а также про гибридные модели.

А пока посмотрите наши вакансии.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Перевод] Как я создавал карты континентов для своей игры

Часть 1. SVG и системы координат До недавнего времени размеры карт в моей игре Dragons Abound были фиксированными и несколько недетерминированными. Я считал их «региональными» — не картами всего мира, но его значительными частями, такими например, как западное побережье США ...

Google запатентовала VR-обувь, в которой можно ходить вечно

Взбираться по холмам, исследовать пещеры, путешествовать по бескрайним просторам. Скоро можно будет отправляться в большое приключение в комфорте своей квартиры. Ожидается, что это не только приведет к созданию новых игр «для впечатлительных», но и будет самым простым способом, не утруждая ...