Фильтрация по схожести образцов

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

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

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

Построение набора данных для сравнения образцов

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

Для генерирования набора данных включите в файл recommendations. py следующую функцию:

def calculateSimilarItems(prefs,n=10):

#     Создать словарь, содержащий для каждого образца те образцы, которые

#     больше всего похожи на него. result={}

#     Обратить матрицу предпочтений, чтобы строки соответствовали образцам itemPrefs=transformPrefs(prefs)

c=0

for item in itemPrefs:

#     Обновление состояния для больших наборов данных c+=1

if c%100==0: print "%d / %d" % (c,len(itemPrefs))

#     Найти образцы, максимально похожие на данный scores=topMatches(itemPrefs,item,n=n,similarity=sim_distance) result[item]=scores

return result

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

В сеансе работы с интерпретатором Python постройте набор данных о схожести образцов и посмотрите, что получится: >>> reload(recommendations)

>>> itemsim=recommendations.calculateSimilarItems(recommendations.critics) >>> itemsim

{‘Lady in the Water’: [(0.40000000000000002, ‘You, Me and Dupree’),

(0.2857142857142857, ‘The Night Listener’),… ‘Snakes on a Plane’: [(0.22222222222222221, ‘Lady in the Water’),

(0.18181818181818182, ‘The Night Listener’),…

и т. д.

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

Выдача рекомендаций

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

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

Таблица 2.3. Рекомендации для Toby,

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

Фильм

Оценка

Night

О.x

Night

Lady

О.x

Lady

Luck

О.x

Luck

«Snakes»

4,5

0,182

0,818

0,222

0,999

0,105

0,474

«Superman»

4,0

0,103

0,412

0,091

0,363

0,065

0,258

«Dupree»

1,0

0,148

0,148

0,4

0,4

0,182

0,182

Итого

 

0,433

1,378

0,713

1,764

0,352

0,914

После нормализации

 

 

3,183

 

2,598

 

2,473

В каждой строке указан фильм, который я смотрел, и оценка, которую я ему выставил. Для каждого фильма, который я не смотрел, имеется столбец, где показано, насколько он похож на виденные мной фильмы. Например, коэффициент подобия между фильмами «Superman» и «The Night Listener» равен 0,103. В столбцах с названиями, начинающимися с О.x, показана моя оценка, умноженная на коэффициент подобия; поскольку я поставил фильму «Superman» оценку 4,0, то, умножая число на пересечении строки «Superman» и столбца «Night» на 4,0, получаем: 4,0 X 0,103 = 0,412.

В строке «Итого» просуммированы коэффициенты подобия и значения в столбцах «О.x» для каждого фильма. Чтобы предсказать мою оценку фильма, достаточно разделить итог для колонки «О.x» на суммарный коэффициент подобия. Так, для фильма «The Night Listener» прогноз моей оценки равен 1,378/0,433 = 3,183.

Реализуем эту функциональность, добавив последнюю функцию в файл recommendations.py:

def getRecommendedItems(prefs,itemMatch,user): userRatings=prefs[user] scores={} totalSim={}

# Цикл по образцам, оцененным данным пользователем for (item,rating) in userRatings.items( ):

# Цикл по образцам, похожим на данный for (similarity,item2) in itemMatch[item]:

# Пропускаем, если пользователь уже оценивал данный образец if item2 in userRatings: continue

#         Взвешенная суммы оценок, умноженных на коэффициент подобия scores.setdefault(item2,0) scores[item2]+=similarity*rating

#        Сумма всех коэффициентов подобия totalSim.setdefault(item2,0) totalSim[item2]+=similarity

#      Делим каждую итоговую оценку на взвешенную сумму, чтобы вычислить

#      среднее

rankings=[(score/totalSim[item],item) for item,score in scores.items( )]

#      Возвращает список rankings, отсортированный по убыванию rankings.sort( )

rankings.reverse( ) return rankings

Протестируйте эту функцию на построенном ранее наборе данных о схожести предметов, чтобы получить новые рекомендации для Toby: >> reload(recommendations)

>> recommendations.getRecommendedItems(recommendations.critics,itemsim,’Toby’)

[(3.182, ‘The Night Listener’), (2.598, ‘Just My Luck’), (2.473, ‘Lady in the Water’)]

Фильм «The Night Listener» по-прежнему лидирует с большим отрывом, а «Just My Luck» и «Lady in the Water» поменялись местами, но остались близки. Важнее тот факт, что функции getRecommendedItems не пришлось вычислять коэффициенты подобия для всех остальных критиков, поскольку нужный набор данных был построен заранее.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100