LBSN中基于活动区域划分的元路径兴趣点推荐
2017-12-07徐泽锋刘文菊
徐泽锋，刘文菊，王 赜
（天津工业大学计算机科学与软件学院，天津 300387）
LBSN中基于活动区域划分的元路径兴趣点推荐
徐泽锋1，刘文菊2，王 赜2
（天津工业大学计算机科学与软件学院，天津 300387）
基于位置的社交网络（Location Based Social Networks，LBSN）的相关服务推荐越来越多，而兴趣点（Point Of Interest，POI）推荐作为LBSN相关服务中的一项个性化推荐也备受关注，越来越多的学者投入研究。目前，各种基于位置的推荐算法层出不穷，但由于LBSN中的数据极度稀疏的原因，导致许多算法推荐精度不高，本文提出了一种基于用户活动区域划分的元路径推荐算法。首先，根据用户签到以及点评的地点呈现区域性，将用户活动区域分为频繁活动区域和不经常活动区域，根据LBSN结构特征构建用户-活动区域和活动区域-兴趣点之间的二分图模型，其次引入元路径，计算从用户到兴趣点的实例路径的关联度，最后根据关联度大小生成推荐列表。结果表明，该算法较传统的LBSN推荐算法有更好的推荐效果。
基于位置的社交网络；区域划分；元路径；兴趣点推荐
0 引言
随着网络的发展，web 2.0技术的进步，卫星通信、无线传感器网络、GPS导航设备等不断向前发展，用户获得实时位置的功能越来越精确，这样也催生了基于位置的社交网络（Location Based Social Network，LBSN），使得基于位置的社交网络迅速发展。国内外一些流行的基于位置的服务如微信朋友圈、Gowalla、Foursquare、街旁等正在一步一步促进人们的社交模式从传统的在线社交转变为基于位置的社交。在LBSN中增加位置信息，以签到的形式与好友分享兴趣点（Point of Interest，POI）。基于LBSN的兴趣点推荐能够向用户推荐一些未曾访问过但是可能感兴趣的兴趣点，有效的使用户对城市有进一步了解，增强用户体验，同时促进商业发展，意义重大。
随着用户的参与度的提高，用户数量及签到地点的数量巨大，个性化的推荐技术在不同应用领域也受到了工业界和学术界的广泛关注[1]。但是，这些大规模用户数量和各种信息为用户了解身边的事物带来方便的的同时也给用户带来了困扰。面对如此巨大的信息量，用户的选择就有些迟疑，用户所期待的是能智能地通过其自身的位置信息感知周围环境向其进行个性化推荐服务。LBSN包含了用户和其签到的兴趣点相关信息，但是由于兴趣点数量巨大，同时每个用户访问的兴趣点个数十分有限，所以用户、兴趣点之间的签到矩阵极度稀疏，给兴趣点推荐带来了新的挑战。但是，根据学者相关研究，用户签到位置呈现区域化，其活动范围受空间和社会关系等的影响具有一定的规律性。
根据以上问题及其研究，本文提出了一种基于用户活动区域划分的元路径兴趣点推荐算法。首先根据用户签到信息呈现的区域化对用户签到的兴趣点进行区域化划分为经常活动区域和不经常活动区域；然后定义区域节点，构建用户-活动区域、活动区域-兴趣点的异构网络模型；最后引入元路径，计算用户到兴趣点之间的关联度得到元路径特征值，计算用户到候选兴趣点的签到概率生成推荐列表。实验表明，本文提出的推荐算法有较好的推荐效果，在提高推荐精确度的同时对数据稀疏性有一定的缓解。
1 相关工作
随着位置感知技术和基于位置的社会化网络的兴起与发展，为用户提供网络社交与共享平台的同时，也能够及时记录用户位置签到信息，这为定量研究移动个体活动在时间、空间特征及社会关系的关联性上提供了大量的数据，逐渐引起学者们的关注[2]，推荐技术发展到今天已经取得了不少成果。CHO等人[3]把用户分成近距离好友、远距离好友和其他用户，然后利用协同过滤的推荐算法实现对用户的近距离与远距离的好友信息相结合来进行推荐。ZHENG等人[4]运用协同过滤的思想进行兴趣点推荐。YE等人[5]结合用户偏好、社交关系和兴趣点地理位置三方面因素，综合基于用户的协同过滤推荐、基于好友的协同过滤推荐和基于地理位置的推荐的混合协同过滤推荐算法。
以上研究整体来说就是基于用户的历史签到信息，分析用户偏好、社交关系等，运用协同过滤的思想来设计推荐算法，而有研究人员结合上下文信息构建推荐模型。高榕等人[6]在已有的基于矩阵分解的基础上融合关于兴趣点的评论信息、用户社交关联和地理信息这3个因素进行兴趣点推荐。陈志雄等人[7]针对现有社交网络兴趣点推荐的研究工作主要集中在挖掘兴趣点的情景信息而对用户偏好的影响尚未充分研究的问题，提出一种融合用户偏好、时间信息、地理位置和评论信息的模型来进行兴趣点推荐。CHENG等人[8]将用户社交关系和地理位置融入概率矩阵分解模型，通过建立用户在位置上的签到概率模型作为多中心高斯模型来捕获地理影响力，继而吧社交信息和地理信息融入到一个广义的矩阵分解模型中。
有学者对用户的签到信息进行分析，发现用户的签到位置呈现周期性和区域化[9]，这主要与他们在社交网络中好友关系有关。PELECHRINIS等人[10]对大量移动个体用户的活动进行分析，发现两个个体的活动相似性与他们社会网络中近邻存在较强的关联性，进一步研究发现个体移动活动、社交关系和链路预测彼此影响。
2 基于用户活动区域划分的元路径兴趣点推荐
2.1 用户活动区域划分
我们每天生活在一定区域，其位置变化随着时间变化具有一定的随机性，通过对大量用户的位置轨迹追踪研究，这种随机性又表现出规律性，即用户的活动范围较为集中。对LBSN中的每个用户来说，他可以借助于社交网络分享自己感兴趣的位置，并对这些位置做出自己的评价，通过统计这些点评位置的信息，同样也能够反映出一个移动用户活动范围。日常生活中用户一般是以家庭所在地为中心，在一定区域范围内活动。因此可以根据用户点评实体对象的位置信息来确定其活动范围，利用点评对象的区域分布密度来确定用户活动范围，这包括由于其日常周期性行为活动而形成的频繁活动区域和非频繁活动区域。
定义 1. 用户集合：用户 U={ui|i∈[1,n]}表示LBSN中用户的集合，其中n表示用户的个数。集合中每个用户包含用户 ID和一些基本属性（如年龄、性别等）。
定义2. 实体对象集合：LBSN中实体对象的集合用L表示，L={lj| j∈[1,m]},其中m表示LBSN中实体对象的个数。LBSN中的实体对象即用户签到或感兴趣的兴趣点，如商场、餐馆、游泳馆等。每一个实体对象包含其ID、经度、纬度等相关信息。
定义3. 用户活动区域：设在一定活动区域内所有用户签到的兴趣点之间的最大距离和最小距离分别为Dmax和Dmin，两个点评实体间距离大小的中位数设为D. Ru为用户 u的所有点评或签到的实体对象的中心点到最远点评实体的距离，为该用户在这个区域的一个活动范围。若Ru< D，则将该用户的活动范围视为该用户的频繁活动区域；若Ru> D，则以该用户点评或签到的中心点为圆心，D为半径的一个范围视为该用户的频繁活动区域，而将Ru- D的范围视为该用户的非频繁活动区域。
2.2 元路径集的确定
2.2.1 元路径
元路径主要用来描述异构网络中任意两个节点间的不同路径类型[11]。对于LBSN中两个节点之间的连接路径可以是不同长度，不同类型。节点间不同的路径类型和路径长度所代表的物理意义和体现的节点间关联程度都是不同的。
定义 5. 实例路径：设存在真实路径 p=[a1, a2，…an]，ai为LBSN中节点。对任意i，节点ai的类型为 Ai， ai和 ai+1之间的关系类型为 Ri，则路径p称为元路径的一条实例路径，所有这样的真实路径称为元路径P的实例路径集P′。
2.2.2 用户活动区域图模型构建
LBSN是一种异构网络，主要由用户和实体对象节点组成，用户和用户之间、实体对象和实体对象之间存在一定的关系，用户和实体对象之间主要表现为签到行为。如图1表示的LBSN结构图。
而在本文定义3中定义了频繁活动区域和非频繁活动区域，用户、实体对象（兴趣点）、位置信息是LBSN相关服务中三个基本对象。本文提出的算法中引入新的节点 R，用来表示活动区域。用户在一定区域内的签到数据可以分为在频繁活动区域的签到和在非频繁活动区域的签到。在引入新的区域节点R之后，利用用户和活动区域的关系将签到行为构建二分图
图1 LBSN 结构图Fig. 1 LBSN structure diagram
图2 LBSN 结构图模型Fig.2 LBSN structure diagram model
2.2.3 LBSN中元路径集的确定
由图2可知，用户签到的兴趣点一部分来自其频繁活动区域，一部分来至非频繁活动区域，通过活动区域节点将二者连接起来。图2中用户u1和u2在频繁活动区域内都对l4兴趣点有过签到，则可以将l5这个兴趣点推荐给用户u1，其关联的路径为：u1-R11-u2-R21-l5，利用u1和u2之间的关联性，将l5推荐给用户 u1，同理可以将l1和l2推荐给 u2用户，其关联的路径分别为u2-R21-u1-R11-l1、u2-R21-u1- R11-l2。
根据以上描述，归纳出四种路径，U-Ru1-U*-R*1-L、U-Ru1-U*-R*2-L、U-Ru2-U*-R*1-L、U-Ru2-U*-R*2-L（其中U为目标用户，Ru1、Ru2分别为目标用户的频繁活动区域和非频繁活动区域，U*代表与目标用户相关联的用户，R*1、R*2分别为用户U*的频繁活动区域和非频繁活动区域，L为待推荐的兴趣点）。
以上四种路径都是从目标用户到兴趣点的，体现的是目标用户和兴趣点的关联性，将这四种路径作为元路径集。
2.2.4 LBSN中元路径特征值的计算
定义6. 元路径特征值：元路径的特征值体现的是元路径中首末节点之间的一种关联程度，其计算方法由所有实例路径体现的关联程度之和所得。
对于给定的元路径，其实例路径的关联程度为实例路径各边权值之积。设E(P)表示元路径特征值，c(p)表示实例路径p的关联程度，则元路径特征值计算方法如下：
其中，n为元路径P的实例路径数：
在实验过程中首先为实例路径的每条边计算一定的权值，然后根据权值计算实例路径的关联程度。
（1）对于元路径中的用户和活动区域这条边（即U-R边），采用用户在活动区域的签到比例，分别用以代表用户与频繁活动区域、用户与非频繁活动区域边的权值。
（2）对于活动区域与用户边（即 R-U边），采用两个用户的相似性来度量。在元路径U-R-U*中，即采用U和U*两个用户的相似性。由于LBSN中用户签到矩阵极度稀疏，所以当用户只有一个签到兴趣点时采用Jaccard计算这两个用户的相似度，当两个用户签到的兴趣点个数都大于1时，则用余弦相似性计算两个用户的相似度。
（3）对于活动区域和兴趣点边（即 R-L边），本文引用一个关注度来衡量用 (,)con u l表示用户u对兴趣点l的关注度，其计算公式如下：
其中， (,)N u l表示用户u在兴趣点l处的签到次数， ()N u为用户签到的总次数， ()N U 为所有的签到用户数， ()N l为在兴趣点l签到的用户数。如果一个用户在某个兴趣点的签到次数高于其他用户，则可以认为这个用户对这兴趣点的关注度较其他用户高。由公式（3）可以看出若一个用户频繁访问一个兴趣点，但是这个兴趣点总的来说并不被其他用户频繁访问，则 (,)con u l值就越大，即用户对此兴趣点的关注度较高。
2.3 推荐算法及结果生成
在给定用户以及用户的签到信息，根据特定的元路径，给用户推荐其可能访问的兴趣点，其计算方式为：
根据公式（4），对于给定的用户u，可以计算其对兴趣点l访问的一个概率，再由概率由大到小返回一个推荐列表。
3 实验与分析
3.1 实验数据集
本文采用的数据集为Gowalla公开数据集，此数据集共包括 196585个签到用户，对每个用户包括用户 ID、签到时间、签到兴趣点的经纬度和签到兴趣点的ID。用户签到的总记录为6442892条，以及700000个签到兴趣点，签到矩阵是极度疏松。根据本文提出的算法，对数据进行处理，得到21700个用户，1560352条签到记录，共76956个签到兴趣点。
3.2 评价指标及对比实验
在兴趣点推荐问题中，通常采用准确率（precision）和召回率（recall）来评价算法的优劣。其计算方法如下：
3.3 实验结果与分析
本文提出的基于用户活动区域划分的元路径兴趣点推荐算法（OurMethod）将与基于用户签到记录计算用户相似度的协同推荐方法[5]（User-Based Collaborative Filtering，UBCF）和基于用户共同好友计算用户相似度的协同过滤推荐方法[12]（Friend-Based Collaborative Filtering，FBCF）来进行试验对比和分析。其中，UBCF算法是基于用户签到记录计算用户相似性，再运用传统协同过滤方法进行推荐；FBCF是基于用户共同好友和签到信息计算用户相似性，再运用传统协同过滤算法进行推荐。本文针对同一数据集（Gowalla公开数据集）进行实验，选取推荐列表兴趣点个数分别为 5，10，15，20，25五种情况，就三种推荐算法推荐的准确率和召回率进行对比，其实验对比图如图3、图4所示。
图3 准确率对比图Fig.3 The precision of the comparison chart
图4 召回率对比图Fig.4 The recall of the comparison chart
根据实验的结果，随着推荐兴趣点数量的增加，推荐准确度（precision）逐渐降低，而召回率（recall）逐渐升高，实验结果与实际应有趋势相符。总体看来，本文提出的基于用户活动区域划分的元路径兴趣点推荐算法优于基于用户签到记录计算用户相似度的协同推荐算法和基于用户共同好友计算用户相似度的协同过滤推荐算法，具有更好的推荐效果。
4 总结
在对LBSN的异构网络运用传统的推荐方法进行兴趣点推荐的过程中，因为数据的极度稀疏性或多或少存在一些局限性。本文提出的基于用户活动区域划分的元路径推荐算法。首先，根据用户签到、点评地点呈现区域性，将用户活动区域分为频繁活动区域和不经常活动区域，根据LBSN结构特征构建用户-活动区域、活动区域-兴趣点之间的二分图模型，其次引入元路径，计算从用户到兴趣点的实例路径的关联度，最后根据实例路径关联度计算用户到兴趣点的概率，然后根据概率大小生成推荐列表。结果表明，该算法较传统的推荐算法有更好的准确率和召回率。
本文仍然存在一些不足有待进一步加强，如果考虑上下文信息如时间、天气、交通工具等因素，使得推荐结果更具个性化，达到用户更满意的效果。
[1] ADOMAVICIUS G, TUZHILIN A. Toward the next generation of recommender system: A survey of the state-of-the-art and possible extensions. IEEE Transaction on Knowledge and Data Engineering, 2005, 17(6): 734-749.
[2] WANG D, PEDRESCHI D, SONG C M, et al. Human mobility social ties and link prediction. In Proc. of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, 2011: 1100-1108.
[3] CHO E, MYERS S A, LESKOVEC J. Friendship and Mobility: user movement in location-based social networks. In Proc.of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, 2011: 1082-1090.
[4] ZHENG Y, XIE X. Learning travel recommendation from user-generated GPS traces. ACM Transaction on Intelligent Systems and Technology(TIST), 2011, 2(1): 2-30.
[5] YE M, YIN P, LEE W C, et al. Exploiting geographical influence for collaborative point-of-interest recommendation//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. Beijing, China, 2011: 325-334.
[6] 高榕, 李晶, 杜博等. 一种融合情景和评论信息的位置社交网络兴趣点推荐模型[J]. 计算机研究与发展, 2016,53(4): 752-763.GAO R, LI J, DU B, et al. An interest point recommendation model for location social network based on scenario and comment information[J]. Journal of Computer Research and Development, 2016, 53(4): 752-763.
[7] 陈志雄, 曾诚, 高榕. 一种基于位置社交网络融合多种情景信息的兴趣点推荐模型[J]. 计算机应用研究, 2017,34(10).CHEN Z X, ZENG C, GAO R. An interest point recommendation model based on location social network fusing multiple situational information[J]. Application Research of Computers, 2017, 34(10).
[8] CHENG C, YANG H Q, KING I, et al. Fused matrix factorization with geographical and social influence in location-based networks[C]//Proc of the 26th AAAI conf on Artificial Intelligence(AAAI’12). Menlo Park, CA: AAAI,2012: 211-276.
[9] LI Z, DING B, HAN J, et al. Mining periodic behaviors for moving objects. In proc. of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 2010: 1099-1108.
[10] PELECHRINIS K, KRISHNAMURTHY P. Location Affiliation Networks: Bonding Social and Spatial Information. In Proc. of the 2012 European conference on Machine Learning and Knowledge Discovery in Databases. 2012: 531-547.
[11] SUN Y, HAN J, YAN X, et al. Pathsim: Meta path-based top-k similarity search in heterogeneous information networks. Proceedings of the VLDB(Very Large Data Base)Endowment, 2011, 4(11): 235-246
[12] MA H, KING I, LYU M R. Learning to recommendation with social trust ensemble. SIGIR, 2009: 189-196.
Recommendation of Meta Path Interest Points Based on Active Region Partition in LBSN
XU Ze-feng1, LIU Wen-ju2, WANG Ze2
(School of Computer Science and Software Technology, Tianjin Polytechnic University, Tianjin, 300387, China)
Location Based Social network (Location -based Social Networks, LBSN) recommended related services more and more, and the Point Of Interest (Point Of Interest, POI) is recommended as a personalized recommendation in LBSN related services also, much attention has been paid more and more scholars research on. At present, all kinds of location based recommendation algorithm emerge in endlessly, but due to data in LBSN extremely sparse, caused many recommended precision is not high, this paper proposes a meta-path recommendation algorithm based on user activity area partition. First of all, according to the users to sign in and comment on the location of the present regional, frequent user activity area can be divided into active area and not often activity area,according to the characters of LBSN structure building user interest points-activity area and activity area - the dichotomy between graph model, then introduce meta-path, calculated from the user to an instance of an interest point path correlation degree, according to the size of the correlation generated recommended list. The results show that this algorithm has better recommendation effect than traditional LBSN recommendation algorithm.
Location based social network; Division; meta-path; Point of interest recommend
TP389.1
A
10.3969/j.issn.1003-6970.2017.11.017
本文著录格式：徐泽锋，刘文菊，王赜. LBSN中基于活动区域划分的元路径兴趣点推荐[J]. 软件，2017，38（11）：85-89
徐泽锋，男，硕士研究生，主要研究方向：推荐系统； 刘文菊，女，教授，主要研究方向：企业信息化、计算机网络与安全；王赜，男，教授，主要研究方向：计算机网络与安全、互联网+应用、云网络安全。
刘文菊，女，教授，主要研究方向：企业信息化、计算机网络与安全。
