基于图嵌入和GRU的兴趣点推荐模型①

王兴源

（南京邮电大学 计算机学院,南京 210046）

随着移动设备,全球定位系统（Global Position System,GPS）和Web 2.0技术的迅速发展,基于位置的社交网络（Location-Based Social Network,LBSN）逐渐在人们的日常生活中普及.与传统的社交网络相比,LBSN不仅包括了人与人之间的联系,还可以共享人们之间的位置信息,使得线上社交和线下社交相结合,用户可以随时分享自己或浏览他人的足迹.目前主流的社交应用（如Twitter、Foursquare、Gowalla等）都满足LBSN的主要特性.这样的应用每天都在产生TB级别的时空数据,其通常以GPS数据或签到数据（check-ins）的形式记录.这些信息既是个人行为习惯与偏好的体现[1],也在一定程度上反映了一座城市里人们的生活方式和移动模式.基于以上数据,多种类型的推荐被提出[2],其中兴趣点推荐为其重要研究方向之一.

如图1所示,兴趣点推荐模型的方法主要分为传统推荐方法和深度学习推荐方法.其中传统推荐方法可分为以下5种:（1）协同过滤,其基本思想为相似的用户有相似的兴趣,通过相似度计算进行推荐.Ference等[3]综合考虑用户偏好,社交因素以及地理位置,在协同过滤的基础上提出了UPS-CF算法,将本地居民和外地居民分开推荐.（2）概率模型,其认为用户-POI签到矩阵分布符合特定的概率分布模型.Cheng等[4]基于对用户签到数据的观测,发现其有家、公司等多个分布中心,基于此提出了一个多中心高斯分布模型来进行推荐.（3）矩阵分解,其将用户签到矩阵分解为用户矩阵U和兴趣点矩阵V,从U和V中可以分别得到所有用户和兴趣点的潜在表示向量,通过两种表示向量内积计算推荐评分.Cheng等[5]提出的基于矩阵分解和马尔科夫链的FPMC-LR模型,依据矩阵分解学习所有用户的整体偏好,通过兴趣点转移矩阵的马尔科夫链来挖掘出人们在时间维度的移动模式.（4）基于链接的模型,此类模型考虑用户与用户,兴趣点与兴趣点,用户与兴趣点之间的联系,据此构建对应图进行推荐.Ying等[6]通过构建一个HITS（Hyperlink Induced Topic Search）为基础的模型,将兴趣点推荐问题转化用户-兴趣点的相关度问题.（5）混合模型,即综合考虑各个模型的优缺点,一般采用两个模型进行联合推荐.Ye等[7]的USG模型中,一方面通过协同过滤处理用户偏好以及朋友关系,另一方面又采用幂律分布概率模型对地理因素进行建模,最后将推荐的结果线性相加进行混合推荐.张岐山等[8]提出的SoGeoCat模型将协同过滤和矩阵分解算法相结合,根据用户相似性与潜在兴趣点进行建模,克服了单一模型的不足,缓解了数据稀疏的问题.

图1 兴趣点推荐方法分类

深度学习的兴趣点推荐方法主要有以下4种:（1）基于RNN（Recurrent Neural Networks）的方法.由于近来RNN在自然语言处理领域表现优秀,研究人员就尝试着将其应用在任务相似的兴趣点推荐领域.Liu等[9]提出了ST-RNN（Spatial-Temporal RNN）时空循环神经网络模型,此模型在普通的RNN基础上增加了时间转移矩阵和距离转移矩阵,通过此方法,ST-RNN能够捕捉时间因素和距离因素对人们移动轨迹的影响.（2）基于LSTM（Long Short-Term Memory）的方法.LSTM在其网络结构中引入了输入门,遗忘门和输出门的概念,解决了RNN在处理较长序列时产生的梯度消失问题.Zhao等[10]提出的SLSTM模型,采用了堆叠LSTM和Embedding嵌入层来进行兴趣点推荐.王立等[11]提出的POI-LSTM推荐框架,将用户信息、好友关系、POI信息和评论信息进行Embedding化以后输入到LSTM神经网络中捕捉用户的兴趣变化趋势来进行推荐.Huang等[12]提出的AT-LSTM模型,将时空信息融入模型中,同时引入了注意力机制,实现了高效的兴趣点推荐.Zhao等[13]提出的STGN模型,基于LSTM与时空数据,对LSTM每个cell的内部结构进行了修改优化,使得推荐效果大幅度提高.（3）基于GRU（Gated Recurrent Unit）的模型.相比于LSTM,GRU因使用同一门控来控制需要遗忘和记忆的信息而大大减少了网络结构所需要的参数,使得其计算代价变低了.（4）基于图嵌入（Graph Embedding,GE）的模型.GE通过对类似于用户-兴趣点这样的二分图进行学习,得到低维的特征表示用作后续步骤的推荐.Xie等[14]通过对兴趣点-兴趣点图,兴趣点-区域图,兴趣点-时间图,兴趣点-文字图进行学习,分别研究了序列因素、地理因素、时间因素和语义因素对用户移动轨迹的影响,通过计算用户移动轨迹之间的相似性来进行兴趣点推荐.

虽然上述的传统方法和深度学习方法在兴趣点推荐领域中取得了不错的成绩,但是他们没有对兴趣点本身附带的辅助信息进行很好的使用和融合,如兴趣点的种类,兴趣点的品牌等.本文提出了一种基于图嵌入的GRU兴趣点推荐方法GE-GRU.该模型首先利用GE方法对POI本身及其辅助信息进行融合,得到了信息丰富的深层兴趣点Embedding表示信息,再将此Embedding信息输入到GRU网络中进行训练,最后利用用户Embedding和通过GE模型学习到的兴趣点Embedding进行推荐.相比于现有的模型,GE-GRU一方面吸收了GE可以通过从图中学习出低维特征表示的优点,另一方面运用了GRU网络擅长捕捉序列依赖信息的特点,两者相结合,使得其在兴趣点推荐上表现良好.

本文的贡献点如下:

（1）在数据预处理阶段,为了缓解数据稀疏问题,采用了扩充用户移动序列的数据增强方法.

（2）对兴趣点及其辅助信息进行了融合处理,使得兴趣点表征信息更加丰富.

（3）将GE图嵌入模型与GRU门控循环单元模型相结合,吸取了二者的优点,提高了兴趣点推荐效果.

后文组织如下:第1节介绍兴趣点推荐的问题定义以及GE和GRU的简介; 第2节介绍GE-GRU兴趣点推荐模型的具体实现细节; 第3节介绍数据集、数据预处理以及实验结果及分析; 第4节总结概括全文.

1 相关背景

本节主要介绍模型的问题定义,和模型架构相关的基于图嵌入的模型和GRU网络结构.

1.1 问题定义

1.2 图嵌入简介

图广泛存在于真实世界的多种场景中,图即节点和边的集合,如社交网络中人与人之间的联系,兴趣点与兴趣点之间的关联.

图嵌入技术[15]是一种将图数据,通常为高维稠密矩阵映射为低微稠密向量的过程,其习得的向量不仅能够保留图模型的结构信息和潜在的特征,还能够很好地解决图数据难以高效输入机器学习算法的问题.图嵌入将属性图转换为向量或者向量集,学习得到的嵌入数据捕捉了图的拓扑结构、顶点到顶点的关系以及关于图、子图和顶点的其他相关信息.

图嵌入技术的基础是Word2Vec算法[16],其思想为:利用海量的文本序列,根据上下文单词预测目标单词共同出现的概率,构造出一个最优化的神经网络,此网络中的特定参数矩阵即单词的向量.Skip-gram为Word2Vec的模型之一,如图2所示,其网络有输入层、隐层和输出层.网络的输入即每个单词的独热编码（one-hot）,独热编码是一个长度与单词字典相同的向量,除了其在字典的对应位置为1以外,其他都为0,隐层没有激活函数,其输出为单词的嵌入表示,输出层为与预测单词邻域单词的Softmax分类器.由图2可以看出,Word2Vec本质上是一种将单词从高维冗长的独热编码形式降维到含义丰富的低维表示向量.

图2 Skip-gram模型

图嵌入的方法主要分为3类[15]:1）基于因子分解的方法; 2）基于随机游走的方法; 3）基于深度学习的方法.DeepWalk[17]是典型的基于随机游走的方法,其受Word2Vec启发,首先选取某特定的点作为起点,接着随机游走一定的步数,得到序列,将此序列视为句子输入到Word2Vec模型中进行训练,得到图中每个点的表示向量,该向量反映的是该点在途中的局部结构,两个点在图中的共有近邻点越多,其对应的两个向量之间的相似度就越高.

1.3 GRU简介

GRU是循环神经网络的一种,其网络结构与LSTM类似,都是为了解决长期记忆和反向传播中的梯度等问题而提出的,而前者与后者不同之处在于,GRU在使用了更少的门控单元的情况下能够达到与LSTM网络十分相当的效果,因此GRU相比之下更加容易训练,很大程度上提高了训练效率.

GRU的每个cell结构如图3所示,包括重置门（reset gate）,更新门（update gate）和隐藏层.重置门用来控制当前cell需要保留多少上个cell传递的记忆,更新门在功能上实现了LSTM中遗忘门和输入门的功能,其控制了需要从上个cell的隐藏层中遗忘多少信息,和需要从当前cell的隐藏层中加入多少信息,两者结合得到最后输出的隐藏层信息.GRU的前向传播公式如下:

图3 GRU模块结构

其中,σ表示Sigmoid函数,W表示GRU网络结构中的各权重矩阵,h表示隐藏层信息,b表示偏置项,tanh表示输出的激活函数.

2 模型介绍

现有的兴趣点推荐模型存在着数据稀疏与冷启动问题,针对此问题,本文提出了融合兴趣点与其辅助信息的思路.兴趣点辅助信息指的是兴趣点名称,兴趣点品牌以及兴趣点种类这些和兴趣点本身密切相关的信息.现有的基于深度学习的兴趣点推荐模型只考虑对兴趣点本身进行学习,而忽略了兴趣点辅助信息中所蕴含的信息.通常,有着相似辅助信息的兴趣点在Embedding空间中也会有着相似的Embedding表示.基于这样的前提,本文提出了采用GE方法学习出融合辅助信息的兴趣点Embedding表示,再将融合了Embedding表示的用户序列信息输入到GRU神经网络中得到用户Embedding表示,此用户Embedding和兴趣点Embedding进行内积运算,得到该用户下一个可能去的兴趣点列表排序,据此进行推荐.

本节将从兴趣点基础Embedding生成模型、改良Embedding生成模型,GE-GRU模型网络结构3方面进行介绍.

2.1 基础Embedding生成模型

基于GE的Embedding生成模型主要采用了随机游走与Word2Vec的思想,本小节将分4个步骤介绍该模型.

（1）提取用户访问序列.如图4所示,对同一个用户来说,如果其连续访问两个兴趣点的时间不超过ΔT,则这两次连续访问在同一个用户访问序列中.

图4 提取用户序列

（2）兴趣点-兴趣点有向图构造.如图5所示,根据步骤（1）已经提取完成的用户访问序列,建立兴趣点-兴趣点有向图G.

图5 构建有向图

（3）随机游走.本步骤采用了DeepWalk[13]的思想,如图6所示,根据步骤（2）已经建立好的有向图进行随机游走:从一个节点出发,按照一定的概率随机移动到其邻居节点,并将该节点作为新的当前节点,执行数次这样的步骤,得到一条游走路径,其中每次从当前节点vi移动到其邻居节点vj的概率如式（6）所示.

图6 随机游走

（4）生成兴趣点Embedding.此处采用了Word2Vec中skip-gram模型的思想,将步骤（3）得到的游走序列看作文本数据输入到模型中,其目的是最大化同一序列中两个节点之间共现的概率,因此训练得出的这两个节点在Embedding空间中很接近.如图7所示,通常可以采用output matrix作为所有节点的Embedding集合.

图7 生成兴趣点Embedding

2.2 改良Embedding生成模型

本小节主要介绍针对2.1节步骤（4）生成兴趣点Embedding的改良工作,主要分为以下两点:

（1）兴趣点与其辅助信息融合.在2.1节步骤（4）中,模型只利用了兴趣点本身的信息输入到网络中,并没有利用到类似于兴趣点种类这样的辅助信息,如此学习得出的兴趣点Embedding蕴含的信息比较单一,不能够很好地缓解冷启动问题.加入兴趣点辅助信息后,神经网络能够挖掘出深层次的兴趣点信息,让Embedding含义变得更加丰富.

Eq为融合后的兴趣点 q的Embedding,通过这样的方式,在Embedding空间中,辅助信息相似的兴趣点之间的距离就会比较相近,缓解了兴趣点推荐中的冷启动问题.

（2）在上述（1）中,式（2）的融合方式是基于这样一个前提:所有的辅助信息对于兴趣点Embedding的重要程度都是一致的.这显然不符合实际,例如某用户要前往健身房运动,此时健身房的兴趣点种类（运动）要比健身房的品牌更加趋近于用户访问该兴趣点的原因.因此,不同的辅助信息对于兴趣点的重要程度是不一致的,针对此,本文提出了基于注意力机制的兴趣点辅助信息融合方法.

2.3 GE-GRU模型网络结构

如图8所示,GE-GRU模型网络的整体架构分为GE和GRU所示,首先通过GE训练出兴趣点的Embedding表示,再将此Embedding表示当作基于GRU的网络中的Embedding层的初始化参数,这一步桥接了模型的两个部分,使得蕴含深层次信息的兴趣点Embedding能够顺利输入到GRU网络中进行训练,从而使得后续的神经网络能够拥有良好的输入,提高了训练的质量.

图8 GE-GRU整体模型

具体的GE结构如图9所示,SI0,SI1,…,SIn表示兴趣点本身及其n个辅助信息,第1步对兴趣点及其辅助信息进行简单Embedding表示,第2步将各Embedding表示采用注意力机制,按式（2）的方式结合成新的兴趣点Embedding.模型的最后一层是sampled Softmax,Softmax函数的一种变体.训练完成后,采用模型输出层的output matrix作为所有兴趣点Embedding的矩阵集合.

图9 GE模块框架

2.4 损失函数

可将模型最终的任务看作一个多分类任务,即若该任务中共有N个兴趣点,每次推荐都是在进行一次N分类,挑选出评分排名最靠前的k个兴趣点进行推荐,而多分类的损失函数通常使用交叉熵损失函数来表示.

交叉熵能够衡量同一个随机变量中的两个不同概率分布的差异程度,在机器学习中就表示为真实的概率分布和预测的概率分布之间的差异,交叉熵的值越小,其模型预测效果就越好.在多分类问题中,交叉熵通常与Softmax函数一起出现,Softmax函数将模型输出的结果进行处理,使其所有分类的预测值和为1,再通过交叉熵来计算损失.最终损失函数如式（9）所示.

其中,q 为模型预测的概率分布,而 p为真实的概率分布,模型的目的就是不断缩小预测的概率分布与真实的概率分布之间的差异,差异越小,实验效果就越好.

2.5 训练方法

GE-GRU每次单独处理一条分割好的序列,采用mini-batch梯度下降的方法对模型进行训练.batch_size即每次训练的样本数量,当batch_size太小比如1时,每一个训练数据都要进行权值更新,这样就舍弃了向量化处理带来的加速; 当batch_size太大如全部样本都算为一个batch,全部数据训练完才进行一次权值更新,在数据量大时,单次迭代时间太长.综合考虑,本实验将batch_size定为512,采用Adam优化器对损失函数进行优化.

Adam优化器结合了AdaGrad和RMSProp两种优化器的优点,其实现简单,计算高效,对内存需求少;参数更新不受梯度伸缩变换的影响,并且非常适用于大规模的数据以及参数的场景,十分符合本文的需求.

3 实验

3.1 数据集介绍

本文使用的Foursquare数据集[18]是一个典型的基于位置的社交网络数据集,时间跨度从2010年4月至2011年9月,地理范围集中在美国加利福尼亚州.具体数据如表1所示.

表1 Foursquare数据集参数

3.2 数据预处理

本文采用了Cheng等[5]的方法对用户访问序列做了分割处理,即将同一用户访问序列中,如果连续两次访问之间的时间间隔不超过6 h,则将其编入同一序列之中,若超过6 h,则编入不同序列中.同时,为了防止不活跃用户与不活跃兴趣点对数据集的影响,本文还过滤掉了总check-ins数少于5条的用户和兴趣点,以及对用户序列分割后少于5条访问序列的用户.

如表2所示,在数据增强前,数据集提取出的有效用户移动序列数为13 830条,数据增强后,序列总数扩充到了119 142条.深度学习的特性是样本数量越多,其效果越明显.在数据增强前,总样本数量仅有13 830条,用于训练的样本数量仅有9681条,样本太少的情况下,神经网络几乎无法学习出隐藏于序列中的知识,所以实验效果很差.

表2 样本数量对比

3.3 Baseline方法介绍

（1）FPMC-LR[5]:基于矩阵分解和马尔科夫链的兴趣点推荐模型,依据矩阵分解学习所有用户的整体偏好,通过兴趣点转移矩阵的马尔科夫链来挖掘出人们在时间维度的移动模式.

（2）LSTM[20]:长短期记忆网络,通过遗忘门来选择性遗忘上个cell传入的信息,通过输入门来选择需要记忆多少当前cell中新的信息,通过输出门输出隐层信息.

（3）GRU[21]:门控循环单元,整体结构与LSTM类似,不同之处在于其将遗忘门和输入门合二为一成更新门.

3.4 评价指标

本文采用了兴趣点推荐中常用的Accuracy@k指标来评价实验结果,具体定义如下:

在某一次推荐中,计算所有兴趣点的排序分数,按照从高到底编入一个列表,其中真实标签兴趣点所在的排序位置为,如果m≤k,则称该次推荐命中,记为hit=1,否则hit=0.最终结果如式（10）所示.

3.5 实验结果分析

本文采用Accuracy@1,Accuracy@5,Accuracy@10,Accuracy@15,Accuracy@20五种评价标准.实验结果如表3所示.

表3 对比实验

相较于传统推荐方法FPMC-LR与深度学习推荐方法LSTM、GRU,GE-GRU在Foursquare数据集上效果最优,在Accuracy@10这一指标上,GE-GRU的效果为0.467,优于GRU 3%,优于LSTM 7%.在其他Accuracy指标上,仅在Accuracy@20上,GE-GRU效果稍逊于FPMC-LR,且相差不多.在k越来越大时,其同时推荐的兴趣点个数也增加了,推荐成本也增加了.这说明在将序列数据输入到GRU网络之前,通过GE学习得出的兴趣点Embedding,在很好地融合了其辅助信息后,挖掘出了兴趣点深层次的信息,使得兴趣点Embedding蕴含的内容更加丰富,从而让用户访问序列表示更加准确.

4 结论

本文在基于位置的社交网络背景下,采用了数据增强方法,丰富了用户访问序列数量,通过图嵌入技术对兴趣点及其辅助信息在注意力机制下融合,得到的兴趣点Embedding挖掘出了深层次的信息,将此Embedding输入到GRU中能够捕捉到用户近期偏好.实验结果表明,本文的GE-GRU方法能够有效地提升兴趣点推荐的准确率,并且能够缓解数据稀疏与冷启动的问题.