Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
«Национальный исследовательский университет
«Высшая школа экономики»
Факультет Бизнес-информатики
Отделение Прикладной математики и информатики
Кафедра Анализа данных и искусственного интеллекта
ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА БАКАЛАВРА
на тему
Рекомендательная система на основе узорных структур
Выполнил студент группы 472ПМИ
Корнилов Денис Игоревич
Научный руководитель:
Доцент, к.т.н,
Игнатов Дмитрий Игоревич
Москва 2014
Оглавление
Введение 2
1.Анализ формальных понятий 5
1.1.Основные определения 5
1.2.Узорные структуры 6
1.2.1.Введение в узорные структуры 6
1.2.2.Интервалы в качестве узоров 7
1.2.3.Интервальные векторы в качестве узоров 8
1.3.Выводы и результаты по главе 8
2.Рекомендательные системы и алгоритмы 9
2.1.Существующие подходы 9
2.1.1.Фильтрация содержимого 9
2.1.2.Коллаборативная фильтрация 10
2.2.Подход Slope One 11
2.2.1.Модельный пример 14
2.3.Подход на основе узорных структур (RAPS) 15
2.3.1.Модельный пример 17
2.4.Выводы и результаты по главе 18
3.Машинные эксперименты 19
3.1.Данные 19
3.2.Точность и полнота 19
3.3.Програмные средства 22
3.4.Эксперименты и оценка результатов 23
3.5.Выводы и результаты по главе 25
Список литературы 26
Приложение 1 27
Приложение 2 27
Приложение 3 32
Приложение 4 34
Приложение 5 36
Введение
Прежде всего, необходимо дать определение рекомендательной системы. Рекомендательные системы – это специальные программы, главная цель которых заключается в формировании рекомендаций различных продуктов или сервисов для пользователей на основе их предпочтений [4].
С появлением Интернета сильно выросло количество информации, с которой люди ежедневно сталкиваются. Это означает, что люди должны ориентироваться среди чрезвычайно большого количества доступных альтернатив, когда хотят что-либо найти. Например, от выбора нового мобильного телефона или плеера до поиска кинофильма для вечернего просмотра. С другой стороны выступают владельцы интернет-магазинов и сервисов: они заинтересованы в персональной рекламе и рекомендациях каждому конкретному пользователю, потому что такой подход может существенно увеличить прибыль компаний. Как результат, в последние годы интерес к разработке и улучшению существующих рекомендательных систем значительно вырос.
В наши дни рекомендательные системы уже достаточно распространены и имеют большое количество применений. В первую очередь, рекомендательные системы используются в интернет-коммерции для того, чтобы помочь пользователям выбрать подходящие товары. Такие сервисы собирают информацию о предпочтениях пользователей и пытаются предложить им полезные товары. Яркими примерами компаний, использующих данный подход, являются Amazon, eBay, iTunes и другие. Другое важное применение рекомендательных систем – это помощь пользователям в выборе книг, музыки и фильмов. Например, сервисы Pandora, GoodReads, and IMDb используют рекомендательные системы для этих целей.
На данный момент существует множество методов для формирования рекомендаций, но все они имеют свои преимущества и недостатки [4], [5]. Именно поэтому исследования в данной области актуальны.
Главная задача этой работы – разработка рекомендательной системы кинофильмов на основе узорных структур и исследование ее практической полезности. Узорные структуры позволяют использовать методы Анализа Формальных Понятий для данных со сложными описаниями, например интервалами или графами [2].
Стоит отметить, что Анализ Формальных Понятий уже применялся при построении рекомендательных систем на основе коллаборативной фильтрации [7]. В той работе было разработано два метода, которые использовали решетку понятий для поиска «ближайших соседей» и прогнозирования. В другой работе использовали узорные структуры для поиска генов со схожими биологическими функциями [3].
Объектом данного исследования являются рекомендательные системы. Предмет исследования –метод формирования рекомендаций на основе узорных структур.
Помимо представленного в работе метода рекомендаций на основе узорных структур, также был рассмотрен и реализован метод рекомендаций Slope One [6]. Алгоритм Slope One использовался для экспериментальной проверки метода, разработанного на основе узорных структур.
Для экспериментов использовались свободно распространяемые данные оценок фильмов MovieLens, которые содержат 100000 оценок от 943 пользователей по 1682 фильмам.
Экспериментальное сравнение разработанного алгоритма и алгоритма Slope One проводилось для различных наборов параметров по трем критериям: среднее время работы, средняя точность и средняя полнота.
Для проведения экспериментов было написано несколько программ на языке MATLAB:
программа, которая обрабатывает начальные данные и преобразовывает их в глобальные матрицы, с которыми работают все остальные программы.
программа, которая запускает методы с различными параметрами и сравнивает полученные результаты в терминах точности и полноты.
программа, реализующая алгоритм рекомендаций на основе узорных структур.
программа, которая реализовывала алгоритм Slope One.
программа для вычисления точности и полноты.
Результаты экспериментов показали, что разработанный метод рекомендаций на основе узорных структур дает неплохие рекомендации и применим для практического использования.
Данная работа разбита на три смысловые части. В первой рассматриваются основные определения Анализа Формальных Понятий и узорных структур. Во второй части, рассматриваются существующие подходы к рекомендательным системам, приводятся алгоритм Slope One и алгоритм рекомендаций на основе узорных структур с примерами применения. Заключительная часть посвящена проведенным экспериментам и всему с ними связанному.
|
