融合地理位置与社交关系的兴趣点推荐算法

王三军　王玉姣

摘要摘要：随着位置社交网络的快速增长，越来越多的人借助其分享他们的喜好和位置信息，利用这些信息的潜在规律和呈现出来的偏好特征能够有效地帮助用户发现他们真正感兴趣的地点。然而，用户历史记录数据存在着严重的稀疏性，导致推荐结果不准确。鉴于此，融合地理位置因素和用户社交关系，利用矩阵分解模型提出了一种兴趣点推荐（GSMF算法）。实验结果表明，与主流的兴趣点推荐算法相比，该方法在准确率和召回率等多项指标上均取得了更好的结果。

关键词关键词：地点推荐；社交关系；地理因素；GSMF算法

DOIDOI：10.11907/rjdk.171342

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2017）005003405

0引言

近年来，随着Web2.0技术的快速发展，多种地理信息系统已成功实现，如Google公司的Google Earth、微软的MSN Visual Earth等，位置服务和在线社交网络趋于融合，基于位置的社交网络（LBSNs）[13]也在日益兴起，如：Foursquare、Facebook等。用户通过基于位置的社交网络平台以签到的形式分享他们根据自己的喜好而探索的兴趣地点和各种信息。通过对这些丰富的签到信息进行挖掘，可以将其与用户的其它特征结合起来，形成基于用户的历史记录的兴趣库。用户既可以通过兴趣库为其他用户（如朋友）推荐自己感兴趣的位置点和社交场所，并且也可以帮助相关企业分析用户的兴趣从而为用户提供更加个性化的服务。

目前，在已有的推荐算法中，较为普遍的是通过用户的历史签到记录寻找相似用户来进行协同过滤推荐。然而，由于用户签到数据存在严重的稀疏性问题，相似用户的识别一直很困难，导致已有的地点推荐方法效果都不好。为了提高推荐效果，有研究中采用一些签到的辅助信息，例如用户的社交信息[45]、地理位置[6]、情景因素[7]。然而，基于已有工作而建立的模型大多都只是从某一辅助信息出发，假设推荐对象之间相互独立，从而建立一种静态模型，忽略了相关辅助信息之间的内在联系在许多应用场景下对最终推荐效果产生的影响，从而导致推荐结果不准确。

为了能更好地对推荐过程进行建模，从而体现出推荐对象间的关联关系对推荐结果产生的影响。本文在已有的基于矩阵分解的经典推荐算法基础上，提出一种解决现有问题的新思路——融合地理位置和用户社交关系的兴趣点推荐算法，即Geographical and Social Matrix Factorization（GSMF）算法。实验结果表明，与相关主流算法相比，该算法在推荐准确率、召回率等指标上得到了有效提高。

1相关研究

Ye等[8]受基于好友之间分享较多共同兴趣的观点启发，深入研究基于LBSNs的地点推荐方法中用户之间的好友关系，通过分析来自Foursquare的数据集，发现好友关系与地理位置之间的强关联性，进而提出一种基于好友关系的协同过滤推荐方法，该方法通过概率模型体现好友社会关系对地点推荐的影响。Gao等[9]在LBSNs中将矩阵因式分解与位置和社交影响力融合起来进行研究，将社交信息、地理影响力融入到一个广义矩阵分解的框架中，他们将用户在位置上的签到概率模型作为多中心高斯模型来捕获地理影响力，该方法能够有效改进推荐性能。

Cheng等[10]通过22万用户收集2 200万个签到数据，并从分析空间、时间、社交和文本等相关用户足迹几大方面定量评估用户移动性模式，发现：①基于位置的社交网络用户遵循“Levy Flight”移动模式并采用周期性的行为；②地理和经济限制条件影响着移动的模式和用户的社会地位；③与签到相关的基于内容和情感的微博分析能够为更好地理解用户参与这些服务并提供更加丰富的语境来源。Ye等[11]考虑到地理位置的影响，通过假设签到概率和地理距离是幂律分布的，从而取得良好推荐效果。然而，用所提出的协同过滤方法在解决大规模数据集时存在时间耗费较长等缺点。Cheng等[12]将用户社交关系融入概率矩阵分解框架中，但是他们首先通过建立用户在位置上签到的概率模型，继而才将社交信息和地理信息融入一个广义的矩阵分解模型中。Liu等[13]主要从地理的角度，因近邻地点往往有着相似用户的兴趣爱好，所以将地理位置融入矩阵分解模型中，能够更准确地预测用户喜好。Brent Hecht等[14]对Twitter用户资料中与位置领域相关的用户行为进行研究，发现用户的国家和地区事实上能够很容易精准确定，从而表明通过用户的隐含信息揭示位置信息与用户偏好之间的联系。

然而，利用辅助信息的协同过滤推荐方法时间耗费较长，单一信息利用矩阵模型进行推荐的方法其推荐结果不准确。鉴于此，本文融合多因素利用矩阵模型推荐的新思路能够实现更高效的推荐。

2GSMF算法模型

兴趣点的矩阵分解，特别是针对隐式数据的矩阵分解的引入很重要，因为这不仅能够帮助理解如何在给定位置信息情况下推荐兴趣点，而且可以帮助解释为何对于空间聚集效应的建模可以应对来自于矩阵分解稀疏性的挑战，更重要的是，这可能会提升位置推荐的性能。为此，本文综合地理位置和用户社交关系两种因素，提出一种基于地理位置和用户社交关系的矩阵分解模型的兴趣点推荐算法——Geographical and Social Matrix Factorization（GSMF）算法。

2.1地理位置建模

用户在兴趣点的签到记录包含着许多物理信息，因此引用了文献[11]中一个真实数据集的用户签到活动空间分析，该数据集是众所周知的Foursquare数据集。文献[11]中距離和用户兴趣点的关系如图1所示，其中横轴表示用户距离常居地的距离，纵轴表示在此距离上签到记录所占比例。线性部分占近90% 的签到记录，显示了用户签到距常居地一般都很短，这也就形成了常居地附近地点类簇的现象。这一现象可以归因于地理影响，可以直观地作如下解释：①人们往往访问的兴趣点接近于他们的家庭或者办公室；②人们可能对某个兴趣点周围的兴趣点也很感兴趣，即使该兴趣点距离其常居地较远。因此，用户的签到地点往往是形成地理集群区域。根据用户签到的地理集群现象可以进行精确的兴趣点推荐。下文将根据该现象研究地理位置对用户签到行为的兴趣点推荐有何影响。

为了实现这一目标，对地理位置进行兴趣推荐建模。如上分析，用户大多数倾向于在离常居地近的地点签到，因而本文只对距离当前用户常居地近的兴趣点进行考虑，对于过远的地点则不加以考虑。

将用户和地点映射到一个共享的潜在空间，矩阵分解能够有效估计大多数近乎所有地点的整体关系。然而，经典的矩阵分解忽略了地理近鄰位置之间的强关系。从用户签到表中分析得到，最近的近邻地点更倾向于分享共同的用户。受这一观点的启发，本文提出用户ui对地点lj的偏好可用其对地点lj几个近邻地点的偏好表示，设R=ULT，因此本文修改i，j如下：

rnewi，j=αuilTj+（1-α）∑lk∈N（lj）sim（lj，lk）uilTk（1）

其中，i，j是矩阵中的一个元素，α∈[0，1]，是一个加权参数，用于控制近邻地点的影响。该算法认为由于人的行动所限制，只考虑离当前用户近的地点。比如，用户在北京旅游，系统推荐厦门的旅游景点给他，那他是不会接受该推荐的。因此算法提出了一个距离限制的变量：N，N（lj）是地点lj的N组邻近的地点，在实验中，根据经验值设置N=10，如果待推荐的地点不在用户当前位置的N（lj）中则不考虑该地点。N可以根据用户或者应用需求进行设置。

sim（lj，lk）表示近邻地点lk在地点lj地理位置的权重，据前人研究表明，地理邻近的的相似位置往往会有同一用户的访问，其可用如下的高斯函数来表示sim（lj，lk）两个地点的相似度。

sim（lj，lk）=11+D（li，lj）σlk∈N（lj）（2）

其中xj、xk分别表示地点lj、lk的地理坐标（经度和纬度），σ用来表示真实距离到地点位置相似度的放缩关系，设置为1。

本文方法不同于文献[9]，本文考虑地点lj附近的近邻地点N（lj）之间的关系，用户ui对地点lj的偏好是由ui、lj和N（lj）决定。然而，文献[9]用户ui对地点lj的偏好预测是由地点lj与用户ui访问过的地点L（lj）之间的距离来预测的。一般地，N（lj）和L（lj）是完全不同的或者有很小的重叠，这是因为用户ui签到的地点只占到很小的比例。因此这两种方法是由不同的地理位置来建模的。文献[13]中同时考虑到了地点更远的一些区域，而本文只考虑用户一定范围的区域，另外融入用户社交关系进行多因素预测。

2.2用户社交关系建模

文献[18]表明，大多数用户倾向于朋友对他推荐的东西，由此可见，朋友之间推荐的信任度非常高，因此社交影响对推荐系统的影响不可忽视。通常用户间的社交因子可以通过他们是不是好友来决定。但是可以发现，社交网络上的用户并非与其所有好友的签到行为具有相似性，就像现实生活中一样，好友可能有很多，但兴趣品味相一致的只有少数几个。文献[19]提出好友间的社交因子还与他们的共同好友相关。

用户ui与其朋友uf之间的相似度因子s（i，f）由他们是否为好友和他们的共同好友计算得到。计算公式如式（3）所示。

s（i，f）=η×i，f+（1-η）×|Fi∩Ff||Fi∪Ff|（3）

其中，η∈[0，1]，是一个可调节参数。i，f表示用户ui和他朋友uf是否为好友关系，若是好友关系则i，f=1，否则，i，f=0。Fi是用户ui的朋友数据集，Ff是用户uf的朋友数据集。

基于用户的朋友之间有着相似的兴趣爱好，将这一因素融入矩阵分解模型中。因此，本文添加社交因素进一步优化矩阵分解模型如下：

minU，L12||W⊙（R-）||2F+λ12||U||2F+λ22||L||2F+λ32∑mi=1∑f∈Fis（i，f）||Ui-Uf||2（4）

2.3GSMF推荐算法

根据前面考虑的两种因素，本文将地理位置和用户社交关系这两个因素融入矩阵分解模型中，提出GSMF算法。该算法不仅考虑了推荐地点与用户当前位置的距离，同时也能根据用户的社交关系使推荐的效果更好。

将上文中加入地理因素的式（2）和加入社交因素的式（3）带入式（4）中，得到GSMF算法的最小化加权正规化的平方误差损失公式优化如下：

minU，LY（U，L）=12||W⊙（R-ULTPα）||2F+λ12||U||2F+λ22||L||2F+λ32∑mi=1∑f∈Fis（i，f）||Ui-Uf||2（5）

其中，W∈Rm×n是一个权重矩阵；⊙是两个矩阵的Hadamard乘积；Pα=αI+（1-α）PT，I∈Rn×n是单位矩阵；P∈Rn×n，且Pj，k=sim（lj，lk）。s（i，f）是用户ui和他朋友uf之间的相似度因子。λ1、λ2是控制用户和地点矩阵的权重参数，λ3是控制社交关系的权重参数。||U||2F、||L||2F分别用来控制用户和地点的过度拟合。

由于目标函数存在多个变量，可以用一个合适的算法来得到这两个变量U和L。其核心思想就是固定其它参数变量，使目标函数最小化。该算法将会保持更新变量直至收敛或者达到最大的迭代次数。

3实验结果与分析

实验过程如下：搭建实验环境、介绍实验数据集、进行算法验证。实验使用了Foursquare以及Gowalla两个数据集，分别从准确率和召回率两个方面对不同的算法进行实验，最后对实验结果进行分析。从准确率和召回率两个方面进行分析，结果表明，本文提出的GSMF推荐算法是有效的。

3.1实验数据集与实验环境

为了验证推荐算法的准确性，对于两个数据集都进行预处理，都仅保留了每天至少访问5个位置的活跃用户。同时将各种数据分为训练集和测试集，训练集用来学习或训练推荐方法中的相关参数，测试集用来验证推荐的准确性。为了保证在训练集和测试集中都有评分数据，按一定的比例随机地将两个数据集分为训练集和测试集。本文实验中按 8：2的比例将数据随机地分为训练集和测试集。

本实验使用的Foursquare数据集由亚利桑那州立大学计算机学院采集提供。Foursquare数据集主要包括的内容有：用户签到记录数据、用户的常居地数据以及用户的好友关系数据。在这里面，边（好友关系）的数量为47 164条，朋友关系数据中节点数量（用户）为11 326个，签到数据的数量是1 385 223条。Gowalla數据集包含的签到数据为456 988条，用户数量为10 162，地点个数为24 250。

本文实验环境为：Windows7（64位）操作系统，4GB DDR3内存，Intel CPU i3 M350 2.27GHz CPU，实验程序使用Matlab2014版本。

3.2评价指标

在本文中，使用准确率和召回率作为位置推荐的评价指标[1112]来评估 top-k推荐的性能。准确率和召回率分别用P@k和R@k来表示。对一个目标用户ui，P@k表示前k个被推荐的兴趣点会包括多少比例的测试访问地点。R@k是指前k个被推荐兴趣点中有多少比例是这个用户访问过的。LT（ui）表示用户ui签到过的地点，LR（ui）表示前k个被推荐的兴趣点。P@k和R@k定义如下：

P@k=1|T|∑ui∈T|LT（ui）∩LR（ui）|k（8）

R@k=1|T|∑ui∈T|LT（ui）∩LR（ui）|LT（ui）（9）

其中，T表示测试数据中用户的数量。在实验中，选择P@5、P@10、R@5和R@10作为评价指标。

3.3对比算法设计与参数设置

①USG：文献[11]提出的融合用户偏好、地理影响基于线性融合框架的POI兴趣点推荐算法；②MFSR：文献[18]提出的模型，将用户的社交网络关系考虑到推荐模型中，此方法没有考虑产品之间的联系；③PMF：文献[20]提出的概率矩阵分解方法，此方法也没有考虑产品之间的联系；④MGMMF：文献[12]提出的通过多中心高斯模型来捕获地理影响力，继而把社交信息和地理影响力融入到一个广义矩阵因式分解的框架中。

k的值分别设置为5、10。每改变一次k值，为每一个算法计算准确率P@k和召回率R@k。在实验中，考虑实验的效果和有效性，设置隐式空间维数r为200。λ1、λ2是控制用户和地点矩阵的权重参数，通过交叉验证设置为0.015，λ3是控制社交关系的权重参数，设置为0.01。由文献[12]可知，当只考虑距离用户近的地点时，公式（1）中的地理位置权重α在为0.4时推荐效果最佳，因此本实验设置α为0.4。

3.4实验结果分析

实验1：不同特征向量维度下的算法比较分析。

如图2和表1可知，真实的Foursquare数据集和Gowalla数据集表明，由于分别加入对社交关系影响和地理位置因素的影响，PMF算法、MFSR算法和MGMMF算法比较而言，无论是在准确率还是召回率，都有更好的结果。因为MFSR算法是在PMF算法中融入了社交因素，而MGMMF算法是在PMF算法中融入了地理位置，同时该算法采用多中心高斯模型来对地理位置进行建模。而本文算法由于同时融合上述2种因素，相对于MFSR算法和MGMMF算法，在Foursquare数据集上（k=5）准确率分别提高了27.2%和16.6%，召回率分别提高了35.7%和11.8%，在Gowalla数据集上（k=5）准确率分别提高了30%和18.2%，召回率分别提高了36.6%和9.3%。而且本文提出的算法对地理位置建模和社交关系建模上都采用广义矩阵分解的模型，因此无论是准确率还是召回率，与USG算法（采用线性融合框架）相比，在Foursquare数据集上（k=5）准确率和召回率分别提高了6.06%和5.56%，在Gowalla数据集上（k=5）准确率和召回率分别提高了4%和-3.52%。这个结果表明本文的算法虽然没有十分显著的提高，但是进一步说明地理信息和用户之间的社会关系信息对传统协同过滤算法精度的提高起着较大作用，同时说明基于矩阵分解模型的推荐算法优于基于线性融合框架的推荐算法。

实验2：不同稀疏度下的实验结果比较。

为了研究数据稀疏对算法的影响，因此本文对原有的Foursquare数据集进行数据清洗，分别去掉10%、20%、50%的签到记录，这样得到了3种不同的稀疏度，再按照标准情况的实验流程进行实验。可以看出，数据稀疏情况下，融合多种影响因素的协同过滤算法比基于用户的协同过滤算法更能对好的推荐效果起主要作用。

本文在得出数据稀疏情况下算法的平均准确率后，与标准情况下的结果作比较，算出准确率降低的比例。数据稀疏情况下算法准确率降低比例的实验结果如表1所示。

从图3中可以看到，算法PMF的准确率下降最多，GSMF下降最少。GSMF算法在准确率上的降低比例相比USG算法降低了31%，能够更好地处理数据稀疏的状况，这说明基于矩阵分解模型的兴趣点推荐算法比线性融合框架在数据稀疏情况下有更好的推荐效果。

4结语

本文提出了一种在兴趣点推荐过程中考虑推荐对象的社会信息和地理信息的方法，并给出了将它们相结合的基于矩阵分解模型的推荐框架。真实数据集的实验结果表明，推荐对象的社会信息和地理信息在推荐过程中起到了重要作用，对于提高推荐精度有着明显的改善作用。另外，在兴趣点推荐框架中，基于矩阵分解模型比基于线性融合模型框架更加高效。

未来工作中将进一步研究解决数据稀疏、冷启动问题等给本文方法带来的挑战，并且研究如何将更多的信息，如时间信息、评论信息等加入到基于矩阵分解模型的推荐框架中，以进一步提高推荐效果。

参考文献参考文献：

[1]BACKSTROM L，SUN E，MARLOW C.Find me if you can：improving geographical prediction with social and spatial proximity[C].Proceedings of the 19th International Conference on World Wide Web，ACM，North Carolina，2010：6170.

[2]SCELLATO S，NOULAS A，MASCOLO C.Exploiting place features in link prediction on locationbased social networks[C].Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，San Diego，2011：10461054.

[3]MONREALE A，PINELLI F，TRASARTIR R，et al.Where next：a location predictor on trajectory pattern mining[C].In：Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，Paris，2009：637646.

[4]ZHENG V W，CAO B，ZHENG Y，et al.Collaborative filtering meets mobile recommendation：a usercentered approach[C].AAAI，2010：236241.

[5]MA H，ZHOU D，LIU C，et al.Recommender systems with social regularization[C].Proceedings of the Fourth ACM International Conference on Web Search and Data Mining.ACM，2011：287296.

[6]ZHENG V W，ZHENG Y，XIE X，et al.Collaborative location and activity recommendations with GPS history data[C].Proceedings of the 19th International Conference on World Wide Web.ACM，2010：10291038.

[7]李偉，陈毓芬，李萌，等.基于情境的POI个性化推荐方法研究[J].武汉大学学报：信息科学版，2015，40（6）：829833.

[8]YE M，YIN P，LEE W C.Location recommendation for locationbased social networks[C].Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems.ACM，2010：458461.

[9]GAO H，TANG J，HU X，et al.Contentaware point of interest recommendation on locationbased social networks[C].AAAI，2015：17211727.

[10]CHENG Z，CAVERLEE J，LEE K，et al.Exploring millions of footprints in location sharing services[C].SIGCHI Conference on Human Factors in Computing Systems.ACM，2011：237246.

[11]YE M，YIN P，LEE W C，et al.Exploiting geographical influence for collaborative pointofinterest recommendation[C].Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM，2011：325334.

[12]CHENG C，YANG H，KING I，et al.Fused matrix factorization with geographical and social influence in locationbased social networks[C].AAAI，2012：1723.

责任编辑（责任编辑：孙娟）