一种通过上下文相关的图嵌入表示人移动模式的方法

本发明属于机器学习中的神经网络领域，是一种基于深度学习的方法，该方法首次将词嵌入技术应用于图模型，学得融合了上下文语义信息的签到点向量表示，进而通过循环神经网络(Recurrent Neural Network，RNN)得到每条轨迹的向量表示，然后利用强化学习从带标签和不带标签的轨迹数据中提取用户的隐含移动模式，出产生当前轨迹的用户。

在基于地理位置信息的社交网络(Location-Based Social Network，LBSN)应用中，如个性化的位置推荐、出行规划和人流动预测等，学习人流动性规律是一项重要而复杂的任务，且该任务有着十分广泛的应用场景，例如：通过上述学得的人流动性规律出产生当前轨迹的用户，进一步出该用户的朋友关系，从而实现为当前这条轨迹预测其对应的朋友关系。就实际应用方面而言，本发明可用于帮助寻社会中的极端组织，例如：给定一组匿名的轨迹，仅仅利用轨迹信息识别出一组犯罪分子/，或出他们的同伙；它还可以用于朋友关系重建，即根据各自的轨迹重建社交圈。

近年来，循环神经网络(RNN)等深度学习的模型经常利用低维嵌入技术来建模轨迹信息，例如学得签到点的嵌入表示或者轨迹的嵌入表示。基于RNN的方法基本都可以从那些连续的长度可变的签到点序列中捕获语义信息，而且RNN中的每个单元都会存储之前单元的信息，这些信息将影响后续单元。然后，通常用梯度下降算法，如SGD、Adam和AMSGRAD等来优化RNN模型中针对特定任务的可学习参数。

然而，现有的工作在有效地建模用户移动模式问题上仍面临以下挑战：(1)缺乏用于学习签到点嵌入表示的语料库。时空数据处理和自然语言处理领域的词嵌入不同的是，自然语言的文本处理过程中可以利用丰富的语料库来训练不同单词的密集表示，并且对于不同的自然语言处理任务，每个单词表示包含的语义信息也不尽相同。但是对于基于地理位置的社交网络数据而言，其包含的语义信息明显不足，这是因为大多数用户通常只访问少量的兴趣点，而且由于移动轨迹的不规律性和签到点的稀疏性，很难利用现有的这些兴趣点去表示某一签到点。(2)忽略了上下文信息的限制。在一条给定的轨迹中，不同的签到点都有其各自对应的地理位置信息以及签到时间信息，这意味着每个签到点都受用户的移动模式或签到偏好影响的上下文空间限制，例如：用户的下一个签到点可能是当前签到点周围的某个点，而且用户更喜欢访问离自己比较近的兴趣点。不难看出，地理约束在签到点的嵌入表示和轨迹的嵌入表示中起着重要作用。(3)缺乏带标签的训练数据。在许多真实的应用场景中，我们很难获取大量的带标签数据训练模型，但这恰好也是用户移动模式学习中的关键。

基于上述问题，本发明提出了一种新的通过上下文相关的图嵌入来表示人移动的方法，该方法在学习过程中引入了强化学习的思想，充分利用了签到点的地理位置信息和不带标签的轨迹信息，从而有效缓解了数据稀疏和加标数据有限等问题。

本发明的目的在于通过一种新的上下文相关的图嵌入模型，学得人移动模式的表示，进而引入强化学习的方法出当前轨迹的产生者。在整个模型的训练过程中，本发明利用带标签的轨迹和不带标签的轨迹同步进行训练，同时还利用对抗学习中的策略梯度方法更新模型参数，进一步增强模型性能。

基于上述发明思路，本发明设计了一种通过上下文相关的图嵌入表示人移动模式的方法，其包括以下步骤：

S1，数据预处理：将原始轨迹依据特定的时间间隔切割，并划分训练集DL与测试集DU；

S2，合成上下文相关图：根据DL与DU中用户的历史轨迹分别构建签到点空间图Gspatial和访问序列图Gvisit，然后通过上述两种图合成一个全连通的上下文相关图Gtotal；

S3，对于S31，S32，S33定义的模型，执行反向传播，直到模型收敛：

S31，上下文相关的图嵌入：对于DL与DU中每一个签到点lτ，基于上述上下文相关图Gtotal生成签到点的低维分布表示C(lτ)，然后，引入非线性变换协同训练签到点的分布表示，进而得到初始化签到点的嵌入表示C′(lτ)。接着，本发明将该签到点对应的时间向量u(lτ)与初始化签到点的嵌入表示C′(lτ)拼接起来，即可得到签到点的最终表示Cτ；

S32，轨迹编码：基于前一步得到的签到点的最终表示即可利用循环神经网络对轨迹进行编码，在此，本发明用RNN的最后一个隐含状态归一化后的结果X来表示当前这条轨迹；

S33，预训练轨迹分类器，判别器：基于前一步得到的轨迹嵌入表示，利用加标轨迹(正样本){(Tl,Ul)∈DL}预训练轨迹分类器Ρθ，其中Tl为用户的子轨迹，Ul为轨迹对应的标签，DL代表正样本集合。紧接着，利用该分类器为未标记轨迹(负样本)预测其对应的标签然后通过最小化上述分类器在正负样本上的交叉熵来预训练判别器Fε；

S4，使用小批量训练方法更新模型参数，重复该步骤直至此模型遍历所有的数据：从正样本DL中采集B组数据对(带标记轨迹，对应的标签)，从负样本DU中也采集B组数据(未标记轨迹)，并通过分类器Ρθ为这些未标记轨迹预测其对应的标签；利用判别器Fε判定分类器预测的标签的可信度，随之更新判别器的行为价值函数a(·)；计算期望奖励的梯度通过策略梯度更新模型中的参数{θ,ω,φ}，其中θ为轨迹分类器的参数，ω为嵌入表示签到点的参数，φ为嵌入表示轨迹的参数；

S5，给出一条未标记轨迹利用上述训练好的分类器Ρθ与判别器Fε预测出该轨迹对应的概率分布向量中每一维代表这一维对应的用户是本次预测结果的概率值，本发明选择概率值最大的那一维对应的用户作为最终的预测结果。

上述通过上下文相关的图嵌入表示人移动模式的方法，所述步骤S1的目的在于切割轨迹，划分训练集DL与测试集DU。具体包括以下分步骤：

S11，依据固定的时间间隔(6小时)将一条完整轨迹划分为连续的子轨迹，每条子轨迹为基于该时间间隔分割后的签到点序列。若已知当前轨迹由用户uk产生，则将此轨迹记为其中N代表用户的个数，每一个lτ(τ∈[1,n])代表时间戳tτ时的签到点，而且每一个lτ都有与之对应的地理坐标分别代表经度值和纬度值。对于不知道是谁产生的轨迹，即未标记轨迹，则将其记为

S12，为了进一步挖掘用户的移动模式，本发明加入了时间因素。具体而言，将一天划分为24个离散的时间戳且这24个基于密度的时间表示采样于高斯分布，即在tτ时签到的节点其相应的时间向量可以被表示为其中d*代表时间向量的维度；

S13，划分训练集与测试集，本发明选取每个用户子轨迹的50％Tl以及其对应的标签Ul作为训练集{(Tl,Ul)∈DL}，剩余的50％作为测试集

S14，获得已知标签的向量表示：对于训练集数据的已知标签，本发明将使用0-1向量编码表示该标签；

S15，按照轨迹长度对其进行排序，这样能使同一个批次的轨迹长度尽可能相似。此操作可以减少了处理轨迹过程中不必要的填充。

上述通过上下文相关的图嵌入表示人移动模式的方法，所述的步骤S2，目的在于合成一个全连通的上下文相关图Gtotal。具体包括以下步骤：

S21，构建签到点空间图，根据签到点集合中两点之间的距离是否大于给定的阈值来决定是否应将这两点连接起来，即可构建出无向的空间图Gspatial{V,Es}，其中，V是从训练集和测试集的签到记录中采样的签到点集合，Es代表节点之间的边的集合，但是如果给定的阈值太小，则有些离的比较远的签到点会变为孤立点，导致此图不连通。为了避免孤立点的出现，本发明引入了三个虚拟节点，即起点sp、终点ep以及补全节点cp，进而将V中所有的节点分别与此三个节点一一连接；

S22，构建访问序列图，为了融合用户的访问意向以及序列化移动模式，本发明进一步构建了有向图Gvisit{V,A,Evisit}，其中Evisit代表用户访问过的地点的转换，A是Gvisit中子轨迹的集合，例如：若则它所包含的任一签到点vi∈V；

S23，合成全连通的上下文相关图Gtotal{V,E}，首先利用Gspatial初始化Gtotal，然后将Evisit中的边逐一加入E中，进而得到用于学习签到点表示的无向图Gtotal，该图既考虑了签到点地理位置信息又考虑了签到的序列模式。

上述通过上下文相关的图嵌入表示人移动模式的方法，所述的步骤S31，目的在于通过上下文相关的图嵌入获得签到点的最终表示Cτ。具体包括以下步骤：

S311，在上述上下文相关图Gtotal上随机游走获取签到点的上下文Con(lτ)＝lτ-a:lτ+a，其中lτ-a:lτ+a代表签到点lτ附近连续的2a+1个签到点序列，a为固定的滑动窗口的大小，τ为当前签到点在这条轨迹中的索引位置；

S312，使用连续词袋模型得到签到点lτ的低维分布表示C(lτ)∈Rd，d为低维向量空间的维数；

S313，引入非线性变换协同训练每个签到点的表示，进而得到初始化签到点的嵌入表示C'(lτ)＝Relu(W'C(lτ)+b')，其中C(lτ)为签到点lτ的低维向量表示，Relu为特定的激活函数，记ω＝{W',b'}为签到点嵌入表示过程中可学习的参数；

S314，将每一个签到点的初始化嵌入表示C'(lτ)和时间信息u(lτ)拼接起来可得签到点的最终表示Cτ，形式化地表示为Cτ＝[C'(lτ),u(lτ)]。

上述通过上下文相关的图嵌入表示人移动模式的方法，所述的步骤S32，目的在于利用RNN对轨迹进行编码，进而获得当前轨迹的最终表示X。具体包括以下步骤：

S321，对于每条(子)轨迹T＝{l1,l2,...,ln}，设hτ-1和hτ(τ∈{1,2,...,n})分别代表该轨迹的前一步和当前的隐藏状态，其中初始状态h0为一个全0的矢量。RNN的输入门，遗忘门，输出门分别可由如下计算获得：iτ＝σ(WiCτ+Uihτ-1+Vicτ-1+bi)，fτ＝σ(WfCτ+Ufhτ-1+Vfcτ-1+bf)，oτ＝σ(WoCτ+Uohτ-1+Vocτ-1+bo)，其中b*为偏差向量，σ为logistic激活函数，Cτ代表签到点lτ的最终表示，矩阵W*，U*，V*为不同的门参数。记忆单元cτ的更新规则为：cτ＝fτcτ-1+iτtanh(WcCτ+Uchτ-1+bc)，其中tanh(·)为双曲正切函数，初始状态c0亦为一个全0矢量，隐藏状态ht更新规则如下：hτ＝tanh(cτ)oτ；

S322，本发明在此选用当前轨迹的最后一个隐藏状态归一化之后的结果作为这条轨迹的最终表示：其中为最后一个隐藏状态hn的第i维向量，d′为隐藏状态hn的维度，[,]代表向量元素之间的拼接操作。

上述通过上下文相关的图嵌入表示人移动模式的方法，所述的步骤S33，目的在于利用加标轨迹(正样本){(Tl,Ul)∈DL}训练轨迹分类器Ρθ，进而利用该分类器为未标记轨迹(负样本)预测其对应的标签然后通过最小化上述分类器在正负样本上的交叉熵来预训练判别器Fε。具体包括以下步骤：

S331，利用加标轨迹(正样本){(Tl,Ul)∈DL}预训练轨迹分类器Ρθ，其训练目标为最大化期望奖励Rθ＝∑u∈UΡθ(u|X)a(X,u)，其中，Ρθ(u|X)代表为轨迹X预测的标签为u的概率，a(·)为选择u作为当前预测的标签所对应的行为价值函数，该函数被用来衡量或评估预测的标签的真实性，若X为从带标记的轨迹中采样的数据，则a(X,u)＝1，否则，a(X,u)＝Fε(X,u)，令作为未加标轨迹的奖励去影响分类器，W”和b”为学习参数，o＝Relu(XTWru)，Relu为激活函数，Wr为学到的参数矩阵；

S332，利用分类器Ρθ为未标记轨迹(负样本)预测其对应的标签

S333，最小化上述分类器在正负样本上的交叉熵来预训练判别器Fε，即

上述通过上下文相关的图嵌入表示人移动模式的方法，所述的步骤S4，目的在于利用小批量训练的方法不断更新模型参数{θ,ω,φ}，重复该步骤直至此模型遍历所有的数据。具体包括以下步骤：

S41，划分小批量数据：从训练数据{(Tl,Ul)∈DL}中采集B组真实的加标轨迹和其对应的标签，从测试数据中也采集B组未加标的轨迹数据和该模型为之预测的标签B为每个小批量的样本大小；

S42，更新判别器的行为价值函数，即通过判别器Fε(X,u)计算出分类器预测的标签Ρθ(u|X)为真实标签的概率；

S43，计算期望奖励的梯度：将策略参数的向量记为θ，则策略参数的更新可表示为：其中，即U为真实标签Ul与预测的标签的并集，上述分类器的训练目标可重写为在此训练过程中，本发明使用了小批量训练方法更新参数θ，其近似梯度可通过下式求得：其中，B为批次大小，ul，Xl，分别代表真实标签，带标记的轨迹，预测的标签，未标记的轨迹。故，参数θ的更新规则为：其中，β为学习率，θnew和θold分别代表更新后的参数和当前参数；

S44，在本发明中，为了更好地对签到点和轨迹编码，此处同时更新了嵌入表示签到点的参数ω和嵌入表示轨迹的参数φ，故参数更新公式可重写为其中γ＝{θ,ω,φ}。

与现有技术相比，本发明具有以下有益效果：

1、本发明首次尝试利用基于图的模型去学习用户签到点的嵌入表示，该方法为利用地理位置信息和未标记的移动数据进行移动模式学习的任务提供了一个新视角；

2、本发明提出了一种融合了上下文语义信息且可以动态更新签到点嵌入表示和轨迹嵌入表示的方法，该方法不仅提供了更精确和更全面的移动模式表示，而且有效地缓解了数据稀疏和加标数据有限的问题；

3、本发明提出了一种利用强化学习从加标和未加标的轨迹数据中提取隐含移动模式的方法，该方法可以近似真实的用户轨迹分布，并借鉴对抗学习的思想设计了一种判别器来判定生成的数据的真实性，进一步增强了模型性能。

图1为一种通过上下文相关的图嵌入表示人移动模式的方法的整体框架图。

术语解释

LBSN是Location-based Social Network的缩写，表示“基于位置的社会网络”。LBSN除了包含传统社会网络中人与人的关系外，还记录了用户签到时间及地理位置等信息。

RNN是Recurrent Neural Network的缩写，表示“循环神经网络”，是一类用于处理序列数据的神经网络。

以下结合附图对本发明作进一步描述。

实施例

本实施提供的通过上下文相关的图嵌入表示人移动模式的方法，可用于包含用户签到记录的这种数据集。如表1所示的真实世界的LBSN数据集，以Gowalla(http://snap.stanford.edu/data/loc-gowalla.html获取)为例进行实验。

表1：本发明实验数据的相关信息

|u|表示用户的数量；

|DL|/|DU|分别表示用于训练和测试的子轨迹个数；

|L|表示数据集中不同签到点的个数；

表示轨迹被划分前的平均长度；

Tr表示数据集中轨迹长度的范围；

New York表示数据集Foursquare中区域为纽约的数据；

Tokyo表示数据集Foursquare中区域为东京的数据。

在本实施例中，如图1所示，本发明通过上下文相关的图嵌入表示人移动模式的方法包括步骤S1～S5。步骤S1，针对Gowalla数据集，首先对轨迹进行划分得到(子)轨迹集合以及签到点集合，接下来，将每个用户涉及到的每一条子轨迹与其对应的用户连接起来，选取每个用户总的子轨迹的50％带标记轨迹作为训练集DL，剩余的50％未标记子轨迹DU用来测试；步骤S2，根据用户的历史轨迹分别构建签到点空间图Gspatial和访问序列图Gvisit，然后通过上述两种图合成一个全连通的上下文相关图Gtotal；步骤S3，对于S31，S32，S33定义的模型，执行反向传播，直到模型收敛：S31，对于DL与DU中每一个签到点lτ，基于上述上下文相关图Gtotal生成签到点的低维分布表示C(lτ)，然后，引入非线性变换协同训练签到点的分布表示，得到初始化签到点的嵌入表示C′(lτ)，接着，本发明将该签到点对应的时间向量u(lτ)与初始化签到点的嵌入表示C′(lτ)拼接起来，即可得到签到点的最终表示Cτ；S32，基于前一步得到的签到点的嵌入表示即可利用循环神经网络对轨迹进行编码，在此，本发明用RNN的最后一个隐含状态归一化后的结果X来表示当前这条轨迹；S33，基于前一步得到的轨迹嵌入表示，利用加标轨迹(正样本){(Tl,Ul)∈DL}预训练轨迹分类器，初始化该轨迹分类器Ρθ，进而利用该分类器为未标记轨迹(负样本)预测其对应的标签然后通过最小化上述分类器在正负样本上的交叉熵来预训练判别器Fε；步骤S4，使用小批量训练方法更新模型参数，重复该步骤直至此模型遍历所有的数据：从加标轨迹DL中采集B组数据对(带标记轨迹，对应的标签)，从未标记轨迹DU中也采集B组数据(未标记轨迹)，并通过分类器Ρθ为这些未标记轨迹预测其对应的标签；利用判别器Fε判定分类器预测的标签的可信度，随之更新判别器的行为价值函数a(·)；计算期望奖励的梯度通过策略梯度更新模型中的参数{θ,ω,φ}；步骤S5，给出一条未标记轨迹利用上述训练好的分类器Ρθ与判别器Fε预测出该轨迹对应的概率分布向量中每一维代表这一维对应的用户是本次预测结果的概率值，本发明选择概率值最大的那一维对应的用户作为最终的预测结果。

从表2中的实验结果可以看出，使用本发明的通过上下文相关的图嵌入表示人移动模式的方法，其预测效果要全面优于以往的方法。由此可知，本发明提出的基于图的融合了上下文语义信息且可以动态更新签到点嵌入表示和轨迹嵌入表示的方法着实提升了模型的预测性能。

ACC@K表示准确率，即预测正确的轨迹个数占所有轨迹个数的比例；

macro-P表示精确率，即预测正确的轨迹个数占预测的轨迹个数的比例；

macro-R表示召回率，即预测正确的轨迹个数占真实的轨迹个数的比例；

macro-F1表示精确值和召回率的调和均值；

TULER-LSTM，TULER-GRU，Bi-TULER：分别为本发明复现的三个基于LSTM，GRU，以及双向LSTM单元的TULER方法，TULER为近期在用户-轨迹链接问题上表现最好的方法。

HTULER-L，HTULER-G，HTULER-B：为本发明复现的三个分别基于多层LSTM，GRU，以及双向LSTM单元的HTULER方法。

TULVAE是一种通过变分推断，以半监督的方式解决用户-轨迹链接问题的方法。TLUTE-L，TLUTE-G：TLUTE原本是用来衡量用户的嵌入表示和轨迹的嵌入表示之间相似度的一种方法，但本发明的任务在于将轨迹与对应的用户链接起来，故该任务可被视为一个分类任务。在此，为了便于与本发明提出的方法做比较，本发明去除了原始TLUTE中相似度衡量的那个模块，TLUTE-L，TLUTE-G分别为基于LSTM和GRU单元的简化版TLUTE方法。

表2：GraphTUL在四个真实数据集上进行轨迹-用户链接预测的效果

本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。本领域的普通技术人员可以根据本发明公开的这些技术启示做出各种不脱离本发明实质的其它各种具体变形和组合，这些变形和组合仍然在本发明的保护范围内。