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

Crab: A Python Framework for Building Recommendation Engines

Hi all,

In this weekend I presented a lecture at the XII Python User Group Pernambuco Meeting about the framework I've been working on at these last months. The framework is called Crab and it is a Python library for building recommendation engines. Its main goal is to be an alternative for machine learning researchers and developers for use standard-of-the-art implemented recommendation algorithms, evaluate and extend it by building new techniques using the basic core provided by the framework.   

Me presenting the Crab : A Python framework for building recommendation engines

The framework has started in 2010, as a support toolkit for my master degree thesis about recommendation engines. I've implemented the Collaborative Filtering techniques as also the evaluation metrics used in recommendations (Precision, Recall, F1-Score, RMSE, etc). But since last month (April,2011) I decided to give the framework a shot to become more visible and bring more contributors for the project. The project became part of a Non-profitable organization called Muriçoca Labs, a team of  developers and researchers interested in Machine Learning and Artificial Intelligence. We also decided to    migrate all the core of the project using the scientific libraries Numpy, Scipy and Matplotlib, since the speed and the legibility of the code were the main advantages of these toolkits.   

The project started last month and had its first sprint where the team is focused on rewriting all the code of the old crab to this new release as also make it a independent project member of the Scikit repository - Sub-projects of Scipy Framework and a sub-module of the Scikit-Learn  (a popular python framework for machine learning algorithms). 

We are quite excited and working harder! By the way the Crab framework is already in production providing the recommendations of the brazilian social network AtePassar.  We are with lot of ideas and features such as content based filtering algorithms, recommendations as services providing REST APIs and Databases Models Support.

If you are interested in the project and want to know how to join us or use our projects, please let me know and add a comment below and I will be glad to help you!  The project is at the beginning, but we are working harder to see it in action as a possible alternative for Python developers that want to work with this hot topic in the data mining and web services: Recommender Systems.

Below I provide the slides that I presented about the project at the lecture.

Crab - A Python Framework for Building Recommendation Systems

View more presentations from Marcel Caraciolo

Meet the Muriçoca Labs here  and the link for the Crab framework here.

Regards,

Marcel Caraciolo

Evaluating Recommender Systems - Explaining F-Score, Recall and Precision using Real Data Set from Apontador

Hi all,

In this post I will introduce three metrics widely used for evaluating the utility of recommendations produced by a recommender system : Precision , Recall and F-1 Score.  The F-1 Score is slightly different from the other ones, since it is a measure of a test's accuracy and considers both the precision and the recall of the test to compute the final score.

Introduction about the Recommender Systems Evaluation

The Recommender systems are a sub-domain of information filtering system techniques that attempts to recommend information items such as movies, programs, music, books, page that are likely to be of interest of the user.  The final product of a recommender system is a top-list of items recommended for the user ordered by a evaluated score that represents the preference of that item for the user. So highest the value, more interested the user will be.  But to produce the right recommendations is not trivial and there are several studies and research on evaluating the recommendations of such engine.

Therefore, when you develop a recommender engine for your problem domain, the main question after all work is done is: "What are the best recommendations for the user ?"  Before looking after the answers, we should investigate the question.  What exactly we mean as a good recommendation ? And how will we known when the recommender system is producing them ?  The remainder of this post is to explain how we can evaluate such engines in a way that we provide the best possible recommender that should recommend possible items that the user hasn't yet seen or expressed any preference for. A optimal recommender system would be the one that could predict all your preferences exactly would present a set of items ranked by your future preference and be done.

For that , most recommender engines operate by trying to do just that, estimating rating for some or all other items.  One possible way of evaluating recommender's suggestions is to evaluate the quality of its estimated preference values, that is, evaluating how closely the estimated preferences match the actual preferences of the user.

Introducing Precision and Recall Metrics

In recommender systems,  for the final the user the most important result is to receive an ordered list of recommendations, from best to worst.  In fact, in some cases the user doesn't care much about the exact ordering of the list - a set of few good recommendations is fine. Taking this fact into evaluation of recommender systems, we could apply classic information retrieval metrics to evaluate those engines: Precision and Recall. These metrics are widely used on information retrieving scenario and applied to domains such as search engines, which return some set of best results for a query out of many possible results.

For a search engine for example, it should not return irrelevant results in the top results, although it should be able to return as many relevant results as possible.  We could say that the 'Precision' is the proportion of top results that are relevant, considering some definition of relevant for your problem domain. So if we say 'Precision at 10' would be this proportion judged from the top 10 results.  The 'Recall' would measure the proportion of all  relevant results included in the top results. See the Figure 1 as an example to illustrate those metrics. 

Precision and Recall in the context of Search Engines

In a formal way, we could consider documents as instances and the task it to return a set of relevant documents given a  search term. So the task would be assign each document to one of two categories:  relevant and not relevant.  Recall is defined as the number of relevant documents (the instances that belongs to relevant category) retrieved by a search divided by the total number of existing relevant documents, while precision is defined as the number of relevant documents (the instances that belongs to relevant category) retrieved by a search divided by the total number of documents retrieved by the search.

In recommender systems those metrics could be adapted so:

"The precision is the proportion of recommendations that are good recommendations, and recall is the proportion of good recommendations that appear in top recommendations."

In recommendations domain, a perfect precision score of 1.0 means that every item recommended in the list was good (although says nothing about if all good recommendations were suggested) whereas a perfect recall score of 1.0 means that all good recommended items were suggested in the list (although says nothing how many bad recommendations were also in the list).

Running to an example

For showing an example of evaluating a recommender system, let's test-drive a 'slope-one' recommender on a simple data set fetched from the brazilian location-based social networking website, software for mobile devices Apontador. Its main goal is to help people to interact with their friends and update their location by using GPS enabled mobile devices, such as iPhones and Blackberries. The sample data set, I've fetched using the Apontador API by writing a simple python crawler for accessing their data (The code I used is based on the Python Library developed by Apontador).  The output is a comma-delimited file with 3463 samples composed by user IDs, location IDs (places) and the ratings (preference values from the range 1 to 5) for that location.  In the figure below you can see the structure of this file. Unfortunately, for privacy purposes I can't show the respective usernames and places for each place rated.

234 UserIDs, 1599 PlaceIDs,  3463 Ratings for the Apontador Data Set

After some pre-processing for the experiments, I have pre-processed the database and came into a rating distribution. This plot represents a heat map illustrating the distribution of the ratings evaluated by the users (rows) to places (columns). The black areas represent the absence of the rating for that particular place from that user.

Ratings Matrix - Users x Items

To evaluate the accuracy of the recommender engine we must have a training data and a test data. Generally, this can be simulated to a recommender, since using new items it is not predictable for sure how the user will like that new item in the future. For this, the data mining researcher must set aside a small part of the real data set as test data. These test preferences are not present in the training data fed into a recommender under evaluation - which is all data except the test data. Therefore, the recommender is asked to estimate preferences for the missing test data, and the scores estimated are compared to the actual values.

Base on this data set split, it is simple to produce a kind of "score" for the recommender. For instance, we could compute the average difference between the estimated and actual preference. This references to another popular metric used to evaluate classifiers called root-mean-square.  It is a metric represented by the square root of the average of the squares of the differences between actual and estimated preference values. The optimal classifier is the one  that have lower scores (RMSE), because that would mean  the  estimates differed from the actual preference values by less. 0.0 would mean perfect estimation -- no difference at all between the estimates and actual values.

In the figure above,  the table illustrates the difference between a set of actual and estimated preferences, and how they are translated into scores. RMSE heavily penalizes estimates that are quite different in range such as the place 2 there, and that is considered desirable by some.  The magnitude of the difference  is important for example when you estimate an item with 2 stars which the actual preference would be 5 stars, it is probably more than twice as 'bad' as one different by just 1 star.

After running our recommender system using as inputs the training and test set, which it will compare its estimated preferences to the actual test data. The main code for this task can be found here at my personal repository at Github (Crab Recommender System). We will use 70% of the data to train; and test with other 30%.  And those sets are chosen randomly.

Evaluating  the Slope One Recommender

It shows as result three scores: The first one,  it is a score indicating how well the recommender (slope-one) performed.  In this case we use the Root Mean Square Error (RMSE) . The value 1.04 is not great, since there is so little data here to begin with. Your results may differ as the data set is split randomly, and hence the training and test set may differ with each run.

The second and the third ones are respectively the precision and recall. Precision at 20 is 0.1722; on average about 3 of recommendations were 'good'.  Recall at 20 is 0.1722; so only on average about 3 are good recommendations among those top recommended.  But we still haven't decided what exactly is a 'good' recommendation ? Intuitively, the most highly preferred items in the test set are the good recommendations, and the rest aren't.

Let's take look at the preferences of the user 2452498672 at our simple data set. If we consider as test data the preferences for items A,B,C and the preference values for these 4, 3, 2.  With these values missing from the training data, our expectation is that the recommender engine to recommend A before B, and  B before C because we know the order that the user 2452498672  prefer those items. But how will we know which item is a good idea to recommend ?  Consider the item C which the user doesn't seem to like it much or the item B that is just average. We could consider that A is a good recommendation whereas B and C are valid, but not good recommendations. So we conclude that it is important to give an threshold that divides good recommendations from bad. If we choose not to pick explicitly one, we could use some statistics like the user's average plus one standard deviation for example.

If we decide to vary the quantities the number of recommended items, we could plot a graph by using these two measures together (precision x recall) so that we can assess to what extent the good results blend with bad results.  The goal is to get the precision and recall values for my recommendation lists both close to one. The figure below shows the plot of those quantities varied for the slope-one recommender. For each list of N recommendations, we enter a point that corresponds to the precision and recall values of that list.  The Good precision-recall points are located in the upper-right conner of the graph because we want to have high precision and high recall. These plots are extremely useful for you to compare different approaches for a particular data set.

Precision-Recall Graph

Looking at the figure we can conclude that the slope-one approach is not particular efficient for this type of data set maybe because of small amount of samples to train/test the recommender or because of the characteristics of this data set.  

Explaining  F1- Score

The F-Score or F-measure is a measure of a statistic test's accuracy.  It considers both precision and recall  measures of the test to compute the score. We could interpret it as a weighted average of the precision and recall,  where  the best F1 score has its value at 1  and worst score at the value 0.

F-Score Formula (Image from Wikipedia)

In recommendations domain, it is considered an single value obtained combining both the precision and recall measures and indicates an overall utility of the recommendation list.  

Running to an example

Running again our slope-one recommender into our simple data set we get as result the value  0.1722. 

Evaluating  the Slope One Recommender

 As we can see by the result the recommender performed not well at this data set. It can be due to the amount of data set or the particular characteristics of the data set that is not appropriate for this type of algorithm. It would be necessary more robust tests to see its performance and compare with another approaches.  One of the particular features of slope-one recommender is that can produce quick recommendations at runtime with a simple algorithm, but it takes significant time to pre-compute its internal structures before it can start.

The figure below presents our plot combining the length of the recommendation lists represented by 'at' using our training and test data set and the F-scores estimated for each amount.  It is expected that the best one approaches are with the F-Scores with values nearby 1.0.

F1 Score Graph, the best are with score f near to 1.0 (top right of the graph)

Conclusions and Contribution

For the slope-one recommender the values for precision and recall produced are interesting and illustrates   the power of a simple collaborative filtering technique which involves just a little bit of linear algebra. You can learn more about the Slope-One recommender system here. Soon I will also talk more about this technique in a dedicated post.  What is important to figure out  in those evaluations is that you have to choose carefully which recommendation algorithm to use. Each algorithm has its own characteristics and properties that can interact in harder ways with a given data set.  So is essential to use as many as possible variations of collaborative , content and hybrid algorithms to evaluate which one is faster or more accurate to the data set we will want to work with.

Another important observation related to precision and recall tests is how can we define what a 'good' recommendation is. As we have seen earlier, we must define a threshold to represent the usefulness of an item recommended and a poor choice could really prejudice the evaluation of the recommender algorithm. Furthermore, those tests could be problematic if we consider recommendations that aren't not necessarily among the user already knows about!  Imagine running such a test for a user who would love the restaurant 'Recanto Paraibano'.  Of course it is a great recommendation for this user, but the user has never heard of this restaurant before. If a recommender actually returned this restaurant when recommending new places to go, it would be penalized; since the test framework can only pick good recommendations from among those in the user's set of preferences already. It is a discovery problem, and a harder task for recommender engines and is a special topic approached by several researchers in the literature.

The problem is further complicated if we consider the preferences as 'booleans' such as 'liked' or 'disliked' and don't contain preference values.  This implies that the test doesn't have a notion of relative preference on which to select a subset of good items. So the best test is to randomly select some 'liked' items as the good ones.  But despite of all these problems the test has great use but it is not perfect, so you must understand the test's limitations in the context of the features of the data set available for you to work.

In this post I presented some metrics used to evaluate the quality of the recommendations in a recommender engine and explained through some examples using real data set from Apontador social network.  All the code used here is provided at by personal repository at Github  and is all written in Python.

Finally, I conclude that evaluations are really important in the recommendation engine building process, which can be used to empirically discover improvements to a recommendation algorithm.

Below all the references used to write this post. 

I hope you have enjoyed this post.

Regards,

Marcel Caraciolo

References

Herlocker, Evaluating Collaborative Filtering Recommender Systems, 2004. 

Wikipedia, F1-Score.

Wikipedia, Precision and Recall.

Bryan Sullivan's Blog, Collaborative Filtering made easy, 2006.

Apontador, Apontador API.