Introduction to Recommendations with Map-Reduce and mrjob

Hi all,

In this post I will present how can we use map-reduce programming model for making recommendations.   Recommender systems are quite popular among shopping sites and social network thee days. How do they do it ?   Generally, the user interaction data available from items and products in shopping sites and social networks are enough information to build a recommendation engine using classic techniques such as Collaborative Filtering.

Why Map-Reduce ?

MapReduce is a framework originally developed at Google that allows easy large scale distributed computing across a number of domains. Apache Hadoop is an open source implementation of it.  It scales well to many thousands of nodes and can handle petabytes of data. For recommendations where we have to find the similar products to a product you are interested at , we must calculate how similar pairs of items are. For instance, if someone watches the movie Matrix, the recommender would suggest the film Blade Runner. So we need to compute the similarity between two movies. One way is to find correlation between pairs of items.  But if you own a shopping site, which has 500,00 products, potentially we would have to compute over 250 billion computations. Besides the computation, the correlation data will be sparse, because it's unlikely that every pair of items will have some user interested in them. So we have a large and sparse dataset. And we have also to deal with temporal aspect since the user interest in products changes with time, so we need the correlation calculation done periodically so that the results are up to date.  For these reason the best way to handle with this scenarion and problem is going after a divide and conquer pattern, and MapReduce is a powerful framework and can be used to implement data mining algorithms.  You can take a look at this post about MapReduce or go to these video classes about Hadoop.

Map-Reduce Architecture

Meeting mrjob

mrjob is a Python package that helps you write and run Hadoop Streaming jobs. It supports Amazon's Elastic MapReduce(EMR) and it also works with your own Hadoop cluster.  It has been released as an open-source framework by Yelp and we will use it as interface for Hadoop since its legibility and ease to handle with MapReduce tasks.  Check this link to see how to to download and use it.

Movie Similarities

Imagine that you own a online movie business, and you want to suggest for your clients movie recommendations.  Your system runs a rating system, that is, people can rate movies with 1 to 5 starts, and we will assume for simplicity that all of the ratings are stored in a csv file somewhere.

Our goal is to calculate how similar pairs of movies are, so that we recommend movies similar to movies you liked.  Using the correlation we can:

• For every pair of movies A and B, find all the people  who rated botha A and B.
• Use these ratings to form a Movie A vector and a Movie B vector.
• Calculate the correlation between those two vectors
• When someone watches a movie, you can recommend the movies most correlated with it

So the first step is to get our movies file which has three columns:  (user, movie, rating). For this task we will use the MovieLens Dataset of Movie Ratings with 10.000 ratings from 1000 users on 1700 movies (you can download it at this link).

Here it is a sample of the dataset file after normalized.

So let's start by reading the ratings into the MovieSimilarities job.


You want to compute how similar pairs of movies are, so that if someone watches the movie The Matrix, you can recommend movies like BladeRunner. So how should you define the similarity between two movies ?

One possibility is to compute their correlation. The basic idea behind it is for every pair of movies A and B, find all the people who rated both A and B. Use these ratings to form a Movie A vector and a Movie B vector.  Then, calculate the correlation between these two vectors.  Now when someone watches a movie, you can now recommend him the movies most correlated with it.

So let's divide to conquer. Our first task is for each user, emit a row containing their 'postings' (item, rating). And for reducer, emit the user rating sum and count for use later steps.




Before using these rating pairs to calculate correlation,  let's see how we can compute it.  We know that they can be formed as vectors of ratings, so we can use linear algebra to perform norms and dot products, as alo to compute the length of each vector or the sum over all elements in each vector. By representing them as matrices, we can perform several operations on those movies.
To summarize, each row in calculate similarity will compute the number of people who rated both movie and movie2 , the sum over all elements in each ratings vectors (sum_x, sum_y) and the squared sum of each vector (sum_xx, sum__yy). So  we can now can calculate the correlation between the movies. The correlation can be expressed as:

So that's it! Now the last step of the job that will sort the top-correlated items for each item and print it to the output.


So let's see the output. Here's a sample of the top output I got:

MovieA	MovieB	Correlation
Return of the Jedi (1983)	Empire Strikes Back, The (1980)	0.787655
Star Trek: The Motion Picture (1979)	Star Trek III: The Search for Spock (1984)	0.758751
Star Trek: Generations (1994)	Star Trek V: The Final Frontier (1989)	0.72042
Star Wars (1977)	Return of the Jedi (1983)	0.687749
Star Trek VI: The Undiscovered Country (1991)	Star Trek III: The Search for Spock (1984)	0.635803
Star Trek V: The Final Frontier (1989)	Star Trek III: The Search for Spock (1984)	0.632764
Star Trek: Generations (1994)	Star Trek: First Contact (1996)	0.602729
Star Trek: The Motion Picture (1979)	Star Trek: First Contact (1996)	0.593454
Star Trek: First Contact (1996)	Star Trek VI: The Undiscovered Country (1991)	0.546233
Star Trek V: The Final Frontier (1989)	Star Trek: Generations (1994)	0.4693
Star Trek: Generations (1994)	Star Trek: The Wrath of Khan (1982)	0.424847
Star Trek IV: The Voyage Home (1986)	Empire Strikes Back, The (1980)	0.38947
Star Trek III: The Search for Spock (1984)	Empire Strikes Back, The (1980)	0.371294
Star Trek IV: The Voyage Home (1986)	Star Trek VI: The Undiscovered Country (1991)	0.360103
Star Trek: The Wrath of Khan (1982)	Empire Strikes Back, The (1980)	0.35366
Stargate (1994)	Star Trek: Generations (1994)	0.347169
Star Trek VI: The Undiscovered Country (1991)	Empire Strikes Back, The (1980)	0.340193
Star Trek V: The Final Frontier (1989)	Stargate (1994)	0.315828
Star Trek: The Wrath of Khan (1982)	Star Trek VI: The Undiscovered Country (1991)	0.222516
Star Wars (1977)	Star Trek: Generations (1994)	0.219273
Star Trek V: The Final Frontier (1989)	Star Trek: The Wrath of Khan (1982)	0.180544
Stargate (1994)	Star Wars (1977)	0.153285
Star Trek V: The Final Frontier (1989)	Empire Strikes Back, The (1980)	0.084117

As we would expect we can notice that

• Star Trek movies are similar to other Star Trek movies.
• The people  who likes Star Trek movies are not so fans of Star Wars and vice-versa;
• Star Wars Fans will be always fans! :D
• The Sci-Fi movies are quite similar to each other;
• Star Trek III: The Search for Spock (1984) is one the best movies of Star Trek (several positive correlations)

To see the full code, checkout the Github repository here.

Book Similarities

Let's see another dataset. What about Book Ratings ? Let's see this dataset of 1 million book ratings.   Here's again a sample of it:

But now we want to compute other similarity measures besides correlation. Let's take a look on them.

Cossine Similarity

Another common vector-based similarity measure.

Regularized Correlation

We could use regularized correlation by adding N virtual movie pairs that have zero correlation. This helps avoid noise if some movie pairs have very few raters in common.

Jaccard 
The implicit data can be useful. In some cases only because you rate a Toy Store movie, even if you rate it quite horribly, you can still be interested in similar animation movies.  So we can ignore the value itself of each rating and use a set-based similarity measure such as the Jaccard Similarity.


Now, let's add all those similarities to our mapreduce job and make some adjustments by making a new job for counting the number of raters for each movie. It will be required for computing the jaccard similarity.

Ok,  let's take a look at the book similarities now with those new fields.

BookA	BookB	Correlation	Cossine	Reg Corr	Jaccard	Mutual Raters
The Return of the King (The Lord of The Rings, Part 3)	The Voyage of the Dawn Treader (rack) (Narnia)	0	0.998274	0	0.068966	2
The Return of the King (The Lord of the Rings, Part 3)	The Man in the Black Suit : 4 Dark Tales	0	1	0	0.058824	6
The Fellowship of the Ring (The Lord of the Rings, Part 1)	The Hobbit : The Enchanting Prelude to The Lord of the Rings	0.796478	0.997001	0.49014	0.045714	16
The Two Towers (The Lord of the Rings, Part 2)	Harry Potter and the Prisoner of Azkaban (Book 3)	-0.184302	0.992536	-0.087301	0.022277	9
Disney's 101 Dalmatians (Golden Look-Look Books)	Walt Disney's Lady and the Tramp (Little Golden Book)	0.88383	1	0.45999	0.166667	5
Disney's 101 Dalmatians (Golden Look-Look Books)	Disney's Beauty and the Beast (Golden Look-Look Book)	0.76444	1	0.2339	0.166667	7
Disney's Pocahontas (Little Golden Book)	Disney's the Lion King (Little Golden Book)	0.54595	1	0.6777	0.1	4
Disney's the Lion King (Disney Classic Series)	Walt Disney Pictures presents The rescuers downunder (A Little golden book)	0.34949	1	0.83833	0.142857	3
Harry Potter and the Order of the Phoenix (Book 5)	Harry Potter and the Goblet of Fire (Book 4)	0.673429	0.994688	0.559288	0.119804	49
Harry Potter and the Chamber of Secrets (Book 2)	Harry Potter and the Goblet of Fire (Book 4)	0.555423	0.993299	0.496957	0.17418	85
The Return of the King (The Lord of The Rings, Part 3)	Harry Potter and the Goblet of Fire (Book 4)	-0.2343	0.02022	-0.08383	0.015444	4

• Lord of The Rings, books are similar to other Lord of The Ring books
• Walt Disney books are similar to other Walt Disney books. 
• Lord of The Ring books does not stick together Harry Potter books.

The possibilities are endless.

But is it possible to generalize our input and make our code to generate similarities for different inputs ? Yes it is.  Let's abstract our input. For this, we will create a VectorSimilarities Class that represents input data in the following format:


So if we want to define a new input format, just subclass the VectorSimilarities class and implement the method input.

So here's the class for the book recommendations using our new VectorSimilarities.

And here's the class for the movies recommendations. It simply reads from a data file and lets the VectorSimilarities superclass do the work.

Conclusions

As you noticed map-reduce is a powerful technique for numerical computation and speacially when you have to compute large datasets. There are several optimization I can do in those scripts such as numpy vectorizations for computing the similarities. I will explore more these features in the next posts: one handling with recommender systems and popular social networks as also how you can use the Amazon EMR infrastructure to compute your jobs!

I'd like to thank Edwin Chen and his post using those examples with Scala and whose post inspired me to explore these examples above in Python.

All code for those examples above can be downloaded at my github repository.

Stay tunned,

I hope you enjoyed this article,

Best regards,

Marcel Caraciolo