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

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

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.

**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.

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

Awesome! Thank you

ReplyDeleteThanks, great job!

ReplyDeleteThanks so much man! Really looking forward to your next few posts which hopefully will delve deeper into the workings of mrjob.

ReplyDeleteGreat post, Please let me know how " def calculate_similarity " works

ReplyDeleteThe output has 19,21 0.4,2 and 21,19 0.4,2 but there is only one yield statement

In "def calculate_ranking", I think I should do 1- similarity to get the Highest correlated to the top .

In "def top_similar_items" Where do you give the K to emit the closest items

Thanks