一种基于位置和时间信息的兴趣点推荐方法

谭 伟,贾朝龙,桑春艳

(重庆邮电大学 软件工程学院,重庆 400065)

在当今信息化时代,随着互联网技术和定位技术的飞速发展以及社会经济的快速发展,人们选择出行的方式以出行的地点越来越广泛。人们的兴趣点(POI,point of interest)如:旅游景点、电影院、博物馆、餐厅等也不断增加,然而,面对大量的POIs,人们如何根据个人喜好快速选择与自己兴趣相关的兴趣点成为了用户的一个难题。基于这样的环境下,基于位置的社交化网络(LBSNs,location-based social networks)推荐技术及其相关的应用服务应运而生,目前比较流行的LBSNs有Foursquare、Gowalla、Geo Life、微信朋友圈等[1]。

在基于位置的社交网络(LBSNs)中,鼓励用户分享自己每天的信息,如:行程信息、位置信息、POI签到信息以及其它的相关信息[2]。用户访问过的POIs的相关信息(如签到时间、经纬度、日期等)可以通过显示和隐式的方式同时获得,即用户到达一个POI之后的签到行为和手机的自动定位功能,而这些信息又可以被其好友(其他用户)共享[3]。使用用户以及POIs的相关信息,就能够对用户推荐用户未曾访问过的POIs。而协同过滤是推荐系统比较流行的方法,协同过滤主要是通过不同的用户对项目的评分以及用户或项目之间的相似度来给用户推荐项目[4]。

笔者提出一种根据位置和时间信息的POI推荐方法。根据用户的历史出行地点的签到信息数据,通过分析地点签到信息的地理信息,使用出行地点签到时间及签到数量来计算POI的流行度,最后根据综合分析POIs地理信息和流行度来向用户推荐用户未曾访问过的POIs。研究得:

1)研究使用POIs的位置信息(经度、纬度)计算POIs之间的距离,然后根据距离信息计算POIs之间的相似度,距离越远相似度越低。

2)使用POIs在不同时间被签到的数量来计算POIs的流行度,将一天划分为不同的时间段,分别计算POIs在每个时间段被签到的数量,数量越大表示该POIs在该时间点的流行度越高,最后根据POIs在各个不同时间点的流行度计算POIs之间的相似度。

3)根据位置和时间信息融合1)、2)中计算出的POIs之间的相似度,最终计算出不同POIs的整体相似度来向用户推荐新的POIs,并且分析了不同占比对实验结果的影响效果。

1 相关工作

基于位置信息的推荐方法,基于时间信息的推荐方法和基于位置时间信息的推荐方法。

1)基于位置信息的推荐方法。在LBSNs中,用户和POIs的位置信息对于兴趣点推荐是一个比较重要的因素,因为用户更加倾向于访问离自己比较近的POIs。文献[5-7]使用幂律分布函数计算用户从当前POI访问下一POI的概率;文献[8-10]使用高斯分布函数计算用户从当前POI访问下一POI的概率;文献[11-13]使用核密度估计来建模地理位置影响。

2)基于时间信息的推荐方法。时间信息对于POI推荐来说是一个非常重要的因素,因为用户出行地点是根据时间的变化而改变的。文献[14-16]都是使用时间信息将一天分为24 h或者上午、下午、晚上、傍晚等,然后使用协同过滤相关的一些推荐方法产生POIs推荐。文献[17]从POIs的角度出发,使用时间信息将一天均等分为12份,即12个时间戳,统计所有POIs在不同时间戳的被签到的次数,然后以向量的方式表示每个POI,使用时间信息以向量的方式计算POIs之间的相似度,最后以Top-N的方式产生推荐。文献[18]从用户的角度出发,在基于用户的协同过滤(User-based collaborative filtering)的基础上,使用改进后的余弦相似度计算POIs的相似度。首先使用K-means算法将所有用户分为活跃用户和不活跃用户,对于活跃用户,根据用户在一天24 h(均等分为24个时间戳)的签到情况产生POIs推荐;对于不活跃用户,根据用户在一天中的签到情况产生POIs推荐。

3)基于位置时间信息的推荐方法。现有的一些方法从用户的角度出发,使用位置和时间信息综合分析产生POIs推荐。文献[6]从用户的角度出发,在基于用户的协同过滤的基础上进行改进,依次融入POIs在不同时间是否有被签到记录以及位置信息后计算兴趣点的评分,最后以Top-N的方式向目标用户推荐新的POIs。文献[19]从用户的角度出发,根据用户的历史签到情况采用模糊C均值(Fuzzy C-means)算法将用户分为活跃用户和不活跃用户,对于活跃用户,根据用户在一天中不同时间的签到记录,提出二维(POIs的经纬度)高斯核密度估计算法计算相似度产生POIs推荐;对于不活跃用户,使用一维(POIs之间的距离)幂律分布函数的方式计算相似度产生推荐。

2 基于位置和时间信息的兴趣点推荐方法

2.1 问题描述

主要研究的问题是从POIs的角度出发分为3个步骤,首先,使用POIs的位置信息(经度和纬度)计算用户历史访问和未曾访问过的地点的相似度;然后,使用时间信息统计POIs在一天内不同时间段被签到的次数,以向量的形式表示每个POIs,计算用户历史访问和未曾访问过的地点的相似度;最后使用位置和时间信息综合分析计算整体相似度,即估算出目标用户对未曾访问过的POIs的访问概率,进而对目标用户进行POIs推荐。

假设U={u1,u2,…,un}为用户集合,L={l1,l2,…,ln}为POIs集合。使用位置和时间信息计算出目标用户u可能访问所有未曾访问过的POIs的概率,以Top-N的方式向目标用户u进行POIs推荐。

2.2 使用位置信息进行相似度建模

在社交网络中,地理信息是一个比较重要的因素。在现实生活中,相对于较远的兴趣点,人们往往会更加倾向于选择访问离自己位置更近的兴趣点,如图1所示,图1展示了Foursquare数据集中兴趣点的位置信息分布情况,从图1中可以看出兴趣点分布在很多区域,大部分数据都集中在分布在几个比较集中的群集里面,这说明人们更加倾向于访问距离比较近的兴趣点。所以将地理位置信息融入到的兴趣点推荐方法中,在单考虑地理位置信息影响时,用户访问下一个兴趣点的概率与用户所在兴趣点和下一个兴趣点之间的距离成反比,即距离越远用户访问的概率越小,用公式(1)计算用户访问下一兴趣点的概率。

图1 Foursquare数据集中兴趣点分布情况Fig.1 Distribution of interest points in foursquare dataset

2.3 融入时间信息进行相似度建模

在现实社会中,人们在不同的时间点会根据实际的情况访问不同的地方,如图2所示,图2展示了Foursquare数据集中2个随机POIs在一天24 h各个不同时间地点被用户签到的次数,从图2中可以看出:兴趣点L1在8～12 h和13～17 h这2个时间段被签到频率比较高,这说明L1可能是某办公地点,因为在现实生活中这个时间段为上班时间;兴趣点L2在10～12 h和18～20 h这2个时间段被签到的频率比较高,其中18～20 h这个时间段的频率最高,这说明L2可能是某娱乐场所。

图2 Foursquare 2个兴趣点签到分布Fig.2 Foursquare sign in distribution of 2 interest points

通过上述分析以及考虑到在实际中用户的签到行为,将用户的签到时间按照不同的时间段进行分段处理,统计在不同时间段兴趣点被用户签到的次数。从图2可以看出,兴趣点在白天的被签到的次数往往较多,而在深夜以及凌晨时间段的被签到的次数较少,因此将1天24 h进行不同时间段的划分,如表1所示。然后统计每个POI在不同时间段被签到的次数,以矩阵的形式表示所有POIs在不同时间段被签到的情况,如表2所示。

表1 时间段划分Table 1 Time period division

表2 POIs时间矩阵Table 2 POIs time matrix

为了得到更好的推荐效果,将上述矩阵数据进行标准缩放,常用的标准缩放有归一化和标准化处理,由于考虑到采用的数据量比较大(Foursquare数据的兴趣点签到记录有194 108条),而归一化处理容易受到异常点的影响大,其鲁棒性较差,适合传统精确小数据的场景,所以采用标准化的方式处理上述矩阵数据。计算公式如下

经过标准化之后,以向量的形式表示每个兴趣点[17],如公式6,Cv(li)表示兴趣点li在每个时间点的被签到情况。使用时间信息计算兴趣点之间的相似度的计算公式如下

综合考虑兴趣点的位置信息和时间信息,以整体的方式计算兴趣点之间的相似度,计算公式如公式(7)所示,其中α为参数,取值区间为(0,1),表示位置信息和时间信息的不同占比。

在向目标用户推荐新的兴趣点时,将兴趣点划分为用户访问过和用户未曾访问过的2个集合,将用户访问过的集合作为用户的特征集合,统计计算特征集合中所有兴趣点在一天中被签到的次数,选取前k个兴趣点作为用户的特征兴趣点。计算前k个用户访问过的兴趣点与所有用户未曾访问过的兴趣点的相似度,最后以Top-N的方式向目标用户推荐前N个兴趣点集合。

3 实验结果与分析

3.1 实验数据集

实验的数据采用来自真实世界的数据集,这些数据来自于Foursquare真实数据集[6],Foursquare数据集采集的是2010年8月到2011年7月用户在新加坡的签到数据,数据中一共包括2 321名用户,5 596个签到兴趣点以及194 108条签到记录。Foursquare数据集信息含有用户ID、兴趣点ID、兴趣点的经度和纬度以及用户在兴趣点的签到时间。数据集的相关内容如表2所示。

表2 实验数据集Table 2 Experimental data set

3.2 评估方法

准确率(Precision)和召回率(Recall)是TOP-N推荐的重要评价指标,故采用准确率和回归率来评估提出的推荐算法的性能,对目标用户u推荐结果的准确率和召回率计算公式如下

其中:Pu@n表示向目标用户u推荐前N个兴趣点时的准确率;Ru@n表示向目标用户u推荐前N个兴趣点时的召回率;TPu表示向目标用户u推荐正确的兴趣点的数量;FPu表示向目标用户u推荐错误的兴趣点的数量;FNu表示向目标用户u没有推荐到的兴趣点的数量。

整体的准确率和召回率计算公式如下

其中:Pall表示最终推荐算法的准确率;Rall表示最终推荐算法的召回率;表示在训练集和测试集中都存在的用户的数量。

3.3 实验结果分析

3.3.1 使用位置信息推荐效果

在实验中,设置用户的访问过的兴趣点的特征兴趣点数量k为k={1,2,3,4,5,6,7},产生的兴趣点推荐数量N为N={10,20,30},实验结果的准确率和召回率如图3和图4所示。

图3 不同k值和N值的准确率Fig.3 Accuracy of different K and N values

图4 不同k值和N值的召回率Fig.4 Recall rates for different K and N values

从实验结果中可以看出,兴趣点推荐数量固定不变时,当k取值在1～6时,推荐结果的准确率和召回率基本上都是随着k的增加而增加,但当k取值从6调整到7时,实验结果的准确率和召回率基本都有所下降,k取值为6时,产生的推荐效果比较好;k固定不变时,实验结果的准确率随着兴趣点推荐数量的增加而下降,实验结果的召回率随着兴趣点推荐数量的增加而增加。

3.3.2 加入时间因素后推荐效果

在实验中,设置用户的访问过的兴趣点的特征兴趣点数量k为6,产生的兴趣点推荐数量N为N={10,20,30},实验结果的准确率和召回率如图5和图6所示。

图5 不同α值的准确率Fig.5 DifferentαAccuracy of values

图6 不同α值的召回率Fig.6 DifferentαRecall rate of values

从实验结果中可以看出,兴趣点推荐数量为10时,α的取值为0.1时,实验结果的准确率较高;兴趣点推荐数量为20时,α的取值为0.1和0.9时,实验结果的准确率较高;兴趣点推荐数量为30时,α的取值为0.1和0.9时,实验结果的准确率较高。综合考虑准确率召回率以及兴趣点推荐数量,当α的取值为0.1时实验结果的效果比较好。

3.3.3 基于位置信息和融入时间信息后的比较

为了验证融入时间信息后的效果比未融入时间信息的效果即仅使用位置信息好,综合考虑了不同情况下的选取用户不同特征兴趣点数量和进行不同数目的推荐兴趣点的准确率和召回率,采取平均值的方式,即不同情况下的平均准确率和平均召回率,将两种方式进行了实验对比。LB表示仅使用位置信息的建模,LTB表示融入时间信息后的建模。实验对比结果如图7和图8所示:

图7 是否融入时间信息的准确率对比Fig.7 Whether to integrate the accuracy comparison of time information

图8 是否融入时间信息的召回率对比Fig.8 Recall rate comparison whether time information is integrated

从对比实验结果中可以看出,无论是准确率和召回率,在融入时间信息后的效果都要比仅使用位置信息的效果好,这说明在使用位置信息的建模中融入时间信息后进行建模效果更佳。在准确率上,推荐的兴趣点为Top-10时,融入时间信息后准确率提高了0.6%,推荐兴趣点为Top-20和Top-30时,融入时间信息后准确率提高了0.1%;在召回率上,推荐兴趣点为Top-10、Top-20和Top-30时,融入时间信息后召回率平均提高了0.1%。从而说明提出的基于位置和时间信息的兴趣点推荐方法是有效的。

4 结束语

基于兴趣点的位置和时间信息,提出了一种基于位置和时间信息的兴趣点推荐方法。从兴趣点的角度出发,综合分析兴趣点的位置信息和兴趣点在一天中不同时间段被签到的情况,使用这些信息计算兴趣点之间的相似度,以Top-N的方式向目标用户推荐新的兴趣点集合,实验结果表明,研究提出的方法是有效的。在未来的工作中,考虑融入更多有关用户和兴趣点的信息以得到更好的推荐效果,如用户的朋友和社交关系以及兴趣点的类别和评论信息等。