# A dictionary of movie critics and their ratings of a set of movie
critics = {'Lisa Rose': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.5,
'Just My Luck': 3.0, 'Superman Returns': 3.5,
'You, Me and Dupree': 2.5, 'The Night Listener': 3.0},
'Gene Seymour': {'Lady in the Water': 3.0, 'Snakes on a Plane': 3.5,
'Just My Luck': 1.5, 'Superman Returns': 5.0,
'The Night Listener': 3.0,
'You, Me and Dupree': 3.5},
'Michael Phillips': {'Lady in the Water': 2.5,
'Snakes on a Plane': 3.0,
'Superman Returns': 3.5,
'The Night Listener': 4.0},
'Claudia Puig': {'Snakes on a Plane': 3.5, 'Just My Luck': 3.0,
'The Night Listener': 4.5, 'Superman Returns': 4.0,
'You, Me and Dupree': 2.5},
'Mick LaSalle': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0,
'Just My Luck': 2.0, 'Superman Returns': 3.0,
'The Night Listener': 3.0,
'You, Me and Dupree': 2.0},
'Jack Matthews': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0,
'The Night Listener': 3.0, 'Superman Returns': 5.0,
'You, Me and Dupree': 3.5},
'Toby': {'Snakes on a Plane': 4.5, 'You, Me and Dupree': 1.0,
'Superman Returns': 4.0}}Выработка рекомендаций
Из книги Тоби Сегарана “Программируем коллективный разум”, 2008 г.
В этом словаре критик выставляет фильму оценку от 1 до 5. Как бы ни было выражено предпочтение, необходимо отобразить его в виде числового значения. Если бы вы создавали сайт для онлайновой торговли, то могли бы использовать 1 как признак того, что посетитель делал покупки в прошлом, и 0 – что не делал.
critics['Lisa Rose']{'Lady in the Water': 2.5,
'Snakes on a Plane': 3.5,
'Just My Luck': 3.0,
'Superman Returns': 3.5,
'You, Me and Dupree': 2.5,
'The Night Listener': 3.0}Собрав данные о том, что людям нравится, нужно как-то определить, насколько их вкусы схожи. Для этого каждый человек сравнивается со всеми другими и вычисляется коэффициент подобия (или оценка подобия). Для этого есть несколько способов: евклидово расстояние и коэффициент корреляции Пирсона.
Оценка по евклидову расстоянию
В этом случае предметы, которые люди оценивали сообща, представляются в виде координатных осей. Теперь в этой системе координат можно расположить точки, соответствующие людям, и посмотреть, насколько они оказались близки.
Чем ближе два человека в пространстве предпочтений, тем более схожи их предпочтения. Поскольку эта диаграмма двумерная, то одновременно можно смотреть только на два показателя, но принцип остается тем же самым и для большего числа показателей.
Чтобы вычислить расстояние между Toby и LaSalle на этой диаграмме, возьмем разности координат по каждой оси, возведем их в квадрат, сложим, а затем извлечем квадратный корень из суммы:
from math import sqrt
sqrt(pow(5-4,2)+pow(4-1,2))3.1622776601683795Расстояние, вычисленное по этой формуле, будет тем меньше, чем больше сходства между людьми. Однако нам нужна функция, значение которой тем больше, чем люди более похожи друг на друга. Этого можно добиться, добавив к вычисленному расстоянию 1 (чтобы никогда не делить на 0) и взяв обратную величину:
1/(1+sqrt(pow(5-4,2)+pow(4-1,2)))0.2402530733520421Новая функция всегда возвращает значение от 0 до 1, причем 1 получается, когда предпочтения двух людей в точности совпадают. Теперь можно собрать все воедино и написать функцию для вычисления оценки подобия.
def sim_distance(prefs, person1, person2):
'''Return a distance-based similarity score for person1 and person2.'''
# get the list of shared items
si = {}
for item in prefs[person1]:
if item in prefs[person2]:
si[item] = 1
# if no ratings in common, return 0
if len(si) == 0:
return 0
# add up the squares of all the differences
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 + sum_of_squares) # between (0, 1)Этой функции при вызове передаются имена двух людей, для которых требуется вычислить оценку подобия.
sim_distance(critics,'Lisa Rose','Gene Seymour')0.14814814814814814Получили оценку подобия между Lisa Rose и Gene Seymour.
Коэффициент корреляции Пирсона
Коэффициент корреляции Пирсона – это мера того, насколько хорошо два набора данных ложатся на прямую. Формула сложнее, чем для вычисления евклидова расстояния, но она дает лучшие результаты, когда данные плохо нормализованы, например если некоторый критик устойчиво выставляет фильмам более низкие оценки, чем в среднем.
Для визуализации этого метода можете нанести на диаграмму оценки, выставленные двумя критиками, как показано на следующем рисунке.
Mick LaSalle оценил фильм «Superman» на 3, а Gene Seymour – на 5, поэтому мы наносим точку (3, 5).
На диаграмме также изображена прямая линия. Она называется линией наилучшего приближения, поскольку проходит настолько близко ко всем точкам на диаграмме, насколько возможно. Если бы оба критика выставили всем фильмам одинаковые оценки, то эта линия оказалась бы диагональной и прошла бы через все точки. В этом случае получилась бы идеальная корреляция с коэффициентом 1.
Но в нашем случае критики разошлись в оценках, поэтому коэффициент корреляции равен 0,4. На следующем рисунке показан пример с гораздо более высоким коэффициентом корреляции 0,75.
У коэффициента корреляции Пирсона есть одно интересное свойство, которое можно наблюдать на рисунке – он корректирует обесценивание оценок. Видно, что Jack Matthews систематически выставляет более высокие оценки, чем Lisa Rose, но линия все равно проходит близко к точкам, поскольку их предпочтения схожи. Если один критик склонен выставлять более высокие оценки, чем другой, то идеальная корреляция все равно возможна при условии, что разница в оценках постоянна. Метод евклидова расстояния в этом случае выдал бы результат, что критики не похожи, поскольку один всегда оказывается строже другого, несмотря на то что их вкусы, по существу, очень сходны.
Программа для вычисления коэффициента корреляции Пирсона сначала находит фильмы, оцененные обоими критиками, и вычисляет сумму и сумму квадратов выставленных ими оценок, а также сумму произведений оценок. На последнем этапе найденные значения используются для вычисления коэффициента корреляции.
def sim_pearson(prefs, p1, p2):
'''Return the Pearson correlation coefficient for p1 and p2.'''
# get the list of shared items
si = {}
for item in prefs[p1]:
if item in prefs[p2]:
si[item] = 1
# find the number of elements
n = len(si)
# if no ratings in common, return 0
if len(si) == 0:
return 0
# add up all the preferences
sum1 = sum([prefs[p1][item] for item in si])
sum2 = sum([prefs[p2][item] for item in si])
# sum up the squares
sum1Sq = sum([pow(prefs[p1][item], 2) for item in si])
sum2Sq = sum([pow(prefs[p2][item], 2) for item in si])
# sum up the products
pSum = sum([prefs[p1][item] * prefs[p2][item] for item in si])
# calculate Pearson score
num = pSum - (sum1 * sum2)/n
den = sqrt((sum1Sq - pow(sum1, 2)/n) * (sum2Sq - pow(sum2, 2)/n))
if den == 0:
return 0
else:
return num/den # between(-1, 1)Эта функция возвращает значение от –1 до 1. Значение 1 означает, что два человека выставили каждому предмету в точности одинаковые оценки. В отличие от евклидовой метрики, масштабировать возвращенное значение для приведения к нужному диапазону не требуется.
sim_pearson(critics, 'Lisa Rose','Gene Seymour')0.39605901719066977Ранжирование критиков
Имея функции для сравнения двух людей, можно написать функцию, которая будет вычислять оценку подобия всех имеющихся людей с данным человеком и искать наилучшее соответствие. В данном случае меня интересуют кинокритики с таким же вкусом, как у меня. Тогда я буду знать, на кого ориентироваться, принимая решение о выборе фильма. Возвращает первые n элементов отсортированного списка результатов.
def topMatches(prefs, person, n = 5, similarity = sim_pearson):
'''Return the best matches for person from the prefs dictionary.'''
scores = [(similarity(prefs, person, other), other)
for other in prefs if other != person]
# sort the list so the highest scores appear at the top
scores.sort(reverse = True)
return scores[0:n] topMatches(critics,'Toby',n=3)[(0.9912407071619299, 'Lisa Rose'),
(0.9244734516419049, 'Mick LaSalle'),
(0.8934051474415647, 'Claudia Puig')]Рекомендование предметов
В действительности я хочу, чтобы мне порекомендовали фильм.
Можно было бы посмотреть, какие фильмы понравились человеку с похожими на мои вкусами, и выбрать из них те, что я еще не смотрел. Но при таком подходе можно было бы случайно наткнуться на критиков, ничего не писавших о фильмах, которые могли бы мне понравиться.
Можно также отобрать критика, которому почему-то понравился фильм, получивший отрицательные отзывы от всех остальных критиков, вошедших в список topMatches.
Чтобы разрешить эти проблемы, необходимо ранжировать сами фильмы, вычислив взвешенную сумму оценок критиков. Берем каждого из отобранных критиков и умножаем его оценку подобия со мной на оценку, которую он выставил каждому фильму.
В таблице показан результат вычислений.
В таблице приведены коэффициенты корреляции для каждого критика и оценки, поставленные ими трем фильмам («The Night Listener», «Lady in the Water» и «Just My Luck»), которые я сам не оценивал. В столбцах «П.x» находится произведение коэффициента подобия на оценку, выставленную критиком. Смысл в том, чтобы мнение критика с похожими на мои вкусами вносило больший вклад в общую оценку, чем мнение критика, не похожего на меня. В строке «Итого» приведены суммы вычисленных таким образом величин.
Можно было бы использовать для ранжирования сами эти суммы, но тогда фильм, который просмотрело больше людей, получил бы преимущество. Чтобы исправить эту несправедливость, необходимо разделить полученную величину на сумму коэффициентов подобия для всех критиков, которые рецензировали фильм (строка «S подоб.» в таблице).
Поскольку фильм «The Night Listener» рецензировали все, величина «Итого» для него делится на сумму всех коэффициентов подобия. Напротив, фильм «Lady in the Water» критик Puig не рецензировал, следовательно, в этом случае величина «Итого» делится на сумму коэффициентов подобия всех критиков, кроме Puig. В последней строке показано частное от деления.
def getRecommendations(prefs, person, similarity = sim_pearson):
'''Get recommendations for a person by using a weighed averaged ranking.'''
totals = {}
simSums = {}
for other in prefs:
# don't compare me to myself (skip to the next iteration)
if other == person:
continue
sim = similarity(prefs, person, other)
# ignore scores of zero or lower
if sim <= 0:
continue
for item in prefs[other]:
# only score movies I haven't seen yet
if item not in prefs[person] or prefs[person][item] == 0:
# similarity * score
totals.setdefault(item, 0)
totals[item] += prefs[other][item] * sim
# sum of similarities
simSums.setdefault(item, 0)
simSums[item] += sim
# create the normalized list
rankings = [(total/simSums[item], item) for item, total in totals.items()]
# return the sorted list
rankings.sort(reverse = True)
return rankingsЗдесь мы в цикле обходим всех людей, присутствующих в словаре prefs. Для каждого вычисляется коэффициент подобия с заданным человеком person. Далее обходятся все фильмы, которым текущий критик выставил оценку. В строке, выделенной полужирным шрифтом, вычисляется окончательная оценка фильма – оценка, данная каждым критиком, умножается на коэффициент подобия этого критика и произведения суммируются. В самом конце оценки нормализуются путем деления на сумму коэффициентов подобия и возвращается отсортированный список результатов.
getRecommendations(critics,'Toby', similarity=sim_distance)[(3.5002478401415877, 'The Night Listener'),
(2.7561242939959363, 'Lady in the Water'),
(2.461988486074374, 'Just My Luck')]Итак, построена полная система рекомендования, способная работать с товарами любого вида или со ссылками. Необходимо лишь заполнить словарь, поместив в него людей, предметы и оценки, а затем его можно использовать для рекомендования предметов любому пользователю.
Подбор предметов
Но что если нужно узнать, какие предметы похожи друг на друга? Вы могли столкнуться с такой ситуацией на сайтах онлайновой торговли, особенно если сайт еще не собрал о вас достаточно информации.
В данном случае вы можете определить степень сходства, выявив людей, которым понравился данный товар, и посмотрев, что еще им понравилось. По существу, это тот же метод, которым мы уже пользовались для определения похожести людей, – нужно лишь вместо людей всюду подставить товары. Стало быть, мы сможем применить уже написанные функции, если преобразуем словарь, заменив
{'Lisa Rose': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.5},
'Gene Seymour': {'Lady in the Water': 3.0, 'Snakes on a Plane': 3.5}}на
{'Lady in the Water':{'Lisa Rose':2.5,'Gene Seymour':3.0},
'Snakes on a Plane':{'Lisa Rose':3.5,'Gene Seymour':3.5}}def transformPrefs(prefs):
'''Swipe the people and the item.'''
results = {}
for person in prefs:
for item in prefs[person]:
results.setdefault(item, {})
# flip item and person
results[item][person] = prefs[person][item]
return resultsвызовем функцию topMatches , чтобы найти фильмы, похожие на «Superman Returns»
movies=transformPrefs(critics)
topMatches(movies,'Superman Returns')[(0.6579516949597695, 'You, Me and Dupree'),
(0.4879500364742689, 'Lady in the Water'),
(0.11180339887498941, 'Snakes on a Plane'),
(-0.1798471947990544, 'The Night Listener'),
(-0.42289003161103106, 'Just My Luck')]Обратите внимание, что в этом примере встречаются отрицательные коэффициенты корреляции. Это означает, что тем, кому нравится фильм «Superman Returns», фильм «Just My Luck» обычно не нравится.
Не всегда очевидно, что перестановка людей и товаров приведет к полезным результатам, но во многих случаях это позволяет провести интересные сравнения. Сайт онлайновой торговли может хранить истории покупок, чтобы рекомендовать товары посетителям. В этом случае описанная выше перестановка людей и товаров позволит найти людей, которые могли бы купить определенный товар. Это может оказаться очень полезным при планировании маркетинговых акций для продвижения товаров.
Фильтрация по схожести образцов
Мы реализовали механизм рекомендования таким образом, что для создания набора данных необходимы оценки, выставленные каждым пользователем. Для нескольких тысяч людей или предметов это, возможно, и будет работать, но на таком большом сайте, как Amazon, миллионы пользователей и товаров, поэтому сравнение каждого пользователя со всеми другими, а затем сравнение товаров, которым каждый пользователь выставил оценки, займет недопустимо много времени. Кроме того, на сайте, который продает миллионы разных товаров, перекрытие вкусов может быть очень мало, поэтому нелегко решить, какие пользователи похожи.
Техника, которую мы применяли до сих пор, называется коллаборативной фильтрацией по схожести пользователей. Альтернатива известна под названием «коллаборативная фильтрация по схожести образцов». Когда набор данных очень велик, коллаборативная фильтрация по схожести образцов может давать лучшие результаты, причем многие вычисления можно выполнить заранее, поэтому пользователь получит рекомендации быстрее.
Основная идея заключается в том, чтобы для каждого образца заранее вычислить большинство похожих на него. Тогда для выработки рекомендаций пользователю достаточно будет найти те образцы, которым он выставил наивысшие оценки, и создать взвешенный список образцов, максимально похожих на эти.
Отметим одно существенное отличие: хотя на первом шаге необходимо исследовать все данные, результаты сравнения образцов изменяются не так часто, как результаты сравнения пользователей. Это означает, что не нужно постоянно пересчитывать для каждого образца список похожих на него; это можно делать, когда нагрузка на сайт невелика, или вообще на отдельном компьютере.
Построение набора данных для сравнения образцов
Чтобы сравнивать образцы, нужно первым делом написать функцию, которая построит полный набор данных о похожих образцах.
def calculateSimilarItems(prefs, n = 10):
'''Return a dictionary of items showing which other items they are most similiar to.'''
result = {}
# invert the preference matrix to be item-centric
itemPrefs = transformPrefs(prefs)
c = 0
for item in itemPrefs:
# status updates for large datasets
c += 1
if c%100 == 0:
print("%d/%d" % (c, len(itemPrefs)))
# find the most similar items to this one
scores = topMatches(itemPrefs, item, n = n, similarity=sim_distance)
result[item] = scores
return resultЭта функция сначала обращает словарь предпочтений, вызывая написанную ранее функцию transformPrefs, которой передается список образцов вместе с оценками, выставленными каждым пользователем. Далее в цикле обходятся все образцы и трансформированный словарь передается функции topMatches, которая возвращает наиболее похожие образцы и коэффициенты подобия для них. Наконец функция создает и возвращает словарь, в котором каждому образцу сопоставлен список наиболее похожих на него образцов.
itemsim=calculateSimilarItems(critics)
itemsim{'Lady in the Water': [(0.4, 'You, Me and Dupree'),
(0.2857142857142857, 'The Night Listener'),
(0.2222222222222222, 'Snakes on a Plane'),
(0.2222222222222222, 'Just My Luck'),
(0.09090909090909091, 'Superman Returns')],
'Snakes on a Plane': [(0.2222222222222222, 'Lady in the Water'),
(0.18181818181818182, 'The Night Listener'),
(0.16666666666666666, 'Superman Returns'),
(0.10526315789473684, 'Just My Luck'),
(0.05128205128205128, 'You, Me and Dupree')],
'Just My Luck': [(0.2222222222222222, 'Lady in the Water'),
(0.18181818181818182, 'You, Me and Dupree'),
(0.15384615384615385, 'The Night Listener'),
(0.10526315789473684, 'Snakes on a Plane'),
(0.06451612903225806, 'Superman Returns')],
'Superman Returns': [(0.16666666666666666, 'Snakes on a Plane'),
(0.10256410256410256, 'The Night Listener'),
(0.09090909090909091, 'Lady in the Water'),
(0.06451612903225806, 'Just My Luck'),
(0.05333333333333334, 'You, Me and Dupree')],
'You, Me and Dupree': [(0.4, 'Lady in the Water'),
(0.18181818181818182, 'Just My Luck'),
(0.14814814814814814, 'The Night Listener'),
(0.05333333333333334, 'Superman Returns'),
(0.05128205128205128, 'Snakes on a Plane')],
'The Night Listener': [(0.2857142857142857, 'Lady in the Water'),
(0.18181818181818182, 'Snakes on a Plane'),
(0.15384615384615385, 'Just My Luck'),
(0.14814814814814814, 'You, Me and Dupree'),
(0.10256410256410256, 'Superman Returns')]}Напомним, что эту функцию следует запускать лишь тогда, когда необходимо обновить данные о схожести образцов. Пока количество пользователей и выставленных ими оценок невелико, это имеет смысл делать чаще, но по мере роста числа пользователей коэффициенты подобия образцов обычно перестают сильно изменяться.
Выдача рекомендаций
Теперь вы готовы выдавать рекомендации, пользуясь словарем данных о схожести образцов без обращения ко всему набору данных. Необходимо получить список всех образцов, которым пользователь выставлял оценки, найти похожие и взвесить их с учетом коэффициентов подобия.
В таблице показана процедура выработки рекомендаций на основе фильтрации по схожести образцов. Критики тут вообще не участвуют, а сравниваются фильмы, которые я оценивал, с теми, которые не оценивал.
В каждой строке указан фильм, который я смотрел, и оценка, которую я ему выставил. Для каждого фильма, который я не смотрел, имеется столбец, где показано, насколько он похож на виденные мной фильмы. Например, коэффициент подобия между фильмами «Superman» и «The Night Listener» равен 0,103. В столбцах с названиями, начинающимися с О.x, показана моя оценка, умноженная на коэффициент подобия; поскольку я поставил фильму «Superman» оценку 4,0, то, умножая число на пересечении строки «Superman» и столбца «Night» на 4,0, получаем: 4,0 × 0,103 = 0,412. В строке «Итого» просуммированы коэффициенты подобия и значения в столбцах «О.x» для каждого фильма. Чтобы предсказать мою оценку фильма, достаточно разделить итог для колонки «О.x» на суммарный коэффициент подобия. Так, для фильма «The Night Listener» прогноз моей оценки равен 1,378/0,433 = 3,183.
def getRecommendedItems(prefs, itemMatch, user):
'''Get recommendations using the item-based filtering.'''
userRatings = prefs[user]
scores = {}
totalSim = {}
# loop over items rated by this user
for (item, rating) in userRatings.items():
# loop over items similar to this one
for (similarity, item2) in itemMatch[item]:
# ignore if user has already reated this item
if item2 in userRatings:
continue
# weighted sum of rating times similarity
scores.setdefault(item2, 0)
scores[item2] += similarity * rating
# sum of all the similarities
totalSim.setdefault(item2, 0)
totalSim[item2] += similarity
# divide each total score by total weighting to get an average
rankings = [(score/totalSim[item], item)
for item, score in scores.items()]
# return the rankings from highest to lowest
rankings.sort(reverse = True)
return rankingsgetRecommendedItems(critics,itemsim,'Toby')[(3.182634730538922, 'The Night Listener'),
(2.5983318700614575, 'Just My Luck'),
(2.4730878186968837, 'Lady in the Water')]Фильм «The Night Listener» по-прежнему лидирует с большим отрывом, а «Just My Luck» и «Lady in the Water» поменялись местами, но остались близки. Важнее тот факт, что функции getRecommendedItems не пришлось вычислять коэффициенты подобия для всех остальных критиков, поскольку нужный набор данных был построен заранее.