常晓雨，余正生

(杭州电子科技大学计算机学院，浙江 杭州 310018)



引入时间衰减项的兴趣点推荐算法

常晓雨，余正生

(杭州电子科技大学计算机学院，浙江 杭州 310018)

摘要：兴趣点推荐已成为帮助人们发现感兴趣点的重要手段，传统推荐算法仅仅对固定时间段内的兴趣点做推荐，而没有考虑兴趣点推荐存在时间上的衰减现象.为了进一步提高兴趣点推荐算法的性能，总结了传统基于兴趣点相似度的协同过滤推荐算法，设计了表现更优异的改进算法——引入时间衰减项的兴趣点推荐算法.实际数据集上的测试结果表明，改进算法在精准度、召回率和F指标等方面比传统基于兴趣点相似度的协同过滤推荐算法有更好的表现.

关键词：兴趣点推荐；协同过滤；时间衰减项；推荐算法

0引言

随着智能手机的普及和定位技术的发展，人们更容易获得自己位置的实时信息，从而促使了基于位置的社交网络的出现，例如大众点评，Foursquare，Jiepang等[1-3].基于位置的社交网络中包含了用户对兴趣点访问的时间信息，为人们在推荐算法中考虑时间衰减性提供了便利.例如，文献[4]对固定时间段内的兴趣点做推荐，但没有考虑兴趣点推荐存在时间上的衰减现象，因此这种算法并不适用于对整个时间轴上的兴趣点做推荐.在兴趣点推荐中，用户访问时间间隔越短的兴趣点之间的相似度越高，在推荐算法中的权重越大.为了进一步挖掘兴趣点推荐中的时间特性，本文提出了一种引入时间衰减项的兴趣点推荐算法，它不仅适用于固定时间段内的兴趣点，还可以对整个时间轴上的兴趣点做推荐.

1相似度求解公式

1)余弦相似度.在余弦相似度求解公式中，通过兴趣点评分向量之间的夹角余弦来度量它们之间的相似度.兴趣点i，j的余弦相似度如下：

(1)

2)修正余弦相似度.在余弦相似度基础上进行了改进，通过减去用户对兴趣点的平均评分解决了余弦相似度没有考虑用户评分等级差异的问题.兴趣点i，j的修正余弦相似度如下：

(2)

3)皮尔逊相关系数相似度.与修正余弦相似度一样，它也解决了用户评分等级差异的问题.兴趣点i，j的皮尔逊相关系数相似度如下：

(3)

2引入时间衰减项的兴趣点推荐算法

就统计意义上来说，用户访问时间相隔越短的兴趣点之间相似度越高，在推荐算法中的权重越大.实验中引入适合本文数据集应用场景的时间衰减函数如下：

f(|tui-tuj|)=Qt+e-Nt|tui-tuj|,i,j∈G,t∈T.

(4)

式中，Qt，Nt(Qt，Nt>0)为时间衰减参数，取值与特定系统相关，G为兴趣点的集合，T为用户访问兴趣点的时间集合.分别在3.3节实验1和实验3中对Qt和Nt取值进行了测试.

通过引入时间衰减函数式(4)得到改进后的兴趣点相似度求解公式如下：

wtime(i,j)=w(i,j)f(|tui-tuj|).

(5)

式中，w(i,j)表示通过传统兴趣点相似度求解公式得到的兴趣点i和j之间的相似度.

用户u对兴趣点i的评分预测公式如下[7]:

(6)

3仿真实验

3.1实验数据集

本文抓取了大众点评中杭州下沙地区用户从2012-06-10到2015-06-10的签到数据，如表1所示.

表1　杭州下沙地区用户签到数据集

表1中，u代表用户的编号，1≤u≤m，m为收集的用户总数；i代表兴趣点的编号，1≤i≤n，n为兴趣点总数；rui代表用户u对兴趣点i的最近一次评分值，tui代表用户u对兴趣点i的最近一次签到时间.

本文共抓取到1 276 683条签到数据，通过以下步骤给用户u推荐预测评分值最大的N个兴趣点：

1)随机选取1/8的签到兴趣点作为测试集，剩余7/8的签到兴趣点作为训练集；

2)通过式(5)计算出各个兴趣点之间的相似度，得到兴趣点相似度矩阵；

3)将兴趣点相似度矩阵中的数据按降序排列，得到排序好的兴趣点相似度矩阵；

4)利用评分预测式(6)，预测出用户u对测试集中各个兴趣点的预测评分；

5)将预测评分值最大的N个兴趣点推荐给用户u.

3.2算法评价指标

R(u)表示用户u推荐的N个兴趣点的集合，T(u)表示用户u实际感兴趣的兴趣点集合，则召回率(Recall，记为PRecall)、精准度(Precision，记为PPrecision)和F指标(F-Measure，记为F)[8]分别如下所示：

(7)

(8)

(9)

召回率描述的是在用户实际感兴趣的兴趣点当中被推荐的比例，精准度描述的是推荐列表当中用户实际感兴趣的兴趣点所占的比例，但这2个指标经常出现相互矛盾的情况，往往1个指标增大的同时另1个指标随之减小，为了综合考虑召回率和精准度，实验中还用到了综合评价指标F指标.

3.3仿真实验与分析

实验中的数据来源于大众点评网，将这些数据运用于兴趣点推荐是本文的数据集应用场景.

实验1用户对兴趣点的平均回访率与时间跨度的关系.

回访率是用户访问了某个兴趣点相隔一段时间后再次访问这个兴趣点的概率.平均回访率是全体用户回访率的平均值.平均回访率与时间跨度的关系如图1所示，反映出随着时间的增长用户整体对兴趣点的感兴趣程度的变化规律.

图1　平均回访率与时间跨度关系图

由图1可知，在本文数据集应用场景中，平均回访率y与时间跨度x整体呈现出以e为底的指数函数关系，即y=m+e-qx(m,q>0)函数关系.时间跨度在0～420 h之间时，平均回访率随时间跨度变化较大，主要是非常住人口或旅游人员起到比较大的作用.时间跨度为420 h以后平均回访率保持在0.13左右，这部分是常住人口经常访问的兴趣点随时间跨度变化不大.因此在本文数据集应用场景中的引入的时间衰减函数为式(4)，并且Qt取值为0.13.

实验2传统基于兴趣点相似度的协同过滤推荐算法中不同的相似度计算方法的性能表现.

在推荐列表长度N取不同值情况下，对利用式(1)、式(2)、式(3)的3种方法对兴趣点推荐算法的推荐性能进行比较实验，实验结果如图2和图3所示.

图2　不同N时，3种算法的精准度和召回率

图3　不同N时，3种算法的F指标

由图2和图3可知，从精准度、召回率和F指标方面看，余弦算法优于修正余弦算法，修正余弦算法又优于皮尔逊相关系数算法；由图2可知，余弦算法的精准度和召回率相交在7～8之间，表明杭州下沙地区用户每次最有可能访问7～8个兴趣点.

实验3引入时间衰减项的兴趣点推荐算法中时间衰减参数Nt对推荐性能的影响.

根据引入时间衰减项的兴趣点推荐算法中时间衰减参数Nt对推荐性能的影响，取得Nt的最优值如表2所示.

由实验2结论可知，杭州下沙地区用户每次最有可能访问7～8个兴趣点，这里推荐列表长度N值取为8.

表2　推荐列表长度N=8时，不同时间衰减参数Nt下的精准度和召回率

由表2可知，当时间衰减参数Nt逐步减小时精准度和召回率都在逐步增大，当Nt=0.005时精准度和召回率达到最大，本实验场景中时间衰减参数Nt取值为0.005.

实验4对比引入时间衰减项的兴趣点推荐算法与实验2中性能最好的基于兴趣点相似度的协同过滤推荐算法的性能表现.

在推荐列表长度N取不同值情况下，对两种推荐算法的推荐性能进行比较实验，实验结果如图4和图5所示.

时间衰减参数Qt和Nt已经分别在实验1和实验3中得到，这里取它们的最优值.

图4　不同N时，2种算法的精准度和召回率

图5　不同N时，2种算法的F指标

由图4和图5可知，引入时间衰减项的兴趣点推荐算法比传统基于兴趣点相似度的协同过滤推荐算法在精准度、召回率和F指标方面有更好的表现.

4结束语

本文以杭州下沙地区用户签到数据集为实验数据，研究并得到了兴趣点相似度在整个时间段内的时序特征，提出了引入时间衰减项的兴趣点推荐算法.通过一系列测试实验，验证了引入时间衰减项的兴趣点推荐算法比传统基于兴趣点相似度的协同过滤推荐算法有更好的性能表现.但在不同数据集应用场景中时间衰减函数的类型不一定相同，本文没能给出时间衰减函数的一般公式，这将是下一步研究的方向.

参考文献

[1]李敏，王晓聪，张军，等.基于位置的社交网络用户签到及相关行为研究[J].计算机科学，2013，40(10)：72-76.

[2]YANGD,ZHANGD,YUZ,etal.Asentiment-enhancedpersonalizedlocationrecommendationsystem[C]//Proceedingsofthe24thACMConferenceonHypertextandSocialMedia.ACM, 2013: 119-128.

[3]孟祥武，胡勋，王立才，等.移动推荐系统及其应用[J].软件学报，2013，24(1)：91-108.

[4]徐翔俊，聂任灿.基于位置的社会网络中面向时序特征的兴趣点推荐算法[J].计算机应用研究，2015，32(7)：1959-1961.

[5]BOBADILLAJ,ORTEGAF,HERNANDOA,etal.Recommendersystemssurvey[J].Knowledge-BasedSystems, 2013, 46(1): 109-132.

[6]XIANGC,GUISHENGY,LONGZ,etal.Methodofcollaborativefilteringbasedonuncertainuserinterestscluster[J].Journalofcomputers, 2013, 8(1): 186-193.

[7]项亮.推荐系统实践[M].北京：人民邮电出版社，2012：41-64．

[8]HERLOCKERJL,KONSTANJA,TERVEENLG,etal.Evaluatingcollaborativefilteringrecommendersystems[J].ACMTransactionsonInformationSystems(TOIS), 2004, 22(1): 5-53.

DOI：10.13954/j.cnki.hdu.2016.03.009

收稿日期：2015-09-15

基金项目：国家自然科学基金资助项目(61502131)

作者简介：常晓雨(1987-)，男，河南许昌人，硕士研究生，机器学习.通信作者：余正生教授，E-mail：yuzhengsheng@hdu.edu.cn.

中图分类号：TP181

文献标识码：A

文章编号：1001-9146(2016)03-0042-05

Point-of-interest Recommendation Algorithm Introducing Time Attenuation Item

CHANG Xiaoyu, YU Zhengsheng

(SchoolofComputer,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Abstract：Point-of-interest(PoI) recommendation has become an important means to help people find interesting locations. Traditional recommendation algorithms just focus the recommendation on a fixed period of time, without taking account of the attenuation phenomena of time. In order to further improve the performance of the recommendation algorithm, this paper summarizes the traditional collaborative filtering recommendation algorithms based on the similarity of PoI and designs a superior improved algorithm which is the PoI recommendation algorithm introducing time attenuation item. The test results on real datasets show that the improved algorithm performs better than the traditional collaborative filtering recommendation algorithms based on the similarity of PoI in terms of precision, recall rate and F-measure.

Key words：point-of-interest recommendation; collaborative filtering; time attenuation item; recommendation algorithm