融合时空信息的双向GRU下一个地点推荐

李 全，李书明，许新华，向丹丹，曹双双

(湖北师范大学 计算机与信息工程学院，湖北 黄石 435002)

1 引 言

随着计算机网络的飞速发展，微博、微信和Facebook等社交网络吸引数十亿用户相互交流和共享信息.近年来，基于定位的社交网络服务的快速增长.这些服务已经吸引了许多人用户可以通过大量的地理标记数据与用户分享他们的位置和经验.这些签到数据可以让我们更好的了解移动用户的行为.例如，我们可以根据用户的历史足迹，预测他们下一步将要去哪[1].例如：博物馆和咖啡厅等.地点推荐可以帮助用户在位置社交网络的海量数据中找到自己感兴趣的信息，从而访问新的地理区域，方便用户的生活[2].

大多数基于机器学习的POI推荐的方法包括协同过滤的地点推荐和矩阵分解地点推荐，其中矩阵分解方法是将不同用户的签到数据转化为用户-位置矩阵，通过矩阵分解的方式，计算用户和位置的特征向量表示，从而进行推荐.然而，用户签到的数据具有周期性和序列性.因此如何更好地分析用户序列数据，成为了地点推荐算法有待解决的问题.随着深度学习的发展，循环神经网络(Recurrent Neural Network，RNN)可以很好地处理序列数据[3]，并成为建模序列数据的一种经典方法.但是RNN由于梯度消失的原因只能有短期记忆能力，长短期记忆(Long-Short Term Memory，LSTM)模型通过门控制技术在一定程度上解决了梯度消失的问题.而门控循环单元(Gated Recurrent Unit，GRU)模型作为LSTM的一种变体，将遗忘门和输入门合成了一个更新门，具有参数少和效率高等优点，相比于LSTM模型要更简单.因此，本文选择GRU模型作为分析用户签到序列数据的基本模型.在用户的签到数据中，空间信息的经纬度坐标会影响到用户的签到行为.例如有些人在逛完商场之后，可能会去附近的电影院，而不会去距离较远的网球场.另外，时间信息也是影响用户签到行为的重要因数.例如有些人中午下班之后会去餐厅，而在晚上下班之后会去酒吧.总之，如何根据用户的时间和空间等上下文信息为用户准确地推荐下一个地点，仍然是一个具有挑战性的问题.为了解决以上问题，本文提出了一种融合时空信息的双向GRU下一个地点推荐算法.

2 相关工作

地点推荐算法包括基于协同过滤的推荐、基于神经网络的推荐和基于序列信息的推荐等.在基于协同过滤的推荐方法：Zhang 等人[4]提出了一种个性化的有效的地理位置推荐框架iGeoRec.该框架一方面可以为每个用户计算个性化的位置概率分布.另一方面通过似然估计方法预测用户访问下一位置的概率.Lian 等人[5]提出了一种结合地理模型和加权矩阵分解的兴趣点推荐算法.该算法认为人类的位置活动具有空间聚集现象.因此将地理信息融入矩阵分解模型中，并讨论该模型中的用户的区域向量和兴趣点的区域向量的影响.Gao 等人[6]提出了一种融合时间影响和矩阵分解的兴趣点推荐算法.该算法介绍了4种时间聚合策略，并将不同的时间状态融入到用户的签到偏好中.

在基于神经网络的推荐方面：Yang 等人[7]将协同过滤和半监督学习结合起来，采用神经网络实现兴趣点推荐.通过深度神经网络学习用户和兴趣点的潜在特征，并预测用户下一个兴趣点的偏好.Xing 等人[8]结合卷积神经网络和概率矩阵分解提出了一种基于卷积矩阵分解的兴趣点推荐模型.该模型融合了用户的签到信息、社交关系和评论信息等.

在基于序列信息的推荐方面：Cheng等人[9]提出了FPMC-LR模型，该模型结合了位置转移矩阵的马尔科夫链和用户地理距离从而实现地点推荐.Feng等人[10]提出了PRME模型，该模型采用个性化度量嵌入方法实现用户的下一个地点推荐.随着自然语言处理技术的发展，循环神经网络已经被成功的应用于文本分类，情感分类和机器翻译等领域.在循环神经网路中GRU模型具有训练模型参数少，效率高等优点.另外，在人们的生活中，时空信息也会影响到用户的签到行为.因此，本文将签到序列中两个相邻地点之间的时间间隙和距离间隔通过嵌入层映射为特征向量，然后采用双向GRU模型从两个方向提取序列信息和时空信息，从而提出了一种融合时空信息的双向GRU下一个地点推荐算法.该算法可以更好的结合用户的时空信息，提高下一个地点推荐的性能.

3 融合时空信息的双向GRU兴趣点推荐技术

3.1 问题的描述

3.2 GRU模型

循环神经网络基础模型RNN由于梯度消失等原因只有短期记忆能力，LSTM模型通过门控制技术在一定程度上解决了梯度消失的问题.而GRU模型作为LSTM的一种变体，具有参数少和效率高等优点，相比于LSTM模型更简单.GRU具体结构如图1所示.

图1 GRU模型图Fig.1 Model of GRU

由图1可知，GRU模型的公式如下：

rt=σ(Wrhht-1+Wrxxt+br)

(1)

zt=σ(Wzhht-1+Wzxxt+bz)

(2)

(3)

(4)

3.3 融合时空信息的双向GRU推荐模型

在进行地点推荐的过程中，将相邻地点之间的时间间隙和距离间隔通过嵌入层投影为特征向量，通过GRU模型对用户的签到序列、时间信息和距离信息进行双向的特征分析，从而更好的获取用户个性化潜在特征.本文提出了融合时空信息的双向GRU(Spatiotemporal Bidirectional Gated Recurrent Unit，BiGRU+ST)推荐模型如图2所示.

图2 BiGRU+ST模型图Fig.2 Model of BiGRU+ST

rt=σ(Wrhht-1+Wrxxp_ti+Wrddp_ti+Wrttp_ti)+br)

(5)

zt=σ(Wzhht-1+Wzxxp_ti+Wzddp_ti+Wzttp_ti)+bz)

(6)

(7)

(8)

3.4 目标函数和训练方法

融合时空信息的双向GRU的推荐模型将采用BPR算法定义目标函数.首先利用pair-wise的方法得到训练集的正例样本集和负例样本集，构造模型参数的最大后验概率函数，然后将最大化后验概率函数转换为最小化目标函数，最后采用随机梯度下降法更新模型参数，如公式(9)、(10)、(11)和(12)所示[11].

max ln(p(Θ|≻u，t))=ln(p(≻u，t|Θ))+ln(p(Θ))

(9)

定义最小化目标函数如公式(10)所示.

(10)

模型参数为Θ={Wrh，Wrx，Wrd，Wrt，Wzh，Wzx，Wzd，Wzt，Whr，Whx，Whd，Wht，br，bz，bh，L，D，T}，其中权重矩阵包括Wrh，Wrx，Wrd，Wrt，Wzh，Wzx，Wzd，Wzt，Whr，Whx，Whd，Wht，偏置向量包括br，bz，bh，地点的潜在特征矩阵为L为.地点间距离间隔的潜在特征矩阵为D.地点间时间间隙的潜在特征矩阵为T.正则化的超参数为λ.目标函数对模型参数求偏导数的公式如公式(11)所示.

(11)

通过设置学习率为α.最后采用随机梯度下降法更新相关参数，使目标函数最小化，直至目标函数收敛，如公式(12)所示.

(12)

融合时空信息的双向GRU的地点推荐算法的学习率为α，正则化系数为λ，具体步骤如下：

输入：签到数据C，时间间隙tt，距离间隔dd.

输出：模型参数Θ={Wrh，Wrx，Wrd，Wrt，Wzh，Wzx，Wzd，Wzt，Whr，Whx，Whd，Wht，br，bz，bh，L，D，T}.

//构造训练数据

1.for each user u inUdo

4.time_index=f(Δtti，tt)，dis_index=Δdti*1000/dd

7. end for

8. Add a user training listDutoD

9.end for

//训练模型参数

10.Initialize the parameter set Θ

11.Randomly choose a user u inU

12.Get training listDuof the user u fromD

15.Util minimizing the objective(10)

16.Saving the learned parameter set Θ

4 实验和结果分析

4.1 数据集

文本选择了两种公开的基于位置社交网络的数据集.在数据集中，每一行都包括用户标识符，签到点标识符，签到时间和签到点的经纬度坐标等信息[12].其中Foursquare是来自于美国的地理位置签到数据集，Gowalla是来自于美国斯坦福大学SNAP实验室公布的数据集.我们首先对两个数据集进行预处理.对每个用户，将签到次数小于4的用户删除.对每个签到点，将被签到次数小于4的签到点删除.将每个数据集80%的数据作为训练集，剩余的20%的数据作为测试集.两个数据集统计特性如表1所示.

表1 两个数据集统计信息Table 1 Statistical information of two datasets

4.2 评价标准

为了评价本文提出的融合时空信息的双向GRU模型(BiGRU+ST)与其他基本baselines模型的性能，我们使用3个标准的评价指标，即准确率(Precision@K)、召回率(Recall@K)和F1@K值，其中K表示待推荐的地点总数.准确率表示在推荐列表中正确的地点数与已推荐总数的比率.召回率表示在推荐列表中正确的地点数与用户应该访问地点总数的比率.F1值将准确率和召回率进行了综合.以上3个评价指标如公式(13)所示.

(13)

其中R(u)表示为用户u推荐的地点的集合，T(u)表示用户u实际访问的地点的集合.

4.3 实验结果分析

本文选定了6种地点推荐算法与所提的BiGRU+ST算法进行对比.MF 是将每个用户的签到点序列转换为用户-位置矩阵，然后该矩阵被分解为用户潜在特征矩阵和位置潜在特征矩阵，最后预测用户对待推荐地点的评分[13].FPMC-LR是结合了位置转移矩阵的马尔科夫链和用户地理距离从而实现地点推荐.PRME采用个性化度量嵌入方法实现用户的下一个地点推荐.RNN是将用户的签到数据转化为签到序列，然后通过循环神经网络对签到序列进行分析，得到用户的潜在特征表示，最后对待推荐的地点进行预测.GRU是基于门控循环单元的地点推荐方法.GRU+ST是指门控循环单元在分析用户的签到序列的时候，将位置信息和时空信息进行了融合，从而得到用户的潜在特征表示.

本文选择Python作为实验的编程语言，选择Theano作为深度学习框架.在训练模型的过程中，将学习率α设置为0.001，正则化系数λ设置为0.01，嵌入向量的维度latent_size设置为60.模型推荐的列表长度K分别取5、10和20.当K取不同值时，地点推荐算法的准确率、召回率和F1值是不同的，实验结果如表2所示.

表2 两个数据集上的准确率和召回率实验结果Table 2 Experimental results of precision and recall on two datasets

4.3.1 性能的比较

当推荐列表长度K取不同值时，本文选定的6个不同推荐算法与所提的BiGRU+ST推荐算法分别对2个数据集进行评估，它们的准确率和召回率结果如表2所示.RNN推荐算法在准确率和召回率方面都要优于MF、FPMC-LR和PRME算法.GRU推荐算法可以产生比上述推荐算法，特别是RNN算法更好的推荐性能，说明了GRU模型在分析签到序列数据方面存在明显的优势.GRU+ST推荐算法与GRU算法相比在准确率和召回率方面分别提高了4%-6%.说明了当将位置信息和时空信息进行融合之后，该模型可以更好的提取用户的特征，从而提高推荐算法的效果.BiGRU+ST相比于 GRU+ST算法在P@5，P@10，P@20，R@5，R@10和R@20等方面平均提高了3%，4%，6%，3%，5%和6%，说明该模型通过双向分析签到序列和时空信息又能进一步有效的提高地点推荐算法的性能.

4.3.2 参数对BiGRU+ST的影响

在基于BiGRU+ST的地点推荐中，推荐算法的性能会随距离间隔和时间间隙的不同而不同.该部分主要在Foursquare数据集的基础上进行实验分析，并将该数据集划分为80%的训练集和20%的测试集.本文设置了不同的距离间隔和时间间隙的实验，验证距离间隔和时间间隙对推荐算法性能的影响，其中dd表示距离间隔，tt表示时间间隙.

1)距离间隔dd的实验分析

本实验在保持时间间隙不变的情况下，将两个地点的距离间隔分别设置为50m，100m，150m，200m，250m，300m，350m和400m.通过调节不同的距离间隔，观察BiGRU+ST算法在R@5，R@10，R@20，F1@5，F1@10和F1@20等性能指标的变化.不同距离间隔的BiGRU+ST算法实验结果如图3所示.

图3 距离间隔dd的对比实验Fig.3 Comparsion of distance interval dd

由图3可知，当距离间隔50≤dd<200时，BiGRU+ST地点推荐算法性能先逐渐增加，当距离间隔200≤dd≤400时，该推荐算的性能又逐渐减少.说明当地点之间的距离间隔为200m时，BiGRU+ST推荐算法的Recall和F1值达到最大值，所以本文设置地点间的距离间隔为200m比较合理.

2)时间间隙tt的实验分析

本实验在距离间隔不变的情况下，将两个地点的时间间隙分别设置为8min，15min，30min，60min，120min，240min，480min和720min.通过调节时间间隙。观察BiGRU+ST算法在R@5，R@10，R@20，F1@5，F1@10和F1@20等性能指标的变化.不同时间间隙的BiGRU+ST算法实验结果如图4所示.

图4 时间间隙tt的对比实验Fig.4 Comparsion of time interval tt

由图4可知，当时间间隙8≤tt<30时，BiGRU+ST地点推荐算法的性能先逐渐增加，当时间间隙30≤tt<720时，该推荐算法的性能逐渐减少.当地点之间的时间间隙为30min，BiGRU+ST地点推荐算法的召回率和F1值达到最佳值，所以本文设置时间间隙的取值为30min比较合理.

5 结束语

本文主要研究通过双向GRU模型分析地点的签到序列、时间和距离等上下文信息，获取用户的个性化偏好.首先将两个地点之间的时间间隙和距离间隔通过嵌入层投影为潜在特征向量，然后采用双向GRU模型提取签到序列、时间序列和距离序列的信息，获取用户的特征向量表示.最后，通过贝叶斯个性化排序算法构造目标函数并学习模型参数.对两个数据集进行实验分析，表明本文所提的算法相比其他相关的地点推荐算法在地点推荐性能上有了较大的提高，证明了该模型的有效性.在未来的工作中，基于图神经网络的学习模型融合多种上下文信息将是一个非常值得关注的方向.