Содержание


Рекомендательные системы

Часть 1. Введение в подходы и алгоритмы

Принципы работы рекомендательных механизмов Интернета

Comments

Серия контента:

Этот контент является частью # из серии # статей: Рекомендательные системы

Следите за выходом новых статей этой серии.

Этот контент является частью серии:Рекомендательные системы

Следите за выходом новых статей этой серии.

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

Базовые подходы

В большинстве рекомендательных систем применяется один из двух базовых подходов: коллаборативная фильтрация (collaborative filtering) и контентная фильтрация (content-based filtering). Существуют также и другие подходы (в том числе гибридные).

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

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

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

В таблице на рис. 1 строки соответствуют набору блогов, а столбцы — пользователям. Ячейка на пересечении строки блога и столбца пользователя содержит количество статей, прочитанных этим пользователем в этом блоге. Кластеризация пользователей на основе читательских привычек (например, с помощью алгоритма ближайшего соседа) позволяет выделить два кластера, каждый из которых содержит по два пользователя. Обратите внимание на схожесть читательских привычек у членов каждого кластера: Кластер 1 образуют участники с именами Марк и Элиза, каждый из которых прочел по несколько статей по тематике "Linux" и по тематике "Облачные вычисления". Кластер 2 образуют участники с именами Меган и Джилл, каждый из которых прочел по несколько статей по тематике "Java-технологии" и по тематике "Agile-технологии".

Рисунок 1. Простой пример коллаборативной фильтрации
Image shows simple example of                     collaborative filtering
Image shows simple example of collaborative filtering

Теперь вы сможете идентифицировать определенные различия в рамках каждого кластера и сформировать значимые рекомендации. В кластере 1 Марк прочел 10 статей из блога по продуктам с открытым исходным кодом, а Элиза не прочла ни одной такой статьи; Элиза прочла одну статью в блоге по Agile-технологиям, а Марк не прочел ни одной такой статьи. Таким образом, исходя из рис. 1, Элизе можно порекомендовать блог по продуктам с открытым исходным кодом. Для Марка невозможно сформировать никаких рекомендации, поскольку небольшая разница между ним и Элизой по количеству прочтений блога по Agile-технологиям с большой вероятностью будет отфильтрована. В кластере 2 Джилл прочла три статьи в блоге по продуктам с открытым исходным кодом, а Меган не прочла ни одной такой статьи; Меган прочла 3 статьи в блоге по Linux, а Джилл не прочла ни одной такой статьи. Таким образом, для участников кластера 2 можно сформировать следующие две рекомендации: участнику Джилл рекомендуется блог по Linux, а участнику Меган — блог по продуктам с открытым исходным кодом.

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

Рисунок 2. Сходства и различия, используемые в коллаборативной фильтрации
Image shows similarities and                     differences used in collaborative filtering

Хотя на рис. 2 показана упрощенная картина (которая к тому же страдает от разреженности данных по причине использования лишь двух образцов), такое представление весьма удобно.

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

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

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

Рисунок 3. Ранжированный список различий, используемый в контентной фильтрации
Image shows ranked differences used in                     content-based filtering
Image shows ranked differences used in content-based filtering

Диаграмму Венна (см. рис. 2 можно применить и в этом случае: если одна сторона — это пользователь Элиза, а другая — это ранжированный набор подобных блогов, то сходства игнорируются (поскольку Элиза уже прочла соответствующие блоги), а ранжированные различия создают возможности для выработки рекомендаций.

Гибридные подходы

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

Алгоритмы, используемые рекомендательными системами

Известный подход, примененный в конкурсе Netflix prize, наглядно демонстрирует, что в рекомендательных механизмах могут быть использованы самые различные алгоритмы. Получаемые результаты могут различаться в зависимости от проблемы, для решения которой спроектирован конкретный алгоритм, и от отношений, которые присутствуют в данных. Многие из этих алгоритмов пришли из области машинного обучения (которая, в свою очередь, представляет собой подобласть искусственного интеллекта), которая занимается алгоритмами для обучения, прогнозирования и принятия решений.

Корреляция Пирсона

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

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

Алгоритмы кластеризации

Алгоритмы кластеризации— это разновидность т. н. "спонтанного обучения" (unsupervised learning), позволяющая выявить структуру в рядах на первый взгляд случайных (или немаркированных) данных. В общем случае такой алгоритм базируется на выявлении сходства между элементами (например, между читателями блога) посредством вычисления их расстояния от других элементов в пространстве признаков (feature space) (признаком в пространстве признаков может, например, быть количество прочитанных статей в наборе блогов). Количество независимых признаков определяет размерность пространства признаков. Если элементы "близки" друг к другу, то их можно объединить в один кластер.

Существует множество алгоритмов кластеризации. Самым простым из них является алгоритм k-средних (k-means), который разделяет элементы на k кластеров. Первоначально элементы распределяются по этим кластерам в произвольном порядке. Затем для каждого кластера вычисляется центр масс (или просто центр) как функция его членов. После этого проверяется расстояние каждого члена кластера от центра этого кластера. Если по результатам этой проверки член оказывается ближе к другому кластеру, то он перемещается в этот кластер. После проверки всех расстояний для всех членов центры кластеров вычисляются заново. При достижении стабильного состояния (в процессе очередной итерации члены не перемещались) набор считается кластеризованным надлежащим образом, и алгоритм останавливается.

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

Существует множество других разновидностей кластеризации, в том числе теория адаптивного резонанса (Adaptive Resonance Theory), нечеткая кластеризация методом C-средних (Fuzzy C-means), вероятностная кластеризация с помощью EM-алгоритма (Expectation-Maximization) и т. д.

Другие алгоритмы

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

  • Байесовские сети доверия (Bayesian Belief Nets)— визуально могут быть представлены как ориентированный ациклический граф, ребра которого представляют связанные вероятности переменных.
  • Цепи Маркова (Markov chains)— основаны на таком же подходе, как у байесовских сетей доверия, но решают проблему выработки рекомендации как последовательную оптимизацию, а не как простое прогнозирование.
  • Классификация по методу Роккио (Rocchio classification) (основанная на векторной модели) — использует отзывы о релевантности элементов для повышения точности рекомендаций.

Проблемы рекомендательных систем

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

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

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

Что дальше

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


Ресурсы для скачивания


Похожие темы

  • Оригинал статьи: Recommender systems, Part 1: Introduction to approaches and algorithms.
  • Recommender Systems Wiki: этот сайт предлагает информацию о рекомендательных системах из широкого диапазона источников.
  • Recommendations @ LinkedIn: презентация по рекомендательному механизму LinkedIn (авторы: Abihishek Gupta и Adil Aijaz).
  • Hulu's Recommendation System: узнайте о том, как рекомендательный механизм от Hulu помогает владельцам контента продвигать свой контент на платформе Hulu.
  • Netflix Recommendations: Beyond the 5 stars: рекомендательный механизм Netflix, конкурс Netflix Prize и проблемы, возникшие в ходе этого конкурса.
  • Web-Scale User Modeling for Targeting: эта статья от компании Yahoo! описывает платформу моделирования пользователей с целью оптимизации подбора объявлений для пользователей в масштабе всего Интернета с помощью Hadoop-технологий.
  • A Survey of Collaborative Filtering Techniques: всеобъемлющий и весьма полезный обзор по рекомендательным системам и их проблемам, а также по методикам коллаборативной фильтрации.
  • AI Application Programming, 2nd edition (M. Tim Jones, Cengage Learning, 2005): книга по рекомендательным системам и по искусственному интеллекту в целом.
  • Patterns In and Across Aggregated Data — Is "Anonymous" Collaborative Filtering Really Safe?: (Kent Anderson): некоторые опасности и риски в сфере конфиденциальности при использовании коллаборативной фильтрации.
  • How Target Figured Out a Teen Girl Was Pregnant Before Her Father Did: проблемы рекомендательных систем и потенциальные риски при использовании коллаборативной фильтрации в торговле.

Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Open source, Web-архитектура
ArticleID=970009
ArticleTitle=Рекомендательные системы: Часть 1. Введение в подходы и алгоритмы
publish-date=04292014