许多重要的应用都依赖于详细的轨迹信息，由于记录仪器的带宽、电池续航和容量的限制，绝大多数轨迹数据都是稀疏的，这导致依赖轨迹的应用程序的准确性和质量下降。目前已经有一些方法用于提高轨迹数据精度，这些技术绝大部分依赖于已有的路网数据，即从（全部或者部分）轨迹中推断道路网络。但事实上，路网数据并不总是可用或可靠的，这就需要新的轨迹插值技术来解决这个问题。本次为大家带来数据库领域顶级会议VLDB 2024 的文章《KAMEL: A Scalable BERT-based System for Trajectory Imputation》。许多重要的应用程序严重依赖GPS设备生成的轨迹数据，这些应用包括路径搜索(路由)、交通监控和预测、基于位置的服务、联系人追踪、地图推断和城市规划等，轨迹数据的准确性会影响到这些应用的服务质量。为了提高轨迹数据的准确性，通常基于已有路网数据对轨迹进行修正，但是路网数据本身也可能是不准确甚至不可用的，比如微软宣称其现有地图上存在100多万公里的缺失。文章介绍了一种名为Kamel的可扩展的新型轨迹修正框架，它有如下几个特性：（1）不需要预先输入路网信息；（2）不需要高密度的轨迹数据；（3）支持大规模区域的轨迹修正；（4）支持离线批量模式和在线模式的轨迹输入流。该框架的主要思想是将轨迹插值（Trajectory Imputation）问题转化为自然语言处理（NLP）中的寻找缺失词（finding missing word）任务，使用的NLP模型为BERT，并且解决了如下几个模型应用的问题：（1）无空间感知。BERT产生的结果可能在现实世界中不存在；（2）数据差异。训练数据因子，即每个单词在训练集中的平均出现次数，相比于语料数据中的每个单词，轨迹数据中每个点平均出现的次数更低，这会影响模型的训练效果；（3）多缺失点。轨迹插值需要在两个已知点中找到一个或多个缺失点，这与BERT一次输出一个缺失词不同，需要进行转换。 Kamel主要包括5个模块：Tokenization、Partitioning、Spatial Constrains、Multipoint Imputation和Detokenization，详细的框架图如图1所示。它接收两种输入数据：训练数据和用户输入的稀疏轨迹。输入数据经过Kamel处理后生成稠密轨迹并输出。Tokenization：将每个输入点转换为覆盖特定空间区域的token，减少了原输入的数量，并且增加了每个输入在训练集出现的次数。Partitioning：基于输入数据的空间覆盖情况构建多种BERT模型，后续根据新的训练数据扩展已有模型，接收一系列代表轨迹的tokens，选择性的选取模型进行插值。Spatial Constrains：接收一组候选tokens集合，丢弃不满足空间约束的集合，解决空间感知问题。Multipoint Imputation：从候选的tokens中选取概率最大的token作为结果，并迭代的调用BERT模型输出一系列tokens。Detokenization：Tokenization的逆过程。将tokens还原成修正后的轨迹。将原始空间划分为一组不重叠的单元，单元内的所有空间点都被赋予相同的token。考虑两个问题：（1）划分方式；（2）划分大小。采用正六边形而不是矩形进行划分。使用六边形进行划分可以使得每个单元的六个邻居到质心的距离相同，并且保证每个相邻的邻居共享相同的边界长度（矩形的长宽边界长度不相等），同时将点映射到六边形单元的开销是恒定的，可以通过坐标系转换完成。单元大小将会影响Kamel的准确性，较大的覆盖单元可以让每个token的平均出现次数增多，提高插值准确性，但是单元内过多的空间点又会导致Tokenization和Detokenization的效果，为此Kamel会对输入数据进行采样尝试不同的大小，并选择最高精度情况下对应的大小。原始BERT分别针对不同语言进行训练并预测，对应到Kamel中则是针对不同空间区域进行轨迹插值。Kamel中维护了两个仓库：（1）轨迹仓库，维护Tokenization后的轨迹；（2）模型仓库，维护了为不同区域构建的BERT模型。模型的构建和更新是离线完成的，轨迹插值过程是在线完成的，因此模型更新不会影响到在线的轨迹插值过程。模型存储库的数据结构如图2所示，在该数据结构中，每一层存储了不同数量的BERT模型，阴影部分代表已建立BERT模型的空间，只有包含了到达某一数量的tokens时我们才建立模型。考虑到内存开销，我们并不需要对每一层都进行维护。每一层的单元有两类：Single-cell和Neighbor-cell，后者主要用来处理划分边界附近的轨迹插值问题。每个单元包含以下一个或多个内容：（1）覆盖范围内轨迹的tokens数量；（2）BERT模型及元数据，如最新更新日期等；（3）至多两个邻居单元格的BERT模型（及元数据）和指针。该数据结构具有高度扩展性，可以对每个单元格进行构建和更新，详情操作参见原论文。最后需要指出的是，对于那些无法适应任何模型的子轨迹，通过简单的直线进行填补。空间感知的实质就是从BERT模型的原始输出结果中剔除那些不符合常识的结果，Spatial Constrains就是实现这一目的的手段，其在实现了物理运动约束的基础上，还避免了算法运行过程中可能产生的循环。（1）速度约束：给定时间范围和速度，车辆行驶区域是有限度的。（2）方向约束：车辆行驶时必须以正确的顺序和合理的偏向角行驶。在图3中举出了几个例子，其中t4是被速度约束拒绝的token，因为其位于绿色区域外；t5是被方向约束拒绝的token，因为其位于D和t2方向的45°夹角内（红色区域）。在使用BERT进行多个空间点插值的过程中可能会导致循环，如果发现插值序列的最后x个tokens是重复的，此时就发生了循环，而一旦检测到循环就会拒绝所有的结果。Kamel通过设置x值来定义循环，可以通过合理设置这个值避免错误的判断循环情况，图3.d提供了一个立交桥寻路的例子：在这个例子中，Kamel的插值结果为t8、t7、t6、t8，尽管t8出现了两次，但是并没有拒绝这个轨迹，因为这个轨迹没有任何长度的重复序列。2.4 Multipoint Imputation该模块提供了两种算法使得BERT支持在每两个连续轨迹token中进行多个tokens的插值。分别为Iterative BERT Calling和Bidirectional Beam Search。 2.4.1 Iterative BERT Calling该方法通过迭代调用BERT，在原始相邻的token中连续插入多个token，直到任意token之间的间隙距离小于gap。算法1提供了Iterative BERT Calling的伪代码，原始相邻的S和D经过BERT和Spatial Constraints处理后，得到了合理的候选tokens集合，然后插入其中概率最高的token，并检查token之间是否存在大于gap的间隙，如果存在则找到这个token，然后继续调用BERT。2.4.2 Bidirectional Beam Search迭代调用BERT基于贪心策略的方法，获取的解可能不是全局最优，因此提出Bidirectional Beam Search方法，旨在选取源token和目标token之间最可能的tokens序列。该方法的主要思想为：（1）在多个方向上搜索并跟踪最可能的token序列，确保最后的解是全局最优的；（2）通过乘法计算token序列的概率，并根据序列长度进行归一化，避免较长序列的概率过低。 该算法通过在AllGaps中进行插值后，选取了前B个最大概率的Segments，并将符合要求的Segments及其对应归一化的概率记录到全局解中，将不符合要求的Segments在下一阶段继续进行插值，直到所有解都被记录且全部符合要求，最终选取所有解中概率最大的解，从而确保了全局最优。Multipoint Imputation模块的输出结果是一组六边形的token，Detokenization获取此输出并且将每个token转换为一个点。当原始的轨迹数据上传到Kamel时，使用DBSCAN聚类算法对token内的点进行空间聚类，聚类结果可能出现三种情况：（1）当数据量足够时，token内出现了多个聚类中心（图4.(a)）；（2）当数据量较少时，token的聚类中心几乎是所有数据的质心（图4.(b)）；（3）当数据量严重不足时，DBSCAN算法甚至不能运行，此时聚类中心为六边形的质心（图4.(c)）。该过程是离线进行的。 在对轨迹进行在线插值时，Detokenization环节对图4.(a)中的情况，会计算当前token与前一个匹配token的入角以及和后一个匹配token的出角的平均值，然后选择与该方向角更近的簇。对于图4.(b)、4.(c)的情况，则选取数据质心或者六边形质心作为轨迹点。基线方法：将基于真实系统实现的Kamel与TrImpute进行比较，还比较了线性插值，其中轨迹由一条简单的直线输入。为了进行完整的分析，将Map Matching结果作为依赖道路网络的技术示例。数据集：（1）Porto, Portugal. 出租车行驶的1.7M条轨迹，由约83M个GPS点组成，行驶总长度约8.8M公里，行驶总面积约500平方公里。（2）Jakarta, Indonesia. 共享单车行驶的56K条轨迹，由约56M个GPS点组成，行驶总长度约500K公里，行驶总面积约660平方公里。评价指标：（1）召回率：在真实轨迹点集合P中，成功召回的比例；（2）精度：在插值轨迹点集合Q中，成功召回的比例；（3）失败率：由于无法对轨迹段进行插值，从而采取线性插值方法。失败率定义为线性插值轨迹段的比例；（4）时间开销：算法运行过程中训练和插值时间。 参数设置：（1）token之间允许的最大间隔为100m；（2）精度阈值（即认为匹配成功时，真实点和匹配点之间可容忍的距离）为50m（Porto）和20m（Jakarta）；（3）认为轨迹稀疏的距离为1km；（4）分割时六边形尺寸设置为75m；（5）Beam Search时取前B个最大概率的tokens段，B取10；（6）模型仓库金字塔结构中维护层数为3，总层数为10。（1）CPU：Intel(R) Xeon(R) Silver 4112 CPU @2.60 GHz主要考虑以下几个方面进行了实验：（1）数据集中轨迹点的稀疏情况；（2）精度阈值；（2）训练和插值时间开销；（3）道路类型、划分网格类型和训练数据属性；（4）针对Kamel各个部分的消融实验。我们主要介绍（1）、（2）、（4）三个方面。如图5所示，结果说明Kamel相比于其它方法（除了对照的地图匹配方法）在短距离和中距离稀疏情况下有最好的性能，在长距离稀疏情况下仍有效果，并且始终保持了可接受的失败率。如图6所示，结果说明三种方法在应对较高的精度阈值时表现不错，但是随着精度阈值减小，匹配精度上升，Kamel的优势逐渐展现出来。Kamel无论在训练还是插值时间的开销上相比于TrImpute都更高。对于训练过程，因为涉及到BERT复杂的训练过程，Kamel要花费更多的时间，但由于训练是离线进行的，所以时间差距影响不是很大；对于插值过程，Kamel以更长的运行时间换取了更高的预测精度。消融实验通过比较下列4种系统变体进行：（1）Kamel：完整系统；（2）No Part：禁用Spatial Partitioning模块；（3）No Const：禁用Spatial Constrains模块；（4）No Multi：禁用Multipoint Imputation模块。如图8所示，对比不同稀疏距离下的召回率和精度，去除任何模块都会导致召回率和精度下降。去除Multipoint Imputation模块对召回率产生的影响最大，因为系统只预测了相邻token中的一个点，降低了召回率。去除Spatial Constrains对精度的影响最大，而对召回率影响最小，因为去除该模块并不影响对部分轨迹的正确插值，但是会产生一些额外的噪声点，导致精度下降。 考虑精度阈值，无论是召回率还是精度，发现Spatial Partitioning模块在中等偏下的精度阈值下具有非常重要的作用，因为在较低的精度阈值下，No Part曲线最低，但随着精度阈值逐渐增加，在中等大小的精度阈值下，No Part曲线最高，并且这个过程中该曲线上升幅度最大。论文介绍了一种可扩展的基于BERT的轨迹插值系统Kamel，Kamel将轨迹插值问题转换为NLP中的寻找缺失词问题。由于BERT并不适合于轨迹插值问题，因此，Kamel框架引入了Tokenization、Partitioning、Spatial Constrains、Multipoint Imputation和Detokenization 5个模块使得BERT适用于轨迹插值。这些模块调整了轨迹数据的性质，使其更适合BERT，并在BERT的输入和输出中都注入了空间感知。基于真实系统实现和真实数据集的实验结果表明，Kamel显著优于实验中使用的其它方法。此外，Kamel能够在紧密的精度阈值下插值城市范围的轨迹，填补需要数十个插值点的大型稀疏间隙。
| 重庆大学计算机科学与技术专业2024级硕士生，重庆大学Start Lab团队成员。 | 
|
重庆大学时空实验室（Spatio-Temporal Art Lab，简称Start Lab），旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有3~5名研究生名额，欢迎计算机、GIS等相关专业的学生报考！
图文｜黄天羽
编辑｜李佳俊
审核｜李瑞远
审核｜杨广超
