6
$\begingroup$

I'm learning about collaborative filtering, and all the resources I've found so far describes how to find items a user might like. However, how would I find the most similar users to a specific user, given the following conditions:

  • The user-item ratings are sparse, i.e., most of the items are likely not rated by a user.
  • Ideally, the similarity score between user A and user B is affected more heavily by items they've both reviewed. However, given the sparse nature of the ratings, even if an item is only rated by one of the users, it should still affect the similarity score somewhat based on what we predict the other user's rating would be.
$\endgroup$

2 Answers 2

3
+100
$\begingroup$

Collaborative filtering has two main steps. At a high level:

  1. Find similar users
  2. Recommend items based on what those similar users liked.

So, I'd think we automatically solve the "find similar users" problem in the course of developing a collaborative filtering recommender system. We'll be addressing just the first subproblem here, for which I've adapted Chapter 9.3 of Mining of Massive Datasets to a constructed toy example.

Toy Example & a Naive Attempt

Suppose we have a utility matrix $U$, where each row corresponds to a user, and each column corresponds to an item. This matrix is populated with user ratings of each item (in this case, movies): $0$: dislike, $1$: like, and a blank, which indicates no rating was given. A possible $U$ is shown below:

Movie1 Movie2 Movie 3 Movie 4
Alice 1 0 1
Bob 1 0 1
Charlie 1 0 1

In reality, this matrix is probably much sparser (as you correctly note).

The problem of evaluating user similarity then boils down to defining some metric for comparing two vectors (i.e., rows of $U$). As a first attempt, let's try a common metric:

Jaccard/Intersection-over-Union. The Jaccard metric (or, the more-intuitively-named intersection-over-union) is calculated as follows:

$$J(A, B) \triangleq \frac{\#(\text{items rated by A and B})}{\#(\text{items rated by A or B})}.$$

The Jaccard metric ranges from 0 (most dissimilar) to 1 (most similar). Convince yourself that this is indeed the correct range.

As an example, $J(\text{Alice}, \text{Bob}) = 2/4$, since both users rated movies 2 and 3, but only Alice rated movie #1 and only Bob rated movie #4. Compute the others as an exercise.

This metric, out of the box, sometimes addresses your constraint that items that were rated by both individuals are weighted more heavily (increasing the numerator) than items that were rated by only one individual (increasing the denominator). But there are serious limitations.

Limitations. At this point, you probably noticed something strange -- Alice and Bob's ratings for Movie 2 and Movie 3 disagree, but this doesn't get reflected in the final similarity score. This metric might be suitable for different types of data (e.g., bought product vs. didn't buy product -- try thinking of other examples), but we've lost a lot of information about our ratings.

Cosine similarity is also sometimes used for vector similarity, and could more directly address your approach with a simple change: upweight dimensions in which both individuals rated an item. However, this also requires you to set "blank" values of $U$ to some number. I'd encourage you to think about the limitations/assumptions that this approach makes.

Hopefully, this simple example highlights the difficulty of the problem. Now, let's try incorporating your two constraints: (1) sparse ratings, and (2) heavier weightings for items rated by both users (while still considering items rated by one user).

Clustering: Combating Sparsity

Combating sparsity. Maybe we have some prior knowledge about the items being rated, and we can merge multiple items into a cluster by creating a revised utility matrix, where we group columns (items) and fill cells with the average of each users' ratings among each cluster (or blank if a user did not rate any items in a cluster). For example, if we merge Movies 1 and 2 from $U$, we might get:

Movie1+2 Movie3 Movie4
Alice 0.5 1
Bob 1 0 1
Charlie 0.5 1

We could then use the same similarity metrics as before, and cluster users that way. Or...

Clustering, again!? Those pesky blank spaces are hard to fill in -- the naive metrics either throw them away (Jaccard), or have to fill in some arbitrary value (Cosine distance). What if we tried clustering similar users in the same way:

Movie1+2 Movie3 Movie4
Alice+Charlie 0.5 1 1
Bob 1 0 1

Cool! Now, everything's filled in, and (1) we found some similar users (Alice + Charlie), and (2) if we were to expand this matrix to many more users, now that the Alice+Charlie row is filled in, we could perhaps use those naive distance metrics to find similar users.

In reality, you might need to repeat this item-level + user-level clustering process multiple times.

As an exercise, I'd try to work through the exercises in the end of Ch. 9.3 (p. 327-28).

With clustering, we might be able to come up with a rudimentary user similarity metric (e.g., # of "clustering steps"/merges it takes to unify two individuals). But this is not good at breaking ties in sparse data -- what if we merge multiple users into one cluster in one step?

More advanced similarity metrics

Past work has proposed metrics such as PIP (Proximity-Impact-Popularity). Given a pair of users, this metric (1) upweights ratings with similar valence (both positive or negative), (2) upweights identical ratings with stronger valence (e.g., both giving 5/5 star rating > both giving 4/5 star), and (3) upweights similar ratings that are "distinctive" (similar & far from average rating across all users). The full details are in the paper.

PIP is one way to encode OP's desire that " the similarity score between user A and user B is affected more heavily by items they've both reviewed."

This paper is quite well-cited, so its descendant works might give you further inspiration/improvements for your use case. In any case, there are survey papers that explore different distance-based metrics for user similarity (though I'm not the best to judge their quality).

Matrix factorization for user/item similarity

The other option is to factorize the utility matrix $U$ into some matrix product $U \approx PQ^\top$, where $U \in \mathbb{R}^{n_U \times n_I}$ such that $n_U, n_I$ are the number of unique users and items, respectively, $P \in \mathbb{R}^{n_U \times d}$, and $Q \in \mathbb{R}^{n_I \times d}$. $P$ and $Q$ are interpretable as matrices whose rows correspond to some abstract representation of users and items, respectively (i.e., the columns represent values of some latent factors). The simplest version of this boils down to solving some optimization problem of the form

$$\underset{\mathbf{P}, \mathbf{Q}}{\text{minimize}} \sum_{i=1}^{n_U} \sum_{j=1}^{n_I} (U_{ij} - P_i \cdot Q_j^\top)^2$$

and then applying a pre-existing distance metric (e.g., cosine distance, Pearson correlation) to the rows of $P$. This is a simplified version of Sec. 2 of this paper.

Hopefully, this answers your question -- I'd encourage using these resources as a starting point.

$\endgroup$
2
  • 1
    $\begingroup$ It seems with this method we get clusters of similar users, but there is not comparable similarity "scores" produced as a result? Is it possible to construct some kind of similarity measure/score so that I can recommend the top-K most similar users to a certain user? $\endgroup$ Commented Sep 2, 2023 at 22:30
  • $\begingroup$ Great question (+1) -- I've updated the answer with some more advanced methods that are more amenable to top-K ranking, though I'll admit this takes me to the edge of my expertise. I hope this is sufficient to give you a launchpad to look for more resources. $\endgroup$ Commented Sep 3, 2023 at 0:34
0
$\begingroup$

Without reference to any specific algorithm:

Information about similarity among users are already encoded in the item matrix $A$ in the case of item-item collaborative filtering (CF).If there are $N$ items over columns and $M$ users over rows. Once CF algorithm is applied and entire matrix is known, columns of transpose of $B=A^{T}$ can generate similarity scores. User's preferences live in the $ColumnSpan(B)$ space.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.