第16卷第3期 智能系统学报 Vol.16 No.3 2021年5月 CAAI Transactions on Intelligent Systems May 2021 D0L:10.11992tis.202004009 基于时空循环神经网络的下一个兴趣点推荐方法 柴瑞敏，殷臣，孟祥福，张霄雁，关昕，齐雪月 (辽宁工程技术大学电子与信息工程学院，辽宁葫芦岛125105)】 摘要：下一个兴趣点推荐已经成为基于位置的社交网络(location--based social networks,,LBSNs)中一个重要任 务。现有的模型没有深入考虑相邻签到兴趣点之间的转移时空信息，无法对用户访问下一个兴趣点的长短时 间偏好和远近距离偏好进行有效建模。本文通过对循环神经网络(recurrent neural network,RNN)进行扩展，提 出一个新的基于会话的时空循环t神经网络模型(sesson-based spatial--temporal recurrent neural network,SST RNN)用于下一个兴趣点推荐。该模型通过设置时间转移矩阵和空间转移矩阵分别对用户的时间和空间偏好 信息进行建模，综合考虑连续签到兴趣点的序列信息、时空信息以及用户偏好进行下一个兴趣点推荐。通过 在2个真实公开的数据集上进行实验，结果显示本文提出的SST-RNN模型的推荐效果比主流的推荐模型有显 著提升。在Foursquare和CA数据集上，ACC@5评价指标分别提升了36.38%和13.81%，MAP评价指标分别提 升了30.72%和17.26%。 关键词：下一个兴趣点推荐：基于位置的社交网络：循环神经网络；序列信息：时间偏好：空间偏好：用户偏好： 会话 中图分类号：TP183文献标志码：A文章编号：1673-4785(2021)03-0407-09 中文引用格式：柴瑞敏，殷臣，孟祥福，等.基于时空循环神经网络的下一个兴趣点推荐方法，智能系统学报，2021,16(3)： 407-415. 英文引用格式：CHAI Ruimin,YIN Chen,MENG Xiangfu,etal.A recurrent neural network model based on spatial and temporal information for the next point of interest recommendation J.CAAl transactions on intelligent systems,2021,16(3):407-415. A recurrent neural network model based on spatial and temporal information for the next point of interest recommendation CHAI Ruimin,YIN Chen,MENG Xiangfu,ZHANG Xiaoyan,GUAN Xin,QI Xueyue (School of Electronic and Information Engineering,Liaoning Technical University,Huludao 125105,China) Abstract:The next point-of-interest (POl)recommendation has become an important task in location-based social net- works.The existing models lack in-depth research on the temporal and spatial information transition between adjacent check-in POIs and cannot effectively model the long/short time and distance preferences of the users accessing the next POI.In response,this paper proposes a new session-based spatial-temporal recurrent neural network(SST-RNN)model that is used to recommend the next POI.This model takes advantage of the spatial transition matrix and temporal trans- ition matrix to respectively model the user's spatial and temporal preferences,and comprehensively considers the se- quence information and spatial-temporal information of consecutive check-in POIs as well as user preferences to do the next POI recommendation.Experimental results in two real open datasets show that the performance of the proposed SST-RNN model is significantly enhanced compared with the state-of-the-art models.On the Foursquare and CA data- sets,the ACC@5 is increased by 36.38%and 13.81%,and the MAP is increased by 30.72%and 17.26%,respectively. Keywords:next point of interest recommendation;location-based social networks,recurrent neural network;sequence information;temporal preferences;spatial preferences;user preferences;session 收稿日期：2020-04-09. 基金项目：国家自然科学基金面上项目(61772249) 随着基于位置的社交网络发展，一些基于位 通信作者：孟祥福.E-mail:marxi(@I26.com. 置服务的社交软件被广泛使用，如Foursquare
DOI: 10.11992/tis.202004009 基于时空循环神经网络的下一个兴趣点推荐方法 柴瑞敏，殷臣，孟祥福，张霄雁，关昕，齐雪月 （辽宁工程技术大学 电子与信息工程学院，辽宁 葫芦岛 125105） 摘 要：下一个兴趣点推荐已经成为基于位置的社交网络 (location-based social networks，LBSNs) 中一个重要任 务。现有的模型没有深入考虑相邻签到兴趣点之间的转移时空信息，无法对用户访问下一个兴趣点的长短时 间偏好和远近距离偏好进行有效建模。本文通过对循环神经网络 (recurrent neural network, RNN) 进行扩展，提 出一个新的基于会话的时空循环神经网络模型 (sesson-based spatial-temporal recurrent neural network, SSTRNN) 用于下一个兴趣点推荐。该模型通过设置时间转移矩阵和空间转移矩阵分别对用户的时间和空间偏好 信息进行建模，综合考虑连续签到兴趣点的序列信息、时空信息以及用户偏好进行下一个兴趣点推荐。通过 在 2 个真实公开的数据集上进行实验，结果显示本文提出的 SST-RNN 模型的推荐效果比主流的推荐模型有显 著提升。在 Foursquare 和 CA 数据集上，ACC@5 评价指标分别提升了 36.38% 和 13.81%，MAP 评价指标分别提 升了 30.72% 和 17.26%。 关键词：下一个兴趣点推荐；基于位置的社交网络；循环神经网络；序列信息；时间偏好；空间偏好；用户偏好； 会话 中图分类号：TP183 文献标志码：A 文章编号：1673−4785(2021)03−0407−09 中文引用格式：柴瑞敏, 殷臣, 孟祥福, 等. 基于时空循环神经网络的下一个兴趣点推荐方法 [J]. 智能系统学报, 2021, 16(3): 407–415. 英文引用格式：CHAI Ruimin, YIN Chen, MENG Xiangfu, et al. A recurrent neural network model based on spatial and temporal information for the next point of interest recommendation[J]. CAAI transactions on intelligent systems, 2021, 16(3): 407–415. A recurrent neural network model based on spatial and temporal information for the next point of interest recommendation CHAI Ruimin，YIN Chen，MENG Xiangfu，ZHANG Xiaoyan，GUAN Xin，QI Xueyue (School of Electronic and Information Engineering, Liaoning Technical University, Huludao 125105, China) Abstract: The next point-of-interest (POI) recommendation has become an important task in location-based social networks. The existing models lack in-depth research on the temporal and spatial information transition between adjacent check-in POIs and cannot effectively model the long/short time and distance preferences of the users accessing the next POI. In response, this paper proposes a new session-based spatial–temporal recurrent neural network (SST-RNN) model that is used to recommend the next POI. This model takes advantage of the spatial transition matrix and temporal transition matrix to respectively model the user’s spatial and temporal preferences, and comprehensively considers the sequence information and spatial–temporal information of consecutive check-in POIs as well as user preferences to do the next POI recommendation. Experimental results in two real open datasets show that the performance of the proposed SST-RNN model is significantly enhanced compared with the state-of-the-art models. On the Foursquare and CA datasets, the ACC@5 is increased by 36.38% and 13.81%, and the MAP is increased by 30.72% and 17.26%, respectively. Keywords: next point of interest recommendation; location-based social networks; recurrent neural network; sequence information; temporal preferences; spatial preferences; user preferences; session 随着基于位置的社交网络发展，一些基于位 置服务的社交软件被广泛使用，如 Foursquare、 收稿日期：2020−04−09. 基金项目：国家自然科学基金面上项目 (61772249). 通信作者：孟祥福. E-mail：marxi@126.com. 第 16 卷第 3 期 智 能 系 统 学 报 Vol.16 No.3 2021 年 5 月 CAAI Transactions on Intelligent Systems May 2021
·408· 智能系统学报 第16卷 Gowalla、Yelp等，人们可以轻松地通过签到的形 要用户提供其将要访问下一个兴趣点的距离间 式分享他们的位置和记录生活。同时，用户大量 隔。这有两方面的好处：首先根据用户的距离间 的签到信息也为探索人们的行为规律提供了机 隔，能够给用户提供更灵活的推荐，如果当前的 遇。下一个兴趣点推荐已经成为基于位置的社交 推荐列表用户不满意，用户可以有更多的灵活性 网络的重要任务。 去调整不同的距离间隔而得到不同的推荐列表， 然而，与传统的推荐系统（如音乐、视频和图 使用户能够与模型进行交互而不是只能得到固定 书推荐等)不同，时空属性对于兴趣点推荐起着 推荐列表；其次，根据用户提供的距离间隔，能够 很强的约束性：并且，在兴趣点的签到信息中，用 分析出用户此时表现的偏好模式（即近距离偏好 户并没有明确给出对兴趣点的喜爱或偏好。用户 或者远距离偏好)，进而根据用户的偏好给出个性 的隐式反馈信息以及地点签到信息存在稀疏性问 化的推荐列表。 题，因此下一个兴趣点的推荐极具挑战性。为了 时间信息在兴趣点推荐中也具有较大作用。 提高兴趣点的推荐效果，一些研究将序列信 用户偏好会随时间发生变化，用户在不同的时间 息)、时空信息B、社交关系以及签到兴趣点 间隔内会表现出不同的偏好。当用户要访问的下 的上下文信息整合到模型中。本文主要利用 一个兴趣点的时间点与当前用户时间点的时间间 签到信息中的序列信息、时间信息和空间信息进 隔较短时，模型应倾向于推荐用户较近的一些地 行下一个兴趣点推荐。 点。同时，利用相邻时间间隔信息也能提供一些 序列信息在下一个兴趣点推荐中扮演着重要 隐含的有价值信息。当用户从当前景点紧接着去 角色。一些研究通过整合用户历史签到序列信息 附近的下一个景点时，不同的用户在这两个兴趣 提升模型的效果，FPMC模型山通过结合矩阵分 点通常有相似的访问时间间隔。因此利用用户在 解和马尔科夫链捕获用户连续签到兴趣点之间的 相邻兴趣点之间的转移时间间隔有利于进行兴趣 序列影响。最近，一些研究采用RNN模型1用 点推荐。 于序列信息分析，基于循环神经网络(RNN)的方 由于RNN模型在序列建模中具有很好效果， 法能够更有效地捕捉序列数据之间的关系，因此 本文采用RNN模型对序列信息建模，通过对RNN 在兴趣点推荐中得到了广泛应用，并成为当前主 进行改进使其能够满足对用户变化的时空偏好信 流的推荐模型。然而，RNN存在梯度爆炸和梯度 息进行下一个兴趣点推荐。现有模型通常将用户 消失的问题，不能学习到较长序列内远距离的依 的整个签到序列作为RNN的输入用于下一个兴 赖关系。为了解决这个问题，长短时记忆(LSTM两 趣点推荐。而实际上，使用用户的整个签到记录 和门控循环单元(GRU)2种RNN变体被提出， 并不一定适用于实际的应用场景，随着用户签到 使得循环神经网络能够学习到长序列内远距离的 记录数量快速地增加，计算开销也随之增加。因 依赖问题。 此，本文仅根据最后一次会话信息用于下一个兴 空间信息是基于位置服务的基本属性，对 趣点推荐。为了对用户签到序列中用户变化的复 兴趣点的推荐同样起着重要作用。一些研究表 杂时空偏好进行建模，本文分别建立时间转移矩 明11，人们更倾向于访问距离用户当前位置较 阵和空间转移矩阵。时空转移矩阵由用户相邻签 近的地点。这些模型通过将距离作为权重系数或 到兴趣点之间的时空间隔信息确定；为了进一步 者根据兴趣点之间的距离进行聚类进而推荐位置 考虑用户的时间偏好，用户会话中的每个兴趣点 较近的兴趣点，限制了模型给用户推荐远距离的 与推荐兴趣点的时间间隔信息也被整合到模型 兴趣点。通过对实验数据集分析发现，在本文使 中。本文通过同时考虑用户的两类时间信息（包 用的Foursquare和CA数据集中，分别有24%和 括相邻兴趣点的时间间隔和会话中访问过的兴趣 42%的相邻签到兴趣点之间的距离间隔大于10km, 点与下一个兴趣点的时间间隔)、空间信息、签到 这说明用户多数情况下偏好访问距离较近的兴趣 序列信息和用户偏好给出个性化的下一个兴趣点 点，但也有较大比例用户依然偏好访问距离较远 推荐。 的兴趣点。在现有的下一个兴趣点推荐模型中， 1相关工作 大多数模型倾向于推荐较近的地点限制了模型的 表现，使得模型并不会自适应用户需求和偏好的 传统兴趣点推荐通常采用协同过滤算法。矩 变化而进行推荐，这也意味着模型推荐的兴趣点 阵分解920是协同过滤最常用的方法，其目标是 列表是固定不变的。为了解决上述问题，模型需 将“用户一兴趣点”隐式评分矩阵分解为2个低维
Gowalla、Yelp 等，人们可以轻松地通过签到的形 式分享他们的位置和记录生活。同时，用户大量 的签到信息也为探索人们的行为规律提供了机 遇。下一个兴趣点推荐已经成为基于位置的社交 网络的重要任务。 然而，与传统的推荐系统 (如音乐、视频和图 书推荐等) 不同，时空属性对于兴趣点推荐起着 很强的约束性；并且，在兴趣点的签到信息中，用 户并没有明确给出对兴趣点的喜爱或偏好。用户 的隐式反馈信息以及地点签到信息存在稀疏性问 题，因此下一个兴趣点的推荐极具挑战性。为了 提高兴趣点的推荐效果，一些研究将序列信 息 [1-2] 、时空信息[3-5] 、社交关系[6-8] 以及签到兴趣点 的上下文信息[9-12] 整合到模型中。本文主要利用 签到信息中的序列信息、时间信息和空间信息进 行下一个兴趣点推荐。 序列信息在下一个兴趣点推荐中扮演着重要 角色。一些研究通过整合用户历史签到序列信息 提升模型的效果，FPMC 模型[1] 通过结合矩阵分 解和马尔科夫链捕获用户连续签到兴趣点之间的 序列影响。最近，一些研究采用 RNN 模型[13] 用 于序列信息分析，基于循环神经网络 (RNN) 的方 法能够更有效地捕捉序列数据之间的关系，因此 在兴趣点推荐中得到了广泛应用，并成为当前主 流的推荐模型。然而，RNN 存在梯度爆炸和梯度 消失的问题，不能学习到较长序列内远距离的依 赖关系。为了解决这个问题，长短时记忆 (LSTM)[14] 和门控循环单元 (GRU)[15] 2 种 RNN 变体被提出， 使得循环神经网络能够学习到长序列内远距离的 依赖问题。 空间信息是基于位置服务的基本属性[16] ，对 兴趣点的推荐同样起着重要作用。一些研究表 明 [17-18] ，人们更倾向于访问距离用户当前位置较 近的地点。这些模型通过将距离作为权重系数或 者根据兴趣点之间的距离进行聚类进而推荐位置 较近的兴趣点，限制了模型给用户推荐远距离的 兴趣点。通过对实验数据集分析发现，在本文使 用的 Foursquare 和 CA 数据集中,分别有 24% 和 42% 的相邻签到兴趣点之间的距离间隔大于 10 km， 这说明用户多数情况下偏好访问距离较近的兴趣 点，但也有较大比例用户依然偏好访问距离较远 的兴趣点。在现有的下一个兴趣点推荐模型中， 大多数模型倾向于推荐较近的地点限制了模型的 表现，使得模型并不会自适应用户需求和偏好的 变化而进行推荐，这也意味着模型推荐的兴趣点 列表是固定不变的。为了解决上述问题，模型需 要用户提供其将要访问下一个兴趣点的距离间 隔。这有两方面的好处：首先根据用户的距离间 隔，能够给用户提供更灵活的推荐，如果当前的 推荐列表用户不满意，用户可以有更多的灵活性 去调整不同的距离间隔而得到不同的推荐列表， 使用户能够与模型进行交互而不是只能得到固定 推荐列表；其次，根据用户提供的距离间隔，能够 分析出用户此时表现的偏好模式 (即近距离偏好 或者远距离偏好)，进而根据用户的偏好给出个性 化的推荐列表。 时间信息在兴趣点推荐中也具有较大作用。 用户偏好会随时间发生变化，用户在不同的时间 间隔内会表现出不同的偏好。当用户要访问的下 一个兴趣点的时间点与当前用户时间点的时间间 隔较短时，模型应倾向于推荐用户较近的一些地 点。同时，利用相邻时间间隔信息也能提供一些 隐含的有价值信息。当用户从当前景点紧接着去 附近的下一个景点时，不同的用户在这两个兴趣 点通常有相似的访问时间间隔。因此利用用户在 相邻兴趣点之间的转移时间间隔有利于进行兴趣 点推荐。 由于 RNN 模型在序列建模中具有很好效果， 本文采用 RNN 模型对序列信息建模，通过对 RNN 进行改进使其能够满足对用户变化的时空偏好信 息进行下一个兴趣点推荐。现有模型通常将用户 的整个签到序列作为 RNN 的输入用于下一个兴 趣点推荐。而实际上，使用用户的整个签到记录 并不一定适用于实际的应用场景，随着用户签到 记录数量快速地增加，计算开销也随之增加。因 此，本文仅根据最后一次会话信息用于下一个兴 趣点推荐。为了对用户签到序列中用户变化的复 杂时空偏好进行建模，本文分别建立时间转移矩 阵和空间转移矩阵。时空转移矩阵由用户相邻签 到兴趣点之间的时空间隔信息确定；为了进一步 考虑用户的时间偏好，用户会话中的每个兴趣点 与推荐兴趣点的时间间隔信息也被整合到模型 中。本文通过同时考虑用户的两类时间信息 (包 括相邻兴趣点的时间间隔和会话中访问过的兴趣 点与下一个兴趣点的时间间隔)、空间信息、签到 序列信息和用户偏好给出个性化的下一个兴趣点 推荐。 1 相关工作 传统兴趣点推荐通常采用协同过滤算法。矩 阵分解[19-20] 是协同过滤最常用的方法，其目标是 将“用户−兴趣点”隐式评分矩阵分解为 2 个低维 ·408· 智 能 系 统 学 报 第 16 卷
第3期 柴瑞敏，等：基于时空循环神经网络的下一个兴趣点推荐方法 ·409· 矩阵，分别表示用户和兴趣点的潜在因子。然 同之处体现在：1)模型只使用用户最后的会话作 而，矩阵分解方法不适用于用户签到序列信息的 为RNN的输，具有更快的推荐速度；2)模型能够 建模。 根据用户的查询条件以及用户的偏好变化情况进 序列信息和时空信息是下一个兴趣点推荐的 行自适应调整，为相同用户推荐变化的个性化的 最基本要素。为了提升下一个兴趣点的推荐效 兴趣点推荐列表。 果，一些模型，如基于MC模型的方法、基于嵌 入的方法22]和基于神经网络RNN的方法，通过 2相关定义 整合序列信息和时空信息用于下一个兴趣点推 令U={山，2，…，4u}表示所有用户组成的集 荐。文献[1]提出了FPMC模型，该模型结合矩 合，P={P1,P2,…,P}和G={88,…,8n}分别表 阵分解和马尔科夫链对用户偏好和序列信息建 示兴趣点的集合及其对应兴趣点的地理坐标的集 模。文献[21]是FPMC模型的扩展，通过结合用 合，其中U和P分别表示用户数量和兴趣点数 户的地理位置约束为用户推荐下一个兴趣点。文 量。本文中用户和兴趣点的标识都用连续的整数 献[24]提出了POI2vec,该模型应用二叉树结构 编码，编码值从1开始。 对附近的兴趣点进行聚类，进而为用户推荐下一 定义1兴趣点(PO)。兴趣点是具有唯一标 个兴趣点。文献[17]提出了PRME-G,该模型利 识（编码）的地点，它包含经纬度信息。 用嵌人的方法，通过度量嵌入的方法整合兴趣点 定义2历史签到序列。某一用户“的历史 的序列信息和地理位置信息进行下一个兴趣点推 签到序列表示为H={,哈…，P,其中P%表示 荐。文献[22]提出了一种嵌入学习方法(GE)用 用户u在时刻访问过兴趣点P。 于兴趣点推荐，该方法利用二部图对POI推荐上 定义3下一个兴趣点推荐。给定用户的历 下文中的一对上下文进行建模，并通过对4对嵌 史签到记录，用户最后的签到位置信息以 入模型(POI-POI、POI-Time、POI-Regin和POI- 及查询条件Q=(△d,+),其中△d表示用户访问下 Word)进行统一优化。 一个兴趣点的距离间隔。下一个兴趣点推荐目标 然而，以上模型缺乏对用户连续签到的两个 是为用户推荐其在，时刻最有可能访问的TOP-K 兴趣点之间的转移时空信息的考虑，并且时间信 个兴趣点。 息和空间信息之间复杂的交互也被忽略。最近， 序列信息和时空信息也被广泛地整合到RNN网 3基于时空循环神经网络的兴趣点 络中。文献[25]提出了Distance2Pre模型，利用 推荐模型 GRU模型首次整合用户不同地理距离偏好进行 下一个兴趣点预测，提出线性和非线性方式整合 3.1模型的输入信息 用户距离偏好分数的2种结构模型。文献[4幻 图1中P,(Q)表示用户在兴趣点P,发出的查 通过对RNN改进，提出整合时空信息的RNN模 询。S()的取值为0或1，用于判断用户签到兴趣 型(ST-RNN),然而它使用固定窗口的时空转化信 点是否属于同一个会话。S()的值根据用户2个 息，缺乏对相邻的兴趣点之间的转移信息进行建 相邻签到兴趣点之间的时间差得到，如果用户在 模。文献[26]提出了改进的LSTM模型，该模型 t时刻签到与1-时刻签到的差大于π，即S(t)=0, 在LSTM模型中加入时间门和距离门，通过对相 表示用户在4和t时刻的签到兴趣点不属于同 邻签到地点之间的时间间隔和距离间隔进行建模 一个会话。 来提取用户长期和短期兴趣偏好。 用户的偏好是随时间变化的，同时用户所处 以上模型都是将用户的历史签到记录作为 地点也有可能发生变化，因此利用用户整个历史 RNN的输入，本文使用用户最后一次的会话信息 签到记录进行下一个兴趣点推荐并不一定合适。 作为RNN的输入。并且，上述模型都忽略了用户 在下一个兴趣点推荐中，用户最近的签到地点通 历史签到兴趣点与最终推荐的兴趣点的时间间隔 常对于下一个兴趣点的推荐具有较大影响，因此 信息。与本文工作最为相似是Distance.2Pre模 本文仅使用用户最后一次会话信息作为RNN的 型，该模型通过对用户的不同距离偏好进行建 输入，用户的签到会话表示为相邻的签到兴趣点 模，但其忽略了用户偏好与时间之间的关联，这 之间的最大间隔不超过π，的一段连续签到序 就意味着随着时间的改变，无论是之后的1个小 列。从图1可以看出用户的历史签到记录被分成 时还是2天内，Distance2Pre将始终为用户预测相 了多个会话，session1和session2是已完成会话， 同的推荐列表。本文提出的模型与上述模型的不 session,是用户最后一次会话。图1中用户历史
矩阵，分别表示用户和兴趣点的潜在因子。然 而，矩阵分解方法不适用于用户签到序列信息的 建模。 序列信息和时空信息是下一个兴趣点推荐的 最基本要素。为了提升下一个兴趣点的推荐效 果，一些模型，如基于 MC 模型的方法[21] 、基于嵌 入的方法[22-23] 和基于神经网络 RNN 的方法，通过 整合序列信息和时空信息用于下一个兴趣点推 荐。文献 [1] 提出了 FPMC 模型，该模型结合矩 阵分解和马尔科夫链对用户偏好和序列信息建 模。文献 [21] 是 FPMC 模型的扩展，通过结合用 户的地理位置约束为用户推荐下一个兴趣点。文 献 [24] 提出了 POI2vec，该模型应用二叉树结构 对附近的兴趣点进行聚类，进而为用户推荐下一 个兴趣点。文献 [17] 提出了 PRME-G，该模型利 用嵌入的方法，通过度量嵌入的方法整合兴趣点 的序列信息和地理位置信息进行下一个兴趣点推 荐。文献 [22] 提出了一种嵌入学习方法 (GE) 用 于兴趣点推荐，该方法利用二部图对 POI 推荐上 下文中的一对上下文进行建模，并通过对 4 对嵌 入模型 (POI-POI、POI-Time、POI-Regin 和 POIWord) 进行统一优化。 然而，以上模型缺乏对用户连续签到的两个 兴趣点之间的转移时空信息的考虑，并且时间信 息和空间信息之间复杂的交互也被忽略。最近， 序列信息和时空信息也被广泛地整合到 RNN 网 络中。文献 [25] 提出了 Distance2Pre 模型，利用 GRU 模型首次整合用户不同地理距离偏好进行 下一个兴趣点预测，提出线性和非线性方式整合 用户距离偏好分数的 2 种结构模型。文献 [4] 通过对 RNN 改进，提出整合时空信息的 RNN 模 型 (ST-RNN)，然而它使用固定窗口的时空转化信 息，缺乏对相邻的兴趣点之间的转移信息进行建 模。文献 [26] 提出了改进的 LSTM 模型，该模型 在 LSTM 模型中加入时间门和距离门，通过对相 邻签到地点之间的时间间隔和距离间隔进行建模 来提取用户长期和短期兴趣偏好。 以上模型都是将用户的历史签到记录作为 RNN 的输入，本文使用用户最后一次的会话信息 作为 RNN 的输入。并且，上述模型都忽略了用户 历史签到兴趣点与最终推荐的兴趣点的时间间隔 信息。与本文工作最为相似是 Distance2Pre 模 型，该模型通过对用户的不同距离偏好进行建 模，但其忽略了用户偏好与时间之间的关联，这 就意味着随着时间的改变，无论是之后的 1 个小 时还是 2 天内，Distance2Pre 将始终为用户预测相 同的推荐列表。本文提出的模型与上述模型的不 同之处体现在：1) 模型只使用用户最后的会话作 为 RNN 的输，具有更快的推荐速度；2) 模型能够 根据用户的查询条件以及用户的偏好变化情况进 行自适应调整，为相同用户推荐变化的个性化的 兴趣点推荐列表。 2 相关定义 U = {u1,u2,··· ,u|U|} P = {p1, p2,··· , p|P|} G = {gp1 ,gp2 ,··· ,g|P|} |U| |P| 令 表示所有用户组成的集 合， 和 分别表 示兴趣点的集合及其对应兴趣点的地理坐标的集 合，其中 和 分别表示用户数量和兴趣点数 量。本文中用户和兴趣点的标识都用连续的整数 编码，编码值从 1 开始。 定义 1 兴趣点 (POI)。兴趣点是具有唯一标 识 (编码) 的地点，它包含经纬度信息。 u H u ti = {p u t1 , p u t2 ,··· , p u ti } p u ti u ti p 定义 2 历史签到序列。某一用户 的历史 签到序列表示为 ，其中 表示 用户 在 时刻访问过兴趣点 。 H u ti p u ti Q = (∆d,ti+1) ∆d ti+1 定义 3 下一个兴趣点推荐。给定用户的历 史签到记录 ，用户最后的签到位置信息 以 及查询条件 ,其中 表示用户访问下 一个兴趣点的距离间隔。下一个兴趣点推荐目标 是为用户推荐其在 时刻最有可能访问的 TOP-K 个兴趣点。 3 基于时空循环神经网络的兴趣点 推荐模型 3.1 模型的输入信息 p7(Q) p7 S (t) S (t) ti ti−1 πs ti ti−1 图 1 中 表示用户在兴趣点 发出的查 询。 的取值为 0 或 1，用于判断用户签到兴趣 点是否属于同一个会话。 的值根据用户 2 个 相邻签到兴趣点之间的时间差得到，如果用户在 时刻签到与 时刻签到的差大于 ，即 S(t)=0， 表示用户在 和 时刻的签到兴趣点不属于同 一个会话。 πs 用户的偏好是随时间变化的，同时用户所处 地点也有可能发生变化，因此利用用户整个历史 签到记录进行下一个兴趣点推荐并不一定合适。 在下一个兴趣点推荐中，用户最近的签到地点通 常对于下一个兴趣点的推荐具有较大影响，因此 本文仅使用用户最后一次会话信息作为 RNN 的 输入，用户的签到会话表示为相邻的签到兴趣点 之间的最大间隔不超过 的一段连续签到序 列。从图 1 可以看出用户的历史签到记录被分成 了多个会话，session1 和 session2 是已完成会话， session3 是用户最后一次会话。图 1 中用户历史 第 3 期 柴瑞敏，等：基于时空循环神经网络的下一个兴趣点推荐方法 ·409·
·410- 智能系统学报 第16卷 签到序列上面的0和1数值表示相邻的两个兴趣 条件进行动态推荐，用户最后的一个会话信息被 点之间是否属于一个会话。本文将用户的每一次 用于推荐。例如，当用户在P地点提出查询时 签到记录作为训练目标，每个用户将会得到s-1 模型将会根据用户在p,的签到时间判断是否上 训练序列，s为用户历史签到总数。下面举例说 一个会话已结束，当用户的前一个会话结束时（即 明模型的训练和推荐过程。如果一个用户在3时 S)=0),用户最后一次签到的p地点将作为一 刻之前已访问过P、p2两个兴趣点，用户访问P1 个新的会话用于推荐下一个兴趣点，当S(①=1， 和P2之间的时间间隔小于π，那么P1和P2属于 说明p?地点的签到属于上一个会话信息，此时P6 同一个会话，假如用户在t(-52≤π)时刻在P 和P,将共同作为一个会话信息用于推荐下一个 兴趣点提出一个查询Q,此用户最后的会话信息 兴趣点。 {P1,P2,P}将会作为序列输入用于推荐，兴趣点p4 3.2序列建模 将会作为目标兴趣点进行训练。假如用户在 本文采用RNN模型对用户的签到序列信息 t4(t4-3>元)时刻在p4地点提出查询Q,由于当前 进行建模。在RNN中，用户在时刻签到的隐藏 用户的会话信息不属于上一会话，模型将在4时 层向量h,表示为 刻新建一个只包括当前用户查询位置的会话信息 h=f(Mp +Ch) (1) 作为输入，用户下一个访问的兴趣点5将会被作 式中：表示对应兴趣点p编码的低维向量；f 为训练目标。在模型的训练中，用户每次访问的 表示激活函数；M、C分别表示参数矩阵。 下一个兴趣点被当成目标兴趣点，由于它的地理 3.3时空偏好建模 信息和签到时间是已知的，用户访问下一个兴趣 一些模型在对空间信息建模时，通常认为用 点的时空间隔信息也可以通过计算得到。本文使 户更倾向于访问位置较近的地，点，通过利用空间 用用户访问下一个兴趣点的时空信息作为用户的 距离作为参数控制用户的空间偏好。然而，这些 查询信息在模型中进行训练。通过大量用户历史 模型无法对用户的远距离偏好的兴趣点进行推 签到数据集来学习，用户访问下一个兴趣点的远近 荐。传统的RNN模型对近距离和远距离的用户 距离偏好、长短时间偏好和时空信息的交互作用。 偏好建模存在困难，因此需要对RNN模型进行改 0 进。本文通过设置2个空间转移矩阵W、W2对 会话 用户的空间偏好进行建模，W,用于捕获用户的短 会话 距离偏好，W2用于捕获用户长距离偏好。为了能 P p/Q) 够让转移矩阵W,自然过渡到转移矩阵W2,设置 了一个最大距离间隔π4。当兴趣点转换距离在最 用户历史签到 用户提交查询时所处位置 大距离间隔内时，用户的空间偏好转移矩阵由距 Ps 离间隔对W,和W2转移矩阵进行加权计算得到。 session, session, session 当兴趣点转换距离在最大距离间隔外时，用户表 训练 输入会话 目标 session, 现出远距离的偏好，此时W2将作为空间转移矩 P P 阵。在训练时，用户访问下一个兴趣点的转换距 session 3 离（△d)由用户历史签到兴趣点相邻的下一个签 session P P P Pa 到兴趣点的距离相减得到，即 session, △d4=h(gt-8P) Ps 式中：△d表示相邻兴趣点的距离间隔；g表示 session, 安 用户u在k时刻访问的兴趣点p的经纬度坐标；h 预测 session, P p?) 表示Harversine公式，用于计算经纬度坐标之间的 1-=π 距离。根据用户签到兴趣点的转换距离，兴趣点 session, M?) 12-62=π 的空间转移矩阵可表示为 图1 基于会话的下一个兴趣点推荐模型的训练与推荐 Y(πa-△dk)W+△dW2 △d<ra 过程 Fig.1 Training and recommendation process of the next W2,△d≥πa POI recommendation model based on session 得到用户的空间转移矩阵D4后，用DM替 在模型的推荐过程中，模型根据用户的查询 代式(1)中的M矩阵，因此考虑用户空间偏好的
s−1 s t3 p1 p2 p1 p2 πs p1 p2 t3 t3 −t2 ⩽ πs p3 Q p1, p2, p3 p4 t4 t4 −t3 > πs p4 Q t4 p5 签到序列上面的 0 和 1 数值表示相邻的两个兴趣 点之间是否属于一个会话。本文将用户的每一次 签到记录作为训练目标，每个用户将会得到 训练序列， 为用户历史签到总数。下面举例说 明模型的训练和推荐过程。如果一个用户在 时 刻之前已访问过 、 两个兴趣点，用户访问 和 之间的时间间隔小于 ，那么 和 属于 同一个会话，假如用户在 ( ) 时刻在 兴趣点提出一个查询 ，此用户最后的会话信息 { }将会作为序列输入用于推荐，兴趣点 将会作为目标兴趣点进行训练。假如用户在 ( ) 时刻在 地点提出查询 ，由于当前 用户的会话信息不属于上一会话，模型将在 时 刻新建一个只包括当前用户查询位置的会话信息 作为输入，用户下一个访问的兴趣点 将会被作 为训练目标。在模型的训练中，用户每次访问的 下一个兴趣点被当成目标兴趣点，由于它的地理 信息和签到时间是已知的，用户访问下一个兴趣 点的时空间隔信息也可以通过计算得到。本文使 用用户访问下一个兴趣点的时空信息作为用户的 查询信息在模型中进行训练。通过大量用户历史 签到数据集来学习，用户访问下一个兴趣点的远近 距离偏好、长短时间偏好和时空信息的交互作用。 会话 会话 会话 p1 p1 p1 p1 p2 p2 p2 p3 p3 p4 p4 p4 p5 p5 p6 p6 p7 p7 p1 p2 p3 p4 p5 p6 p2 p3 p4 p5 p6 t1 t2 t3 t4 t5 t6 S(t) p7 (Q) p8 用户历史签到 用户提交查询时所处位置 session1 session1 session1 session1 session2 session2 session3 session4 session2 session3 训练 t7−t6<=πs t7−t6>=πs 预测 p(?) p(?) 1 1 0 1 0 输入会话 目标 图 1 基于会话的下一个兴趣点推荐模型的训练与推荐 过程 Fig. 1 Training and recommendation process of the next POI recommendation model based on session 在模型的推荐过程中，模型根据用户的查询 p7 p7 S (t) = 0 p7 S (t) = 1 p7 p6 p7 条件进行动态推荐，用户最后的一个会话信息被 用于推荐。例如，当用户在 地点提出查询时， 模型将会根据用户在 的签到时间判断是否上 一个会话已结束，当用户的前一个会话结束时 (即 )，用户最后一次签到的 地点将作为一 个新的会话用于推荐下一个兴趣点，当 ， 说明 地点的签到属于上一个会话信息，此时 和 将共同作为一个会话信息用于推荐下一个 兴趣点。 3.2 序列建模 tk htk 本文采用 RNN 模型对用户的签到序列信息 进行建模。在 RNN 中，用户在 时刻签到的隐藏 层向量 表示为 htk = f(M pu tk +Chtk−1 ) (1) p u t k p f M C 式中： 表示对应兴趣点 编码的低维向量； 表示激活函数； 、 分别表示参数矩阵。 3.3 时空偏好建模 W1 W2 W1 W2 W1 W2 πd W1 W2 W2 ∆d 一些模型在对空间信息建模时，通常认为用 户更倾向于访问位置较近的地点，通过利用空间 距离作为参数控制用户的空间偏好。然而，这些 模型无法对用户的远距离偏好的兴趣点进行推 荐。传统的 RNN 模型对近距离和远距离的用户 偏好建模存在困难，因此需要对 RNN 模型进行改 进。本文通过设置 2 个空间转移矩阵 、 对 用户的空间偏好进行建模， 用于捕获用户的短 距离偏好， 用于捕获用户长距离偏好。为了能 够让转移矩阵 自然过渡到转移矩阵 ，设置 了一个最大距离间隔 。当兴趣点转换距离在最 大距离间隔内时，用户的空间偏好转移矩阵由距 离间隔对 和 转移矩阵进行加权计算得到。 当兴趣点转换距离在最大距离间隔外时，用户表 现出远距离的偏好，此时 将作为空间转移矩 阵。在训练时，用户访问下一个兴趣点的转换距 离 ( ) 由用户历史签到兴趣点相邻的下一个签 到兴趣点的距离相减得到，即 ∆dk = h ( g u,pk+1 k+1 −g u,pk k ) ∆dk g u,pk k u k p h Harversine 式中： 表示相邻兴趣点的距离间隔； 表示 用户 在 时刻访问的兴趣点 的经纬度坐标； 表示 公式，用于计算经纬度坐标之间的 距离。根据用户签到兴趣点的转换距离，兴趣点 的空间转移矩阵可表示为 D∆dk = (πd −∆dk)W1 πd + ∆dkW2 πd , ∆dk < πd W2 , ∆dk ⩾ πd D∆dk D∆dk M 得到用户的空间转移矩阵 后，用 替 代式 (1) 中的 矩阵，因此考虑用户空间偏好的 ·410· 智 能 系 统 学 报 第 16 卷
第3期 柴瑞敏，等：基于时空循环神经网络的下一个兴趣点推荐方法 ·411· RNN公式可以表示为 用户访问每个兴趣点的偏好分数xp,利用softmax h f(Dad.p+Ch) 函数计算用户访问每个兴趣点的概率： 同理，为了考虑用户的时间偏好，本文也设置 exp(x) yp.= -,m∈1,2，…，N 两个时间转移矩阵W、W,和最大时间间隔元来 捕获用户的短时间偏好和长时间偏好。两个相邻 2 exp(xe.) =1 签到兴趣点之间的时间间隔由用户历史签到兴趣 式中：N表示兴趣点的总数；m表示兴趣点的唯一 点与相邻的下一个兴趣点的签到时间差得到，表 标识；y.表示用户将会访问标识为m的兴趣点的 示为 概率。 △=一 式中：△1为相邻签到兴趣点之间的时间间隔， 4模型实验及结果 min;表示用户u在k时刻访问兴趣点p的时 4.1 实验设置 间点。因此用户的时间转移矩阵可表示为 1)数据集 π，-△)W3,△W + T4= ，△tk<π 本文使用2个公开数据集，即Foursquare和 W4,△t≥π CA数据集。2个数据集中，用户的每次签到记录 为了同时考虑用户的时间转移偏好和距离转 都包括4个属性：用户ID、兴趣点D、签到时间 移偏好，本文使用时间转移矩阵和空间转移矩阵 和GPS位置。Foursquare数据集2m,包括用户在 乘积的形式作为用户的时空偏好转移矩阵。因 Foursquare应用软件上2010年8月一2011年1月 此RNN公式可以改写为 在新加坡的352850条签到记录；CA数据集包括 ha=f(T·Dad'p%+Ch) 生活在美国加利福尼亚州的4163名使用者的 为了更充分利用签到序列中的时间信息，本 483813个签到信息、121142个不同的兴趣点。 文进一步提取用户签到序列中的每个兴趣点与推 遵循常用的下一个兴趣点预处理方式21,26,2，在 荐兴趣点的时间间隔△a: 这2个数据集中，移除了少于5次签到信息的用 △a=t-P 户以及少于5个用户访问的兴趣点。数据预处理 式中：k∈{1,2，…，；表示用户将要访问的下一 结果如表1所示。本文选择用户历史签到数据集 个兴趣点的时刻；表示用户在时刻访问兴趣 的最后一次签到记录作为测试集，其余作为训练 点Pk的签到时间。这里对△a.进行分段表示，时 集，以前的大多数工作251也都采用这种方法 间间隔为20min,分成等间距的145段，每段用对 对数据集进行分割。 应的连续整数表示。例如：当0≤△a<20min 表1数据预处理结果 时，其分段数值编号为0，当△aw≥2880min时，其 Table 1 Data preprocessing results 数值编号为144。之后通过嵌入层得到对应的嵌 数据集 用户 兴趣点 签到数 平均签到 入向量△a4,因此整合时间信息△a的循环神经 Foursquare 2321 5596 194108 86.63 网络可进一步表示为 CA 3041 9641 186364 61.28 hn=f(T4·Da4(p4+△au)+Ch-) 最后，将用户签到序列信息和用户偏好作为 2)参数设置 用户访问下一个兴趣点的最终推荐向量，表示为 实验中，SST-RNN模型采用PyTorch编程实 h“=h+u 现，设置用户向量、兴趣点向量和时间间隔向量 式中：h,表示RNN网络最终的输出向量；u表示 的嵌入维度为20，隐藏层神经元个数为20。向量 用户的嵌人向量；表示，时刻用户将要访问的 嵌入过程是通过PyTorch提供的“nn.Embedding 下一个兴趣点对应的偏好向量。 嵌入查找表的方法实现。时间转移矩阵和空间转 3.4模型推荐 移矩阵的大小为R2020,元为8h。在Foursquare 受矩阵分解的启发，用户对下一个兴趣点的 数据集中，最优的参数值为π=24h,π=14km,在 偏好可由偏好向量：与兴趣点p对应的向量p CA数据集中，最优的参数值为π=16h,π=12km, 的内积来表示。向量的内积越大表示用户越倾向 参数的确定将在之后的“参数分析”部分进行说 于访问此兴趣点，即 明。学习率设置为0.001，激活函数选择ReLU。 xp=h⑧p 本文使用交叉嫡损失函数和BPTT算法进行误差 本文将兴趣点推荐问题看成分类问题，根据 的计算和误差的反向传播，使用SGD优化器对参
RNN 公式可以表示为 htk = f(D∆dk · p u tk +Chtk−1 ) W3 W4 πt 同理，为了考虑用户的时间偏好，本文也设置 两个时间转移矩阵 、 和最大时间间隔 来 捕获用户的短时间偏好和长时间偏好。两个相邻 签到兴趣点之间的时间间隔由用户历史签到兴趣 点与相邻的下一个兴趣点的签到时间差得到，表 示为 ∆tk = t u,pk+1 k+1 −t u,pk k ∆tk t u,pk k u k p 式中： 为相邻签到兴趣点之间的时间间隔， min； 表示用户 在 时刻访问兴趣点 的时 间点。因此用户的时间转移矩阵可表示为 T∆tk = (πt −∆tk)W3 πt + ∆tkW4 πt , ∆tk < πt W4, ∆tk ⩾ πt 为了同时考虑用户的时间转移偏好和距离转 移偏好，本文使用时间转移矩阵和空间转移矩阵 乘积的形式作为用户的时空偏好转移矩阵。因 此 RNN 公式可以改写为 htk = f(T∆tk · D∆dk · p u tk +Chtk−1 ) ∆atk 为了更充分利用签到序列中的时间信息，本 文进一步提取用户签到序列中的每个兴趣点与推 荐兴趣点的时间间隔 ： ∆atk = t u,pi+1 i+1 −t u,pk k k ∈ {1,2,··· ,i} t u,pi+1 i+1 t u,pk k tk pk ∆atk 0 ⩽ ∆atk < 20 ∆atk ⩾ 2 880 ∆at k ∆at k 式中： ； 表示用户将要访问的下一 个兴趣点的时刻； 表示用户在 时刻访问兴趣 点 的签到时间。这里对 进行分段表示，时 间间隔为 20 min，分成等间距的 145 段，每段用对 应的连续整数表示。例如：当 min 时，其分段数值编号为 0，当 min 时，其 数值编号为 144。之后通过嵌入层得到对应的嵌 入向量 ，因此整合时间信息 的循环神经 网络可进一步表示为 htk = f(T∆tk · D∆dk ·(p u tk + ∆atk )+Chtk−1 ) 最后，将用户签到序列信息和用户偏好作为 用户访问下一个兴趣点的最终推荐向量，表示为 h u ti = hti +u hti u h u ti ti 式中： 表示 RNN 网络最终的输出向量； 表示 用户的嵌入向量； 表示 时刻用户将要访问的 下一个兴趣点对应的偏好向量。 3.4 模型推荐 h u ti p p 受矩阵分解的启发，用户对下一个兴趣点的 偏好可由偏好向量 与兴趣点 对应的向量 的内积来表示。向量的内积越大表示用户越倾向 于访问此兴趣点，即 xp = h u ti ⊗ p 本文将兴趣点推荐问题看成分类问题，根据 用户访问每个兴趣点的偏好分数 xp ,利用 softmax 函数计算用户访问每个兴趣点的概率： ypm = exp(xpm ) ∑N n=1 exp(xpn ) , m ∈ 1,2,··· ,N N m ypm m 式中： 表示兴趣点的总数； 表示兴趣点的唯一 标识； 表示用户将会访问标识为 的兴趣点的 概率。 4 模型实验及结果 4.1 实验设置 1）数据集 本文使用 2 个公开数据集，即 Foursquare 和 CA 数据集。2 个数据集中，用户的每次签到记录 都包括 4 个属性：用户 ID、兴趣点 ID、签到时间 和 GPS 位置。Foursquare 数据集[27] ，包括用户在 Foursquare 应用软件上 2010 年 8 月—2011 年 1 月 在新加坡的 352 850 条签到记录；CA 数据集包括 生活在美国加利福尼亚州的4 163 名使用者的 483 813 个签到信息、121 142 个不同的兴趣点。 遵循常用的下一个兴趣点预处理方式[21, 26, 28] ，在 这 2 个数据集中，移除了少于 5 次签到信息的用 户以及少于 5 个用户访问的兴趣点。数据预处理 结果如表 1 所示。本文选择用户历史签到数据集 的最后一次签到记录作为测试集，其余作为训练 集，以前的大多数工作[9, 25, 29] 也都采用这种方法 对数据集进行分割。 表 1 数据预处理结果 Table 1 Data preprocessing results 数据集 用户 兴趣点 签到数 平均签到 Foursquare 2 321 5596 194108 86.63 CA 3 041 9641 186364 61.28 2）参数设置 πs πt πd πt πd 实验中，SST-RNN 模型采用 PyTorch 编程实 现，设置用户向量、兴趣点向量和时间间隔向量 的嵌入维度为 20，隐藏层神经元个数为 20。向量 嵌入过程是通过 PyTorch 提供的“nn.Embedding” 嵌入查找表的方法实现。时间转移矩阵和空间转 移矩阵的大小为 R 20x20 ， 为 8 h。在 Foursquare 数据集中，最优的参数值为 =24 h， =14 km，在 CA 数据集中，最优的参数值为 =16 h， =12 km， 参数的确定将在之后的“参数分析”部分进行说 明。学习率设置为 0.001，激活函数选择 ReLU。 本文使用交叉熵损失函数和 BPTT 算法进行误差 的计算和误差的反向传播，使用 SGD 优化器对参 第 3 期 柴瑞敏，等：基于时空循环神经网络的下一个兴趣点推荐方法 ·411·