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

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

Коллаборативная фильтрация, совместная фильтрация (англ. collaborative filtering) — это один из методов построения прогнозов (рекомендаций) в рекомендательных системах, использующий известные предпочтения (оценки) группы пользователей для прогнозирования неизвестных предпочтений другого пользователя. Его основное допущение состоит в следующем: те, кто одинаково оценивал какие-либо предметы в прошлом, склонны давать похожие оценки другим предметам и в будущем. Например, с помощью коллаборативной фильтрации музыкальное приложение способно прогнозировать, какая музыка понравится пользователю, имея неполный список его предпочтений (симпатий и антипатий). Прогнозы составляются индивидуально для каждого пользователя, хотя используемая информация собрана от многих участников. Тем самым коллаборативная фильтрация отличается от более простого подхода, дающего усреднённую оценку для каждого объекта интереса, к примеру, базирующуюся на количестве поданных за него голосов. Исследования в данной области активно ведутся и в наше время, что также обуславливается и наличием нерешённых проблем в коллаборативной фильтрации.

Описание

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

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

1. Находят тех, кто разделяет оценочные суждения «активного» (прогнозируемого) пользователя.
2. Используют оценки сходно мыслящих людей, найденных на первом шаге, для вычисления прогноза.

Алгоритм, описанный выше, построен относительно пользователей системы.

Существует и альтернативный алгоритм, изобретённый Amazon, построенный относительно предметов (продуктов) в системе. Этот алгоритм включает в себя следующие шаги:

1. Строим матрицу, определяющую отношения между парами предметов, для нахождения похожих предметов.
2. Используя построенную матрицу и информацию о пользователе, строим прогнозы его оценок.

Для примера, можно посмотреть семейство алгоритмов Slope One

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

Типы коллаборативной фильтрации

Типы коллаборативной фильтрации

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

Основанный на соседстве

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

1. Присвоить вес каждому пользователю с учётом схожести его оценок и активного пользователя.
2. Выбрать несколько пользователей, которые имеют максимальный вес, то есть максимально похожи на активного пользователя. Данная группа пользователей и называется соседями.
3. Высчитать предсказание оценок активного пользователя для неоценённых им предметов с учётом весов и оценок соседей.

Основанный на модели

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

Этот подход является более комплексным и даёт более точные прогнозы, так как помогает раскрыть латентные факторы, объясняющие наблюдаемые оценки.

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

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

Гибридный

Данный подход объединяет в себе подход основанный на соседстве и основанный на модели. Гибридный подход является самым распространённым при разработке рекомендательных систем для коммерческих сайтов, так как он помогает преодолеть ограничения изначального оригинального подхода (основанного на соседстве) и улучшить качество предсказаний. Этот подход также позволяет преодолеть проблему разреженности данных и потери информации. Однако данный подход сложен и дорог в реализации и применении.

Проблемы

Разреженность данных

Как правило, большинство коммерческих рекомендательных систем основано на большом количестве данных (товаров), в то время как большинство пользователей не ставит оценки товарам. В результате этого матрица «предмет-пользователь» получается очень большой и разреженной, что представляет проблемы при вычислении рекомендаций. Эта проблема особенно остра для новых, только что появившихся систем. Также разреженность данных усиливает проблему холодного старта.

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

С увеличением количества пользователей в системе, появляется проблема масштабируемости. Например, имея 10 миллионов покупателей $O(M)$ и миллион предметов $O(N)$, алгоритм коллаборативной фильтрации со сложностью равной $O(MN)$ уже слишком сложен для расчётов. Также, многие системы должны моментально реагировать на онлайн запросы от всех пользователей, независимо от истории их покупок и оценок, что требует ещё большей масштабируемости.

Проблема холодного старта

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

Синонимия

Синонимией называется тенденция похожих и одинаковых предметов иметь разные имена. Большинство рекомендательных систем не способны обнаружить эти скрытые связи и поэтому относятся к этим предметам как к разным. Например, «фильмы для детей» и «детский фильм» относятся к одному жанру, но система воспринимает их как разные.

Мошенничество

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

Разнообразие

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

Белые вороны

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

Применение в социальных сетях

Коллаборативная фильтрация широко используется в коммерческих сервисах и социальных сетях. Первый сценарий использования это создание рекомендации относительно интересной и популярной информации на основе учёта «голосов» сообщества. Такие сервисы, как Reddit и Digg — это типичные примеры систем, использующих алгоритмы коллаборативной фильтрации.

Другая сфера использования заключается в создании персонализированных рекомендаций для пользователя, на основе его предыдущей активности и данных о предпочтениях других, схожих с ним пользователей. Данный способ реализации можно найти на таких сайтах, как YouTube, Last.fm и Amazon, а также в таких геолокационных сервисах, как Gvidi и Foursquare.

См. также

• Cold start problem
• Collaborative search engine
• Collaborative model
• Reputation system

• Метод k ближайших соседей
• Социальный граф
• Рекомендательные системы
• Коллективный разум

Литература

• Fleder D., Hosanagar K. Blockbuster Culture's Next Rise or Fall: The Impact of Recommender Systems on Sales Diversity (англ.) // Management Science, Vol. 55, No. 5, May 2009, pp. 697—712 : журнал. — 2009. — P. 1—49.

• Xiaoyuan Su and Taghi M. Khoshgoftaar. A Survey of Collaborative Filtering Techniques (англ.) // Hindawi Publishing Corporation, Advances in Artificial Intelligence archive, USA : журнал. — 2009. — P. 1—19.

• Yehuda Koren. Factor in the Neighbors: Scalable and Accurate Collaborative Filtering (англ.) // Yahoo! Research, Haifa : журнал. — 2009. — P. 1—11. Архивировано 23 октября 2010 года.

• Linden G., Smith B., and York J. Item-to-Item Collaborative Filtering (англ.) // IEEE Internet Computing, Los Alamitos, CA USA : журнал. — 2003. — P. 76—80.

• Sarwar B., Karypis G., Konstan J., and Riedl J. Item-Based Collaborative Filtering Recommendation Algorithms (англ.) // University of Minnesota, Minneapolis : Материалы конф. / WWW10, Hong Kong, May 1—5, 2001. — 2001. — P. 285—295.

• Melville P.,Mooney R., Nagarajan R. Content-Boosted Collaborative Filtering for Improved Recommendations (англ.) // University of Texas, USA : Материалы конф. / AAAI-02, Austin, TX, USA, 2002. — 2002. — P. 187—192.

• Zan Huang, Xin Li, Hsinchun Chen. Link Prediction Approach to Collaborative Filtering (англ.) // University of Arizona, USA : Материалы конф. / JCDL’05, Denver, Colorado, USA, June 7—11, 2005. — 2005. Архивировано 25 декабря 2012 года.

• Понизовкин Д.М. Построение оптимального графа связей в системах коллаборативной фильтрации (рус.) // «Программные системы: теория и приложения» : журнал. — 2011. — № 4(8). — С. 107—114. — ISSN 2079-3316.

• Sammut C., Webb J. (Eds.). Encyclopedia of Machine Learning. — NY, USA: IBM T. J.Watson Research Center, 2010. — Т. 1. — С. 829—838. — 1031 с. — ISBN 978-0-387-30768-8.