Преобразование кода совместной фильтрации Python для использования Map Reduce

Question

Используя Python, я вычисляю косинусное сходство между элементами.

с учетом данных о событии, представляющих покупку (пользователь, предмет), у меня есть список всех предметов, "купленных" моими пользователями.

Учитывая эти входные данные

(user,item)
X,1
X,2
Y,1
Y,2
Z,2
Z,3

Я строю словарь Python

{1: ['X','Y'], 2 : ['X','Y','Z'], 3 : ['Z']}

Из этого словаря я генерирую купленную / не купленную матрицу, а также другой словарь (bnb).

{1 : [1,1,0], 2 : [1,1,1], 3 : [0,0,1]} 

Оттуда я вычисляю сходство между (1,2), вычисляя косинус между (1,1,0) и (1,1,1), получая 0,816496

Я делаю это по:

items=[1,2,3]
for item in items:
  for sub in items:
    if sub >= item:    #as to not calculate similarity on the inverse
      sim = coSim( bnb[item], bnb[sub] )

Я думаю, что метод грубой силы убивает меня, и он работает только медленнее, когда данные становятся больше. На моем надежном ноутбуке этот расчет выполняется часами при работе с 8500 пользователями и 3500 объектами.

Я пытаюсь вычислить сходство для всех предметов в моем диктофоне, и это занимает больше времени, чем мне бы хотелось. Я думаю, что это хороший кандидат на MapReduce, но у меня проблемы с «мышлением» в терминах пар ключ / значение.

В качестве альтернативы, проблема с моим подходом и не обязательно является кандидатом на сокращение карты?

Answer 1

На самом деле это не функция «MapReduce», но она должна дать вам значительное ускорение без всех хлопот.

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

import numpy as np
bnb_items = bnb.values()
for num in xrange(len(bnb_items)-1):
    sims = cosSim(bnb_items[num], bnb_items[num+1:]

def cosSim(User, OUsers):
""" Determinnes the cosine-similarity between 1 user and all others.
Returns an array the size of OUsers with the similarity measures

User is a single array of the items purchased by a user.
OUsers is a LIST of arrays purchased by other users.

"""

    multidot = np.vectorize(np.vdot)
    multidenom = np.vectorize(lambda x: np.sum(x)*np.sum(User))

    #apply the dot-product between this user and all others
    num = multidot(OUsers, User)

    #apply the magnitude multiplication across this user and all others
    denom = multidenom(OUsers)

    return num/denom

Я не тестировал этот код, поэтому могут быть некоторые глупые ошибки, но идея должна помочь вам на 90%.

Это должно иметь ЗНАЧИТЕЛЬНОЕ ускорение. Если вам все еще нужно ускориться, есть замечательное сообщение в блоге, в котором реализована система рекомендаций "Slope One" здесь .

Надеюсь, это поможет, Будет