一种基于用户关系和用户偏好的下一个兴趣点推荐方法

方 金 凤，孟 祥 福,2

(1.辽宁工程技术大学测绘与地理科学学院，辽宁 阜新 123000；2.辽宁工程技术大学电子与信息工程学院，辽宁 葫芦岛 125105)

0 引言

随着无线通信设备的快速普及以及GPS定位技术的快速发展，海量基于位置服务数据能真实反映用户的行为规律，使得对用户行为模式的探索成为可能[1-4]。下一个兴趣点推荐作为基于位置服务数据最典型的应用之一，旨在根据用户行为习惯准确推测出用户下一时刻将要访问的兴趣点，为用户的决策行为提供帮助，为商家的营销活动提供参考，因此，研究下一个兴趣点推荐方法具有重要的现实意义和应用价值。

与一般兴趣点推荐不同，用户的序列访问行为对其要访问的下一个兴趣点具有重要影响，推荐列表会随签到信息时刻变化，且用户的每次移动均会导致推荐列表明显变化,因此，下一个兴趣点推荐本质上是行为序列数据分析与推荐[5,6]。马尔科夫链是解决序列分析问题的有效手段，学者们最初常基于马尔科夫链进行用户的下一个行为推荐[7-9]，但随着马尔科夫阶数(记忆步长)的增加，计算量会以指数形式增长，限制了该方法的应用。词嵌入模型可将词的特征映射到低维空间中，从而缩短计算维度,有学者据此提出基于嵌入的下一个兴趣点推荐方法[10,11]，通过将兴趣点嵌入低维空间中可捕获兴趣点间的相关性并减少计算量，但该方法无法有效获取兴趣点间的序列影响。为此，在采用嵌入方式进行下一个兴趣点推荐时，通常结合其他能够捕获兴趣点序列关系的方法，如Venue2Vec[12]基于用户对兴趣点的序列签到信息与兴趣点之间的距离构建兴趣点转移图，然后将兴趣点的序列信息输入词嵌入模型中学习，进而获得兴趣点的向量表示。循环神经网络(Recurrent Neural Network,RNN)能在序列数据中自动挖掘上下文信息之间的交互影响，在下一个兴趣点推荐中也得到广泛应用，并成为当前主流的推荐模型[13-15]，但RNN模型在长序列建模中存在梯度爆炸和梯度消失问题，为此，提出长短时记忆(Long Short-Term Memory,LSTM)[16,17]和门控循环单元(Gated Recurrent Unit,GRU)[18,19]两种RNN变体，形成了基于LSTM和GRU网络的下一个兴趣点推荐算法。

综上，下一个兴趣点推荐方法已取得一定进展，且多依据用户偏好进行推荐。研究表明，具有相似偏好的用户往往具有相似的行为[20]，可通过与某用户具有相似偏好的用户间接预测该用户的行为，此外，朋友间的信息分享会影响用户的决策[20-23]，因此，对用户关系(包括用户偏好相似关系和用户朋友关系)的挖掘和分析在下一个兴趣点推荐中至关重要。K近邻最初用于解决分类问题，后逐渐应用于各类预测问题，在基于位置的服务、空间分析等领域应用广泛[24]。鉴于此，本文应用K近邻算法，基于用户关系和历史签到记录，由当前序列的近邻序列挖掘当前序列的隐含信息，共同实现对用户下一个兴趣点的推荐。通过在真实数据集上展开实验，对本文方法进行效果与性能实验评价，以验证方法的有效性和优越性。

1 下一个兴趣点推荐方法

本文下一个兴趣点推荐方法(Relationships and Preferences-Gated Recurrent Unit，RP-GRU)的具体实现流程如图1所示。首先，对用户的访问记录进行分段处理，由此获取不同时段的用户偏好；其次，将用户关系引入下一个兴趣点推荐中，通过构建的用户关系图获取用户关系向量，并将用户关系向量同当前偏好向量与周期偏好向量进行拼接，由此得到用户向量，将用户向量与兴趣点向量相乘可获得兴趣点的近期得分；然后，采用用户长期访问序列的K近邻序列获取用户的长期偏好，计算出兴趣点的长期得分；最后，将兴趣点的近期得分与长期得分相加得到兴趣点的总得分，据此进行下一个兴趣点推荐。

图1 下一个兴趣点推荐的解决方案Fig.1 Solutions for next POI recommendation

1.1 用户关系向量

1.1.1 用户关系图构建

(1)用户关系图由节点(代表用户)、边(代表用户关系)和权重(代表用户关系的紧密度)组成。用户关系包括朋友关系和偏好相似关系，两个用户访问的共同兴趣点越多，说明其偏好越相似，如果两个用户存在朋友关系或两者访问过同一兴趣点，则两者之间边的权重加1。以4个用户对3个兴趣点的访问情况及用户之间的朋友关系为例(表1)，可构建出用户关系图(详见图1)。

表1 用户对兴趣点的访问记录及其朋友关系Table 1 Users′ check-in records for POIs and friend relationships

(2)重启随机游走算法通过迭代方式探索网络图的整体结构以捕捉两个节点之间的关系，进而得到节点间的接近度[25]。本文根据用户关系构建用户关系图，将计算两个用户之间的相似性问题转化为计算用户关系图中两个节点之间的接近度问题，进而通过重启随机游走算法评估两个用户之间的相关性。用户关系图中两节点之间连线的权重代表从一个用户到另一个用户的转移强度，如与u2相连边的权重总和为4，u2与u4相连边的权重为2，则从u2到u4的转移概率为2/4(从u4到u2的转移概率为2/6)。由此，用户ui到uj随机游走的概率可由式(1)计算。从用户关系图中的一个节点出发，选取模型训练表现最优对应的步长和次数进行随机游走，并对图中所有节点重复此操作即可获得模型训练的序列输入数据。本文中步长为20，次数为50次。由于不同数据集下参数的取值各异，对于较大的数据集需适量增加步长和随机游走次数以提升模型性能，使得依赖短随机游走得到的信息能够在不需全局重新计算的情况下适应网络出现的小变化。

(1)

式中：f(ui,uj)为以ui和uj为顶点的边的权重，f(ui,uj)与f(uj,ui)不一定相同；F(ui)为用户关系图中与ui有边相连的节点集合。

(2)

(3)

(4)

(5)

式中：η为学习率，根据文献[26]取值为0.025。

1.2 周期偏好与当前偏好

按照用户对兴趣点的签到时间将用户偏好划分为长期偏好(用户所有签到记录)、周期偏好(包括当前偏好和月偏好)和当前偏好。

1.2.1 当前偏好与月偏好 当前偏好指用户最后一次签到1天之内的签到记录(日偏好)，月偏好指与用户最后一次签到相距1个月内的签到记录,两者均用GRU模型建模，以签到兴趣点和签到时间为输入，区别在于输入数据的时间间隔不同。签到时间包括签到星期和签到时刻，分别用独热编码(one-hot encoding)表示，签到星期分为7 d，如周一表示为[1,0,0,0,0,0,0]，签到时刻分为24 h，如0点表示为[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]。模型在t时刻的输入St由当前时刻签到兴趣点向量pt、签到星期向量Weekt与签到时刻向量Hourt组成，记做St=[pt:Weekt:Hourt]。通过GRU模型对月偏好和当前偏好建模(图2)，其计算方法为：

图2 当前偏好建模Fig.2 Current preference modeling

ht=f(St,Wht-1,b)

(6)

uc=σ(Wo·ht+bo)

(7)

式中：ht为GRU模型的输出；uc为当前偏好向量；ht-1为GRU模型上一时刻的输出；W、Wo和b、bo分别为神经网络的权重和偏置。

1.2.2 周期偏好 受DeepMove模型[18]的启发，用户的周期偏好对其访问下一个兴趣点存在一定影响。DeepMove模型以日为单位对用户的签到记录进行划分，以用户每日签到兴趣点向量的平均值表示用户当日的信息。本文利用分层注意力机制通过用户的月偏好和当前偏好得到用户的周期偏好(式(8)-式(10))。通过用户的当前偏好uc与向量ot得到月偏好模型每一时刻对用户周期偏好贡献的注意力权重αt，将ht与其对应注意力权重αt相乘作为月偏好每一时刻对用户周期偏好的贡献，月偏好所有时刻的贡献之和up即为用户的周期偏好(图3)。

图3 周期偏好建模Fig.3 Periodic preference modeling

ot=tanh(Wht+bw)

(8)

(9)

(10)

式中：ht为月偏好模型每一时刻的输出;W和bw分别为神经网络的权重和偏置；ot为ht经过一层全连接神经网络后的向量；uc为周期偏好的输入，文献[27]中uc向量被随机初始化，然而本文以当前偏好模型在最后一个时刻得到的输出向量作为uc。

1.3 兴趣点近期得分

wi=eiW

(11)

式中：ei为嵌入之前的向量；wi为嵌入之后的向量；W∈Rm×d为模型需要训练的权重矩阵。

(12)

式中：l(P,Qt)用于判断在输入序列为Qt的条件下模型能否正确预测兴趣点P，能正确预测，l(P,Qt)=1，否则l(P,Qt)=0；θ为模型所有可训练的参数；λ为正则化系数。

1.4 兴趣点长期得分

现有下一个兴趣点推荐算法通常只利用用户自身的偏好信息进行推荐，忽略了相邻序列(指与该用户的历史签到序列相似的序列)中的潜在协作信息(即两序列之间的共性)，相邻序列存在类似的行为模式，反映与当前序列相似的用户意图。例如，当前用户的历史访问序列为[公园1，公园2，博物馆1，公园3]，序列1为[公园1，公园2，博物馆2，公园3，宾馆]，序列2为[动物园1，公园2，动物园2，公园3，饭店]，相比序列2，序列1与当前用户的历史访问序列更接近，由此可以推断当前用户的意图与序列1较相似，该用户离开公园3后，要访问的兴趣点大概率是序列1中的宾馆，而非序列2中的饭店。

采用K近邻序列对用户长期偏好进行挖掘，主要通过当前用户历史访问序列的相似序列探索该用户可能访问的下一个兴趣点。序列之间的相似性由两个序列共同访问过兴趣点的数量与两个序列分别访问过兴趣点的总数量的比值表示。首先，通过式(13)计算当前序列s与数据集中其他序列n之间的相似性，根据相似性结果在数据集中找出与当前序列最相似的K个序列,构成当前序列的K近邻序列集合Ns；然后，通过每个兴趣点在K个近邻序列中的存在情况为兴趣点赋分值，作为兴趣点的长期得分Score2(i)(式(14))，由此可得兴趣点的总分值Score(i)=Score1(i)+Score2(i)；最后，对Score(i)进行排序，将分值较大的前K个兴趣点推荐给用户。

sim(s,n)=|s∩n|/|s∪n|

(13)

(14)

式中：ln(i)为检验兴趣点i是否存在于当前序列的K近邻序列中的标记，如果序列n包含兴趣点i，则ln(i)=1，否则ln(i)=0。

2 实验结果与分析

2.1 实验设置

选取真实的CA数据集和Gowalla数据集进行算法验证：CA数据集采用Fousquare点评网站(https://foursquare.com/about)上2010年1月至2011年8月4 163名加利福尼亚用户的483 813条签到信息，兴趣点的纬度范围为[-33.94°,52.31°]，经度范围为[-159.35°,151.17°]；Gowalla数据集是兴趣点推荐广泛使用的公开数据集(http://snap.stanford.edu/data/loc-gowalla.html)，包括2009年2月至2010年10月196 591名用户的6 442 890条签到信息，兴趣点的纬度范围为[32.65°,40.59°]，经度范围为[-122.87°，-114.04°]。为缓解数据的稀疏性，移除签到次数少于10的用户和兴趣点。用户签到数据集的格式如表2所示，选择用户历史签到数据集的最后一次签到记录作为测试集，其余为训练集。

表2 实验数据集格式Table 2 Format of experimental datasets

选择常用的Accuracy@k(ACC@k(式(15)))和MRR@k(式(16))作为实验评价指标：ACC@k可衡量推荐列表中兴趣点的准确程度，如果用户访问的下一个兴趣点真实出现在推荐列表中，则认为预测正确，其值为1，否则为0，ACC@k取所有测试实例的平均值，值越高表示模型的推荐效果越好；MRR@k可衡量推荐列表中兴趣点的排名，用户访问下一个兴趣点在推荐列表的位置越靠前，则MRR@k的得分越高。

(15)

(16)

2.2 实验结果

为验证本文模型引入用户关系的有效性，分别在CA和Gowalla数据集上将未引入用户关系和引入用户关系后得到的推荐结果进行对比，结果如表3所示。由表3可以看出，引入用户关系的算法要显著优于未引入用户关系的算法，这是因为朋友之间会分享相关信息，也会结伴访问相同的兴趣点；同时，历史访问行为相似的用户很可能未来也会访问相似的兴趣点。以ACC@10评价指标为例，引入用户关系的算法在CA和Gowalla数据集上分别比未引入用户关系的算法准确度提升了25.17%和18.13%，说明用户关系对预测用户的决策行为至关重要，引入用户关系的算法可显著提升推荐结果的准确性。

表3 用户关系对推荐性能的影响Table 3 Impact of user relationship on recommendation performance

为验证本文采用K近邻方法分析用户长期序列偏好的有效性，分别在CA和Gowalla数据集上将未采用K近邻方法和采用K近邻方法得到的推荐结果进行对比，通过测试K不同取值的实验得出，在CA和Gowalla数据集上K分别取100和300。由表4可知，无论是推荐准确性指标ACC@k还是索引值指标MRR@10，采用K近邻序列挖掘用户的长期兴趣点偏好均优于未采用K近邻算法，表明K近邻序列对挖掘当前序列的隐含信息具有积极作用，由此可以证明本文添加K近邻序列的有效性，但添加K近邻长期序列分析法对实验结果的提升不明显。以ACC@10指标为例，采用K近邻算法后的模型比未采用K近邻的模型在CA和Gowalla两数据集上分别高出4.20%和1.27%，这是因为用户的下一个行为主要受当前偏好和周期偏好的影响较大，长期偏好对用户决策的影响力较小。

表4 K近邻序列对推荐性能的影响Table 4 Impact of K-nearest neighbor sequences on recommendation performance

为进一步验证本文算法的有效性，分别与5种经典的下一个兴趣点推荐算法进行对比，结果如表5所示。1)FPMC-LR[9]：基于马尔科夫链并结合矩阵分解对序列建模获取用户偏好，进而实现下一个兴趣点的推荐；2)PRME-G[10]：采用个性化度量嵌入的方法进行下一个兴趣点推荐，将空间距离作为权重控制用户的距离偏好，同时整合用户偏好信息、序列信息和地理位置信息；3)POI2Vec[11]：典型的基于嵌入模型的方法，将Word2Vec应用于兴趣点预测，将每个兴趣点看作Word2Vec中的一个word，实现下一个兴趣点的预测；4)Distance2Pre[19]：利用GRU模型获取用户签到历史序列信息和距离偏好进行推荐，提出线性和非线性两种整合模型，本文使用效果更好的非线性模型进行对比；5)CSRM[15]：一种新颖的兴趣点推荐方法，不仅对用户的签到信息进行建模，还考虑相似用户的会话签到信息。

表5 不同算法推荐性能对比Table 5 Comparison of different algorithms in recommendation performance

由表5可知，基于GRU对用户历史签到数据建模的Distance2Pre和RP-GRU模型显著优于只基于当前兴趣点进行推荐的FPMC-LR和PRME-G模型，从侧面说明GRU模型对于序列建模的有效性，同时也反映出当前签到兴趣点序列较短，无法有效预测用户偏好信息，应考虑更长期的序列信息，以免误解用户的访问意图。整体看，与5种对比算法相比，兼顾用户关系以及用户不同阶段偏好的RP-GRU模型在两数据集上的效果均最好，证明该方法有效。

3 结论

本文对用户的访问记录进行分段处理，根据签到时间划分为长期偏好、周期偏好和当前偏好，通过GRU模型对用户的周期偏好和当前偏好建模，采用用户历史签到序列的K近邻序列挖掘用户的长期偏好，同时引入用户关系，为下一个兴趣点推荐提供了新的解决方案，并通过在真实数据集上进行实验以及与现阶段主流的下一个兴趣点推荐方法进行对比，验证了本文方法的有效性。

下一个兴趣点推荐是基于位置服务的典型应用，具有重要的研究价值和良好的发展前景，未来将从以下两方面进行研究：1)K近邻算法中K值的确定，虽然本文方法可应用于不同数据集中，但K近邻的取值需依据不同数据集而定，下一步将考虑在更多的数据集上进行实验，寻找K近邻取值与数据集之间的关联性，争取自适应确定K近邻数量；2)用户关系的界定，需重点探索朋友关系和偏好相似关系建模的侧重点。