Коллаборативная фильтрация: алгоритмы и применение

Введение

Алгоритм

Коллаборативная фильтрация (CF) — это техника, используемая системами рекомендаций. Коллаборативная фильтрация имеет два значения: узкое и более общее. В более современном, узком смысле, коллаборативная фильтрация — это метод автоматического прогнозирования (фильтрации) интересов пользователя путем сбора информации о предпочтениях или вкусах от множества пользователей (совместной работы). Основное предположение подхода коллаборативной фильтрации заключается в том, что если человек А имеет такое же мнение, как и человек Б по какому-либо вопросу, то А с большей вероятностью разделит мнение Б по другому вопросу, чем мнение случайно выбранного человека. Например, система рекомендаций на основе коллаборативной фильтрации для предпочтений в телевизионных программах может предсказывать, какое телевизионное шоу понравится пользователю, исходя из частичного списка его вкусов (понравившихся или не понравившихся передач). Эти прогнозы специфичны для пользователя, но используют информацию, полученную от многих пользователей. Это отличается от более простого подхода, который присваивает средний (неспецифический) балл каждому интересующему элементу, например, на основе количества голосов. В более общем смысле, коллаборативная фильтрация — это процесс фильтрации информации или выявления закономерностей с использованием техник, включающих сотрудничество между несколькими агентами, точками зрения, источниками данных и т. д. Алгоритм рекомендаций Top-N на основе пользователей использует векторную модель, основанную на сходстве, для определения k наиболее похожих пользователей для активного пользователя. После того, как k наиболее похожих пользователей найдены, их соответствующие матрицы «пользователь-элемент» агрегируются для определения набора элементов, которые следует рекомендовать. Популярным методом поиска похожих пользователей является локально-чувствительное хеширование, которое реализует механизм ближайшего соседа за линейное время. Преимущества этого подхода включают: объяснимость результатов, что является важным аспектом систем рекомендаций; простота создания и использования; легкость добавления новых данных; независимость содержания рекомендуемых элементов; хорошая масштабируемость при наличии большого количества сопоставимых элементов. Этот подход также имеет ряд недостатков. Его производительность снижается при разреженности данных, что часто встречается в веб-приложениях. Это ограничивает масштабируемость подхода и создает проблемы при работе с большими наборами данных. Хотя он может эффективно обрабатывать новых пользователей, поскольку опирается на структуру данных, добавление новых элементов становится более сложным, так как представление обычно основано на определенном векторном пространстве. Добавление новых элементов требует включения нового элемента и повторной вставки всех элементов в структуру.

Collaborative filtering (CF) is a technique used by recommender systems. Collaborative filtering has two senses, a narrow one and a more general one. In the newer, narrower sense, collaborative filtering is a method of making automatic predictions (filtering) about the interests of a user by collecting preferences or taste information from many users (collaborating). The underlying assumption of the collaborative filtering approach is that if a person A has the same opinion as a person B on an issue, A is more likely to have B's opinion on a different issue than that of a randomly chosen person. For example, a collaborative filtering recommendation system for preferences in television programming could make predictions about which television show a user should like given a partial list of that user's tastes (likes or dislikes). These predictions are specific to the user, but use information gleaned from many users. This differs from the simpler approach of giving an average (non specific) score for each item of interest, for example based on its number of votes. In the more general sense, collaborative filtering is the process of filtering for information or patterns using techniques involving collaboration among multiple agents, viewpoints, data sources, etc. The user based top N recommendation algorithm uses a similarity based vector model to identify the k most similar users to an active user. After the k most similar users are found, their corresponding user item matrices are aggregated to identify the set of items to be recommended. A popular method to find the similar users is the Locality sensitive hashing, which implements the nearest neighbor mechanism in linear time. The advantages with this approach include: the explainability of the results, which is an important aspect of recommendation systems; easy creation and use; easy facilitation of new data; content independence of the items being recommended; good scaling with co rated items. There are also several disadvantages with this approach. Its performance decreases when data gets sparse, which occurs frequently with web related items. This hinders the scalability of this approach and creates problems with large datasets. Although it can efficiently handle new users because it relies on a data structure, adding new items becomes more complicated since that representation usually relies on a specific vector space. Adding new items requires inclusion of the new item and the re insertion of all the elements in the structure.

На основе модели

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

Гибридный

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

Глубокое обучение

В последние годы было предложено множество методов нейронного и глубокого обучения. Некоторые обобщают традиционные алгоритмы матричной факторизации с помощью нелинейной нейронной архитектуры или используют новые типы моделей, такие как вариационные автоэнкодеры. Хотя глубокое обучение применяется в различных сценариях: с учетом контекста, последовательности, социальных тегов и т.д., его реальная эффективность в простом сценарии коллаборативной рекомендации вызывает вопросы. Систематический анализ публикаций, применяющих глубокое обучение или нейронные методы к задаче рекомендации top-k, опубликованных на ведущих конференциях (SIGIR, KDD, WWW, RecSys), показал, что в среднем менее 40% статей воспроизводимы, а на некоторых конференциях – и того меньше, всего 14%. В целом, исследование выявило 18 статей, из которых воспроизвести удалось лишь 7, а 6 из них уступали гораздо более старым и простым, но правильно настроенным базовым моделям. В статье также выделены потенциальные проблемы в современных научных исследованиях и призывается к улучшению научной практики в этой области. Аналогичные проблемы были отмечены и другими исследователями, в том числе в рекомендательных системах, учитывающих последовательность.

Контекстная совместная фильтрация

Многие системы рекомендаций просто игнорируют другую контекстную информацию, существующую наряду с оценками пользователей при предоставлении рекомендаций по товарам. Однако, благодаря повсеместной доступности контекстной информации, такой как время, местоположение, социальная информация и тип используемого устройства, для успешной системы рекомендаций становится важнее, чем когда-либо, предоставлять рекомендации, учитывающие контекст. По словам Чару Агравала, "системы рекомендаций, учитывающие контекст, адаптируют свои рекомендации к дополнительной информации, определяющей конкретную ситуацию, в которой они делаются. Эта дополнительная информация и называется контекстом". Чтобы воспользоваться преимуществами коллаборативной фильтрации, и особенно методов, основанных на соседях, подходы можно расширить от двумерной матрицы оценок до тензора более высокого порядка. Для этого необходимо найти наиболее похожих пользователей на целевого; можно извлекать и вычислять сходство срезов (например, матрицы "товар-время"), соответствующих каждому пользователю. В отличие от случая, не учитывающего контекст, где вычисляется сходство двух векторов оценок, в подходах, учитывающих контекст, сходство матриц оценок, соответствующих каждому пользователю, вычисляется с использованием коэффициентов корреляции Пирсона. Один из сценариев применения коллаборативной фильтрации – рекомендовать интересную или популярную информацию, по мнению сообщества. Типичный пример – статьи, появляющиеся на главной странице Reddit, поскольку они получают положительные оценки ("upvotes") от сообщества. По мере роста и разнообразия сообщества, продвигаемые статьи лучше отражают средние интересы его членов. Википедия – еще одно применение коллаборативной фильтрации. Волонтеры вносят вклад в энциклопедию, отсеивая ложные сведения от фактов. Другой аспект коллаборативных систем фильтрации – возможность генерировать более персонализированные рекомендации, анализируя информацию о предыдущей активности конкретного пользователя или историю других пользователей, чьи вкусы считаются схожими. Эти данные используются для создания профилей пользователей и помогают сайту рекомендовать контент индивидуально для каждого. Чем больше пользователь взаимодействует с системой, тем лучше становятся рекомендации, поскольку система получает данные для улучшения своей модели этого пользователя.

Many recommender systems simply ignore other contextual information existing alongside user's rating in providing item recommendation. However, by pervasive availability of contextual information such as time, location, social information, and type of the device that user is using, it is becoming more important than ever for a successful recommender system to provide a context sensitive recommendation. According to Charu Aggrawal, "Context sensitive recommender systems tailor their recommendations to additional information that defines the specific situation under which recommendations are made. This additional information is referred to as the context." In order to take advantage of collaborative filtering and particularly neighborhood based methods, approaches can be extended from a two dimensional rating matrix into a tensor of higher order. For this purpose, the approach is to find the most similar/like minded users to a target user; one can extract and compute similarity of slices (e. g. item time matrix) corresponding to each user. Unlike the context insensitive case for which similarity of two rating vectors are calculated, in the context aware approaches, the similarity of rating matrices corresponding to each user is calculated by using Pearson coefficients. One scenario of collaborative filtering application is to recommend interesting or popular information as judged by the community. As a typical example, stories appear in the front page of Reddit as they are "voted up" (rated positively) by the community. As the community becomes larger and more diverse, the promoted stories can better reflect the average interest of the community members. Wikipedia is another application of collaborative filtering. Volunteers contribute to the encyclopedia by filtering out facts from falsehoods. Another aspect of collaborative filtering systems is the ability to generate more personalized recommendations by analyzing information from the past activity of a specific user, or the history of other users deemed to be of similar taste to a given user. These resources are used as user profiling and helps the site recommend content on a user by user basis. The more a given user makes use of the system, the better the recommendations become, as the system gains data to improve its model of that user.

Проблемы

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

Небольшая распространенность данных

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

Масштабируемость

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

Синонимы

Синонимия – это тенденция, когда множество одинаковых или очень похожих товаров имеют разные названия или записи. Большинство систем рекомендаций не способны выявить эту скрытую взаимосвязь и, следовательно, рассматривают эти товары как разные. Например, казалось бы различные элементы "детский фильм" и "детская кинокартина" на самом деле относятся к одному и тому же товару. Фактически, степень вариативности в использовании описательных терминов оказывается больше, чем обычно предполагают. Распространенность синонимов снижает эффективность рекомендаций коллаборативной фильтрации. Тематическое моделирование (например, метод латентного распределения Дирихле) может решить эту проблему, группируя различные слова, относящиеся к одной теме.

Серые овцы

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

Шиллинговые атаки

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

Разнообразие и длинный хвост

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

Инновации

В результате конкурса Netflix были разработаны новые алгоритмы для коллаборативной фильтрации (КФ). Межсистемная коллаборативная фильтрация, объединяющая профили пользователей из нескольких систем рекомендаций в многозадачном режиме, что позволяет совместно использовать закономерности предпочтений между моделями. Устойчивая коллаборативная фильтрация, обеспечивающая стабильность рекомендаций при попытках манипулирования. Эта область исследований остается актуальной и до конца не решена.

Вспомогательная информация

Матрица пользовательских элементов является базовым фундаментом традиционных методов коллаборативной фильтрации и страдает от проблемы разреженности данных (т.е. проблемы холодного старта). Следовательно, помимо матрицы пользовательских элементов, исследователи стремятся собирать дополнительную вспомогательную информацию для повышения эффективности рекомендаций и разработки персонализированных рекомендательных систем. Обычно выделяют два основных типа вспомогательной информации: информация об атрибутах и информация о взаимодействиях. Информация об атрибутах описывает свойства пользователя или элемента. Например, атрибуты пользователя могут включать общий профиль (например, пол и возраст) и социальные связи (например, подписчики или друзья в социальных сетях); атрибуты элемента – это свойства, такие как категория, бренд или контент. Кроме того, информация о взаимодействиях относится к неявным данным, показывающим, как пользователи взаимодействуют с элементами. К широко используемой информации о взаимодействиях относятся теги, комментарии, отзывы и история просмотров и т.д. Вспомогательная информация играет значительную роль в различных аспектах. Явные социальные связи, как надежный показатель доверия или дружбы, часто используются при вычислении сходства для поиска пользователей, схожих по интересам с целевым пользователем. Информация о взаимодействиях – теги – рассматривается как третье измерение (в дополнение к пользователю и элементу) в продвинутых методах коллаборативной фильтрации для построения трехмерной тензорной структуры, используемой для поиска рекомендаций.