к.т.н., доц. Ефромеева Е.В., Ефромеев Н.М.

Московский государственный технологический университет «СТАНКИН»

Обзор техник коллаборативной фильтрации

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

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

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

На данный момент существует множество различных алгоритмов КФ, и применяются они прежде всего в электронной торговле (интернет-магазин Amazon.com заявляет, что около 35% продаж происходят в результате рекомендаций пользователям товаров, которые им должны понравиться).

Главное предположение КФ в том, что если пользователь х и пользователь у оценивают n элементов одинаково или показывают одинаковое поведение, к примеру, покупая, слушая или смотря одно и то же, то и с другими элементами они будут вести себя тоже одинаково.

Техника КФ использует базу данных предпочтений пользователя для предсказания того, какие продукты, которые он еще не использовал, могут ему понравиться. Типичный сценарий КФ - это список m юзеров {u1, u2, …, um} и список n элементов {i1,i2,…, in}, и каждый пользователь ui имеет список элементов Iui, которые он оценил.  Оценки могут быть как точными значениями, например, баллами от 1 до 5, так и неявными, такие как покупки, переходы на страницы и т.д. Например, можно из списка людей и сериалов, которые им нравятся и не нравятся (табл. 1), создать матрицу пользователь-элемент (табл. 2). В ней Дима – активный пользователь, для которого нужно составить рекомендации. В матрице есть незаполненные поля, значений которых не известны.

Таблица 1. Список людей и фильмов, которые им нравятся и не нравятся

Евгений

(+) Касл (Kastle); Сверхъестественное (Supernatural); (-) Папины дочки

Вера

(+) Сверхъестественное (Supernatural); Папины дочки;(-) Доктор Хаус(House M.D.)

Олег

(+) Доктор Хаус (House M.D.); (-) Сверхъестественное (Supernatural)

Дима

(+) Касл (Kastle); (-) Доктор Хаус (House M.D.)

Таблица 2. Матрица «Пользователь-Элемент»

 

Касл (Kastle)

Сверхъестественное (Supernatural)

Доктор Хаус (House M.D.)

Папины дочки

Евгений

+

+

 

Вера

 

+

+

Олег

 

+

 

Дима

+

+

?

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

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

Гибридные КФ техники такие, как КФ с усиленным содержанием и Персональный диагноз (ПД), сочетают в себе обе техники, и КФ, и ФОС, в надежде избежать проблем каждой из техник и тем самым повысить качество рекомендаций.

Краткий обзор техник представлен в табл. 3.

Таблица 3. Обзор техник коллаборативной фильтрации

Кате-гории КФ

Техники

Достоинства

Недостатки

КФ ОП

·                    КФ, основанные на соседстве (основанные на пользователе/элементе с корреляцией Пирсона или косинус угла между векторами)

·                    Основанные на элементе/пользователе лучшие N рекомендации

·                    Легкие в использовании

·                    Новые данные легко добавить

·                    Не используют свойства элементов для выдачи рекомендаций

·                    Хорошая масштабируемость для совместно оценённых элементов

·                    Зависимы от рейтингов пользователей

·                    Качество рекомендаций заметно падает в случае разреженности данных

·                    Не могут выдать рекомендации новым пользователям (элементам)

·                    Ограниченная масштабируемость для очень больших баз данных

КФ ОМ

·                    КФ, основанные на Байесовских сетях

·                    Кластерные КФ

·                    КФ, основанные на процессе Маркова

·                    КФ скрытой семантики

·                    Лучше справляются с разреженными данными и масштабируемостью

·                    Улучшенное качество предсказаний

·                    Дороги в создании и использовании

·                    Всегда нужно выбирать между масштабируемостью и качеством предсказаний

Гибридные КФ

·                    КФ, основанные на содержании

·                    КФ с усиленным содержанием

·                    КФ ОП + КФ ОМ

·                    Самое лучшее качество предсказаний

·                    Справляются с проблемами КФ, такими как разреженность данных и др.

·                    Повышенная сложность и стоимость в создании и обслуживании

·                    Нужна дополнительная информация о пользователях / элементах

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

Литература:

1.     C. Thompson. If you liked this, you’re sure to love that. The New York Times, Nov 21, 2008.

2.     G. Linden, B. Smith, and J. York, “Amazon.com recommendations: item-to-item collaborative filtering,” IEEE Internet Computing, vol. 7, no. 1, pp. 76–80, 2003.

3.     M. Balabanovic and Y. Shoham, “Content-Based Collaborative Recommendation,” Comm. ACM, Mar. 1997, pp. 66-72.