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

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

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

М. Тим Джонс, инженер-консультант, Emulex

M. Тим Джонс (M. Tim Jones) является архитектором встраиваимого программного обеспечения и автором работ: Программирование Приложений под GNU/Linux, Программирование AI-приложений и Использование BSD-сокетов в различных языках программирования. Он имеет опыт разработки процессоров для геостационарных космических летательных аппаратов, а также разработки архитектуры встраиваемых систем и сетевых протоколов. Сейчас Тим работает инженером-консультантом в корпорации Эмулекс (Emulex Corp.) в г.Лонгмонт, Колорадо.



29.04.2014

Где можно встретить рекомендательную систему

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

LinkedIn— сайт бизнес-ориентированной социальной сети — предлагает пользователю рекомендации относительно людей, которых он, возможно, знает, рабочие места, которые могли бы его привлечь, группы, в которые он мог бы захотеть вступить, компании, которыми он мог бы заинтересоваться. Специализированная система коллаборативной фильтрации LinkedIn основана на технологии Apache Hadoop.

Amazon— популярный сайт электронной коммерции — использует рекомендации на основе контента. Когда посетитель выбирает для покупки какой-либо товар, Amazon на основе этого исходного товара рекомендует посетителю другие товары, приобретенные другими пользователями (с помощью матрицы покупки следующего товара на основе его схожести с предыдущей покупкой). Компания Amazon запатентовала этот подход под названием item-to-item collaborative filtering (коллаборативная фильтрация от элемента к элементу).

Hulu— веб-сайт потокового видео — использует рекомендательный механизм для распознавания контента, который мог бы представлять интерес для пользователей. Он также использует (в оффлайновом режиме) механизм Hadoop для масштабируемой обработки огромных объемов данных при выполнении т. н. "коллаборативной фильтрации на основе элементов" (item-based collaborative filtering). Подробные сведения об онлайновой и оффлайновой архитектуре Hulu под названием ItemCF находятся в открытом доступе.

Netflix— поставщик видеоконтента на условиях аренды и в виде потокового сервиса — является широкоизвестным примером в этой сфере. В 2006 г. компания Netflix объявила конкурс на совершенствование своей рекомендательной системы под названием Cinematch. В 2009 г. три группы разработчиков объединенными усилиями создали "ансамбль" из 107 рекомендательных алгоритмов, формирующий единый прогноз. Этот ансамбль сыграл ведущую роль в повышении точности прогнозирования, в результате чего именно эта объединенная группа и выиграла приз Netflix.

Кроме того, рекомендательные механизмы используются на таких сайтах, как Facebook, Twitter, Google, MySpace, Last.fm, Del.icio.us, Pandora, Goodreads, а также на вашем любимом сайте онлайновых новостей. Использование того или иного рекомендательного механизма становится стандартным элементом современного веб-представительства.

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

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

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

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

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

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

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

Рисунок 1. Простой пример коллаборативной фильтрации
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

Диаграмму Венна (см. рис. 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: проблемы рекомендательных систем и потенциальные риски при использовании коллаборативной фильтрации в торговле.
  • Раздел Open source на сайте developerWorks— обширный ассортимент справочной информации, инструментов и обновлений, который поможет применять технологии с открытым кодом в разработках и использовать их вместе с продуктами IBM.

Обсудить

  • Присоединяйтесь к сообществу developerWorks . Связывайтесь с другими пользователями developerWorks и знакомьтесь с ориентированными на разработчиков форумами, блогами, группами и вики-ресурсами.

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


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

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


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