3
$\begingroup$

I'm currently learning about Collaborative Learning and Content-based Recommendation.

One of the main things that is discussed in both methods is about calculating similarity between two users or two items. Commonly, similarity between two entity (each represented by a vector) can be calculated using Cosine similarity or other similarity coefficients.

One question that I haven't found the answer is about calculating similarity between two entities in which each has a feature that explains each entity's location.

Let's say, the entities in my data is about restaurants and each restaurant has several attributes such as

  • food price average
  • user rating/review score
  • location in $(\text{lat}, \text{long})$
  • etc.

For food price average or user rating, maybe it's still relevant to include them in cosine similarity function, but how about location–which is described in a tuple of real numbers? What's the best way to include distance between entities as a component in the similarity function?

Thanks!

$\endgroup$
2
$\begingroup$

Perhaps you could transform the latitude and longitude into spherical coordinates. In this coordinate system, the cosine of the angle between the vectors has a natural geometric interpretation.

$\endgroup$
  • $\begingroup$ After I experimented a little, this option might be work just well. I converted $(lat, long)$ coordinates to $(x, y, z)$ using WGS84 as mentioned here. $\endgroup$ – sokokaleb Apr 11 '17 at 20:05
1
$\begingroup$

This answer is from my view point of how I would insert distance component into restaurant recommendations.

Firstly, I don't feel it is right to insert this distance component into cosine similarity because it is just a innocent dot product which says how similar vectors are and nothing more. But sorting order of recommendations can be changed by using a simple formula like

Sort order based on the values $r_i*(1+e^{-b(dist)})$ or any similar formula for that reason.

where $b(.)$ is the bucketed value for the distance between the restaurant and customer which can be found from latitude longitude position of the same by using Haversine formula and $r_i$ the original restaurant rating. This does not change the restaurant rating but merely changes the sorting order based on user location.

Example : Let [(A, 3.5, 2 miles), (B, 4, 10 miles)] be a sample list of elements of tuple type (Restaurant, rating, distance)

Our buckets are say 0-2 miles is 0 and 2-5 miles as 1 and 5-10 miles as 2 etc. So A and B compound rating comes to $7$, $4.5$. So A will be on top.

I hope this kind of helps. Any edits giving some cool ideas and good references are always welcome.

$\endgroup$
  • $\begingroup$ That would be one interesting option to sort the items in recommendation. I'm in favor of that inverse exponential function as it would bring up locations that are closer to the top of recommended items. However, I'm still looking into option whether it's possible to include it in the vector itself. Thanks! $\endgroup$ – sokokaleb Apr 10 '17 at 3:58
1
$\begingroup$

Let's recall the rating prediction of restaurant $ x $ and user $i$ as a weighted sum according to the similarity:
$$r_{x,i} = \frac{\sum_{j\in N(i,x)} s_{i,j} \cdot r_{x,j}} {\sum_{j'\in N(i,x)} s_{i,j'}} $$ were $ s_{i,j}$ is the similarity between user $i$ and user $j$ and $N(i,x)$ is the set of all restaurants that were both similar to restaurant $x$ and were rated by user $x$. This set can be found by applying knn and finding $k$ similar users to user $i$ (i.e. the collaborative in collaborative filtering).

Now given more prior knowledge, such as geographical location, we can tweak our formula to account for those biases. Generally speaking, when you see a user rates a restaurant, you should account the habits rating of that user (how much does he usually rates above or below the mean) and the restaurant affect (how the restaurant is rated in respect to the mean rating).
Denoting the total rating mean as $\mu $, the user mean rating as $\bar{r_i}$ and the restaurant average rating as $\bar{r_x}$, we can break down the rating to it's biases (deviances from the mean) as such: $$b_{x,i} = \mu + \underset{b_i}{\underbrace{(\bar{r_i} - \mu)}}+ \underset{b_x}{\underbrace{(\bar{r_x} - \mu)}}$$ Now the prediction will look as follows: $$r_{xi} = b_{x,i} + \frac{\sum_{j\in N(i,x)} s_{i,j} \cdot (r_{x,j}-b_{x,j})} {\sum_{j'\in N(i,x)} s_{i,j'}} $$ Now this was quite general, just in order for us to speak in terms of biases. Once at hand we can apply them as we see fit.
The most simple way I can think of (you're welcome to share more elaborate ones) is to take the restaurant bias $b_x$ and instead of calculating it over the whole data (using the general $\mu$), you can do as follows:

  • Take all your lats and longs, project them onto some 2D sheet or 3D ellipsoid (Depends on the accuracy you wish to achieve. What projection to use is somewhat an art for it self, there's vast literature, but usually simpler method work good enough).
  • Cluster the restaurants into some $H$ clusters. Those will be geographically related. (Again, Euclidean distance will do, but there are more sophisticated ones)
  • For every cluster $h\in H$ you calculate it's own $\mu^{(h)}$, and now for all the restaurants $x^{(h)}$ related to cluster $h$ you calculate it's own bias term: $$b_{x^{(h)},i} = \mu^{(h)} + \underset{b_i}{\underbrace{(\bar{r_i} - \mu^{(h)})}}+ \underset{b_{x^{(h)}}}{\underbrace{(\bar{r_{x^{(h)}}} - \mu^{(h)})}}$$

So, basically, you broke down your general rating data into $H$ geographically close datasets that capture some spatial locality.

I'll be happy to elaborate more if needed.

$\endgroup$
  • $\begingroup$ Hi, thanks for the answer. However, if I correctly understood your answer—which is more of how to "predict rating" and give recommendation—my current concern is not about the recommendation itself, but about the similarity between vectors. Your answer might become useful in later steps of the process. $\endgroup$ – sokokaleb Apr 10 '17 at 4:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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