Анатомия рекомендательных сервисов (Часть 2)

Эта статья – продолжение опубликованной в блоге Centrobit моей статьи Анатомия рекомендательных сервисов (Часть 1).
Здесь мы поговорим про алгоритмы товарных рекомендаций для интернет-магазинов, основанные на близости поведения посетителей. Из подключенных к crossss.ru более 150 магазинов, в 32% именно такие алгоритмы работают лучше любых других.

Например, в блоге crossss мы уже писАли о том, как внедрение рекомендаций в магазине BeMad повысило ценность посетителя на 253%.

Как мы этого добиваемся?

Сначала — краткое содержание предыдущей серии

Рекомендательная система – это программный комплекс, который определяет интересы и предпочтения посетителя и дает рекомендации в соответствии с ними. Такая система может встраиваться в сайт интернет-магазина с помощью JS-сниппета или интеграции по API, как, например, http://crossss.ru, и, таким образом, осуществляет расширяющую персонализацию интернет-магазина.
Для построения рекомендаций такая система может использовать различные данные о текущем посетителе, их основные группы — на картинке:

Рекомендательные системы по принципу рекомендации можно разделить на несколько классов (от более простых к более сложным):

• Рекомендации, подбираемые вручную (сотрудник магазина вручную заводит списки связанных товаров)
• Статические рекомендации товар-к-товару (Item-To-Item Collaborative Filtering — мы о них коротенько говорили в первой части статьи)
• Контентные рекомендательные системы (основанные исключительно на свойствах продуктов — мы их тоже обсудили в первой части )
• Динамические рекомендации, создаваемые на основе поведения конкретного посетителя и контекста

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

Подходы к построению динамической рекомендательной системы

В целом подходы к построению динамической рекомендательной системы можно разделить на методы, основанные на соседстве и методы, основанные на моделях.

Пусть у нас в интернет-магазине происходят события, состоящие в том, что посетителю U в ситуации S, находящемуся на странице с товаром I, показывается рекомендация товара A. В результате посетитель может совершить покупку на некоторую сумму.

В методах, основанных на соседстве, имеющиеся реализации событий напрямую используются для генерации рекомендации A при заданных {U, S, I}. В свою очередь, такие методы делятся на статистические (товар–к–товару), которые мы рассматривали в предыдущей статье, и динамические (посетитель-к-посетителю).

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

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

В отличие от методов, основанных на соседстве, методы, основанные на моделях, используют реализации событий для обучения предсказательной модели. В качестве такой модели может использоваться фактически любая аппроксимационная модель. В литературе известно использование байесовской кластеризации (Bayesian Clustering), анализа латентной семантики (Latent Semantic Analysis), латентной Дирихле-аллокации (Latent Dirichlet Allocation), метода максимальной энтропии (Maximum Entropy), машин Больцмана (Boltzmann Machines), метода опорных векторов (SVM — Support Vector Machines), и малоранговых аппроксимаций (Singular Value Decomposition). Вероятно, это только небольшая часть всего многообразия применявшихся для решения задачи моделей.

В этой статье мы рассмотрим методы, основанные на соседстве.

Динамические рекомендации, основанные на соседстве

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

Пусть теперь появился посетитель 5, для которого мы тоже знаем несколько рейтингов:

Какой товар ему порекомендовать?
Найдем ближайших к нему посетителей. Воспользуемся той же простейшей косинусной метрикой подобия между посетителями u и v, что и в первой статье:

Здесь – множество товаров, оцененных обоими посетителями u и v, и , – собственно эти оценки.
Итак, мы должны учесть только те товары, которым проставил рейтинги Посетитель5. Получаем следующие расстояния посетителей с Посетителем5:

Выберем k=2 ближайших по этому расстоянию к Посетителю5, это будут Посетитель2 и Посетитель1. В качестве приближения к оценке Посетителя5 товара номер i можно взять среднее их оценок:

Здесь — рассчитанная оценка товаров, не оцененных Посетителем5 самостоятельно, – множество оценивших i ближайших соседей v посетителя u.
В результате получаем для Посетитель5 такие оценки товаров:

Красным обозначены те товары, которые он еще не оценивал. Значит, надо ему порекомендовать Товар3.

У полученной нами оценки есть несколько почти очевидных недостатков. Во-первых, Посетитель4 намного ближе к Посетитель5, чем Посетитель2. Значит, его оценка должна бы быть важнее. Чтобы учесть это, возьмем взвешенную пропорционально близости посетителей оценку

Кроме того, разные посетители дают в среднем разную оценку товарам. Поэтому оценка 3 для Посетитель1 может быть скорее положительной, а для Посетитель2 – скорее отрицательной. Это означает, что вместо самих оценок полезно использовать приведенные и нормализованные для каждого посетителя оценки

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

Применяя модифицированную косинусную метрику, нормализуя оценки к интервалу [-1,1] и используя взвешенные на расстояние между посетителями оценки, получаем модифицированную матрицу оценок:

Расстояния посетителей с Посетителем5:

Теперь 2 ближайших к Посетителю5 — Посетитель2 и Посетитель4, а приведенные оценки товаров Посетитель5 таковы:

Значит, используя этот алгоритм, Посетителю5 мы порекомендуем Товар5.

Посетитель-к-посетителю или товар-к-товару?

Качество рекомендательных методов в значительной мере зависит от соотношения числа посетителей и товаров в интернет-магазине.
Рассмотрим магазин, в котором 1000 посетителей дали 10000 оценок 100 товаров (таким образом, оценено 10% товаров). Для простоты предположим, что оценки распределены равномерно по товарам. Тогда среднее ожидаемое число соседей у каждого посетителя выражается формулой

где U – множество посетителей, I – множество товаров, p – среднее число оценок на посетителя , а среднее число общих оценок у двух посетителей – .
В нашем примере это будет 650 и 1, соответственно.
С другой стороны, среднее ожидаемое число соседей у каждого товара выражается как
,
где q – среднее число оценок на товар , а среднее число общих оценок у двух товаров .
В нашем примере это будет, соответственно, 99 и 10.

Что из этого лучше?

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

то есть

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

Добро пожаловать в реальный мир

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

• Источник трафика; если трафик пришел из поисковика – то ключевая фраза, если из рекламы – то рекламная компания
• Просмотренные товарные категории, концентрация внимания (движение мыши) внутри товарных категорий, время, проведенное на каждой товарной категории
• Просмотренные карточки товаров, концентрация внимания (движение мыши) внутри карточки товара, время, проведенное на каждой карточке товара
• Поисковые запросы на сайте
• Посещенные нетоварные страницы сайта, например, условия оплаты или доставки, посещение которых непосредственно после карточки товара является индикацией желания купить данный товар

Единственным явным источником данных о предпочтениях посетителя является подтверждение заказов. При этом даже то, что посетитель положил товары в корзину, не является признаком того, что он их выбрал: во многих интернет-магазинах посетители складывают по нескольку однотипных товаров в корзину, чтобы их там сравнить – это происходит при отсутствии на сайте странички сравнения товаров.
В-третьих, для данных в неявной форме существует проблема интерпретации. Например, то, что посетитель открыл карточку товара, не является признаком того, что товар посетителю понравился. Наоборот, если карточка была открыта и быстро закрыта, то это говорит скорее о том, что товар посетителю неинтересен. Достаточно точно же интерес посетителя к товару можно оценить, только исследуя одновременно времена, проведенные посетителем на разных карточках товаров и движение мыши по каждой карточке.
Для каждого товара можно определить его ценность в воронке продаж – матожидание средней суммы покупки посетителем, оказавшимся на карточке товара i. Тогда, имея меру близости посетителей w, учитывающую их параметры поведения, и рассчитанные некоторым образом условные рейтинги товаров для каждого из этих посетителей, получаем оценку средней суммы покупки посетителем u, если он перейдет на карточку товара i

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

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

И на будущее…

Я думал, что это будет последняя статья в этой серии, но оказалось, что ни по времени, ни по объему даже описание того, что у нас сделано в рекомендательной системе сервиса персонализации http://crossss.ru, в нее не умещается. Поэтому эта статья в серии – далеко не последняя.
Отдельное спасибо @Владимиру Кольцову за критику терминологии первой статьи, надеюсь, что в этой я более корректен.

Автор: nickm197

Источник