地理分层结构与社会关系的兴趣点推荐

李昱杭 杨艳 高静远

摘  要：随着基于地理位置的社交网络的兴起，兴趣点（POI）推荐引起了人们的许多关注。POI推荐向用户推荐他们可能感兴趣但没有访问过的地方，从而解决用户“下一步去哪”的问题。本文提出新的用户相似性度量、全局影响力以及热门POI的概念。综合考虑了多个影响因素之间的关系，以地理分层结构的矩阵分解模型（HGMF）为基础，提出新的POI推荐算法HGS-MF。在Yelp和Gowalla社交网络数据集上对HGS-MF进行了评估。实验结果表明，HGS-MF方法的实验表现均优于传统的POI推荐算法。

关键词：矩阵分解;地理分层结构;社会关系;推荐;兴趣点

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

Abstract：With the rise of location-based social networks，Points of Interest （POI） recommendations have attracted a lot of attention.The POI recommends places which users may be interested in but have not visited，thus addressing the user's issue about Where to Go Next.This paper proposes new user similarity measures，global influences，and the concept of popular POIs.Based on the relationship between multiple influencing factors，a new POI recommendation algorithm HGS-MF is proposed based on the Hierarchical Geographical Matrix Factorization model （HGMF）.HGS-MF is evaluated on the social network datasets of Yelp and Gowalla.The experimental results show that the performance of the HGS-MF method is superior to that of the traditional POI recommendation algorithm.

Keywords：matrix factorization;geographical hierarchy;social relationship;recommendation;Points of Interest

1   引言（Introduction）

隨着移动设备的普及与定位技术的进步，越来越多的人们通过社交软件分享生活。由于大规模移动记录的易得性和社交网络信息的广泛性，POI推荐成为热门的话题，很多研究工作者通过对用户的签到记录进行分析，从而获取用户的偏好。例如：Zhao等人[1]、Lian等人[2]、Liu等人[3]对用户的签到数据进行分析，发现用户签到行为具有一定的地理规律，通过签到行为可以将完全不吸引用户的地点与未被发现但可能吸引用户的地方进行区分。此外，POI的类别具有一定的层级关系，某些类别的POI可以进一步地划分，用户的内容偏好也同样呈现出一定的层次结构[4]。

然而，当前的大多数矩阵分解模型都存在一个问题：它们只考虑用户和POI的偏好，没有考虑到用户的多种社交关系和最近一段时间热门的POI对用户的影响，例如，年轻人可能喜欢去他仰慕的公众人物签到过的POI进行签到，用户也有更大的可能性喜欢去与他具有相似行为的用户去过的POI进行签到。此外，年轻人可能会去最近比较火暴的店签到，因此，只考虑用户偏好和POI的属性，来推测这个用户的行为会降低POI推荐的准确率。

为了进一步提高实验表现，本文在之前的方法基础上提出一种新的用户的社交关系，并提出全局影响力与热门POI的概念，向用户进行更为准确的POI推荐，提出了一种地理分层结构与社会关系的推荐算法（Hierarchical Geographic and Social Matrix Factorization，HGS-MF），实验结果表明，在Yelp和Gowalla两个真实数据集上与相关的算法相比较，该算法在召回率，准确率等评价指标上相对于传统方法都得到了显著提高。

2   相关工作（Related work）

近些年，随着地理位置的社会网（LBSN）的发展，研究者可以更方便地分析用户的签到记录进而分析用户的行为习惯，从而得到其偏好。许多研究者尝试提高POI推荐模型，从而提高实验效果。

在传统的基于用户的协同过滤模型基础上，文献[5]—文献[6]融合用户偏好、社会影响和地理影响因素，旨在提高推荐的准确性，但它没有考虑POI具有一定地理层级的关系，比如美术家更喜欢去美术博物馆签到，而不是普通博物馆;Li等人[7]根据社交朋友和类似用户的签到记录建模，从而提高模型的实验表现，但它考虑社交因素不够全面，并未考虑公众人物对用户的影响。

在传统的基于时间影响的推荐模型基础上，文献[8]—文献[9]提出时间感知的协同过滤推荐模型，通过结合时间因素和地理影响因素，根据人们日常生活习惯划分时间轴，并将中午时段作为午餐时段，但是每个人的生活作息不同，用部分人的日常生活习惯推测每个人的行为是不准确的，并且会降低POI推荐的效果。

在传统的基于矩阵分解的推荐模型基础上，Li等人[10]通过结合时间影响，考虑用户偏好、地理图形影响和用户移动性行为，利用地理因子分解方法实现的POI推荐，但是忽略了社交关系对用户的重要影响;Hu等人[11]根据用户签到频数，提取用户对POI的偏好，从而实现POI推荐，但是它没有考虑地理因素影响，并且在社交关系方面考虑的不够全面;Zhao等人[1]、Lian等人[2]分析用户的签到数据，发现用户签到行为具有地理规律，并且发现POI的类别具有一定的层级关系，但其未考虑用户的社会关系，并且在POI的影响力方面考虑的不全面。

這些算法虽然在一定程度上解决了POI推荐领域上的一些问题，但是仍具有一定的局限性，例如：用户相似性的影响因素选取过于单一，没有充分挖掘POI的热门信息，没有充分利用用户的社交关系。本文基于分层地理矩阵分解模型。提出一种新的用户的社交关系，并提出全局影响力与热门POI的概念，从而向用户进行更为准确的POI推荐。

3   HGS-MF算法（HGS-MF algorithm）

3.1   基础模型

3.1.1   加权矩阵分解模型

给定用户签到频数矩阵，其中M、N分别为用户的个数和POI个数，矩阵中每一项表示用户在POI 签到的次数。

3.2   HGS-MF算法

本算法在HGMF模型的基础上进行改进，提出新的用户相似性度量、全局影响力和热门POI的概念。

3.2.1   社会关系

在现实生活中，用户在访问某POI时，更倾向于倾听朋友的意见。用户的朋友往往与用户拥有相同的行为习惯，在用户未访问过的POI，用户往往会听从朋友的推荐[12]。

本文认为社交关系由用户相似度与用户的影响力两方面组成。在目前已有的用户相似度计算中，只考虑在相同POI签到的用户的相似性，以及拥有公共好友的用户相似性，并没有考虑到用户的多种社交关系和最近一段时间热门的POI对用户的影响。本文在这两种相似度的基础上提出时间影响下的用户相似性，并且在目前已有的POI推荐中，没有在社交关系中考虑到用户的影响力因素，本文提出了用户全局影响力，并融入社交关系中。

定义1（用户好友关系矩阵）：设F为用户的好友列表，满足，矩阵中每一项表示用户与用户的好友关系，如果满足好友关系，则值为1，否则为0。

定义2（时间影响用户行为矩阵）：设T为在时间影响下的用户的行为矩阵，本文将时间分为24小时，满足，矩阵中每一项表示用户i在时间段内在POI 的签到情况，如果签到则为1，否则为0。

根据对比可以看出，在参数均最优的情况下，HGS-MF模型在精确率与召回率两方面都高于其他算法。

5   结论（Conclusion）

本文利用用户的社会关系，提出了一个新的用户相似性度量、全局影响力以及热门POI的概念，在此基础上提出结合分层地理矩阵分解模型得到HGS-MF模型，利用两步优化，第一步优化采用交替最小二乘法和梯度下降方法求解单层模型，第二步采用KKT条件优化分层模型。实验结果表明，融合社会关系与热门POI影响力的加权矩阵分解能够有效地提高推荐性能，模型优于传统的POI推荐算法。未来将尝试将本文提出的模型和深度学习相结合，期待进一步提高兴趣点推荐性能。

参考文献（References）

[1] Zhao P，Xu X，Liu Y，et al.Exploiting Hierarchical Structures for POI Recommendation[J].IEEE International Conference on Data Mining （ICDM），2017：655-664.

[2] Lian D，Zhao C，Xie X，et al.GeoMF：Joint Geographical Modeling and Matrix Factorization for Point-of-Interest Recommendation[C].Acm Sigkdd International Conference on Knowledge Discovery & Data Mining.ACM，2014：831-840.

[3] Liu B，Fu Y，Yao Z，et al.Learning geographical preferences for point-of-interest recommendation[C].Acm Sigkdd International Conference on Knowledge Discovery & Data Mining.ACM，2013：1043-1051.

[4] Moreno-Jimenez J M，Vargas L G.A Probabilistic Study of Preference Structures in the Analytic Hierarchy Process with Interval Judgments[J].Mathematical and Computer Modelling，1993，17（4-5）：73-81.

[5] Ye M，Yin P，Lee W C .Location recommendation for location-based social networks[C].Acm Sigspatial International Symposium on Advances in Geographic Information Systems.DBLP，2010：458.

[6] Ye M，Yin P F，Lee W C，et al.Exploiting Geographical Influence for Collaborative Point-of-interest Recommendation[C].International Acm Sigir Conference on Research & Development in Information Retrieval.ACM，2011：325-334.

[7] Li H，Hong R，Zhu S，et al.Point-of-Interest Recommender Systems：A Separate-Space Perspective[C].2015 IEEE International Conference on Data Mining （ICDM）.IEEE Computer Society，2015：231-240.

[8] Yuan Q，Cong G，Ma Z，et al.Time-aware point-of-interest recommendation[C].International Acm Sigir Conference on Research & Development in Information Retrieval.ACM，2013：363-372.

[9] Yuan Q，Cong G，Sun A.Recommendation with Geographical and Temporal Influences[C].Acm International Conference on Conference on Information & Knowledge Management.ACM，2014：659-668.

[10] LiX T，CongG，et al.Rank-GeoFM：A Ranking based Geographical Factorization Method for Point of Interest Recommendation[C].Proceedings of the 38th International ACM SIGIR Conferenceon Researchand Development in Information Retrieval，2015：433-442.

[11] Hu Y，Koren Y，Volinsky C.Collaborative Filtering for Implicit Feedback Datasets[C].Eighth IEEE International Conference on Data Mining.2008：263-272.

[12] Wang H，Terrovitis M，Mamoulis N.Location recommendation in location-based social networks using user check-in data[C].Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.ACM，2013：364-373.

[13] Xianyi Z，Qian W，Yunquan Z.Model-driven Level 3 BLAS Performance Optimization on Loongson 3A Processor[C].2012 IEEE 18th International Conference on Parallel and Distributed Systems.IEEE，2012：684-691.

[14] Sarwar B，Karypis G，Konstan J，et al.Item-based collaborative filtering recommendation algorithms[C].International Conference on World Wide Web，2001：285-295.

作者簡介：

李昱杭（1997-），女，硕士生.研究领域：社会网，数据挖掘.

杨  艳（1975-），女，博士，教授.研究领域：社会网，数据挖掘.本文通讯作者.

高静远（1994-），男，硕士生.研究领域：社会网，POI推荐.