基于区域活跃用户的好友推荐和位置推荐算法

董立岩, 王雪松, 王朝阳, 李永丽

(1. 吉林大学 计算机科学与技术学院, 长春 130012； 2. 东北师范大学 信息科学与技术学院, 长春 130117)

定位技术使用户可随时通过移动便携互联网设备分享其活动的地理位置, 使基于位置的社交网络[1-2]推荐成为目前该领域的研究热点, 其中包括基于好友用户的推荐[3-4]和基于专家用户的推荐[5]等.

社交网络中好友的推荐研究目前已有很多结果[6-12]. Wu等[9]将在线友谊信息和离线用户行为考虑到好友推荐中, 采用Markov链基于位置聚类和阈值评估的余弦相似理论方法进行推荐; Lin等[10]提出了一种基于3种传统朋友关系的线性框架提高推荐的准确性.

专家用户即为在社交网络中拥有较大影响力的用户. 专家用户拥有丰富的经验, 可给出相对普通用户更准确的评价, 专家用户更易获取其他用户的信任, 专家用户签到的位置也更值得推荐. 但专家用户的寻找范围可能相对过大, 传统算法中专家用户的范围一般为全国范围内, 这样的范围对于普通用户不具有普遍性. 普通用户的活动可能只集中在10 km或5 km为直径的范围内, 距离因素对推荐具有重要影响[6]. 本文提出一种基于区域活跃用户的推荐算法, 将区域活跃用户作为推荐标准, 为普通用户推荐, 更符合用户的要求.

1 区域活跃用户定义

本文推荐算法使用区域活跃用户(一种专家用户)作为推荐标准. 通过专家用户的位置信息和时间信息, 先计算给定区域内的区域活跃用户, 再将得到的区域活跃用户推荐给普通用户, 同时计算用户间的相似度为目标用户进行好友推荐. 获取区域活跃用户后, 根据区域活跃用户的签到记录, 为用户推荐价值高的位置.

1.1 区域活跃用户度量标准

区域活跃用户是指在特定区域内社交活动频繁、 签到频率高并频繁分享个人体验的专家用户. 区域活跃用户在一定程度上对该区域的兴趣点及项目了解程度较高, 相应排名靠前. 用户的活跃程度评判标准根据用户的签到数据衡量, 主要分为两方面： 1) 用户在区域内的签到地点数目[7], 若用户在特定区域内的签到较少, 则一定程度上可认定该用户为非区域活跃用户, 且推荐价值较低； 2) 用户的总签到次数, 部分用户进行特定活动时, 签到地点可能会很多, 但总签到次数少, 这种情况可认定用户为非区域活跃用户. 签到数据体现了用户在社交网络中的活跃程度, 签到地点和数量多说明用户在特定区域活跃度高, 其推荐价值高. 故本文采用用户签到数据中的签到地点数目和签到总次数两个标准对用户进行评审, 判断其是否为区域活跃用户[8].

1.2 区域活跃用户计算过程

本文根据签到数据集, 通过用户签到地点数和用户的签到总次数进行区域活跃用户计算, 步骤如下:

1) 获取用户当前位置, 并以用户签到地点的经度和纬度进行位置展示, 根据用户当前位置确定需要进行计算的区域. 获取以用户位置为圆心、R为半径圆的范围内所有签到数据. 将得到的区域数据集记为RDS(region data set). 该步骤确定区域, 并获取区域内的所有签到数据.

2) 根据步骤1)获得的部分签到数据集, 对数据集中的每个用户进行签到地点数的计算, 以获得用户在该区域内进行过签到的所有地点, 计算公式为

(1)

其中：L表示地点集合,L∈RDS;cu,i表示用户u在地点i的签到记录;I为指示函数, 若用户在i位置有签到记录, 则I=1, 否则I=0. 最后得到在区域内用户签到地点数的集合.

3) 根据步骤1)获得的部分签到数据集, 计算数据集中每个用户在该区域内的签到总次数. 计算区域内每个用户在区域地点签到次数的总和, 计算公式为

(2)

其中:L表示地点集合,L∈RDS;cu,j表示用户u在地点i的签到记录, 用户的所有签到记录全部计算. 在该过程中根据用户所在区域的签到总次数进行排序, 得到每个用户在区域L内的签到总次数. 计算结果反应了用户对区域了解的广度.

4) 将上述步骤中得到的基于签到地点数的用户排序与基于签到总数的用户排序, 分别选取top-N签到地点数的用户和top-N签到总数的用户, 求得两个用户集的交集, 得到区域活跃用户集, 根据区域活跃用户集进行推荐. 这里定义区域活跃用户集为raus(regional active user set).

2 基于区域活跃用户的推荐方法

2.1 用户的好友推荐方法

若用户在所属社交网络中属于新用户, 则可将对于区域了解程度最高的专家用户推荐给新用户, 而这些区域了解程度高的专家用户即为本文提出的区域活跃用户. 根据计算得到的区域活跃用户集raus, 将集合用户中的top-N活跃用户推荐给目标用户. 而该top-N活跃用户的选取方式也分为基于用户总签到数和用户签到地点数两种.

若用户在所属社交网络中为老用户, 则该用户有一定的签到记录, 在为老用户进行好友推荐时, 此时用户的签到信息在一定程度上也反映了用户的喜好[13-14]. 本文根据计算区域活跃用户与目标用户之间的相似度进行度量, 通过签到位置的相似度判断是否进行好友推荐, 若两个用户在区域内具有较多共同的签到记录, 则表明用户的相似度高, 相似度计算公式为

(3)

2.2 基于区域活跃用户的位置推荐

位置推荐[15]分为两种形式: 1) 用户签到数据少甚至无数据, 此时属于冷启动类型[16], 将区域活跃用户签到频繁的位置推荐给用户； 2) 对具有一定签到数据的用户进行推荐, 通过计算用户之间的相似度[17], 寻找出与用户相似度最高的区域活跃用户, 将该区域活跃用户签到过但目标用户未进行签到的地点推荐给目标用户. 在位置推荐时, 推荐的衡量标准也分为两种： 基于位置的被签到总次数和基于位置的被签到总人次.

基于区域活跃用户签到数推荐方法的计算公式为

(4)

其中：Uraus表示区域活跃用户集；L∈RDS;cu,i表示用户u在位置i的签到记录. 计算在选定区域内, 所有区域活跃用户在需要进行推荐位置的签到总数. 基于区域活跃用户签到人次推荐方法的计算公式为

(5)

对于不同的目标用户, 其衡量接受推荐的标准可能不同, 被签到次数与总签到人次均可作为标准. 综合考虑两种标准得到综合推荐方法, 记为

raus(uk,li)=α·rauscc(uk,li)+(1-α)·rauslc(uk,li).

(6)

时间因素[18]对推荐的准确性具有重要影响. 加入时间因素, 只考虑签到时间与用户当前时间差值在一定范围内的签到, 若超出该时间差值范围, 则将不考虑该签到记录. 加入时间因素基于位置被签到总数推荐方法的计算公式为

(7)

其中：t表示用户进行推荐的时间；tu表示数据集中用户的签到时间, 本文假设该时间的选择只考虑24 h内的时间划分.

同理, 加入时间因素基于位置被签到人次推荐方法的计算公式为

(8)

最终得到加入时间因素的综合推荐算法为

raus(uk,li)=α·rauscct(uk,li)+(1-α)·rauslct(uk,li).

(9)

3 实 验

3.1 实验数据

本文的数据集源于Gowalla数据集, 收集了用户在2009-02--2010-10期间的签到数据, 包含6 442 890条签到数据, 其中有196 591个节点, 950 327条边. 节点表示用户, 边表示用户之间的好友关系. Gowalla数据集中包含两个文本文件： Gowalla_edges.txt和Gowalla_totalCheckins.txt. 其中Gowalla_edges.txt文件中记录了用户的好友关系, Gowalla_totalCheckins.txt文件中记录了用户的签到信息.

3.2 实验结果与分析

实验通过给定用户的经度和纬度及选定区域的半径大小获取该区域内的推荐位置, 选取

lat=30.255 730 992 7, lon=-97.763 385 772 7

为用户当前位置, 设定不同区域半径R. 当R=10 000时, 得到了基于位置签到总数的推荐概率排名前20的位置以及基于位置签到人次的推荐概率排名前20的位置, 结果分别列于表1和表2.

表1 基于位置被签到总次数的推荐概率Table 1 Recommendation probability based on total number of places checked in

表2 基于地点被签到总人次的推荐概率Table 2 Recommendation probability of total number of people based on location checked in

由表1可见, 位置ID为420315的位置被签到次数最多. 由表2可见, 位置ID为9241的签到总人次数最多. 两种不同推荐结果表明, 不同的推荐方式得到的推荐结果不相同. 设α=0.4, 由式(9)可得列于表3的最终推荐结果.

表3 综合推荐概率Table 3 Comprehensive recommendation probability

图1 不同N值的精确率比较Fig.1 Comparison of precision rates with different N values

由表3可见, 当同时考虑位置的被签到总次数和签到人次时, 得到的推荐结果与只考虑某一条件的实验结果存在较大差异, 证明了本文提出综合考虑两个因素的正确性, 当α=0.4时, 推荐结果较好.

下面将本文推荐方法与目前已有经典的位置推荐算法进行比较, 以证明本文算法的有效性. 不同算法的实验对比结果如图1～图3所示. 进行比较的算法如下：

1) USG算法[19], 基于用户偏好、 社会关系、 地理位置的推荐算法, 是目前被广泛应用的推荐方法；

2) UP算法, 根据用户历史签到数据中获取用户爱好的推荐算法;

3) FB算法, 基于社会关系的推荐算法.

图2 不同N值的召回率比较Fig.2 Comparison of recall rates with different N values

图3 不同N值的F-measure值比较Fig.3 Comparison of F-measure values with different N values

由图1～图3可见, 本文提出的基于区域活跃用户的位置推荐算法相比于其他传统推荐算法的精确率、 召回率和F-measure值均有一定的提高.

综上所述, 本文提出了一种新的推荐机制——基于区域活跃用户的推荐方法, 根据用户的位置信息和时间信息进行位置推荐及好友推荐使推荐更具实时性. 首先考虑用户寻求推荐所在位置, 计算出该区域中的活跃用户, 然后将这些活跃用户推荐给其他用户, 可最大程度地完成相应推荐. 在基于区域活跃用户的基础上, 添加时间因素. 推荐标准变为基于签到总次数与基于签到总人数相融合. 两种标准在深度和广度上进行推荐, 可选择相应权重决定对应标准所占百分数. 最后在真实签到数据集Gowall上进行实验. 实验结果表明, 本文提出的将位置的被签到总次数与位置的被签到人次相融合更合理, 同时算法在准确率、 召回率、F-measure值上均有一定提高.