Как работают персональные рекомендации

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

Этот пост позволит понять ту часть сложной работы Google, которая связана непосредственно с системой рекомендаций для пользователя. Этот пост будет по традиции содержать разные определения и формулы. :) Системы персональных рекомендаций играют важную роль в жизни крупных порталов и интернет-магазинов. Amazon заявляет, что более 40% продаж на их сайте происходит за счёт грамотной системы рекомендаций для пользователя. Существует несколько способов построения такой системы. Это и примитивные модели, и иерархическая кластеризация, и коллаборативная фильтрация, о которой далее пойдет речь. Строго говоря, проблема построения персональных рекомендаций выглядит так:

Для истории кликов N пользователей (U = {u1, u2, ..., uN}) над множеством статей S (S= {s1, s2, ..., sM}) и выбранного пользователя u с множеством истории кликов Cu {si1, ... si|Cu|} подобрать K статей, которые могут быть для него интересны.

Google решает эту проблему с помощью двух алгоритмов:

• MinHash-кластеризация
• Вероятностная латентно-семантическая индексация (PLSI)

MinHash работает достаточно просто - он делит всех пользователей системы по кластерам с вероятностью, соответствующей пересечению множеств интересов системы. В случае Google под интересом подразумевается клик пользователю ui на статью sj. Математически эту метрику "схожести" можно записать как

где ui - пользователи, Cui - множество интересов пользователя. Чтобы система работала корректно, метрика должна быть определена на множестве всех пользователей - Google применяет улучшения алгоритма Locality Sensitive Hashing и Map Reduce для проведения таких вычислений в реальном времени. Вероятностная латентно-семантическая индексация рассматривает пользователей и статьи как случайные величины и строит связь между этими множествами через смешанное распределение. Представьте огромный массив, состоящий из всех пользователей и статей. Прочтя ту или иную новость, в соответствующую ячейку матрицы заносится маркер. Размер массива очень большой и PLSI уменьшает его, позволяя спрогнозировать все комбинации пользователей и статей. Детальное описание модели опустим, оно достаточно сложное. :) После того, как кластеры пользователей сформированы, можно определить, насколько та или иная статья подходит для рекомендации:

• Взять кластеры, к которым относится пользователь.
• Для каждого кластера проверить, как часто его пользователи "голосовали" за статью (т.е. кликали на неё). Нормализовать величину.
• Посчитать ранг статьи.

Для более точной работы персональных рекомендаций Google также использует метрику, которая называется "со-визиты" (covisitation). Идея её в том, что со-визит между статьями s и s' имеет место, если в течение заданного интервала времени пользователь сначала перешёл по статье s, а потом по s' или наоборот. Хранить все со-визиты можно в виде графа, узлами которого являются статьи, а рёбрами - количество со-визитов.

Теперь, после определения всех методов построения рекомендаций, можно собрать все алгоритмы воедино и построить такую систему:

1. Пользователь открывает Google.
2. Система выбирает кандидатов на рекомендации, построив объединение двух множеств: множества статей, которые просматривались всеми пользователями кластера, и множества статей, которые имели со-визиты с историей пользователя.
3. Сортировка кандидатов.
4. Выдача данных пользователю.

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

Персональные рекомендации для интернет-магазина

Алгоритм простой:

1. Строим таблицу истории кликов для каждого пользователя, время жизни которой не превышает нескольких дней. Также строим таблицу для всех товаров, в каждой ячейке которой есть частота со-визитов между каждым товаром.
2. При появлении нового клика забираем каждый элемент из истории кликов и обновляем коэффициенты по всем парам просмотренным товарам с новым товаром. Чем меньше времени прошло между просмотром «старого» и «нового» товара, тем выше можно сделать коэффициенты.
3. При создании списка рекомендаций для конкретного товара нужно выбрать такие товары, которые имеют с текущим наибольший ранг. Интуитивно этот тип рекомендаций можно назвать как «Пользователи, которые смотрели этот товар, также смотрели».