Recommender systems with collaborative filters
Intro
A recommender system (or recommendation system) is a very important tool for a data scientist, because such systems are widely used by small and large companies for a variety of purposes. Their main mission is to predict the “rating” or “preference” of a user given an item. Amazon, for example, uses recommendation systems to recommend books for their customers based on previous purchases. YouTube and Netflix use recommendation systems for recommending new content to their customers.
Recommender systems goals
Recommender systems promise a lot of benefits to business, such as:
- Increased conversion rate;
- Higher profit margin;
- The user will like your platform better;
- Improves User Experience;
- Increases your LTV and decreases Churn rate.
Common approaches
There are several ways to build a recommendation system, using complex machine learning algorithms or just basic math, the most popular approaches being collaborative filters and content-based filter.
Collaborative filters
In this class of algorithms, for each user an item is indicated based on another user with “similar behavior”. For example, Alice and Bob are two people with similar interests in TV shows. Alice recently watched and liked Game of Thrones, but Bob has not watched it yet. The recommendation system will automatically recommend Game of Thrones to Bob, since his interests are similar to Alice’s.
Content-based filters
When the company knows its products in detail, it is possible to implement a content-based filter system. To implement it, it is necessary to classify all products with tags or similar properties. For example, if I watch the Supernatural TV show, it contains the ‘terror’ and ‘comedy’ tags, so the algorithm will recommend similar tagged content, like the TV show Lucifer.
End-to-end collaborative filter
Some steps are required to implement a basic collaborative filter system:
- Get similarity between users or objects;
- Understand the mathematical concept of similarity;
- Implement the recommender model.
Measuring similarity
The concept of similarity is a complement to distance. The distance between two points can be easily obtained using the Euclidean distance, by calculating the length of a straight line connecting two points. When we talk about similarity, instead of finding out how far two points are, our goal is to find out “how close” the points are. The similarity value is usually expressed as a number between 0 and 1, where 0 means a low similarity, and 1 a high similarity.
Cosine similarity
With two vectors U and V, where U=(3, 5) and V=(1, 5), the distance between U and V can be easily calculated by using Euclidean distance. But how similar are these vectors? A common way to measure similarity is called cosine similarity.
To measure similarity, we need to calculate the angle between the vectors.
The smaller the angle, the greater the similarity. To verify, just remember the properties of the cosine function:
- cos(0º) = 1
- cos(90º) = 0
- cos(180º) = -1
That is, using cosine similarity, when the angle between the vectors approaches 0º, the vectors are very similar (parallel with the same direction), so the similarity is 1. When the angle reaches 90º, the vectors are orthogonal and the similarity is 0º. Finally, with an angle of 180º, the vectors are opposite with similarity -1. Considering only non-negative vectors (in the first quadrant of the Cartesian plane) the similarity varies only between 0 and 1.
With this concept in mind, the similarity can be calculated with the following equation:
This formula exists in every Linear Algebra book and should be familiar to engineering, physics and mathematics students.
Collaborative filter algorithm
The next step after learning how to calculate similarity, is to implement the concept in a collaborative filter algorithm. The process uses similarity between users of a fictional platform.
Defining the problem:
- Our problem is movie recommendation. Given an [i, j] matrix, consider the rating of i users for j movies with the user rating represented by an integer ranging from 1 to 5. If the movie was not rated, its rating is 0;
- For each user, the goal is to recommend a series of movies they have not watched (rating = 0);
- For each movie j and user i who did not watch the movie, we try to find a user from a group U that is similar to user i who has watched the movie j;
- For each similar user u get the rating for the movie j and multiply by the cosine similarity of the user i with u. Dividing the result by the number of users in the U set, we have the weighted average rating for the movie j;
- Now sort the movies by the average obtained for each user and use this value to estimate the user’s rating of the movie, then recommend the first N movies in the ranking for each user.
This technique is so similar to the KNN algorithm that, with some adaptations, it can be used to solve the recommendation problem (which will be explained later).
For example: imagine that I did not watch the movie Forrest Gump, but I watched and rated many other movies. All you have to do is to find a group of users who watched movies that I also watched, and also watched Forrest Gump.
In this example, let’s suppose that we find 2 users with preferences similar to mine. Let’s assume that the first one has a 90% similarity to me and has given 5 stars to the movie, and the second one has an 80% similarity to me and has given 3 stars to the movie. To estimate my rating, the weighted average (0.9×5 + 0.8×3) / 2 = 3.45 is calculated.
Surprise
Surprise is a Python library for building and analysing recommender systems. There is also a built-in MovieLens Dataset with 100,000 movie ratings, from 1,000 users and 1,700 movies. The main purpose of Surprise is to give their users the perfect control over their experiments, provide several ready-to-use prediction algorithms - such as SVD - neighbourhood methods, similarity measures and tools to analyse and compare algorithm performance.
Let's explore Surprise.
Load the MovieLens 100k dataset and import it in Python:
The next step is to select an estimator and similarity measure. In this implementation, the idea is to use a collaborative item-item filtering approach. The estimator selected is KnnBasic with cosine similarity:
The method build_anti_testset allows us to make recommendations to new users, finding all the user-movie pairs in the training set where the user has not watched the movie, and creates a “test suite” from these entries. From its result, we sort and retrieve the top 3 recommendations for each user:
To see the output, just map the movie ID with their name to each user. In the surprise Github dataset you can find this code and others.
The result:
As you can see, each user receives personalised recommendations based on past ratings. A weakness of collaborative filtering is called “cold start” which is characterised by the question:
How will we make recommendations to new users?
Netflix gives its new users a list to select some content that they like. I believe that from that moment on it makes the recommendations.
Conclusion
In this post we saw how to implement a collaborative filter from end to end, from the beginnings of linear algebra, cosine similarity, recommendation system types to a “hello world” of the surprise library with KNN algorithm. It is highly recommended to explore the most out of the surprise library, test other estimators from the surprise lib, and the next step is to use deep learning to make our recommender algorithm, like Boltzmann Machines.
References
[1] C. Mathieu A. Das and D. Ricketts. Maximizing profit using recommender systems. WWW, 2010.
[2] H. Anton. Elementary Linear Algebra. John Wiley Sons, Incorporated,1993.
[3] Z. Gantner H. S. C. Newell B. P. Knijnenburg, M. C. Willemsen. Explaining the user experience of recommender systems, user modeling and user-adapted interaction,. 2012.
[4] T.Keenan. What is content-based filtering?https://www.upwork.com/hiring/data/what-is-content-based-filtering/. Last accessed 18 August 2019.
[5] S.Luo. Introduction to recommender system. https://towardsdatascience.com/intro-to-recommender-systemcollaborative-filtering-64a238194a26, 2018. Last accessed 18 August 2019.
[6] M. Nadeem. How youtube recommends videos. https://towardsdatascience.com/how-youtube-recommends-videos-b6e003a5ab2f , 2018. Last accessed 18 August 2019.
[7] Netflix. How the Netflix recommendation system works. https://help.netflix.com/pt/node/100639. Last accessed 18 August 2019.
[8] R. Sentance. How to boost conversion rates by 32%: a recommendation engine case study. https://econsultancy.com/retail-case-study-personalisation-recommendation/, 2018. Last accessed 18 August 2019.
[9] Surprise. Surprise overview. http://surpriselib.com/. Last accessed 18 August 2019.
[10] Z. Tabaei and M. Fathian. Using customer lifetime value model for product recommendation: An electronic retailing case study. IJEEEE, 2012.
