转换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,1,0)和(1,1,1)之间的余弦来计算(1,2)之间的相似性,得到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个项目时运行了几个小时.

我正试图计算我的dict中所有项目的相似度,这比我想要的时间更长.我认为这是MapReduce的一个很好的候选者,但我在键/值对方面遇到了"思考"问题.

或者,问题是我的方法,而不一定是Map Reduce的候选人吗？

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"推荐系统.

希望有所帮助,威尔