Geographical and Overlapping Community Modeling Based on Business Circles for POI Recommendation

Abstract

Point-of-interest (POI) recommendation is a challenging task since check-in data is extremely sparse and the social relationships in traditional recommendation have a limited effect. To solve this challenge, we propose a new geographical model with social influence and user preference. More specifically, we firstly propose a business circle conception which is more suitable for the modern consumption pattern in an urban city in POI recommendation. Then we decompose the user-location matrix into two geographical latent factors and integrate them into our business circle framework. Besides, we incorporate the user preference as a regularization of matrix factorization framework into our model by means of aggregating overlapping interest communities of users via their check-ins categories. Extensive experiments are conducted on two real-world datasets and the experimental results demonstrate that our model outperforms other existing algorithms.

1 Introduction

Early recommender systems have been widely used in online website to promote the sales volume of the online consumption [1, 2], while the recent recommender systems began to focus on recommending the offline consumption by using the information provided through integrated devices. Using the information of Internet of things is a growing trend [3] and online location-based social networks (LBSNs) is one of the typical representatives [4]. Because the information of real-time locations becomes easier to be acquired by GPS, LBSNs have undergone a rapid development, such as Foursquare, Gowalla and Facebook Places, in which users can share the experience in the physical world by checking in a POI. LBSNs can help people discovering the interesting places, especially in an urban city, where the POIs are in enormous quantity and hard to choose for users.

LBSNs can benefit users outdoor activities and bridge the gap between the physical world and online social network, but POI recommendation in LBSNs encounters more challenging issues than recommendation in traditional online websites for the following reasons. (a) Extremely sparse check-in data. POI recommendation is facing a huge challenge caused by extremely sparse check-in data. An individual user usually checks in a limited number of locations for two factors. On one hand, though there are numerous locations in a city, users only check in a small section for the restriction of distance. On the other hand, users prefer to check in their favorite locations repetitively, leading to the number of check-ins in different locations is limited. (b) The limited effect of social influence. The traditional social relationship has limited effect in LBSNs for the reason that there is only a very small portion of overlapping check-ins among social friends [5]. In other words, we should explore more appropriate implicit social relationships in LBSNs to improve the accuracy of recommendation. (c) Complex and diverse factors. In POI recommender systems, relatively speaking, there are more factors to be considered, such as geographical factor, temporary factor, category attributes and so on. Among these factors, geographical and temporary factors are intrinsic properties in POI recommendation for the check-ins in specific time and location. In other words, POI recommendation is an online-to-offline recommendation.

In this paper, we explore the geographical limits and overlapping interest community information to improve the recommendation accuracy. Firstly, we propose a business circle conception which is more suitable for the real modern consumption pattern in an urban city in POI recommendation. Besides, we propose two geographical latent factors inspired by these previous work [6,7,8] and integrate them into our business circle framework. Moreover, we incorporate the user preference into our model by means of aggregating overlapping interest communities of users via their check-ins categories. In experiments, we analyze the effect of parameters in our algorithm and then compare our CBGeoMFC model with three baseline algorithms to evaluate the performance our method.

2 The Proposed Model

2.1 Business Circle Conception

In urban cities, instead of a specific shop, people would often choose an area (such as a business circle) when they go outside. For example, when you have a date with your friends, you may expect a series of dating activities and all that dating locations are geographically close. So you will consider a prosperous region containing all that required venues, and we call that region as a business circle. In addition, in order to integrate the situation that people check in near the home or working place, we can also regard the surrounding area of the home and working place as a business circle.

Business circle is highly correlated to the geographical features, and we use the Haversine Formula [9] to get the great circle distance between two locations using their geo-co-ordinates as

$$\begin{aligned} \begin{aligned} d&= 2{\mathbf {R}}\arcsin \bigg (\big (\sin ^2(\frac{\varphi _2-\varphi _1}{2})+\cos (\varphi _1)\cos (\varphi _2)\sin ^2(\frac{\lambda _2-\lambda _1}{2})\big )^\frac{1}{2}\bigg )\\ \end{aligned} \end{aligned}$$

(1)

where $\varphi$ is latitude, $\lambda$ is longitude, and ${\mathbf {R}}$ is the earth’s radius.

And we define the negative of great-circle distance is the geographical similarity between two locations $geoSim(l_j,l_{j'}) = - d(l_j,l_{j'})$, where $l_j$ ad $l_{j'}$ are two locations in the location set $L = \{l_1,...l_n\}$. By applying $f(x)=\frac{x-\min (x)}{\max (x)-\min (x)}$ to map the similarity to the range of [0, 1], which is taken as the input of the Affinity Propagation (AP) clustering algorithm [10] to cluster all the check-in locations into groups, the business circles can be obtained with each group representing one business circle and the representative location being the centroid of the business circle.

2.2 Geographical Modeling

Matrix Factorization. Low rank matrix factorization is widely used in POI recommendation, which approximates a user-location frequency matrix R by the multiplication of two k-dimensional latent matrices, namely user check-in preference latent matrix $U \in \mathbb {R}^{m\times k}$ and location characteristic latent matrix $L \in \mathbb {R}^{n\times k}$, where m and n are the numbers of users and locations respectively.

$$\begin{aligned} \min \limits _{U,L}||I\odot (R-UL^T)||^2_F + \lambda _u ||U||^2_F + \lambda _l ||L||^2_F \end{aligned}$$

(2)

where $I \in \mathbb {R}^{m\times n}$ is a [0, 1] matrix with $I_{i,j}=1$ indicating that user i has visited location j and $I_{i,j}=0$ otherwise. The tuning parameters $\lambda _u$, $\lambda _l$ is non-negative to avoid overfitting and $||\cdot ||^2_F$ is the Frobenius norm.

CBGeoMF. In this section, we redefine the users’ activity and POI influence and incorporate them into our business circle conception, and hence propose a new geographical matrix factorization model based on business circles (CBGeoMF).

The business circle is a geographical priority concept. In other words, users always concern more about which consumption centers they want to go to instead of a specific POI. To abstract this conception, first of all, we give the definition of user’s activity on business circles and attraction of POI in the business circle.

User’s Activity on Business Circles

• 1. User is more active on the business circles where he/she has checked in more times.

• 2. The business circles which are geographically near the activity business circles have more potential to be active.

For the foregoing considerations, the problem is to evaluate the density distribution on each business circle, which can be modeled by using the two-dimensional kernel density estimation approach. Assume that we have obtained a business circle set $C=\{c_1,...c_w\}$, the estimated density of user $u_i$ in a business circle $c_q$ can be defined as

$$\begin{aligned} x_{i,c_{q}} = \frac{1}{P_{i}}\sum _{c_{q'}\in P_{i}}\frac{n^{c_{q'}}_i}{\delta }K(\frac{d(c_q,c_{q'})}{\delta }) \end{aligned}$$

(3)

where $K(\cdot )$ is standard normal distribution with $\delta$ being the standard deviation, $P_i$ is the set of business circles that user $u_i$ has visited and $n^{c_{q'}}_i$ is the check-in number of $u_i$ on business circle $c_q'$. And $d(c_q,c_{q'})$ denotes the distance of business circles $c_{q}$ and $c_{q'}$, i.e. the distance between the corresponding centroids returned by AP.

In this way, the activity of user on circle is represented by a non-negative matrix X, which is estimated by both the check-in frequency counts and geographical information.

Attraction of POI in the Business Circle. Considering that users are more likely attracted by the popular locations, the locations in a dense region are more attractive. Similar to user’s activity, the attraction of location $l_{j}$ in a business circle $c_{q}$, denoted as $y_{l_j\in c_{q}}$, can be computed in the same way using kernel density estimation approach, $y_{l_j\in c_{q}} = \frac{1}{\delta n_{c_q}} \sum _{l_{j'}\in c_q} K(\frac{d(l_j,l_{j'})}{\delta })$, where $n_{c_q}$ is the number of locations in $c_q$, and $l_{j'}$ is the other locations in the same business circle $c_q$ as $l_j$. In this way, the attraction of POIs in their corresponding circles can be represented by the non-negative matrix Y.

The preference of users on locations can be decomposed into two low rank w-dimensional latent factors, where w is the number of business circles. One is user’s activity on business circles $X \in \mathbb {R}^{m\times w}$, and the other is the attraction of POI in the corresponding circle $Y \in \mathbb {R}^{n\times w}$. By augmenting the matrix of the two latent geographical matrices X and Y with the original latent matrices U and L, the objective function can be defined as follows

$$\begin{aligned} \min \limits _{U,L}||I^R\odot (R-UL^T-XY^T)||^2_F + \lambda _u ||U||^2_F + \lambda _l ||L||^2_F + \lambda _x ||X||^2_F \end{aligned}$$

(4)

In the above objective function, the user’s activities on circles X are initially initialized by using Eq. (3), and then they are iteratively updated to meet the fact that users activity behavior would change to reflect their real check-in behavior.

2.3 Overlapping Community Modeling

Social network is often taken as a good side information in recommender systems to improve accuracy. However, it works relatively less effective in a location-based recommendation for two reasons: (a) Geographical Limitation. Unlike the traditional recommendation, LBSN has an intimate relations with both online and offline, that is to say, we have to consider the geographical limitation in real life. For example, though two users have similar following relationship or preference, it is still not suitable to recommend one’s check-in locations to another if their frequently visited places are far away. (b) Sparse Social Relationship. Another reason is that compared to a traditional online social relationship, users in LBSN have fewer direct social connections and 90% user’s overlap check-ins to his/her friends’ check-ins is less than $20\%$, which is mentioned in the previous studies [5, 11]. We incorporate the category influence and geographical social network information as a regularization term of matrix factorization based model to consider both the user’s preference and geographical limitation, which is inspired from the relevant studies [12,13,14].

As aforementioned, the AP algorithm is used to cluster all the check-ins into a set of clusters, and each cluster represents a business circle. Considering the geographical limitation, the users who have similar frequently visited business circles are defined to be geographical social friends. We can effectively settle the defects that there are few overlap check-ins of a user to his/her friends’ check-ins by aggregating the check-ins on locations into the check-ins on business circles. The common check-ins on locations are infrequent, even though the users have the similarity routines, however, their frequently visited business circles can be the same. In this way, the geographical feature can be enhanced. Furthermore, compared with [11, 15, 16] which believed users are more geographical similar when their ‘homes’ are near, our approach don’t need to build a multi-center gaussian model for each user to estimate the rough home location.

In the first place, the Pearson Correlation Coefficient (PCC) is used to calculate the similarity matrix $S_{if}$ of users. Considering the number of check-ins of each user differs greatly, we first normalize the visit frequency of each user from 0 to 1 by $r^c_{i,{c_q}} = \frac{fre_{i,{c_q}}}{\max \{fre_i\}}$. Then the similarity $S_{if}$ is defined as $S_{if} = \frac{\sum _{c\in C_{if}} (r^c_{i,{c_q}}-\bar{r^c_i})(r^c_{f,{c_q}}-\bar{r^c_f})}{\sqrt{\sum _{c\in C_{if}}(r^c_{i,{c_q}}-\bar{r^c_i})^{2}}\sqrt{\sum _{c\in C}(r^c_{f,{c_q}}-\bar{r^c_f})^{2}}}$, where $fre_{i,{c_q}}$ is the check-in frequency of user i on business circle $c_q$, $r^c_{i,{c_q}}$ is the rating (normalized visited frequency) of user i on business circle $c_q$, $\bar{r^c_i}$ is the average rating of user i on all the circles, and $C_{if}$ is the business circles set that both user $u_i$ and user $u_f$ have visited.

Table 1. The statistics of data sets.

Then we cluster the users into overlapping communities $M=\{m_1,...m_h\}$ according to corresponding category information. And the regularization term is $\frac{\lambda _h}{2} \sum ^m_{i=1} \sum ^h_{p=1} I^M_{ip} Z_{ip} \sum _{u_f \in m_{ip}} S_{if} ||U_i - U_f||^2_F$, where $m_{ip}$ denotes the community $m_p$ containing the users in the same community as $u_i$, $I^M_{ip}$ equals 1 if $u_i$ belongs to $m_p$ or equals 0 otherwise, $Z_{ip}$ is the preference of $u_i$ on community $m_p$, which is defined as $Z_{ip} = \frac{fre_{i,{m_p}}}{\max _{\forall m}\{fre^m_i\}}$, where $fre_{i,{m_p}}$ is the check-in frequency of user i on community $m_p$.

In this way, we solve the problem that common check-ins of users on locations are insufficient by incorporating both the user preference (category information) and geographical social network information.

2.4 The Overall Model and Optimization

Accordingly, the objective function of the overall model is as follows

$$\begin{aligned} E =&\frac{1}{2}\sum ^m_{i=1}\sum ^n_{j=1}I^R_{ij}(R_{ij}-U_iL^T_j-X_iY^T_j)^2 + \frac{\lambda _u}{2} ||U||^2_F + \frac{\lambda _l}{2} ||L||^2_F + \frac{\lambda _x}{2} ||X||^2_F \nonumber \\&+ \frac{\lambda _h}{2} \sum ^m_{i=1} \sum ^h_{p=1} I^M_{ip} Z_{ip} \sum _{u_f \in m_{ip}} S_{if} ||U_i - U_f||^2_F \end{aligned}$$

(5)

Stochastic Gradient Descent (SGD) is used to find a local minimum of our objective function Eq. (5), and the gradient descent w.r.t. $U_i$, $L_j$ and $X_i$ are

$$\begin{aligned} \frac{\partial E}{\partial U_i}=&-\sum ^n_{j=1}I^R_{ij}(R_{ij}-U_iL^T_j-X_iY^T_j)L_j + \lambda _uU_i + \lambda _h\sum ^h_{p=1} I^M_{ip} Z_{ip} \sum _{u_f \in m_{ip}} S_{if} (U_i - U_f) \nonumber \\ \frac{\partial E}{\partial L_j}=&-\sum ^m_{i=1}I^R_{ij}(R_{ij}-U_iL^T_j-X_iY^T_j)U_i + \lambda _lL_j\\ \frac{\partial E}{\partial X_i}=&-\sum ^n_{j=1}I^R_{ij}(R_{ij}-U_iL^T_j-X_iY^T_j)Y_j + \lambda _xX_i \nonumber \end{aligned}$$

(6)

3 Experiments

3.1 Dataset Description

We use the Foursquare and Jiepang datasets to evaluate the performance of our model which are widely used in previous studies in the location-based recommender system [6, 17]. The Foursquare dataset contains a long-term (about 10 months) check-in data in New York City (NYC) collected from Foursquare, ranging from April 2012 to February 2013, and Jiepang dataset contains check-ins in HongKong from December 2011 to September 2012. Each check-in contains a user ID, a location ID, a category ID and a category name, latitude and longitude coordinates. Table 1 lists the general statistics of our two datasets. To split the dataset into training set and testing set, we firstly aggregate the check-ins for each location of each user. After that, we select 80% data randomly as the training set to train the model and the remaining 20% are held out for testing.

3.2 Evaluation Metrics

Considering only limited locations will be recommended to users in location-based recommendation, we use the Top-N recommendation approach to evaluate our model, including Precision@N, Recall@N, and F1@N metrics. F1@N is the harmonic mean of precision and recall.

3.3 Parameters Analysis

There are six parameters in our algorithm, namely $\lambda _h$, $\lambda _x$, $\lambda _u$, $\lambda _l$, N, and k. We set the dimension of latent matrices k as 2 and the regularization coefficients $\lambda _u, \lambda _l$ equal to 0.01 in all experiments. Then we analyze the effect of social regularization coefficient $\lambda _h$, user activity regularization coefficient $\lambda _x$, and the length of recommend list N respectively by fixing other parameters in this section.

Parameter Analysis on ${\varvec{\lambda }}_{\varvec{h}}.$ Parameter $\lambda _h$ represents the impact on community social relationship. On the Foursquare dataset, we fix the parameters $N=5, \lambda _x=0.01$ and increase the $\lambda _h$ from 0 to 0.07 unevenly. It’s obvious that the accuracy is sensitive to the community social regularization. Compared with the situation that we don’t consider the impact of community influence (i.e. $\lambda _h=0$), the accuracy can be promoted $44.8\%$ when $\lambda _h = 0.005$ on Foursquare. Besides, on the Jiepang dataset, we fix the parameters $N=5, \lambda _x=40$, and the accuracy can be promoted by $6.3\%$ at the best performance when setting $\lambda _h = 0.07$ as shown in Table 2.

Table 2. Parameter analysis: the influence of $\lambda _h$ on the proposed CBGeoMFC model.

Parameter Analysis on ${\varvec{\lambda }}_{\varvec{x}}.$ Parameter $\lambda _x$ is the Frobenius norm coefficient of user activity. On Foursquare, we fix the parameters $N=5, \lambda _h=0.005$ and then test $\lambda _x$ from 0.0001 to 150 as shown in Table 3. The accuracy has almost no improvement when $\lambda _x < 1$ while it increases rapidly when $\lambda _x > 1$ and achieves the best performance as $\lambda _x = 100$. As for the Jiepang dataset, the best result is achieved as $\lambda _x = 40$. The experiment result shows that user activity on most circles is unimportant, for the large value of $\lambda _x$ generates a rather strong constraints. When the parameter $\lambda _x$ continues to increase, the constraints become stronger so that it removes some obvious features and the value begins to decrease. This is consistent with the real world situation that users always check-in in a limited number of circles. The accuracy is promoted $9.9\%$ and $19.2\%$ at the best performance on the Foursquare and Jiepang datasets respectively.

Table 3. Parameter analysis: the influence of $\lambda _x$ on the proposed CBGeoMFC model.

Parameter Analysis on ${\varvec{N}.}$ Parameter N is the length of recommend list in the top-N recommendation. Setting $\lambda _x=0.01, \lambda _h=0.01$ and $\lambda _x=40, \lambda _h=0.7$ on the Foursquare and Jiepang datasets respectively, we change the parameter N from 1 to 20 and find that precision has a decline trend while recall continues growing when parameter N increases. $F_1$ measuring result considers both precision and recall and arrives the best performance as $N=20$ on Foursquare and $N=7$ on Jiepang as shown in Fig. 1.

Fig. 1.

The influence of N on the CBGeoMFC model.

3.4 Comparison Experiments

In this section, comparison results will be reported to compare the proposed CBGeoMFC method with some existing methods, namely UBCF, PMF [18] and MFC [12]. For all comparison methods, the parameters are set as suggested in the corresponding papers. In particular, for the sake of fairness, we set the same random initial value for all the methods, and set the learning rate as 0.0001 and regularization coefficients as 0.01 for every algorithms. We use parameter $\lambda _x=40, \lambda _h=0.1$ and $\lambda _x=100, \lambda _h=0.005$ on the Jiepang and Foursquare datasets in our CBGeoMFC model.

The comparison results are shown in Fig. 2. Our algorithm achieve the best performance among all the three comparison algorithms in terms of all evaluation metrics for considering both social influence and geographical limits. From the results, we can find that UBCF is not appropriate in POI recommendation for the reason that the check-in data is too sparse and users have few overlapping check-ins. Compared with PMF, our model improves the recommendation precision, recall and F1 by 93.9%, 63.7%, 80.5% and 64.1%, 24.9%, 34.8% respectively on Jiepang and Foursquare. Compared with MFC, our model improves the recommendation precision, recall and F1 by 39.1%, 46.2%, 40.5% and 34.9%, 15.2%, 20.7% respectively on Jiepang and Foursquare. Overall, our CBGeoMFC model outperforms the compared algorithms.

Fig. 2.

Performance comparison.

4 Conclusions

POI recommendation can benefit users outdoor activities in an urban city and bridge the gap between the physical world and online social network, but it encounters more challenges for the reasons that the check-in data is too sparse, various factors have to be considered and the effect of social influence is limited. To solve these challenges, we propose a business circles conception and use AP algorithm to cluster all the check-ins into business circles. By aggregating the check-ins on locations into the check-ins on business circles, we can effectively settle the defects that there are few overlap check-ins of a user to his/her friends’ check-ins. Then we compute the user’s activity and attraction of the POI on each circle to evaluate the user preference on location, which is more consistent with the modern consumption pattern in an urban city. In addition, we cluster the users into overlapping communities according to the corresponding category information and social relationships. Finally, we incorporate all above factors into a matrix factorization framework. The experimental results have confirmed that our algorithm remarkably outperforms other existing algorithms.