The idea: people who agreed before will agree again
A film site keeps a ratings matrix: one row per user, one column per film, a rating from 1 to 5 where the user has rated the film. Most cells are empty. To recommend a film, the site has to guess the empty cells. Collaborative filtering guesses them from the ratings alone. It needs no genre, no actor list and no age of the user.
The page shows the neighbourhood method, also called memory-based. Nothing is trained. To fill one cell it does three things:
- measure how similar every other row (or column) is to the target's;
- keep the k nearest neighbours that have a rating to offer;
- take a weighted average of those ratings.
User-user works on rows: "users who rate like Ann gave Titanic a low score". Item-item works on columns: "Ann gave low scores to the films that are rated like Titanic". The other way to fill the matrix is to learn a short vector for every user and film; see Matrix Factorization.
Similarity: cosine and Pearson
Two users can only be compared on the films both have rated, the co-rated films. Ann and Bob share Alien, Matrix and Notebook. The page needs at least two shared ratings; with fewer it shows "—".
Cosine similarity treats the shared ratings as two vectors a and b and takes the cosine of the angle between them (see 2D Vectors and the Dot Product):
cosine(a, b) = (a · b) / (|a| |b|)
Ratings are all positive, so the cosine of raw ratings is always above 0. Ann loves Alien and dislikes Notebook; Eve gives almost everything a 5. Cosine still says 0.79. Every user ends up between 0.57 and 0.99 (Demo 2).
Pearson correlation first subtracts each user's own mean rating, then takes the same cosine. What is left says "above my usual" or "below my usual". Ann minus 3.00 is (+2, −2, −1) on Alien, Notebook, Amélie; Eve minus 4.75 is (−0.75, +0.25, +0.25). The signs disagree everywhere, and Pearson is −0.90. See Correlation and Scatter Plots for Pearson r in general.
| similarity to Ann | Bob | Cat | Dan | Eve |
|---|---|---|---|---|
| cosine | 0.97 | 0.99 | 0.57 | 0.79 |
| Pearson | +0.82 | +0.94 | −0.97 | −0.90 |
Picking k neighbours
Not everyone gets a vote. A neighbour must have a rating for the target (for Ann × Titanic, a user who has rated Titanic) and a similarity above 0. Among those, the k most similar are kept. The idea is the same as in K-Nearest Neighbors, with similarity in place of distance.
With k = 1 the prediction is one person's opinion: Cat, so 2.00 (Demo 3). With k = 2 Bob joins and the answer moves to 1.54 (Demo 1). A large k with cosine lets in users who are not alike at all: with k = 3 Eve becomes a neighbour and the prediction rises to 2.01 (Demo 2). Real systems use k between 20 and 50.
The weighted average
User-user does not copy the neighbours' ratings. Cat's mean is 4.00, so her 3 for Titanic means "below my usual". Each neighbour's rating is taken as a distance from that neighbour's mean, weighted by similarity, and added to the target user's mean:
r̂(u, i) = mean(u) + Σ sim(u, v) × (r(v, i) − mean(v)) / Σ sim(u, v)
Ann × Titanic, Pearson, k = 2:
Cat 0.94 × (3 − 4.00) = −0.94
Bob 0.82 × (1 − 3.00) = −1.63
r̂ = 3.00 + (−2.58 / 1.76) = 1.54
This matters most for a user who rates high or low. Cat's neighbours for Notebook are Bob (gave 2) and Ann (gave 1). A plain weighted average says 1.51. But both are below their own mean of 3.00, by 1 and by 2, and Cat's mean is 4.00, so the prediction is 4.00 − 1.49 = 2.51 (Demo 5).
Item-item averages the target user's own ratings of the similar films. They all come from one person, so there is no mean to correct for:
r̂(u, i) = Σ sim(i, j) × r(u, j) / Σ sim(i, j)
Ann × Titanic, Pearson, k = 2:
Notebook 0.92 × 1 = 0.92
Amélie 0.90 × 2 = 1.80
r̂ = 2.72 / 1.82 = 1.49
Both methods agree here: Ann would not like Titanic (Demo 4). A prediction of 3.5 or more would be worth recommending.
User-user or item-item
| user-user | item-item | |
|---|---|---|
| compares | rows (users) | columns (films) |
| averages | the neighbours' ratings of the target film | the target user's ratings of the neighbour films |
| similarities change | every time a user rates something | slowly: a film's column has many ratings, so it can be computed ahead of time |
| explanation to the user | "people like you liked it" | "because you liked Alien" |
| first used at scale | GroupLens news filtering, 1994 | Amazon, "customers who bought this also bought" |
A shop usually has far more users than items, and a user rates only a few items, so two users often share nothing. Item columns are fuller. That is why large sites moved to item-item.
Cold start
Everything above needs ratings to compare. A new user has none. Fay shares no film with anyone, so no similarity exists and she has no neighbours. Item-item fails too, because she has rated no film to start from. The page falls back to the film's mean, 3.50 for Titanic, which is the same for everybody (Demo 6).
A new film is worse. Ann has good neighbours, but none of them has rated Dune. Dune's column is empty, so it is similar to nothing. There is no prediction at all, and the film is never recommended until someone rates it (Demo 7).
Real systems get around the cold start with something other than ratings: a sign-up quiz, the most popular items, or features of the user and the item (genre, text, price). Using item features is called content-based filtering, and a mix of both is a hybrid recommender.
What the page leaves out
Textbook Pearson takes each mean over the co-rated films only; the page uses the mean of all of a user's ratings, as many implementations do. It also skips: shrinking a similarity that rests on very few shared ratings; adjusted cosine for item-item (subtracting user means from the columns); dividing by each user's spread as well as the mean; implicit feedback such as clicks and purchases; sparse storage and approximate neighbour search for millions of users; and measuring the result with RMSE or precision@k.