不断的学习,我们才能不断的前进
一个好的程序员是那种过单行线马路都要往两边看的人

DB-TOD

论文地址

摘要

轨迹数据捕获了道路网络上车辆(如汽车、出租车)的运动,并且轨迹异常值(或“异常轨迹”)表示与其他轨迹显著不同的轨迹。注意,对于轨迹异常检测问题,每个轨迹对应于给定的源和目标对(SD-pair),并且给定SD对的异常轨迹预计与对应于相同SD对的正常轨迹非常不同。以图1为例。它设计了两个SD对,分别表示为<S1、D1>和<S2、D2>,并绘制了从S1(S2)到D1(D2)的许多轨迹。注意相同颜色的轨迹走相同的路线。轨迹R1是异常值,因为它与从S1移动到D1的其他轨迹非常不同。类似地,轨迹R2被视为异常值。此外,对应于<S1,D1>的轨迹对异常值<S2,D2>的检测没有影响。
yi-chang-gui-ji-gai-shu

丰富的应用基础激发了大量的轨迹异常检测研究工作。现有的大多数工作研究的是在欧氏空间[6,9,10,21]下通过距离或密度测度来检测轨迹异常点的更一般的问题。这些方法没有考虑车辆轨迹的特殊性,如潜在道路网络的限制和有经验驾驶员的驾驶偏好。其他工作通过监督/半监督学习来解决这个问题[12,13,19]。它们都需要大量的手动标记,这在实际应用中是不切实际的。在这些离群点检测方法中,[4,25]是两种典型的车辆轨迹检测方法。[4] 提出了一种孤立轨迹异常检测方法iBOAT,该方法需要对历史轨迹数据建立倒排索引,并对数据库进行查询。[25]通过将输入轨迹与道路网络匹配并计算历史数据与输入轨迹之间的编辑距离来确定输入轨迹是否为离群值。然而,它只能基于导出的异常分数将完整的轨迹标记为正常或异常。换言之,它无法定位实际异常的子轨迹,也无法导出不完整轨迹的异常分数。我们声称,从部分轨迹推断轨迹是正常还是异常的能力实际上是非常理想的。以乘坐出租车为例。考虑到客户的取车地点和目的地,如果我们能够检测到出租车司机所走的当前路径是一个潜在的异常值,客户希望尽快收到更改,以提高服务质量,并将客户的损失和风险降至最低。作为结论,我们认为理想的车辆轨迹离群点检测方法应该具有以下特性:

  • 效率。计算速度应该很快,以支持日益增长的弹道数据量的吞吐量。
  • 积极性。在正确量化异常程度的同时,要准确地检测出假阳性率较低的异常值。
  • 预警能力。它应该支持早期检测具有部分轨迹的潜在异常值的任务。

本文尝试从一个新的角度来解决这一问题,即建立人的驾驶行为模型,并提出一种快速的车辆轨迹异常检测方法DB-TOD。采用并扩展了最大熵逆强化学习模型和自动特征修正机制对驾驶行为进行建模。我们的模型能够通过从经验丰富的驾驶员生成的历史轨迹数据中学习到的路径偏好,正确地推断出每个路段的潜在成本,从而保证了该模型的有效性。效率是通过基于模型的方法框架来实现的。也就是说,在训练了概率模型之后,就不需要再访问轨迹数据库了。对于查询轨迹,所需的唯一任务是根据非常有效的模型计算异常分数。此外,我们的方法还可以处理在观测到部分轨迹的情况下对潜在异常值的预警问题。
综上所述,本文主要做了三方面的贡献。首先,提出了一种快速的在线轨迹异常检测方法。据我们所知,这是首次从人类驾驶行为建模的角度研究离群点检测问题。该方法的计算量与通过轨迹的路段大小成线性关系,使得处理大量轨迹数据流的速度非常快。其次,通过引入自动特征修正机制,对MEIRL模型进行了扩展,提高了对驾驶行为建模的能力。第三,基于两个真实数据集进行综合实验。结果表明,DB-TOD在效率和有效性方面均显著优于现有方法。

相关工作

在文献中,轨迹异常检测方法主要分为三类:
第一类是基于距离和密度指标。[9] 研究多维数据集中基于距离的离群点检测问题。[10] 将轨迹分割成一组线段,然后通过距离和密度混合方法检测出边缘线段。[6] 提出了一种结合距离和密度的方法来检测欺诈出租车的轨迹。[21]通过两种基于密度的定义,即点异常值和轨迹异常值,来提取轨迹异常值,目的是从轨迹流数据中提取异常值。然而,它不能量化轨迹的离群度,其参数对数据集的依赖性很强。这些基于度量的方法往往研究一般的车辆运动轨迹,而忽略了车辆运动轨迹的独特性。此外,这些方法需要访问历史数据库,以计算其他轨迹的密度或距离,这进一步涉及到在数据库系统中查询轨迹数据的研究领域[8,17,20]。
第二类是基于监督/半监督学习。,[12] 提出了一种识别可疑运动的离群点检测框架。采用离散模式片段表示轨迹,提取特征进一步支持分类算法。[13] 提出了一种基于条件随机的GPS轨迹异常检测方法。[19] 提出了一种用于视频监控场景中异常行为轨迹检测的半监督学习框架。然而,这些基于监督/半监督学习的方法需要对数据集进行大量的人工标注,这对实际应用是不现实的。
第三类是基于模式检测异常值。这些方法大多是针对车辆的运动轨迹设计的,因为其形成模式的强烈倾向和对道路网络的限制。基于轨迹离群点的“少”和“不同”特性,[22]提出了一种基于隔离的iBAT方法,该方法首先将原始轨迹映射到网格序列中,建立历史网格轨迹索引,然后采用iForest算法检测孤立轨迹。然而,这种方法只能支持完整的轨迹。提出了一种改进的iBOAT算法,即iBOAT[3,4],以克服iBAT算法的缺点,支持部分轨迹的在线检测。[11] 同时考虑空间、时间和行为特征,将轨迹转化为网格轨迹。然而,它是为探测异常的海洋行为而设计的。在[24]中提出的TPRO还着重于检测车辆异常值,通过确定每个SD对的top-k流行轨迹,并根据查询轨迹和流行轨迹之间的编辑距离得出异常值分数。TPRRO是文献[25]中提出的TPRO的一个增强版本,是一种实时离群点检测算法,因为它可以检测不在历史轨迹数据集中的轨迹。注:TPRO只能检测历史数据中的异常值。然而,TPRO和TPRRO都只能在完全观测到完整轨迹的情况下得出异常值得分。

最后,我们介绍一些基本的定义。
定义2.1(道路网)。
将道路网建模为有向图 $G(V,E)$ ,其中V表示表示十字路口的顶点集,E表示路段的边集。每条边$r \in E$从一个顶点$v \in V$到另一个顶点$ v^‘ ( \neq v) \in V $,其中$r.s=v$和$r.e=v^‘$分别表示边的起始顶点和结束顶点。
初始2.2(原始轨迹)。原始轨迹$T={p1 \rightarrow p2 ... \rightarrow p_n}$是通过GPS等定位技术获得的带有时间戳的点位置列表。
在本文中,我们主要研究由出租车和汽车产生的车辆轨迹。由于出租车和小汽车的移动受到底层道路网的约束,我们采用了地图匹配算法,[15] 将轨迹映射到道路网络上,得到如下所示的边缘轨迹。为了简化我们的讨论,我们将边轨迹称为下面的轨迹,我们的工作是基于边轨迹而不是原始轨迹。
定义2.3(边缘轨迹)。边轨迹是路径$R={r1 \rightarrow r2 \rightarrow ... \rightarrow rn}$,由记录原始轨迹T路径的相邻路段列表组成,即$ \forall ri,ri+1 \in R , ri,ri+1 \in E 和ri.e=ri+1.s$。
初始2.4(路线决策)。路由决定$ai=(r_u \rightarrow r_v) \in E \times E$,表示从路段ru到相邻路段rv的过渡,其中ru.E=rv.s。我们将整套路线决策表示为A。请注意,给定一个边轨迹$R={r1 \rightarrow r2 \rightarrow ... \rightarrow rn$,它也可以用一系列路由决策来表示,即R=$a1 \rightarrow a2 \rightarrow ... \rightarrow an}$,式中$ai=(ri \rightarrow ri+1)$。
定义2.5(异常轨迹)。给定一个SD对$<rs,rd>,如果轨迹R很少出现并且与其他轨迹不同,则该轨迹R是一个异常值。

DB-TOD

DB-TOD建立一个概率模型来模拟轨迹数据的分布,并将低概率的轨迹作为离群点返回。更具体地说,给定一个SD对$<rs,rd>,如果$P(R|rs,rd) < \zeta_sd$,我们将轨迹R报告为异常值,其中$ \zeta_sd $是预先定义的阈值。
利用概率模型来检测异常值是很有前途的,因为该模型可以看作是历史数据的压缩表示和汇总。因此,对于一个新的轨迹,只需通过概率模型来获得可能性,而不需要扫描历史轨迹,这有助于提高检测速度/吞吐量,从而解决效率问题。此外,驾驶行为建模提供了一种更好的方法来理解车辆轨迹和轨迹异常的原因。

ob-tod
图2总结了DB-TOD的概述。对预处理阶段进行在线处理,以生成定义2.3中定义的映射轨迹,并收集相同SD对的轨迹。作为我们系统的关键部分,在线模型训练阶段采用了一种称为AFC-MEIRL的模型,该模型是一种概率模型,用于通过利用上述驾驶偏好对车辆轨迹进行建模。根据预处理阶段获得的历史轨迹,在线训练模型参数。在推断出模型参数后,执行两个在线异常检测任务。第一个任务是执行传统的离群点检测,即判断完全观测到的轨迹是否为离群点;第二个任务是在轨迹尚未到达目的地且仅观测到部分轨迹时尽早对潜在的离群点发出警报。本文首先介绍了如何采用逆强化学习模型对弹道数据进行建模,然后对该模型进行了改进,使其具有更好的建模能力,最后给出了如何将该模型应用于完整/部分弹道的快速在线离群点检测

MEIRL

与传统的点数据分布建模不同,轨迹是具有拓扑约束的序列数据。因此,我们采用最大熵逆强化学习,(MEIRL)模型[26],重点是通过一组历史动作轨迹对顺序决策策略进行建模。在强化学习/序列决策理论中,有三个关键要素,即状态 $\zeta$ 、行动$a$和奖励$p$。状态$\zeta \in S$表示代理的状态。动作$a \in A$指从S到S的映射。动作$a_1 = \zeta_1 \rightarrow \zeta_2$表示当前处于状态的代理$\zeta_1$,在执行操作后$a_1$,将处于状态$\zeta_2^1$。奖励$p$指执行操作后将收到的奖励,通常是状态或操作的函数。这三个要素使得决策过程的建模成为可能,即处于某一状态的agent需要考虑其将获得的报酬来决定执行哪一个动作,并且在执行某一动作后处于新的状态。它继续执行将代理从一个状态转换到另一个状态的决策,直到到达终端状态。

采用MEIRL对车辆轨迹进行建模来检测车辆轨迹异常点,可以将路段视为状态,将某一交叉口的路径决策视为路径决策,(如左转、右转或直行)作为一种行为,并将司机视为代理人。每个驾驶员沿着一个路段行驶,在十字路口做出路线选择,然后沿着另一个路段行驶。她/他继续此过程,直到到达目的地(即终点路段)。

lu-xian-jue-ce
图3(a)显示了现实世界中道路网的一部分。有8个路段$r_1,r_2,...r_8$,形成4条双向道路。我们可以通过将道路网转换为图3(b)所示的对偶图来对决策过程进行建模。然后,我们可以将状态视为路段$r_i$,将相邻路段之间的过渡(即路由决策$a_i$)视为动作$a$。对于驾驶场景,当一个人做出决策时,他/她脑海中会有一定的路径成本,例如下一条路的长度、转弯角度、道路等级等,这些路径成本很难明确量化,因此我们将其视为一项行动的潜在成本。这样,我们就可以把负的潜在成本作为报酬,因为成本越低越好,等于报酬越高。给定完整的车辆轨迹R={r_a \rightarrow r_b \rightarrow ...}$,可以表示为驾驶员连续执行的动作序列,并分别连续收取奖励。根据MEIRL[26],它对服从最大熵原理的作用序列进行建模,即:。,


目录