Введение

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

Основная задача рекомендательных алгоритмов – анализировать запросы пользователя и на основе этих данных предсказивать его действия.

1. Актуальность темы

В сервисах которые предлагают большой выбор товаров или контента существует проблема длинного хвоста. Данная проблема походим под категорию Распределение Парето (отношение 20% к 80%), представленую на рисунке 1. Так например 20% видов товаров в интернет магазине делают 80% выручки. Пользователи покупают в основном популярные товары, а про существование оставшихся 80% товаров пользователь может даже не знать. Таким образом появляется проблема, когда пользователь может не знать о существовании товара только потому, что он не популярен среди большинства. Для решения данной проблемы созданы алгоритмы рекомендаций которые персонализируют предложения исходя из данных о пользователях[1].

Рисунок 1. Проблема длинного хвоста.

На данный момент существует целый ряд направлений в данной сфере:

• Приватность. Необходимо обезопасить доступ к приватным данным пользователей. Важно исключить возможность идентифицировать личные данные пользователей исходя из работы алгоритма[2];
• Отказоустойчивость. Необходимо защитить алгоритм от атак злоумышленников, которые могут подать неправильные данные в качестве исходных данных, тем самым уменьшив его эффективность[3];
• Определение важности действий пользователей. При просмотре или покупке товара пользователь проявляет свой интерес к данному продукту, однако важность покупки намного выше чем важность просмотра[4];
• Социальность. Активное развитие социальных сетей дает возможность узнать информацию про интересы не только конкретного пользователя, но и интересы его друзей и знакомых[5];
• Мобильные платформы. Развитие операционных мобильных операционных систем дало возможность собирать больше информации о пользователях, а также существенно увеличило количество данных о текущем контексте пользователя[6];
• Оптимизация алгоритмов. С развитием технологий появилась возможность собирать большие массивы информации. Из-за этого необходимо оптимизировать алгоритмы таким образом, чтобы использовалось меньше оперативной памяти и процессорного времени, при условие увеличение эффективности алгоритма[7];
• Объединение алгоритмов. За 15 лет развития сферы было создано большое количество алгоритмов, которые используют разные исходные данные про пользователя и рекомендуемые товары, а также имеют различные подходы к их обработке. Таким образом существует несколько способов получить предсказания в каждой ситуации. Задача заключаться в объеденение нескольких методов для более точного прогноза.[8]

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

Регулярно проводятся чемпионаты для поиска решения для наиболее важных проблем.

2. Цель и задачи исследования, планируемые результаты

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

Дополнительные задачи исследования:

• Анализ подходов для создания систем удовлетворяющих пользовательские запросы;
• Оценка рекомендательных алгоритмов;
• Изучение технологий анализа больших массив информации;
• Объединение несколько рекомендательных алгоритмов в один гибридный;
• Оценка эффективности работы алгоритмов.

Объект исследования:Системы удовлетворения пользовательских запросов.

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

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

1. Оптимизация алгоритмов основанных на действиях пользователей для применения в сфере рекомендаций мобильных приложений.
2. Оптимизация алгоритмов основанных на свойствах объектов для применения в сфере рекомендаций мобильных приложений.
3. Оптимизация алгоритмов основанных на знаниях для применения в сфере рекомендаций мобильных приложений.
4. Оптимизация объединение подходов в гибридный алгоритм.

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

• Доступна информация про объекты предсказания(жанр, категория, и т.д.);
• Доступна информация про пользователей и их множества данных;
• Объект предсказания имеют оценку экспертов(от 0 до 5);
• Алгоритм должен указывать какие данные наиболее сильно повлияли на предсказания, для того, чтобы пользователю было проще сделать свой выбор;
• Алгоритм должен работать в режиме реального времени и предоставлять предсказания пользователю в течении нескольких секунд;
• Алгоритм должен учитывать обратную связь от пользователей(понравилось предсказание или нет, какие данные для предсказаний важны, и т.д.);
• Алгоритм должен собирать новые данные от пользователей и обратную связь во время работе предсказаний, и использовать эти данные обновляя основную матрицу расстояний(не обязательно в режиме реального времени, например раз в сутки).

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

Даная сфера науки начала активно развиваться сравнительно недавно, ориентировачно с 2007 года, когда был объявлен конкурс Netflix на 1 000 000 $ по улучшению их рекомендательной системы.

3.1 Обзор международных источников

Существует большое количество научных публикаций связанных с система удовлетворения пользовательских запросов и технологий Big Data. Наиболее весомый вклад в данную сферу внесли ученые из США и Западной Европы.

Публикация Jeffrey Dean и Sanjay Ghemawat MapReduce: Simplified Data Processing on Large Clusters содержит анализ технологии MapReduce. MapReduce является подходом в программировании, который связан с реализацией обработки и генерации больших массивов данных[2].

Публикация Jorge Aranda, Inmar Givoni, Jeremy Handcock, Danny Tarlow An Online Social Network-based Recommendation System содержит анализ системы, которая использует данные профиля пользователя и его социальные связи[3].

Публикация Yehuda Koren Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model содержит информацию об особенностях алгоритмов рекомендаций основанных на факторизации матриц[4].

Публикация Michael Hahsler recommenderlab: A Framework for Developing and Testing Recommendation Algorithms содержит информацию об особенностях работы с фреймворком recommenderlab, который используют при создании рекомендательных систем[5].

Публикация Ruslan Salakhutdinov, Andriy Mnih, Geoffrey Hinton Restricted Boltzmann Machines for Collaborative Filtering содержит информацию про примененение машин Больцмона в алгоритмах рекомендаций[6].

Публикация Silva N.B. A graph-based friend recommendation system using Genetic Algorithm содержит информацию про особенности алгоритма рекомендаций, который основан на генетических алгоритмах[7].

Публикация Songjie Gong Learning User Interest Model for Content-based Filtering in Personalized Recommendation System содержит информацию про особенности алгоритмов рекомендаций основаных на свойствах объектов[8].

Публикация Wahidah Husain, Lam Yih Dih A Framework of a Personalized Location-based Traveler Recommendation System in Mobile Application содержит информацию про про особенности алгоритмов рекомендаций основаных на геолокации[9].

3.2 Обзор национальных источников

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

Публикация Гомзина А.Г. и Коршунова А.В. Системы рекомендаций: обзор современных подходов содержит обзор существующих подходов при создании систем рекомендаций. Приведены и систематизированы основные идеи каждого из подходов, а также проведен их сравнительный анализ[10].

Публикация Зайцева И.Б. Методика наивного Байесовского классификатора для задачи совместной фильтрации в системах рекомендации содержит подробный анализ математического аппарата алгоритмов рекомендаций, которые используют найвный Байесовский подход для совместной фильтрации. Данный метод на практике используется в алгоритмах поисковых движков[11].

Публикация Дьяконова А.Г. Алгоритмы для рекомендательной системы: технология LENKOR содержит описание алгоритмов, которые заняли первые места на Международном соревновании «ECML/PKDD Discovery Challenge 2011 (VideoLectures.Net Recommender System Challenge) по написанию рекомендательной системы для ресурса VideoLectures.net (научного репозитариялекций)[12].

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

Публикация Соболя А.С. Построение и адаптация newsql субд в частном «облаке». Анализируются вопросы построения NewSQL СУБД в частном «облаке» с учетом ограничений БД. Формализуются требования к будущей NewSQL СУБД, в которой планируется обслуживать систему электронного документооборота (СЭД) и систему бизнес-аналитики предприятия[14].

3.3 Обзор локальных источников

Научных публикаций связанных непосрдественно с созданием рекомендательных систем найдено не было, однако студенты и преподователи ДонНТУ имеют целый ряд научных публикаций связанных с анализом данных и использованием технологии Big Data, которые связанны с темой дипломной работы.

Работа магистра ДонНТУ Филоновой В.А. Разработка модели персонализации и алгоритма управления контентом веб-сайта с учетом постоянных и текущих потребностей пользователя под руководством Шелепова В.Ю. связана с решением проблемы персонализации web-страниц на основе данных о пользователе путем применения алгоритма CLOPE[15].

Работа магистра ДонНТУ Михнюка Д.В. Разработка и исследование алгоритмического обеспечения интеллектуальной системы формирования рекомендаций на основе методов коллаборативной фильтрации под руководством Егошиной А.А. посвящена анализу и модификации алгоритмов коллаборативной фильтрации для удовлетворения пользовательских запросов[16].

Работа магистра ДонНТУ Чуприн В.И. Повышение эффективности реализации модели распределённых вычислений MapReduce в рамках программного каркаса Hadoop под руководством Дмитриевой О.А. посвящена модификации технологии Big Data – MapReduce на основе фреймворка Hadoop[17].

Работа магистра ДонНТУ Дрига В.В. Разработка и исследование алгоритма построения взвешенных обучающих выборок на основе методов кластеризации данных под руководством Волченко В.В. посвящена проблеме кластеризации больших массивов данных на группы похожих объектов[18].

Работа магистра ДонНТУ Носова А.С. Исследование социально-экономического развития стран мира с использованием среды анализа R и многомерная визуализация под руководством Аверина Г.В. посвящена проблеме визуализации данных при помощи инструмента анализа данных R[19].

Работа магистра ДонНТУ Петце А.О. Предварительная обработка данных и отбор факторов в задачах нейросетевой классификации и прогнозирования под руководством Хмелевого С.В. посвящена проблеме прогнозированния на основе массивов данных при помощи нейронных сетей.[20].

4. Анализ подходов при создании систем удовлетворяющих пользовательские запросы

4.1 Алгоритмы основанные на действиях пользователей (user-based).

Системы используют только информацию о действиях пользователя. Основная идея следующая – если пользователи U1 и U2 купили книгу B1, а пользователь U2 купил еще и книгу B2, то логично, что книга B2 будет также интересна пользователю U1.

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

4.2 Алгоритмы основанные на свойствах объектов (item-based).

Системы данного типа не используют данные о действиях пользователя и только анализируют свойства рекомендуемых предметов и свойства текущего пользователя.

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

4.3 Алгоритмы основанные на знаниях (knowledge-based recommendations).

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

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

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

4.4 Гибридные алгоритмы (hybrid).

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

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

4.5 Сравнение подходов.

Сравнение алгоритмов представлено в таблице 1.

Таблица 1. Сравнение подходов к созданию рекомендательних систем.

5. Анализ структуры рекомендательных систем

Диаграмма работы абстрактной рекомендательной системы представлена на рисунке 2.

Рисунок 2. Диаграмма работы абстрактной рекомендательной системы.

(Анимация Размер: 99 Kb; Количество кадров: 9; Количество повторов: 5)

Выводы

Существует несколько способов реализации алгоритма рекомендаций. Однако не один из способов в одиночку не может дать хороших результатов. Поэтому на практике всегда необходимо использовать гибридную систему которая объеденяет несколько способов.

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

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

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

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

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

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

Список источников

1. Leskovec J., Rajaraman A., Ullman J. Mining of Massive Datasets // The MOOC. – 2014. [Электронный ресурс]: http://www.mmds.org/.
2. Dean J., Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters // Google, Inc. – 2004. [Электронный ресурс]: http://static.googleusercontent.com/media/research.google.com/en//archive/mapreduce-osdi04.pdf
3. Aranda J., Givoni I., Handcock J., Tarlow D. An Online Social Network-based Recommendation System // University of Toronto – 2007. [Электронный ресурс]: http://www.cs.toronto.edu/syslab/courses/csc2231/07au/projects/2/aranda.pdf
4. Koren Y. Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model // University of Toronto – 2007. [Электронный ресурс]: http://research.yahoo.com/files/kdd08koren.pdf
5. Hahsler M. recommenderlab: A Framework for Developing and Testing Recommendation Algorithms // Southern Methodist University – 2008. [Электронный ресурс]: http://cran.r-project.org/web/packages/recommenderlab/vignettes/recommenderlab.pdf
6. Salakhutdinov R., Mnih A., Hinton G. Restricted Boltzmann Machines for Collaborative Filtering // Southern Methodist University // Proceeding – 2007.
7. Silva N.B. A graph-based friend recommendation system using Genetic Algorithm // Southern Methodist University // Evolutionary Computation – 2010.
8. Gong S. Learning User Interest Model for Content-based Filtering in Personalized Recommendation System // Zhejiang Business Technology Institute – 2010.
9. Husain W., Dih L.Y. A Framework of a Personalized Location-based Traveler Recommendation System in Mobile Application // Universiti Sains Malaysia – 2012.
10. Гомзин А.Г., Коршунов А.В. Системы рекомендаций: обзор современных подходов // Труды ИСП РАН . 2012. №. [Электронный ресурс]: http://cyberleninka.ru/article/n/sistemy-rekomendatsiy-obzor-sovremennyh-podhodov (дата обращения: 28.05.2015).
11. Зайцев И.Б. Методика «наивного» Байесовского классификатора для задачи совместной фильтрации в системах рекомендации // ДНА . 2005. №2. [Электронный ресурс]: http://cyberleninka.ru/article/n/metodika-naivnogo-bayesovskogo-klassifikatora-dlya-zadachi-sovmestnoy-filtratsii-v-sistemah-rekomendatsii (дата обращения: 28.05.2015).
12. Дьяконов А.Г. Алгоритмы для рекомендательной системы: технология LENKOR // Бизнес-информатика . 2012. №1 (19). [Электронный ресурс]: http://cyberleninka.ru/article/n/algoritmy-dlya-rekomendatelnoy-sistemy-tehnologiya-lenkor (дата обращения: 28.05.2015).
13. Хашковский В.В., Шкурко А.Н. Современные подходы в организации систем обработки больших объемов данных // Известия ЮФУ. Технические науки . 2014. №8. [Электронный ресурс]: http://cyberleninka.ru/article/n/sovremennye-podhody-v-organizatsii-sistem-obrabotki-bolshih-obemov-dannyh (дата обращения: 28.05.2015).
14. Соболь А.С. Построение и адаптация newsql субд в частном облаке // Вестник СибГАУ . 2013. №4 (50). [Электронный ресурс]: http://cyberleninka.ru/article/n/postroenie-i-adaptatsiya-newsql-subd-v-chastnom-oblake (дата обращения: 28.05.2015).
15. Филонова В.А. Разработка модели персонализации и алгоритма управления контентом веб-сайта с учетом постоянных и текущих потребностей пользователя // Портал магистров ДонНТУ, 2014 - [Электронный ресурс]: http://masters.donntu.ru/2014/fknt/filonova/diss/index.htm (дата обращения: 28.05.2015).
16. Михнюк Д.В. Разработка и исследование алгоритмического обеспечения интеллектуальной системы формирования рекомендаций на основе методов коллаборативной фильтрации // Портал магистров ДонНТУ, 2014 - [Электронный ресурс]: http://masters.donntu.ru/2014/fknt/mihnyuk/ (дата обращения: 28.05.2015).
17. Чуприн В.И. Повышение эффективности реализации модели распределённых вычислений MapReduce в рамках программного каркаса Hadoop // Портал магистров ДонНТУ, 2014 - [Электронный ресурс]: http://masters.donntu.ru/2014/fknt/chuprin/diss/index.htm (дата обращения: 28.05.2015).
18. Дрига В.В. Разработка и исследование алгоритма построения взвешенных обучающих выборок на основе методов кластеризации данных // Портал магистров ДонНТУ, 2013 - [Электронный ресурс]: http://masters.donntu.ru/2013/fknt/driga/index.htm (дата обращения: 28.05.2015).
19. Носов А.С. Исследование социально-экономического развития стран мира с использованием среды анализа R и многомерная визуализация // Портал магистров ДонНТУ, 2013 - [Электронный ресурс]: http://masters.donntu.ru/2013/fknt/nosov/diss/index.htm (дата обращения: 28.05.2015).
20. Петце А.О. Предварительная обработка данных и отбор факторов в задачах нейросетевой классификации и прогнозирования // Портал магистров ДонНТУ, 2013 - [Электронный ресурс]: http://masters.donntu.ru/2013/fknt/pettse/diss/index.htm (дата обращения: 28.05.2015).

Примечания

При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2015 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.