Collaborative Filtering

Netflix Prize 2006: миллион долларов за улучшение алгоритма на 10%. Выиграли BellKor Pragmatic Chaos. Netflix не использовал алгоритм - слишком дорого внедрять. Сегодня: 80% просмотров Netflix приходит из рекомендаций. Amazon генерирует 35% выручки через фразу «Customers who bought this also bought...». За этой фразой стоит collaborative filtering - алгоритм, который вообще не знает, что такое «книга» или «фильм». Он знает только одно: кто что оценил.

• **Amazon** (item-based CF, Linden et al. 2003) обрабатывает миллиарды покупок, чтобы предложить «похожие товары» - предвычисленная матрица item-item обновляется ежедневно, 35% выручки
• **Netflix** использует user-based и item-based CF как компоненты гибридной системы, комбинируя с deep learning моделями - 80% просмотров из рекомендаций
• **Spotify** Discover Weekly - user-based CF на implicit feedback (время прослушивания), еженедельно 30 треков, MAU >400 миллионов
• **Last.fm** построил scrobble-based CF: анализирует историю прослушиваний миллионов пользователей для музыкальных рекомендаций без explicit ratings
• **YouTube** использует item-based CF как один из компонентов гибридной системы ранжирования - более 500 часов видео загружается каждую минуту

Предварительные знания

• Introduction to Recommender Systems

Amazon и рождение промышленного collaborative filtering

В 2003 году Greg Linden, Brent Smith и Jeremy York из Amazon опубликовали статью «Amazon.com Recommendations: Item-to-Item Collaborative Filtering». Они показали, что предвычисленная таблица item-item similarity позволяет делать рекомендации за O(1) - просто lookup по таблице. Это решило проблему масштаба: Amazon обслуживал миллионы пользователей, и user-based CF был слишком медленным. Подход стал стандартом индустрии на десятилетие. Патент US6266649B1 - «item-to-item collaborative filtering» - до сих пор принадлежит Amazon.

User-Based CF: похожие пользователи

Netflix Prize 2006: миллион долларов за улучшение алгоритма рекомендаций на 10%. Выиграли BellKor Pragmatic Chaos. Netflix не использовал алгоритм - слишком дорого внедрять. Сегодня: 80% просмотров Netflix приходит из рекомендаций. Цена этих 80% - не сложная математика. Это один вопрос: **кто смотрел то же самое?**

Алгоритм работает в три шага: 1. **Вычислить similarity** между целевым пользователем и всеми остальными 2. **Выбрать k ближайших соседей** (пользователей с максимальным сходством) 3. **Предсказать оценку** как взвешенное среднее оценок соседей Формула предсказания для пользователя **u** на товар **i**:

Почему используется **(r_vi - r_v_mean)**, а не просто **r_vi**? Потому что люди оценивают по-разному. Один щедрый пользователь ставит всем фильмам 4-5 звёзд. Другой строгий - 2-3. Если Боб поставил 4 (при среднем 4.5), это **ниже его нормы** - фильм ему не очень. Вычитание средней **нормализует** оценки: +0.5 означает «лучше обычного», -1.0 - «хуже обычного» для данного пользователя.

**Сложность user-based CF:** для каждого предсказания нужно вычислить сходство с **каждым** пользователем - это O(n) на предсказание, где n - число пользователей. Для Netflix с 500 миллионами пользователей это неприемлемо. Поэтому на практике: (1) предвычисляют матрицу сходства офлайн, (2) используют approximate nearest neighbors (ANN), или (3) переходят на item-based CF.

**Порог минимальных общих оценок** - частая ошибка начинающих. Если два пользователя оценили всего 1 общий фильм одинаково, их Pearson correlation = 1.0 (идеальная). Но это **статистически бессмысленно**. Устанавливать минимум общих оценок (обычно 5-20) для надёжного сходства.

Item-Based CF: похожие товары

В 2003 году инженеры Amazon опубликовали статью, изменившую индустрию: **«Item-to-Item Collaborative Filtering»** (Linden et al.). Вместо поиска похожих пользователей - поиск **похожих товаров**. Если люди, купившие книгу A, также покупали книгу B, эти книги похожи. Знаменитая фраза «Customers who bought this also bought...» - это item-based CF. Именно этот алгоритм добавил 35% к годовой выручке Amazon.

Ключевое преимущество: **стабильность**. Вкусы пользователей дрейфуют - сегодня человек смотрит боевики, через год - документалки. Но связь между товарами стабильна: «Властелин Колец» и «Хоббит» всегда будут похожи. Матрица item-item similarity вычисляется один раз и обновляется редко. А ещё товаров обычно **меньше**, чем пользователей - матрица компактнее.

**Adjusted cosine vs обычный cosine для item-based CF.** Обычный cosine сравнивает столбцы матрицы напрямую. Проблема: пользователь, ставящий всем 5, «завышает» сходство для любой пары товаров. **Adjusted cosine** вычитает среднюю оценку пользователя перед расчётом - это аналог Pearson correlation, но для item-based подхода. Исследования показывают, что adjusted cosine значительно точнее.

**Предвычисление - ключ к масштабированию.** В production item-item similarity matrix вычисляется офлайн (batch job раз в сутки). При запросе пользователя система просто смотрит: какие товары оценены -> для каждого находит k похожих -> ранжирует. Онлайн-часть - O(m*k), где m - число оценок пользователя, k - число соседей. Для 100 оценок и k=20 это 2000 lookups - миллисекунды.

Метрики сходства: cosine, Pearson, Jaccard

Collaborative filtering упирается в один вопрос: **как измерить похожесть?** Два пользователя - два вектора оценок. Насколько они «близки»? Ответ зависит от выбранной метрики, и этот выбор **критически влияет** на качество рекомендаций. Три основные метрики: **cosine similarity**, **Pearson correlation**, **Jaccard index** - каждая имеет свою нишу.

**Когда какую метрику?** Практическое правило: - **Explicit ratings** (1-5 звёзд): **Pearson** для user-based, **adjusted cosine** для item-based. Причина - нормализация убирает эффект «щедрых» и «строгих» оценщиков. - **Бинарные данные** (купил / не купил): **Jaccard**. Здесь нет «масштаба» - только множества. - **Implicit feedback** (время просмотра, клики): **Cosine** на нормализованных данных. Pearson плохо работает с неотрицательными данными.

**Pearson undefined при нулевой дисперсии.** Если пользователь поставил всем фильмам одну и ту же оценку (например, всем 5), вектор после вычитания средней = [0, 0, 0, ...]. Pearson correlation даст деление на ноль. Обрабатывать этот edge case - возвращать 0 (нет информации о предпочтениях).

**Совет для production:** не выбирать одну метрику заранее - протестировать все на A/B тесте. Для MovieLens Pearson обычно побеждает, для Amazon (implicit) - cosine. Единственный надёжный способ - эксперимент на реальных данных.

Выбор соседства: параметр k

Сходство со всеми пользователями вычислено. Теперь вопрос: **сколько соседей (k) использовать для предсказания?** Это гиперпараметр, и его выбор - баланс между шумом и сигналом. Слишком мало соседей - предсказание неустойчиво. Слишком много - в «соседи» попадают далёкие пользователи с нерелевантными вкусами.

**Weighted average** - ключевой механизм. Не все соседи равнозначны: ближайший сосед (similarity = 0.95) должен влиять сильнее, чем далёкий (similarity = 0.3). Поэтому оценки взвешиваются по сходству. Это автоматически уменьшает влияние далёких соседей - даже при большом k.

**Threshold-based neighborhood** - альтернатива фиксированному k. Вместо «взять k ближайших» - брать «всех с similarity > threshold» (например, > 0.5). Это адаптивно: для популярного пользователя может быть 100 соседей, для нишевого - 3. Комбинированный подход: threshold > 0.3 И k <= 50.

**Ошибка: оценивать k на тех же данных, на которых обучали.** Это даст заниженную ошибку и завышенный оптимальный k. Всегда использовать hold-out set или cross-validation. На MovieLens-1M оптимальный k обычно в диапазоне 20-50 для user-based и 10-30 для item-based CF.

Ключевые идеи

• **User-based CF** находит похожих пользователей и заимствует их оценки. Netflix Prize 2006 и 80% просмотров Netflix - всё строится на этой идее
• **Item-based CF** сравнивает товары по паттернам оценок. Стабильнее user-based (товары не меняют «вкусы»), масштабируется лучше, предвычисляется offline. Amazon Patent 2003 - Greg Linden et al.
• **Метрики сходства**: Pearson для explicit ratings (нормализует шкалу), Jaccard для бинарных данных (купил/не купил), adjusted cosine для item-based CF. Выбор метрики критичен - проверять A/B тестом
• **Параметр k** - bias-variance tradeoff: малый k = шум, большой k = потеря персонализации. Оптимум находится через cross-validation, обычно 10-50
• **Предвычисление item-item матрицы** - ключ к production-масштабу: 2000 lookups вместо O(n*m) в real-time

Связанные темы

Collaborative filtering - фундамент, на котором строятся продвинутые методы:

• Введение в рекомендательные системы — Обзор content-based, collaborative и гибридных подходов
• Matrix Factorization — SVD и ALS решают проблему разреженности CF, извлекая latent factors из матрицы оценок

Вопросы для размышления

• User-based CF и item-based CF дают разные рекомендации. В каких сценариях один подход лучше другого? Думать о соотношении пользователей и товаров на разных платформах.
• Pearson correlation = 1.0 между двумя пользователями, оценившими только 2 общих фильма. Стоит ли доверять этому сходству? Какой минимальный порог общих оценок установить?
• Если проектировать collaborative filtering для платформы, где 99% данных - implicit (клики, просмотры) и только 1% - explicit (оценки), какую стратегию выбрать?

Связанные уроки

• rec-01 — Обзор content-based и collaborative подходов перед погружением
• rec-03 — Matrix Factorization решает проблему разреженности CF через latent factors
• ml-14-knn — kNN - та же механика ближайших соседей, но для классификации
• ml-19-pca — PCA и SVD - математическая основа для matrix factorization CF
• prob-04-bayes — Байесовский update - альтернативный взгляд на предсказание оценок
• aie-09-embeddings — Neural CF использует embeddings вместо similarity матриц
• la-15-svd