Matrix factorization

Отбор кандидатов: матричные факторизации и коллаборативные фильтрации

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

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

RecSys 101

Представим что у нас есть некоторый магазин где есть 5_000_000 пользователей, 100_000 товаров которые пользователи покупают регулярно.

Мы можем создать матрицу взаимодействий 𝑅 размером 𝑚 × 𝑛, где каждый элемент $r_{ij}$ отражает взаимодействие пользователя 𝑖 с элементом 𝑗.

Это взаимодействие может называется feedback и оно может быть:

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

Explicit feedback

explicit feedback - это такие действия, которые выражают явное отношения пользователя к товару.

Как правило таких данных мало, но они намного качественнее

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

Implicit feedback

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

Таких данных достаточно много, но они очень шумные

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

Коллаборативная фильтрация это просто

Теперь когда мы чуть больше знаем о данных, на которых можно обучить рекомендательные системы давайте разберемся, как же нам использовать эти данные, что бы мы могли рекомендовать другим пользователь релевантные товары?

Для примера возьмем 4 пользователя и 10 товаров с нашего ритейл магазина.

Кате понравился 1, 4, 8 и не понравился 5 товар
Пете понравился 1, 3, 8, но не понравился 4 и 5 товар

Эти пользователи очень похожи по своей истории взаимодействий, так почему бы нам не порекомендовать 3 товар из истории Пети?

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

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

User2User

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

Такой пример мы уже разобрали, но давайте разберем поподробнее как это работает:

Шаг 1: Рассчитать меру схожести между пользователями

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

Формула коэффициента Пирсона для двух пользователей u и v:

s(u, v) = \frac{\sum_{i \in I_{u} \cap I_{v}} (r_{ui} - \bar{r}_{u})(r_{vi} - \bar{r}_{v})}{\sqrt{\sum_{i \in I_{u} \cap I_{v}} (r_{ui} - \bar{r}_{u})^2} \sqrt{\sum_{i \in I_{u} \cap I_{v}} (r_{vi} - \bar{r}_{v})^2}}

Где:

$r_{ui}$ и $r_{vi}$ — рейтинги пользователей u и v для элемента i,
$\bar{r}{u}$ и $\bar{r}{v}$ — средние рейтинги пользователей u и v,
$I_u \cap I_v$ — множество элементов, которые оценили оба пользователя.

Шаг 2: Определение соседей для пользователя

Используем расчетные меры схожести, чтобы выбрать соседей для пользователя u. Для этого выберем тех пользователей, у которых значение схожести $s(u, v)$ выше некоторого порогового значения $\alpha$ .

Шаг 3: Оценка рейтинга для непросмотренных элементов

Теперь, когда у нас есть схожие пользователи (соседи), мы можем предсказать рейтинг для элементов, которые пользователь (u) не оценивал, на основе рейтингов соседей:

\hat{r}_{ui} = \frac{\sum_{v \in N(u)} s(u, v) r_{vi}}{\sum_{v \in N(u)} |s(u, v)|}

Где:

$\hat{r}_{ui}$ — предсказанный рейтинг для элемента i пользователем u,
$r_{vi}$ — реальный рейтинг элемента i соседом v.

Шаг 4: Рекомендация элементов

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

import numpy as np

# Функция для расчета меры схожести Пирсона
def pearson_similarity(user_ratings, user1, user2):
    common_items = np.intersect1d(user_ratings.columns[user_ratings.loc[user1] != 0], 
                                  user_ratings.columns[user_ratings.loc[user2] != 0])
    
    if len(common_items) == 0:
        return 0
    
    r1 = user_ratings.loc[user1, common_items]
    r2 = user_ratings.loc[user2, common_items]
    
    mean_r1 = r1.mean()
    mean_r2 = r2.mean()
    
    numerator = np.sum((r1 - mean_r1) * (r2 - mean_r2))
    denominator = np.sqrt(np.sum((r1 - mean_r1) ** 2)) * np.sqrt(np.sum((r2 - mean_r2) ** 2))
    
    return numerator / denominator if denominator != 0 else 0

# Вычислим меру схожести для каждого пользователя по отношению к другим
users = df.index
similarities = pd.DataFrame(np.zeros((len(users), len(users))), index=users, columns=users)

for user1 in users:
    for user2 in users:
        if user1 != user2:
            similarities.loc[user1, user2] = pearson_similarity(df, user1, user2)

# Отображение матрицы схожести между пользователями
tools.display_dataframe_to_user(name="User Similarity Matrix", dataframe=similarities)

similarities


#          Петя  Маша  Вася     Катя
# Петя  0.00000   0.0   0.0  0.57735
# Маша  0.00000   0.0   0.0  0.00000
# Вася  0.00000   0.0   0.0 -0.50000
# Катя  0.57735   0.0  -0.5  0.00000

Матрица схожести пользователей (результаты)

Катя наиболее схожа с Петей (схожесть ( s(Катя, Петя) = 0.577 )).
У Кати и Васи отрицательная схожесть (( s(Катя, Вася) = -0.5 )), что говорит о противоположных предпочтениях.
Маша и Вася не имеют значимой схожести с другими пользователями.

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

# Функция для предсказания рейтинга на основе соседей
def predict_rating(user_ratings, similarities, user, item):
    neighbors = similarities.loc[user].nlargest(2).index  # выбираем двух самых похожих соседей
    
    numerator = 0
    denominator = 0
    
    for neighbor in neighbors:
        rating_by_neighbor = user_ratings.loc[neighbor, item]
        if rating_by_neighbor != 0:  # Если сосед оценил этот элемент
            similarity = similarities.loc[user, neighbor]
            numerator += similarity * rating_by_neighbor
            denominator += abs(similarity)
    
    return numerator / denominator if denominator != 0 else 0

# Найдем для Кати предсказания по всем непросмотренным элементам
unrated_items = df.columns[df.loc['Катя'] == 0]
predicted_ratings = {}

for item in unrated_items:
    predicted_ratings[item] = predict_rating(df, similarities, 'Катя', item)

# Отображаем предсказанные рейтинги для Кати
predicted_ratings

# {'Item 2': 0, 'Item 3': 1.0, 'Item 6': 0, 'Item 7': 0, 'Item 9': 0}

Item 3: 1.0 (высокая вероятность того, что Кате понравится этот элемент)
Остальные элементы получили предсказанный рейтинг 0.

Итог

На основе алгоритма user-to-user рекомендаций можно рекомендовать Кате Item 3, так как этот элемент получил наивысший предсказанный рейтинг.

Item2Item

Item-to-Item коллаборативная фильтрация — это подход, который предлагает рекомендации на основе схожести между элементами, а не пользователями.

Item-to-Item — это подход к коллаборативной фильтрации, который основан на нахождении схожести между элементами (товарами) для рекомендаций, вместо расчета схожести между пользователями. Этот метод получил широкое распространение благодаря его успешной реализации в системах рекомендаций Amazon.

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

Почему Item2Item эффективен?

Масштабируемость: User2User плохо масштабируется с увеличением числа пользователей, в то время как Item2Item более эффективно использует информацию о взаимодействиях пользователей с меньшим набором элементов.
Решение проблемы холодного старта: Благодаря агрегации пользовательских действий можно лучше обрабатывать новые элементы и улучшить рекомендации для новых пользователей.

Шаги:

Построим матрицу взаимодействий (user-item).
Рассчитаем схожесть между элементами (item-to-item).
Предскажем рейтинги для элементов, которые пользователь еще не оценил.
Выдадим рекомендации.

import pandas as pd
import numpy as np

# Шаг 1: Создаем матрицу взаимодействий user-item
data = {
    'Item 1':  [1, 0, -1, 1],
    'Item 2':  [0, 1, 0, 0],
    'Item 3':  [1, 0, -1, 0],
    'Item 4':  [-1, -1, 0, 1],
    'Item 5':  [-1, 0, -1, -1],
    'Item 6':  [0, 0, 0, 0],
    'Item 7':  [0, 0, 1, 0],
    'Item 8':  [1, 0, 0, 1],
    'Item 9':  [0, 0, 0, 0],
    'Item 10': [0, 0, 1, -1]
}

df = pd.DataFrame(data, index=['Петя', 'Маша', 'Вася', 'Катя'])

# Шаг 2: Функция для расчета меры схожести Пирсона между элементами
def pearson_similarity_items(user_ratings, item1, item2):
    common_users = np.intersect1d(user_ratings.index[user_ratings[item1] != 0], 
                                  user_ratings.index[user_ratings[item2] != 0])
    
    if len(common_users) == 0:
        return 0
    
    r1 = user_ratings.loc[common_users, item1]
    r2 = user_ratings.loc[common_users, item2]
    
    mean_r1 = r1.mean()
    mean_r2 = r2.mean()
    
    numerator = np.sum((r1 - mean_r1) * (r2 - mean_r2))
    denominator = np.sqrt(np.sum((r1 - mean_r1) ** 2)) * np.sqrt(np.sum((r2 - mean_r2) ** 2))
    
    return numerator / denominator if denominator != 0 else 0

# Шаг 3: Вычисляем матрицу схожести для всех пар элементов
items = df.columns
item_similarities = pd.DataFrame(np.zeros((len(items), len(items))), index=items, columns=items)

for item1 in items:
    for item2 in items:
        if item1 != item2:
            item_similarities.loc[item1, item2] = pearson_similarity_items(df, item1, item2)

print("Матрица схожести элементов:")
print(item_similarities)

# Матрица схожести элементов:
#          Item 1  Item 2  Item 3  Item 4  Item 5  Item 6  Item 7  Item 8  Item 9  Item 10
# Item 1      0.0     0.0     1.0     0.0     0.0     0.0     0.0     0.0     0.0     -1.0
# Item 2      0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0      0.0
# Item 3      1.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0      0.0
# Item 4      0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0      0.0
# Item 5      0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0      0.0
# Item 6      0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0      0.0
# Item 7      0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0      0.0
# Item 8      0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0      0.0
# Item 9      0.0     0.0     


# Шаг 4: Функция для предсказания рейтинга на основе item-item коллаборативной фильтрации
def predict_rating_item_based(user_ratings, item_similarities, user, item):
    rated_items = user_ratings.columns[user_ratings.loc[user] != 0]  # элементы, которые пользователь уже оценил
    
    numerator = 0
    denominator = 0
    
    for rated_item in rated_items:
        rating_by_user = user_ratings.loc[user, rated_item]
        similarity = item_similarities.loc[item, rated_item]
        numerator += similarity * rating_by_user
        denominator += abs(similarity)
    
    return numerator / denominator if denominator != 0 else 0

# Шаг 5: Предсказания для пользователя (например, для Кати)
user = 'Катя'
unrated_items = df.columns[df.loc[user] == 0]
predicted_ratings_item_based = {}

for item in unrated_items:
    predicted_ratings_item_based[item] = predict_rating_item_based(df, item_similarities, user, item)

print(f"\nПредсказанные рейтинги для {user}:")
for item, rating in predicted_ratings_item_based.items():
    print(f"{item}: {rating:.2f}")

# Теперь на основе этих предсказаний можно рекомендовать пользователю элементы с наивысшими предсказанными оценками.
# Предсказанные рейтинги для Катя:
# Item 2: 0.00
# Item 3: 1.00
# Item 6: 0.00
# Item 7: 0.00
# Item 9: 0.00

Особенности коллабортивной фильтрации

Холодный старт - коллаборативная фильтрация плохо работает с новыми пользователями и товарами из-за недостатка данных о их взаимодействиях. Это затрудняет создание точных рекомендаций.
Feedback loop - рекомендации основаны на предыдущих действиях пользователя, что может привести к повторению одних и тех же типов контента. Это замыкает пользователя в ограниченном круге интересов.
Feature engine - методы коллаборативной фильтрации не требуют дополнительных сведений о пользователях или товарах. Рекомендации строятся исключительно на основе их взаимодействий.

Как работают рекомендации под капотом?

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

База документов (Document Pool)

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

Отбор кандидатов (Candidate Generation)

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

На этапе отбора кандидатов задача сводится к уменьшению числа потенциальных рекомендаций с миллионов до сотен. Ведь учитывать все комбинации пользователь-товар это огромное число, которое и не поместится в память и будет долго вычисляться. Так давайте возьмем Top-K товаров!

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

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

Методы отбора кандидатов

Но как нам отобрать нужных кандидатов? Есть ли какие-то способы как понять что для конкретного пользователя товар x лучше чем товар y?

Эвристические подходы: Самые популярные товары или товары, популярные среди конкретных групп пользователей.
Коллаборативные подходы: Методы вроде item2item или user2user для определения похожести.
Контентные подходы: Поиск элементов, близких по эмбеддингам. Для ускорения могут использоваться такие структуры данных, как HNSW и FAISS.
Учет бизнес-логики: Например, продвижение новых товаров или увеличение разнообразия.

Ранжирование (Ranking)

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

Для ранжирования используется комбинированная модель, включающая:

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

На практике чаще всего используют ранжирующие модели, которые комбинируют различные признаки:

Предсказания базовых моделей (коллаборативные и контентные).
Признаки пользователя: Пол, возраст, история взаимодействий.
Признаки объекта: Цена, вес, жанр, характеристики взаимодействий.
Агрегационные признаки: За 7, 14, 30, n дней
Объединенные признаки: user-item, user-category, user-segment
Контекстуальная информация: День недели, погода, местоположение.

Задачи, на которые можно обучить модель:

Бинарная классификация: Определение наличия положительного взаимодействия.
Регрессия: Пример — предсказание времени просмотра видео для определения заинтересованности пользователя.
Ранжирование: Подходы pairwise и listwise помогают модели правильно упорядочивать объекты для пользователя.

Реранкинг (Re-ranking)

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

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

Финальная рекомендация

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

Матричная факторизация

SVD

ALS

Alternative Least Squares (ALS) — это метод матричной факторизации, который достаточно часто применяется в рекомендательных системах.

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