Integrating Spatial Relationship into a Matrix Factorization Model for POI Recommendation
-
摘要: 兴趣点(point of interest, POI)推荐是在基于位置的社交网络中流行起来的个性化服务。针对数据稀疏和隐性反馈的使用等问题，提出了一种关系型矩阵分解模型——合作竞争矩阵分解(cooperative competition matrix factorization, CC‑MF)。该模型根据用户与POI间的相互关系建模，融入空间关系，并将空间关系细分为空间距离关系和空间拓扑关系，挖掘POI之间、POI与用户之间的空间关系, 以缓解数据稀疏问题；同时使用加权最小二乘准则构建目标函数，缓解隐性反馈问题。在现实世界签到Foursquare数据集上进行实验，结果显示: (1)CC‑MF模型显著提高了推荐结果的准确性；(2)考虑空间拓扑关系的空间距离因素能够进一步提升推荐系统的性能。因此，CC‑MF模型具有良好的拓展性和解释性，且缓解了数据稀疏和隐性反馈使用问题。Abstract:Objectives Point of interest (POI) recommendation is the prevalent personal service in location‑based social network(LBSN), and aims to provide personalized recommendation services by using the information carried by LBSN. The utilization of spatial relationship information as the side information supplies a chance to product better POI recommend. However, thousands of users and POIs in the LBSN make the user‑POI check‑in matrix very large and sparse.In addition, check‑in record data is typical implicit feedback data, which cannot directly reflect the user?s preference. To tackle the aforementioned challenges, we propose a relational matrix factorization model based on cooperative competition matrix factorization (CC‑MF).Methods The CC‑MF model can simulate the relationship between users and POIs, and divides spatial relationships into spatial distance relationship and spatial topological relationship. In order to alleviate the problem of data sparsity, the model excavates the spatial relationships among POIs, POIs and users by integrating spatial relationships. Firstly, we use nonlinear function to establish the spatial distance relationship between users and POIs, which can connect the relationship between users and POIs. Then, k‑nearest neighbor (kNN) algorithm is used to calculate the geo‑neighbors of POI by considering the spatial distance factor of spatial topological relationship, which can further alleviate the sparsity of data. Finally, the spatial relationship is integrated into the matrix factorization model. Meanwhile, the weighted least square method is used as the objective function of the CC‑MF model to relieve the implicit feedback problem. Experiments are carried out on the real‑world check‑in Foursquare datasets. We test the recommendation performance of the proposed model and baseline methods, and analyze the crucial influence of different spatial relationships on POI recommendation. The precision and recall are used as evaluation metrics.Results The results show that: (1) The CC‑MF model significantly improves the precision and recall of the recommendation results. (2) Considering the spatial distance factor of the spatial topological relationship can further improve the performance of the recommendation system.Conclusions Therefore, CC‑MF model can make use of spatial relationship better and more comprehensive.The proposed CC‑MF model has better scalability and better interpretability, and can alleviate the problems of data sparsity and implicit feedback usage.
-
推荐系统是根据用户的某些行为收集用户的偏好，推荐给用户适合他们偏爱的服务或者物品[1]。推荐系统在网上购物、浏览器搜索、外卖等领域具有广泛的应用。随着社交网络、全球定位技术和移动互联服务的发展，基于位置的社交网络（location-based social network，LBSN）服务也随之流行起来，例如Foursquare、Gowalla、Yelp[2]等服务。这些LBSN服务通过用户的社交媒体将用户访问一个位置或签到的信息分享给社交网络好友，通过这种签到信息，可以发掘出用户与其签到位置的相互关系，并以此帮助人们寻找他们感兴趣的地方。兴趣点（point of interest，POI）推荐是根据用户的历史签到信息[3]学习用户的访问偏好，推荐给人们感兴趣但没有访问过的位置。POI推荐不仅能够帮助人们发现未知的感兴趣的地方，而且能够帮助营业者吸引潜在用户。
目前，POI推荐面临着数据稀疏和隐性反馈的使用这两大问题[4]。针对数据稀疏性，很多研究者尝试使用加边信息来解决数据稀疏的问题[5-10]。由于空间因素在POI推荐中能产生较大影响，文献[11]研究了空间聚类现象以及空间距离对于用户签到行为的影响；文献[12-13]首先研究空间聚类现象，通过Tobler的地理学第一定律[14]得出“一个用户倾向访问附近的POI”，然后根据用户签到数据，分析得出用户签到的概率服从幂律分布；文献[15]通过分析用户活动性提出了一种包括二维高斯核密度分析算法和一维幂律算法的推荐框架；文献[13]通过人类活动的阶段性表现研究时间对POI推荐的影响；文献[16]通过将时间的影响分为长期影响、短期影响和时变影响来分析时间对POI推荐的作用，取得了较好的结果。除了空间和时间因素外，还有学者考虑了社交关系[6, 17-20]。文献[6]提出了一种评价社交关系的一种度量，即信任度，由信任度来计算不同社交关系的影响程度；文献[17]提出了潜在的社交关系，认为用户潜在的社交关系会对用户的偏好产生影响，但是社交关系因素对于POI推荐系统性能的提升作用有限。也有研究提出使用社交评论信息来帮助推荐[17, 21-23]，如文献[22]研究了用户评论的语义信息，并给出了这些信息对于POI推荐性能的提升；文献[24]使用卷积矩阵分解（matrix factorization，MF）方式较好地融入了社交评论信息。针对隐性反馈使用问题，文献[25-27]采用加权矩阵分解（weighted matrix factorization，WMF）或负采样方法来解决该问题，分别是为每个元素增加一个权重或者概率的方式和用缺失数据建模的方式。这两种方法是目前针对隐性反馈使用问题的主要应对方法。
针对POI推荐系统中的数据稀疏性，本文采用融入空间关系的方法来缓解该问题。当前研究虽然考虑了地理因素的影响[4, 9, 12-13, 28-29]，并且分析了地理因素的影响模式，但一般都是从空间距离的角度分析该因素的作用，较少考虑空间拓扑关系的影响，而空间拓扑关系是地理空间相关关系的重要组成部分。对于空间分析，空间关系的确立非常重要，因此考虑空间拓扑关系对于融入地理空间要素的POI推荐至关重要。本文在融入空间关系时，将空间关系进一步细分为空间距离关系与空间拓扑关系，缓解了数据稀疏的影响。
针对隐性反馈使用问题，本文采用WMF技术来缓解此问题，提出合作竞争矩阵分解模型（cooperative competition matrix factorization，CC-MF），首先通过分析影响POI推荐的相关关系，将空间关系因素融入到推荐模型中，从用户与POI关系的角度融入空间距离因素，从POI与POI关系的角度融入考虑空间拓扑关系的空间距离因素，然后综合它们间的合作关系和竞争关系寻找空间关系的影响。通过使用隐语义模型和WMF以及曝光矩阵分解模型完成推荐任务的启发[27]，从关系的角度分析空间关系因素的影响，并把空间关系融入到MF模型中，完成POI推荐。
1 兴趣点推荐
1.1 问题描述
在POI推荐中，极度的数据稀疏严重影响POI推荐结果的精度。例如，本文使用的用户POI签到Foursquare数据集的数据密度为0.81%。而在推荐系统方面流行的movielens数据集（small）的数据密度为1.7%，由此可见POI推荐任务形势更加严峻。POI推荐的数据稀疏性提高了推荐算法运算复杂性及正确推荐的难度。
根据数据反馈得到的信息类型可以将数据反馈分为显性反馈和隐性反馈[26]，显性反馈数据能够获取正例和负例，通过正例获得用户喜欢什么，通过负例获得用户不喜欢什么，因此只需要通过这些显性反馈去推测用户的偏爱。但是，显性反馈数据获取很困难。而隐性反馈数据（例如签到数据）只有正例，没有负例，该类问题被称为单类问题[25]。在用户-POI矩阵中，有签到信息的元素标记为1，没有签到信息的元素标记为0，如图 1所示。对于没有签到信息的元素，不知道是用户不喜欢还是用户没接触过此POI，或是其他原因。隐性反馈不能直接得出用户的偏好，但是能利用它帮助推荐，因此隐性反馈值得深入考虑。
1.2 矩阵分解
MF技术是协同过滤（collaborative filtering，CF）技术中比较流行的一种处理方法。将MF运用到推荐算法上，可以将m个用户在n个POI上的原始用户签到矩阵Rm×n分解为一个用户特征矩阵Pm×k和物品特征矩阵Qk×n，P和Q的隐性特征空间的维度为k。用户原始签到矩阵R通常是一种非常稀疏的矩阵，且矩阵中元素的个数也能达到千万甚至上亿，使用MF技术可以有效降低数据的维度，合理有效地利用有限的信息。
奇异值分解（singular value decomposition，SVD）是矩阵分解的一种形式，不同于其他矩阵分解方法，SVD适用于任何矩阵。对于矩阵Am×n，可以通过SVD得到Am×n→Xm×k×Yk×n。因为MF的扩展性极好和易于实现，研究人员提出了多种拓展MF算法，以适应不同推荐任务和改进原始MF模型。SVD++是MF中的一个经典模型，它是基于用户的某些隐性反馈信息能够从侧面反映用户的某些偏好的假设提出的。局部低秩矩阵近似（local low rank matrix approximation，LLORMA）是由文献[30]根据矩阵分解出来的矩阵需要满足局部低秩假设提出的。WMF是文献[25]提出用来解决单类问题的一种策略，使用的是加权低秩逼近技术；还有一种策略是负采样技术。社交正则化（social regularization，SRui）是由文献[31]提出的，它将隐性的社交关系融入到了MF中，认为用户的隐性社交关系也能影响人们的选择。除此之外，还有融合深层神经网络和MF的推荐技术[32]，如广义矩阵分解与多层感知机结合等。
1.3 地理信息的作用
地理信息与人们的生活密切相关，它已经在人们的生活中变得常见，许多研究者已将其作为影响POI推荐的因素加入考虑。如文献[12]提出的统一协同POI推荐框架——基于用户偏好和社交影响以及地理影响的推荐（user preferen- ce/social influence/geographical influence based recommendation，USG），将用户偏好、社交信息、地理信息等因素加入到POI推荐模型中，帮助推荐。对于地理信息，他们先对数据进行统计分析，然后从分析结果中总结距离与用户签到之间的关系。文献[4]提出了特征空间分离因子分解模型（feature-space separated factorization model，FSS-FM）模型，加入了时间因素和空间因素的影响，它认为POI的隐性特征中包含时间序列特征和空间特征，并通过时间邻居和空间邻居来进行进一步的求解。文献[33]中提出了一个使用视觉内容、地理信息和社交关系的联合框架——视觉内容和地理影响POI推荐（visual contents and geographical influence for point-of-interest recommendation，VCG），使用图片挖掘更多的POI信息来增强或完善POI的隐性向量。文献[34]通过建立一个自动捕捉用户签到行为的时空上下文信息，且结合知识图谱嵌入的时空上下文感知和基于翻译推荐框架（spatiotemporal context-aware and translation-based recommender framework，STA），更加深刻地发掘了时空信息与用户签到行为的相关性。文献[35]将POI的地理影响、POI的地理敏感性及其物理距离纳入学习框架，研究了POI特有的地理影响。
2 CC-MF矩阵分解模型
针对数据稀疏和隐性反馈使用问题，基于经典的SVD矩阵分解模型，本文提出了一种关系型用户个性化推荐模型CC-MF。首先，CC-MF模型的目的是对于不同用户可以推荐给他们符合自身偏好的POI。其次，CC-MF模型是一种强调个性化推荐的推荐算法，根据合作关系和竞争关系来构建模型。本文关于合作关系的描述为：对于用户，一个用户可能访问某区域内的多个POI，因此，对于POI，它周围POI的被访问次数就会与该POI的访问之间产生一种合作关系，本文使用曝光量描述和计算这种关系的基础。因为在用户-POI签到矩阵中，用户没有签到记录的POI不一定是用户不喜欢的，还有可能是用户根本没有接触过的，所以可以从这方面考虑，假设用户接触POI，给POI赋予一个权重，根据考虑空间拓扑关系的空间距离因素，该值由此因素确定的地理邻居反映。竞争关系描述为：对于用户而言，（1）从时间角度上来讲，同一时间用户不能访问两个POI，这是带有时间的现实属性；（2）从POI角度来看，POI之间存在竞争关系，表现在大部分POI是想得到比较多的访问用户而不是较少的。所以POI之间既有增加该POI被访问概率的因素，又有阻碍该POI被访问的因素。据此，本文在添加影响因素时，通过赋予不同权重来表示合作-竞争关系。CC-MF模型是考虑合作关系和竞争关系而提出的个性化推荐模型，也是结合了空间拓扑因素、空间距离因素的拓展MF。
本文的整体推荐框架如图 2所示，具体步骤如下：
1）转换数据承载方式。对原始签到数据集进行处理，提取信息后转换成用户-POI签到矩阵。
2）挖掘空间关系影响。挖掘用户与POI之间的空间距离因素影响和POI与POI之间的考虑空间拓扑关系的空间距离影响。
3）矩阵分解。构建融入空间距离因素和考虑空间拓扑关系的空间距离因素的矩阵分解模型，获得用户与POI特征向量。
4）个性化推荐。生成给定用户的Top-k个POI推荐列表，实现个性化POI推荐。
对于考虑合作关系和竞争关系的推荐模型，参考文献[36]，其基本的预测公式为：
$$ {\widehat{r}}_{ui}={b}_{i}+{b}_{u}+{\mathit{p}}_{u}{\mathit{q}}_{i}^{\mathrm{T}} $$ (1) 式中，$ {\widehat{r}}_{ui} $是对$ {r}_{ui} $预测的一个值，$ {\widehat{r}}_{ui} $越大，表示用户u访问POI i的概率越大，反之亦然；bi是POI i的偏置项；bu是用户u的偏置项；$ {\mathit{p}}_{u} $是用户u的特征向量；$ {\mathit{q}}_{i}^{\mathrm{T}} $是POI i的特征向量的转置。
2.1 空间距离因素影响
生活圈就是根据人类行为的时空特征、公共资源划分出的一种活动区域，是人类生活在空间上的展开[37]。从认知科学和地理学结合来看，2014年，诺贝尔生理学或医学奖获得者O’Keefe教授发现了位置细胞，Moser夫妇在O’Keefe教授的研究基础上发现了网格细胞，这两种细胞的作用是形成脑中位置信息。所以，人们能够对经常活动的区域在大脑中形成认知地图，依据认知地图，人们可以在脑中形成一种距离概念，判断人们与POI距离是否在可承受范围。而对于计算距离因素常用的幂律公式，由于收集到的原始签到数据中签到位置一般是由经纬度表示的，所以由此来计算两个POI间的转移概率，不过原始签到数据同一个人连续签到的间隔或一个POI连续有人在此签到的间隔较长，可能是几小时，也可能是几天或几星期[16]，这对于数据清洗及统计使用两个连续的签到行为是一个巨大的挑战。除此之外，使用幂律公式由距离求取转移概率所使用的距离变量，其取值范围能从0到几十千米，在半径几十千米的范围中包含上千个POI[12-13]，这会导致POI的转移概率量级差异巨大，从而使计算得到的较大的转移概率吞没掉较小的转移概率而产生与现实不符的情况。所以，本文首先将生活圈概念、特点及作用引入到POI推荐领域，在LBSN上添加生活圈，并根据以相关行为主义地理学、时间地理学、活动分析法等为核心的行为主义研究以及实际情况，选取生活圈半径。其次，计算用户以往的活动中心，统计用户访问过的POI位置（经纬度）、频率，假设每个POI的权重相同，计算出每个用户的活动中心。之后，根据用户活动中心和生活圈，所有POI对于每个用户都会被分为两个部分，即生活圈内的POI和生活圈外的POI。通过生活圈来判断空间距离因素的影响，可以清晰地将POI划分为生活圈内和生活圈外，使得处理空间距离因素更加符合实际情况。为了满足上述计算需求，本文使用非线性函数给予空间距离因素影响一个值，计算公式为：
$$ {D}_{ui}=\left\{\begin{array}{c}1, l\left(i|u\right)\le d\\ 0, l\left(i|u\right)>d\end{array}\right. $$ (2) 式中，Dui= 1表示POI i在以用户u活动中心为中心的生活圈范围内，反之则不在；l是POI i距离用户u往常活动中心的距离；d是本文根据生活圈理论以及实验测试所得出的生活圈半径。
根据式（2）对每个用户、每个POI进行判断，计算得出对每个用户存在空间距离影响的POI集合，得到预测公式为：
$$ {\widehat{r}}_{ui}={b}_{i}+{b}_{u}+{\mathit{p}}_{u}({\mathit{q}}_{i}^{\mathrm{T}}+{\alpha }_{1}\sum\limits_{{i}^{\text{'}}\in {I}_{u, d}^{D}}{w}_{{i}^{\text{'}}}{\mathit{q}}_{{i}^{\text{'}}}^{\mathrm{T}}) $$ (3) 式中，α1为空间距离关系影响系数；$ {I}_{u, d}^{D} $为距离用户u活动中心小于d km的POI集合；$ {w}_{{i}^{\text{'}}} $为$ {I}_{u, d}^{D} $集合长度的倒数。
2.2 考虑空间拓扑关系的空间距离因素影响
在地理学中，地理空间关系不仅包括空间距离关系，还有空间拓扑关系。空间拓扑关系对于地理学是一种重要的空间关系，对空间关系的建立和空间分析有着至关重要的作用。由于空间拓扑关系能显示和突出区域性、相邻性等关系，所以本文不仅融入了空间距离关系的影响，还考虑带有空间拓扑关系的空间距离因素的影响，并以此来帮助POI推荐。
根据之前提到的合作关系和竞争关系，POI的地理邻居会对其产生影响，所以本文使用POI地理邻居的曝光量来反映考虑空间拓扑关系的空间距离因素的影响。由于原始签到数据中是以POI的形式来记录空间实体的，这与承载着拓扑关系的矢量或栅格地图中以面状实体记录空间实体不同，不能直接判断相邻的空间实体，并且两个POI距离最近并不代表它们对应的空间实体是最近的。所以，本文是在空间拓扑关系约束下使用k近邻（k-nearest neighbor，kNN）的方法来寻找POI的地理邻居，并以此反映空间实体的关系。首先，在LBSN上根据POI的地理坐标选择离该POI最近的k个POI作为它的地理邻居（由于空间拓扑关系约束，k不能太小），记录它们在测试签到数据集上被访问频率的总和，之后对所有POI都计算其地理邻居；然后，对所有POI的地理邻居被访问频率求均值；最后，对于每个POI地理邻居被访问频率与均值求差，并乘以一个系数$ \mu $，再使用sigmoid函数将POI的考虑空间拓扑关系的空间距离影响进行归一化。根据式（4）~（7）计算POI的考虑空间拓扑关系的空间距离影响。
$$ {G}_{i}^{\mathrm{\text{'}}}=\sum \limits_{j\in {I}_{i}}{F}_{j} $$ (4) $$ \stackrel{-}{G}=\frac{\sum\limits_{i\in I}{G}_{i}^{\mathrm{\text{'}}}}{\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}\left(I\right)} $$ (5) $$ {G}_{i}=\sigma \left(\mu \left({G}_{i}^{\mathrm{\text{'}}}-\stackrel{-}{G}\right)\right) $$ (6) $$ \sigma =\frac{1}{1+{\mathrm{e}}^{-x}} $$ (7) 式中，$ {G}_{i}^{\mathrm{\text{'}}} $为POI i的地理邻居被访问频率总和，表示POI i的地理邻居在历史签到记录中的总体曝光量；$ {I}_{i} $为POI i的地理邻居集合；I为所有POI集合；$ {F}_{j} $为POI j被访问的频率；$ \stackrel{-}{G} $为所有POI地理邻居被访问频率总和的均值，它是衡量一个POI地理邻居总体曝光量大小的指标，类似于将POI分为位于繁华地区或不繁华地区，此外，由于采用的是自适应数据集的均值而不是固定值，因此对于其他地区数据集也有一定的适用性；Gi为POI i受到的考虑空间拓扑关系的空间距离影响；$ \mu $为计算系数，本文取0.1。计算Gi的过程中使用sigmoid函数是为了增大地理邻居访问频率总和在$ \stackrel{-}{G} $附近的POI间差异，而减小地理邻居访问频率总和远大于或远小于$ \stackrel{-}{G} $的POI间的差异，可以强化考虑空间拓扑关系的空间距离因素对位于均衡地带POI的影响，而弱化对位于特别繁华地带的POI或位于特别不繁华地带的POI的影响。
由于签到矩阵上大多数标记为0的元素并非用户不喜欢，而是不知道，所以本文的任务是模拟用户接触POI，使用用户地理邻居被访问的次数总和作为一个计算量，并依靠此值计算考虑拓扑空间关系的空间距离因素影响。这样做的优势在于：对于那些用户没有签到的POI，它们也将会有一个值参与后续的计算，能够更好地提取POI的特征。加入考虑空间拓扑关系的空间距离影响的预测公式为：
$$ \begin{array}{l}{\widehat{r}}_{ui}={b}_{i}+{b}_{u}+{\mathit{p}}_{u}({\mathit{q}}_{i}^{\mathrm{T}}+{\alpha }_{1}\sum\limits_{{i}^{\text{'}}\in {I}_{u, d}^{D}}{w}_{{i}^{\text{'}}}{\mathit{q}}_{{i}^{\text{'}}}^{\mathrm{T}}+\\ \mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }{\alpha }_{2}\sum\limits_{{i}^{″}\in {I}_{i, K}^{G}}{w}_{{i}^{″}}{\mathit{q}}_{{i}^{″}}^{\mathrm{T}})\end{array} $$ (8) 式中，α2是考虑空间拓扑关系的空间距离影响系数；$ {I}_{i, K}^{G} $为POI i的K个地理邻居集合；$ {w}_{{i}^{″}} $为使用softmax函数根据空间拓扑关系影响Gi计算的权重。
2.3 计算优化策略
本文使用WMF中的加权最小二乘准则构建模型的目标函数，它会对拥有更高频率的元素赋予更大的权重，也是文献[26]提出的用来解决隐性反馈问题的一种方案。为了使模型既能取得好的性能，又可以降低计算量，在更新参数的过程中加入引导程序，采用分块更新参数。使用这种处理方式可以有效地降低计算时间，且能更快地使模型收敛。
原始目标函数为：
$$ {O}_{\mathrm{W}\mathrm{M}\mathrm{F}}=\mathrm{m}\mathrm{i}\mathrm{n}\sum\limits_{u, i}{w}_{ui}{\left({r}_{ui}-{\widehat{r}}_{ui}\right)}^{2} $$ (9) 式中，$ {w}_{ui} $为与用户u在POI i的历史签到记录频率有关的信任度，更多的签到记录意味着更大的$ {w}_{ui} $。由于用户-POI签到矩阵中的0元素可能是未知情况，所以只有是1的元素才加入优化。
在本文的预测公式（8）下，目标函数为：
$$ {O}_{\mathrm{G}\mathrm{E}\mathrm{O}}=\mathrm{m}\mathrm{i}\mathrm{n}\sum\limits_{u, i}{w}_{ui}{\left({r}_{ui}-{\widehat{r}}_{ui}\right)}^{2}+\lambda {‖\mathit{\theta }‖}^{2} $$ (10) 式中，$ \lambda $为正则化系数；$ \mathit{\theta } $表示所有需要更新的参数向量。
对于式（10），本文采用随机梯度下降法（stochastic gradient descent，SGD）更新参数：
$$ \mathit{\theta }\leftarrow \mathit{\theta }-s\frac{\partial {O}_{\mathrm{G}\mathrm{E}\mathrm{O}}}{\partial \mathit{\theta }} $$ (11) 式中，s为学习率。
3 模型推荐性能实验
3.1 实验数据集与参数设置
本文使用真实签到Foursquare数据集[13]来测试所提出的CC-MF模型的性能。该数据集包括2 321个用户、5 596个POI，总共194 108个签到记录，数据稀疏度为0.81%。使用机器学习中常见的网格搜索法调整超参，经过多次重复实验，设置参数学习率s为0.001，正则化系数λ为0.001，空间距离关系影响系数α1为1.8，考虑空间拓扑关系的空间距离影响系数α2为0.004 5，生活圈半径d为1.5 km，地理邻居个数k为10。实验使用计算机处理器（CPU）为i7-8700，内存为32 GB。
实验中对数据集进行切片，按时间顺序的前80%作为训练集，后20%作为测试集。由式（8）计算出所有隐性变量，之后根据计算得到的$ {\widehat{r}}_{ui} $按照大小顺序，为每个用户推荐出k个POI。
3.2 评价指标
评价指标取决于推荐任务，CC-MF模型的任务是推荐给用户Top-k型推荐[4]。本文使用精确率P和召回率R这两种评价指标来评估CC-MF模型的性能。精确率是指推荐正确的POI个数与推荐个数k的比值，召回率是指推荐正确的POI个数与用户在测试集中实际去过的POI个数的比值。
$$ P=\frac{1}{\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}\left(U\right)}\sum\limits_{u=1}^{\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}\left(U\right)}\frac{{S}_{u}\bigcap {M}_{u}\left(k\right)}{k}\times 100\mathrm{\%} $$ (12) $$ R=\frac{1}{\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}\left(U\right)}\sum\limits_{u=1}^{\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}\left(U\right)}\frac{{S}_{u}\bigcap {M}_{u}\left(k\right)}{\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}\left({S}_{u}\right)}\times 100\mathrm{\%} $$ (13) 式中，U表示用户集合；$ {S}_{u} $表示用户在测试集中访问过的POI集合；$ {M}_{u}\left(k\right) $表示CC-MF推荐算法得出的k个POI集合。
3.3 计算复杂度
假设本文使用m×n的用户签到矩阵，包含m个用户和n个POI。矩阵分解过程的计算复杂度为O（mn2）。计算空间距离因素影响的计算复杂度为O（n），考虑空间拓扑关系的空间距离影响的计算复杂度为O（n），本文采用离线计算，该过程的计算复杂度将不被算入到总计算复杂度中。因此，本文提出的推荐算法的计算复杂度为O（mn2）。
3.4 实验结果及分析
本文实验采用的基线方法包括：基于用户的协同过滤（user-based collaborative filtering，UCF）[38]，UCF是一种经典的基于用户协同过滤推荐方法；分解个性化马尔科夫链（factorized personalized Markov chain，FPMC）[16]，FPMC是将用户偏好转化为个性化的马尔科夫链；基于排序的地理因子分解方法（ranking based geographical factorization method，Rank-GeoFM）[28]，Rank-GeoFM是融合空间因素的MF模型，且运用了一种排序优化算法；特征空间分离因子分解模型（feature-space separated factorization model，FSS-FM/T）[4]，FSS-FM/T是融入空间因素的WMF模型，运用排序优化算法；基于矩阵分解的上下文感知POI推荐模型（general matrix factorization model，UCGSMF）[23]，UCGSMF是融合地理信息的矩阵分解上下文感知的推荐算法。在Foursquare数据集上使用本文提出的CC-MF方法与上述几种基线方法进行了对比实验，且测试了空间距离因素和考虑空间拓扑关系的空间距离因素的影响，实验结果分别如图 3和图 4所示。
![]()
图 3 使用Foursquare数据集的推荐性能Figure 3. Recommendation Performance Using the Foursquare Data Sets![]()
图 4 不同因素的推荐性能影响Figure 4. Effects of Different Features on the Recommendation Performance由于模型是根据得分排序得到的推荐序列，所以排在最前面的几个推荐POI即推荐个数为5时，推荐算法得出的结果是最重要的[28]。
1）对比不同基线方法和CC-MF模型的推荐性能。由图 3（a）可以得出，相较几种基线方法，CC-MF模型在k = 5，10，20时，推荐结果的精确率比各基线方法的精确率都要高，性能提升显著，这是因为CC-MF模型加入了考虑空间拓扑关系的空间距离因素的影响。在k = 5时，CC-MF模型的精确率为11.52%，比表现较好的FSS-FM/T提高了约10.33%；除FSS-FM/T以外的其他基线方法，精确率提升的幅度均超过15%。在k = 10或20时，CC-MF模型的精确率仍优于其他基线算法。由图 3（b）可以得出，在k = 5时，CC-MF模型的召回率比其他基线方法提升约4%~9%，在k = 10或20时结果相似，即CC-MF模型的召回率也优于其他基线方法。这说明了空间关系对POI推荐有影响，且融入空间拓扑关系的空间距离因素能够更好地提升推荐算法的性能。
2）对比不同因素的推荐性能影响。如图 4所示，CC-MF模型同时计算空间拓扑因素和空间距离因素的影响，CC-MF/G只计算空间距离影响，CC-MF/D只计算考虑空间拓扑关系的空间距离因素影响，CC-MF/G/D为空间拓扑因素和空间距离因素都不考虑。由图 4可以得出，加入空间距离因素和考虑空间拓扑关系的空间距离因素都能提高推荐系统的性能。在k=5时，对比CC-MF/G/D，加入空间距离因素的CC-MF/G的精确率提升了约5.38%，召回率提升了约7.73%；加入考虑空间拓扑关系的空间距离因素的CC-MF/D的精确率提升了约11.17%，召回率提升了约11.08%；加入空间距离因素和考虑空间拓扑关系的空间距离因素的CC-MF的精确率提升了约14.86%，召回率提升了约13.66%。在k = 10或20时结果类似，此处不再赘述。
3）对比不同参数K和d的影响。图 5和图 6展示了POI地理邻居个数K和生活圈半径d取不同值时对模型推荐性能的影响。可以看出，K和d不同的取值对模型推荐性能的影响很大，合适的取值能有效提升模型的推荐性能。从图 5可以看出，随着K的增大，POI推荐的性能都有明显提升；当K到达阈值时，推荐性能不再提升并逐渐降低。综合考虑POI推荐的精确率和召回率，当K=10时，模型性能达到最优。这表示地理邻居的个数不能过多，也不能过少，当地理邻居过少时，可能会使K个地理邻居中没有包含真正相邻的空间实体，导致与现实不符的情况，不能很好地显示地理邻居的影响且产生偏差；当地理邻居过多时，可能会使地理邻居的影响差异缩小，以至于不能产生良好的效果。从图 6中也可以看出，d的选择不能太大，也不能太小。综合考虑POI推荐的性能，当d=1.5 km时，模型性能达到最优。这表示d过大或过小都不能很好地表示用户的生活圈范围。
通过多次实验，得到如下结论：
1）与多种基线方法对比，从精确率和召回率上看，本文提出的CC-MF模型比当前常用的几种模型的推荐效果都好。
2）考虑空间拓扑关系的空间距离影响能够进一步提升模型的性能。
4 结语
针对数据稀疏和隐性反馈使用问题，本文提出了POI推荐模型CC-MF，首先从关系角度衡量用户、POI间的相互关系，并融入空间拓扑关系以及空间距离关系因素影响，能够有效模拟空间关系的作用，并且具有较好的解释性和拓展性。在Foursquare签到数据集上进行实验，结果表明：（1）CC-MF模型的性能优于当前常用的POI推荐算法；（2）将空间关系细分为空间距离关系和空间拓扑关系并融入模型，可以更有效地提升推荐算法的性能。在未来的工作中，尝试将时间、社交关系等因素加入到CC-MF模型中，研究时空、社交关系等因素的影响模式。
-
![]()
图 3 使用Foursquare数据集的推荐性能
Figure 3. Recommendation Performance Using the Foursquare Data Sets
![]()
图 4 不同因素的推荐性能影响
Figure 4. Effects of Different Features on the Recommendation Performance
-
[1] Bobadilla J, Ortega F, Hernando A, et al. Recommender Systems Survey[J]. Knowledge‑Based Systems, 2013, 46: 109-132
[2] Lu J, Wu D, Mao M, et al. Recommender System Application Developments: A Survey[J]. Decision Support Systems, 2015, 74: 12-32 doi: 10.1016/j.dss.2015.03.008
[3] Zhang C, Wang K. POI Recommendation Through Cross-Region Collaborative Filtering[J]. Knowle‑ dge and Information Systems, 2016, 46(2): 369-387 doi: 10.1007/s10115-015-0825-8
[4] Cai L, Xu J, Liu J, et al. Integrating Spatial and Temporal Contexts into a Factorization Model for POI Recommendation[J]. International Journal of Geographical Information Science, 2018, 32(3): 524-546 doi: 10.1080/13658816.2017.1400550
[5] 宁津生, 吴学群, 刘子尧. 顾及道路通达性和时间成本的多用户位置推荐[J]. 武汉大学学报·信息科学版, 2019, 44(5): 633-639 doi: 10.13203/j.whugis20190026 Ning Jinsheng, Wu Xuequn, Liu Ziyao. Multi-user Location Recommendation Considering Road Accessibility and Time-Cost[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 633-639 doi: 10.13203/j.whugis20190026
[6] 朱敬华, 明骞. LBSN中融合信任与不信任关系的兴趣点推荐[J]. 通信学报, 2018, 39(7): 157-165 https://www.cnki.com.cn/Article/CJFDTOTAL-TXXB201807016.htm Zhu Jinghua, Ming Qian. POI Recommendation by Incorporating Trust-Distrust Relationship in LBSN[J]. Journal on Communications, 2018, 39(7): 157-165 https://www.cnki.com.cn/Article/CJFDTOTAL-TXXB201807016.htm
[7] 廖国琼, 姜珊, 周志恒, 等. 基于位置社会网络的双重细粒度兴趣点推荐[J]. 计算机研究与发展, 2017, 54(11): 2 600-2 610 doi: 10.7544/issn1000-1239.2017.20160502 Liao Guoqiong, Jiang Shan, Zhou Zhiheng, et al. Double Fine-Granularity POI Recommendation on Location-Based Social Networks[J]. Journal of Computer Research and Development, 2017, 54(11): 2 600-2 610 doi: 10.7544/issn1000-1239.2017.20160502
[8] Baral R, Li T. Exploiting the Roles of Aspects in Personalized POI Recommender Systems[J]. Data Mining and Knowledge Discovery, 2018, 32(2): 320-343 doi: 10.1007/s10618-017-0537-7
[9] 王艳东, 李昊, 王腾, 等. 基于社交媒体的突发事件应急信息挖掘与分析[J]. 武汉大学学报·信息科学版, 2016, 41(3): 290-297 doi: 10.13203/j.whugis20140804 Wang Yandong, Li Hao, Wang Teng, et al. The Mining and Analysis of Emergency Information in Sudden Events Based on Social Media[J]. Geomatics and Information Science of Wuhan University, 2016, 41(3): 290-297 doi: 10.13203/j.whugis20140804
[10] 禹文豪, 艾廷华, 杨敏, 等. 利用核密度与空间自相关进行城市设施兴趣点分布热点探测[J]. 武汉大学学报·信息科学版, 2016, 41(2): 221-227 doi: 10.13203/j.whugis20140092 Yu Wenhao, Ai Tinghua, Yang Min, et al. Detecting "Hot Spots" of Facility POIs Based on Kernel Density Estimation and Spatial Autocorrelation Technique[J]. Geomatics and Information Science of Wuhan University, 2016, 41(2): 221-227 doi: 10.13203/j.whugis20140092
[11] Hu L, Sun A, Liu Y. Your Neighbors Affect Your Ratings: On Geographical Neighborhood Influence to Rating Prediction[C]//The 37th International ACM SIGIR Conference on Research and Development in Information Retrieval, Gold Coast Queensland, Australia, 2014
[12] Ye M, Yin P, Lee W-C, et al.Exploiting Geographical Influence for Collaborative Point-of-Interest Re‑ commendation[C]//The 34th International ACM SIGIR Conference on Research and Development in Information Retrieval, Beijing, China, 2011
[13] Yuan Q, Cong G, Ma Z, et al. Time-Aware Point-of-Interest Recommendation[C]//The 36th International ACM SIGIR Conference on Research and Development in Information Retrieval, Dublin, Ireland, 2013
[14] Miller H J. Tobler?s First Law and Spatial Analysis[J]. Annals of the Association of American Geographers, 2004, 94(2): 284-289 doi: 10.1111/j.1467-8306.2004.09402005.x
[15] Si Y, Zhang F, Liu W.An Adaptive Point-of-Interest Recommendation Method for Location-Based Social Networks Based on User Activity and Spatial Features[J]. Knowledge‑Based Systems, 2019, 163: 267-282 http://www.sciencedirect.com/science/article/pii/S0950705118304283
[16] Li X, Jiang M, Hong H, et al. A Time-Aware Personalized Point-of-Interest Recommendation via High-Order Tensor Factorization[J]. ACM Transactions on Information System, 2017, 35(4): 1-23
[17] 王楠, 李金宝, 刘勇, 等. TPR-TF: 基于张量分解的时间敏感兴趣点推荐模型[J]. 吉林大学学报(工学版), 2019, 49(3): 920-933 https://www.cnki.com.cn/Article/CJFDTOTAL-JLGY201903032.htm Wang Nan, Li Jinbao, Liu Yong, et al. TPR-TF: Time-Aware Point of Interest Recommendation Model Based on Tensor Factorization[J]. Journal of Jilin University (Engineering and Technology Edition), 2019, 49(3): 920-933 https://www.cnki.com.cn/Article/CJFDTOTAL-JLGY201903032.htm
[18] Ye M, Liu X, Lee W C. Exploring Social Influence for Recommendation a Generative Model Approach[C]//The 35th International ACM SIGIR Conferen‑ ce on Research and Development in Information Retrieval, Portland, USA, 2012
[19] Guo J, Zhang W, Fan W, et al. Combining Geographical and Social Influences with Deep Learning for Personalized Point-of-Interest Recommendation[J]. Journal of Management Information Systems, 2018, 35(4): 1 121-1 153 doi: 10.1080/07421222.2018.1523564
[20] Wu R, Luo G, Yang Q, et al. Learning Individual Moving Preference and Social Interaction for Location Prediction[J]. IEEE Access, 2018, 6: 10 675-10 687 doi: 10.1109/ACCESS.2018.2805831
[21] Gao S. Spatiotemporal Analytics for Exploring Human Mobility Patterns and Urban Dynamics in the Mobile Age[J]. Spatial Cognition and Computation, 2014, 15(2): 86-114 doi: 10.1080/13875868.2014.984300
[22] Gao R, Li J, Du B, et al. A Synthetic Recommendation Model for Point-of-Interest on Location-Based Social Networks: Exploiting Contextual Information and Review[J]. Journal of Computer Research and Development, 2016, 53(4): 752-763 http://www.researchgate.net/publication/303128375_A_synthetic_recommendation_model_for_point-of-interest_on_location-based_social_networks_exploiting_contextual_information_and_review
[23] 彭宏伟, 靳远远, 吕晓强, 等. 一种基于矩阵分解的上下文感知POI推荐算法[J]. 计算机学报, 2019, 42(8): 1 797-1 811 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201908009.htm Peng Hongyuan, Jin Yuanyuan, Lü Xiaoqiang, et al. Context-Aware POI Recommendation Based on Matrix Factorization[J]. Chinese Journal of Computers, 2019, 42(8): 1 797-1 811 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201908009.htm
[24] Xing S, Liu F, Zhao X, et al. Points-of-Interest Recommendation Based on Convolution Matrix Factorization[J]. Applied Intelligence, 2018, 48(8): 2 458-2 469 doi: 10.1007/s10489-017-1103-0
[25] Pan R, Zhou Y, Cao B, et al. One-class Collaborative Filtering[C]// The 8th IEEE International Conference on Data Mining, Pisa, Italy, 2008
[26] Hu Y, Koren Y, Volinsky C.Collaborative Filtering for Implicit Feedback Datasets[C]// The 8th IEEE International Conference on Data Mining, Pisa, Italy, 2008
[27] Liang D, Charlin L, Mcinerney J, et al. Modeling User Exposure in Recommendation[C]//The 25th International Conference on World Wide Web, Montréal Québec, Canada, 2016
[28] Li X, Cong G, Li X L, et al. Rank-GeoFM: A Ranking Based Geographical Factorization Method for Point of Interest Recommendation [C]//The 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, Santiago, Chile, 2015
[29] Lian D, Zhao C, Xie X, et al. GeoMF: Joint Geographical Modeling and Matrix Factorization for Point-of-Interest Recommendation[C]//The 20th ACM SIGKDD International Conference on Knowle‑ dge Discovery and Data Mining, New York, USA, 2014
[30] Lee J, Kim S, Lebanon G, et al. LLORMA: Local Low-Rank Matrix Approximation[J]. The Journal of Machine Learning Researcch, 2016, 17(1): 442-465
[31] Hao M. An Experimental Study on Implicit Social Recommendation[C]//The 36th International ACM SIGIR Conference on Research and Development in Information Retrieval, Dublin, Ireland, 2013
[32] He X, Liao L, Zhang H, et al. Neural Collaborative Filtering [C]//The 26th International Conferen‑ ce on World Wide Web, Perth, Australia, 2017
[33] Zhang Z, Zou C, Ding R, et al. VCG: Exploiting Visual Contents and Geographic Influence for Point-of-Interest Recommendation[J]. Neurocomputing, 2019, 357: 53-65 doi: 10.1016/j.neucom.2019.04.079
[34] Qian T, Liu B, Nguyen Q V H, et al. Spatiotemporal Representation Learning for Translation-Based POI Recommendation[J]. ACM Transactions on Information System, 2019, 37(2): 1-24 doi: 10.1145/3295499
[35] Wang H, Shen H, Ouyang W, et al. Exploiting POI-specific Geographical Influence for Point-of-Interest Recommendation[C]//The 27th International Joint Conference on Artificial Intelligence, Stockholm, Sweden, 2018
[36] Koren Y, Bell R, Volinsky C. Matrix Factorization Techniques for Recommender Systems[J]. Computer, 2009, 42(8): 30-37 doi: 10.1109/MC.2009.263
[37] 柴彦威, 张雪, 孙道胜. 基于时空间行为的城市生活圈规划研究: 以北京市为例[J]. 城市规划学刊, 2015(3): 61-69 https://www.cnki.com.cn/Article/CJFDTOTAL-CXGH201503009.htm Chai Yanwei, Zhang Xue, Sun Daosheng. A Study on Life Circle Planning Based on Space Time Beha‑ vioural Analysis: A Case Study of Beijing[J]. Urban Planning Forum, 2015(3): 61-69 https://www.cnki.com.cn/Article/CJFDTOTAL-CXGH201503009.htm
[38] Zhou D, Wang B, Rahimi S M, et al. A Study of Recommending Locations on Location-based Social Network by Collaborative Filtering[C]//The 25th Canadian Conference on Artificial Intelligence, Toronto, Canada, 2012
-
期刊类型引用(5)
1. 钟雷洋，周颖，高松，夏吉喆，李珍，李晓明，乐阳，李清泉. 突发公共卫生事件下的人口流动模式变化识别. 武汉大学学报(信息科学版). 2024(07): 1237-1249 . 
百度学术
2. 姜涛，徐胜华，李晓燕，张志然，王勇，罗安，何璇. 时空序列嵌入门控扩张残差网络的兴趣点推荐. 武汉大学学报(信息科学版). 2024(09): 1683-1692 . 百度学术
3. 刘万增，陈杭，任加新，张兆江，李然，赵婷婷，翟曦，朱秀丽. 基于混合智能的街景影像知识提取方法. 测绘学报. 2024(09): 1817-1828 . 百度学术
4. 邓玉洁. 一种隐私保护机制的POI推荐模型分析. 微型电脑应用. 2024(12): 312-316 . 百度学术
5. 李华孝杨，徐青，王卓苧，朱新铭，黄文君. 一种融合用户空间行为特征的兴趣点推荐算法. 测绘科学技术学报. 2024(06): 674-680 . 百度学术
其他类型引用(10)
下载:
计量
- 文章访问数: 983
- HTML全文浏览量: 306
- PDF下载量: 126
- 被引次数: 15
