DeepTEA: Effective and Efficient Online Time-dependent Trajectory Outlier Detection

PVLDB 2022. DeepTEA: Effective and Efficient Online Time-dependent Trajectory Outlier
Detection

Abstract

研究异常轨迹检测,目的是提取道路中车辆的异常移动。可以帮助理解交通行为,识别出租车欺诈。由于交通状况在不同时间不同地点会发生变化,所以这个问题具有挑战。本文提出了Deep-probabilistic-based time-dependent anomaly detection algorithm (DeepTEA)。使用深度学习方法从大量轨迹里面获得time-dependent outliners,可以处理复杂的交通状况,并精确地检测异常现象。本文还提出了一个快速的近似方法,为了在实时环境下捕获到异常行为。相比SOTA方法,本文方法提升了17.52%,并且可以处理百万计的轨迹数据。

2. Problem Definition

Definition 1(Trajectory). 轨迹点$p_{t_i}$是一个三元组$(t_i, x, y)$,分别是时间戳、纬度、经度。轨迹$T$是一个轨迹点的有序序列$$,其中$t_1 < \dots < t_i < \dots < t_n$。

轨迹异常检测分为两类,一类是只考虑与正常路线不同的异常轨迹。另一种是考虑与time-dependent的正常路线不同的异常轨迹。

Definition 2(Time-dependent Trajectory Outlier)。给一条轨迹$T$,起点$S_T$,终点是$D_T$,还有travel时间,一个time-dependent轨迹异常定义为:相同的$S_T$和$D_T$以及相同的出发、到达时间下的轨迹里面,一个很稀有的、不同于其他轨迹的轨迹。

举例,如果一个轨迹在2016年10月1日的上午10点出发,11点到达,那么一条稀有的轨迹且和相同时间相同OD的轨迹不同的轨迹就是这个Time-dependent Trajectory Outlier.

Problem 1(Online Time-dependent Trajectory Outlier Detection)。给定一条正在前进的轨迹$T$,实时计算并更新这条轨迹是时间依赖的异常轨迹的概率。

3. The DeepTEA Model

3.1 Framework

给定轨迹$T$,在旅行过程中推算latent traffic pattern $q(z \mid T)$。轨迹观测值 $\tau$ 反映时间依赖的轨迹转移,可以在 inference network 里面用来建模latent time-dependent route $r$。之后,time-dependent route $r$用来生成轨迹观测值$\tau$。

3.2 Latent Traffic Pattern Inference

latent traffic pattern $z$,表示旅途过程中的动态交通状况,比如 $\{\text{smooth} \rightarrow \text{congested} \rightarrow \text{smooth} \}$,或者$\{\text{congested} \rightarrow \text{smooth} \}$。

3.2.1 Challenges

给定轨迹 $T$,我们想基于 $T$ 的空间转移,推算出 latent traffic pattern $q(z \mid T)$。举个例子,一个远距离的移动表明当时的交通状况是通畅的。但是一个轨迹 $T$ 可能表示一些随机行为,比如停车休息,这种行为不能表明当时的交通状况。这是在表示实际交通模式时的第一个挑战。第二个挑战是交通状态在不同的地方,不同的时间是不同的,动态的。同一时间,不同OD也是不一样的。而且在整个旅途中的交通状态变化也是剧烈的。可能开始的时候顺畅,结束的时候拥堵。捕获交通状态很重要,因为它对时间依赖的正常路径影响很大。

3.2.2 Design

为了解决第一个挑战,我们从时间 $t_i$ 的一组轨迹 $\{ T_{t_i} \}$ 里面学习latent traffic pattern $z$,而不是单条轨迹 $T$。这里我们用 time point series 表示旅行时间。为了从 $\{ T_{t_i} \}$ 里面很好地组织交通信息,我们使用一个 map grid matrix $Z_{t_i}$,这里面每个单元表示平均速度,用这个对 $t_i$ 的交通状态建模。从图2可以看出,红色表示速度低,表示拥堵。绿色表示畅通。黄色表示即将拥堵,平均速度介于红绿之间。为了解决同一时间不同位置交通状态的多样性,我们用CNN建模。对于没有车辆的区域,CNN可以从有车辆的单元学到信息,而不是将他们表示为缺失值。因为实时状态下交通状况变得很频繁,我们用RNN捕获这种不断变化的动态性,解决第二个挑战。交通状态的变化可以通过RNN很好的建模。然后我们用一个高斯分布和RNN的隐藏状态,推算 latent traffic pattern $z$。CNN+RNN选用了 Convolutional LSTM。

我们用上面的随时间变化的动态交通状态来推算latent traffic pattern $z$。这里的想法是交通状态会因为复杂的实时特征发生变化,比如信号灯、事故、早晚高峰。因此,我们在DeepTEA里面会随时间变化更新$Z$,表示为$Z_{t_i}$,表示轨迹点$p_{t_i}$在时间$t_i$的交通状态。我们会从实际交通状况$Z = \{ Z_{t_i}, Z_{t_{i+1}}, \dots, Z_{t_{i+n}} \}$里面推算latent traffic pattern $z$。这里面的交通状况对应的时间分别是对应轨迹点$\{ p_t, p_{t+1}, \dots, p_{t_{i+n}} \}$的时间。对于真实交通状况$Z$,我们可以得到轨迹$T$经过的时间的平均速度。换句话说就是,真实交通状况$Z_{t_i}$是一个平均速度矩阵,它包含了整个城市在$t_i$的移动状态。如果两个轨迹点之间的时间差很小,那么$Z_{t_i}$和$Z_{t_{i+1}}$可能会很相似。这样的话,我们需要把速度按时段提前聚合起来,就取平均速度,比如10分钟的时段,而不再使用时间点。为了减轻稀疏的问题,我们使用CNN将有车辆的位置的信息传播到没有车辆没数据的位置上。为了捕获不同时段的动态变化,我们用RNN建模时间维度的交通转移。这样,spatial traffic correlation和temporal transition通过$f_1(Z)$来捕获:

这里函数$f_1(\cdot)$是一个CNN+RNN,CNN对每个$Z_i$都使用,然后用RNN对他们建模,捕获traffic transition。

为了让模型具有生成能力,并且对交通状态的不确定性建模,在给定实际交通状态$Z$的时候,我们用高斯分布对latent traffic pattern $z$建模,可以用来在给定轨迹$T$时近似latent traffic pattern $z$的分布,如公式2所示。我们将参数记为$\phi$,

均值$\mu_Z$和标准差$\sigma_Z$通过MLP函数 $g_1(f_1(Z))$得到,参数是$\phi = \{ f_1(\cdot), g_1(\cdot) \}$。

这种方式在给定轨迹$T$的时候可以很好的推断出latent traffic pattern $z$。在训练阶段,参数$\phi$可以学到如何捕获latent traffic pattern $z$,而且能表示交通状态的多样性和动态性。

3.3 Latent Time-dependent Route Inference

3.3.1 Challenges

轨迹$T$不仅可以表示位置信息,还可以表示两个轨迹点之间转移的latent traffic pattern $z$。相比只最大化位置信息的似然,对位置和latent traffic pattern $z$同时做更informative,因为它可以反映在时间依赖的交通状态下的轨迹转移。

3.3.2 Design

一条轨迹 $T$ 不仅能反映位置 $p_{t_i}$,还能基于两个连续轨迹点 $p_{t_{i-1}}$ 和 $p_{t_i}$ 之间的转移,传递出 latent traffic pattern $z$。这里我们用 $o(p_{t_i}, z)$ 表示轨迹 $T$ 背后的观测值 $\tau_i$。这里希望用一个神经网络处理观测值 $p_{t_i}$ 和 $z$:

我们使用一个神经网络学习 latent traffic pattern $z$ 的观测值 $p_{t_i}$:

$\text{NN}$的参数是$W$和$Q$。

然后,我们学习一条轨迹 $T$ 经过的 latent time-dependent route $r$。我们解释过,轨迹 $T$ 不仅能表示轨迹点 $p_{t_i}$ 的位置信息,还能指明两个轨迹点之间转移的 latent traffic pattern $z$。latent time-dependent route $r$ 的含义可以解释为:高峰时间段城市路段的交通状态是拥堵的,驾驶员通常会上高速,因为那里会畅通。

轨迹 $T$ 经过的 latent time-dependent route $r$ 的表示为:

$\gamma$ 是推测 latent time-dependent route $r$ 时的参数。

基于之前的轨迹点和 latent traffic pattern $z$,我们可以用RNN获得轨迹观测值之间的转移,RNN记为 $f_3$,这里使用GRU:

$h_{i-1}$ 是之前观测值 $\tau_{i-1}$ 的隐藏状态,也就是轨迹点 $p_{t_{i-1}}$ 带着 latent traffic pattern $z$。

对于轨迹观测值的不确定性,我们通过高斯分布建模 $q_\gamma (r \mid T)$:

我们用一个神经网络 $g_3(h_n)$ 来学习均值和标准差。

为了在 latent traffic pattern 里面区分正常的轨迹转移和异常的轨迹转移,需要设计一个模块对轨迹里 latent time-dependent normal route建模,这里 $z$ 会提供 time-dependent traffic 信息。使用高斯分布:

$k$ 表示 latent time-dependent route 的类型,服从多项式分布:

$\pi$ 是多项式分布的参数。然后,趋近 $q_\gamma (r \mid T)$ 的均值的 latent time-dependent route 是time-dependent normal route。

然后,推断网络可以从给定的轨迹 $T$ 里面推算 latent time-dependent route $r$,latent time-dependent route type $k$,还有 latent traffic pattern $z$ 为 $q_{\gamma,\phi}(r, k, z \mid T)$。通过使用 mean-field approximation,可以分解为:

$q_\gamma (k \mid T)$ 可以转换为在给定 轨迹 $T$ 经过 latent time-dependent route $r$ 的条件下,route type $k$ 的分布:

$K$ 是一个超参数,表示 route 类型的个数。

因此,推断网络可以从轨迹 $T$ 的观测值 $o(p_{t_i}, z)$ 推断出 latent time-dependent route $r$。$\gamma = \{ f_2(\cdot), f_3(\cdot), g_3(\cdot), \pi, \mu_r, \sigma_r \}$ 这些都是参数。

3.4 Trajectory Observation Generation

生成轨迹观测值的目标是给定 latent time-dependent route $r$,time-dependent route type $k$ 和 latent traffic pattern $z$ 时,最大化生成轨迹观测值 $\tau_i$ 的概率,也就是 $o(p_{t_i}, z)$。这个概率记为 $p_\theta (T \mid r, z, k)$,$\theta$ 表示用于生成过程的参数。从对称的角度来看,我们用RNN来生成轨迹观测值 $\tau_i$,也就是 $o(p_{t_i}, z)$:

RNN的起始输入是 $\eta_0$。从 $\eta_1$ 开始,输入变成上一个隐藏状态 $\eta_{i-1}$ 和轨迹观测值 $o(p_{t_i}, z)$。因此,观测值 $\tau_i$,也就是 $p_{t_i}$ 在 latent traffic pattern $z$ 的时候,可以通过下面的公式生成:

$g_4(\cdot)$是一个函数,把输出映射到网格的个数。softmax 用来把概率的和变成1。然后轨迹观测值 $\tau_i$ 可以通过多项式分布生成。

因此,轨迹观测值 $\tau_i$,也就是 $o(p_{t_i}, z)$,可以基于 latent time-dependent route $r$,route type $k$ 和 latent traffic pattern $z$ 生成。我们给生成用的参数记为 $\theta = \{ f_4(\cdot), g_4(\cdot) \}$。这些参数会在训练的过程中学到。

3.5 Optimization

我们上面讲了,轨迹观测值不仅能反映位置信息,还能基于两个连续的轨迹点的转移传递出 latent traffic pattern。因此,目标函数是最大化观测到的轨迹的边缘对数似然:

我们通过最大化ELBO来优化上面的边缘对数似然函数:

轨迹 $T$ 的边缘对数似然函数的 ELBO 通过下面的公式计算:

其中,$p_\theta(z)$ 是 latent traffic pattern $z$ 的先验概率。生成网络 $\log p_\theta(T \mid r, z, k)$ 可以通过下面公式计算:

整个训练过程的算法如算法1所示。在训练过程中,模型参数通过优化轨迹 $T$ 的 ELBO 来学习。然后这些学到的参数会用于 online anomaly detection,后面会介绍。

3.6 Complexity Analysis

训练 DeepTEA 的复杂度是 $O(N \cdot (d_{Z_1} d_{Z_2} \bar{V} + \bar{n}))$,$N$ 是轨迹数,$d_{Z_1}$ 和 $d_{Z_2}$ 是 $Z$ 的大小,$\bar{V}$ 是时间间隔的平均个数,$\bar{n}$ 是轨迹的平均长度。

Online Trajectory Outlier Detection by DeepTEA

基于算法1学习得到的参数,当下一个轨迹观测值 $\tau_{i+1}$ 实时过来的时候,异常分数会实时更新。这个过程要快。而且直到轨迹完成,这个异常分数都要更新。

4.1 Online Detection by Generation

图3展示了在线异常轨迹检测的步骤。

我们通过学到的网络生成观测到的轨迹来检测异常。latent time-dependent route 的分布 $q_\gamma (r \mid T)$ 可以通过参数 $\gamma$ 来计算。latent traffic pattern $z$ 可以通过参数 $\phi$ 和 $Z$ 获得。给定 $q_\gamma (r \mid T)$ 里面第 $k$ 个均值 $u_k$,我们用 RNN 生成轨迹观测值:

RNN的起始输入是 $\eta_0$,这里设置为 $u_k$。从 $\eta_1$ 开始,输入标称隐藏状态 $\eta_{i-1}$ 和轨迹观测值 $\tau_i$,即 $o(p_{t_i}, z)$。因此 $\tau_{i+1}$ 可以用下面的公式生成:

$g_4(\cdot)$ 是用来把输出映射到网格数的函数。

给定学到的 $q_\gamma (r \mid T)$ 和 latent traffic pattern $z$,轨迹 $T$ 的实时异常分数 $s_a(\tau_{i:i})$ 可以计算为 1 - 生成轨迹观测值 $\tau_{i:i}$ 的似然,即 $\{ \tau_1 \rightarrow \tau_2 \rightarrow \dots \tau_i \}$:

在线上场景下,给定之前的轨迹观测值 $\tau_{i:i}$,下一个轨迹观测值的异常分数可以通过之前这个数来计算:

算法2是在线检测的过程。输入是轨迹 $T$,参数是从算法1学到的。对于新来的轨迹观测值 $\tau_{i+1}$,如果 latent traffic pattern $z$ 变了,那我们就更新 $z$。然后基于 $\tau_{1:i}$ 计算 $\tau_{1:i+1}$。最后返回异常分数。

4.2 Complexity Analysis

整个检测的复杂度是 $\mathcal{O}(d_{Z_1} d_{Z_2})$,$d_{Z_1}$ 和 $d_{Z_2}$ 是 $Z$ 的大小。

5 The DeepTEA-A Model: Approximate Online Detection

5.1 Approximation Algorithm

5.1.1 Challenge

基于 $\tau_{1:i}$ 的异常分数更新依赖 $t_{i+1}$ 的交通状态矩阵 $Z$,如果路网很大,这里耗时会长。

5.1.2 Design

受 GM-VSAE 的启发,本文提出了近似算法。使用 $\tau_1$ 的时段的交通状态矩阵 $Z$ 作为整个 trip 过程的交通状况的近似。这样,$Z$ 只要在第一个轨迹观测值 $\tau_1$ 的时候算一下就好了。online 更新的时候就不需要再算这个了。

给定一个起点 $S_T$ 和终点 $D_T$,从 $q(k \mid S_T, D_T, z_{S_T})$ 这里面取出最优的 latent route type $k$ 来近似最有 latent route pattern $u_k$,这需要从 $q_\gamma (r \mid T)$ 的 $k$ 个均值里面找,$Z_{S_T}$ 是 trip 开始时的交通状况。这样,最优的 latent route type $k$ 在 trip 一开始的时候就能拿到。从第二个轨迹观测值开始,这个 $k$ 就不需要再算了。

对于起点 $S_T$,交通状况 $Z_{S_T}$ 的隐藏状态可以通过下面公式计算:

然后 $z_{S_T}$ 可以从 $q_\phi (z_{S_T} \mid Z_{S_T})$ 里面采样得到:

然后,$\tau_{S_T}$ 可以通过 $f_2(\cdot)$ 得到:

同理,$\tau_{D_T}$ 按同样的方式计算。

然后 $q(k \mid S_T, D_T, z_{S_T})$ 通过 MLP 计算:

$f_5$ 就是 MLP。参数记为 $\delta = \{ f_5 (\cdot) \}$。

公式20里面,为了获得最优的 $k$,需要跑 $k$ 次。一个简单的方法是通过 $q_\gamma (k \mid T)$ 从轨迹 $T$ 里面找到最优的 $k$。因此 $q(k \mid S_T, D_T, z_{S_T})$ 和 $q_\gamma (k \mid T)$ 要尽可能的相近。我们用交叉熵最小化两个分布的差别:

这个交叉熵 $l_k$ 会和公式 16 的ELBO同时训练。然后在线检测阶段的时候,最优的 $k$ 是 $q(k \mid S_T, D_T, z_{S_T})$ 里面最高概率的那个。然后直接就能拿到最优 latent time-dependent route $u_k$。

需要注意的是,近似算法的训练过程和算法1不一样。首先,交通状况的使用不一样,近似算法只用了 $Z_{S_T}$。第二,公式26,是一个 co-training 过程,为了近似两个分布。训练后得到模型参数 $\phi, \gamma, \theta, \delta$。整个训练过程如算法3所示。先从 $Z_{S_T}$ 里面获得 $z_{S_T}$。然后获得最优的 latent time-dependent route $u_k$,这个数只要在轨迹开始的时候算一下就好了。然后基于 $p_\theta(\tau_{1:i} \mid u_k)$ 更新异常分数就好了。

5.2 Complexity Analysis

在线检测的复杂度 $\mathcal{O}(d_{h_t}(d_{h_t} + d_{\tau_i}))$。这项是新的轨迹观测值 $\tau_{i+1}$ 到来的时候 RNN 的变换过程的复杂度。因为 $d_{h_t}, d_{\tau_i}$ 是常数,所以近似算法的复杂度是 $\mathcal{O}(1)$