Математическое обеспечение рекомендательных информационных систем и его реализации

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ РЕКОМЕНДАТЕЛЬНЫХ ИНФОРМАЦИОННЫХ СИСТЕМ И ЕГО РЕАЛИЗАЦИИ

Б.С. Шевченко

Иркутский национальный исследовательский

технический университет,

Е.А. Черкашин

Институт динамики систем и теории

управления им. В.М. Матросова СО РАН

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

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

MATHEMATICAL SUPPORT OF RECOMMENDED INFORMATION SYSTEMS AND ITS IMPLEMENTATION

B. Shevchenko, E. Cherkashin

The article provides a brief literature review of research in the field of recommendatory information systems and examples of their applications. In general, schemes of application of mathematical support (methods of multivariate data analysis) are presented at different stages of solving problems of estimating the user's interest in a product or service. The main problems that need to be solved are identified, both at the stage of development of recommendatory systems and at the stage of their operation.

Keywords: recommendation systems; data analysis; artificial intelligence; collaborative filtering; content filtering; conclusion on precedents.

Введение

Рекомендательные системы (РС) [1] - информационные системы поддержки принятия решений, предназначенные для оценки уровня интереса пользователя к определенному продукту или сервису (объекту) на основе имеющейся информации о пользователе и/или объекте. Отрасль разработки РС начала активно развиваться при появлении онлайн-сервисов продаж, и в настоящее время РС - одно из активных направлений развития систем поддержки принятия решений, ориентированное прежде всего на коммерческое использование, а также на решение задач повышения продуктивности поиска релевантной информации.

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

Рекомендательные системы появились в Интернете достаточно давно, около 20 лет назад. Однако настоящий подъем в этой области случился примерно 5-10 лет назад, когда проводилось соревнование NetflixPrize. Компания Netflix тогда не выпускала в прокат цифровые копии, а рассылала VHS-кассеты и DVD. Для фирмы было очень важно повысить качество рекомендаций, ведь чем лучше Netflix рекомендует своим пользователям фильмы, тем больше фильмов они берут в прокат. Соответственно, растет и прибыль компании. В 2006 году компания запустила соревнование NetflixPrize. Она выложила в открытый доступ собранные данные: около 100 миллионов оценок по пятибалльной шкале с указанием ID проставивших их пользователей. Участники соревнования должны были как можно лучше предугадывать, какую оценку поставит определенному фильму тот или иной пользователь. Качество предсказания измерялось при помощи метрики RMSE (среднеквадратичное отклонение). У Netflix уже был алгоритм, который предсказывал оценки пользователей с качеством 0,9514 по метрике RMSE. Задача была улучшить предсказание хотя бы на 10 % - до 0,8563. Победителю был обещан приз в $ 1 000 000. Соревнование длилось примерно три года. За первый год качество предсказания улучшили на 7 %, далее прогресс немного замедлился. Наконец две команды с разницей в 20 минут прислали свои решения, которые проходили порог в 10 % и имели качество, одинаковое с точностью до четвертого знака. В задаче, над которой множество команд билось три года, решающими оказались двадцать минут. Опоздавшая команда (как и многие другие, участвовавшие в конкурсе) осталась ни с чем, однако сам конкурс очень сильно подстегнул развитие в данной сфере [2].

В области рекомендательных систем используется специальная терминология. Объектом обозначается то, что система рекомендует пользователям, например продукты, услуги, товары, новости, книги, DVD и т.п. Профилем пользователя или объекта являются данные, характеризующие пользователя или объект. Именно эти данные используются в процессе оценивания релевантности объекта желаниям пользователя. Этот процесс называется фильтрацией. В результате фильтрации объекты ранжируются в соответствии с полученной оценкой, а пользователю предоставляется некоторое конечное подмножество, элементы которого имеют максимальную релевантность, т.е. оцениваются как наиболее интересные пользователю. Далее под интересом мы будем понимать именно интерес пользователя к объекту. Т.к. РС - это прежде всего информационные системы, то все объекты и пользователи описываются при помощи атрибутов. Именно атрибуты являются входной информацией во всех процедурах оценивания интереса. Качество рекомендации - оценка точности предсказания интереса, сделанного РС, например, в сравнении с имеющимися примерами, т.е. оценками конкретных объектов конкретными пользователями.

Рекомендательные системы полезны не только для информационных ресурсов и порталов электронной коммерции, они могут также открыть новые возможности в области безопасности, автомобильной промышленности [3], рекламы [4] и др.

Существует ряд подходов к оценке интереса:

1. На основе фильтрации содержания (content-based information filtering), при этом в информационной системе создаются профили пользователей и объектов, включающие социальный статус пользователя, возраст, место проживания, род деятельности, а также характеристики, выражающие интерес пользователя к объекту; профили объектов включают позицию в системе классификации, его потребительские характеристики.

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

3. Интеллектные (knowledge-based), при которых оценка вычисляется на основе формализованных знаний.

4. Гибридные (hybrid prediction) методы, которые базируются на подходах № 1 и 2, включая элементы из № 3, что призвано повышать эффективность подходов № 1 и/или 2.

Например, в Music Genome Project музыкальный аналитик оценивает каждую композицию по сотням различных музыкальных характеристик, при помощи которых выявляются музыкальные предпочтения пользователя. Перечень оценок формирует профиль музыкального произведения. Основная проблема первого типа РС (фильтрации содержания) - это работоспособность системы на начальном этапе ее эксплуатации, так называемый «холодный старт»: для новых пользователей в системе нет необходимой информации в профиле для принятия решения о том, какие объекты следует предлагать. В связи с этим в современных рекомендательных системах реализуется механизм сбора и анализа данных о пользователях с применением явных и неявных методов.

Явные методы сбора данных предполагают выполнение следующих действий:

· запрос у пользователя оценки объекта по некоторой шкале;

· запрос у пользователя ранжировки группы объектов от наилучшего к наихудшему;

· предъявление пользователю двух объектов с вопросом о том, какой из них лучше;

· предложение создать список объектов, характеризующих предпочтения пользователя.

Примерами неявного сбора данных выступают:

· наблюдение за тем, что просматривает пользователь в интернет-магазине или базе данных;

· ведение записей о поведении пользователя онлайн;

· сбор информации из социальных сетей, например, как в работах [5-7].

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

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

математический рекомендательный информационный пользователь

Рекомендательные системы поиска текстовых документов

В обзоре [8] рассмотрены РС в области предоставления пользователям текстовых документов, в частности научных статей. Более половины (55 %, 34 из 62) систем построены на основе фильтрации содержания. Алгоритмы коллаборативной фильтрации использованы только в 18 % (11 из 62) случаев. Представлены подходы, основывающиеся на стереотипировании и гибридных методах. Авторы исследования пришли к выводу, что в 81 % случаев моделирование пользователя на основе автоматического сбора информации не приносит значимых результатов по сравнению с явным указанием набора ключевых слов.

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

В РС, в которых применялась коллаборативная фильтрация, ни в одном из проектов не удалось успешно использовать явные рейтинги: пользователи были слишком ленивы, чтобы самостоятельно задавать рейтинг статьям. Неявные рейтинги получены из данных по количеству страниц, прочитанных пользователем, взаимодействию пользователей с документами (загрузка, редактирование, представление) и цитированию. Главная проблема коллаборативной фильтрации для научных работ - это дефицит информации, например, для РС научных статей Mendeley по сравнению с Netflix (онлайн фильмы) дефицит составляет три порядка.

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

Основными проблемами в области РС являются:

· отсутствие общего базиса оценивания качества систем (по предметным областям), включая объективную информацию о реальных оценках реальных пользователей, нестабильность методов оценивания и высокую их зависимость от «шума»;

· неиспользованный потенциал научных исследований: новые научные результаты не внедряются в практические приложения (большинство работающих РС базируются на простых методах), данные существующих практических реализаций РС научно не исследуются, нет тесного взаимодействия со смежными областями анализа данных, а также друг с другом, низкий научный интерес к рекомендательным системам;

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

Среди открытых проектов выделяются MyMediaLite, LensKit, Mahout, Duine, RecLabCore, easyrec и Recommender.

Методы фильтрации содержания

В статье [5] рассматривается анализ профиля пользователя в социальной сети «ВКонтакте» для решения проблемы холодного старта при рекомендации жанров и произведений музыки и фильмов. Авторами разработана рекомендательная система EZSurf, автоматизирующая процесс веб-серфинга и фильтрации контента с использованием профиля пользователя в социальной сети «ВКонтакте», а также API сервисов last.fm, TheMovieDB для получения сведений о схожих объектах (музыкальных произведениях). Такой подход существенно упрощает хранилище данных РС, поскольку не требует создания собственной системы классификаций и базы объектов.

В работе [9] рассматривается задача выделения N объектов с наивысшими оценками интереса, задача top-N, при применении фильтрации контента. Предлагается математическая модель контентной рекомендательной системы, основанная на нечетких множествах, критерий оценки качества рекомендаций и алгоритм решения задачи. Математическая модель и алгоритм протестированы на данных сайта last.fm.

Методы коллаборативной фильтрации

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

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

Коэффициент Пирсона [3]:

,

где - множество пользователей, которые оценили объекты и.

Косинус угла между двумя векторами и:

.

Производится формирование конечного множества объектов наиболее близких к объекту . Вычисление рейтинга объекта осуществляется по формуле

.

Популярный подход к формированию множества рекомендаций - это упорядочивание всех объектов по критерию схожести и выборке некоторого фиксированного количества объектов с максимальным рейтингом [10]. В качестве меры similarity двух объектов выступает cos угла между n-мерными векторами.

В работах [3, 10] также представлен обзор способов использования вышеупомянутых методов вычисления оценок, которые разделены на два класса - анамнестические, т.е. основывающиеся на одновременной обработке всех имеющихся данных, и модельные, при которых производится предварительная обработка данных, выполняемая, например, раз в сутки. Второй класс позволяет быстрее вычислять оценки интереса, однако не обеспечивает актуальности данных. В классе аналитических способов, как правило, используются методы многомерного анализа данных на основе «ближайшего соседства» (Neighbourhood-based), в то время как в модельных методах используется методы анализа скрытых факторов (Latent Factors). Существуют гибридные методы, объединяющие оба предыдущих класса.

Гибридные методы

В статье [11] рассмотрена задача разработки алгоритмов оценивания лекционного материала. Авторами предложен алгоритм вычисления близости лекций (объектов), где каждая лекция характеризуется подмножеством некоторого набора значений (например, подмножеством авторов лекций относительно множества всех авторов). Базовый алгоритм реализует подход фильтрации содержания. Для алгоритма подобраны коэффициенты, при помощи которых можно объединять оценки различных атрибутов в одну общую оценку лекции. Наиболее значимыми атрибутами оказались «категории», «авторы», «языки», «название» и «описание». Цель - синтезировать набор лекций фиксированной длины, рекомендованных для просмотра заданному пользователю, из фиксированного множества «новых», не использованных в построении профилей пользователя и объекта.

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

Приложения рекомендательных систем на новостных сайтах

В работе [12] создан рекомендательный сервис новостей для посетителей сайта, время пересчета рекомендаций в котором на каждую тысячу новых записей в журнале WEB-сервера составляет 1,5-2 с, благодаря чему ресурс заявлен авторами как функционирующий в режиме, близком к реальному времени. Для проекта «Рамблер-новости» подобный результат является удовлетворительным, так как 1000 новых запросов к сайту производится за чуть большее время. В исследовании использован адаптированный алгоритм MinHash для идентификации записей журнала и неточного их сравнения. Цель работы - показать целесообразность применения NoSQL-технологий для создания сервисов указанного качества. Важным свойством приведенной реализации является то, что задачи хранения и анализа данных удалось объединить с задачей предоставления доступа к результатам в единой системе, избежав накладных расходов на перемещение данных из одного источника в другой, что улучшило общую производительность сервиса. Кроме того, предложенный подход упрощает решение повседневных задач сбора статистики о взаимодействии пользователя с веб-приложением путем анализа структурированных логов мощным языком запросов СУБД MongoDB. В результате продемонстрировано, что применение NoSQL к решению подобного класса задач является весьма перспективным.

Оценка эффективности работы рекомендательных систем

В статье [13] поднята проблема сравнительной оценки различных подходов к построению РС. Классической оценкой точности предсказания интереса является оценка RMSE, среднеквадратическое отклонение, которое вычисляется при помощи формулы

где - множество пар пользователей и объектов - оценка интереса объекта пользователем i, - оценка интереса, проведенная РС.

Сопутствующие технические задачи

Одной из важных задач, решаемых при разработке РС, является создание пользовательского интерфейса, адекватно отображающего систему критериев, по которым необходимо производить подбор объектов для пользователя. Например, в статье [14] представлен модуль естественно-языкового интерфейса к базе данных РС, который реализован на основе математических моделей семантических объектов. При помощи модели решаются задачи определения семантики языковой конструкции, заданной пользователем, включая синонимы, классы, отношения и ограничения. В статье приводятся сведения о программной реализации предложенного метода в среде PHP + SQL и результатах тестирования программы на задаче доступа к базе данных РС автомобильного салона.

В статье [15] решается проблема обеспечения ограничения доступа к личным данным пользователей в контексте построения РС встраивания рекламных сообщений в информационный поток. При этом необходимо контролируемо предоставлять в одностороннем порядке в РС информацию из БД пользователей. Предложено вместо традиционных средств VPN использовать режим функционирования сети с синхронным изменением IP-адреса сервера и переключение клиента на этот адрес.

Заключение

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

· пользователи неохотно предоставляют информацию о себе и своих потребностях, либо разработчики РС уделяют мало внимания процессу информационного наполнения профиля пользователя;

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

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

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

Библиографический список

1. Jannach D., Zanker M., Felfernig A., Friedrich G. Recommender Systems: An Introduction. Cambridge University Press, 2010.

2. Как работают рекомендательные системы. Лекция в Яндексе [Электронной ресурс] // Хабрахабр. URL: https://habrahabr.ru/company/yandex/blog/241455/ (12.12.2016).

3. Пятикоп Е.Е. Исследование метода коллаборативной фильтрации на основе сходства элементов // Наукові праці ДонНТУ. Серія: Інформатика, кібернетика та обчислювальнатехніка. 2013. Вып. 2 (18). С. 109-114.

4. Бритвина Е.В. Сегментирование рекомендательной системы с использованием метода организации соединения «клиент - сервер», основанного на программно-конфигурируемых сетях и применении протокола с быстрым перескоком IP-адреса [Электронный ресурс] // Современные проблемы науки и образования: электронный научный журнал. 2015. № 6. URL: https://www.science-education.ru/ru/article/view?id=16875 (12.12.2016).

5. Авхадеев Б.Р., Воронова Л.И., Охапкина Е.П. Разработка рекомендательной системы на основе данных из профиля социальной сети «ВКонтакте» // Вестник Нижневартовского государственного университета. 2014. Вып. 3. С. 10.

6. Hossain N. Why the Interest Graph Is a Marketer's Best Friend [Электронный ресурс]. URL: http://mashable.com/2012/06/19/interest-graph-marketer/#Hr95qUR_7Eqa (12.12.2016).

7. Жернакова О. Системы рекомендаций и поиска видеоконтента [Электронный ресурс] // Телемультимедиа. 2012. URL: http://www.telemultimedia.ru/art.php?id=464 (12.12.2016).

8. Beel J., Gripp B., Langer S., Breitinger C. Research-paper recommender systems: a literature survey // International Journal on Digital Libraries. 2016. № 17. P. 305. doi:10.1007/s00799-015-0156-0

9. Амелькин С.А., Понизовкин Д.М. Математическая модель задачи top-N для контентных рекомендательных систем // Известия МГТУ «МАМИ». 2013. № 3 (17). Т. 2. С. 26-31.

10. Нефедова Ю.С. Архитектура гибридной рекомендательной системы GEFEST (Generation-Expansion-Filtering-Sorting-Truncation) // Системы и средства информатики. 2012. Т. 22. Вып. 2. С. 176-196.

11. Дьяконов А.Г. Алгоритмы для рекомендательной системы: технология Lenkor // Бизнес-информатика. 2012. № 1 (19). С. 32-39.

12. Клеменков П.А. Построение новостного рекомендательного сервиса реального времени с использованием NoSQL СУБД // Информатика и еe применение. 2013. Т. 7. Вып. 3. С. 14-21.

13. Амелькин С.А. Оценка эффективности рекомендательных систем // Труды 14-й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» - RCDL-2012, Переславль-Залесский, 15-18 октября 2012 г.

14. Правиков А.А., Фомичев В.А. Разработка рекомендательной системы с естественно-языковым интерфейсом на основе математических моделей семантических объектов // Бизнес-информатика. 2010. № 4 (14). С. 3-11.

15. Бритвина Е.В. Сегментирование рекомендательной системы с использованием метода организации соединения «клиент - сервер», основанного на программно-конфигурируемых сетях и применении протокола с быстрым перескоком IP-адреса [Электронный ресурс] // Современные проблемы науки и образования: электронный научный журнал. 2015. № 6. URL: https://www.science-education.ru/ru/article/view?id=16875 (12.12.2016).

Размещено на Allbest.ru