> For the complete documentation index, see [llms.txt](https://torchme.gitbook.io/t.me-persecond300k/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://torchme.gitbook.io/t.me-persecond300k/recsys/navigation/models/matrix-factorization.md). # Matrix factorization ## Отбор кандидатов: матричные факторизации и коллаборативные фильтрации Матричная факторизация остается одним из самых популярных методов для создания рекомендательных систем. И например за то время пока я работаю в ритейле матричные факторизации сильно выиграют у нейросетей в определенных сферах бизнеса за их простоту, скорость и без излишеств. В этой статье я бы хотел подробно сильно углубиться в матричные факторизации, коллаборативный сигнал, типы фитбека и разобраться почему же ALS все еще так хорош. *** ## RecSys 101 Представим что у нас есть некоторый магазин где есть 5\_000\_000 пользователей, 100\_000 товаров которые пользователи покупают регулярно. Мы можем создать матрицу взаимодействий 𝑅 размером 𝑚 × 𝑛, где каждый элемент $$r\_{ij}$$​ отражает взаимодействие пользователя 𝑖 с элементом 𝑗. Это взаимодействие может называется **feedback** и оно может быть: * Для товара, что его положили в корзину * Для музыки, что ее дослушали * Для статьи, что ее лайкнули * Для видео, что его посмотрели больше чем на половину * etc ### Explicit feedback **explicit feedback** - это такие действия, которые выражают явное отношения пользователя к товару.
{% hint style="warning" %} Как правило таких данных мало, но они намного качественнее {% endhint %} Так-же дизлайки могут не означать, что ему не подобный товар и категория товара, возможно ему не понравился конкретно этот товар или у него неприязнь к определенному автору, фильму. ### Implicit feedback **implicit feedback** - это любая другая информация, действия пользователя на сайте. Он не отражает явного отношения пользователя к товару, но является прокси-метрикой.
{% hint style="warning" %} Таких данных достаточно много, но они очень шумные {% endhint %} Покупки тоже не означают явного отношения, например пользователь вынужден покупать данный товар, это может быть подарок или разовый случай. ### Коллаборативная фильтрация это просто Теперь когда мы чуть больше знаем о данных, на которых можно обучить рекомендательные системы давайте разберемся, как же нам использовать эти данные, что бы мы могли рекомендовать другим пользователь **релевантные** товары?
Для примера возьмем 4 пользователя и 10 товаров с нашего ритейл магазина. * Кате понравился **1, 4, 8** и не понравился **5** товар * Пете понравился **1,**** ****3,**** ****8,** но не понравился **4 и 5** товар Эти пользователи очень похожи по своей истории взаимодействий, так почему бы нам не порекомендовать **3** товар из истории Пети? {% hint style="info" %} Идея **коллаборативной фильтрации** - хотим рекомендовать пользователю товары понравившиеся похожим на него пользователя. А в более общем случае это некоторое семейство моделей, которые основаны на похожестях взаимодействий по истории между пользователями и товарами. {% endhint %} ### 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 те элементы, которые получили наивысшие предсказанные рейтинги. ```python 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 )), что говорит о противоположных предпочтениях. * Маша и Вася не имеют значимой схожести с другими пользователями. #### Предсказанные рейтинги для Кати ```python # Функция для предсказания рейтинга на основе соседей 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](https://www.cs.umd.edu/~samir/498/Amazon-Recommendations.pdf). Основная идея заключается в том, что элементы, которые пользователь уже оценил, могут быть использованы для поиска наиболее похожих на них товаров, которые пользователь ещё не оценивал. Такой метод более масштабируем по сравнению с 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)** {% hint style="success" %} Чтобы эффективно и быстро предложить пользователю релевантные товары, нужно сузить круг возможных вариантов. {% endhint %} На этапе отбора кандидатов задача сводится к уменьшению числа потенциальных рекомендаций с миллионов до сотен. Ведь учитывать все комбинации пользователь-товар это огромное число, которое и не поместится в память и будет долго вычисляться. Так давайте возьмем Top-K товаров! Этот процесс может учитывать интересы пользователя, историю покупок и просмотров. * **Кандидаты** — это потенциальные элементы (товары, фильмы и т.д.), которые система рассматривает для рекомендации. * **Позитивы** — это элементы, с которыми пользователь уже взаимодействовал положительно в прошлом. Они используются для обучения модели, чтобы предсказать, что пользователь может захотеть в будущем. * Негативы - это элементы, с которыми пользователь не хотел бы взаимодействовать или уже негативно провзаимодействовал когда-либо. Они так-же используются для обучения. **Методы отбора кандидатов** {% hint style="info" %} Но как нам отобрать нужных кандидатов? Есть ли какие-то способы как понять что для конкретного пользователя товар x лучше чем товар y? {% endhint %} 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 *** ## Дополнительные материалы {% embed url="" %} {% embed url="" %} {% embed url="" %} {% embed url="" %} {% embed url="" %} {% embed url="" %} {% embed url="" %} {% embed url="" %}