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

 

  # Если нет  ни одной общей оценки, вернуть  0

  if len(si)==0: return 0

 

  # Сложить квадраты разностей

  sum_of_squares=sum([pow(prefs[person1][item]-prefs[person2][item],2)

                      for item in prefs[person1] if item in prefs[person2]])

 

  return 1/(1+sqrt(sum_of_squares))

 

Попробуем найти  оценку подобия между сайтами Imhonet и Kinopoisk. Для этого в интерпретаторе вызовем функцию sim_distance:

Аналогично  найдем оценку подобия между сайтами Imdb и Cinemaxx:

Таким образом, можно пробовать различные варианты и наблюдать наибольшее или наименьшее совпадение предпочтений объектов.

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

Коэффициент корреляции Пирсона

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

Для визуализации этого метода можно нанести на диаграмму оценки, выставленные двумя киносайтами. Например, сайт Kinonews оценил фильм «Морской бой» на 8,1, а сайт Imhonet – на 7,4. Следовательно, получаем точку с координатами (8,1; 7,4). Аналогичным образом наносим все остальные точки, соответствующие фильмам (рисунок 9).

Рисунок 9. Диаграмма сравнение  двух киносайтов

На диаграмме изображена прямая линия, которая называется линией наилучшего приближения, поскольку она проходит максимально близки ко всем точкам. Если бы оба эксперта выставили всем фильмам одинаковые оценки, то эта линия оказалась бы диагональной и прошла бы через все точки. Коэффициент корреляции в этом случае равнялся 1 (идеальная корреляция). В нашем случае эксперты разошлись в оценках, поэтому коэффициент корреляции равен 0,86.

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

# Возвратить  коэффициент корреляции Пирсона  между p1 и p2

def sim_pearson(prefs,p1,p2):

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

  si={}

  for item in prefs[p1]:

    if item in prefs[p2]: si[item]=1

 

  # Если нет  ни одной общей оценки, вернуть 0

  if len(si)==0: return 0

 

  # Найти общее число элементов

  n=len(si)

 

  # Вычислить сумму всех предпочтений

  sum1=sum([prefs[p1][it] for it in si])

  sum2=sum([prefs[p2][it] for it in si])

 

  # Вычислить сумму квадратов

  sum1Sq=sum([pow(prefs[p1][it],2) for it in si])

  sum2Sq=sum([pow(prefs[p2][it],2) for it in si]) 

 

  # Вычислить сумму произведений

  pSum=sum([prefs[p1][it]*prefs[p2][it] for it in si])

 

  # Вычислить коэффициент Пирсона

  num=pSum-(sum1*sum2/n)

  den=sqrt((sum1Sq-pow(sum1,2)/n)*(sum2Sq-pow(sum2,2)/n))

  if den==0: return 0

 

  r=num/den

 

  return r

 

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

Введем в  интерпретаторе команду exp.sim_pearso(exp.experts, ‘imhonet’, ‘kinonews’) для вычисления коэффициента корреляции Пирсона для точек, изображенных на диаграмме (рисунок 9):

Из примера  видно, что оценка подобия киноэкспертов Imhonet и Kinonews достаточно велика.

Манхэттенское расстояние

Также хорошо известной мерой является манхэттенское расстояние, или «расстояние городских кварталов», которое определяется следующим образом:

,

где d_ij – расстояние между объектами i и j, x_ik – значение k-го показателя для i-го объекта. Данная метрика является средним разностей по координатам. В большинстве случаев эта мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида. Однако стоит отметить, что для этой меры влияние отдельных больших разностей (выбросов) уменьшается, так как они не возводятся в квадрат.

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

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

def sim_manhetten(prefs,person1,person2):

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

  si={}

  for item in prefs[person1]:

    if item in prefs[person2]:

      si[item]=1

 

  # Если нет  ни одной общей оценки, вернуть  0

  if len(si)==0: return 0

 

  # Сложить разности

  sum_r=sum(abs(prefs[person1][item]-prefs[person2][item])

                      for item in prefs[person1] if item in prefs[person2])

 

  return 1/(1+sum_r)

 

Воспользуемся функцией sim_manhetten для нахождения расстояния между экспертами Imdb и Cinemaxx:

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

 

2.3.3. Ранжирование объектов

 

Идея алгоритма  коллаборативной фильтрации состоит  в просмотре большой группы людей (пользователи сервиса) и отыскании в ней меньшей группы с такими же вкусами, как у конечного пользователя. Алгоритм сравнивает, какие еще вещи им нравятся, объединяет предпочтения и создает ранжированный список предложений. Рассмотрим пример ранжирования объектов. В качестве объектов в данном случае выступают киносайты. На основе алгоритма сравнения двух сайтов можно написать функцию, которая будет вычислять оценку подобия всех имеющихся сайтов с данным сайтом или пользователем и искать наилучшее соответствие. С помощью данной функции пользователь сможет ориентироваться на обзоры определенного сайта и принимать решение о выборе фильма. Естественно пользователя интересует именно тот сайт, который представляет оценки фильмов схожие с личными вкусами пользователя. Листинг реализации данной функции на языке Python представлен ниже.

 

# Возвратить  список наилучших соответствий  для сайта из словаря prefs

 

def topMatches(prefs,person,n=6,similarity=sim_pearson):

  scores=[(similarity(prefs,person,other),other)

                  for other in prefs if other!=person]

 

# Отсортировать  список по убыванию оценок

  scores.sort()

  scores.reverse()

  return scores[0:n]

 

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

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

Таким образом, можно сделать вывод о том, что сайты наиболее приближенные по оценкам к сайту Kinopoisk: Imhonet, Kinonews и Imdb.

 

2.3.4. Рекомендование предметов

 

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

1. Фильтрация по схожести объектов.
2. Фильтрация по схожести образцов.

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

 

Киносайт	Подобие	Форсаж 5	П. х. Форсаж 5	Призрачный гонщик 2	П. х. Призрачный гонщик 2
Imhonet	0,59	7,7	4,54	5,8	3,42
Kinopoisk	0,15	7,6	1,14	5,2	0,78
Cinemaxx	0,06	8,8	0,53	8,0	0,48
Kinonews	0,69	7,9	5,45	6,6	4,55
Imdb	0,23	7,3	1,68	–	–
Итого:			13,34		9,23
S подоб.			1,13		0,9
Итого / S подоб.			11,8		10,25

 

В данной таблице  приведены коэффициенты корреляции для каждого эксперта и оценки, поставленные ими двум фильмам, которые я намеренно не оценивал. В столбцах «П.х» находится произведение коэффициента подобия на оценку, взятую с киносайта. Идея заключается в том, чтобы мнение пользователей данного сайта с похожими на мои личные вкусы имело больший вклад в общую оценку, чем мнения пользователей, непохожих на меня. В строке «Итого» приведены суммы вычисленных подобным способом величин. Можно было бы использовать для ранжирования сами эти суммы, но тогда фильм, который представлен на большем количестве сайтов, получил бы преимущество. Для избегания подобной ситуации необходимо разделить полученную величину на сумму коэффициентов подобия для всех сайтов, которые имеют оценку по заданному фильму. Результат поместим с строку S подоб. в таблице. Так как оценка фильма «Форсаж 5» была представлена всеми сайтами, величина «Итого» для него делится на сумму всех коэффициентов, а оценка фильма «Призрачный гонщик 2» не была представлена сайтом Imdb, следовательно, величина «Итого» делится на сумму коэффициентов подобия всех экспертов, кроме вышеуказанного. В последней строке таблицы выведено частное от деления. Так, например, прогноз для фильма «Форсаж 5» будет равен 13,34/1,13=11,8.

Программу, реализующую  данный алгоритм можно представить  следующим образом:

 

# Получить рекомендации  для заданного человека, пользуясь  взвешенным средним

# оценок, данных всеми остальными сайтами

def getRecommendations(prefs,person,similarity=sim_pearson):

  totals={}

  simSums={}

  for other in prefs:

    # Сравнивать  меня с собой же не нужно

    if other==person: continue

    sim=similarity(prefs,person,other)

 

    # Обойти нулевые и отрицательные оценки

    if sim<=0: continue

    for item in prefs[other]:

   

      # Оценивать только те фильмы, которые я еще не посмотрел

      if item not in prefs[person] or prefs[person][item]==0:

        # Произведение коэффициента подобия и оценки

        totals.setdefault(item,0)

        totals[item]+=prefs[other][item]*sim

        # Сумма коэффициентов подобия

        simSums.setdefault(item,0)

        simSums[item]+=sim

 

  # Создание нормализованного списка

  rankings=[(total/simSums[item],item) for item,total in totals.items()]

 

  # Вернуть отсортированный список

  rankings.sort()

  rankings.reverse()

  return rankings

 

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

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

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

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

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