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

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

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

Описание[править | править исходный текст]

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

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

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

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

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

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

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

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

Типы коллаборативной фильтрации[править | править исходный текст]

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

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

Основанный на соседстве[править | править исходный текст]

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

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

Основанный на модели[править | править исходный текст]

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

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

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

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

Гибридный[править | править исходный текст]

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

Проблемы[править | править исходный текст]

Разреженность данных[править | править исходный текст]

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

Масштабируемость[править | править исходный текст]

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

Проблема холодного старта[править | править исходный текст]

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

Синонимия[править | править исходный текст]

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

Мошенничество[править | править исходный текст]

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

Разнообразие[править | править исходный текст]

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

Белые вороны[править | править исходный текст]

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

Применение в социальных сетях[править | править исходный текст]

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

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

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

Литература[править | править исходный текст]

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