Conversion du code de filtrage collaboratif python pour utiliser Map Reduce

Question

En utilisant Python, je calcule la similarité des cosinus entre les éléments.

données d'événement donné représentant un achat (utilisateur, article), j'ai une liste de tous les articles 'achetés' par mes utilisateurs.

Compte tenu de ces données d'entrée

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

je construis un dictionnaire python

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

A partir de ce dictionnaire, je produis un acheté/pas acheté matrice, également un autre dictionnaire (ENB).

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

De là, je suis le calcul de similitude entre (1,2) en calculant le cosinus entre (1,1,0) et (1,1,1), ce qui donne 0,816496

je suis faisant cela par:

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]) 

Je pense que l'approche de la force brute est de me tuer et il ne fonctionne que plus lent que les données devient plus grande. En utilisant mon ordinateur portable fidèle, ce calcul dure des heures lorsqu'il s'agit de 8500 utilisateurs et 3500 articles.

J'essaye de calculer la similarité pour tous les articles dans mon dict et cela prend plus de temps que je le voudrais. Je pense que c'est un bon candidat pour MapReduce mais j'ai du mal à "penser" en termes de paires clé/valeur.

Sinon, est-ce que le problème est lié à mon approche et n'est pas nécessairement un candidat pour Map Reduce?

Answer 1

Il ne s'agit pas réellement d'une fonction "MapReduce", mais elle devrait vous donner une accélération significative sans tous les tracas.

J'utiliserais numpy pour "vectoriser" l'opération et vous faciliter la vie. À partir de là, vous aurez juste besoin de faire une boucle dans ce dictionnaire et d'appliquer la fonction vectorisée comparant cet élément à tous les autres.

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 

Je ne l'ai pas testé ce code afin qu'il peut y avoir des erreurs stupides, mais l'idée si vous obtenez 90% de la route.

Ceci devrait avoir une accélération significative. Si vous avez encore besoin d'une accélération, il y a un blog merveilleux qui implémente un système de recommandation "Slope One" here.

Espoir qui aide, Est-ce que