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

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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ НАЦИОНАЛЬНЫИ? ИССЛЕДОВАТЕЛЬСКИИ? УНИВЕРСИТЕТ «ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет бизнеса и менеджмента

Выпускная квалификационная работа

СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ РЕКОМЕНДАТЕЛЬНЫХ СИСТЕМ

Пляскин Павел Александрович

Москва, 2018



Оглавление

Введение

Глава 1. Рекомендательные системы

1.1 Определение рекомендательных систем

1.2 Примеры успешных рекомендательных систем

1.3 Типы рекомендательных систем

1.4 Методы построения рекомендательных систем

1.5 Критерии оценки качества рекомендательной системы

1.6 Проблемы

Глава 2. Разработка систем. Описание методов и их особенностей реализации в данной работе

2.1 Описание используемых данных

2.2 Практическая реализация рекомендательных систем

Глава 3. Результаты применения рекомендательных систем

3.1 Оценка качества построенных моделей

3.2 Описание полученных результатов

Заключение

Список литературы



Введение

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

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

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

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

Целью данной работы является формирование рекомендаций по использованию алгоритмов рекомендательной системы с помощью теоретического и практического сравнения алгоритмов.

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

1. Провести теоретический анализ алгоритмов построения рекомендательных систем;

2. Реализовать наиболее популярные из рассмотренных алгоритмов;

3. Провести анализ качества построенных моделей на основе базы данных MovieLens;

4. Оценить полученные результаты, разработать рекомендации по использованию различных алгоритмов.



Глава 1. Рекомендательные системы

1.1 Определение рекомендательных систем

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

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

При явном способе сборе данных пользователей сам предоставляет данные о себе, которые затем используются в работе рекомендательной системе.

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

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

· Запрос у пользователя персональных данных

· Запрос у пользователя ранжирования объектов

· Запрос у пользователя списка любимых или интересных объектов

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

При неявном сборе данных о пользователе происходит сбор данных без явного участия пользователя.

Неявный сбор данных может быть реализован следующим образом:

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

· Сбор информации о пользователе у партнеров

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

1.2 Примеры успешных рекомендательных систем

На сегодняшний день рекомендательные системы имеют практически все крупные сервисы, например:

· Amazon.com

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

· imdb.com

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

· Last.fm

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

· Facebook

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

· Netflix

Данный сервис предоставляет услуги аренды и просмотра видео контента. Компания проводила одно из первых крупных открытых соревнований, в котором участникам предлагали улучшить уже существующую рекомендательную систему на Netflix. Главным призом являлась интеграция разработанной победителем рекомендательной системы в продуктивное использование и $1 000 000. Это соревнование вызвало огромный интерес у научного сообщества.

· Google, Yandex, Mail.Ru

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

В каждом сервисе, в котором встроена рекомендательная система, существует собственная специфика, на основании которой строятся рекомендации, однако цель каждой рекомендательной системы - предсказывать объекты, которые будут интересны пользователю.

1.3 Типы рекомендательных систем

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

На сегодняшний день существует несколько подходов к формированию рекомендаций [2] (рис. 1):

Рис. 1. Типы рекомендательных систем

Естественно, каждый из этих типов обладает какими-то своими преимуществами и недостатками. Без проведения исследования на сравнение качества рекомендаций формируемым каждым типом невозможно наверняка сказать какой из типов проявит себя лучше в том или ином случае.

Далее рассмотрим каждый тип рекомендательный системы.

Collaborative filtering (коллаборативная фильтрация)

Термин коллаборативная фильтрация впервые был упомянут в контексте первой коммерческой рекомендательной системы Tapestry, которая была создана для фильтрации корпоративной почты. Данный тип рекомендательных систем предлагает рекомендации на основе оценок или покупок других пользователей. Коллаборативная фильтрация основывается на собранной информация о пользователях и о продуктах, которые оценили данные пользователи. На основе этих данных строится матрица, которую принято называть user-item matrix, она и является основополагающим элементом данного типа рекомендательных систем. Строки этой матрицы обозначают пользователей, столбцы - объекты, а на их пересечении ставится оценка, которую выставил .

Пример такой матрицы представлен в таблице 1:

Таблица 1. Пример user-item матрицы.

		Объекты
Пользователи		Item 1	Item 2	Item 3	…	Item n
	User 1	2	3	-	…	5
	User 2	3	4	3	…	-
	User 3	3	2	-	…	3
	…	…	…	…	…	…
	User n	1	-	5	…	4

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

1. Для каждого пользователя (объекты) найти, насколько похожи другие пользователи (объекты) похожи на данный.

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

Остается вопрос, что же именно считать «похожими» пользователями или объектами. Существует несколько способов, которые применяют для вычисления меры схожести пользователей или объектов, некоторые из них будут более подробно рассмотрены далее. Однако в большинстве случаев на основе user-item матрицы, строится матрица подобия или similarity matrix.

Тут стоит отметить, что коллаборативная фильтрация также делится еще на два направления: user-based и item-based, в каждом из них свой подход к расчету матрицы подобия [1].

· User-based

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

Таблица 2. Пример расчета подобия пользователей.

	Item 1	Item 2	Item 3	…	Item n
User 1	2	3	-	…	5
User 2	3	4	3	…	4
User 3	3	2	-	…	3
…	…	…	…	…	…
User n	1	-	5	…	4

· Item-based

При использовании данного типа используется уже мера подобия двух объектов, рассчитывается она на основе оценок объектов от тех пользователей, которые оценили оба сравниваемых объекта (табл. 3) [5]:



Таблица 3. Пример расчета подобия объектов.

	Item 1	Item 2	Item 3	…	Item n
User 1	2	3	-	…	5
User 2	3	4	3	…	4
User 3	3	2	-	…	3
…	…	…	…	…	…
User n	1	-	5	…	4

Таким образом в обоих подходах формируется два вектора оценок равной длинны (в первом случае оценок пользователя, во втором - объекта), затем вычисляется одна из мер схожести, которые будут рассмотрены в разделе 1.4. «Методы построения рекомендательных систем».

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

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

· Высокая точность

· Простая реализация

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

· Высокая универсальность подхода

Метод коллаборативной фильтрации является самым универсальным подходом, так как не требует никакой информации об объектах и предметной области

Главным недостатком этого типа систем является проблема «холодного старта», это недостаток информации о пользователях или объектах в начале работы сервиса. Более подробно эта проблема будет рассмотрена в следующем разделе.

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

Content base (основанные на контенте)

Content-base рекомендательные системы предлагают рекомендации на основе информации, собранной о конкретном товаре. Рекомендации такого типа используют знания о предметах и игнорируют оценки пользователей этих объектов. В качестве входящей информации системы используют свойства рассматриваемых объектов, такие как производитель, автор, жанр и так далее [8].

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

Преимуществами Content-base рекомендательных систем являются:

· Возможность осуществить рекомендацию новому пользователю

· Возможность осуществить рекомендация новых объектов

Недостатками такого вида рекомендательных систем являются:

· Невысокая точность

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

· Высокое время разработки

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

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

Knowledge-based (основанные на знаниях)

Раньше часто можно было встретить, что рекомендательные системы типа Content-base выделяются как частный случай knowledge-based рекомендательных систем, однако рекомендательные системы, основанные на контенте, стали настолько популярными, что теперь их рассматривают как отдельный тип.

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

· Case-based

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

· Demographic-based

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

· Utility-based

Рекомендация объектов происходит на основе расчета его полезности для пользователя

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

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

· Высокая точность

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

Недостатками такого вида рекомендательных систем являются:

· Высокая сложность разработки

Этот недостаток вытекает из преимуществ knowledge-base систем. Для качественной проработки и настройки такой системы потребуются глубокое знание предметной области, квалифицированные специалисты и немало времени

· Сбор данных

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

Данный тип рекомендательных систем широко используется среди крупных интернет-магазинов, в их числе российский сервис Связной.

Hybrid (гибридные)

Любые комбинации вышеперечисленных типов относят к гибридным рекомендательным системам. Наиболее активно применяется комбинация коллаборативной фильтрации с рекомендациями, основанными на контенте [3]. Это помогает компенсировать недостатки отдельно взятых типов, например, сильно уменьшает влияние проблемы холодного старта для коллаборативной фильтрации.

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

1.4 Методы построения рекомендательных систем

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

Collaborative filtering

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

Меры сходства можно разделить на несколько типов:

· Сходство, основанное на расстоянии

· Корреляции как сходства

· Другие меры сходства

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

Сходство, основанное на расстоянии

Для определения сходства между объектами или признаками можно вычислить евклидово расстояние или расстояние Хемминга. Евклидово расстояние -- это геометрическое расстояние в многомерном пространстве. Для вычисления евклидового расстояния между двумя точками x и y в n-мерном пространстве используется формула:

,

Расстояние Хемминга - это метрика различия объектов, которые представлены в виде бинарного множества, одинаковой размерности. Расстояние будет равно количеству разных координат сравниваемых векторов:

,

Также в качестве меры сходства, основанной на расстоянии может использоваться Манхэттенское расстояние.

Корреляции как сходства

Часто как меру сходства в рекомендательных системах используют коэффициент корреляции Пирсона.

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

,

где , - оценки пользователей

, - средняя оценка пользователя

n - количество элементов

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

Другие меры сходства

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

Косинусная мера для двух векторов -- это косинус угла между рассматриваемыми векторами, другими словами, это скалярное произведение векторов, деленное на длину каждого из двух векторов.

,

Singular Value Decomposition (SVD)

Метод базируется на теореме о сингулярном усеченном разложении матрицы:

,

где в случае рекомендательных систем

· R - это user-item матрица размерностью , описанная в главе 1

· U - это матрица «признаков» пользователя размерностью ,

· D - диагональная матрица некоторых значений, которые можно назвать «весами» признаков, и размерностью

· V - матрица признаков объекта размерностью

· k - количество признаков, которые будут учитываться (чем меньше, тем более высокая степень усечения)

· N - количество пользователей

· M - количество объектов

Можно сказать, что матрица U демонстрирует насколько сильно пользователю нравится тот или иной признак объекта. А матрица V показывается насколько объект соответствует тому или иному признаку. Для упрощения обычно сразу выполняют умножение матрицы U на D (далее под матрицей U будет подразумеваться именно это произведение), таким образом получают матрицу, которая отражает насколько пользователю нравится каждый признак, и насколько он для него важен.

Благодаря данному разложению, можно уменьшить число параметров с , до , что является очень существенным, так как на практике N и M измеряются в тысячах и миллионах (пользователи и объекты, участвующие в рекомендательной системе), тогда как задается вручную и обычно измеряется в десятках. При этом матрица , построенная на сокращенном множестве параметров, дает приближение исходной матрицы R [9].

Теперь чтобы предсказать оценку пользователя для объекта необходимо взять некий вектор - набор параметров пользователя из матрицы U, и вектор (параметры объекта из матрицы V), и выполнить их скалярное произведение. В результате мы получим искомую оценку пользователя .

,

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

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

,

,

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

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

,

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

k-Means

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

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

Существует множество различных алгоритмов кластеризации, но мы рассмотрим один из наиболее популярных алгоритмов. K-means является одним из самых простых и в тоже время эффективным алгоритмом кластеризации. Алгоритм его работы довольно легко понять[12]:

1. Задается определенное число кластеров - k.

2. Случайным образом выбираются k объектов, которые объявляются центрами кластеров.

3. Всем объектам присваивается значение того кластера, центр которого является к этой записи ближайшим.

4. Затем вычисляются центры каждого кластера, которые называются центроиды. Центр класса смещается к своему центроиду.

5. Шаги 3-4 повторяются до тех пор, пока центроиды не перестанут смещаться и на каждой итерации объекты, принадлежащие одному кластеру, перестанут меняться.

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

В рамках применения k-means в коллаборативных рекомендательных системах пользователи разбиваются на заданное количество кластеров. Затем пользовательская оценка объекта предсказывается на основе среднего значения отклонения оценки этого объекта внутри кластера от среднего рейтинга объекта, это не единственный способ предсказать оценку используя данный метод [6]. Существует множество вариаций в выполнении финального действия, в котором могут учитываться разные факторы, однако главной особенностью, которая остается неизменной, является то, что предсказания выполняются внутри кластера. Это и есть основное преимущество использования алгоритма кластеризации для построения рекомендаций, так как тогда не приходится вычислять меру сходства между всеми объектами или признаками, а только внутри одного кластера, это помогает существенно снизить затраты на вычислениях по сравнению с классическим подходом коллаборативной фильтрации.

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

1.5 Критерии оценки качества рекомендательной системы

Очевидно, что всегда необходимо иметь возможность оценить качество рекомендательной системы. Можно выделить несколько критериев, по которым это самое качество нужно оценивать [11]:

· Точность

Действительно ли рекомендованные объекты подходят пользователю

· Покрытие

Какая часть объектов из всего множества объектов, может быть рекомендована

· Скорость обучения

Как быстро рекомендательная система способна выдать список из объектов, рекомендованных пользователю

· Степень новизны

Выданные системы рекомендации должны быть новыми для пользователя, вряд ли кому-то интересно увидеть в рекомендованных список самых популярных товаров, о которых и так всем известно

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

Precision

Precision или точность определяется как доля рекомендованных объектов, которые интересны пользователю, среди всех рекомендованных объектов [10].

Recall

Recall или полнота - это доля объектов, которые были рекомендованы системой, среди всех объектов, которые интересны пользователю [4].

На рисунке эти показатели можно отразить следующим образом (рис. 2):

Рис. 2. Расчет метрик Recall и Precision.



,

,

F1 score

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

Рассчитывается по следующей формуле:

,

Метрики Precision, Recall и F1 могут применяться для оценки любого типа рекомендательных систем, однако стоит учитывать, что в случае, когда одно из множеств z или y значительно больше другого, предпочтительно использовать метрику F1.

Root mean square deviation (RMSE)

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

Данная метрика рассчитывается по формуле:

,

Кратко алгоритм оценки качества рекомендательной системы и расчета рассмотренных метрик можно описать следующими шагами на примере системы коллаборативной фильтрации:

1. Из реальной user-item матрицы вырезается часть данных как тестовое множество.

2. Система строит рекомендации для тестового множества.

3. В сравнении с выданными рекомендациями и реальными значениями вычисляются рассмотренные метрики.

1.6 Проблемы

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

· Отсутствие информации о пользователе

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

· Высокая разреженность в данных

Из-за того, что большинство пользователей не оценивают большинство предметов, в данных возникает высокая степень разреженности [13].

· Холодный старт

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

· «Белые вороны»

Так называют пользователей, мнение которых постоянно не совпадает с мнением большинства. Из-за их особенностей во вкусе им трудно что-то рекомендовать, так как тяжело найти похожих на них пользователей [7].

· Масштабируемость

Увеличение количества пользователей и объектов может существенно увеличить время выдачи рекомендаций.

· Поддельные оценки

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

Отразить основные недостатки каждого из типов рекомендательных систем можно отобразить на следующей схеме (рис. 3):

Рис. 3. Схема недостатков по типам рекомендательных систем.



Глава 2. Разработка систем. Описание методов и их особенностей реализации в данной работе

2.1 Описание используемых данных

В рамках данной работы для создания и сравнения рекомендательных систем будут использоваться данные с веб-сайта MovieLens. Набор данных представляет из себя следующий набор файлов:

1. Movies.csv

Файл movies.csv содержит информацию о фильмах, которые представлены в данном наборе данных. Файл содержит следующую информацию:

· movieId - id фильма.

· title - название фильма, также в скобках после название указана дата выхода.

· genres - жанры фильмы, которые указаны через разделитель.

Пример данных (табл. 4):

Таблица 4. Пример входных данных movies.csv

movieId	title	genres
1	Toy Story (1995)	Adventure|Animation|Children|Comedy|Fantasy
2	Jumanji (1995)	Adventure|Children|Fantasy
3	Grumpier Old Men (1995)	Comedy|Romance

В файле приведено 9 125 уникальных фильмов. Уникальных жанров, которые присваиваются фильмам - 20. Как видно из примера, каждому фильму может быть присвоено более одного жанра, от 1 до 10. Посмотрим на то, фильмы каких жанров чаще всего встречаются в данных, а заодно и посмотрим на все возможные жанры (рис. 4):



Рис. 4. График количества фильмов по жанрам

Видно, что фильмы жанров драма и комедия встречаются в разы чаще, чем фильмы всех других жанров. Эта особенность также будет оказывать влияние на рекомендательные системы, построенные на типах content based и knowledge based.

В наборе файлов представлены фильмы разных годов, начиная с 1902 года, хотя и такой фильм всего один, и заканчивая фильмами, выпущенными в 2016 году (рис. 5).

Рис. 5. График количества фильмов по годам выпуска.

Преимущественно в базе MovieLens присутствуют фильмы, произведенные в 1990 - 2010 годах.

2. Links.csv

Данный файл используется для того, чтобы указать каждому фильму его id в других крупных базах данных о фильмах, imbd.com и tmdb.com.

Поля, содержащиеся в файле:

· movieId - id фильма.

· imdbId - id фильма на imdb.com

· tmdbId - id фильма на tmdb.com

Пример входных данных (табл. 5):

Таблица 5. Пример входных данных links.csv

movieId	imdbId	tmdbId
1	114709	862
2	113497	8844
3	113228	15602

Благодаря данному соответствию можно будет легко найти страницу нужного объекта в двух самых крупных базах данных, посвященных фильмам, там можно найти более детальную информацию, например, информацию об актерах и режиссере. Эти факты могут быть особенно полезными при построении knowledge based рекомендательных систем.

3. Tags.csv

Файл tags.csv дает нам возможность взглянуть на теги, которые пользователи поставили к фильмам. Тегом в данном случае является вручную введенное слово или короткая фраза. Данный файл состоит из 1 296 строк, в которых представлены теги для 61 пользователя и 689 фильмов. Поля:

· userId - id пользователя

· movieId - id фильма

· tag - значение тега

· timestamp - время заполнения тега, представленное в формате UNIX timestamp (количество секунд прошедшее с 01.01.1970)

Пример входных данных (табл. 6):

Таблица 6. Пример входных данных tags.csv

userId	movieId	tag	timestamp
15	34162	forgettable	1141391765
68	2174	music	1249808064
77	1199	Trilogy of the Imagination	1163220043

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

4. Ratings.csv

Наиболее важный файл, который дает возможность использовать с данным набором данных рекомендательные системы построенные на основе collaborative filtering. Файл состоит из 100 004 записей. Уникальных пользователей, поставивших оценки - 671. Уникальных оцененных фильмов - 9 066. Поля:

· userId - id пользователя

· movieId - id фильма

· rating - оценка, которую поставил пользователь данному фильму

· timestamp - время заполнения тега, представленное в формате UNIX timestamp (количество секунд прошедшее с 01.01.1970)



Таблица 7. Пример входных данных ratings.csv

userId	movieId	rating	timestamp
1	31	2.5	1260759144
2	17	5.0	835355681
4	435	1.0	949920135

Диапазон выставляемых оценок от 1.0 до 5.0 с шагом 0.5. Если пользователь не оценивал фильм, то записи об этом в файле не будет. Так как данный файл, является основополагающим в дальнейшем построении рекомендательных систем, рассмотрим его более детально.

Для каждого пользователя из данного файла присутствует минимум 20 оценок фильмов. Медиана количества оценок пользователей расположилась на отметке 71 оценки. При этом 75 процентов пользователей имеют не более 161 оценки. Для одного из пользователей имеются данные об оценках для 2 391 фильма.

Максимальное количество оценок для одного фильма - 341. Медиана количества оценок для фильмов - 3. Однако 3 063 фильма оценены лишь по одному разу, а 75 процентов фильмов не были оценены более 9 раз. Такие показатели не являются самыми лучшими, так как данные имеют высокую степень разреженности, что может отрицательно сказаться на качестве предсказаний.

2.2 Практическая реализация рекомендательных систем

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

· pandas, numpy - обработка данных

· surprise - реализация рекомендательных систем

· sklearn - вычисление метрик качества рекомендаций

· seaborn, matplotlib - визуализация и построение графиков

Collaborative filtering

Для построения рекомендательной системы user-based коллаборативной фильтрации на основе корреляции Пирсона было реализовано несколько функций:

· getcorrelation (dat, u1, u2)

Данная функция принимает на вход три параметра:

1. dat - user-item матрица

2. u1 - id пользователя 1

3. u2 - id пользователя 2

Функция использует матрицу оценок и рассчитывает значение коэффициента корреляции Пирсона между пользователями, указанными во входных параметрах. В качестве порога минимально совместно оцененных объектов выставлено значение 5, то есть если указанные пользователи совместно оценили менее 6 объектов, возвращается значение корреляции 0. Это сделано для того, чтобы избежать получения высокой меры сходства между пользователями, которые оценили вместе, например, только один объект, так как этого явно недостаточно, чтобы сделать вывод о том, что они похожи. Продемонстрируем пример работы функции рассчитав схожесть нескольких пользователей между собой (рис. 6):

Рис. 6. Пример использования функции getcorrelation()

Благодаря данной функции мы видим, что пользователи 2 и 20 абсолютно не похожи, в то время как пользователи 202 и 20 имеют довольно много общего.

· findsimusers(dat, user, n = 5, similarity=getcorrelation)

Функция для поиска пользователей с максимальной мерой сходства принимает на вход четыре параметра:

1. dat - user-item матрица

2. user - id пользователя

3. n - количество пользователей

4. similarity - функция для расчета сходства, в случае если необходимо будет заменить меру сходства

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

Для примера работы функции найдем наиболее похожих пользователей для пользователей 10 и 20 (рис. 7).

Рис. 7. Пример использования функции findsimusers().

· getmemovies (dat, user, movies, n=5, similarity=getcorrelation)

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

1. dat - user-item матрица

2. user - id пользователя

3. movies - матрица фильмов

4. n - количество рекомендаций

5. similarity - функция сходства

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

Пример использования функции. Порекомендуем пользователям с id 26, 19, 5 и 40 по одному фильму (рис. 8).

Рис. 8. Пример использования функции getmemovies().

Как мы видим для пользователей 26, 19 и 5 удалось выполнить неплохие рекомендации, система предсказала довольно высокие оценки. Однако с пользователем 40 не удалось выполнить таких качественных рекомендаций. По всей видимости для этого пользователя не удалось найти достаточно похожих пользователей.

SVD

Рекомендательная система, основанная на методе SVD, была реализована с использованием бесплатной библиотеки Surprise для Python. В данной библиотеке уже реализовано несколько функций и методов необходимых для построения рекомендательных систем, что позволяет упростить практическую реализацию.

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

Выполнив такую обработку данных, можно построить рекомендательную систему используя SVD разложение, которое реализовано в методах библиотеки. В качестве параметров разложения было выбрано количество факторов равное 100. Это означает, что вектор параметров пользователя и объекта, которые были описаны в главе 1, имеют размерность 100.

k-Means

Метод k-Means также был реализован с помощью библиотеки Surprise, и ее встроенных методов. В данном случае также использовалась матрица, в которой были проставлены нули для тех объектов, которые пользователем не были оценены.

Пользователи были кластеризованы на 40 кластеров, данный параметр является гиперпараметром для метода k-means, это значит, что алгоритм не оптимизирует этот параметр, но напрямую от него зависит. В машинном обучении для этого часто используют метод GridSearch, который автоматически выполняет проход по всей сетке параметров, то есть построение моделей по заданному подмножеству параметров и возвращает тот набор параметров, который показал наивысшее качество.

В качестве меры расстояния между объектами было выбрано косинусное расстояние, оно также было подобрано с помощью метода GridSearch.



Глава 3. Результаты применения рекомендательных систем

3.1 Оценка качества построенных моделей

Для оценки качества моделей были выбраны следующие метрики:

1. RMSE

2. Precision

3. Recall

4. F1 - score

Значение и способ вычисления этих метрик уже были описаны в главе 1. Для расчета данных метрик было выделено случайное множество в размере 25% от всех данных, таким образом в тестовой выборке оказалось 25 001 оценок.

Расчет метрики RMSE не представляет в данном случае никаких трудностей, так как существуют несколько библиотек позволяющих ее расcчитать. Такая функция есть как в sklearn, так и в библиотеке surprise.

Однако расчет метрик Precision и Recall не настолько очевиден и довольно вариативен, поэтому была реализована функция:

precision_recall_at_k (predictions, k=10, threshold=3.5)

Входные параметры:

1. predictions - таблица со столбцами userId, movieId, true_r (реальная оценка), pred_r (предсказанная оценка)

2. k - количество рассматриваемых объектов

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

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

Так же и параметр threshold может быть довольно вариативным и зависит как минимум от системы измерения принятой для выставления оценок. Так как в рассматриваемом наборе данных максимальная оценка объекта равна 5, то предположим, что объекты с оценкой более или равной 3.5 будут считаться интересными для пользователя.

Теперь рассчитаем эти метрики у построенных рекомендательных систем.

Collaborative filtering

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

cv_user (dat, test_ratio, similarity = getcorrelation)

Входные параметры:

1. dat - user-item матрица

2. test_ration - размер тестовой выборки в процентах

3. similarity - функция меры сходства

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

Таблица 8. Пример таблицы для оценки качества модели.

userId	movieId	true_r	pred_r
15	34162	forgettable	1141391765
68	2174	music	1249808064
77	1199	Trilogy of the Imagination	1163220043

Теперь с помощью библиотеки sklearn вычислим RMSE и вычислим Precision и Recall через функцию precision_recall_at_k. Получим следующие результаты (табл. 9):

Таблица 9. Метрики качества алгоритма CF.

Метрика	Значение
RMSE	1.25
Precision	0.83
Recall	0.68
F1-score	0.75

SVD

Так как данный алгоритм реализовывался с помощью сторонней библиотеки, в ней уже предусмотрена функция по расчету RMSE. Вычисление метрик Precision и Recall также будет выполнено с помощью функции precision_recall_at_k. Полученные результаты (табл. 10):

...