融合地点影响力的兴趣点推荐算法.docx

    融合地点影响力的兴趣点推荐算法    许朝 孟凡荣 袁冠 李月娥 刘肖摘 要：為解决兴趣点（POI）推荐不准确和效率低的问题，深入分析社交因素和地理位置因素的影响，提出了一种融合地点影响力的POI推荐算法首先，为了解决签到数据稀疏的问题，将2度好友引入协同过滤算法中构建了社交影响模型，通过计算经历和好友相似度获取2度好友对用户的社交影响;其次，深入考虑地理位置因素对POI推荐影响，在对社交网络分析的基础上构造了地点影响力模型，通过PageRank算法发现用户影响力，结合POI被签到次数计算地点影响力，获取准确的整体位置偏好，并使用核密度估计方法对用户签到行为建模和获取个性化地理位置特征;最后，融合社交模型和地理位置模型提高推荐准确性，并通过构造POI推荐候选集来提高推荐效率在Gowalla和Yelp签到数据集上实验，结果表明所提算法能够快速完成POI推荐，在准确率和召回率指标上明显优于融合时间因素的位置推荐（LRT）和融合地理社交因素的个性化位置推荐（iGSLR）算法Key：兴趣点推荐;基于位置的社交网络;协同过滤算法;地点影响力;核密度估计：TP391.1文献标志码：APointofInterest recommendation algorithm combining location influenceXU Chao1，2， MENG Fanrong1， YUAN Guan1*， LI Yuee2， LIU Xiao11.College of Computer Science and Technology， China University of Mining and Technology， Xuzhou Jiangsu 221116， China;2.Archives， China University of Mining and Technology， Xuzhou Jiangsu 221116， ChinaAbstract：Focused on the issue that PointOfInterest （POI） recommendation has low recommendation accuracy and efficiency， with deep analysis of the influence of social factors and geographical factors in POI recommendation， a POI recommendation algorithm combining location influence was presented. Firstly， in order to solve the sparseness of signin data， the 2degree friends were introduced into the collaborative filtering algorithm to construct a social influence model， and the social influence of the 2degree friends on the users were obtained by calculating experience and friend similarity. Secondly， by deep consideration of the influence of geographical factors on POI， a location influence model was constructed based on the analysis of social networks. The users influences were discovered through the PageRank algorithm， and the location influences were calculated by the POI signin frequency， obtaining overall geographical preference. Moreover， kernel density estimation method was used to model the users signin behaviors and obtain the personalized geographical features. Finally， the social model and the geographic model were combined to improve the recommendation accuracy， and the recommendation efficiency was improved by constructing the candidate POI recommendation set. Experiments on Gowalla and Yelp signin datasets show that the proposed algorithm can quickly recommend POIs for users， and has high accuracy and recall rate than Location Recommendation with Temporal effects （LRT） algorithm and iGSLR （Personalized GeoSocial Location Recommendation） algorithm.Key words：pointofinterest recommendation; locationbased social network; collaborative filtering algorithm; location influence; kernel density estimation0 引言随着网络技术和移动对象定位技术的进步，基于位置的社交网络（LocationBased Social Network， LBSN）得到了快速的发展，为人们提供了极其便利的位置服务。

典型的LBSN应用有Foursquare、Gowalla和大众点评等，这些应用主要包括位置推荐、位置签到、位置评论和位置共享等功能[1-2]在LBSN中，为用户推荐可能感兴趣的地理位置的服务被称为兴趣点（PointOfInterest， POI）推荐POI推荐对促进旅游、商家营销推荐、研究用户的活动模式和生活规律具有重要意义协同过滤算法被广泛应用于轨迹聚类[3]和位置预测算法中，大量的兴趣点推荐算法[4-6]在协同过滤算法的基础上，通过考虑社交和地理位置等诸多因素的影响来提升推荐效果， 然而，这些算法普遍存在以下两个问题：1）推荐不准确LBSN中兴趣点总数异常庞大，用户访问的兴趣点只占极少一部分，这导致用户兴趣点签到矩阵极为稀疏，使得挖掘用户的偏好具有难度，且由于各算法在考虑社交和地理位置等因素的影响时不够深入全面，进一步造成推荐的不准确2）推荐缺乏个性化、推荐效率低协同过滤算法的基础是相似度计算，算法缺乏个性化的表示方法，导致难以获取用户的个性化偏好由于算法缺乏简单有效的召回机制，需要针对所有兴趣点计算推荐得分，因此造成大量的时间消耗，导致推荐效率低对于问题1），本文探索用户好友及2hop好友的社交影响，缓解数据的稀疏问题。

融入从整体签到数据和个人签到数据中深入挖掘的地理位置特征，提升推荐的准确性对于问题2），本文利用核密度估计方法对用户的个人签到数据进行建模，用以获取用户个性化的地理位置偏好，提高推荐的个性化程度同时，构造推荐候选集以提高算法的推荐效率针对上述问题，本文综合应用协同过滤技术和社交网络分析技术，从理论上研究LBSN中POI推荐问题，从应用上解决数据稀疏和推荐效率低的问题1 相关工作目前大多数兴趣点推荐算法由协同过滤算法发展而来，主要分析社交因素、地理位置因素和时间因素的影响，并将这些影响因素加入模型中进而改善推荐的效果1）基于社交因素的推荐根据社会同质理论和影响理论，好友间会表现出共同的兴趣爱好和相似行为，用户倾向于接受朋友的推荐大量的研究利用社交因素来提高兴趣点推荐的质量其中：文献[1]在协同过滤算法的基础上，综合考虑社交因素和地理位置因素，提出了融合地理社交因素的个性化位置推荐（Personalized GeoSocial Location Recommendation，iGSLR）算法;文献[4]利用矩阵分解（Matrix Factorization，MF）模型，融合用户的社交影响力对模型进行增强;文献[5]将好友类型划分为社交好友、位置好友和邻近好友，系统地考虑了不同好友的社交影响; 文献[6-7]通过对社交因素、地理位置因素和兴趣点类别因素之间相关性的研究，提升推荐效果。

2）融合地理位置因素的推荐与音乐、电影等项目推荐不同，地理位置因素是興趣点推荐的一个独特因素，大量的研究利用兴趣点在空间上的聚集现象来提高推荐的准确性[8-11]主流的地理位置建模方法有以下三类：幂律分布、高斯分布和核密度估计方法其中：文献[8-9]认为用户签到的分布符合幂律分布，通过幂律分布获取用户签到的距离偏好; Liu等[10]将用户签到分布抽象为高斯分布，结合泊松因子模型进行协同过滤推荐; 与以上方法不同，文献[1，11]利用核密度估计方法从二维角度对用户签到记录进行建模，避免了对所有用户设置公共距离函数的局限性，因此可以获取个性化的地理位置偏好3）综合其他因素的推荐除了社交因素和地理位置因素，时间、兴趣点流行度等因素也会对用户的签到行为产生影响其中，Gao等[12]提出的融合时间因素的位置推荐（Location Recommendation with Temporal effects， LRT）算法，按时间（T=24h）将用户兴趣点签到矩阵进行划分，使用矩阵分解方法获取用户签到的时间偏好文献[13-14]认为兴趣点的流行度体现了兴趣点的服务质量，因此将流行度融入协同过滤算法中，结合社交因素和地理位置因素能够更好地完成推荐。

然而，之前的研究很少考虑用户好友影响力的传播属性，用户的2hop好友也会影响用户行为;同时，在挖掘地理位置特征时不够深入全面，如地点影响力的计算仅考虑兴趣点被签到频率在推荐效率方面，算法缺乏简单有效的召回机制，推荐效率低本文在之前的研究基础上作出以下改进：首先，通过实验验证了用户2hop好友对用户签到行为的影响，并将用户2hop好友加入协同过滤算法的计算中，从而缓解数据稀疏问题，提高推荐的准确性;其次，在对社交网络分析的基础上，构造了地点影响力模型，通过随机游走（PageRank）算法获取用户影响力，并结合地点被签到的频率进一步挖掘地点影响力，深入全面地获取整体地理位置偏好;然后，使用核密度估计方法对个人签到记录进行建模，获取用户个性化的地理位置偏好;最后，综合社交因素和地理位置因素，提高推荐的准确性和个性化程度，并根据地点影响力排名和好友访问兴趣点集合生成推荐候选集，提升推荐效率2 问题描述和相关分析2.1 问题描述在LBSN中，数据集主要分为用户集U={u1， u2， …， um}， 兴趣点集L={ l1， l2， …， ln }和访问时间集T={ t1， t2， …， tk }兴趣点推荐问题的示意图如图1所示，当用户ui在地理层lj和时间层tk完成签到时，其签到记录可以用三元组表示为C=〈ui， lj，tk〉。

本文的研究框架如图2所示。