在许多基于位置的应用中，异常轨迹检测已经成为一项重要的任务。虽然针对这项任务提出了许多方法，但它们都存在各种问题，包括(1)无法检测异常子轨迹，这些异常子轨迹是轨迹数据中的细粒度异常，(2)非数据驱动，(3)需要足够的监督标签，这些标签的收集成本很高。本次为大家带来数据库领域顶级会议ICDE 2023的论文：《Online Anomalous Subtrajectory Detection on Road Networks with Deep Reinforcement Learning》。随着GPS设备、智能手机等移动计算和地理定位技术的进步，空间中各种运动物体(如人、车辆)产生了大量的空间轨迹数据。这些收集到的轨迹数据记录了运动物体在不同时间戳的移动轨迹，反映了物体不同的移动模式。在各种轨迹挖掘应用中，异常轨迹检测在许多实际场景中起着至关重要的作用。例如，实时车辆轨迹异常检测有助于更好地进行交通管理。此外，研究人类的流动行为以发现其异常轨迹有助于预测异常事件(如内乱和大流行爆发)。在这种情况下，异常值/异常是指不显示正常移动模式的轨迹，偏离大多数具有相同源和目的地的轨迹(称为SD对)。考虑图1中的示例。从源S(e1)到目标D(e10)有三条轨迹。如果大多数具有相同SD对<S,D>的轨迹遵循T1(蓝色)或T2(绿色)，则认为轨迹T3(红色)是异常的。 近年来，异常轨迹的检测备受关注，并提出了各种方法来解决这一问题。然而，目前的方法没有很好地解决几个关键挑战：（1）无法检测异常子轨迹。大多数现有方法仅侧重于识别粗粒度级别的异常轨迹，并检测整个轨迹是否异常。（2）非数据驱动。现有方法基于预定义的参数和或规则，并且不是数据驱动的。（3）要求有足够的监督标签。目前虽然已经开发了几种机器学习模型来识别异常轨迹，但这些方法的有效性在很大程度上依赖于监督学习框架下足够的标记数据。因此，该论文提出了一种基于强化学习的新型解决方案RL4OASD，它避免了现有方法的上述问题。论文的主要贡献如下：- 提出了第一个基于深度强化学习的解决方案来检测异常子轨迹。所提出的模型1）可以自然地检测异常子轨迹，2）是数据驱动的，3）不需要标记数据。此外，它还可以通过在线学习处理异常轨迹的概念漂移。
- 对两个真实世界的轨迹数据集（即成都和西安）进行了广泛的实验。论文将其提出的解决方案与各种基线进行比较，结果表明论文的解决方案是有效的（例如，与现有最佳方法相比，它产生了20-30%的改进）并且高效（例如，处理每个新的数据所需的时间不到0.1毫秒）生成的数据点）。
- 手动标记两个真实数据集（成都和西安）的异常子轨迹以进行测试。每个标记数据集涵盖 200个SD对和1,688个与这些SD对进行地图匹配的轨迹（1,057个）与成都数据集（西安数据集）。该标记数据集比现有已知数据集大50倍以上。
确定正在进行的轨迹的子轨迹是否异常是一个决策过程，可以建模为马尔可夫决策过程（MDP）。论文提出了一个名为RL4OASD的弱监督框架（见图2）。该框架由三个部分组成，即数据预处理、RSRNet和ASDNet。在数据预处理中，论文对原始轨迹进行地图匹配，将其映射到道路网络上并获得地图匹配的轨迹。基于地图匹配的轨迹，论文使用基于路段之间的历史过渡数据的一些启发式方法来计算轨迹中涉及的路段的一些标签。这些带有噪声的标签将用于以弱监督方式训练RSRNet。在RSRNet中，论文基于交通上下文特征和正常路线特征来学习路段的表示。这些向量形式的表示将被输入到ASDNet中，以定义用于标记异常子轨迹的MDP状态。在ASDNet中，论文将标记异常子轨迹的任务建模为MDP，并通过策略梯度方法学习策略。ASDNet输出细化的路段标签，进一步用于再次训练RSRNet，然后RSRNet为ASDNet提供更好的观察结果，以训练更好的策略。该过程进行迭代，论文将RSRNet和ASDNet组合而成的算法称为RL4OASD。2.2 数据预处理
数据处理组件涉及地图匹配过程和获取噪声标签的过程。获取噪声标签的过程涉及四个步骤：（1）论文根据不同的SD对和时隙对数据集中的历史轨迹进行分组。（2）然后，计算每组中所有轨迹从一个路段到另一个路段的转换分数。（3）对于每条轨迹，引用它所属的组，并将其映射到每个路段的一系列过渡分数。（4）通过使用阈值参数α来获得噪声标签，其中0表示正常路段，其分数大于α意味着该路段被频繁行驶，否则为1。例如，通过使用阈值α=0.5，得到T3的噪声标签为<0,1,1,1,1,1,1,1,0>。在RSRNet中，论文采用LSTM结构，它接受不同长度的轨迹并捕获轨迹背后的顺序信息。论文将两种类型的特征嵌入到表示中，即道路网络上的交通上下文特征和给定SD对的正常路线特征。交通上下文特征（TCF）。地图匹配的轨迹对应于一系列路段，每个路段自然都是令牌的形式（即路段id）。论文将RSRNet嵌入层中的每个路段预训练为向量，以捕获交通上下文特征（例如行驶速度、行程持续时间、道路类型）。为此，论文采用Toast，一种最新的道路网络表示学习模型，用于支持基于路段的应用。学习到的路段表示将用于初始化RSRNet中的嵌入层，并且这些嵌入可以通过模型训练进一步优化。正常路线特征(NRF)。给定一个时隙中的SD对，论文首先推断其中的正常路线。直观上，正常轨迹通常遵循相同的路线。如果轨迹包含一些其他路段很少经过的路段，则它可能包含异常。因此，论文通过计算经过该路线的轨迹相对于其SD对内的所有轨迹的比例来推断该路线为正常路线。推断结果是通过将阈值（用δ表示）与每个路段的分数进行比较来获得的。需要注意的是正常的路线特征和噪声标签都是0-1的形式。两者的区别在于，前者是捕获正常路线的信息，而后者的则是通过路线级别的正常路线获取。相比之下，后者用作训练 RSRNet的标签，它是通过计算边缘级别的过渡频率获得的。此外，前者在整个训练过程中使用，而后者仅用于预训练RSRNet中的表示（这将为ASDNet提供热启动）。在获得令牌形式的正常路线特征后，论文通过将令牌嵌入为one-hot向量来获得该特征的向量。论文将获得的向量称为嵌入正常路线特征。 训练RSRNet。图2展示的是RSRNet的架构。首先给定一系列嵌入的交通上下文特征xit(1≤i≤ n)，其中n表示轨迹长度，LSTM获得每个路段的隐藏状态hi。然后，将hi与嵌入的正常路线特征xin连接起来，表示为zi=[hi ；xin]。论文采用交叉熵损失在基于zi的预测标签
和噪声/细化标签yi之间训练RSRNet，即：
考虑在线异常子轨迹检测的任务是顺序扫描正在进行的轨迹，并针对每个路段，确定该位置是否发生异常。论文将该过程建模为马尔可夫决策过程（MDP），涉及状态、动作和奖励。a.状态（State）：论文将扫描路段ei时的状态表示为si。状态si(1<i≤n)表示为zi和v(ei−1.l) 的串联，其中zi是从RSRNet获得的，v(ei−1.l)表示通过嵌入其标记（即0或1）在前一个路段ei−1上的标签的向量。状态设计的基本原理是从三个方面捕获特征，即交通上下文、正常路线和先前的标签。b.操作（Action）：论文用a表示MDP的一个动作，即将每个路段标记为正常或不正常。当两个相邻路段的标签不同时，可以识别异常子轨迹边界。c.奖励（Reward）：奖励包括两部分。一种称为局部奖励，旨在捕获路段标签的局部连续性。理由是正常路段或异常路段的标签不会频繁改变。第二个称为全局奖励，旨在指示改进标签的质量（由RSRNet的交叉熵损失表示）。论文将损失作为一些反馈来指导ASDNet的训练。本地奖励是中间奖励，它鼓励路段上标签的连续性。具体来说，它被定义为：全局奖励旨在衡量ASDNet改进标签的质量。论文将改进后的标签输入RSRNet，并将全局奖励计算为：MDP的政策学习。MDP的核心问题是学习一个策略，该策略指导智能体根据构造的状态选择行动，以使累积奖励最大化。论文通过策略梯度方法学习策略，称为REINFORCE算法，其计算如下：RSRNet和ASDNet的联合训练。论文联合训练两个网络（RSRNet和ASDNet）。首先，在道路网络上绘制原始轨迹并生成噪声标签。然后随机采样200个轨迹来分别预训练RSRNet和ASDNet。对于RSRNet，论文使用噪声标签以监督方式训练网络。对于ASDNet，论文将其操作指定为噪声标签，并通过梯度上升步骤训练策略网络。预训练为两个网络提供了一个热启动，其中两个网络的参数已合并联合训练前从正常路线获取的一些信息。在联合训练期间，论文随机采样10,000个轨迹，对于每个轨迹，生成5个epoch来迭代训练RSRNet和ASDNet。论文应用从ASDNet学习到的策略来获得改进标签，并使用改进标签来训练RSRNet，以获得每个路段上更好的表示zi。然后，使用zi构建状态以在ASDNet中学习更好的策略。由于学习的策略可以进一步细化标签，并且两个网络是联合训练的，在此过程中选择最佳模型。
RL4OASD算法基于学习的策略来检测异常子轨迹。该过程如算法1所示。具体来说，RL4OASD以在线方式接受持续轨迹，将每个路段标记为正常（即0）或非正常（即1）（第 19行）。它首先根据定义将源路段或目标路段标记为正常路段（第2-3行）。然后，它通过调用RSRNet（第5-6行）构建一个状态，并根据ASDNet中学习到的策略对动作进行采样以标记路段（第7-8行）。它监视路段上涉及异常标签（即1）的异常子轨迹，并在其形成时将其返回（第9行）。最后，如果没有检测到异常，算法将返回正常轨迹标签（第11行）。论文进一步开发了两项增强功能来提高RL4OASD的有效性和效率。一种称为路网增强标签（RNEL），另一种称为延迟标签（DL）。
路网增强标签。对于RNEL，论文利用道路网络的图结构来帮助标记路段，其中路段上的标签在以下三种情况之一是确定性的：(1)如果ei−1.out = 1，则 ei.in = 1，则 ei.l = ei−1.l。(2) 如果 ei−1.out = 1，ei.in > 1且ei−1.l = 0，则ei.l = 0。(3) 如果 ei−1.out >1，ei.in = 1，ei−1.l = 1，则ei.l = 1。这里，ei.out和ei.in分别表示路段ei的出度和入度，ei.l表示道路的标签段ei。它们背后的共同直觉是：（a）异常状态从ei−1处的正常（0）到ei处的异常（1）的任何变化都意味着存在从ei−1到其他路段的替代过渡（即，ei−1.out >1); (b) 异常状态从ei−1处的异常(1)到ei处的正常(0)的任何变化都意味着存在从其他路段到ei的替代过渡（即ei.in > 1）。根据规则，论文仅通过强化学习模型在其他情况下执行操作，因此可以避免一些潜在的错误决策。此外，由于通过检查规则而不是调用RL模型来节省某些情况下采取行动的时间，因此可以提高效率。 延迟标签。对于DL，只要识别出边界，RL4OASD就会形成一个异常子轨迹，即，如果ei−1.l = 1 且 ei.l = 0，则边界被识别在 ei−1 处。直观上，形成一个异常子轨迹看起来有点仓促。异常的子轨迹，可能会从目标轨迹中产生许多短碎片。因此，论文将延迟技术视为后处理步骤。具体来说，当形成异常子轨迹时，它会扫描ei−1之后的D个路段。在D条路段中，选择最终位置j(i−1<j≤ i−1+D)，其中该路段的标签为1，然后将位置i−1和j之间的一些0转换为1。可以验证，延迟标记不会产生太多时间成本，并且提供了更好的连续性，避免形成太多碎片。时间复杂度。RL4OASD算法的时间复杂度为O(n)，其中n表示目标轨迹的长度。时间由两个网络主导，即RSRNet和ASDNet。在RSRNet中，一段路段的时间成本包括(a)获取TC和NRF嵌入的时间成本，均为O(1)。(b)通过经典LSTM单元获取z的时间成本，即 O(1）。在ASDNet中，一条路段的时间成本包括(a)构建状态的时间成本，其中z部分已在 RSRNet中计算，v(e.l)部分通过嵌入层获得，其复杂度为O(1)。(b)通过学习的策略对动作进行采样，其时间复杂度为O(1)。正如在算法中看到的，两个网络最多被调用n次。因此，RL4OASD的时间复杂度为O(n) × O(1) = O(n)。对于轨迹或子轨迹异常检测任务，O(n)时间复杂度保持了现有算法当前最好的时间复杂度，并且可以很大程度上满足在线场景的实际需求正如论文的实验所示。数据集：实验在滴滴出行的两个真实世界出租车轨迹数据集（成都和西安）上进行。所有原始轨迹都通过流行的地图匹配算法预处理为地图匹配轨迹，两个城市的道路网络从OpenStreetMap获得。根据之前的研究，论文对数据集进行预处理并过滤那些包含少于25条轨迹SD对，以获得足够的轨迹来指示正常路线。论文从数据集中随机抽取10,000个轨迹进行训练，其余的进行测试。基线：实验将IBOAT、DBTOD、GM-VSAE、SDVSAE、SAE、VSAE和CTSS这七种方法作为基线方法进行比较。参数设置：在RSRNet中，林伟将TCF和NRF特征嵌入到128维向量中，并使用具有128个隐藏单元的LSTM来实现RSRNet。参数α、δ和D分别设置为0.5、0.4和8。为了训练RSRNet，通过实证研究以一小时的粒度计算24个时隙中的噪声标签。在ASDNet中，标签向量v(ei.l)的维度为128。策略网络采用单层前馈神经网络实现，并采softmax函数作为激活函数。根据实证结果，RSRNet和ASDNet的学习率分别设置为0.01和0.001。评估指标：为了验证子轨迹检测的结果，论文考虑两个评估指标F1-score与F1-score的变体T-F1-score。论文使用标记数据集研究异常子轨迹检测。表1报告了不同轨迹长度的有效性，例如，手动将成都数据集分为四组，即G1、G2、G3和G4，使得组中的长度为G1 < 15、15 ≤ G2 < 30、30 ≤ G3 < 45 和 G4 ≥ 45。论文还报告了整个数据集的整体有效性。结果清楚地表明，RL4OASD在不同设置方面始终优于基线。具体来说，就成都（分别是西安）的F1-score分数和T-F1score而言，它比最佳基线（即CTSS）高出约20%和15%（分别为30%和 28%）的整体效果，西安（成都）数据集上F1-score和T-F1-score分别提高约5%-26% 和1%-19%（分别为26%-47%和22%-45%）。一个可能的原因是CTSS需要一个阈值来提取那些异常分数大于阈值的异常部分。然而，很难针对所有复杂的流量情况适当地设置阈值。RL4OASD展示了其优越性，这主要是由于其对于异常子轨迹检测任务的数据驱动性质。此外，论文观察到RL4OASD在F1-score和T-F1-score方面表现出相似的结果趋势，这表明了方法的通用性。表1 与现有基线的有效性比较（左：F1-分数，右：T F1-分数）
图3报告了成都和西安数据集上每个点平均运行时间的在线检测效率。可以观察到成都的运行时间比西安长，因为西安的轨迹普遍较短。还观察到DBTOD在两个数据集上运行速度最快，因为它是一个轻模型，具有一些更便宜的特征（例如用于检测的道路水平和转向角度）的低维嵌入，可以非常快速地完成，而RL4OASD涉及更多操作，包括基于LSTM的RSRNet来捕获特征，以及基于RL的ASDNet来标记每个路段。CTSS运行速度最慢，因为其涉及离散Frechet距离来计算目标轨迹与给定参考轨迹之间的偏差，其时间复杂度为二次方。此外，对于通过生成方案提出的用于轨迹检测的四种基于学习的方法GM-VSAE、SD-VSAE、SAE和VSAE，可以观察到SD-VSAE和VSAE通常比其他方法更快（即GM-VSAE和SAE）。这是因为SAE是用传统的Seq2Seq结构提出的，其中涉及到编码和解码的操作，需要扫描轨迹两次。与SAE相比，VSAE没有编码步骤，只涉及解码步骤来检测一些可能的异常。对于SD-VSAE，它是GM-VSAE的快速版本，它仅使用其SD模块在编码（或推理）步骤中预测一个高斯分量；然而，GM-VSAE在编码步骤中需要多个组件，并使用所有这些组件来检测解码中的异常。总体而言，RL4OASD的运行速度相当快，能够满足实际需求，例如处理每个点的时间不到0.1ms，比轨迹数据的实际采样率（2s）快了20,000倍。
论文研究了道路网络上的在线异常子轨迹检测问题，并提出了第一个基于深度强化学习的解决方案，称为RL4OASD。RL4OASD是一种数据驱动的方法，无需标记数据即可进行训练。论文对两个真实世界的出租车轨迹数据集进行了广泛的实验，并手动标记了异常情况。结果表明，RL4OASD始终优于现有算法，运行速度相当快。| 重庆大学计算机科学与技术2022级硕士研究生，重庆大学START团队成员。 | 
|
重庆大学时空实验室（Spatio-Temporal Art Lab，简称Start Lab），旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有2~3名研究生名额，欢迎计算机、GIS等相关专业的学生报考！
