融合时间序列的POI动态推荐算法

2020-05-09原福永刘宏阳冯凯东梁顺攀

小型微型计算机系统 2020年2期

原福永，李晨，雷瑜，刘宏阳，冯凯东，梁顺攀

(燕山大学信息科学与工程学院，河北秦皇岛 066004)

1 引言

研究用户偏好的兴趣点，不仅能帮助用户和游客探索之前从未访问过的城市中的潜在兴趣点，而且可以吸引潜在的游客为POI商家带来经济效益.但不同于传统的显式反馈推荐，可以利用用户对物品的评分直接表达用户的直接偏好，隐式反馈是通过用户的签到行为记录挖掘其潜在的偏好，这增加了推荐的复杂性.近些年，利用多种异构类型的上下文信息(例如时间、地理位置、标签、评论信息等)挖掘用户的潜在偏好，为用户生成推荐列表，是兴趣点推荐领域的发展趋势.多种异构信息的结合主要包括以下几个方面.

越来越多的兴趣点推荐模型考虑兴趣点的位置信息.文献[1]提出了两种模型：高斯混合模型(GMM)和基于遗传算法的高斯混合模型(GA-GMM)来捕捉地理影响.文献[2]使用三个因素来模拟两个POI之间的地理影响：POI的地理影响，POI的地理敏感性以及它们的物理距离.文献[3]分析LBSN的用户登记活动中呈现的空间聚类现象而导致的地理影响并基于朴素贝叶斯基于地理影响开发了一种协同推荐算法.文献[4]将用户的登记记录和社会影响力整合在一个组合模型中，形成一个新的框架，效果优于其他算法.

在兴趣点推荐领域，时间在多方面影响着用户的兴趣偏好.Song等人[5]提出一种利用用户POI签到时间差异性，以及用户行为相似性进行协同过滤的兴趣点推荐算法.首先，用户对兴趣点的偏好程度会随时间改变.其次，在较短的时间间隔内，用户的兴趣具有周期性[6].再者，用户在一天中不同的时间段对不同兴趣点的喜好有明显差别.Gao等人[7]提出了时序聚合策略，将用户签到行为与对应的不同时间状态整合，证明了引入时间意识因子的重要性.文献[8]支持实时POI推荐，跟踪不断变化的用户兴趣.因此兴趣点推荐是一项时间敏感的任务.

现有的POI推荐领域中，多种异构信息被考虑在内.McAuley.J等人[9]提出了一种将评分与评论文本结合的模型，提高了推荐的准确性.Gao等人[10]提出GeoSoRev模型，将社交因子，地理因子，评论文本信息融合，基于矩阵分解处理三种因子信息，扬长补短，更好的进行个性化兴趣点推荐.文献[11]将基于用户的协同过滤、社交影响因子以及地理因素融合到模型中，提升了POI的推荐效果.文献[12]和文献[13]将一天分成时刻，统计用户在不同的时刻中的访问不同的兴趣点的签到信息，生成用户-时间-兴趣点矩阵，提升推荐效果.

兴趣点推荐中主要存在以下问题.1)签到数据稀疏，降低推荐性能；2)经典的兴趣点推荐算法未能充分利用兴趣点的上下文信息，推荐性能没有显著增加；3)大部分兴趣点领域的推荐算法没有和时间结合，不能在具体的时间点动态推荐.

本文工作主要有：1)结合用户与用户之间的偏好的关系，充分利用数据集中的用户信息为用户推荐；2)加入时间序列，获得与时间有关的兴趣点，形成具有时间意识的兴趣点动态推荐；3)结合地理位置和流行度信息，进一步提升地点推荐的准确性；4)将子模型融合，形成本文提出的融合时间序列的POI动态推荐模型(UTPG).

2 概念介绍及算法框架

本章列出了融合时间序列的POI动态推荐算法所涉及到的相关概念.

2.1 相关概念介绍

主要介绍本模型所利用的各个因子，以及如何将不同因子结合到兴趣点推荐模型中.

2.2 具有个性化特征的时间意识的兴趣点

由于人类的一天中的行为、甚至一周内的行为具有一定的周期性，利用人类的周期性特征，分析用户的行为特征，一方面缓解数据的稀疏性问题，另一方面在某个确定的时刻对用户进行推荐时，结合用户历史签到记录推荐.因此，本文引入时间因素，形成与时间有关的兴趣点动态推荐.

时间的个性化特征是由于不同时间段的社会特征以及人类的习性具有相关性，例如早上8点左右的时间段、中午12点左右的时间段以及晚上7点左右的时间段都是进餐时间，因此对于不同的兴趣点，在不同的时间段被访问的频率存在一定的关联性.除此之外，时间具有连续性特征，分割后的时间段间隔越相邻，其反映的人类社会习性的相似程度越高.

2.3 地理位置影响因子

位置是标记用户签到的兴趣点的地理属性，近年来基于位置的社交网络受到广泛关注.为了将空间地理位置因素加入到本文算法中，使用幂律分布函数表示距离对用户访问兴趣点的影响.

2.4 融合时间序列的兴趣点动态推荐框架

引入具有时间意识的兴趣点动态推荐算法主要分为以下几个部分，如图1所示.

3 融合时间序列的POI动态推荐算法

引入时间意识因子、基于用户的协同过滤算法、以及结合地理位置信息，形成融合时间序列兴趣点动态推荐模型.

3.1 基于用户的协同过滤算法

传统的基于用户的协同过滤的方式是根据用户之间访问相同位置的次数度量.余弦相似度经常被用来表示用户之间的相似程度，如公式(1)所示.

图1 融合时间序列的POI动态推荐算法框架图Fig.1 POI dynamic recommendation algorithm framework diagram of fusion time series

(1)

式中Num(i，l)代表用户i访问地点l的次数，Num(k，l)代表用户k访问地点l的次数.

3.2 时间序列划分

时间序列的划分，常见的划分方式有：将一周划分为以天为时间单位的方式，例如Hosseini S[11]选择每周间隔来提高POI推荐的效率，将一周分为两个时间序列：工作日与休息日.Song等人[5]和Yuan Q等人[14]将一天的时间按照小时划分为24个相等的时间槽.本文将一天划分为24个小时.统计用户在不同时刻的偏好，t为0到23之间的整数，结合时间段的相似度度量，获得用户当前的时间为用户进行动态推荐.

如2.2节介绍，用户访问兴趣点的偏好通常与时间有关，不同兴趣点在不同时间具有不同的流行度，因此考虑时间之间的关系有助于准确的描述用户喜好.

3.3 时间序列度量方式

使用时间序列对基于用户的协同过滤算法进行改进，用户相似性是根据时间序列的特征计算，不同用户在相同时间对同一位置的频率越高，用户之间的相似度越高.衡量用户相似度采用余弦相似度度量，如公式(2)所示.

(2)

统计所有用户在任意两个时间点之间的相似度，得到平均值作为两个时间序列的相似性，如公式(3)所示.

(3)

为了缓解孤立的时间点带来的推荐效果差等问题，使用平滑技术对时刻进行过渡.

用户在t时刻访问位置l的预测评分如公式(4)所示.

(4)

其中，n表示距离当前t时刻的跨度.

用户的相似度如公式(5)所示.

(5)

最终基于用户的协同过滤结果预测评分如公式(6)所示.

(6)

3.4 结合地理影响因子与时间流行度的算法

3.4.1 基于地理因子的推荐算法

POI的访问符合幂律分布.POI间距离越小，用户访问的概率越大.因此，地理位置在兴趣点推荐领域有重要影响.

幂律分布表示两个兴趣点之间距离和用户的签到几率之间的关系，如公式(7)所示.

P(dis)=x×disy

(7)

式中，p：签到POI的概率，dis：POI之间的距离，x和y：参数.取对数，得到公式(8).

logP=logx+ylogdis

(8)

(9)

通过最小二乘回归得出到参数a，b的值，得到用户访问某兴趣点概率和兴趣点之间的距离的关系表达式.再使用朴素贝叶斯方法推荐未访问过的兴趣点.数据集中全部的兴趣点集合为P，用户访问过的兴趣点标记为Pu，则用户未访问过的兴趣点P′被用户访问的概率为P(P′|Pu)，使用贝叶斯的前提为兴趣点之间是否被访问是相互独立的.用户在已经访问过Li的前提下，访问Lj的预测值如公式(10)所示.

(10)

(11)

3.4.2 基于流行度信息的推荐算法

根据划分的时间序列统一兴趣点的流行度信息，得到基于时间的流行度特征分布，预测用户对兴趣点的评分，如公式(12)所示.

(12)

其中，分子是兴趣点l在t时刻被用户访问过的次数，L是所有的兴趣点集合.

3.5 地理因子与流行度信息融合

将地理因子、流行度信息结合，得到用户对兴趣点的评分，如公式(13)所示.

(13)

3.6 UTPG模型

将基于时间序列的用户的协同过滤算法与结合地理位置、流行度信息影响的算法结果融合，得到融合时间序列的POI动态推荐算法，采用线性加权的方式融合，得到用户u在t时刻访问l的预测评分，如公式(14)所示.

Pu，t，l=aP(u)+(1-a)P(PTG)

(14)

其中，a是调节参数，其范围是[0，1].

3.7 算法流程

输入：用户、兴趣点以及访问的时间和位置集合；

输出：兴趣点推荐序列；

步骤1.遍历所有user，计算时刻之间相似度、平均相似度、基于时刻之间的相似度求用户在某个时间访问兴趣点评分；

步骤2.计算基于连续时间概念的两个用户之间余弦相似度W(i，k)，然后计算基于连续时间内，用户在时间t访问兴趣点l的评分P(u)；

步骤3.求出幂律分布表达式，得出用户基于地理影响因子的评分P(G)；

步骤4.计算基于流行度信息的预测评分P(P)；

步骤5.将基于地理位置、流行度信息的两种方法结合，得到用户对兴趣点的预测评分P(PTG)；

步骤6.将基于用户的协同过滤算法与结合地理信息与流行度的算法融合，得到最终的预测结果Pu，t，i.

4 实验及结果分析

4.1 数据集

本文提出的算法采用兴趣点推荐领域常用的真实数据集：Gowalla的用户签到数据集.将该数据集分为3个数据集，数据集记录了用户信息、POI信息、位置信息(经、纬度)等信息.

数据集中80%的数据作为训练集，20%作为测试集.数据集信息如表1所示.

表1 数据集信息表Table 1 Dataset information

其中，Gowalla-X代表从数据集里筛选出去过X个地点以上的用户的签到记录.

4.2 评价标准

本文采用常见的评估指标：精度@N(P)、召回率@N(R)衡量推荐结果的质量，其中N是推荐结果的数量，并采用F1值评价两者之间的关系.精度是一个客观且真实的评价指标，衡量算法的准确率，是推荐系统中常见的指标.召回率是衡量算法覆盖能力的指标，算法覆盖面越大，算法的效果则较优，F1值是调和精确率和召回率的指标，由于精确度和召回率存在一定的矛盾性，因此本文的算法衡量指标采用了F1值.精度计算方式如公式(15)所示.

(15)

其中Ca为预测正确的集合，Call为预测的全部集合.

召回率的计算方式如公式(16)所示.

(16)

其中Ca为预测正确的集合，Ct为实际正确的集合.

F1值的计算方式如公式(17)所示.

(17)

4.3 对比算法

1)TCFRA[5]，考虑了时间敏感的POI的特性，得到推荐结果.

2)PT：根据兴趣点的时间分布特征，得到用户在某时刻对兴趣点的预测评分.

3)UPT：将基于用户、流行度结合，计算预测评分.

4)UTPG算法(基于时间序列的POI动态推荐算法)：将基于用户的协同过滤、基于地理影响因子和时间流行度信息的算法结合，得到用户在某时刻对兴趣点的预测评分.

Gowalla-10数据集：Top-5的推荐结果，UTPG在U：PG为4：1，其中P：G为4：1时的结果最优.Top-10的推荐结果，UTPG在U：PG为4：1，其中P：G为9：1结果最优，推荐结果如表2、3所示.其中U、G、P分别代表基于用户的协同过滤、结合地理位置、流行度信息影响的算法.

Gowalla-20：TOP-5的推荐结果，U：PG为4：1，P：G为3：2结果最优.TOP-10的推荐结果，U：PG为4：1，P：G为4：1时的结果最优.结果如表4、表5所示.

Gowalla-30：TOP-5的推荐结果，U：PG为4：1，P：G为1：9或者P为0时的结果最优，TOP-10的推荐结果中，U：PG为4：1，P：G为3：2时结果最优.结果如表6、表7所示.

表2 Gowalla-10数据集Top-5推荐结果Table 2 Top-5 recommendation results of Gowalla-10

表3 Gowalla-10数据集Top-10推荐结果Table 3 Top-10 recommendation results of Gowalla-10

表4 Gowalla-20数据集Top-5推荐结果Table 4 Top-5 recommendation results of Gowalla-20

表5 Gowalla-20数据集Top-10推荐结果Table 5 Top-10 recommendation results of Gowalla-20

1)算法性能分析：根据实验结果，可以得出，本文算法UTPG模型在TOP-N的N值分别取5、10时，在数据集gowalla-10、gowalla-20、gowalla-30中，不论在精度，召回率，还是F1值方面，效果均为最优.

这也证明了实验选择4个异构信息方面：用户之间的影响、时间的分布特征、兴趣点的流行度信息、地理影响因子都能有效地提升推荐的性能.在新生成的推荐中，算法根据历史签到特征为其动态推荐.

表6 Gowalla-30数据集Top-5推荐结果Table 6 Top-5 recommendation results of Gowalla-30

2)不同数据集中不同影响因子分析：在gowalla-10、gowalla-20、gowalla-30数据集，UPT的准确率、召回率均比PT高，说明用户相互之间的偏好影响比较大，同时UTPG均比PT和UPT的结果好，得出地理影响因子一定程度上提高了推荐性能.因此得出，用户、时间流行度、地理影响因子可以提高推荐的准确率和召回率.

在gowalla-10、gowalla-20、gowalla-30数据集，U：PG均为4：1时取得推荐结果为最优，因此，说明兴趣点推荐中，用户之间的影响比较大.且在gowalla-10、gowalla-20中，基于时间的流行度影响因子大于地理因子所带来的影响.地理影响因子也一定程度上提升了POI推荐的性能.

经过对数据集的分析，可以得出，在签到数据比较少时，使用地理、时间信息能提高推荐的性能，因此，UTPG模型，可以在一定程度上缓解推荐算法中由于数据稀疏而引发的推荐结果差等问题.