Создание прототипа рекомендательной экспертной системы, реализующей методы коллаборативной фильтрации на языке Python

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

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

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

 

 

2.1.2. Математическая постановка задачи коллаборативной фильтрации

 

 

Существует  список m-пользователей U = {u₁, u₂, …, u_m} и список n-объектов I = {i₁, i₂, …, i_n}, о которых пользователи выражают свое мнение, то есть оценивают их. Каждый пользователь u_i имеет список объектов I_ui, который он оценил. Оценка может происходить согласно числовой шкале: например, 10-балльная система. Множество I_ui принадлежит I и может быть пустым. Существует пользователь u_a U, называемый активным, для которого должен быть осуществлен поиск объектов.

Предсказание – это числовое значение P_a,j, показывающая степень похожести объекта i_j I_ua для активного пользователя u_a.

Рекомендация – это список из N объектов, I_r I, которые должны больше всего понравиться активному пользователю. Стоит заметить, что список должен состоять только из объектов, которые ранее активный пользователь не оценивал, то есть I_r I_ua = Φ.

На рисунке 5 показана схема процесса коллаборативной фильтрации: входные данные – список оценок, применение алгоритма, выходные данные – P_a,j предсказание объекта j для активного пользователя, {T_i1, T_i2, …, T_in} – список объектов для активного пользователя.

 

	i1	i2	…	ij	…	in
u1
u2
...
ua
…

 

 

Рисунок 5. Схема процесса алгоритма коллаборативной фильтрации

Алгоритм на входе получает матрицу предпочтений А с размерностью m × n. Каждый элемент a_i,j представляет собой оценку i-ого пользователя для j-ого объекта.

 

 

2.2. Функциональная модель рекомендательной экспертной системы

 

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

Функциональное  моделирование – это процесс моделирования функций, выполняемых информационной системой или объектом, путем создания описательного структурированного графического изображения, показывающего что, как и кем делается в рамках функционирования объектов, связывающих эти функции, с учетом имеющейся информации [11, с. 30]. Целью функционального моделирования является создание функциональной модели системы. Функциональная модель описывает место информационной системы в бизнес-процессе. Она показывает, каким образом выходные данные преобразуются по входным данным, не рассматривая порядок и способ реализации вычислений. Функциональная модель состоит из набора диаграмм потока данных, которые показывают потоки значений от внешних входов через операции и внутренние хранилища данных к внешним выходам [12, с. 91]. Функциональная модель способна обеспечить полное представление, как о функционировании обследуемого процесса, так и обо всех имеющих в нем место потоках информации и материалов.

Функциональную  модель работы рекомендательной экспертной информационной системы можно представить с помощью методологии описания бизнес-процессов – IDEF0. Процесс моделирования системы в IDEF0 начинается с создания контекстной диаграммы – диаграммы наиболее абстрактного уровня описания системы в целом, содержащей определение субъекта моделирования, цели и точки зрения на модель (рисунок 6). На данной диаграмме видно, что входным потоком являются оценки, выставленные ранее независимыми пользователями; при этом выходным – выступают рекомендации и прогнозы экспертной системы. Работа рекомендательной ЭИС выполняется по средствам реализации алгоритмов коллаборативной фильтрации, которые описываются набором правил и процедур. Экспертная система функционирует под управлением пользователя, обеспечивающего внесение информации о предпочтениях в базу данных. После этого, полученные данные будут обрабатываться алгоритмами с помощью интерпретатора Python. Целью функционирования рекомендательной экспертной системы является выработка рекомендаций пользователям, а также составление прогнозов на основе имеющего списка предпочтений.

Рисунок 6. Контекстная диаграмма работы рекомендательной ЭИС

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

Рисунок 7. Декомпозиция процесса работы экспертной системы

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

Стоит заметить, что методология IDEF0 является достаточно простым инструментом, который предназначен лишь для формализации и описания бизнес-процесса. При необходимости для более глубоко и детального изучения каждого из фрагментов модели можно воспользоваться диаграммой потоков данных – DFD и методологией описания бизнес-процессов – IDEF3.

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

 

2.3. Реализация  алгоритмов коллаборативной фильтрации

с помощью  языка Python

 

2.3.1. Сбор информации

 

Любая рекомендательная система производит свои результаты на основе имеющейся или полученной ранее информации. Поэтому первым шагом разработки прототипа рекомендательной экспертной системы является сбор информации о предпочтениях. Для реализации алгоритмов коллаборативной фильтрации необходимо создать базу данных кинофильмы. В качестве объектов выступают киносайты, в качестве образцов – фильмы. Заранее был определен минимальный набор сайтов: Imhonet.ru, Kinopoisk.ru, Cinemaxx.ru, Kinonews.ru, Imdb.com, каждый из которых представляет собственную оценку кинофильмам: «Морской бой», «Гладиатор», «Аватар», «Живая сталь», «Форсаж 5», «Время», «Мальчишник 2», «Призрачный гонщик 2», «Пункт назначения 5». Также для наглядной демонстрации работы некоторых алгоритмов совместной фильтрации в таблицу были добавлены мои собственные оценки, выставленные некоторым фильмам. В результате таблица предпочтений имеет следующий вид:

	Imhonet	Kinоpoisk	Cinemaxx	Kinonews	Imdb	Личные  оценки
Морской бой (Battleship)	7,4	7,3	9,0	8,1	6,5	–
Гладиатор (Gladiator)	8,1	8,6	10,0	8,5	8,4	7,8
Аватар (Avatar)	8,1	8,0	9,0	8,5	8,0	4,3
Живая сталь (Real Steel)	7,8	7,8	9,0	8,2	7,2	6,1
Форсаж 5 (Fast Five)	7,7	7,6	8,8	7,9	7,3	–
Время (In Time)	7,5	7,2	9,0	7,8	6,5	–
Мальчишник 2 (The Hangover Part 2)	7,3	7,2	10,0	7,6	–	–
Призрачный  гонщик 2 (Ghost Rider 2)	5,8	5,2	8,0	6,6	–	–
Пункт назначения 5 (Final Destination 5)	6,4	6,0	8,0	7,2	–	–

 

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

 

# Словарь киносайтов  и выставленные ими оценки  для набора фильмов

 

experts={'imhonet': {'Battleship': 7.4, 'Gladiator': 8.1,

'Avatar': 8.1, 'Real Steel': 7.8, 'Fast Five': 7.7,

'In Time': 7.5, 'The Hangover Part 2': 7.3,

'Ghost Rider 2': 5.8, 'Final Destination 5': 6.4},

'kinopoisk': {'Battleship': 7.3, 'Gladiator': 8.6,

'Avatar': 8.0, 'Real Steel': 7.8, 'Fast Five': 7.6,

'In Time': 7.2, 'The Hangover Part 2': 7.2,

'Ghost Rider 2': 5.2, 'Final Destination 5': 6.0},

'cinemaxx': {'Battleship': 9.0, 'Gladiator': 10.0,

'Avatar': 9.0, 'Real Steel': 9.0, 'Fast Five': 8.8,

'In Time': 9.0, 'The Hangover Part 2': 10.0,

'Ghost Rider 2': 8.0, 'Final Destination 5': 8.0},

'kinonews': {'Battleship': 8.1, 'Gladiator': 8.5,

'Avatar': 8.5, 'Real Steel': 8.2, 'Fast Five': 7.9,

'In Time': 7.8, 'The Hangover Part 2': 7.6,

'Ghost Rider 2': 6.6, 'Final Destination 5': 7.2},

'imdb': {'Battleship': 6.5, 'Gladiator': 8.4,

'Avatar': 8.0, 'Real Steel': 7.2, 'Fast Five': 7.3,

'In Time': 6.5},

'max': {'Gladiator': 7.8, 'Avatar': 4.3, 'Real Steel': 6.1, 'Fast Five': 9.8}}

 

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

Работа с Python будет происходить интерактивно с помощью командной строки. Допустим необходимо узнать, какую оценку выставил сайт Imhonet фильму «Аватар». Для этого в интерпретаторе командной строки Python введем следующие команды и получим результат:

Также в интерпретаторе можно вывести словарь experts с помощью команды print(experts):

 

 

 

 

 

2.3.2. Оценка похожести объектов

 

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

Оценка по евклидову расстоянию

Евклидово расстояние является наиболее простым способом вычисления оценки подобия. В этом случае предметы, которые оценивались сообща, представляются в виде координатных осей, в которых можно расположить точки, соответствующие людям, и выяснить, насколько они оказались близки. В нашем примере предметами будут являться фильмы, а оценки будут выставляться перечисленными выше сайтами. Рассмотрим пример вычисления оценки подобия различных сайтов для двух кинофильмов: «Гладиатор» и «Пункт назначения 5» (рисунок 8).

Рисунок 8. Сайты в пространстве предпочтений

На данной диаграмме показаны сайты, представленные точками в пространстве предпочтений. Ось Х системы координат будет соответствовать 10-ти балльной шкале оценок, выставленных фильму «Пункт назначения 5», а ось У – фильму «Гладиатор». Так, сайт Kinopoisk имеет координату 8,6 по оси Х и координату 6,0 по оси У. Соответственно, чем ближе два сайта в пространстве предпочтений, тем более схожи их оценки. Из диаграммы наглядно видно, что в оценках по фильмам «Гладиатор» и «Пункт назначения 5» наиболее близки сайты Imdb и Kinopoisk, при этом наиболее отдаленными являются Imdb и Cinemaxx. Данная диаграмма двумерная, поэтому одновременно можно смотреть только на два показателя, однако для большего числа показателей принцип остается тем же.

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

,

где d_ij – расстояние между объектами i и j, x_ik – значение k-го показателя для i-го объекта. Расстояние, вычисленное по этой формуле, будет тем меньше, чем больше сходства между объектами. Но необходимо написать функцию, значение которой будет тем больше, чем объекты более похожи друг на друга. Для этого добавим к вычисленному расстоянию 1 и воспользуемся обратной величиной. Теперь функция должна возвращать значения от 0 до 1, причем 1 получается, когда предпочтения объектов полностью совпадают.

Для возведения в квадрат в языке Python предназначена функция pow(n,2), а для извлечения квадратного корня – sqrt.

Листинг программы, вычисляющей оценку подобия по евклидову расстоянию на Python, представлен ниже:

from math import sqrt

 

# Возвратить  оценку подобия person1 и person2 на основе расстояния

def sim_distance(prefs,person1,person2):

  # Получить  список фильмов, оцененных обоими сайтами

  si={}

  for item in prefs[person1]:

    if item in prefs[person2]:

      si[item]=1