Сегодня мы расскажем об одном из двух важнейших алгоритмов систем рекомендаций – совместной фильтрации, обсудим его основные моменты и приведем примеры практического применения, которые, как вы догадываетесь, вовсе не ограничивается интернет-магазинами.
Концепция совместной фильтрации
Совместная, или коллаборативная, фильтрация – это один из подходов к прогнозированию поведения (если быть точнее, выбора) пользователя в рамках систем рекомендации. В двух словах, алгоритм совместной фильтрации предполагает, что пользователь склонен сделать тот или иной выбор на основе его предыдущего поведения. Определение достаточно простое, но за ним кроется математический смысл, который и позволяет успешно применять алгоритм в системах рекомендаций.
Итак, в основе алгоритма – так называемая матрица полезности, в столбцах которой находятся предметы рекомендаций (items), а в строках – пользователи (users). Таким образом, каждая клетка отражает отношение пользователя U к предмету I. Эти отношения – рейтинги (причем не обязательно в прямом смысле – это может быть как проставленная пользователем оценка товара, так и, например, количество прослушиваний композиции) используются для определения похожести предметов на основании близости рейтингов, полученных этими предметами от одного и того же пользователя (в матрице полезности эти рейтинги представлены в строке — векторе пользователя).
Пользователи считаются похожими, если их векторы являются близкими согласно неким показателям математического расстояния (к примеру, расстояния Жаккарда). На следующем шаге рекомендация для пользователя составляется на основании предпочтений похожих на него пользователей.
Основные моменты алгоритма совместной фильтрации
Предлагаем немного подробнее остановиться на основных особенностях алгоритма.
-
Как мы уже писали выше, похожесть товаров и пользователей измеряется при помощи вычисления математического расстояния между векторами (столбцами и строками) товаров и пользователей соответственно. К примеру, пользователям YouTube, как известно, предлагается оценить тот или иной ролик, поставив ему «палец вверх» или «палец вниз». Матрица полезности в этом случае будет состоять, грубо говоря из нулей (ролик не нравится) и единиц (ролик нравится).
-
Нормализация и округление рейтингов необходимы для приведения данных к одному и тому же виду; к примеру, онлайн-магазин может иметь так называемые «хиты продаж» — товары, покупаемые чаще всего, и одновременно пятибалльную систему оценок каждого товара. Система же рекомендует товары пользователю на основании совокупности этих данных – для этого необходимо составить нормализованный и округленный рейтинг каждого товара. При этом существует проблема так называемого «холодного старта», когда пользователи-новички еще не приобрели или не оценили достаточного количества товаров, а новинки еще не успело купить достаточное количество пользователей.
-
Совместная фильтрация основана также на концепции двойственности рекомендаций. Так, система может давать ту или иную рекомендацию на основании похожести предметов или на основании похожести вкусов (рейтингов) пользователей. Для примера возьмем алгоритм работы сервиса last.fm, который рекомендует пользователям музыку на основе их предыдущих прослушиваний. Пользователь может просмотреть список рекомендованных ему исполнителей, причем система прямо указывает, на каком основании она рекомендует ту или иную группу («похоже на…»). С другой стороны, сервис имеет и элементы фильтрации по пользователям – например, при прослушивании радио рекомендаций, учитываются вкусы «друзей» и «соседей» (пользователей с похожими музыкальными предпочтениями).
- На практике матрица полезности часто имеет «прорехи» — далеко не все рейтинги проставлены, далеко не каждая клетка отношений заполнена, данные довольно разрежены, что только усугубляет проблему «холодного старта» в случае, если и сама система еще новая. Например, далеко не всегда фильмы, принадлежащие к одному и тому же жанру, были оценены или просмотрены одним и тем же пользователем. Точно так же, пользователи с похожими вкусами не обязательно просмотрят или высоко оценят один и тот же фильм. Один из способов справиться с этой проблемой – кластеризация предметов и/или пользователей. Для кластеризации используется все тот же показатель математического расстояния между векторами (столбцами) матрицы полезности.
Резюме
В сегодняшней статье мы продолжили обсуждение систем рекомендации и прогнозирования предпочтений пользователей, поделившись с читателями техническими подробностями и практическими примерами работы алгоритма совместной фильтрации. Мы непременно продолжим дискуссию в следующих статьях – не забывайте следить за обновлениями!
Автор: Елизавета Филиппова