Matrix factorization

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

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

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


RecSys 101

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

Мы можем создать матрицу взаимодействий 𝑅 размером 𝑚 × 𝑛, где каждый элемент rijr_{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)=iIuIv(ruirˉu)(rvirˉv)iIuIv(ruirˉu)2iIuIv(rvirˉv)2s(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}}

Где:

  • ruir_{ui} и rvir_{vi} — рейтинги пользователей u и v для элемента i,

  • rˉu\bar{r}{u} и rˉv \bar{r}{v} — средние рейтинги пользователей u и v,

  • IuIvI_u \cap I_v — множество элементов, которые оценили оба пользователя.

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

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

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

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

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

Где:

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

  • rvir_{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 более эффективно использует информацию о взаимодействиях пользователей с меньшим набором элементов.

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

Шаги:

  1. Построим матрицу взаимодействий (user-item).

  2. Рассчитаем схожесть между элементами (item-to-item).

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

  4. Выдадим рекомендации.

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?

  1. Эвристические подходы: Самые популярные товары или товары, популярные среди конкретных групп пользователей.

  2. Коллаборативные подходы: Методы вроде item2item или user2user для определения похожести.

  3. Контентные подходы: Поиск элементов, близких по эмбеддингам. Для ускорения могут использоваться такие структуры данных, как HNSW и FAISS.

  4. Учет бизнес-логики: Например, продвижение новых товаров или увеличение разнообразия.

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

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

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

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

  • Контекстуальная информация: Предпочтения пользователя могут меняться в зависимости от времени дня, дня недели и других факторов.

  • Признаки товаров: Важны такие атрибуты, как бренд, цена и другие характеристики товара.

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

  1. Предсказания базовых моделей (коллаборативные и контентные).

  2. Признаки пользователя: Пол, возраст, история взаимодействий.

  3. Признаки объекта: Цена, вес, жанр, характеристики взаимодействий.

  4. Агрегационные признаки: За 7, 14, 30, n дней

  5. Объединенные признаки: user-item, user-category, user-segment

  6. Контекстуальная информация: День недели, погода, местоположение.

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

  1. Бинарная классификация: Определение наличия положительного взаимодействия.

  2. Регрессия: Пример — предсказание времени просмотра видео для определения заинтересованности пользователя.

  3. Ранжирование: Подходы pairwise и listwise помогают модели правильно упорядочивать объекты для пользователя.

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

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

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

  • Реранкинг позволяет адаптировать финальные рекомендации к изменяющимся условиям в реальном времени.

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

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


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

SVD

ALS

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

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


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

user KNN

item KNN

TF-IDF iKNN

TIFU


Дополнительные материалы

Last updated