Hello everyone, my name is Alejandro Bellogin and I am here to present this work I did together
with one of my Bachelor students, Sergio Torrijos, and my PhD student, Pablo Sanchez, about discovering
related users in location-based social networks.
The main motivation for this work comes from
the fact that neighbour-based recommender systems are very easy to understand and implement,
they have been used since long time ago in the area, however they are not so frequently
used in location-based social networks, where users want to check-in in points-of-interests,
or POIs.
We believe this is because the standard similarity metrics like cosine or jaccard do not capture
the inherent characteristics of this domain.
Because of this, in this work we propose to adapt user similarity metrics for this domain,
and in particular, we study how to integrate sequentiality and geographical information
into nearest-neighbour recommender systems.
Nearest neighbour recommendation, as most
of you may already know, is one type of recommender systems.
Recommender systems want to present interesting recommendations to the users, in this figure,
we represent this target user in red.
In order to predict the preferences of our
target user, it is important to consider the preferences of the rest of the users in the
system
Of all the users
The final goal of the system is to detect
new items the user may like
When we consider all the information available
in the system, we can compute which users are more similar, and use those to infer the
new preferences of our target user
In this example, the selected users would
be the purple ones.
They are called neighbours, or similar users.
As you can imagine, depending on how we define
when two users are similar, we could obtain different neighbourhoods.
which would offer us different recommendations.
This is a direct consequence of the formulation
used by these recommenders: it is a weighted mean that considers how close my neighbours
are to me and how much they liked the item
However, when we want to apply this in location-based
social networks we realise the interactions are not the same: we have no ratings (so we
don’t know if something is enjoyed in a positive or negative way by a user), and we
ignore other signals that are very meaningful in this context: the location of the point
of interest and the moment of the day at which I visited such point of interest.
Because of this, in this paper we aim to integrate
these two signals into novel similarity metrics.
Let us consider this example, where our target user visited a museum on Sunday morning, and
then went to a bar and a park.
Then we know that on Monday she went to a bar and park in the morning, and to a restaurant
in the afternoon.
If we compare this behaviour against the green user, we would notice that both users share
most of the items in common, however the temporal behaviour is not so similar.
On the other hand, if we check the behaviour of the blue user, we would observe that they
both tend to go to similar places around the same time (like park D, or bars A and C) or
move around the same area at a given moment (like J and I which are close to E and G).
Based on this observation, we hypothesise
that classical user similarities might be useful for the cases when we want to capture
global preferences.
However, for location-based social networks, where contextual suggestions based on the
current time or location are much more important, other similarities that take these aspects
into account are needed, and this is exactly what we propose in this paper.
In particular, we present two similarity metrics.
One based on exploiting the common check-ins but only considering those that had happened
around the same time.
We observe in the figure how the matching for item J would not count since they occur
too far apart, whereas the one for item D would count.
In this way, we exploit the temporal information.
Our second similarity metric is based on exploiting how similar the trajectories followed by the
users are.
For this, we use well-known trajectory similarity metrics like Dynamic Time Warping and Hausdorff
distance that are more sensitive to the temporal and geographical dimension than other metrics
like the Euclidean distance.
To validate this, we used data from one of
the most famous location-based social network: Foursquare.
We filtered the data from a dataset with 33 million check-ins and considered only those
included in the city of Tokyo, resulting in around 300 thousand check-ins.
We then splitted this data into a temporal split: 6 months for training and 1 for test.
And used the 4 baselines you can see here: 2 methods based on neighbours (one based on
user similarities and another based on item similarities), and 2 based on matrix factorisation
(one that is optimised according to BPR and another that exploits the geographical influence).
We used 4 metrics to analyse the performance: NDCG for accuracy, feature agreement to capture
the precision in terms of how well we predict the categories (instead of the items), since
it is well-known that this is a very hard problem due to the data being very very sparse;
and one novelty and diversity metric, based on the inverse of popularity and the number
of different items recommended, respectively.
Well, so these are the first results based
on accuracy.
We grouped our 3 proposed approaches and UB, user based, together because they are based
on the same algorithm: a nearest neighbour recommender based on user similarities.
As we can see from the table, neither user based nor item based recommenders are competitive
against the two variations of matrix factorisation tested, the one using geographical information
getting better results
But, in terms of beyond accuracy metrics,
like diversity and novelty, the opposite results are found: item based is the best method,
and some of our proposed metrics help to improve the results of the user based baseline.
This result is particularly positive for the feature agreement metric, where the trajectory
similarity using Hausdorff stands out.
When we analyse these results in more detail,
we observe that there are different types of users in location-based social networks:
those who know the city and, hence, explore it in a more casual way (named local users),
and those that want to know the more touristic places and probably move around the same areas
(which could be labeled as tourists).
If we measure the performance on these two groups separately, the results change dramatically.
While IRenMF is still the best recommender in terms of accuracy, the performance of neighbour
based recommenders improve a lot for tourists, in particular, our approach based on temporal
windows outperforms any other method in terms of category accuracy.
We believe this is a direct consequence of tourists being a more cohesive group than
the general user in a location-based social network, hence, user similarities are more
useful for these cases.
As an additional experiment, we wanted to
check the overlap between the obtained neighbourhoods by the different methods and the explicit
social connections informed by the users in the system.
We found that, although some of the proposed metrics obtain more explicit connections than
classical metrics, this is not always translated into better accuracy; however, it might be
a good indicator to improve the feature agreement, since it is always better than the baseline.
To conclude, we have proposed two novel similarity
metrics that exploit two important dimensions in location-based social networks: one based
on temporal overlap and another based on geographical trajectories.
Although the results were not positive in terms of accuracy metrics, they were competitive
for beyond-accuracy metrics such as novelty and diversity.
In particular, they were especially positive for the subset of users identified as tourists.
In the future, we aim to continue working on this, considering this promising results,
and to integrate other methods from trajectory mining research, such as those methods used
to process GPS trajectories, and study how to apply these techniques with check-ins coming
from location-based social networks
Thank you for listening, if you want to know
more, or have access to the slides, code or related research, please, check our website.
Thanks.