基于自编码器的旅行同伴挖掘

李小昌 陈贝 董启文 陆雪松

摘要：随着移动设备的广泛应用，当今的位置跟踪系统不断产生大量的轨迹数据。同时，许多应用亟需具备从移动物体的轨迹数据中挖掘出一起旅行的物体（旅行同伴）的能力，如智慧交通系统和智慧营销。现有算法或是基于模式挖掘方法，按照特定模式匹配旅行同伴：或是基于表征学习方法，学习相似轨迹的相似表征。前一种方法受限于点对匹配的问题，后一种方法往往忽略轨迹之间的时间相近性。为了改善这些问题，提出了一个基于自编码器的深度表征学习模型Mean-Attn（Mean-Attention），用于发现旅行同伴。Mean-Attn分别使用低维稠密向量表征和位置编码技术，将空间和时间信息同时注入轨迹的嵌入表征中;此外，还利用Sort-Tile-Recursive（sTR）算法、均值运算和全局注意力机制，鼓励轨迹向邻近的轨迹学习;从编码器获得轨迹表征后，利用DBSCAN（Density-Based Spatial Clustering of Applications with Noise）对表征进行聚类，从而找到旅行同伴。实验结果表明，Mean-Attn在寻找旅行同伴方面的表现要优于传统的数据挖掘算法和最新的深度学习算法。

关键词：旅伴同伴;自编码器;时空信息;STR算法;注意力机制

中图分类号：TP391 文献标志码：A DOI：10.3969/j.issn。1000-5641.202091003

0引言

挖掘结伴同行的移动物体（旅行同伴）在许多实际应用中是一个非常有价值的问题。例如，在智慧交通系统中，交通流的优化需要依赖道路传感器监控车流量。如果传感器能够发现大量汽车正沿同一路径行进，交通管制人员则可以及时管控和调整车辆行进路线，以减轻可能发生的交通拥堵。再如，在移动广告中，有研究证明，在同一时间出现在同一地点的消费者，通常会表现出共同的消费偏好。因而，发现一起行走的消费者群体，并向他们发放同一产品类别的优惠券，有可能会增加广告的营销效益。寻找旅行同伴在其他方面也有着广泛应用，包括机场安防、动物迁徙监测和公共游行管理等。

旅行同伴可以从物体的轨迹中挖掘。物体的轨迹是指按时间顺序排列的一系列位置点，而旅行同伴的轨迹在空间和时间上都比较接近，即在相近的时间内互相有大量彼此靠近的位置点。现有的旅行同伴挖掘方法可以大致分為两类：一类是基于模式挖掘的方法;另一类是基于表示学习的方法。基于模式挖掘的方法，通常首先依据专家经验来定义和旅行同伴有关的轨迹模式，即相似的轨迹，然后开发相应的算法从轨迹数据集中挖掘预定义的模式。这类算法中，轨迹的相似性计算通常基于点对之间的欧氏距离，因此要求待检验的轨迹按照时间戳对齐。但是，实际应用中的轨迹通常包含许多缺失的位置点，必须通过插值补齐后才能有效对齐，因而在挖掘过程中会引入大量的测量误差。另外，基于表示学习的方法不需要定义模式或逐点比较，而是使用机器/深度学习模型来学习轨迹的嵌入表征，然后将这些表征进行聚类，从而挖掘出相似的轨迹。现有的轨迹表征模型，一般需要一定的特征工程，或者需要特定的标签以进行有监督学习。在实践中，特征工程通常依赖于问题的定义并且很耗时，会给数据挖掘带来额外的开销;而轨迹标签信息通常很难收集，并且在使用时经常存在伦理问题。除此以外，现有模型更多关注的是轨迹之间空间接近性上的特征，而忽略了轨迹之间时间接近性上的特征。因而，这样挖掘出的轨迹虽然形状相似，但并不一定对应一起旅行的同伴。

为了解决上述问题，本文开发了一种基于自编码器的无监督模型MEAN-Attn。该模型可以直接从原始轨迹中学习表征，输入的原始轨迹不需要按照时间戳对齐，即允许具有不同数量的位置点，也即轨迹长度可以不同。模型学习到的表征同时包含了原始轨迹的空间和时间特征，从而允许通过聚类轨迹表征的方式来发现旅行同伴。Mean-Attn的灵感来源于文本摘要模型MeanSum。MeanSum模型可以用于对主题相似的文本进行摘要式总结。基于此，本文首先使用STR算法对原始轨迹进行分组。STR算法最初用于对空间数据进行分组，以支持R树的批量构建。利用STR分组，可以使同一组内的轨迹具有一定的时空接近性。随后，从每组轨迹中抽取小的批次输入基于注意力的自编码器中。这背后的想法是鼓励时空上更近的轨迹能互相学习到更多相似的表征，同时在轨迹嵌入的时候，本文使用了位置编码技术，将轨迹的时间信息注入模型的输入表征中。然后，对每组轨迹学到的表征做均值计算，并使用一个解码器一编码器结构对表征均值进行重编码。模型的损失函数分为两部分：一部分是轨迹的重构损失，用以控制轨迹学习自身的特征;另一部分是前述重编码表征和相应批次中其他轨迹表征的相似性，用以引导批次中的轨迹互相学习对方的特征。由于在编码时使用了注意力机制，并且使用均值计算来聚合一个批次的编码，因此本文将模型称为Mean-Attn自编码器。当模型训练完毕，就可以使用它的编码器对轨迹进行编码，然后使用聚类算法，如DBSCAN，对编码得到的表征进行聚类。最后，在聚类后同一个簇中的表征所对应的轨迹中，同时具有时间和空间上的相似性的可视为旅行同伴。

1相关工作介绍

1.1基于点对匹配的同伴挖掘

在过去的10年中，寻找旅行同伴的问题在数据挖掘领域已经有了非常广泛的研究。一些具有代表性的研究主要是Flock、Convoy、Swarm和Gathering。本文重点阐述与本文要解决的问题更相关的Convoy和Swarm这两个工作。Flock、Gathering与Convoy、Swarm这两个工作类似，但是定义旅行同伴模式的方法不同。Convoy被定义为一组至少包含m个移动物体的集合，且要求集合中中的移动物体需要在至少k个连续时间点内都是密度连通的：首先，通过在每个时间点执行聚类算法，发现密度联通的簇后，找出那些在连续的时间点内能够至少维护n个簇的对象;然后把这些对象加入Convoy候选集;最后，对于候选集中的每个对象，对其中的所有簇相交以测试所有的簇是否至少包含m个相同的轨迹。为了缓解计算复杂度过高的问题，Jeung等建议，首先根据简化的轨迹挖掘Convoy候选集，然后在微调步中确定每个候选集是否确实合格。另一个类似的工作是Swarm，它通过将旅行同伴定义为在至少k个可能不连续的时间点内具有密度连通特性的移动物体。这个定义放松了Convoy对旅行同伴的约束，即k个时间点可以不连续。这项工作的目的是发现所有封闭的群体，即群体中的轨迹集或者时间点都不能被扩大。由于候选的封闭Swarm数量过高，因此Li等提出了利用两种剪枝策略来缩小模式的搜索空间。

1.2基于表征学习的轨迹相似度计算

近年来，轨迹的表征学习引起了很多关注。因为它几乎不需要特征工程，并且不依赖于基于点对的相似度计算，一旦表征被学习到，就可以非常高效地将表征用于其他任务。与本文工作最相关的研究包括轨迹聚类和基于表征学习的轨迹相似度计算。Yao等使用序列到序列的自编码器来学习轨迹表征，并用于轨迹聚类任务：首先提取轨迹特征，例如速度和转弯速率等;然后将其转换为能描述相应对象移动模式的特征序列;最后，将特征序列输入自编码器模型，以学习固定长度的轨迹表征。随后，Li等提出了一种基于循环神经网络（Recurrent Neural Network，RNN）的模型来学习用于相似度计算的轨迹表征。该模型不需要特征提取，直接从原始轨迹中学习表征。但是，该模型的训练是有监督学习，需要对每条原始轨迹进行下采样，以构建训练对。值得一提的是，这两个工作都只关注寻找具有相似形状的轨迹，因此它们所发现的相似轨迹，有可能是时间上间隔很远的轨迹，因此不能被直接用来发现旅行同伴。另外，Zhang等的模型将额外的语义信息（例如环境约束和轨迹活动）注入到模型中，以获得更精确的轨迹表征。尽管如此，到目前为止还没有发现一个现有模型可以同时学习轨迹之间的时间相似性和空间相似性。

2Mean-Attn模型

2.1轨迹点的嵌入表征

首先，对于给定的轨迹数据集，将整个空间划分为大小相同的正方形单元。然后使用低维稠密表征技术对所有单元的嵌入表征进行预训练，使得空间上接近的单元具有更相似的嵌入表征。对于轨迹中的每个点，使用该点所在单元格的表征作为其表征，那么每条轨迹就可以表示为它所有点的表征的序列。

其次，为了捕获轨迹的时间特征，使用位置编码技术将时间信息注入轨迹的每个点的表征中。位置编码原先被用于Transformer模型中用来捕获文本中各个单词之间的位置信息。由于已经将轨迹表示成了一个标识序列，因此可以使用相同的机制来给每个标识加入时间信息。位置编码PE（Positional Encoding）的计算方法为（本文用PpE表示）

2.2Mean-Attn自编码器

为了鼓励每条轨迹更多地向时空接近的轨迹学习，首先根据轨迹的时空接近性将它们粗略地划分为不同的组，然后将每个组独立地输入到自编码器中。这里使用STR算法对轨迹进行分组。STR算法最初用于将空间接近的对象打包为最小边界矩形MBR（Minimum Bounding Rectangle），并用来构建R树索引的批量加载。由于每个轨迹都可以视为三维空间（t，x，y）中的一个对象，其中t是时间维度，x和y代表两个空间维度，因此可借用STR的思想粗略地对轨迹进行分组。被分到同一个MBR的轨迹在时间上和空间上都更为接近，因此更有可能是旅行同伴。随后从每个MBR中单独抽取轨迹，组成小批次送入模型，相比原来开放式地抽取轨迹组成一个批次，小批次的处理更有可能包含旅行同伴，从而有更多的机会学习到彼此相似的特征。

整个模型由两个共享参数的自编码器构建，如图1所示。左侧的编码器和解码器构成了第一个自编码器，用于重构每条输入的轨迹。编码器和解码器均采用LSTM（Long Short-Term Memory）网络。在模型右侧是一个解码器一编码器结构。首先，对左侧的编码器输出的一个小批次的轨迹表征进行均值运算，得到一个小批次的平均编码，后将其送入右侧的解码器，将解码器输出的中间轨迹再次输到右侧的编码器中，以获得重编码的轨迹平均表征;然后，计算左侧编码器输出的每条轨迹的编码与右侧编码器输出的平均轨迹的重编码之间的相似性，用以控制轨迹在自我编码的同时，尽量学习与其邻近轨迹的特征。为了既保证轨迹的自我重构，又保证从邻近轨迹学到相似的表征，左右两侧的两个编码器和解码器分别需要共享相同的结构和参数。

在两个LSTM编码器上，本文还使用全局注意力机制来汇总每个步骤的隐藏状态，以形成最终的输出编码。该编码考虑了整个轨迹的全局信息，实验证明能够提高编码的表征能力。具体来说，首先初始化与轨迹点维度相等的全局注意力向量a，用来计算轨迹中每个轨迹点的注意力得分，相应公式为其中，Hti表示在左侧模块中编码器生成的针对ti轨迹的注意力聚合编码，Ht'代表由右侧的编码器生成的平均轨迹重编码。通过同时最小化重构损失和相似性损失，迫使编码器产生的编码，既保持轨迹自身的独特特征，也能从同一组中的邻居轨迹那里学到相似的特征。这样，相似的编码所对应的轨迹，同时在时间和空间上具有相似性。

3实验结果

3.1实验数据和评估指标

本文在与亚洲某机场的合作研究中，获得了一个真实的乘客机场轨迹数据集。该数据集包含14 605个轨迹，约有719 507个位置点，每个轨迹包含20至120个点。本文使用此数据集来训练模型，挖掘一起行走的乘客。

将Mean-Attn与简单的LSTM自编码器（LSTM-AE）、两个经典的模式挖掘算法Convoy和Swarm，以及两个机器学习模型T2Vec（Trajectory to Vector）和BFEA（Behavior Feature ExtractionAlgorithm）进行比较。对于基于模式挖掘的两个算法Convoy和Swarm，本文比较它们抽取的簇数（旅行同伴的组数），且先学习轨迹表征，然后对表征聚类得到的簇数进行比较。为了遵循算法的要求，本文在数据集中进行线性插值，针对每条轨迹，每10s为一个时间步，在轨迹点缺失时生成一个插值点。对于T2Vec和BFEA，修改模型的输入，将位置编码添加到其原始嵌入中，以便和本文的模型进行公平比较。本文使用DBSCAN对学习到的编码进行聚类，并比较各个算法的聚类性能。

在评估轨迹表征聚类效果时，本文采用Davis-Bouldin Index、Silhouette Coefficient以及WeightedAverage Entropy（加权平均熵）这3个指标来衡量。Davis-Bouldin Index首先根据每个簇的直径找到最相似的簇，然后计算这些簇的平均相似度，因此较小的值通常表示着较好的聚类性能。SilhouetteCoefficient是衡量每个对象与相同簇内的其他对象相比于簇外的对象是否更相似的一种度量;较高的Silhouette Coefficient值表示每个对象与相同簇内的对象相似度较高，而与簇外对象的相似度较低，因此表明聚类效果更好。Davis-Bouldin Index和Silhouette Coefficient是进行聚类评估的内部指标。除此之外，本文还计算所有簇的加权平均熵并将其作为外部指标。簇的熵是聚类对象的最大似然估计，当簇中的对象的类别较为一致时，簇的熵较小。加权平均熵是所有簇的熵的加权总和，其中每个簇的权重是簇的大小除以对象总数。更好的轨迹表征应使得簇的加权平均熵较小。尽管无法得到轨迹的类别标签，但如果几名乘客是旅行同伴，那么他们更有可能乘坐同一航班。基于此假设，本文将每个轨迹的最后位置点，与10 min后的第一个航班相关联，并将该航班用作进行熵计算的轨迹标签。对于所有这些实验，本文丢弃大小为1的簇，即被视为单独移动的轨跡。

3.2实验参数设定和训练细节

MBR的大小和小批次大小设定：本文将MBR的大小和小批次的大小（输入模型时轨迹与其邻居轨迹数目的总和）分别设定为64和8，MBR的大小即使用STR算法对轨迹进行粗略分组时的组的大小。

网格单元的大小设定：将整个机场空间划分为大小相同的网格单元，每个单元的边长为5 m，共得到15 354个单元。

训练细节：本文使用Adam算法对模型进行优化，学习率固定为0.001，权重衰减率为0.000 01.当轨迹重建损失和表征相似性损失都收敛时，训练即可停止。本文观察到所有的模型都会在20轮后收敛。

3.3主要结果

本文使用DBSCAN对4个深度学习模型学到的轨迹表征进行聚类。其中，距离参数Epsilon从0到0.2进行变化，以0.000 1的增量递增;然后针对每个Epsilon进行聚类，并计算前述3种指标的结果。结果分别如图2a）、图2b）和图2c）所示。

在图2a）和图2b）中可观察到，Mean-Attn在Epsilon变化时，基本上都具有较小的Davis-BouldinIndex值和较大的Silhouette Coefficient值，这表明Mean-Attn的性能在以内部标准来评估时，在大部分情况下都优于LSTM-AE，T2Vec和BFEA。在图2a）中，当Epsilon大于0.16时，使用LSTM-AE训练的所有模型表征都被聚类到同一个簇中，因此不再有相应的指标值。当Epsilon大于0.04时，BFEA同理。T2Vec在Epsilon较小的时候表现不如Mean-Attn。但是当Epsilon大于0.15时，Davis-Bouldin Index值比Mean-Attn小，这是因为经过Mean-Attn聚类得到的同行轨迹之间的表征相似度较大，更易被分到一个簇中;而当Epsilon变大时，簇内则更易引入不相似的噪声轨迹。在图2b）中，Mean-Attn的表现稳定地优于其他3种模型。在图2c）中，还可观察到，对于变化的Epsilon，Mean-Attn生成的簇的加权平均熵始终要小于LSTM-AE、T2Vec和BFEA生成的簇。这意味着Mean-Attn产生的簇内部，乘客对应的航班标签较为一致，也即意味着相较于其他模型，Mean-Attn产生的同一个簇中的轨迹更有可能成为旅行同伴。

此外，本文还将LSTM-AE和Mean-Attn这两个模型找到的至少具有2条轨迹的簇的数量，与Convoy和Swarm提取出来的簇的数量进行了比较，结果如表1所示。对于Convoy和Swarm，本文将k设置为18（至少3 min），将m设置为2（至少有2人同行），然后将e设置为3 m和5 m。例如，表1中的第一行表示一个Convoy必须要在至少18个连续的时间点中，包含至少2条轨迹，他们的轨迹点始终是3 m密度连通的。对于LSTM-AE和Mean-Attn这两个模型，仅显示当它们发现最大数量的簇时的结果。可以观察到，即使放宽变量设定的限制，Convoy和Swarm仍生成许多只包含单个轨迹的簇。相比之下，本文提出的模型可以将更多的轨迹进行聚类，即发现更多的旅行同伴。

3.4敏感性分析

本节通过更改Mean-Attn模型中STR算法的MBR容量和小批次大小这两个超参数来执行敏感度分析。

首先，将输入模型的小批次大小固定为8，然后将STR算法的MBR容量（capacity）设为（32，64，96）。图3a）、图3b）和图3c）显示了结果。从图3中可以观察到，尽管存在细微的差异，但是当MBR容量变化时，3个测量都会产生较为相似的结果。这表明，Mean-Attn对MBR容量的选择具有一定的鲁棒性。

然后，将MBR容量固定为64，并将小批次大小（用轨迹数量（Trajectories）表示）设为（4，8，16）。图4a）、图4b）和图4c）显示了结果。从图4中可以观察到，当小批次大小等于16时，3个指标的表现均为最差。本文认为这是合理的，因为当小批次大小较大时，利用Mean-Attn训练的编码，更有可能从不太相似的轨迹中学习到特征。因此，平均编码与各个轨迹表征的偏差也会更大，这使得表征相似度损失收敛变得更加困难。根据这一结果，本文认为Mean-Attn更偏向于使用较小的批次进行训练。

3.5位置编码的效果

本文利用位置编码技术来捕获轨迹点的时间信息。为了展示这种想法的有效性，本文从轨迹点的嵌入表征中删除位置编码，然后再次训练Mean-Attn模型。随后，计算相应的Davis-Bouldin Index、Silhouette Coefficient和加权平均熵这3个指标，并和原模型的指标进行对比。结果如图5a）、图5b）和图5c1所示。

从图5中可以观察到，使用了位置编码的模型比没有使用位置编码的模型，在绝大多數情况下都表现出了更好的聚类性能。这是因为没有位置编码的Mean-Attn只能学习轨迹之间的空间相似性。在这种情况下，形状相似但在时间维度上完全偏离的轨迹，仍可能生成相似的表征，从而被误认为是旅行同伴;而包含了位置编码的Mean-Attn能够同时学习轨迹之间的时间和空间相似性，从而能被用于更精确地找到旅行同伴。

3.6轨迹可视化

为了展示旅行同伴挖掘的直观效果，本文选择数据集中某一天从凌晨00：00到凌晨02：00这2 h内的轨迹。这段时间内轨迹相对较少，能够更清晰地展示结果。本文分别对LSTM-AE和Mean-Attn生成的轨迹表征进行了DBSCAN聚类，对同一个簇中的轨迹使用相同的颜色来表示。对当DBSCAN发现最大数目的簇时（排除单个轨迹）的结果进行可视化，结果如图6a）和图6b）所示。图6中，x和y代表空间维度，z是时间维度。轨迹通常从右下位置移动到左上位置，代表从航站楼入口移动到登机口。

从图6中可以观察到，Mean-Attn可以发现5组旅行同伴，而LSTM-AE只能发现3组。在蓝色组中，Mean-Attn发现了3条轨迹，而LSTM-AE仅发现了2条轨迹，从图中可见，LSTM-AE没有发现最初偏离其他两个轨迹的那条轨迹。在LSTM-AE发现的粉红色组中，这4个轨迹其实在大部分时间里都偏离了，只是最后移到了同一个登机口。而Mean-Attn可以将它们分为2个簇（粉红色和绿色），每个簇中的2条轨迹看起来更像是旅行同伴。最后，Mean-Attn会识别LSTM-AE未发现的2个黄色旅行同伴，即使他们在大多数情况下的距离都非常接近。由此可见，Mean-Attn可以比LSTM-AE学到更适合用来挖掘旅行同伴的轨迹表征。

4结论

本文提出了一个无监督的深度模型Mean-Attn，用于发现轨迹数据中的旅行同伴。首先采用低维稠密表征技术和位置编码技术对每条轨迹进行嵌入表示。利用这两种技术，可以同时捕获每条轨迹的空间和时间信息。然后，使用Sort-Tile-Recursive算法对原始轨迹进行分组，并从每组中单独抽取小批次输到模型中，以鼓励它们向邻近轨迹学习。在模型的具体结构中，使用了共享参数的双重自编码器，分别从轨迹重构和小批次中轨迹之间的相似性两方面来约束表征的训练，同时使用了全局注意力机制对LSTM的所有隐层进行聚合，以获取最终的轨迹表征。实验结果表明，相比LSTM-AE、T2Vec和BFEA，本文提出的Mean-Attn学习到的轨迹表征，在寻找旅行同伴的应用上有更好的表现。在未来的工作中，一方面将寻找更多的真实数据集，进一步验证模型的效果;另一方面，将采用其他架构，如自注意力机制等，来改进自编码器的编码效果，从而改进旅行同伴的挖掘效率。