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

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

История

Идея использования коллективного поведения для предсказания предпочтений восходит к середине XX века. В 1950-х годах в психологии и социологии изучались механизмы «социального влияния» и «эффекта большинства». Однако практическое применение стало возможным только с развитием вычислительной техники и появлением цифровых платформ.

Одним из первых программных воплощений коллаборативной фильтрации стала система Tapestry, разработанная в 1992 году в исследовательском центре Xerox PARC. Она предназначалась для фильтрации электронной почты и позволяла пользователям вручную ставить пометки о важности писем, после чего система находила корреляции между оценками разных людей. Термин «collaborative filtering» впервые был введён именно в контексте Tapestry.

В 1994 году на конференции AAAI была представлена система GroupLens, созданная в Миннесотском университете. Она автоматизировала процесс сбора оценок и использовала статистические методы для предсказания рейтингов новостных статей. Этот проект стал основой для многих последующих разработок, включая рекомендательные системы Amazon, Netflix и YouTube.

В 2006 году компания Netflix объявила конкурс Netflix Prize с призовым фондом в 1 миллион долларов за улучшение точности собственного алгоритма коллаборативной фильтрации на 10 %. Победившая команда BellKor’s Pragmatic Chaos в 2009 году применила ансамбль из более чем 100 моделей, что значительно продвинуло теорию и практику метода.

Классификация

Методы коллаборативной фильтрации делятся на два основных класса: основанные на памяти (memory-based) и основанные на модели (model-based).

Методы, основанные на памяти

Эти методы работают непосредственно с матрицей взаимодействий «пользователь—объект» (например, таблица оценок от 1 до 5). Предсказание для конкретного пользователя строится путём поиска похожих на него пользователей или похожих на целевой объект.

• User-based (на основе пользователей): Для активного пользователя находятся k наиболее похожих пользователей по критерию корреляции (например, по коэффициенту Пирсона или косинусному сходству). Затем оценка для нового объекта вычисляется как взвешенное среднее оценок этих соседей. Недостаток — плохая масштабируемость при росте числа пользователей.
• Item-based (на основе объектов): Сначала вычисляется сходство между объектами (например, фильмами) на основе того, как их оценивали одни и те же пользователи. Затем для предсказания оценки активного пользователя по объекту X берутся объекты, которые он уже оценил, и их оценки взвешиваются по сходству с X. Этот подход применяется в Amazon и показал лучшую производительность при большом числе пользователей, так как матрица сходства объектов обновляется реже.

Методы, основанные на модели

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

• Матричная факторизация (Matrix Factorization): Матрица взаимодействий разлагается на две низкоранговые матрицы — матрицу скрытых признаков пользователей и матрицу скрытых признаков объектов. Каждый пользователь и объект представляются вектором в пространстве скрытых факторов (например, 10–200 размерностей). Прогноз оценки вычисляется как скалярное произведение соответствующих векторов. Наиболее известный алгоритм — SVD (Singular Value Decomposition) и его варианты (SVD++, FunkSVD).
• Латентные модели на основе вероятностных подходов: Например, латентное размещение Дирихле (LDA) или скрытые марковские модели, используемые для анализа последовательностей действий.
• Нейросетевые модели: Глубокие нейронные сети, в том числе автоэнкодеры и графовые нейронные сети (GNN), позволяют улавливать нелинейные зависимости. Например, модель Neural Collaborative Filtering (NCF) заменяет скалярное произведение на полносвязную сеть.

Устройство и характеристики

Матрица взаимодействий

Исходные данные представляют собой разрежённую матрицу R размером M×N, где M — число пользователей, N — число объектов. Элемент r_ij — это оценка i-го пользователя j-му объекту (если она есть). Разреженность (sparsity) — доля отсутствующих значений — может достигать 99 % и более в реальных системах (например, Netflix Prize). Высокая разреженность является ключевой проблемой, так как снижает точность поиска соседей.

Метрики сходства

Для user-based и item-based методов используются следующие меры:

• Косинусное сходство: cos(u, v) = (u·v) / (||u||·||v||). Не учитывает смещение в оценках (например, один пользователь ставит 4, другой — 2, но оба любят одни и те же фильмы).
• Корреляция Пирсона: Устраняет смещение, нормализуя оценки по среднему каждого пользователя.
• Скорректированное косинусное сходство (adjusted cosine): Используется в item-based, где вычитается средняя оценка пользователя по всем объектам.

Проблемы и ограничения

• Холодный старт (cold start): Для новых пользователей или новых объектов нет истории взаимодействий, поэтому коллаборативная фильтрация не может дать рекомендации. Решается гибридными методами (комбинация с контентной фильтрацией) или использованием демографических данных.
• Разреженность (sparsity): При очень малом числе общих оценок между пользователями сходство становится ненадёжным.
• Серый овёс (gray sheep): Пользователи с нетипичными вкусами, которые не имеют достаточного числа похожих соседей, получают плохие рекомендации.
• Популярность (popularity bias): Алгоритмы склонны рекомендовать популярные объекты, так как они имеют больше оценок, что снижает разнообразие.
• Масштабируемость: Вычисление сходства всех пар пользователей (O(M²)) или объектов (O(N²)) становится непрактичным при миллионах записей. Методы на основе модели (матричная факторизация) решают эту проблему.

Применение

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

• Электронная коммерция: Amazon использует item-based фильтрацию для рекомендаций «покупатели также купили». Система анализирует историю покупок и просмотров.
• Видео- и аудиостриминг: Netflix, YouTube, Spotify применяют комбинацию коллаборативной и контентной фильтрации. Например, Netflix Prize стимулировал развитие матричной факторизации.
• Социальные сети: Facebook и VK используют коллаборативную фильтрацию для предложения друзей, групп и новостей на основе активности подписчиков.
• Новостные агрегаторы: Google News и Яндекс.Новости персонализируют ленту, анализируя клики и время чтения.
• Образовательные платформы: Coursera и Khan Academy рекомендуют курсы на основе успеваемости и предпочтений других учащихся.

Примеры

Рекомендация фильмов

Допустим, есть три пользователя: Алиса, Боб и Чарли. Алиса и Боб высоко оценили «Звёздные войны» и «Властелин колец», а Чарли — только «Звёздные войны». Если Алиса поставила 5 фильму «Матрица», а Боб его не смотрел, то коллаборативная фильтрация (user-based) предскажет, что Боб также оценит «Матрицу» высоко, так как его вкус похож на вкус Алисы.

Netflix Prize

В 2006 году Netflix предоставил набор данных из 100 миллионов оценок (от 1 до 5) от 480 000 пользователей на 17 770 фильмов. Задача — предсказать оценки для тестового набора. Победивший алгоритм BellKor’s Pragmatic Chaos использовал ансамбль из 107 моделей, включая матричную факторизацию, рестриктивные машины Больцмана и линейные регрессии. Улучшение RMSE составило 10,06 % относительно базового алгоритма Cinematch.

Критика

• Отсутствие разнообразия: Из-за склонности к популярным объектам пользователи могут получать однотипные рекомендации, что снижает удовлетворённость.
• Манипуляции: Возможность накрутки оценок (например, ботами) для продвижения определённых товаров или контента.
• Эффект пузыря фильтров: Алгоритмы могут изолировать пользователя от информации, не соответствующей его текущим предпочтениям, что критикуется в контексте социальных сетей и новостных лент.
• Приватность: Для построения точных моделей требуется сбор подробных данных о поведении пользователей, что вызывает вопросы о конфиденциальности.

Источники

• Resnick, P., Iacovou, N., Suchak, M., Bergstrom, P., & Riedl, J. (1994). GroupLens: an open architecture for collaborative filtering of netnews. Proceedings of ACM CSCW.
• Sarwar, B., Karypis, G., Konstan, J., & Riedl, J. (2001). Item-based collaborative filtering recommendation algorithms. Proceedings of WWW.
• Koren, Y., Bell, R., & Volinsky, C. (2009). Matrix factorization techniques for recommender systems. Computer, 42(8).
• Su, X., & Khoshgoftaar, T. M. (2009). A survey of collaborative filtering techniques. Advances in Artificial Intelligence.
• Bell, R. M., & Koren, Y. (2007). Lessons from the Netflix prize challenge. ACM SIGKDD Explorations Newsletter.