Memory-based algorithms

Memory-based algorithms approach the collaborative filtering problem by using the entire database. As described by Breese et. al [1], it tries to find users that are similar to the active user (i.e. the users we want to make predictions for), and uses their preferences to predict ratings for the active user.

This page will talk about the general ideas; for specific equations and implementations, consult the Breese et. all paper and/or our code.

Similarity Measurements

In order to measure similarity, we want to find the correlation between two users. This gives us a value from -1 to 1 which determines who alike two users are. A value of 1 means that they both rate in the exactly the same manner, whereas a value of -1 means that they rate things exactly opposite (i.e. one high, the other low or vice versa).

There were two similarity measurements we used. The first was the Pearson correlation coefficient. It is the basic correlation algorithm for samples adapted for rating information. It tries to measure how much two users vary together from their normal votes - that is, the direction/magnitude of each's vote in comparison to their voting average. If they vary in the same way on the items they have rated in common, they will get a positive correlation; otherwise, they will get a negative correlation.

The other similarity measurement is called vector similarity. We can treat two users as vectors in n-dimensional space, where n is the number of items in the database. As with any two vectors, we can compare the angle between them. Intuitively, if the two vectors generally point in the same direction, they get a positive similarity; if they point in opposite directions, they get a negative similarity. To simulate this we just take the cosine the angle between these two vectors, which gives us a value from -1 to 1.

Predicting Ratings

In order to predict a rating for an item for an active user, we need to find all weights between the active user and all other users. We then take all non-zero weights and have each other user "vote" on what they think the active user should rate the item. Those with higher weights will matter more in the voting process. Once these votes are tallied, we have a predicted vote.

Note that the voting is based on how far off from a user's average they rate a movie - that is, we want to say how far off from the active user's average the active user will rate the item. Thus, with a positive correlation, the active user agrees with however far off the other user voted on a particular item; and with a negative correlation, the active user disagrees (i.e. goes in the opposite direction) from the other user's vote.


This works relatively well, but there are some enhancements we can make to the weighting techniques.




[1] J.S. Breese, D.Heckerman, and C.Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the Fourteenth Conference on Uncertainty in Artifical Intelligence, 1998.