Introduction: The present paper is the outcome of the research “Locus Recommendation using Probabilistic Matrix Factorization Techniques” carried out in Manav Rachna International Institute of Research and Studies, India in the year 2019-20.

Problem: Location Based recommendation systems (LSBNs) are mainstream these days due to the increasing pervasiveness of mobile devices. They provide recommendations to users based on the places which are frequently visited by them or by the people who are socially connected to them. These recommendation services use check-in information to mine users’ patterns and provide interesting and attractive locations to different users. POI recommendation applications aim to provide personalized recommendations of places of interest to users to enrich their experiences.

Objective: The objective of the research is to recommend top- n locations by applying various probabilistic matrix factorization techniques.

Methodology: Matrix factorization is a model based collaborative technique for recommending new items to the users. These techniques are found to be effective and more accurate as they are based on discovering the latent features underlying the user-item rating matrix. In LBSN the rating matrix is generally sparse, thus the concept of matrix factorization is used to generate recommendations.

Results: Experimental results on two real-world LBSNs showed that PFM consistently outperforms PMF. This is because the technique is based on gamma distribution to model user and item matrix. Using gamma distribution is reasonable for check-in frequencies which are all positive in real datasets. However, PMF is based on Gaussian distribution that can allow negative frequency values as well.

Conclusion: The motive of the work is to identify the best technique for recommending locations with the highest accuracy and allow users to choose from a plethora of available locations; the best and interesting location based on the individual’s profile.

Originality: A rigorous analysis of Probabilistic Matrix Factorization techniques has been performed on popular LBSNs and the best technique for location recommendation has been identified by comparing the accuracy viz RMSE, Precision@N, Recall@N, F1@N of different models.

Limitations:User’s contextual information like demographics, social and geographical preferences have not beenconsidered while evaluating the efficiency of probabilistic matrixfactorization techniques for POI Recommendations.

With an increased development/advent in technology, location based social networks (LBSN), in particular Foursquare, Gowalla, Yelp, and Facebook Places are in much use these days. Through LBSN, users can publicize their geographical information and sentiments about various locations they have visited or in which they have an interest. The shared check-in information will help other users to identify popular locations and services such as restaurants and malls through POI recommendation; an important service of LBSN benefitting both LBSN users and POI owners. With mobile technology, users can identify their favorite POIs and can have an essence of improved user experience through accurate POI recommendations. POI owners can also be leveraged with POI recommendations to approach targeted customers.

An LBSN includes a geo-localized dimension to online social networks. The location dimension is now important and is the link between the real and the electronic world. Social and locative technology helps people to explore interesting activities around their arena by information drawn from their location and geocoded data [1]. The addition of location dimension generates a wide variety of relations between different users and venues: User-User connection, showing that two users are related to each other either because they are friends or the venues they have visited are similar; the connection between User-Place mentioning the spot that a particular user has visited; the Place-Place connection, which shows the relation between two places either due to their closeness or due to the same category they belong to. This is illustrated in Figure 1.

Traditional Recommender techniques have been endorsed by e-commerce markets, such as Amazon, Netflix, Flipkart, etc., however, the new user locale aspect in online social networks created tremendous gateways and challenges for existing recommendation systems. Due to this additional dimension, new approaches in recommender systems need to be developed to handle large heterogeneous data being continuously generated. The approaches may be based on different data sources and methodologies for enhancing recommendations. The following unique characteristics have to be considered when developing POI Recommender systems:

Geographical Influence: As mentioned by Tobler, the First Law of Geography defines that “Everything is related to everything else, but near things are more related than distant things” [2]. This law applies to LBSNs also as users tend to go to nearby locations more than distant ones. Moreover, geographically closer POIs might have similar features. Geographical Influence thus plays a crucial role in POI recommender systems.

Social Influence: Standard recommendation methods like collaborative filtering (CF), content-based recommendation (CB), and hybrid methods process information acquired from users’ ratings and item characteristics and generate a list of recommendations based on these. However, in social networks, a users’ behavior and their friends’ check-ins might together decide the recommended list for a user.

Frequency Data and Sparsity: In traditional recommender systems, users provide explicit ratings to products (e.g., mobile phones, sports items, music, and so on), in the range [1-5]. Higher rating values for an item imply users liked the product more and also indicate user preferences. Unlike traditional recommender systems, in LBSN, a user’s choices are measured by the check-in frequency for locations. A user-location rating matrix is then created (rating values here represent how many times a user has been to a particular location). The available frequency data is so rich and voluminous that choosing suitable ones can be overwhelming. Also, the check-in matrix is generally sparser than the user-item rating matrix and is a great barrier for POI recommendation. For example, the Netflix data set is around 99% sparse, whereas Gowalla is about 2.08*10-4.

In a recommender system, one of the significant elements that affect the quality of the recommendation is the algorithm applied for making recommendations. Popular recommendation algorithms are content-based (CB) methods [3], collaborative filtering [4,5,6,7] (CF) methods and Hybrid methods.

Content Based Recommendation: CB filtering recommends and suggests items using the items liked by users in past. Prediction is done by building users’ and items’ profile and finding items with similar content. [8] examined the combined impact of POI-related contents (e.g., category) and user opinions about a location (e.g., user comments) for POI recommendation. Their results demonstrated that content information significantly contributed to user behavior estimation. The SEAL (Sentiment-Enhanced Location search) system proposed by [9] is a fine-grained location search framework that is based on fine-grained user preferences. Their work emphasized collecting user feedback on venues and modeling user preferences by these fine-grained feedbacks. They used tensor factorization to study the positive and negative preferences of a user for personalized location ranking. Content- based recommendation systems, such as the one proposed by [10], match user preferences, discovered from users’ profiles, with various location features, such as tags and categories to generate personalized recommendations displayed on a mini-map. Recent research explored the use of POI content information to reduce data sparsity. The Spatial topic model for POI recommendation, as suggested by [11], considered the spatial and textual features of user posts collected from Twitter. [12] focused on personal interests and local preferences associated with a POI’s content. [13] combined LDA and matrix factorization to study how POI associated tags affect venue recommendation. [14] proposed POI recommendation by using sentiment information and their technique demonstrated improved performance over the state-of-the-art approaches. [15] argued that content information, when combined with social correlations can generate effective recommendations and suggested a topic model based on this for offering better recommendations. A study by [16] considers location content information with its spatio-temporal patterns for recommending interesting locations. Content based technique is robust against the cold start issue for both new users and locations. These techniques work effectively so long as the newly added user or location has a description of the content. Most of the time the data utilized to generate recommendations is hard to capture and phony; thus, content-based systems have many limitations, such as the user might not be provided with novel recommendations as items are suggested based on the user profile. Moreover, due to limited user content, recommendations are not appropriate.

Collaborative Filtering Techniques: CF algorithms are the most accepted algorithms and are one of the influential algorithms in recommendation systems. Unlike CB methods, CF techniques do not need a description of items or users. Recommendations are generated by the opinions of a user’s comparative taste and preferences to the active user. This section provides a literature review about significant POI recommender systems, mainly for collaborative filtering. Existing literature mentioned two classes of collaborative filtering strategies, memory-based and model-based [17].

Memory Based Collaborative Filtering: The memory-based CF computes similarities between the active user and other users (User-User Collaborative Filtering), or between items (item-item approach) to make recommendations. [18] studied the combined effect of social and geographical influences and incorporated both the features into the user-based CF framework for POI recommendation. Their experiment proved that user-oriented CF surpasses item-oriented CF for POI recommendation if geographical information is associated with a user-based CF model. However, adding social information brought little improvement in the model’s performance. [19] extended upon the item-based CF method. However, calculating similarity is rather more difficult in memory-based techniques and the model’s performance is confined by data sparsity. To deal with the aforementioned issues, model-based recommendation algorithms such as “latent semantic models” [20], “Bayesian models” [21], “clustering models” [22,23], and “matrix factorization models” [24,25,26] have been suggested and worked upon.

Model Based Techniques: Among the several CF technologies, matrix factorization is well known and great at managing high dimensional data and mitigating sparsity. According to [24], in this method, item and user vectors are defined in terms of vectors of factors inferred from item rating patterns. To reduce the data sparsity issue, auxiliary information such as time or social trust can be used with existing techniques. [27] proposed to combine the Matrix Factorization technique with the geographical and social influence for POI recommendation. Authors have modeled the geographical influence via the multicenter Gaussian model. The assumption is that a user’s check-ins are generally located around multi centers. To find these multi centers, the authors have proposed a greedy clustering algorithm. Their model does not consider the extremely sparse frequency data. Further, there were problems in finding centers accurately and the outliers’ effect was not dealt with. To overcome this problem, [28] presented a genetic algorithm-based Gaussian mixture model. Their model employed a genetic-based EM algorithm [29] to dissolve the effect of outliers in the mixture model. [30] utilized the mobility records of a user as implicit feedback and proposed a weighted matrix factorization for recommendation.They also added a spatial clustering phenomenon with matrix factorization. [31] analyzed the integrated effect of user preferences, geographical influences, and user mobility behavior. They predicted user preferences by combining probabilistic matrix factorization with a Poisson factor model. The STPMF (Spatial- Temporal Probabilistic Matrix Factorization) model developed by [43] captured users general preferences and multiple geographical features into PMF. [41] were the first ones to develop a model that learns the distribution of user preferences in a generative way. Their model considers two neural network components; one that recommends POI and another component judges if it is a true recommendation or not and helps in optimizing the proposed recommendation. The STACP (Spatio- Temporal Activity Center POI) novel recommendation model proposed by [42] considers the effect of spatial and temporal characteristics of a user jointly. This model trains the matrix factorization model in a static and temporal manner and forms spatio-temporal activity centers for users. [44] suggested a generic bayesian model that integrates the item content and social information using poisson matrix factorization to produce highly accurate recommendations.

Collaborative Filtering experiences data sparsity and scalability issues as the number of users anditems grow. Matrix factorization is a powerful solution to tackle and mitigate data sparsity and also reduce data dimensions, extract hidden features from data. Thus, matrix factorization is widely used in recommender systems owing to their characteristics. As a case study, two probabilistic matrix factorization techniques are trained on theGowalla and Foursquare check-in data set with the aim of studying user mobility behaviour. User mobility patterns indicate the places a user is interested in visiting. This helps in identifying and recommending new locations to the user. The methodology to compute recommendations consisted of the following steps:

Matrix factorization (MF) is a systematic Collaborative Filtering method. Given an m × n user-location rating matrix r to describe m users’ frequency count on n POIs, the MF model learns an m × d user-latent feature matrix and a d × n item-latent feature matrix. Mathematically, it is represented as:

where,

Factorization is performed in a manner that retains theproperties and dependencies of therating matrix. Matrix factorization is an optimization problem in which latent vectors are learned using the function mentioned in equation 2 on the set of available ratings:

where,

Some of the Matrix Factorization models as depicted in literature are Singular Value Decomposition [32, 33], Probabilistic Matrix Factorization (PMF) [25, 34], and Non- Negative Matrix Factorization [35].

In this section we will discuss two latent factor models:

PMF is a robust statistical framework with a Bayesian perspective on the model matrix R. In this model, entries of R are assumed to be normally distributed around the inner product ⟨uᵢ, lⱼ⟩, lthrough a common variance. Letting Iᵢⱼ be 1 if the entry was observed and 0 if the data value was not present, we can write the likelihood of the entries of R as follows.

where,

In these priors, the following are the assumptions:

With additional prior information, more informative prior distributions can be constructed to have an in-depth correlation between observations or features in the design matrix R.

Poisson factorization isone of the probabilistic models of users and items. Each observation of the user-POI rating matrix is assumed to be takenfrom a Poisson distribution; “an exponential family of distribution over positive integers whose parameter is a linearcombination of the corresponding user preferences and item attributes”. In [36, 37, 38], in contrast to classical matrix factorization in which Gaussian Distribution is used to generateboth positive and negative examples, the userand item matrices in PFM are generated from the gamma distribution as it is not feasible to have negative frequencyvisit counts to a place in the real world. The Poisson factor model segments the user-POI check-in count matrix Y as Y~Poisson (U.L). That is, for each user-POI response yij, Poisson distribution is assumed over the mean fij: yij~Poisson(fij). The mean matrix F is divided into two matrices U of M x K and L of N x K. Each element uik of Umxk indicates the preference of user i for “feature” k, and each element lik of L reflects the affinity of item j to feature k. In addition, empirical Gamma Distribution priors are placed with uik and ljk priors. The steps are defined as:

The performance of the two approaches has been experimentally verified. All the approaches have been implemented in Python. The techniques have been applied to the real world Gowalla Dataset and Foursquare Dataset [39]. The Gowalla check-ins were captured for a period from February 2009 to October 2010. The records of users with less than 15 check-ins and POIs with less than 10 visitors are filtered. The new processed data has 18,737 users, 32,510 POIs and 1,278,274 check-ins, resulting in a matrix that is 99.86% sparse.

The Foursquare data contains user check-ins for a period of 17 months from April 2012 to September 2013. These check-ins are generated from within the United States (except Alaska and Hawaii). For this dataset also, records of users with less than 10 check-in POIs, as well as those POIs with less than 10 visitors are eliminated. The processed and cleaned dataset has 24,941 users, 28,593 POIs and 1,196,248 check-ins. The sparsity of user-POI check-in matrix is 99.900%.

A snippet of Gowalla and Foursquare datasets is displayed in Figure 3.

Each Dataset has three columns showing user-id, POI-id, timestamp of check-in made. For this study, we used 70% data as training set and 30% as test set.

The comparison of two techniques: PMF and PFM in terms of evaluation metrics is performed in this section. It compares two traditional approaches on two real LBSNs Gowalla and Foursquare. A statistical analysis of the performance evaluation metrics such as Precision@N, Recall@N, and RMSE and F1@N is performed.

“Root mean square error computes the mean value of all the differences squared between the true and the predicted ratings and then proceeds to calculate the square root out of the result” [40]. It is calculated as:

where, r is observed rating, and r′ is the actual rating.

Figure 6 and Figure 7 display the behaviour of RMSE for Gowalla and Foursquare using PMF.

Values of RMSE for PMF over Gowalla Dataset shows a declining trend with values ranging from 3.38 to 3.29 as the number of epochs increases from 0 to 7. At the 7th iteration, RMSE increases from 3.29 to around 3.34. Similar trends are exhibited in Foursqaure Dataset with values decreasing from 3.38 to 3.32 and increasing at 8th epoch from 3.27 to 3.32. However, for PFM RMSE is always decreasing with the number of epochs and RMSE value is in the range from 3.72-3.60 for Gowalla and between 4.13-4.01 for Foursquare dataset.

Precision and recall are traditional evaluation metrics in machine learning algorithms and for document retrieval tasks. In the recommender system’s context, we most likely wanted to recommend top-N POIs to the user. It makes more sense to compute precision and recall metrics in the first N POIs instead of all the POIs. Thus, the concept of Precision@N and Recall@N is used where N is a user-defined integer, set by the user to satisfy the top-N recommendations objective. It is calculated as:

Precision@N = (# of recommended POIs @N that are relevant) / (# of recommended POIs @N)

Table 1 and Table 2 shows the results obtained for Precision@N for the two techniques when N is varied between 5, 10, 15 and 20, and their comparison is made using graphs shown in Figure 8 and Figure 9 respectively.

Precision@N drops gently with increasing N in both the datasets. PMF is reported to have lower Precision@N values. We have taken N values as 5, 10, 15 and 20 and Precision@N for Gowalla data set for different values of N is reported as 9.60e-4, 1.45e-3, 1.47e-3, 1.65e-3 respectively. Whereas, for Foursquare data set these values are 9.70e-4, 1.33e-3, 1.35e-3, 1.62e-3. However, for PFM Precision@N is reported as 2.20e-2, 2.31e-2, 1.86e-2, 1.61e-2 for different N respectively for Gowalla and a similar trend in values is observed for Foursquare dataset also.

Recall measure relevancy of POIs retrieved from all the predictions.

Recall@N increases gradually as N increases from 5 to 20, on the other hand, values for PMF are small when compared with PFM for two datasets. Recall values for two techniques for different N values show an increasing trend. Compared to PFM, the PMF technique has lower Recall@N. As N varies Recall@N for PMF is 2.93e-4, 9.91e-4, 1.51e-3, 2.43e-3 for Gowalla and 2.79e-4, 9.71e-4, 1.40e-4 and 2.31e-3 for Foursquare respectively. For Gowalla dataset Recall@N using PFM is 9.40e-3, 2.04e-2, 2.48e-2, 2.86e-2 respectively.

F1@N

It is computed as the harmonic mean of precision and recall.

Table 5, Table 6 and Table 7 show the precision, recall and F1 values of PMF and PFM for Gowalla and Foursquare Dataset.

In summary, from the experimental investigation over Gowalla and Foursquare Data set, it can be concluded that the PFM exhibits unvarying performance and is more effective over real-world datasets. Moreover, PFM is much better, more effective, and provides more accurate top-N recommendations in contrast to PMF.

As location-based social networks are gaining prevalence these days, personalized POI recommendation services are boosting up and procuring the attention of industries and scholars. In addition, to help users explore new places, these services are a boon to LBSN providers and helping them to increase their profits. In this paper, we illustrate the task of POI recommendation in LBSNs using matrix factorization. We first describe the unique characteristics of POI recommender systems that distinguish them from traditional recommender systems. We have investigated in detail two traditional probabilistic techniques for the POI recommendation problem. Accuracy comparisons are presented and experimental results on Gowalla and Foursquare datasets indicate that PFM outperforms PMF in accuracy. From the results it can be inferred that PFM is best for the check-in datasets as in real scenarios, check-in frequencies cannot be negative.

Our current and future research plans are inclined to improve the performance of the POI recommendation by exploring more influential factors, and its applicability under realistic scenarios. Specifically, in future work, we plan to extend this work by considering social factors and also by adding time factors that can reflect different contexts about user interests.