I am trying to find the similarity between the two movies using Pearson correlation coefficient. The programs is working well for small inputs but for large inputs (like 100000 lines) it takes forever. My professor said it would take few minutes, but my program is executing forever.
The input format: user|movie|rating
.
If two or more users watch two movies, we will find similarity between them based on rating.
# -*- coding: utf-8 -*-
"""
Created on June 06, 2016
@author: Praveen Allam
"""
from mrjob.job import MRJob
from mrjob.step import MRStep
from itertools import combinations
from itertools import izip
from math import sqrt
class PearsonCorrelation(MRJob):
def steps(self):
return [
MRStep(mapper=self.mapper1,
reducer=self.reducer1),
MRStep(mapper=self.mapper2,
reducer=self.reducer2)
]
def mapper1(self, _, line):
##yield each line to first mapper
user,movie,rating=line.split('|')
yield None,[user,movie,rating]
def reducer1(self, _, value):
##yield all combinations to second mapper
for item1,item2 in combinations(value,2):
yield item1,item2
def mapper2(self,value1,value2):
##yield movie1,movie2 and corresponding ratings of user.
if(value1[0]==value2[0]):
yield [value1[1],value2[1]],[float(value1[2]),float(value2[2])]
def reducer2(self,movies,ratings):
rating=[]
for item in ratings:
rating.append(item)
##extract using izip only if there are more than one instance.
if(len(rating)>1):
v1,v2=izip(*rating)
##calculate the pearson coefficient
corr=self.pearsonCoefficient(v1,v2)
##yield the result
yield "The Similarity between "+movies[0]+" and "+movies[1]+" is: " , corr
def pearsonCoefficient(self,a,b):
n=len(b)
value=range(n)
#sums of individual lists
sum_x=sum([float(a[i]) for i in value])
sum_y=sum([float(b[i]) for i in value])
#sum of the squares of each lists
sum_xSq=sum([a[i]**2.0 for i in value])
sum_ySq=sum([b[i]**2.0 for i in value])
#sum of the products
sumP=sum([a[i]*b[i] for i in value])
#Calculate Pearson coefficient
numerator=sumP-(sum_x*sum_y/n)
denominator=((sum_xSq-pow(sum_x,2)/n)*(sum_ySq-pow(sum_y,2)/n))**0.5
if denominator == 0: return 1
result=numerator/denominator
return result
if __name__ == '__main__':
PearsonCorrelation.run()