融合多种影响因子的兴趣点推荐算法

吴会丛 李娇娥 赵明星 高凯

摘 要： 为了解决兴趣点推荐任务中的数据稀疏性问题和充分利用位置社交网络中的多样信息提高个性化推荐质量，提出了一种融合多种影响因子的兴趣点推荐算法。分别对地理信息和社会信息进行地理影响力建模和社会影响力建模，并联合时间信息和地理信息进行时空影响力建模，然后以加权求和的方式整合3种影响力评分得到用户偏好分数，根据用户偏好分数为每个用户提供1个包含Top-N个兴趣点的推荐列表。实验结果显示，在2个公开数据集上，融合多种影响因子的兴趣点推荐模型的性能优于对比模型。地理-社会-时空影响是兴趣点推荐任务中的关键，对这3种影响建模可为融合关键信息的兴趣点推荐研究提供参考。

关键词： 自然语言处理;兴趣点推荐;地理影响力建模;社会影响力建模;时空影响力建模

中图分类号：TP319文献标识码： A

doi：10.7535/hbkd.2020yx06004

Point-of-interest recommendation algorithm

integrating multiple impact factors

WU Huicong， LI Jiaoe， ZHAO Mingxing， GAO Kai

（School of Information Science and Engineering， Hebei University of Science and Technology， Shijiazhuang， Hebei 050018， China）

In order to solve the problem of data sparseness in the task of point-of-interest recommendation and make full use of the diverse information in the location-based social network to further improve the quality of personalized recommendation， a point-of-interest recommendation algorithm integrating multiple impact factors was proposed. Geographic influence modeling and social influence modeling were performed on geographic information and social information， and temporal information and geographic information were combined to model temporal and spatial influence， and the three influence scores were integrated in a weighted summation manner to obtain user preference score. According to the user preference score， each user was provided with a recommendation list containing Top-N points of interest. The experimental results show that on the two public datasets， the point-of-interest recommendation model that integrates multiple impact factors performs better than the baselines. In addition to the user check-in frequency， the geographic-social-spatial-temporal influence is also a key part of the point-of-interest recommendation task， and the modeling of these three influences is of great significance， which provides certain reference value for the research of point-of-interest recommendation integrating key information.

natural language processing; point-of-interest recommendation; geographic influence modeling; social influence modeling; spatial-temporal influence modeling

近年來，随着移动互联网技术的不断发展和成熟，位置社交网络（location-based social network， LBSN）逐渐兴起并成为人们生活中的重要组成部分。兴趣点（point-of-interest， POI）推荐在LSBN中起着至关重要的作用，不仅是推荐领域中一个非常重要的任务，也是时空数据挖掘中的一项极具意义的应用型研究。

不同于传统推荐任务，在POI推荐场景中，蕴含着大量的时间信息、地理信息和社会信息，用户在进行下一个兴趣点的选择时，除了遵从自身的喜好外，还可能会受到时间的影响、地理的影响和社会的影响。如图1所示，本文将联合用户和未签到过的兴趣点之间的3种影响力（地理影响力、社会影响力和时空影响力）建模，预测目标用户对未签到过兴趣点的偏好分数。

2.3 社会影响力建模

用户之间的社会联系也被广泛使用，以提高兴趣点推荐系统的性能，因为相比陌生人，社交好友在POI上更有可能有共同兴趣。因此，本文通过利用目标用户u与在目标兴趣点v上签到过的好友之间的社会影响力来推断用户u与兴趣点v的相关性得分。该过程包括3个步骤：社会聚合、社会签到频率分布估计和社会影响力分数计算。

步骤1：社会聚合（即聚合用户u的好友在目标兴趣点v上的签到频率） 给定一个用户u和一个未签到过的目标兴趣点v，根据式（8）汇总用户u的好友们（如u′，其中Su，u′=1）在v上的签到频率xu，v：

xu，v=∑[DD（X]u′Su，u′·Ru′，v，（8）

式中：Ru′，v为用户u′在目标兴趣点v上的签到频率;Su，u′表示用户u与用户u′是否是好友关系，如果Su，u′=1，则说明用户

u与用户u′间存在好友关系，否则，不存在好友关系。

步骤2：社会签到频率分布估计 在真实世界的数据集中，社会签到频率的随机变量x遵循幂律分布[17]，其概率密度函数可被定义为

fSo（x）=（β-1）（1+x）-β， x≥0， β>1。

其中β的计算公式如下：

β=1+[∑[DD（X]u∈U ∑[DD（X]v∈Vln（1+xu，v）]-1。

步骤3：社会影响力得分计算 基于社会签到频率分布，对所有用户历史签到数据进行学习后，将社交签到频率转换为正则化的影响力分数。基于fSo（x）的累积分布函数，定义xu，v的社会影响力分数为

sSo（xu，v）=∫xu，v0fSo（z）dz=1-（1+xu，v）1-β。（9）

社会影响力分数sSo反映了用户在POIs上的所有社会签到频率的相对位置，因为1-β<0，所以sSo是一个递增函数，随社会签到频率xu，v的增大而增大。

2.4 时空影响力建模

当前有关兴趣点推荐的研究往往对时间信息和地理信息分开进行建模，但是用户在不同的时间状态（如工作日或休息日）下签到活动中心也是不同的。因此，基于文献＼[21＼]的思想，本文除了进行地理影响力建模，

还联合考虑地理影响力和时间影响力，进行时空影响力建模。

用户的签到活动往往是基于中心的模式，所以需要获取若干个用户签到活动中心。首先，对于每个用户u在某个时间状态T签到过的兴趣点Vu，T按照签到频率排序，然后选择签到最频繁的兴趣点，将与其距离小于距离α的兴趣点划分为一个区域，得到签到活动中心集合Cu，T。

给定用户u在时间状态T下的签到活动中心集合Cu，T，用户u访问兴趣点v的时空影响力得分为

sTemGeo（u，v|Cu，T）=∑|Cu，T|Cu，T

1dist（v，Cu，T） freqCu，T∑i∈Cu，Tfreqi，

式中：1dist（v，Cu，T）為根据兴趣点v与签到活动中心Cu，T之间的距离确定兴趣点v是否属于签到活动中心Cu，T的打分;freqCu，T为用户u在签到活动中心Cu，T的签到频率;∑i∈cu，Tfreqi为用户在所有签到活动中心内的签到概率。

本文只考虑工作时间状态和休息时间状态。时间状态的划分是根据用户对兴趣点的签到时间，周一—周五每天8：00—18：00规定为工作时间状态，其他时间为休息时间状态。因此，时空影响力得分sTemGeo（u，v|Cu，T）可进一步定义为

sTemGeo（u，v|Cu，T）=sTemGeo（u，v|Cu，WT）+sTemGeo（u，v|Cu，LT），（10）

式中：sTemGeo（u，v|Cu，WT）为工作时间状态下的时空影响力得分;sTemGeo（u，v|Cu，LT）为休息时间状态下的时空影响力得分。

2.5 兴趣点推荐

融合式（7）、式（9）和式（10）给定的地理影响力得分、社会影响力得分和时空影响力得分，根据用户u对兴趣点v的偏好，基于加权求和的方式，把这些影响力得分整合，得到一个统一的偏好分数s（u，v）：

s（u，v）=λ1sGeo+λ2sSo（xu，v）+λ3sTemGeo（u，v|Cu，T），

式中λ1，λ2和λ3分别为地理影响力得分、社会影响力得分和时空影响力得分的权重系数，且保证λ1+λ2+λ3=1。

按照偏好分数s（u，v）排序，推荐给用户u得分值最高的Top-N个兴趣点。

3 实 验

3.1 数据集描述

为了证明本文所建模型的有效性，在Gowalla数据集和Foursquare数据集[3]2个公开数据集上进行实验。Gowalla数据集记录了2009-02-01—2010-10-31全球范围内的签到数据，Foursquare数据集包括2012-04-01—2013-09-31的签到数据。每条签到记录都包含1个用户、1个POI兴趣点（纬度和经度）和1个签到时间戳。在实验过程中，本文对数据集进行了预处理。对于Gowalla数据集，将签到次数少于15的用户和被访问人数不足10的兴趣点删除;对于Foursquare数据集，将签到次数少于10的用户和被访问人数不足10的兴趣点删除。被处理过的数据集详细信息如表1所示。

本文将每个数据集划分为训练数据、验证数据和测试数据。对于每个用户，将最早期的70%签到作为训练数据，将最近期的20%签到作为测试数据，其余的10%作为验证数据。

3.2 评价指标设定

为评估推荐模型的性能，本文使用3个评测指标：Precision@N，Recall@N和nDCG@N，其中N∈{10，20}。Precision@N是指推荐结果中用户实际访问的兴趣点数量占推荐结果总数的比例，反映推荐的准确性;Recall@N是指推荐结果里用户实际访问的兴趣点数量占用户实际访问兴趣点总数的比例，反映推荐的全面性;nDCG@N是一种表示推荐模型排序质量的度量方法。

3.3 参数设置

本文采用工程化的方法进行了参数的选择，最优结果可能略有偏差。在进行的所有对比实验中，对于Gowalla数据集，当α=40时，模型性能最佳，对于Foursuqare数据集，当α=15时模型性能最佳。在融合3种影响力时的权重设置上，对于Gowalla数据集，当λ1=0.7，λ2=0.2，λ3=0.1时，模型性能最佳。Foursquare数据集中不存在社交关系数据，因此当λ1=0.9，λ2=0.0，λ3=0.1时，模型性能最佳。

3.4 实验结果与分析

3.4.1 实验结果

为了证明本文模型的有效性，将其与以下4种基线方法进行比较。

PFM[22]：是一类基于概率的模型，在用户-POI签到矩阵分解的基础上实现，可以直接对签到频率数据进行建模，将Beta分布作为先验值放在潜在矩阵U和V上，对签到频率的建模符合泊松分布。

MGMPFM[4]：是一种结合了PFM输出以及地理建模方法的混合模型，采用多中心高斯模型作为地理建模方法。

LRT[18]：是一个时间增强的矩阵分解模型，分别为每个时间间隔进行签到矩阵的分解，以在不同的时间对用户进行建模。

iGLSR[12]：利用POI推荐的地理偏好和社会影响力，采用基于好友的协同过滤对社会影响力建模。对于每个用户，iGLSR使用核密度估计（kernel density estimation，KDE）从历史签到记录中学习距离分布。因此，用户访问新的POI的概率是基于POI与用户所访问的POI之间的距离的KDE值。

由于无法获取Foursquare数据集中的好友社交关系数据，因此对2个数据集进行分开实验：在Gowalla数据集上完整利用了本文提出3种影响力模型，而在Foursquare数据集上只利用了本文所提出的地理影响力模型和时空影响力模型。2个数据集上的实验结果分别如表2和表3所示，本文所有实验中对比模型的实验结果来自文献＼[20＼]和文献＼[21＼]。其中MGMPFM模型是基于地理信息建模的，LRT模型是基于时间信息建模的，iGLSR模型是基于地理信息和社交信息建模的。

从表2可知，所提出的融合多种影响因子的兴趣点推荐模型与其他4种基线模型相比性能有所提升。

由此可见，本文基于时间信息、地理信息和社交信息等多种上下文信息的建模是有意义的。

从表3可知，本文提出的用于兴趣点推荐的地理影响力模型和时空影响力模型的效果明显好于其他3种模型。

3.4.2 实验分析

1）模型参数影响分析 图4展示了在Gowalla数据集上本文模型中的距离阈值参数α在不同取值时，Precision@10，Recall@10和nDCG@10 3个评测指标的结果。从图4可知，在Gowalla数据集上，α=40时模型效果最好，可以综合反映出用户的签到行为具有活动中心性。

2）用户签到POIs数量影响分析 本文仅在Gowalla数据集上进行有关用户签到POIs数量影響的实验和分析，即研究训练数据量大小对实验结果的影响。分别对随机选择的40%，60%和80%训练数据进行实验，对比结果如图5所示。从图5可知，在不同比例的数据上，本文模型的性能均优于4种基线模型，说明本文模型很好地解决了当前兴趣点推荐任务中的数据稀疏性问题。

3）3种影响力的影响分析 本文仅在Gowalla数据集上进行了3种影响力的影响分析，即分别单独利用其中1种影响力进行兴趣点推荐。如表4所示，本文进行了5组实验：仅利用地理影响力建模（Geo）、仅利用社会影响力建模（So）、仅利用时空影响力建模（TemGeo）、融合地理影响力建模与社会影响力建模（Geo+So）、融合3种影响力建模（Geo+So+TemGeo）。从表4可知，融合3种影响力的兴趣点推荐模型性能均好于仅利用1种或2种影响力的推荐模型，证明了所提出的融合多种影响因子的兴趣点推荐模型的有效性。

4 结 语

本文提出了融合多种影响因子的兴趣点推荐模型，分别对地理信息、社会信息进行地理影响力建模和社会影响力建模，并联合时间信息和地理信息进行时空影响力建模，然后以加权求和的方式整合3种影响力评分得到用户偏好分数，达到了充分利用位置社交网络中的信息提高兴趣点推荐性能的目的。通过与其他模型比较，证明了此模型是有效的。

本文模型仍有较大的提升空间。首先，基于地理影响力建模，仅考虑了单个用户频繁活动中心，有一定的局限性;其次，基于社会影响力建模，只考虑了直接好友关系;最后，基于时空影响力建模，时间状态仅笼统地划分为工作时间和休息时间，且在2种时间状态的界定上还有不足。除此之外，未来的工作中拟考虑整合更丰富的上下文信息（如用户评论信息）到兴趣点推荐模型中。

参考文献/References：

[1]BAO Jie， ZHENG Yu， WILKIE D， et al. Recommendations in location-based social networks： A survey[J]. GeoInformatica， 2015， 19（3）： 525-565.

[2]YIN Hongzhi， SUN Yizhou， CUI Bin， et al. LCARS： A location-content-aware recommender system[C]// Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： [s.n.]， 2013： 221-229.

[3]LIU Yiding， PHAM T A N， CONG Gao， et al. An experimental evaluation of point-of-interest recommendation in location-based social networks[C]// Proceedings of the VLDB Endowment. Trondheim：[s.n.]， 2017： 1010-1021.

[4]CHENG Chen， YANG Haiqin， KING I， et al. Fused matrix factorization with geographical and social influence in location-based social networks[C]// Proceedings of the 26th AAAI Conference on Artificial Intelligence. Toronto：[s.n.]， 2012： 17-23.

[5]YE Mao， YIN Peifeng， LEE W C， et al. Exploiting geographical influence for collaborative point-of-interest recommendation[C]//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. Beijing： [s.n.]， 2011： 325-334.

[6]FARRAHI K， GATICA-PEREZ D. Discovering routines from large-scale human locations using probabilistic topic models[J]. ACM Transactions on Intelligent Systems and Technology， 2011， 2（1）： 1-27.

[7]KURASHIMA T， IWATA T， HOSHIDE T， et al. Geo topic model： Joint modeling of user's activity area and interests for location recommendation[C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining. Rome：[s.n.]， 2013： 375-384.

[8]LIU Xin， LIU Yong， ABERER K， et al. Personalized point-of-interest recommendation by mining users' preference transition[C]//Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. Burlingame： [s.n.]， 2013： 733-738.

[9]FU Yanjie， LIU Bin， GE Yong， et al. User preference learning with multiple information fusion for restaurant recommendation[C]//Proceedings of the 2014 SIAM International Conference on Data Mining. Philadelphia： [s.n.]， 2014： 470-478.

[10]YUAN Quan， CONG Gao， MA Zongyang， et al. Time-aware point-of-interest recommendation[C]//Proceedings of the 36th ACM SIGIR Conference on Research and Development in Information Retrieval. Dublin： [s.n.]， 2013： 363-372.

[11]YUAN Quan， CONG Gao， SUN Aixin. Graph-based point-of-interest recommendation with geographical and temporal influences[C]//Proceedings of the 23th ACM International Conference on Information and Knowledge Management. Shanghai： [s.n.]， 2014： 659-668.

[12]ZHANG Jiadong， CHOW C Y. iGLSR： Personalized geo-social location recommendation：A kernel density estimation approach[C]//Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Orlando： [s.n.]， 2013： 334-343.

[13]ZHANG Jiadong， CHOWA C Y. CoRe： Exploiting the personalized influence of two-dimensional geographic coordinates for location recommendations[J]. Journal of Information Sciences， 2015， 291： 163-181.

[14]ZHANG Jiadong， CHOWA C Y， LI Yanhua. LORE： Exploiting sequential influence for location recommendations[C]//Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Dallas： [s.n.]， 2014： 103-112.