基于LSTM与距离优化的兴趣点推荐方法①

张大千,尹广楹

(中国石油大学(华东) 计算机科学与技术学院,青岛 266580)

1 引言

兴趣点(Point-Of-Interest,POI)推荐是个性化推荐方向中的一个分支,其目的在于根据用户访问兴趣点的轨迹日志以及两者本身的特征,为用户推荐符合其偏好的兴趣点[1].在基于位置的社交网络(Location-Based Social Networks,LBSN)中,用户通过移动设备上的应用在附近的兴趣点签到,从而分享自己所处的位置,以生成属于自己的兴趣点行为轨迹.而兴趣点推荐算法从某种意义上讲,是基于用户在LBSN 中的轨迹所研究或改进的一种面向兴趣点的推荐算法.

目前为止,兴趣点推荐相关的研究主要以用户的兴趣点访问序列、访问频次以及用户本身所具有的社会关系网为基准进行推荐.其中,基于序列的推荐方法对兴趣点访问序列进行时空上下文信息的挖掘,从而推测出用户在下一时刻可能将要访问的兴趣点.基于访问频次的兴趣点推荐方法则是将用户在LBSN 中所产生的签到数据转化为用户-兴趣点矩阵,其元素为用户对该兴趣点的总共访问次数,从而将兴趣点推荐任务转化为一般的用户-物品矩阵的空缺项填充任务(即矩阵分解).而基于社交关系网的推荐方法则是根据用户关系网所延展到的其它用户信息,以及用户之间的访问轨迹相似度,为用户进行推荐.

在基于访问频次的兴趣点推荐方法中,针对用户未访问过的兴趣点,其偏好程度能够被有效地预测出来.然而该方法没有考虑到用户本身和兴趣点的地理位置关系,以及用户签到数据的时间关系.同理,基于社交关系网的推荐方法将用户相似度的计算过程以关系网数据进行强化,从而使相似用户的推理以及兴趣点的推荐更具有合理性,但同样没有考虑到用户偏好的时空上下文关系.因此,基于序列和时空上下文信息的方法适用于兴趣点访问序列的推荐,以局部的角度来讲,此方法最有可能实现低访问代价下用户对偏好兴趣点的访问需求,但其推荐的产生方式类似于贪心算法,即根据前n项的兴趣点访问记录生成用户下一个最有可能访问且代价相对较小的兴趣点.在不强调兴趣点访问顺序以及特定访问(必须经过的)兴趣点的情况下,局部访问代价最小不全等于全局访问代价最小.图1为理想状态下兴趣点的推荐结果.

图1 兴趣点推荐示例

基于上述兴趣点推荐的相关研究可以发现,大部分的兴趣点推荐研究成果将LBSN 的信息作为用户喜好的参考进行推荐,完全没有考虑到用户是否有必要访问最符合喜好的兴趣点,以及访问兴趣点所付出的距离代价.而另外一小部分的研究成果虽然考虑到了兴趣点的地理位置以及距离关系为用户进行推荐,但究其细节,很难做到以全局最优为考量满足低访问代价下用户对偏好兴趣点的访问需求.因此,针对上述问题,本文提出了一种基于序列挖掘与距离损失优化的兴趣点推荐方法.其中,序列挖掘的目的在于通过用户的兴趣点访问历史序列总结出用户所感兴趣的兴趣点特征,而距离损失优化的目的在于使兴趣点序列所产生的整体访问代价达到最小.

2 相关工作

如引言所述,许多兴趣点推荐相关的研究基于LBSN 的信息对兴趣点的推荐序列进行优化,力求所生成的兴趣点候选项能够尽可能地符合用户的偏好.其中,一部分基于协同过滤的算法以LBSN 中的签到数据为基准对用户的兴趣点偏好进行预测.例如文献[2]中所提出的模型,将用户与兴趣点之间产生的交互数据转化为矩阵,以矩阵分解的形式预测用户对未曾到达过的地点的偏好程度.

相当一部分融合社交关系信息优化矩阵分解的方法以直接相连的用户间关系为基准对算法模型进行优化.在实际的应用场景中,具有直接关系的用户被认为具有相似的偏好,因此可以当作推荐的依据.基于此,以社交关系信息与评分信息相结合的推荐模型成为主流,如Ma 等所提出的SoRec 模型[3]以及Guo 等所提出的TrustSVD 算法[4].此外,在文献[4]的工作中,用户间的直接社交关系以及评分信息被整合为一个混合矩阵,基于该混合矩阵,Guo 等提出了基于随机梯度下降的分解算法.

然而,所有基于协同过滤的推荐算法具有一定的共性,即侧重于用户对项目所产生的交互值(如评分)而非用户或项目本身,因此该算法无法充分运用兴趣点或用户本身的信息完善其推荐性能.并且,在现实世界中,用户的兴趣点访问轨迹重合率较低,因此对于协同过滤相关的算法,其性能将受到数据稀疏性的制约.针对此类问题,许多有关协同过滤的研究成果以用户-项目交互值之外的信息作为补充,避免数据稀疏性带来的负面影响.

在基于LBSN 的信息中,用户的兴趣点访问轨迹以及兴趣点的地理位置也是推荐算法的重要考虑因素.在龚卫华等[5]提出的基于社区发现的兴趣点推荐方法中,兴趣点按照地理位置被归类为多个簇,根据多个簇所凸显出的喜好特征,用户相对于地理位置簇的隶属度(即喜好程度)被计算出来,从而由面及点,将隶属度高的地理位置簇中的兴趣点推选给相应的用户.基于社区发现的方法侧重于利用用户本身所携带的社区关系网以及兴趣点位置为用户生成兴趣点候选项,充分利用LBSN 中的信息进行推荐.但此方法将兴趣点地理位置作为偏好因素为用户生成推荐列表,并没有将兴趣点地理位置所隐含的访问距离代价考虑在内,在兴趣点次序以及必要性需求较弱的情况下,所推荐的兴趣点序列可能脱离用户的实际要求.

序列推荐是推荐算法的一个子集,其目的在于以用户对物品产生的交互作为历史依据,为用户生成一系列符合其偏好的推荐候选序列.在实际的应用中,用户对物品的偏好可能会随着时间的推移产生变化,因此有必要利用时空上下文相关的信息对推荐算法进行进一步优化.考虑到上述问题,Koren 等在矩阵分解的过程中所产生的偏置信息同时间变量建立映射关系,提出timeSVD[6]模型.但从现实意义上来讲,用户兴趣与时间的映射关系因人而异,简单的线性关系不能够完整准确地描述用户随时间推移产生的兴趣变化.因此,基于序列的推荐更偏向于对用户历史行为建模而非对用户兴趣与时间变量的映射关系建模.

针对推荐任务中用户交互序列所隐含的复杂时空上下文关系,RNN和CNN 的思想也被应用于序列推荐中.Hidasi 等针对大部分推荐系统只能根据短时的会话记录进行推荐,而不能根据长时间的用户行为记录进行有效推荐的问题,对传统RNN 进行了修改,使之更适应于序列化推荐[7].Tang 等提出CASER[8]模型,这是一种基于CNN 思想实现的推荐模型,目的是来预测用户未来可能有交互行为的前n个物品的排序.该模型的主要思想是将一系列最近产生交互的物品嵌入到时间和潜在空间所对应的“图像”中,并使用卷积滤波器学习交互序列作为图像的局部特征.

在兴趣点推荐任务中,用户的兴趣点访问序列具备完整的时空信息.在蒋宗礼等[9]的研究成果中,兴趣点推荐问题被转化为根据用户的历史访问序列预测未来兴趣点序列的问题.在用户的兴趣点历史访问序列中,兴趣点之间的转移概率,即用户从其中一个兴趣点在若干步以内转移至下一个兴趣点的概率,通过统计学的方式计算出来.根据兴趣点之间的转移概率,受到NLP 领域中Skim-gram 方法的启发,以长文本中词预测的方式对用户将要访问的下一个兴趣点进行预测.在强调兴趣点先后顺序的情况下,本方法能够在局部意义上实现为用户推荐访问代价较小且符合习惯的兴趣点访问序列.然而,在现实环境中,存在相对一部分用户,其行为轨迹中对兴趣点的访问顺序并非如句子中的词向量一样具有明显的先后关系,兴趣点之间的转移概率可能差别并不大.因此从全局的角度来看,此类方法不适用于这部分用户的兴趣点推荐.

此外,在实际的应用中,用户并不是在任何时候都对自己所经过的兴趣点信息实时上报.在本文所使用的数据集中,LBSN 信息仅仅包含用户之间简单的关系网以及兴趣点的访问轨迹,并不包含交互类的附加信息(如评分或文本评价).由于用户的行动距离有限,用户之间的兴趣点轨迹重合程度普遍较低,其数据稀疏性比一般的电商平台中的用户订单数据可能还要高,针对未访问过的兴趣点不能单纯以用户相似度做出准确的喜好估计.由此可见,兴趣点推荐虽然是推荐领域中的一个分支,但其所要考虑的因素比一般的推荐算法要广,用户对兴趣点的偏好往往与用户的行动能力、兴趣点的相对距离以及用户本身的社交网(邻近用户的偏好)有关.因此,本文提出了一种兼顾用户偏好以及访问代价的兴趣点推荐方法,旨在将上述信息进行整合,为用户生成符合现实情况的兴趣点访问序列.

3 算法模型

首先,基于LBSN 的兴趣点推荐任务可以表述如下:设U={u1,u2,···,un}为用户集合,而待推荐的兴趣点集合为L={l1,l2,···,lm}.对于集合U中的每一个用户ui,存在按照时间从先到后排序的交互序列Hi={hi1,hi2,···,hit|hij∈L,j∈[0,t]}.此外,在LBSN 中用户之间的关系以图的形式表征,设为G.在关系网G中,每一个节点代表一个用户,而用户之间的边代表两个用户之间存在关系.根据以上数据,预测用户将来可能访问的若干个兴趣点POIi={li1,li2,···,lik|lij∈L,j∈[0,k]},并保证这组兴趣点兼顾用户的偏好以及访问兴趣点所产生的距离代价因素.

针对上述推荐任务,本文提出了如图2所示的算法模型.该算法模型首先将用户与兴趣点的交互矩阵以社交关系信息进行补充,之后对补充后所生成的混合矩阵进行分解.最后,根据用户对兴趣点的访问记录,对矩阵分解的过程中所生成的兴趣点隐向量建立时序关系,以类递归形式的模型对序列进行学习,从而推断出用户将来可能访问的兴趣点.

图2 模型结构

3.1 基于社交距离的混合矩阵

在兴趣点推荐的实际应用环境中,根据访问频次所形成的用户-兴趣点交互矩阵往往表现出较高的稀疏性.通过LBSN 中给定的社交关系网,交互矩阵得以稠密化,为下一步的矩阵分解以及用户或兴趣点的隐特征向量生成做准备.

然而,直接相连的社交关系对相似用户的喜好挖掘并不充分,在现实世界中具有间接关系的用户之间也具有一定的联系.考虑到LBSN 中所提供信息的局限程度,本文参考了文献[4]中的思想,以用户之间的关系距离为参考,将用户社交关系信息以及用户-兴趣点的交互信息整合为混合矩阵.

针对每一个用户ui,其社交关系往往以一定的层级关系进行传递,且用户ui与其他用户之间的可达关系路径并不唯一.因此,用户ui对其本身在社交关系网中能够触及到的其他用户之间存在不同程度的亲疏关系.由于本文所使用的数据集中关系网所包含的信息较为简单(基本只有用户id 以及无向边关系),以用户ui通过关系网到达其他用户所产生的关系距离为准,衡量关系网中其他用户对用户ui的影响程度:

其中,s(i,k) 表示用户ui与uk之间的亲疏程度,而d(i,k)表示在关系网G中用户ui与uk之间所有可达路径的长度,一般为一组离散值.若用户ui无法通过关系网G找到uk,即两者之间根本不存在社交关系,那么两者之间的可达距离最小值m in(d(i,k))将会变为无限大;若i等于k,即uk指向用户自身,那么可达距离最小值为0.由上式可以看出,用户ui与uk之间的最短关系路径长度越小,两者的亲密程度就越高.根据亲疏程度s(i,k)以及用户关于兴趣点的表征向量ui,稠密化的新向量rui得以计算,将每一个rui按行进行组合表示,即可获得新的稠密化交互矩阵.

根据用户间社交关系亲疏程度将矩阵稠密化的步骤可概括如下:

1)对于用户-兴趣点交互矩阵的每一行,可看作用户ui关于兴趣点的表征向量,而向量的每一列fij值代表ui对兴趣点lj的访问次数.即

2)对每一个用户ui,根据其社交关系网中与其他用户的亲疏程度以及其他用户的表征向量,进行加权整合,生成新的稠密化用户向量rui:

3)将每一个用户向量rui以行的形式整合为交互矩阵R,并且以特定的方式将R中的元素缩放至一定的区间内,以提高算法模型收敛的速度及效果.在原本的用户-兴趣点交互矩阵中,元素的值表示特定用户对某个兴趣点所产生的访问次数,由于数据的分布并非固定在一定的值域内,故使用标准化的方式将R中的元素进行线性变换,使其值分布于[−1,1]之间.

至此,原本的用户-兴趣点交互矩阵以用户关系网信息作为参考,经过稠密化与标准化形成新的矩阵R,对其进行矩阵分解,可得到用户或兴趣点的隐特征向量表示.

3.2 带偏置项的矩阵分解

在上一小节中,融合用户社交关系以及兴趣点访问次数的混合矩阵已经构建完成,依据SVD 的思想,考虑到偏置信息[10],矩阵中的每一个元素可表示为:

其中,pi表示用户的隐特征向量,qj表示兴趣点的隐特征向量,而bi和bj分别表示用户和兴趣点的偏移量,µ表示混合矩阵元素的全局偏移量.由于本文对混合矩阵的分解基于SVD 思想,因此拟合过程中采用随机梯度下降法优化以下损失函数:

可以看出,损失部分由两部分构成,前者为预测值与实际值rij之间产生的偏差,而后者为所生成的隐特征向量的模.该损失函数的目的在于同时兼顾高准确率与隐特征向量的低复杂度.

3.3 基于LSTM与距离优化的序列推荐

为了充分利用用户的兴趣点访问序列中所隐含的上下文信息优化推荐性能,将长短期记忆网络的思想应用于基于序列的推荐任务中.长短期记忆网络(Long-Short Term Memory,LSTM)基于RNN 改进,是一种对时间序列所隐含的信息进行挖掘的模型,能够有效避免序列元素的长依赖问题.在本文所使用的Gowalla 数据集中,用户的兴趣点访问序列长度最多可达1600 左右,宜用LSTM 进行处理.

根据Li 等[11]的分析,在实际的推荐任务中,用户的决策过程受到其当前动机和长期偏好的影响.针对两种不同的影响因素,Li 等所提出的行为神经网络针对用户的短期访问行为和历史访问记录分别建立两种不同的LSTM 进行学习,最终以一个全连接网络将两种LSTM 的输出进行汇总,得到用户的下一项可能访问的物品.以Li 等所提出的算法模型作为参考,本文对LSTM 中的损失函数进行改进.改进后的模型能够综合考虑用户喜好以及访问代价,并给出相应的推荐结果.

在原本的LSTM 损失函数中,兴趣点的预测向量与真实表征向量之间的均方误差(Mean Squared Error,MSE)被用来衡量模型的准确度,其推荐结果更偏向于用户的喜好.为了使模型在关注用户喜好的同时能够兼顾兴趣点序列中的距离要素进行推荐,本文提出了基于距离优化的LSTM 模型(LSTM based on Distance Optimization,DO-LSTM),对原本的损失函数做出了如下改进:

该算式中,H表示n个用户序列的集合,即H={H1,H2,···,Hn};ts表示LSTM 训练过程中所采用的时间步长.对于每一个用户i的兴趣点访问序列Hi,以Hi中的前ts项作为输入,所产生的结果应该与Hi中的后|Hi|−ts−1|项形成的子序列保持较小的隐特征向量误差,即每一时刻的MS E(,qt)达到最小,而序列内部的兴趣点距离代价D(Li)不宜过高.因此,该损失函数主要由两部分组成:偏好兴趣点的预测误差以及预测序列的距离代价.其中,偏好兴趣点的预测误差等于每个时刻t中的兴趣点预测值与真实值的MSE 之和,和qt分别表示出现在t时刻的预测值和真实值;而序列的整体距离代价D(Li)由相邻时刻内兴趣点之间的距离依次相加而得,pos()表示预测值所对应的地理位置(一般取预测值最为相似的兴趣点向量所在的地理位置),dist(pos(),pos()) 则表示与之间的距离,采用欧式距离公式进行计算.τ为超参数,用以调节距离代价所占的比重.

在训练的过程中,使用自适应梯度算法(AdaGrad)[12]方法对该损失函数进行最小化.AdaGrad 以每次迭代的历史梯度平方和为分母调整模型中不同参数的学习率,能够更有效地使模型收敛.

最终,如图2所示,LBSN 中的用户-兴趣点交互信息首先以社交网数据为辅助信息形成混合矩阵;基于该混合矩阵,用户和兴趣点的隐特征向量被提取;最后,根据用户的兴趣点访问序列以及所提取的兴趣点特征向量,以序列中所隐含的时空上下文关系为用户推荐一组符合用户偏好以及距离要求的兴趣点.

4 实验

本文使用Gowalla和Yelp 的数据进行研究与实验.Gowalla 数据集中包含了32 510 个地点与18 737 个用户的兴趣点访问轨迹,共计1278 274 条签到数据.Yelp 数据集中包含了30 887 个地点与18 995 个用户的兴趣点访问轨迹,共计860 888 条签到数据.此外,在两个数据集中均包含用户关系网数据.

4.1 实验设置

对于这两种数据集,本文按时间顺序取前80%的数据为训练集,后20%的数据为测试集.在基于LSTM与距离优化的序列推荐模型中,兴趣点本身的推荐准确率要比兴趣点的排序正确程度更加重要,且兴趣点的排序并非单纯依赖于用户的偏好,而是综合考虑了访问兴趣点所产生的距离损失.因此,以Precision@N 衡量模型的推荐性能,即在未来的长度为N的序列中,用户接下来确实要访问的兴趣点所占的比例.

本文选取了以下几种算法模型进行实验对比:

1) 基于协同过滤(CF)的推荐算法:在近百万条签到数据中,对每一个用户寻找访问过相同兴趣点的用户,并标记为此用户的近邻用户.根据近邻程度,即目标用户与近邻用户的兴趣点偏好相同程度,为目标用户推荐近邻用户所偏好的兴趣点.此类方法同样不关心用户或兴趣点本身的特征,近邻用户的计算基于用户与兴趣点的交互行为.

2) 基于奇异值分解(SVD)的算法:SVD 类模型试图将用户-兴趣点之间的交互数据转化为以用户id为行、以兴趣点id为列、以用户对兴趣点访问频次为元素值的矩阵,以矩阵元素实际值与分解项相乘所得的预测值之间的误差为损失函数进行训练.通过SVD 模型,矩阵被分解为两个更小规模的矩阵,矩阵的行或列代表每一个用户或兴趣点的隐特征向量.SVD 的目的在于对未访问部分进行访问频次预估,从而全面挖掘用户偏好的兴趣点,并按照频次大小排序推荐给用户.本实验中,使用biasedSVD[10]模型进行测试.

3) 基于自注意力机制(self-attention)的算法:多用于NLP 领域中语义分析相关的任务中,其目的是根据整个句子中词语之间的联系,判断出相对值得注意,即能够完整表述句子意义的部分.而AttRec[13]模型则是将用户的兴趣点访问序列看作NLP 中的“句子”,并通过自注意力机制判断序列中用户最为关注的兴趣点,该兴趣点往往能够全局性地代表用户访问序列所隐含的整体偏好.

4) 基于长短期记忆网络(LSTM)与距离优化的算法:即本文所提出的DO-LSTM 模型.该模型参考了LSTM在语义分析任务中的用途,根据兴趣点之间的时空上下文推断用户在未来的n个时刻可能访问的兴趣点.和其它的基于序列的推荐算法不同,本模型对未来序列的预测并不完全依赖于用户的喜好,兴趣点的可达性(即访问代价)也是该模型的关注点之一.

4.2 实验效果

取τ=0.7作为损失函数中距离代价所占比重,分别以N=5/10/20 对4 个算法模型分别在Gowalla和Yelp的数据所表现出的性能进行评估,实验结果如图3.

图3 Gowalla和Yelp 数据集中的准确率对比柱状图

由图3可以看出,在完整性有限的数据集中,DOLSTM 模型所表现出的准确率与召回率比其它的算法模型较好.

5 结论与展望

本文对兴趣点推荐研究相关的现状进行分析,针对兴趣点偏好推荐以及兴趣点可达性提出DO-LSTM模型.相比于其它的兴趣点推荐模型,该模型能够在兴趣点交互信息较为促狭的情况下为用户生成一系列偏好的兴趣点,且这些兴趣点对当前用户具有较好的可达性.然而,在兴趣点推荐领域中,本模型仍然具有需要改进的地方:

首先,该模型能够仅根据LBSN 中用户-兴趣点的访问序列、兴趣点地理位置以及简单的用户社交关系网为用户生成相对准确且完整的偏好兴趣点.然而该模型在丰富的LBSN 数据中的性能表现可能不如其它模型,如基于地理-社会-评论关系的推荐方法[14]以及融合地理信息的推荐方法[15],这两种模型分别将评论关系以及兴趣点详细信息作为参考因素优化推荐性能.因此在后续的改进工作中,将继续收集兴趣点的详细信息以及用户-兴趣点评论关系,对模型进行重新设计.

其次,由于用户社交关系网信息过于简单,仅包含成对的用户id 信息,该模型对该信息的利用并不充分,仅以用户之间的社交关系距离为考量预估用户对兴趣点的偏好程度.而改进的方向主要分为两个方面:一是丰富社会关系网的边信息,使关系类型有所区分(如朋友关系、父母关系等).二是使用图神经网络(Graph Neural Networks,GNN)[16]等更加精确的模型分析社交网中每一个用户与其它用户的相互影响程度,从而准确地评估出当前用户在其它近邻用户的影响下对兴趣点的偏好.

综上,在未来的工作中,本模型将根据以上不足之处进行改进,使其能够用于更加复杂的业务环境中.