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

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

Оглавление

• Введение
• 1. Анализ формальных понятий
• 1.1 Основные определения
• 1.2 Узорные структуры
• 1.2.1 Введение в узорные структуры
• 1.2.2 Интервалы в качестве узоров
• 1.2.3 Интервальные векторы в качестве узоров
• 1.3 Выводы и результаты по главе
• 2. Рекомендательные системы и алгоритмы
• 2.1 Существующие подходы
• 2.1.1 Фильтрация содержимого
• 2.1.2 Коллаборативная фильтрация
• 2.2 Подход Slope One
• 2.2.1 Модельный пример
• 2.3 Подход на основе узорных структур (RAPS)
• 2.3.1 Модельный пример
• 2.4 Выводы и результаты по главе
• 3. Машинные эксперименты
• 3.1 Данные
• 3.2 Точность и полнота
• 3.3 Програмные средства
• 3.4 Эксперименты и оценка результатов
• 3.5 Выводы и результаты по главе
• Список литературы
• Приложение 1
• Приложение 2
• Приложение 3
• Приложение 4
• Приложение 5



Введение

Прежде всего, необходимо дать определение рекомендательной системы. Рекомендательные системы - это специальные программы, главная цель которых заключается в формировании рекомендаций различных продуктов или сервисов для пользователей на основе их предпочтений [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 и алгоритм рекомендаций на основе узорных структур с примерами применения. Заключительная часть посвящена проведенным экспериментам и всему с ними связанному.



1. Анализ формальных понятий

1.1 Основные определения

Базовые определения анализа формальных понятий мы используем из [1].

Пусть и - некоторые множества, а - бинарное отношение между и , такое что , то есть- - подмножество их декартового произведения. Тогда тройка называется формальным контекстом. Элементы множества принято называть объектами, а элементы множества называют признаками формального контекста Попросту говоря, пара (или ) означает, что и находятся в бинарном отношении и это можно интерпретировать как “объект имеет признак ”. Два оператора , определяемые ниже, задают соответствие Галуа между и :

(1.1)

(1.2)

Оператор (1.1) для некоторого множества объектов возвращает максимальное множество признаков, которыми обладает каждый объект из множества . Аналогичным образом, оператор (1.2) для некоторого множества признаков возвращает максимальное множество объектов, которые обладают всеми признаками из .

Теперь определим формальное понятие. Пара , где и , называется формальным понятием, если она удовлетворяет условиям: и . В этом случае множество объектов называется объемом формального понятия , а множество признаков называется содержанием формального понятия .

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

1.2 Узорные структуры

Вся информация в данном разделе взята из источников [2] и [3].

1.2.1 Введение в узорные структуры

Пусть - некоторое множество объектов, - множество всех возможных узоров (patterns), которые также называют описаниями объектов. Пусть - операция сходства (similarity operator). Эта операция позволяет нам работать с объектами, которые в качестве признаков имеют не бинарные признаки, как в классическом анализе формальных понятий, а признаки со сложным описанием, например интервалом или графом. Тогда полурешетка пересечений (meet-semi-lattice) описаний объектов. Отображение сопоставляет объекту описание .

Тройку будем называть узорной структурой. Два оператора определяемые ниже задают соответствие Галуа между и :

(1.3)

(1.4)

Оператор (1.3) будем называть первым оператором Галуа (derivation operator). Он для множества объектов возвращает общее максимальное описание (узор) всех объектов из . Оператор (1.4) будем называть вторым оператором Галуа. Он для описания возвращает множество всех объектов, которые разделяют описание .

Пара , где и , называется узорным понятием узорной структуры , если она удовлетворяет двум условиям: и . В этом случае множество объектов называется объемом узорного понятия (A, d), а описание называется содержанием узорного понятия .

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

1.2.2 Интервалы в качестве узоров

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

(1.5)

Откуда очевидно, что:

(1.6)

Также необходимо сделать замечание о том, что действительное число можно представить интервалом

1.2.3 Интервальные векторы в качестве узоров

Будем называть p-размерные векторы интервалов интервальными векторами. В данном случае для интервальных векторов одинаковой размерности и определим операцию сходства как пересечение соответствующих координат интервальных векторов, то есть:

(1.7)

Следует заметить, что интервальные векторы могут быть также частично упорядочены:

(1.8)

1.3 Выводы и результаты по главе

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



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

2.1 Существующие подходы

При написание данного раздела использовались источники [4] и [5].

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

2.1.1 Фильтрация содержимого

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

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

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

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

2.1.2 Коллаборативная фильтрация

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

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

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

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

2.2 Подход Slope One

Slope One - это один из самых простых подходов к рекомендациям на основе коллаборативной фильтрации по схожести предметов, но в то же время точность рекомендаций алгоритма сравнима с более сложными и ресурсоемкими алгоритмами [6]. Он был разработан Даниелем Лемайром и Анной Маклахман в 2004 году и опубликован в 2005 году в статье [6].

Slope one будет использоваться в данном исследовании при проведении экспериментов для сравнения полученных результатов от подхода на основе узорных структур.

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

Таблица 2.1. Оценки фильмов пользователями

user\movie		…		…
		…		…
…	…		…		…
		…		…
…	…		…		…
		…		…

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

Теперь перейдем непосредственно к алгоритму:

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

2) В первую очередь находим множество всех фильмов оцененных пользователем .

3) Для каждого неоцененного фильма пользователем выполняем шаг 4), тем самым считая прогнозируемую оценку для фильма . После этого переходим к шагу 5).

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

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

5) К данному шагу алгоритм подсчитал все возможные прогнозируемые оценки для фильмов из множества .

Алгоритм рекомедует все фильмы с оценками , учитывая минимальную и максимальную допустимые оценки.

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

2.2.1 Модельный пример

Рассмотрим работу алгоритма Slope One на простом примере:

Таблица 2.2. Пример данных для Slope One

user\movie

Попробуем предсказать оценку фильму .

1) Пусть , , и .

2) Находим - множество оцененных пользователем фильмов.

3)

4)

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

2.3 Подход на основе узорных структур (RAPS)

Подход к формированию рекомендаций на основе узорных структур главным образом базируется на теории, представленной в главе 1. Было принято решение дать ему название RAPS (Recommender Algorithm based on Pattern Structures).

Данный метод, как и рассмотренный выше метод Slope One, работает с оценками объектов, полученных от пользователей. Аналогично, если - множество фильмов, - множество пользователей, то пользовательские оценки объектов удобно представить таблицей (Таблица 2.1.). Оценки могут быть целыми числами от до , или, если пользователь не смотрел фильм, то вместо оценки будет стоять , то есть отсутствие оценки.

Опишем сам алгоритм:

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

2) Определяем множество фильмов , которые понравились пользователю, то есть те фильмы, которым пользователь поставил оценку в интервале от до .

3) На этом шаге для каждого фильма , применяем формулу 1.4., находим множество пользователей, которым этот фильм также понравился: .

В результате получим набор множеств пользователей:

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

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

5) На последнем шаге вычисляем вектор

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

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

Проанализируем временную сложность данного алгоритма. Шаг 2) выполняется за , шаги 3), 4) и 5) за каждый. Следовательно, временная сложность данного алгоритма .

2.3.1 Модельный пример

Рассмотрим работу алгоритма на примере:

Таблица 2.3. Пример данных для подхода на основе узорных структур

user\movie

Попробуем сформулировать рекомендации для пользователя :

1) На вход отправляем алгоритму: , и .

2)

3)

4)

.

Например интервал считали так:

. Аналогично и другие интервалы.

5) Исходя из заданных левой и правой границы, из алгоритм рекомендует фильмы и , из рекомендует , и .

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

2.4 Выводы и результаты по главе

В данной главе были рассмотрены основные подходы к рекомендациям: коллаборативная фильтрация и фильтрация содержимого. Затем был рассмотрен метод рекомендаций Slope One, который в дальнейшем будет использоваться как базовый при проведении экспериментов. Наконец, был представлен разработанный подход к формированию рекомендаций на основе узорных структур (RASP).



3. Машинные эксперименты

3.1 Данные

Для практических испытаний разработанного метода рекомендаций на основе узорных структур (RAPS), было принято решение воспользоваться свободно распространяемыми данными оценок фильмов, которые были собраны с сентября 1997 года по апрель 1998 года с помощью вебсайта MovieLens (movielens.umn.edu). Сбор данных проходил в рамках проекта The GroupLens Research Project Университета Миннесоты.

В выбранных данных представленно 100000 оценок по 1682 фильмам от 943 различных пользователей. Причем каждый пользователь в этих данных поставил оценки не менее, чем 20 фильмам.

Данные представляют собой 100000 строк вида:

user id | item id | rating | timestamp

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

3.2 Точность и полнота

Для сравнивания методов рекомендаций Slope One и RAPS первоначально было принято решение воспользоваться стандартными мерами точности (precision) и полноты (recall):

(3.1)

(3.2)



Рисунок 3.1. Множества рекомендованных и релевантных фильмов

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

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

Тогда для сравнивания методов рекомендаций Slope One и RAPS была разработана модификация точности (precision) и полноты (recall), которые мы будем называть скорректированными точностью и полнотой.

Для каждого конкретного пользователя множество просмотренных им фильмов разбивается на два множества: множество фильмов, на которых обучаются алгоритмы (train movies), и множество контрольных фильмов (test movies). Первое множество состояло из 80% просмотренных фильмов, а второе соответственно из 20%. Причем фильмы из первого множества были оценены пользователем ранее, чем фильмы из второго множества. Для такого разбиения все оценки пользователя были упорядочены по времени проставления и потом поделены.

Итак, было принято решение скорректированную точность и полноту рассчитывать по формулам указанным ниже:

(3.3)

(3.4)

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

Рисунок 3.2. Множества рекомендованных, релевантных и контрольных фильмов

3.3 Програмные средства

Для выполнения сравнительного анализа методов Slope One и RAPS на языке программирования MATLAB было написано несколько программ:

1) data_load.m - эта маленькая программа загружает исходных данные и из них создает две разреженные (sparse) матрицы: матрицу оценок и матрицу времени. Эти матрицы сохраняются как глобальные переменные и используются при запуске других программ. Код программы с комментариями приведен в Приложении 1.

2) main.m - эта программа разбивает случайным образом исходное множество пользователей на два: train_users (80%) и test_users (20%).

Затем для каждого пользователя из test_users выполняются следующие шаги: множество просмотренных им фильмов разбивается на множество фильмов, на которых будут обучаться алгоритмы (train movies), и множество контрольных фильмов (test movies) таким образом, как это было описано в разделе 3.2. Далее запускаются рекомендательные алгоритмы RAPS и Slope One с различными параметрами. И в конце вычисляются точность и полнота так же, как описано выше по формулам (3.3) и (3.4). Код программы с комментариями приведен в Приложении 2.

3) raps.m - эта функция является реализацией алгоритма RAPS описанного в разделе 2.3. Код функции с комментариями приведен в Приложении 3.

4) slope_one.m - эта функция является реализацией алгоритма Slope One описанного в разделе 2.2. Код функции с комментариями приведен в Приложении 4.

5) precision_and_recall.m - эта функция вычисляет скорректированную точность и полноту по формулам по формулам (3.3) и (3.4). Код функции с комментариями приведен в Приложении 5.

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

3.4 Эксперименты и оценка результатов

Как уже говорилось выше, для сравнения алгоритмов RAPS и Slope One мы воспользовались формулами точности (3.3.) и полноты (3.4.).

Все пользователи были случайным образом поделены на два множества: на 80% пользователей происходило обучение алгоритмов, а на 20% -тестирование. Причем, для каждого пользователя из контрольной выборки множество просмотренных им фильмов также делилось на два: 80% ранее просмотренных фильмов - для обучения алгоритмов, и 20% последних просмотренных - для тестирования.

Было проведено три серии тестов:

1) Когда хорошей оценкой считалась только оценка (интервал ).

2) Оценка считалась хорошей, если она лежала в интервале .

3) Хорошей оценкой фильма для рекомендации считалась любая оценка в интервале .

Все тесты проводились на компьютере под управлением OS X 10.9.3 с процессором Intel Core i7 2.3 ГГц и 8 ГБ оперативной памяти. Версия MATLAB - R2013a.

Средние значения результатов получились такими:

Таблица 3.1. Результаты экспериментов

	Среднее время, сек	Средняя точность, %	Средняя полнота, %
RAPS
Slope One
RAPS
Slope One
RAPS
Slope One

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

Из таблицы с результатами отчетливо видно, что алгоритм RAPS сильно опережает Slope One по всем критериям оценивания для начальных параметров .

Для параметров оба подхода имеют схожее среднее время работы и точность, но Slope One выдает в два раза менее полные рекомендации.

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

Из всего этого мы можем сделать вывод, что разработанный нами метод рекомендаций на основе узорных структур имеет право на существование. Метод Slope One уже давно применяется в реально работающих рекомендательных система [6], так что мы вполне можем рекомендовать разработчикам использовать разработанный нами метод рекомендаций на основе узорных структур.

3.5 Выводы и результаты по главе

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

Заключение

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

Проведенные эксперименты, сравнивающие методы RAPS и Slope One, показали, что рекомендательная система на основе узорных структур имеет достаточно неплохие показатели точности, полноты и время работы.

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

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

· Дальнейшее исследование и доработка метода RAPS.

· Исследование и разработка второго метода формирования рекомендаций на основе узорных структур. Есть предположение о том, что если брать второй оператор Галуа (1.4) не от одного фильма, как это делается в RAPS, а сразу от нескольких фильмов, например с высокими оценками, то могут получится хорошие результаты.

· Сравнение с моделями рекомендательных систем SVD и SVD++.



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

1) B. Ganter, R. Wille, Formal Concept Analysis, mathematical foundations ed., Springer, 1999.

2) B. Ganter, S.O. Kuznetsov, Pattern structures and their projections, H.S. Delugach, G. Stumme (Eds.), ICCS, LNCS, vol. 2120, Springer, 2001, pp. 129-142.

3) Mehdi Kaytoue, Sergei O. Kuznetsov, Amedeo Napoli, Sйbastien Duplessis, Mining gene expression data with pattern structures in formal concept analysis. Inf. Sci. 181(10), 2011, pp. 1989-2001.

4) Prem Melville and Vikas Sindhwani, Recommender Systems, Encyclopedia of Machine Learning, Claude Sammut and Geoffrey Webb (Eds), Springer, 2010.

5) Yehuda Koren, Robert M. Bell, Chris Volinsky, Matrix Factorization Techniques for Recommender Systems. IEEE Computer 42(8), 2009, pp. 42-49

6) Daniel Lemire, Anna Maclachlan, Slope One Predictors for Online Rating-Based Collaborative Filtering. SDM, 2005, pp. 471-475

7) Patrick du Boucher-Ryan, Derek G. Bridge, Collaborative Recommending using Formal Concept Analysis. Knowl.-Based Syst. 19(5), 2006, pp. 309-315



Приложение 1

data_load.m:

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

clc

clear all

global user_num;

global item_num;

user_num=943;

item_num=1682;

S = load('u.data', '-ascii');

global inf;

inf=sparse(user_num,item_num);

global timestamp;

timestamp=sparse(user_num,item_num);

for i=1:size(S,1)

inf(S(i,1),S(i,2))=S(i,3);

timestamp(S(i,1),S(i,2))=S(i,4);

end

clear S;

clear i;



Приложение 2

main.m:

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

1) Разбивает множество пользователей случайным образом на два множества train_users и test_users (80% и 20% соответственно).

2) Затем последовательно запускает алгоритм RAPS с параметрами хороших фильмов , , . Сохраняет полученные векторы рекомендаций number_of_recommendations для дальнейшего подсчета скорректированной точности и полноты, а также сохраняет затраченное время на каждый запуск. Тут нужно заметить, что алгоритм запускается для каждого пользователя из тестовой выборки: 80% первых оцененных фильмов (используем timestamp, в котором храниться время проставления оценки) идут на обучение метода, 20% последних оцененных потом будем использовать для оценивания результатов.

3) Запускаем алгоритм Slope One также для всех пользователей из тестовой выборки. Аналогично, 80% фильмов каждого пользователя для обучения. Параметры хороших фильмов для данного алгоритма здесь не важны, так как он возвращает нам вектор прогнозируемых оценок для каждого фильма ratings (который мы сохраняем для каждого пользователя). Рекомендованные фильмы из этих оценок мы вычислим при выполнении следующего шага.

4) Рассчитываем среднюю точность, полноту и время для алгоритмов RAPS и Slope One для параметров хороших фильмов , , .

5) Выводим полученные результаты.

Код (221 строка):

clc

global inf;

global timestamp;

global user_num;

global item_num;

min_border=1;

max_border=5;

%razbivaem ishodnuu viborku polzovateley na dve 80% i 20%

stime = RandStream('mt19937ar','Seed',333);

perm=randperm(stime,user_num);

train_users=(perm(1:round(user_num*0.8)))';

test_users=(perm((round(user_num*0.8)+1):user_num))';

clear stime;

clear perm;

%-----------------------raps55-----------------------------------------

left_border=5;

right_border=5;

time_raps55=[];

rec_raps55=[];

for i=1:size(test_users,1)

disp([num2str(size(test_users,1)),' ',num2str(i)])

user=test_users(i);

[i1,temp_index]=sort(timestamp(user,:));

clear i1;

temp_n=size(find(timestamp(user,:)),2);

train_items=(temp_index( (item_num-temp_n+1):(round(temp_n*0.8)+item_num-temp_n ) ))';

test_items=(temp_index( (round(temp_n*0.8)+item_num-temp_n+1):item_num ))';

clear temp_n;

clear temp_index;

tic;

[recommendations,number_of_recommendations]=raps(train_items,train_users,user,left_border,right_border,item_num);

time_raps55=[time_raps55; toc];

rec_raps55=[rec_raps55 number_of_recommendations];

end

%----------------------------------------------------------------------

%-----------------------raps45-----------------------------------------

left_border=4;

right_border=5;

time_raps45=[];

rec_raps45=[];

for i=1:size(test_users,1)

disp([num2str(size(test_users,1)),' ',num2str(i)])

user=test_users(i);

[i1,temp_index]=sort(timestamp(user,:));

clear i1;

temp_n=size(find(timestamp(user,:)),2);

train_items=(temp_index( (item_num-temp_n+1):(round(temp_n*0.8)+item_num-temp_n ) ))';

test_items=(temp_index( (round(temp_n*0.8)+item_num-temp_n+1):item_num ))';

clear temp_n;

clear temp_index;

tic;

[recommendations,number_of_recommendations]=raps(train_items,train_users,user,left_border,right_border,item_num);

time_raps45=[time_raps45; toc];

rec_raps45=[rec_raps45 number_of_recommendations];

end

%----------------------------------------------------------------------

%-----------------------raps35-----------------------------------------

left_border=3;

right_border=5;

time_raps35=[];

rec_raps35=[];

for i=1:size(test_users,1)

disp([num2str(size(test_users,1)),' ',num2str(i)])

user=test_users(i);

[i1,temp_index]=sort(timestamp(user,:));

clear i1;

temp_n=size(find(timestamp(user,:)),2);

train_items=(temp_index( (item_num-temp_n+1):(round(temp_n*0.8)+item_num-temp_n ) ))';

test_items=(temp_index( (round(temp_n*0.8)+item_num-temp_n+1):item_num ))';

clear temp_n;

clear temp_index;

tic;

[recommendations,number_of_recommendations]=raps(train_items,train_users,user,left_border,right_border,item_num);

time_raps35=[time_raps35; toc];

rec_raps35=[rec_raps35 number_of_recommendations];

end

%----------------------------------------------------------------------

%-----------------------sp-----------------------------------------

left_border=4;

right_border=5;

time_sp=[];

rec_sp=[];

for i=1:size(test_users,1)

disp([num2str(size(test_users,1)),' ',num2str(i)])

user=test_users(i);

[i1,temp_index]=sort(timestamp(user,:));

clear i1;

temp_n=size(find(timestamp(user,:)),2);

train_items=(temp_index( (item_num-temp_n+1):(round(temp_n*0.8)+item_num-temp_n ) ))';

test_items=(temp_index( (round(temp_n*0.8)+item_num-temp_n+1):item_num ))';

clear temp_n;

clear temp_index;

tic;

[recommendations,ratings]=slope_one(train_items,train_users,user,left_border,right_border,min_border,max_border,item_num);

time_sp=[time_sp; toc];

rec_sp=[rec_sp ratings];

end

%----------------------------------------------------------------------

%-----------------------precision and recall------------------------

precision_all_raps55=[];

recall_all_raps55=[];

precision_all_sp55=[];

recall_all_sp55=[];

precision_all_raps45=[];

recall_all_raps45=[];

precision_all_sp45=[];

recall_all_sp45=[];

precision_all_raps35=[];

recall_all_raps35=[];

precision_all_sp35=[];

recall_all_sp35=[];

for i=1:size(test_users,1)

%disp([num2str(size(test_users,1)),' ',num2str(i)])

user=test_users(i);

[i1,temp_index]=sort(timestamp(user,:));

clear i1;

temp_n=size(find(timestamp(user,:)),2);

train_items=(temp_index( (item_num-temp_n+1):(round(temp_n*0.8)+item_num-temp_n ) ))';

test_items=(temp_index( (round(temp_n*0.8)+item_num-temp_n+1):item_num ))';

clear temp_n;

clear temp_index;

left_border=5;

right_border=5;

recommendations=find(rec_raps55(:,i));

[precision,recall]=precision_and_recall(user,test_items,recommendations,left_border,right_border);

precision_all_raps55=[precision_all_raps55;precision];

recall_all_raps55=[recall_all_raps55;recall];

recommendations=find(rec_sp(:,i)>=left_border);

[precision,recall]=precision_and_recall(user,test_items,recommendations,left_border,right_border);

precision_all_sp55=[precision_all_sp55;precision];

recall_all_sp55=[recall_all_sp55;recall];

left_border=4;

right_border=5;

recommendations=find(rec_raps45(:,i));

[precision,recall]=precision_and_recall(user,test_items,recommendations,left_border,right_border);

precision_all_raps45=[precision_all_raps45;precision];

recall_all_raps45=[recall_all_raps45;recall];

recommendations=find(rec_sp(:,i)>=left_border);

[precision,recall]=precision_and_recall(user,test_items,recommendations,left_border,right_border);

precision_all_sp45=[precision_all_sp45;precision];

recall_all_sp45=[recall_all_sp45;recall];

left_border=3;

right_border=5;

recommendations=find(rec_raps35(:,i));

[precision,recall]=precision_and_recall(user,test_items,recommendations,left_border,right_border);

precision_all_raps35=[precision_all_raps35;precision];

recall_all_raps35=[recall_all_raps35;recall];

recommendations=find(rec_sp(:,i)>=left_border);

[precision,recall]=precision_and_recall(user,test_items,recommendations,left_border,right_border);

precision_all_sp35=[precision_all_sp35;precision];

recall_all_sp35=[recall_all_sp35;recall];

end

disp(['time_raps55 = ',num2str(sum(time_raps55)/size(test_users,1)) ]);

disp(['precision_average_raps55 = ',num2str(sum(precision_all_raps55)/size(test_users,1))])

disp(['recall_average_raps55 = ',num2str(sum(recall_all_raps55)/size(test_users,1))])

disp(' ')

disp(['time_sp55 = ',num2str(sum(time_sp)/size(test_users,1)) ]);

disp(['precision_average_sp55 = ',num2str(sum(precision_all_sp55)/size(test_users,1))])

disp(['recall_average_sp55 = ',num2str(sum(recall_all_sp55)/size(test_users,1))])

disp(' ')

disp(['time_raps45 = ',num2str(sum(time_raps45)/size(test_users,1)) ]);

disp(['precision_average_raps45 = ',num2str(sum(precision_all_raps45)/size(test_users,1))])

disp(['recall_average_raps45 = ',num2str(sum(recall_all_raps45)/size(test_users,1))])

disp(' ')

disp(['time_sp45 = ',num2str(sum(time_sp)/size(test_users,1)) ]);

disp(['precision_average_sp45 = ',num2str(sum(precision_all_sp45)/size(test_users,1))])

disp(['recall_average_sp45 = ',num2str(sum(recall_all_sp45)/size(test_users,1))])

disp(' ')

disp(['time_raps35 = ',num2str(sum(time_raps35)/size(test_users,1)) ]);

disp(['precision_average_raps35 = ',num2str(sum(precision_all_raps35)/size(test_users,1))])

disp(['recall_average_raps35 = ',num2str(sum(recall_all_raps35)/size(test_users,1))])

disp(' ')

disp(['time_sp35 = ',num2str(sum(time_sp)/size(test_users,1)) ]);

disp(['precision_average_sp35 = ',num2str(sum(precision_all_sp35)/size(test_users,1))])

disp(['recall_average_sp35 = ',num2str(sum(recall_all_sp35)/size(test_users,1))])

%--------------------------------------------------------------------------



Приложение 3

raps.m:

Этой функции на вход подается: множество оценок объектов данного пользователя (на которых происходит обучение), пользователи (на оценках которых обучаемся), номер пользователя (для которого хотим выдать рекомендации), левая и правая границы оценок хороших фильмов, количество имеющихся в базе объектов (фильмов). Эта функция работает с глобальной матрицей матрицей inf (определена выше). Алгоритм работает также, как и описано в разделе 2.3. На выходе: recommendations (список рекомендуемых фильмов), number_of_recommendations (сколько раз порекомендован каждый фильм).

Код (68 строк):

function [recommendations,number_of_recommendations]=raps(items,train_users,user,left_border,right_border,item_num)

global inf;

% %granici description

recommendations=[];

number_of_recommendations=zeros(item_num,1);

for k=1:size(items,1)

item=items(k);

if ((inf(user,items(k))>=left_border)&&(inf(user,items(k))<=right_border))

dleft=zeros(item_num,1);

dright=zeros(item_num,1);

% %nahodim polzovateley, kotorie ocenili film 'item'

set_users=[];

temp_index=find(inf(:,item));

for i=1:size(temp_index,1)

if ( (isempty( find( train_users==temp_index(i) ) )==false) && ...

(inf(temp_index(i),item)>=left_border)&&(inf(temp_index(i),item)<=right_border) )

set_users=[set_users; temp_index(i)];

end

end

size(set_users);

set_users;

% % sozdaem description na osnove etih polzovateley

for i=1:size(set_users,1)

temp_index=find(inf(set_users(i),:));

for j=1:size(temp_index,2)

item_i=temp_index(j);

item_r=inf(set_users(i),temp_index(j));

if ((dleft(item_i)==0)&&(dright(item_i)==0))

dleft(item_i)=item_r;

dright(item_i)=item_r;

elseif (dleft(item_i)>item_r)

dleft(item_i)=item_r;

elseif ((dleft(item_i)<item_r)&&(dright(item_i)<item_r))

dright(item_i)=item_r;

end

end

end

%dleft

%dright

% % vozvrashaem filmi, u kotorih granici >=left_border&&<=right_border

for i=1:item_num

if ( (dleft(i)>=left_border)&&(dright(i)<=right_border) )

number_of_recommendations(i)=number_of_recommendations(i)+1;

end

end

end

end

number_of_recommendations;

recommendations=find(number_of_recommendations);

for k=1:size(items,1)

recommendations(recommendations==items(k))=[];

end

end



Приложение 4

slope_one.m:

Этой функции на вход подается: множество оценок объектов данного пользователя (на которых происходит обучение), пользователи (на оценках которых обучаемся), номер пользователя (для которого хотим выдать рекомендации), левая и правая границы оценок хороших фильмов, левая и правая границы возможных (в данной модели) оценок, количество имеющихся в базе объектов (фильмов). Эта функция работает с глобальной матрицей матрицей inf (определена выше). Алгоритм работает также, как и описано в разделе 2.2. На выходе: recommendations (список рекомендуемых фильмов), ratings (вектор прогнозируемых оценок для каждого фильма).

Код (65 строк):

function [recommendations,ratings]=slope_one(train_items,train_users,user,left_border,right_border,min_border,max_border,item_num)

global inf;

ratings=zeros(item_num,1);

for i=1:size(train_items,1)

ratings(train_items(i))=inf(user,train_items(i));

end

ratings;

for i=1:item_num

if (ratings(i)==0)

P=0;%prognoz

R=0;

for j=1:size(train_items,1)

temp=(inf(train_users,i)).*inf(train_users,train_items(j));

temp_index=find(temp);%ishem S_j,i(train_items)

temp=inf(train_users,i)-inf(train_users,train_items(j));

card=size(temp_index,1);

if (card>0)

dev=0;

for k=1:card

dev=dev+temp(temp_index(k));

end

dev=dev/card;

P=P+dev+inf(user,train_items(j));

R=R+1;

end

end

if (R>=1)

P=P/R;

ratings(i)=P;

end

end

end

%ratings

recommendations=[];

for i=1:item_num

r=ratings(i);

if (r<min_border)

r=min_border;

end

if (r>max_border)

r=max_border;

end

if ((r>=left_border)&&(r<=right_border))

recommendations=[recommendations; i];

end

end

recommendations;

for k=1:size(train_items,1)

recommendations(recommendations==train_items(k))=[];

end

end



Приложение 5

precision_and_recall.m:

Эта функция вычисляет скорректированную точность и полноту как в разделе 3.2. Этой функции на вход подается: номер пользователя, множество оценок объектов данного пользователя (на которых происходит тестирование), полученные рекомендованные фильмы, левая и правая границы оценок хороших фильмов. Эта функция также работает с глобальной матрицей матрицей inf (определена выше). На выходе: precision (скорректированная точность), recall ( скорректированная полнота)

Код (35 строк):

function [precision,recall]=precision_and_recall(user,test_items,retrieved_items,left_border,right_border)

global inf;

for i=size(retrieved_items,1):-1:1

if (isempty( find(retrieved_items(i)==test_items) )==true)

retrieved_items(i)=[];

end

end

relevant_items=[];

for i=1:size(test_items,1)

if ( (inf(user, test_items(i))>=left_border)&&(inf(user, test_items(i))<=right_border) )

relevant_items=[relevant_items; test_items(i)];

end

end

%retrieved_items

%relevant_items

if (isempty(relevant_items)==true)

precision=0;

recall=1;

elseif (isempty(retrieved_items)==true)

precision=0;

recall=0;

else

temp=0;

for i=1:size(retrieved_items,1)

if ( isempty( find(relevant_items==retrieved_items(i)) )==false )

temp=temp+1;

end

end

precision=temp/size(retrieved_items,1);

recall=temp/size(relevant_items,1);

end

end

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

...