2
$\begingroup$

I am working on recommender systems, and using some methodology I have got a probability of each user liking a movie. To elaborate, say user $u_1$ has the following distribution for movie preferences over $8$ movies:

m1     m2    m3   m4    m5    m6    m7   m8
0.12   0.2   0    0.15  0.15  0.3   0    0.08

This shows the preference of $u_1$ towards movies. So $u_1$ prefers movie $m_6$ the most , $m_4$ and $m_5$ equally, and so on. A $0$ means that $u_1$ hasn't seen movies $m_3$ and $m_7$.

Similarly I have the probability values for another user $u_2$ on these 8 movies. I need to know how to compute the similarity between these two probability vectors, because this helps me find the most similar users to a given user, and this is what helps me in collaborative filtering.

I am aware of one method called cosine similarity, but I'm not sure if it's the best way to find similarity in this context. Are there any other methods to find the similarity between two users?

$\endgroup$
2
  • $\begingroup$ What are you trying to achieve by knowing the movie preference similarities of two users? Are you trying to recommend movies to users? Is there anything else other than this that you are trying to achieve by this? $\endgroup$
    – caveman
    Jul 19, 2016 at 20:06
  • $\begingroup$ Yes, my aim is to find similar users to the user "u" in question, and using the movie preferences of these similar users, recommend the top N movies to user "u", which "u" has not rated. $\endgroup$ Jul 20, 2016 at 10:22

5 Answers 5

1
$\begingroup$

Q1: What's the similarity between movie preferences of two users?

A1: Depends. You first need to define the aspect of similarity that you are looking for. In my view, in order to know this aspect, before that you need to specify your objective of knowing this similarity score.

Do you need this similarity measure to create clusters of similarly minded users, and then use movies that they watch to recommend them on others in the same cluster that haven't watched yet?

Let's say that $S$ is the scores random variable, $U$ is the users random variable, and $M$ is the movies random variable. For any user $u_i$ and any movie $m_j$, what we want is knowing this scores expectation: $$ \mathbb{E}\big[S|U=u_i, M=m_j\big] $$

If movie $m_j$ is unseen by user $u_i$, then movie $m_j$ is a candidate for being recommended to $u_i$. If the scores expectation for movie $m_j$ is enough, i.e. greater than some threshold $t$, then we shall recommend it to user $u_i$.

But how can we find $\mathbb{E}\big[S|U=u_i, M=m_j\big]$? We are still in the past where user $u_i$ hasn't seen $m_j$.

Therefore we need to find its estimation $\mathbb{\widehat E}\big[S|U=u_i, M=m_j\big]$.


Q2: How can we estimate $\mathbb{\widehat E}\big[S|U=u_i, M=m_j\big]$?

A2: We need to look at the behaviour of user $u_i$ in relation to past movies that $u_i$ has watched, and then look at how similar movie $m_j$ is to the past movies, and based on this similarity decide the score that $u_i$ would give it if he watches it.

But we can do even better by looking at similarly behaving users $u_a,u_b, \ldots$ to $u_i$ in order to enhance our prediction of $\mathbb{\widehat E}\big[S|U=u_i, M=m_j\big]$.

We can do even better by also looking at general world events (call it context maybe?). E.g. certain recent events can make certain users end up wanting to watch different things.

To cut it short, try this:

  1. Represent the all users as $n$ dimensional vectors. The components of such vectors could be movie ratings, or it could be other things like how they review movies, or even how they click and browser the movie streaming website. User representation is very general, what you mention above (e.g. movie ratings) is only a special case of user representation.
  2. Represent each movie as an $m$ dimensional vector. There are many ways to do this. Simply looking at the list of user rankings for the movie is only a special case of representing the movie. You can look at things such as, movie length, distribution of sound, distribution of visual effects, names of characters that play in the movie, etc. (You can even go as extreme as putting the whole movie in such that each dimension represents the byte value! But this could be too extreme).
  3. Create a dataset such that each user-movie-score triple is represented as a vector. This will give us an $n+m+1$ dimensional vector (recall that $n$ is the user representation, and $m$ is the movie representation). The score is just one number, so it adds just $+1$ to the dimensionality. Say that you have $1000$ users, then you will have $1000$ rows, where each row is a $n+m+1$ dimensional vector. You may also add the context information to each row in the dataset (e.g. augmenting a representation of the context as a $c$ dimensional vector, so each row becomes $n+m+c+1$ dimensional vector).
  4. Train Random Forests on this dataset and ask it to analyze the $n+m$ components (user-movie components) in order to predict the last component (the movie scores). This will give you a regression model.

Then, in order to use this model to predict scores, repeat the same steps 1 to 3, except for pairing users against movies that they haven't seen. Then plug these vectors against the Random Forests regression model to get an expected score for the test user-movie tuple. Finally, if this score is large enough, then recommend the test movie to the test user.

Why is this nice?

  • Random Forests is non-parametric and can identify non-linear patterns.
  • Easy to distribute.

Q3: Can you use other regression methods?

A3: Yes. You need to choose the algorithm that seems to work best in your domain. I suggested Random Forests because I think it's a nice baseline to start with, but you can try fancier ones such as deep learning algorithms along with different methods of representing your users and their movies.

$\endgroup$
2
  • $\begingroup$ Hi Caveman. Thanks for such a thorough answer! However, I am specifically looking at how to just find the similarity between the probability scores of any two users. Using this I can find the most similar users to the current user, and then I recommend the top movies to the user in question using the movie ratings of the similar users. Also could you please have a look at this stats.stackexchange.com/questions/224295/… question and let me know your thoughts on this. $\endgroup$ Jul 20, 2016 at 10:40
  • $\begingroup$ Np. I added another answer that simply describes a method of comparing the similarity of two vectors of movie ratings. It's here stats.stackexchange.com/a/224785/100507 --- but note that all these are heuristics with beefy assumptions and are by no means necessarily optimal (unless you show that your scenarios have assumptions that match those of theirs) $\endgroup$
    – caveman
    Jul 20, 2016 at 17:50
0
$\begingroup$

First, make sure that you preprocess the data. So do the normalizations.

Here are some options:

  1. cosine similarity: use it if the number of movies are small and that data is dense. If the ratings is sparse, aka if users a and b did not rate the same movies, this would fail, because the two users would be orthogonal in the vector space.

euclidean distance: this yields comparable results to cosine similarity when your data is normalized and faces the same problems as cosine similarity

  1. matrix factorization: essentially find latent vectors for every movie and every user. The similarity between two users is just the cosine similarity of their latent vectors. This is useful when the data is sparse.
$\endgroup$
2
  • $\begingroup$ Hi! Thanks for the answer. My data is indeed sparse, which is why I was looking for alternatives to cosine similarity. Could you please elaborate or provide links to the matrix factorization and how to find these latent vectors? What exactly are these latent vectors, and how do these resolve the difficulty that two users might have really less movies that they have rated as common? $\endgroup$ Jul 20, 2016 at 10:44
  • $\begingroup$ Also, what kind of normalizations should be done to use the euclidean distance? $\endgroup$ Jul 20, 2016 at 10:45
0
$\begingroup$

Correspondence analysis(CA), a variant of PCA, will be the best method for such an analysis. CA involves probabilistic approach. It provides a two-dimensional graphical display (biplot) containing points corresponding to every users and every movies. Same category of users will be placed together. Same movies will be placed together(may be because of genre of films). One can also find the the most liked movies by a user using the concept of inner product of vectors. Code for CA can be found on internet and is easy to use.

$\endgroup$
1
  • $\begingroup$ Could you please point out assumptions of the CA method? E.g. does it assume that some relationship is linear? $\endgroup$
    – caveman
    Jul 20, 2016 at 17:45
0
$\begingroup$

This is an alternative view to the answer here.

User $u_i$ hasn't watched the movie $m_j$ yet, but what is the probability that user $u_i$ will give movie $m_j$ a score that is $\ge t$ if he watches it?

Let's say the the set of movie ratings/scores is discrete and is $\mathcal{S}$. Which is common. For example, in a 5-star rating system $\mathcal{S} = \{\frac{1}{5}, \frac{2}{5}, \frac{3}{5}, \frac{4}{5}, \frac{5}{5}\}$. Also let's say that $\mathcal{U}$ is the set of users, and $\mathcal{M}$ is the set of movies.

$t$ is some threshold that we define that we think is a good cut-off point that tells us when is it worthy to recommend a movie to someone. Maybe $t = \frac{4}{5}$ is a good idea.

Let's say that $S$ is scores r.v. that takes values in $\mathcal{S}$, $U$ is users r.v. that takes values in $\mathcal{U}$, and $M$ is movies r.v. that takes values in $\mathcal{M}$.

Then we want to find this probability:

$$ P = \sum_{s \in \mathcal{S}:s \ge t}\Pr(S=s|U=u_i, M=m_j) $$

Only if $P > 0.5$ we recommend movie $m_j$ to user $u_i$.

Let's say that we have $n$ number of movie ratings that their score is $\ge t$. Some of the ratings are by the target user $u_i$ on different movies, some more of them are on the target movie $m_j$ but by different users $u_k$ where $k \ne i$, and usually the vast majority of them are by different users on different movies.

$$ \widehat{\Pr}(S=s|U=u_i, M=m_j) = \frac{1}{n}\sum_{k\in\mathcal{U}}\sum_{l\in\mathcal{M}}\begin{cases} \texttt{sim}^*(u_i,u_k,m_j,m_l) & \text{ if } \texttt{score}(u_k,m_l) \ge s\\ 0 & \text{ if } \texttt{score}(u_k,m_l) < s\\ \end{cases} $$

Where $\texttt{sim}^*(u_i,u_k,m_j,m_l)$ is a similarity score in $[0,1]$ that is $1$ when $u_i$ is perfectly similar to $u_k$ and $m_j$ is perfectly similar to $m_l$ (i.e. $u_i=u_k, m_j=m_l$, which never happens), and is $0$ when $u_i$ is perfectly dissimilar to $u_k$ and $m_j$ is perfectly dissimilar to $m_l$. So usually this similarity score is in between $0$ and $1$.

So what I suggest to you is to give up on only looking for users similarities, and -instead- extend it to user-movies similarities.

You need to find a trade-off between how import user and movie similarities are. For example, if a user is extremely dissimilar to $u_i$, but watches a movie that is extremely similar to movie $m_j$, it nonetheless tells you something that is more than nothing, and you better consider this something. But if both the user and the movie are dissimilar to $u_i$ and $m_j$, then you can probably ignore it.

You need to find the $\texttt{sim}^*$ function. This can be done by searching for all such similarity functions and only choose the one that that minimize some error. The error that I suggest to minimize is this: $$ \texttt{sim}^* = \underset{\texttt{sim} \in \mathcal{H}}{\text{arg min }}\sum_{i \in \mathcal{U}}\sum_{j \in \mathcal{M}} \sum_{k \in \mathcal{U}}\sum_{l \in \mathcal{M}}|\texttt{sim}(u_i,u_k,m_j,m_l) \times \texttt{score}(u_i, m_j) - \texttt{score}(u_k, m_l)| $$ where $\mathcal{H}$ is the space of functions.

Simply, you can assume that $\texttt{sim}^*$ is a polynomial, and then use things like gradient descend or grid search, or whatever suitable search for $\texttt{sim}^*$ and end up finding its estimation $\widehat{\texttt{sim}}^*$ (due to limitations in the assumption that $\texttt{sim}^*$ is a polynomial and limitations in the searching algorithm). As for users and movies, you can represent them as vectors as described here.

Note: Not sure about the minimization objective above. I feel it can be made simpler at least.

$\endgroup$
0
$\begingroup$

Let's say that we have movies $m_1, m_2, \ldots, m_n$. So we have $n$ many movies.

Also let's say that we have users $u_1, u_2, \ldots, u_k$. So we have $k$ many users.

Now you have chosen two users out of those $k$ many users. Namely $u_1$ and $u_2$ users.

Now, your goal is to find to similarity between these two users $u_1$ and $u_2$.

Here is a heuristic:

  1. Find all common movies that were rated by users $u_1$ and $u_2$. Let's say that the two users have only the following movie ratings in common (say) $m_5, m_7, m_9, m_{12}$.
  2. Create this table for each user:

         | m_5 | m_7 | m_9 | m_12
    -----+-----+-----+-----+------
    u_1  | 0.1 | 0.8 | 0.5 | 0.3
    u_2  | 0.15| 0.7 | 0.6 | 0.8
    
  3. Then find the movie-wise absolute differences:

         | m_5 | m_7 | m_9 | m_12
    -----+-----+-----+-----+------
    u_1  | 0.1 | 0.8 | 0.5 | 0.3
    u_2  | 0.15| 0.7 | 0.6 | 0.8
    -----+-----+-----+-----+------
    diff | 0.05| 0.1 | 0.1 | 0.5
    
  4. Then find the average of the absolute differences: $\frac{0.05 + 0.1 + 0.1 + 0.5}{4} = 0.1875$.

The similarity between the two users is then $0.1875$.

But this simple answer is really bad though for any real-life scenario for at least the following reasons:

  • It ignores time. It assumes that if two users rated a movie similarly in the past, then it is exactly as important as if they rated a movie in the present. This is really an unrealistic assumption because people grow differently over time as they age. Therefore it's important to consider the rating time and penalize older events to make them less related.
  • It ignores other behavioral aspects of users that can hint about their movie preferences. It basically assumes that only knowing users movie ratings is adequate to predict what movies they like in the future. Which is obviously unrealistic. The move information we get about the users, the more we can predict their behavior. Of course there is a data size limits after which returns start to diminish, but I think that we are far away from such limits and we have a lot of room of incorporating more input.

These limitations apply to all other answers (including this one, obviously). What I have been trying to address in my other answers is a better solution hat doesn't have those.

$\endgroup$

Your Answer

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

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