# Anomalous Trajectory Detection Using Masked Autoregressive Flow Considering Route Choice Probability

Authors: Pengqian Cao; Renxin Zhong; Wei Huang
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

Taxis play a critical role in public traffic systems, and they deliver myriad travelers with convenient service due to temporal-spatial availability. However, anomalous trajectories such as trip fraud often occur due to greedy drivers. In this study, we propose an anomalous trajectory detection method that incorporates Route Choice analysis into Masked Autoregressive Flow, named MAFRC-ATD. The MAFRC-ATD integrates data-driven and model-based methods. First, we divide the urban traffic network into small grids and represent subtrajectories with a sequence of grids. Second, based on the subtrajectories, we employ the MAFRC-ATD model to calculate the anomaly score of each trajectory. Third, according to the anomaly score, we can identify the anomalous trajectories and distinguish between intentionally and unintentionally anomalous. Finally, we evaluate our method with a real-world dataset in Porto, Portugal. The experiment demonstrates that the MAFRC-ATD can effectively discover anomalous trajectories and can identify the unintentional detours due to traffic congestion.


---

## Body

## 1. Introduction

Taxis provide convenient and available services for a multitude of urban passengers. However, passengers may be victims who are overcharged deliberately by greedy drivers. Two examples are as follows.Example 1.
Many people, mostly tourists, are victims of taxi-driving frauds committed by greedy taxi drivers who overcharge passengers by deliberately taking unnecessary detours [1]. In New York City, nearly 1.1 million dollars have been overcharged due to 21,819 taxicab drivers swindling money out of customers arbitrarily [2].Example 2.
Car hailing is a combination of the Internet and sharing economy, fundamentally changing the way people travel. However, car-hailing platforms lower employment requirements and increase effective supply, bringing safety and economic risks. The risk of overcharging, leaking personal information, or even crimes [3] could occur due to its strong characteristics of a “stranger economy.” Thus, to avoid potential crises, scouring the potential anomalous behaviors from historical record data of cabbies is prohibitively crucial.
To tackle this issue, collecting the GPS traces and discovering the anomalous trajectories from the sheer volume of data is an effective approach. The rapid advances in big data and machine learning grant us an unprecedented opportunity to detect anomalous trajectories via the trace data of moving objects.
Anomalous trajectory detection has attracted extensive research attention. Recently, with the proliferation of deep learning and deep generative models (DGMs), anomalous trajectory detection methods based on deep learning have made remarkable progress in recent years. However, the existing methods are usually faced with the following challenges:Spatiotemporal information for DGM: as a branch of deep learning, deep generative models are employed to identify anomalous trajectories by reconstruction error. However, most deep generative models [4–7] are difficult to directly capture sequential information of trajectory data.Unintentional anomalous trajectory: mostly, drivers may take unintentionally anomalous detours with their experience to avoid traffic congestion. The experience of drivers, particularly, is crucial for route recommendations when traffic congestion occurs. However, traditional anomalous trajectory detection methods seldom consider mining this unintentionally anomalous trajectory pattern.
We take an unintentional anomaly for instance. As shown in Figure1, there are two trajectories denoted as t1 and t2. Obviously, t1 is normal, whereas t2 seems to take a detour trace. However, the travel time of t1 is similar to the travel time of t2, suggesting that the driver of t2 may take a detour to reduce the travel time if traffic congestion or a traffic incident occurs. In real life, this unintentional anomaly is critical to route recommendations for traffic congestion.
To mitigate the above problems, this study proposes a framework that integrates the route choice model in the masked autoregressive flow (MAF), which is one framework of DGMs. Our key insight is that anomalous trajectory detection can be transformed into a distribution estimation task. MAF can fully capture the sequential information of trajectory data by leveraging the autoregressive mechanism and ought to assign the low probability density at the anomalous trajectory (i.e., the likelihood). On the contrary, to capture the actual route choice behavior, the route choice model is applied to distinguish unintentional anomalies due to traffic congestion or traffic incident. When traffic incident or traffic congestion occurs, people will normally take other routes which may be longer in distance, to avoid congestion or incident. Henceforth, the route choice model can successfully mine the patterns of unintentionally anomalous trajectories through the choice probability of corresponding routes.
In a nutshell, this study proposes an anomalous trajectory detection method based on masked autoregressive flow considering route choice analysis, named MAFRC-ATD. First, we extract valid trajectories from the historical dataset and split the traffic network into equal-sized grids; hence, subtrajectories can be represented with a sequence of grids. Second, we employ the MAFRC-ATD model to calculate the anomaly score of each trajectory through the likelihood of subtrajectories and the choice probability of the corresponding route. Finally, according to the anomaly score, each trajectory can be determined whether it is anomalous and, if anomalous, which type of anomalous trajectory it belongs to.Figure 1
An illustration of trips traversing from Porto cathedral to Clérigos church.


### 1.1. Contribution

Overall, the contributions of this study can be summarized as follows.We propose an unsupervised framework based on normalizing flow, which takes advantage of the spatiotemporal information and autoregressive characteristics of trajectories.To explore the unintentional anomalies, we incorporate the route choice model in the normalizing flow. As such, we develop a method MAFRC-ATD which integrates the data-driven and model-based method. In MAFRC-ATD, the route choice model is exploited to distinguish the unintentionally anomalous trajectories due to traffic congestion or traffic incident.We evaluate the proposed method in a real-life dataset in Porto, Portugal. The results show that the MAFRC-ATD model can effectively discover anomalous trajectories and successfully discover unintentional trajectories due to traffic congestion.


### 1.2. Organization

This study is organized as follows. Section2 briefly reviews the related work. Problem formulation and proposed methodology are introduced in Section 3. In Section 4, we evaluate our model with a real-life dataset and analyze the results. Section 5 concludes this study and outlines the future scope.


## 1.1. Contribution

Overall, the contributions of this study can be summarized as follows.We propose an unsupervised framework based on normalizing flow, which takes advantage of the spatiotemporal information and autoregressive characteristics of trajectories.To explore the unintentional anomalies, we incorporate the route choice model in the normalizing flow. As such, we develop a method MAFRC-ATD which integrates the data-driven and model-based method. In MAFRC-ATD, the route choice model is exploited to distinguish the unintentionally anomalous trajectories due to traffic congestion or traffic incident.We evaluate the proposed method in a real-life dataset in Porto, Portugal. The results show that the MAFRC-ATD model can effectively discover anomalous trajectories and successfully discover unintentional trajectories due to traffic congestion.


## 1.2. Organization

This study is organized as follows. Section2 briefly reviews the related work. Problem formulation and proposed methodology are introduced in Section 3. In Section 4, we evaluate our model with a real-life dataset and analyze the results. Section 5 concludes this study and outlines the future scope.


## 2. Related Work

In this section, we will give a brief literature review on anomalous trajectory detection, the probability density estimation with the flow-based model.


### 2.1. Anomalous Trajectory Detection

Trajectory anomaly detection methods can be divided into statistic-based, cluster-based, grid-based, classification-based, and deep learning methods.


#### 2.1.1. Statistic-Based Method

With the help of the popular routes, Zhu et al. [8] proposed time-dependent popular routes-based trajectory outlier detection (outlier is also referred to as anomaly detection in this study) method, considering both spatial and temporal anomalies simultaneously. Liu et al. [9] found that top drivers were better at finding the fastest route than ordinary drivers. However, these algorithms mainly focus on the geometric information of trajectories and neglect semantic information. Thus, Qin et al. [10] proposed the ProbDetect model, which transforms anomaly detection problems into a route choice problem considering semantic information such as trip time and fare, as well as traffic variability. In addition, Kong et al. [11] employed a statistical model to calculate the travel distribution of travel time, driving distance, and travel cost, making it possible to explore the reason for outlier trajectories.


#### 2.1.2. Cluster-Based Method

Knorr and Ng [12, 13] and Knorr et al. [14] applied the distance-based algorithm to detect trajectory anomalies in multidimensional multiscale space. However, “few” anomalies may be averaged over the whole trajectories’ dataset. Based on subtrajectories, Lee et al. [15, 16] proposed TRAOD, which includes two phases: partitioning a trajectory into a set of line segments and then detecting outlying line segments. In addition, Bu et al. [17] and Yu et al. [18] built local clusters and neighbor-based trajectory outliers, respectively, to discover the outlier of trajectory streams. In contrast to the above distance-based mechanism, Wang et al. [19] proposed an anomalous trajectory detection method based on edit distance and hierarchical clustering, which was employed to determine the number of clusters.


#### 2.1.3. Grid-Based Method

Ge et al. [20] proposed an algorithm Top-Eye, where the continuous data space was discretized into grids. Later, Ge et al. [21] applied travel route evidence and driving distance evidence to the trip fraud detection system, finding that the fraudulent drivers do earn more income than drivers without scams. Additionally, Kong et al. [22] proposed the LoTAD method to mine anomalous regions, where the center of each region and the region’s boundary were determined by the improved k-means method and the Voronoi graph while conforming to traffic conditions. Wang et al. [23] proposed a detection method based on the difference and intersection set (DIS) distance.Inspired by the isolation mechanism [24] that the anomalous trajectories are susceptible to being isolated, iBAT [25] was proposed to identify the anomalous trajectories. Based on iBAT, Chen et al. [26] and Sun et al. [27] proposed the online model iBOAT and application, respectively.


#### 2.1.4. Classification Method

Motion-alert algorithm [28, 29] leveraged the support vector machine (SVM) to learn the features of the extracted pattern motif, which are a sequence of motion features related to time and location. Similarly, Piciarelli and Foresti [30] employed a single-class SVM, and then, Piciarelli et al. [31] introduced the clustering method to improve the robustness.


#### 2.1.5. Deep Learning

With the development of the neural network, some researchers have employed deep learning methods, such as recurrent neural networks (RNN) [32, 33], to discover anomalies. Generative models were widely employed to discover anomalous trajectories. GM-VSAE method [34] and IGMM-GAN method [4], for instance, can be applied to uncover outliers in the latent space. In addition, Dias et al. [35] proposed a method using an NF scheme, effectively discovering anomalies in contrast to the GMM method. However, it might be unreasonable to directly flatten multidimensional trajectory data into one dimension and unpractical to evaluate the model in bus data since buses might take bypass routes as well.


### 2.2. Probability Density Estimation with the Flow-Based Model

Many tasks in machine learning, including anomalous trajectory detection, can be formulated as learning and manipulating density distribution. The problem of modeling a probability distribution from a set of given samples is a major goal of probabilistic unsupervised learning or generative modeling [36]. A generative model ought to assign low likelihoods to samples from different distributions, making it attractive to anomaly detection methods.Generative modeling has undergone tremendous advances in recent years, such as generative adversarial networks (GANs) [37] and variational auto-encoders (VAEs) [38]. Recently, NF methods have improved dramatically. Contrary to the GANs and VAEs, NF methods offer an exact density evaluation of probability density. NF was defined in Tabak and Vanden-Eijnden [39] and Tabak and Turner [40] and later popularized by Rezende and Mohamed [41] and by Dinh et al. [42]. NF methods can be divided into autoregressive flows, linear flows [43], residual flows [44–46], planar flow [41], Sylvester flow [47], and infinitesimal flows [48]. Among these flows, autoregressive flows remain the most popular.Regardless of its wide application nowadays, autoregressive architecture was even overlooked in previous work [49] due to the huge cost of high dimensionality. To alleviate this problem, several approaches have been proposed, including recurrent mechanism, masked mechanism, and coupling layer. Recurrent mechanism [50] shares parameters by jointly using an RNN. The main drawback of the RNN-based mechanism is that the internal state of RNN is calculated sequentially, with higher computational complexity than the other two mechanisms. The masked mechanism [51] uses a feedforward neural network and removes appropriate connections by multiplying a binary matrix. However, masked mechanism MAF is efficient to evaluate, but slower to invert, indicating that MAF is appropriate to estimate density probability. Coupling layers [42], which splits the input into two disjoint partitions that the first part stays the same as the input and the second part undergoes an affine transformation, which are equally fast to evaluate the probability density and invert for sampling (sampling from the model and evaluating the model’s density are two invertible operations for normalizing the flow model).


### 2.3. Route Choice Model

Route choice modeling is essential to evaluate travelers’ choice perception within a set of alternative routes, helping analyze and understand travelers’ behavior [52]. Generally, a route choice model has two stages [53]: first is the choice set of possible alternative routes and second is the choice probability of a path, given the route choice set [54, 55]. Route choice models mainly include logit structures [56], GEV structures [57], and non-GEV structures [58].


## 2.1. Anomalous Trajectory Detection

Trajectory anomaly detection methods can be divided into statistic-based, cluster-based, grid-based, classification-based, and deep learning methods.


### 2.1.1. Statistic-Based Method

With the help of the popular routes, Zhu et al. [8] proposed time-dependent popular routes-based trajectory outlier detection (outlier is also referred to as anomaly detection in this study) method, considering both spatial and temporal anomalies simultaneously. Liu et al. [9] found that top drivers were better at finding the fastest route than ordinary drivers. However, these algorithms mainly focus on the geometric information of trajectories and neglect semantic information. Thus, Qin et al. [10] proposed the ProbDetect model, which transforms anomaly detection problems into a route choice problem considering semantic information such as trip time and fare, as well as traffic variability. In addition, Kong et al. [11] employed a statistical model to calculate the travel distribution of travel time, driving distance, and travel cost, making it possible to explore the reason for outlier trajectories.


### 2.1.2. Cluster-Based Method

Knorr and Ng [12, 13] and Knorr et al. [14] applied the distance-based algorithm to detect trajectory anomalies in multidimensional multiscale space. However, “few” anomalies may be averaged over the whole trajectories’ dataset. Based on subtrajectories, Lee et al. [15, 16] proposed TRAOD, which includes two phases: partitioning a trajectory into a set of line segments and then detecting outlying line segments. In addition, Bu et al. [17] and Yu et al. [18] built local clusters and neighbor-based trajectory outliers, respectively, to discover the outlier of trajectory streams. In contrast to the above distance-based mechanism, Wang et al. [19] proposed an anomalous trajectory detection method based on edit distance and hierarchical clustering, which was employed to determine the number of clusters.


### 2.1.3. Grid-Based Method

Ge et al. [20] proposed an algorithm Top-Eye, where the continuous data space was discretized into grids. Later, Ge et al. [21] applied travel route evidence and driving distance evidence to the trip fraud detection system, finding that the fraudulent drivers do earn more income than drivers without scams. Additionally, Kong et al. [22] proposed the LoTAD method to mine anomalous regions, where the center of each region and the region’s boundary were determined by the improved k-means method and the Voronoi graph while conforming to traffic conditions. Wang et al. [23] proposed a detection method based on the difference and intersection set (DIS) distance.Inspired by the isolation mechanism [24] that the anomalous trajectories are susceptible to being isolated, iBAT [25] was proposed to identify the anomalous trajectories. Based on iBAT, Chen et al. [26] and Sun et al. [27] proposed the online model iBOAT and application, respectively.


### 2.1.4. Classification Method

Motion-alert algorithm [28, 29] leveraged the support vector machine (SVM) to learn the features of the extracted pattern motif, which are a sequence of motion features related to time and location. Similarly, Piciarelli and Foresti [30] employed a single-class SVM, and then, Piciarelli et al. [31] introduced the clustering method to improve the robustness.


### 2.1.5. Deep Learning

With the development of the neural network, some researchers have employed deep learning methods, such as recurrent neural networks (RNN) [32, 33], to discover anomalies. Generative models were widely employed to discover anomalous trajectories. GM-VSAE method [34] and IGMM-GAN method [4], for instance, can be applied to uncover outliers in the latent space. In addition, Dias et al. [35] proposed a method using an NF scheme, effectively discovering anomalies in contrast to the GMM method. However, it might be unreasonable to directly flatten multidimensional trajectory data into one dimension and unpractical to evaluate the model in bus data since buses might take bypass routes as well.


## 2.1.1. Statistic-Based Method

With the help of the popular routes, Zhu et al. [8] proposed time-dependent popular routes-based trajectory outlier detection (outlier is also referred to as anomaly detection in this study) method, considering both spatial and temporal anomalies simultaneously. Liu et al. [9] found that top drivers were better at finding the fastest route than ordinary drivers. However, these algorithms mainly focus on the geometric information of trajectories and neglect semantic information. Thus, Qin et al. [10] proposed the ProbDetect model, which transforms anomaly detection problems into a route choice problem considering semantic information such as trip time and fare, as well as traffic variability. In addition, Kong et al. [11] employed a statistical model to calculate the travel distribution of travel time, driving distance, and travel cost, making it possible to explore the reason for outlier trajectories.


## 2.1.2. Cluster-Based Method

Knorr and Ng [12, 13] and Knorr et al. [14] applied the distance-based algorithm to detect trajectory anomalies in multidimensional multiscale space. However, “few” anomalies may be averaged over the whole trajectories’ dataset. Based on subtrajectories, Lee et al. [15, 16] proposed TRAOD, which includes two phases: partitioning a trajectory into a set of line segments and then detecting outlying line segments. In addition, Bu et al. [17] and Yu et al. [18] built local clusters and neighbor-based trajectory outliers, respectively, to discover the outlier of trajectory streams. In contrast to the above distance-based mechanism, Wang et al. [19] proposed an anomalous trajectory detection method based on edit distance and hierarchical clustering, which was employed to determine the number of clusters.


## 2.1.3. Grid-Based Method

Ge et al. [20] proposed an algorithm Top-Eye, where the continuous data space was discretized into grids. Later, Ge et al. [21] applied travel route evidence and driving distance evidence to the trip fraud detection system, finding that the fraudulent drivers do earn more income than drivers without scams. Additionally, Kong et al. [22] proposed the LoTAD method to mine anomalous regions, where the center of each region and the region’s boundary were determined by the improved k-means method and the Voronoi graph while conforming to traffic conditions. Wang et al. [23] proposed a detection method based on the difference and intersection set (DIS) distance.Inspired by the isolation mechanism [24] that the anomalous trajectories are susceptible to being isolated, iBAT [25] was proposed to identify the anomalous trajectories. Based on iBAT, Chen et al. [26] and Sun et al. [27] proposed the online model iBOAT and application, respectively.


## 2.1.4. Classification Method

Motion-alert algorithm [28, 29] leveraged the support vector machine (SVM) to learn the features of the extracted pattern motif, which are a sequence of motion features related to time and location. Similarly, Piciarelli and Foresti [30] employed a single-class SVM, and then, Piciarelli et al. [31] introduced the clustering method to improve the robustness.


## 2.1.5. Deep Learning

With the development of the neural network, some researchers have employed deep learning methods, such as recurrent neural networks (RNN) [32, 33], to discover anomalies. Generative models were widely employed to discover anomalous trajectories. GM-VSAE method [34] and IGMM-GAN method [4], for instance, can be applied to uncover outliers in the latent space. In addition, Dias et al. [35] proposed a method using an NF scheme, effectively discovering anomalies in contrast to the GMM method. However, it might be unreasonable to directly flatten multidimensional trajectory data into one dimension and unpractical to evaluate the model in bus data since buses might take bypass routes as well.


## 2.2. Probability Density Estimation with the Flow-Based Model

Many tasks in machine learning, including anomalous trajectory detection, can be formulated as learning and manipulating density distribution. The problem of modeling a probability distribution from a set of given samples is a major goal of probabilistic unsupervised learning or generative modeling [36]. A generative model ought to assign low likelihoods to samples from different distributions, making it attractive to anomaly detection methods.Generative modeling has undergone tremendous advances in recent years, such as generative adversarial networks (GANs) [37] and variational auto-encoders (VAEs) [38]. Recently, NF methods have improved dramatically. Contrary to the GANs and VAEs, NF methods offer an exact density evaluation of probability density. NF was defined in Tabak and Vanden-Eijnden [39] and Tabak and Turner [40] and later popularized by Rezende and Mohamed [41] and by Dinh et al. [42]. NF methods can be divided into autoregressive flows, linear flows [43], residual flows [44–46], planar flow [41], Sylvester flow [47], and infinitesimal flows [48]. Among these flows, autoregressive flows remain the most popular.Regardless of its wide application nowadays, autoregressive architecture was even overlooked in previous work [49] due to the huge cost of high dimensionality. To alleviate this problem, several approaches have been proposed, including recurrent mechanism, masked mechanism, and coupling layer. Recurrent mechanism [50] shares parameters by jointly using an RNN. The main drawback of the RNN-based mechanism is that the internal state of RNN is calculated sequentially, with higher computational complexity than the other two mechanisms. The masked mechanism [51] uses a feedforward neural network and removes appropriate connections by multiplying a binary matrix. However, masked mechanism MAF is efficient to evaluate, but slower to invert, indicating that MAF is appropriate to estimate density probability. Coupling layers [42], which splits the input into two disjoint partitions that the first part stays the same as the input and the second part undergoes an affine transformation, which are equally fast to evaluate the probability density and invert for sampling (sampling from the model and evaluating the model’s density are two invertible operations for normalizing the flow model).


## 2.3. Route Choice Model

Route choice modeling is essential to evaluate travelers’ choice perception within a set of alternative routes, helping analyze and understand travelers’ behavior [52]. Generally, a route choice model has two stages [53]: first is the choice set of possible alternative routes and second is the choice probability of a path, given the route choice set [54, 55]. Route choice models mainly include logit structures [56], GEV structures [57], and non-GEV structures [58].


## 3. Problem Formulation

Problem formulation is as follows.


### 3.1. Problem Definition and Framework

Problem definition and framework is described in the following secions.


#### 3.1.1. Problem Definition

As stated by Agrawal and Agrawal [59], the goal of anomaly detection is to find data patterns that differ from what is expected. In our work, such unexpected patterns are related to trajectories sufficiently different from the majority which is considered to be normal, such as detour traces. The definitions of this anomalous trajectory detection problem are as follows.Definition 1.
(trajectory). A raw trajectoryT=q1,q2,…,qn is a sequence of records, and each recorded qi is represented by loni,lati, where loni,lati is a pair of latitude and longitude coordinates. q1 and qn are the origin and destination of the trajectory T, respectively.Definition 2.
(anomaly). Anomaly is data that are different from others in the dataset, making people assume that the outlier of these data is not caused by random factors, but by a completely different mechanism [60].Definition 3.
(anomalous trajectory). Given an OD pair, we assumed that there are a set of trajectories whose pick-up locations and drop-off locations are the origin and destination respectively. LetD=T1,T2,…,TM denote this set of trajectories, where the anomalous trajectory is significantly different from the majority in this OD pair.Definition 4.
(unintentionally anomalous trajectory). The unintentionally anomalous trajectory is an anomalous trajectory in a spatiotemporal pattern, which is caused by travelers’ unintentional detours to avoid traffic congestion.


#### 3.1.2. Overview of the Methodology

To achieve the goal of anomalous trajectory detection, we propose the MAFRC-ATD model, and the methodology is shown in Figure2.Figure 2
The overall architecture of MAFRC-ATD.In detail, we first deal with treating the raw trajectories in the following procedures: (1) removing the invalid trajectories, (2) discretizing the traffic network into equal-sized grids (that is grid mapping), (3) extracting all traces crossing the same OD cell pairs, and (4) partitioning trajectories into subtrajectories.Based on the subtrajectories, we employ the MAFRC-ATD to discover anomalies. The anomaly score of each trajectory can be computed through the likelihood of subtrajectories and the choice probability of the corresponding route.Finally, according to the anomaly score, each trajectory can be determined whether it is anomalous and, if anomalous, which type of anomalous trajectory it belongs to.


### 3.2. Data Preprocessing

As stated in Section1, data preprocessing mainly includes two phases: grid mapping and partitioning trajectories into subtrajectories.


#### 3.2.1. Grid Mapping

As shown in Figures3(a) and 3(b), grid mapping is to split the city traffic network into small grids. In detail, for given Nlon and Nlat, the urban traffic network can be split into Nlon×Nlat equal-sized grids. Consequently, each taxi trajectory Tk=qk,1,qk,2,…,qk,i,…,qk,n can be represented with a sequence of traversed grids Tk=t1,t2,…,ti,…,tn, where ti=gqk,i,Nlon,Nlat and g is a grid mapping function.Figure 3
An illustration of grid mapping.t1 to t3 are shown in Figure 2 (a) An illustration of t1 to t3. (b) Grid mapping.
(a)(b)


#### 3.2.2. Partitioning Trajectories

As discussed by Lee et al. [15], the difference between anomalies and normal trajectories might be averaged out over the whole trajectory. To alleviate this problem, trajectories are segmented with subtrajectories. A trajectory Tk=t1,t2,…,ti,…,tn can be partitioned with equal d-length sized subtrajectories as follows:(1)ΩTk:s1,s2,…,st,…,sl,where ΩTk is a set of continuous subtrajectories and sl can be completed as last d-length GPS points. Thus, we can obtain the set of subtrajectories ΩT regarding this OD.


### 3.3. Masked Autoregressive Flow

As stated in Section1, the anomalous trajectory detection problem can be formulated as the probability density estimation problem. NF ought to assign low likelihoods to data from different distributions, making it possible to discover anomalies with low-likelihood predictions. MAF is applied to detect anomalous trajectories as follows.NF pushes an initial density (such as normal distribution) through a series of transformations to produce a richer distribution with more expressive power than the constituent components of these transformations [51]. Assuming that s is a d-length subtrajectory and u is the d-dimensional random variable of the base distribution puu, then s can be represented through the transformation F:(2)s=Fu,where u∼puu, and the transformation F must be differentiable and invertible. Then, the density of s, i.e., ps, can be calculated as follows:(3)ps=puF−1sdetJF−1s,where the inverse of differentiable transformation F−1 and Jacobian determinant detJF−1s can be implemented by MAF.Since the spatiotemporal autoregressive character ofs, ps can be decomposed into a product of conditional densities using the chain rule of probability:(4)ps=∏h=1dpsh∣s1,s2,…,sh−1=∏h=1dpsh∣s1:h−1.Assume that conditional distributionspsh∣s1:h−1 are parameterized as single Gaussian:(5)psh∣s1:h−1=Nsh∣μh,expαh2,where μh=fμhs1:h−1 and αh=fαhs1:h−1, for h=1,2,…,d. Specifically, fμh and fαh are unconstrained scalar functions that compute the mean and log standard deviation given all previous variables, and both two scalar functions are estimated by Germain et al. [61]. The hth dimension of subtrajectory, i.e., sh, can be sampled from the base distribution:(6)sh=uhexpαh+μh,where uh∼N0,1. Thus, the invertible transformation F is easy to access as follows:(7)uh=sh−μhexp−αh,where the absolute determinant of the Jacobian matrix is(8)detJF−1s=det∂F−1∂s=exp−∑hαh.Therefore,ps can be successfully evaluated through (3), where the inverse transformation and its Jacobian determinant can be calculated by (6) and (8)After calculating the likelihood of subtrajectories, the likelihood of the whole trajectory can be calculated as follows. For any trajectoryTk, the likelihood of the corresponding subtrajectory pst can be obtained via the aforementioned process, and the likelihood of trajectory Tk can be defined as the mean value of the pst, i.e.,(9)pTk=1l∑t=1lpst,where t=1,2,…,l.


### 3.4. Route Choice Analysis

As mentioned above, we have detected anomalous trajectory with the MAF method, mostly using geometrical information and sequential information. However, in the real world, anomalous trajectories may occur due to lots of factors, such as travel time and traffic conditions. As described in Section1, detours can be unintentionally generated by drivers whose intentions are to avoid traffic congestion to reduce trip time during peak hours. Apparently, it is extremely crucial to explore this route choice motivation behind anomalous behaviors. However, modeling the motivation behind the choice behavior could be problematic due to the complicated traffic conditions of the road network. The impact of traffic control regulation at an intersection on the Network Macroscopic Fundamental Diagram (NMFD) [62, 63], for example, could also influence the aggregate traffic conditions of the road network. In this study, following Qin et al. [10], we adopt a random utility model based on a multivariate Gaussian model to explore the motivation behind the random choice behaviors.Assumed there are a set of trajectoriesD=T1,T2,…,TM for each pair of OD, ℂ=C1,C2,…,Cm is a set of choice routes that all distinct trajectories pass through in this OD. For any route Cj in the route choice set ℂ, LCj and TCj are its travel length and trip time, and the generalized cost is(10)GCj=LCj+cTCj,where c is the velocity equivalent coefficient, which can be interpreted as the trip length value for a unit of the trip time. The choice probability of the route Cj can be defined as a vectorized form:(11)pCj=PZ≤0,where Z is the difference of generalized cost, i.e., Z=Gcj−Gc1,…,Gcj−GcmT, and Z and 0 are both Rm−1×1 vectors. Thus, pCj can be calculated by the integral of the probability density function for Z:(12)pCj=∫−∞0…∫−∞0exp−1/2Z−μZ⊤Σ−1Z−μZ2πm−1ΣZdZ,where μZ and ΣZ are the mean vector and covariance matrix of Z. To calculate μZ and ΣZ, Z are further decomposed into as follows:(13)Z=AU⊤,where A=−1⋯1⋯00⋯1⋯0⋮⋱⋮⋱⋮0⋯1⋯−1m−1×m and U=GC1,GC2,…,GCm. Thus,(14)μZ=AμU,ΣZ=AΣUAT,where μZ and ΣZ can be derived by μU and ΣU. Obviously,(15)μU=μGC1,μGC2,…,μGCm,and ΣU is(16)ΣU=covGC1,GC1covGC1,GC2⋯covGC1,GCmcovGC2,GC1covGC2,GC2⋯covGC2,GCm⋮⋮⋱⋮covGCm,GC1covGCm,GC2⋯covGCm,GCm.Furthermore,ΣU is given by(17)ΣU=σC12σC1∩22⋯σC1∩m2σC2∩12σC22⋯σC2∩m2⋮⋮⋱⋮σCm∩12σCm∩22⋯σCm2,where σCi∩j2 is the variance of Ci∩j which reflects the overlapped portion of two routes Ci and Cj, and Ci and Cj are arbitrary routes in route set ℂ, for i,j=1,2,…,m.In this way, the choice probability of the routeCj can be obtained by equation (12) by substituting equations (15) and (17) into equation (14).


### 3.5. Anomaly Score

As described in Section1 and Section 3.1, the MAFRC-ATD model integrates the data-driven learning and route choice model. Thereby, the anomaly score is designed to combine the two aspects as follows.The likelihood of a given trajectory and the route choice probability of the given trajectory can be calculated in Sections3.3 and 3.4. For a given OD pair, we assumed that Cj is the corresponding route of trajectory Tk, pTk and pCj are the likelihood of Tk and choice probability of route Cj respectively, and an anomaly score ETk is defined as(18)ETk=−pCj−1mξ⋅sigmoidlogpTk+1,where m is the number of all routes for this OD pair and ξ is the coefficient of unintentionally anomalous. In (18), sigmoid ⋅ is a sigmoid function, i.e., sigmoidx=1/1+e−x, and is monotonically increasing with outputs in the range 0 to 1. Obviously, pCj and pTk of normal trajectories are higher than anomalous trajectories.Assuming that thresholdδ is applied to decide whether the trajectory is anomalous, there are three cases.WhenETk≥1, i.e., pCj−1/mξ≤0, Tk is likely to be an intentionally anomalous trajectoryWhenETk <1 and ETk≥δ, Tk can be categorized as unintentionally anomalous trajectoryWhenETk >0 and ETk<δ, Tk can be regarded as a normal trajectory


## 3.1. Problem Definition and Framework

Problem definition and framework is described in the following secions.


### 3.1.1. Problem Definition

As stated by Agrawal and Agrawal [59], the goal of anomaly detection is to find data patterns that differ from what is expected. In our work, such unexpected patterns are related to trajectories sufficiently different from the majority which is considered to be normal, such as detour traces. The definitions of this anomalous trajectory detection problem are as follows.Definition 1.
(trajectory). A raw trajectoryT=q1,q2,…,qn is a sequence of records, and each recorded qi is represented by loni,lati, where loni,lati is a pair of latitude and longitude coordinates. q1 and qn are the origin and destination of the trajectory T, respectively.Definition 2.
(anomaly). Anomaly is data that are different from others in the dataset, making people assume that the outlier of these data is not caused by random factors, but by a completely different mechanism [60].Definition 3.
(anomalous trajectory). Given an OD pair, we assumed that there are a set of trajectories whose pick-up locations and drop-off locations are the origin and destination respectively. LetD=T1,T2,…,TM denote this set of trajectories, where the anomalous trajectory is significantly different from the majority in this OD pair.Definition 4.
(unintentionally anomalous trajectory). The unintentionally anomalous trajectory is an anomalous trajectory in a spatiotemporal pattern, which is caused by travelers’ unintentional detours to avoid traffic congestion.


### 3.1.2. Overview of the Methodology

To achieve the goal of anomalous trajectory detection, we propose the MAFRC-ATD model, and the methodology is shown in Figure2.Figure 2
The overall architecture of MAFRC-ATD.In detail, we first deal with treating the raw trajectories in the following procedures: (1) removing the invalid trajectories, (2) discretizing the traffic network into equal-sized grids (that is grid mapping), (3) extracting all traces crossing the same OD cell pairs, and (4) partitioning trajectories into subtrajectories.Based on the subtrajectories, we employ the MAFRC-ATD to discover anomalies. The anomaly score of each trajectory can be computed through the likelihood of subtrajectories and the choice probability of the corresponding route.Finally, according to the anomaly score, each trajectory can be determined whether it is anomalous and, if anomalous, which type of anomalous trajectory it belongs to.


## 3.1.1. Problem Definition

As stated by Agrawal and Agrawal [59], the goal of anomaly detection is to find data patterns that differ from what is expected. In our work, such unexpected patterns are related to trajectories sufficiently different from the majority which is considered to be normal, such as detour traces. The definitions of this anomalous trajectory detection problem are as follows.Definition 1.
(trajectory). A raw trajectoryT=q1,q2,…,qn is a sequence of records, and each recorded qi is represented by loni,lati, where loni,lati is a pair of latitude and longitude coordinates. q1 and qn are the origin and destination of the trajectory T, respectively.Definition 2.
(anomaly). Anomaly is data that are different from others in the dataset, making people assume that the outlier of these data is not caused by random factors, but by a completely different mechanism [60].Definition 3.
(anomalous trajectory). Given an OD pair, we assumed that there are a set of trajectories whose pick-up locations and drop-off locations are the origin and destination respectively. LetD=T1,T2,…,TM denote this set of trajectories, where the anomalous trajectory is significantly different from the majority in this OD pair.Definition 4.
(unintentionally anomalous trajectory). The unintentionally anomalous trajectory is an anomalous trajectory in a spatiotemporal pattern, which is caused by travelers’ unintentional detours to avoid traffic congestion.


## 3.1.2. Overview of the Methodology

To achieve the goal of anomalous trajectory detection, we propose the MAFRC-ATD model, and the methodology is shown in Figure2.Figure 2
The overall architecture of MAFRC-ATD.In detail, we first deal with treating the raw trajectories in the following procedures: (1) removing the invalid trajectories, (2) discretizing the traffic network into equal-sized grids (that is grid mapping), (3) extracting all traces crossing the same OD cell pairs, and (4) partitioning trajectories into subtrajectories.Based on the subtrajectories, we employ the MAFRC-ATD to discover anomalies. The anomaly score of each trajectory can be computed through the likelihood of subtrajectories and the choice probability of the corresponding route.Finally, according to the anomaly score, each trajectory can be determined whether it is anomalous and, if anomalous, which type of anomalous trajectory it belongs to.


## 3.2. Data Preprocessing

As stated in Section1, data preprocessing mainly includes two phases: grid mapping and partitioning trajectories into subtrajectories.


### 3.2.1. Grid Mapping

As shown in Figures3(a) and 3(b), grid mapping is to split the city traffic network into small grids. In detail, for given Nlon and Nlat, the urban traffic network can be split into Nlon×Nlat equal-sized grids. Consequently, each taxi trajectory Tk=qk,1,qk,2,…,qk,i,…,qk,n can be represented with a sequence of traversed grids Tk=t1,t2,…,ti,…,tn, where ti=gqk,i,Nlon,Nlat and g is a grid mapping function.Figure 3
An illustration of grid mapping.t1 to t3 are shown in Figure 2 (a) An illustration of t1 to t3. (b) Grid mapping.
(a)(b)


### 3.2.2. Partitioning Trajectories

As discussed by Lee et al. [15], the difference between anomalies and normal trajectories might be averaged out over the whole trajectory. To alleviate this problem, trajectories are segmented with subtrajectories. A trajectory Tk=t1,t2,…,ti,…,tn can be partitioned with equal d-length sized subtrajectories as follows:(1)ΩTk:s1,s2,…,st,…,sl,where ΩTk is a set of continuous subtrajectories and sl can be completed as last d-length GPS points. Thus, we can obtain the set of subtrajectories ΩT regarding this OD.


## 3.2.1. Grid Mapping

As shown in Figures3(a) and 3(b), grid mapping is to split the city traffic network into small grids. In detail, for given Nlon and Nlat, the urban traffic network can be split into Nlon×Nlat equal-sized grids. Consequently, each taxi trajectory Tk=qk,1,qk,2,…,qk,i,…,qk,n can be represented with a sequence of traversed grids Tk=t1,t2,…,ti,…,tn, where ti=gqk,i,Nlon,Nlat and g is a grid mapping function.Figure 3
An illustration of grid mapping.t1 to t3 are shown in Figure 2 (a) An illustration of t1 to t3. (b) Grid mapping.
(a)(b)


## 3.2.2. Partitioning Trajectories

As discussed by Lee et al. [15], the difference between anomalies and normal trajectories might be averaged out over the whole trajectory. To alleviate this problem, trajectories are segmented with subtrajectories. A trajectory Tk=t1,t2,…,ti,…,tn can be partitioned with equal d-length sized subtrajectories as follows:(1)ΩTk:s1,s2,…,st,…,sl,where ΩTk is a set of continuous subtrajectories and sl can be completed as last d-length GPS points. Thus, we can obtain the set of subtrajectories ΩT regarding this OD.


## 3.3. Masked Autoregressive Flow

As stated in Section1, the anomalous trajectory detection problem can be formulated as the probability density estimation problem. NF ought to assign low likelihoods to data from different distributions, making it possible to discover anomalies with low-likelihood predictions. MAF is applied to detect anomalous trajectories as follows.NF pushes an initial density (such as normal distribution) through a series of transformations to produce a richer distribution with more expressive power than the constituent components of these transformations [51]. Assuming that s is a d-length subtrajectory and u is the d-dimensional random variable of the base distribution puu, then s can be represented through the transformation F:(2)s=Fu,where u∼puu, and the transformation F must be differentiable and invertible. Then, the density of s, i.e., ps, can be calculated as follows:(3)ps=puF−1sdetJF−1s,where the inverse of differentiable transformation F−1 and Jacobian determinant detJF−1s can be implemented by MAF.Since the spatiotemporal autoregressive character ofs, ps can be decomposed into a product of conditional densities using the chain rule of probability:(4)ps=∏h=1dpsh∣s1,s2,…,sh−1=∏h=1dpsh∣s1:h−1.Assume that conditional distributionspsh∣s1:h−1 are parameterized as single Gaussian:(5)psh∣s1:h−1=Nsh∣μh,expαh2,where μh=fμhs1:h−1 and αh=fαhs1:h−1, for h=1,2,…,d. Specifically, fμh and fαh are unconstrained scalar functions that compute the mean and log standard deviation given all previous variables, and both two scalar functions are estimated by Germain et al. [61]. The hth dimension of subtrajectory, i.e., sh, can be sampled from the base distribution:(6)sh=uhexpαh+μh,where uh∼N0,1. Thus, the invertible transformation F is easy to access as follows:(7)uh=sh−μhexp−αh,where the absolute determinant of the Jacobian matrix is(8)detJF−1s=det∂F−1∂s=exp−∑hαh.Therefore,ps can be successfully evaluated through (3), where the inverse transformation and its Jacobian determinant can be calculated by (6) and (8)After calculating the likelihood of subtrajectories, the likelihood of the whole trajectory can be calculated as follows. For any trajectoryTk, the likelihood of the corresponding subtrajectory pst can be obtained via the aforementioned process, and the likelihood of trajectory Tk can be defined as the mean value of the pst, i.e.,(9)pTk=1l∑t=1lpst,where t=1,2,…,l.


## 3.4. Route Choice Analysis

As mentioned above, we have detected anomalous trajectory with the MAF method, mostly using geometrical information and sequential information. However, in the real world, anomalous trajectories may occur due to lots of factors, such as travel time and traffic conditions. As described in Section1, detours can be unintentionally generated by drivers whose intentions are to avoid traffic congestion to reduce trip time during peak hours. Apparently, it is extremely crucial to explore this route choice motivation behind anomalous behaviors. However, modeling the motivation behind the choice behavior could be problematic due to the complicated traffic conditions of the road network. The impact of traffic control regulation at an intersection on the Network Macroscopic Fundamental Diagram (NMFD) [62, 63], for example, could also influence the aggregate traffic conditions of the road network. In this study, following Qin et al. [10], we adopt a random utility model based on a multivariate Gaussian model to explore the motivation behind the random choice behaviors.Assumed there are a set of trajectoriesD=T1,T2,…,TM for each pair of OD, ℂ=C1,C2,…,Cm is a set of choice routes that all distinct trajectories pass through in this OD. For any route Cj in the route choice set ℂ, LCj and TCj are its travel length and trip time, and the generalized cost is(10)GCj=LCj+cTCj,where c is the velocity equivalent coefficient, which can be interpreted as the trip length value for a unit of the trip time. The choice probability of the route Cj can be defined as a vectorized form:(11)pCj=PZ≤0,where Z is the difference of generalized cost, i.e., Z=Gcj−Gc1,…,Gcj−GcmT, and Z and 0 are both Rm−1×1 vectors. Thus, pCj can be calculated by the integral of the probability density function for Z:(12)pCj=∫−∞0…∫−∞0exp−1/2Z−μZ⊤Σ−1Z−μZ2πm−1ΣZdZ,where μZ and ΣZ are the mean vector and covariance matrix of Z. To calculate μZ and ΣZ, Z are further decomposed into as follows:(13)Z=AU⊤,where A=−1⋯1⋯00⋯1⋯0⋮⋱⋮⋱⋮0⋯1⋯−1m−1×m and U=GC1,GC2,…,GCm. Thus,(14)μZ=AμU,ΣZ=AΣUAT,where μZ and ΣZ can be derived by μU and ΣU. Obviously,(15)μU=μGC1,μGC2,…,μGCm,and ΣU is(16)ΣU=covGC1,GC1covGC1,GC2⋯covGC1,GCmcovGC2,GC1covGC2,GC2⋯covGC2,GCm⋮⋮⋱⋮covGCm,GC1covGCm,GC2⋯covGCm,GCm.Furthermore,ΣU is given by(17)ΣU=σC12σC1∩22⋯σC1∩m2σC2∩12σC22⋯σC2∩m2⋮⋮⋱⋮σCm∩12σCm∩22⋯σCm2,where σCi∩j2 is the variance of Ci∩j which reflects the overlapped portion of two routes Ci and Cj, and Ci and Cj are arbitrary routes in route set ℂ, for i,j=1,2,…,m.In this way, the choice probability of the routeCj can be obtained by equation (12) by substituting equations (15) and (17) into equation (14).


## 3.5. Anomaly Score

As described in Section1 and Section 3.1, the MAFRC-ATD model integrates the data-driven learning and route choice model. Thereby, the anomaly score is designed to combine the two aspects as follows.The likelihood of a given trajectory and the route choice probability of the given trajectory can be calculated in Sections3.3 and 3.4. For a given OD pair, we assumed that Cj is the corresponding route of trajectory Tk, pTk and pCj are the likelihood of Tk and choice probability of route Cj respectively, and an anomaly score ETk is defined as(18)ETk=−pCj−1mξ⋅sigmoidlogpTk+1,where m is the number of all routes for this OD pair and ξ is the coefficient of unintentionally anomalous. In (18), sigmoid ⋅ is a sigmoid function, i.e., sigmoidx=1/1+e−x, and is monotonically increasing with outputs in the range 0 to 1. Obviously, pCj and pTk of normal trajectories are higher than anomalous trajectories.Assuming that thresholdδ is applied to decide whether the trajectory is anomalous, there are three cases.WhenETk≥1, i.e., pCj−1/mξ≤0, Tk is likely to be an intentionally anomalous trajectoryWhenETk <1 and ETk≥δ, Tk can be categorized as unintentionally anomalous trajectoryWhenETk >0 and ETk<δ, Tk can be regarded as a normal trajectory


## 4. Case Study

In this section, we will evaluate our MAFRC-ATD model using the real-world dataset and present the results as well as discussions of experiments.


### 4.1. Experimental Setup

#### 4.1.1. Dataset Preprocessing

Our experiments are conducted on the real-world taxi trajectory dataset provided by Kaggle ECML-PKDD 2015 competition (https://www.kaggle.com/c/pkdd-15-predict-taxi-service-trajectory-i/data). In detail, the dataset is generated from 442 taxis running in the city of Porto from 01/07/2013 to 30/06/2014. There are 1710670 raw trajectories in total and each taxi reports its location every 15 seconds.Out of approximately 1.7 million trajectories from the original dataset, we remove the trajectories with less than 20 GPS. After filtering, we split the city traffic network space into100m×100m grids, i.e., gl=gw=100m. Consequently, GPS points can be represented with grids and each trajectory can be denoted by a sequence of grids. Subsequently, we extract 4 OD pairs, denoted as OD1 to OD4, respectively. In this study, we segment a trajectory into subtrajectories with 20 GPS points, that is, d=20. Given the fact that there is no labeled dataset available, we choose to manually label anomalies in this paper.Additionally, inspired by Liu et al. [34], to alleviate the problem of unbalanced learning in anomaly detection, we select several detour paths from which anomalous trajectories are generated. The detour paths, called generated routes, traverse the real-world links and are implemented in ArcGIS and Google maps. Among the generated routes, generated anomalous trajectories can be generated through sampling from the GPS points of generated routes. The generated anomalous trajectories are injected into the original dataset for “data argument.”As stated above, the related information of those OD pairs is shown in Table1, where O and D are represented with (longitude and latitude), and each OD pair can be shown in Figure 4. Out of all testing trajectories, the coral color lines represent the original historical dataset in the testing dataset, whereas other colors represent the generated routes from which the generated anomalous trajectories are sampled.Table 1
The information on OD pairs.
OD1OD2OD3OD4O(−8.6399, 41.1598)(−8.6109, 41.1457)(−8.6141, 41.1412)(−8.5856, 41.1485)D(−8.6542, 41.1806)(−8.6098, 41.1605)(−8.6497, 41.1544)(−8.6068, 41.1457)Historical trajectories996946687559Training dataset897852619504Testing datasetHistorical testing dataset99946855Generated trajectories12969Anomalous trajectories15101010Anomaly ratio (%)13.519.7113.5115.63Figure 4
The testing dataset of each OD pair, where the lawn green color upper triangle represents the pick-up location and the cyan color lower triangle represents the drop-off location. (a) OD1, (b) OD2, (c) OD3, and (d) OD4.
(a)(b)(c)(d)


#### 4.1.2. Baseline

In this study, we will evaluate our model compared with the following methods.iBAT [25]: iBAT exploits an isolation mechanism that anomalous trajectories are susceptible to, i.e., anomalies are easy to be separated from the majority of the trajectories since anomalies are “few and different.” It is more likely to be anomalous for a higher anomaly score.ATDC [23]: ATDC proposes a distance metric, namely, the DIS distance, to evaluate the similarity between any two trajectories. Based on the DIS distance, ATDC can further calculate the anomalous score of a trajectory and then determines if it is an anomalous trajectory.


#### 4.1.3. Evaluation Criteria

In this study, we employ the area under the receiver operating characteristic curve (AU-ROC) as the evaluation metric. To evaluate the performance of the anomaly detection method, detection rate (DR) and false alarm rate (FAR) (in this study, we refer to true positive rate (TPR) and false positive rate (FPR) as detection rate and false alarm rate respectively) are two important metrics. As shown in the confusion matrix Table2, trajectories are labeled either as anomalous (i.e., positive) or normal (i.e., negative).Table 2
The confusion matrix of the binary classification problem.
Prediction resultReal valueAnomalousNormalAnomalousTPFPNormalFNTNA trajectory will be classified as one of our possible outcomes: (1) true positive (TP): an anomalous trajectory is correctly predicted as anomalous; (2) false positive (FP): a trajectory is predicted as anomalous while it is normal; (3) false negative (FN): a trajectory is predicted as normal while it is anomalous; (4) true negative (TN): a normal trajectory is correctly predicted as normal. The DR measures the rate of correctly predicted anomalous trajectories among all real anomalies, i.e.,(19)DR=TPTP+FN.The FAR is defined as the proportion of normal trajectories that are predicted as anomalous, i.e.,(20)FAR=FPFP+TN.The better anomaly detection method will have a higher DR and a lower FAR. The ROC curve shows the detection rate (Y-axis) against the false alarm rate (X-axis) at various thresholds, which depicts the tradeoff between false alarms and accurate classifications. AU-ROC value is the area under the ROC curve, and the anomaly detection method is of better quality for higher AU-ROC.


### 4.2. Results

#### 4.2.1. Performance Evaluation on Anomalous Trajectory Detection

We evaluate the results on OD pair with the above baselines. Taking the instance ofOD2, the results of anomalous trajectory detection in OD2 are shown in Figure 5. As shown in the figure, the MAFRC-ATD model shows the highest detection rate under a given false alarm rate, indicating that it can effectively detect the anomalies. Similarly, the MAFRC-ATD model possessed of the lowest false alarm for a given detection rate, indicating that it has less potential for mistaken detection. For the overall curve, the ROC curve of the MAFRC-ATD model covers other the other two curves, suggesting that the MAFRC-ATD method performs better and has expressive power on anomalous trajectory detection.Figure 5
The performance evaluation on anomalous trajectories detection regardingOD2.To explore the influence of anomalous trajectory detection on different OD pairs instead of a given OD pair, we conduct experiments on 4 OD pairs. In detail, we train the model with the training dataset of each OD pair and then evaluate the testing dataset, respectively. OD pairs and the final results are shown in Table3. The results indicate that MAFRC-ATD achieves the best results over the 4 OD pairs and has the potential power to be well-suited for different situations.Table 3
Performance evaluation on anomalous trajectory detection in contrast to baseline.
MethodsODOD1OD2OD3OD4MAFRC-ATD1.000.981.001.00iBAT0.920.940.920.62ATDC0.820.720.830.93The experiments indicate that the MAFRC-ATD model could effectively capture the autoregressive characteristics of trajectories and model the probability density of subtrajectories. However, the reason for the undesirable results of iBAT and ATDC might be that those methods are based on distance or isolation mechanisms, mainly focusing on geometric information of the trajectory and neglecting the sequential information of the trajectory. Obviously, iBAT is well adapted to identify various detours, but may not be suitable for situations where anomalies are intertwined with normal onesOD4. ATDC performs a little terribly when existing local anomalous trajectories (such as OD2 and OD3); it applies to intertwined situations.


#### 4.2.2. Unintentionally Anomalous Trajectory Analysis

In addition to the performance of anomalous trajectories detection, discovering unintentionally anomalous trajectories is also essential. Route choice analysis is employed to discover the unintentional anomalies as follows.TakingOD1, for instance, there are 10 routes for this OD pair, denoted as r1 to r10, respectively, i.e., m=10 and ℂ=rj,forj=1,2,…,10. Trajectory set as well as link information for each route regarding OD1 can be shown in Table 4. Among all paths, r1 contains the most amount of trajectories. For the sake of convenience, “(…)” in r1 represents the trajectories of OD1 except what are contained in r2-r10. ?? shows each route in the OD1.Table 4
The trajectory index set and link information regardingOD1.
RouteTrajectory index setLink set1…[1, 2, 3, 4, 5, 6, 7, 8, 9]2[12][1, 10, 18, 11, 4, 5, 6, 7, 8, 9]3[7, 38, 83][1, 2, 12, 13, 6, 7, 8, 9]4[54][1, 14, 15, 16, 17, 7, 8, 9]5[81][1, 10, 19, 1, 2, 3, 4, 5, 6, 7, 8, 9]6[82][1, 14, 20, 21, 22, 7, 8, 9]7[99, 100, 101][1, 14, 15, 23, 24, 22, 7, 8, 9]8[102, 103, 104][1, 2, 3, 4, 25, 26, 27, 28, 7, 8, 9]9[105, 106, 107][1, 10, 29, 27, 28, 8, 9]10[108, 109, 110][1, 10, 18, 11, 4, 5, 6, 7, 28, 30, 9]In this study, we set velocity equivalent coefficientc as 8.91 m/s according to the mean speed value of historical trips. For any given link in OD1, the generalized cost of each route is calculated as the mean value of the generalized costs of all trajectories corresponding to this route.Whenδ sets to 0.02 and ξ sets to 1.5, experiments show that the trajectories corresponding to ℂn=C1,C2,C3 are normal, whereas trajectories to ℂan=Cj,forj=4,5,…,10 are anomalous. Among all anomalous trajectories, the trajectory corresponding to ℂun=r6, i.e., 82nd trajectory, is unintentionally anomalous, whereas trajectories corresponding to ℂun=ℂan/r6 are intentionally anomalous. Simply we can find that the 82nd trajectory happened on the evening peak hours, Tuesday. The choice probability of the 82nd trajectory is large enough, i.e., greater than 1/mξ, to make the anomaly score less than 1 despite greater than δ. Henceforth, we have sufficient confidence that the 82nd trajectory (i.e., corresponding to r6) has the strong potential to be chosen when taking this trip. This result indicates that the 82nd trajectory could be unintentionally generated by drivers whose intentions are to avoid traffic congestion to reduce trip time during peak hours. The results agree well with the route choice probability result, as shown in Figure 6.Figure 6
The route choice probability of each route inOD1.


## 4.1. Experimental Setup

### 4.1.1. Dataset Preprocessing

Our experiments are conducted on the real-world taxi trajectory dataset provided by Kaggle ECML-PKDD 2015 competition (https://www.kaggle.com/c/pkdd-15-predict-taxi-service-trajectory-i/data). In detail, the dataset is generated from 442 taxis running in the city of Porto from 01/07/2013 to 30/06/2014. There are 1710670 raw trajectories in total and each taxi reports its location every 15 seconds.Out of approximately 1.7 million trajectories from the original dataset, we remove the trajectories with less than 20 GPS. After filtering, we split the city traffic network space into100m×100m grids, i.e., gl=gw=100m. Consequently, GPS points can be represented with grids and each trajectory can be denoted by a sequence of grids. Subsequently, we extract 4 OD pairs, denoted as OD1 to OD4, respectively. In this study, we segment a trajectory into subtrajectories with 20 GPS points, that is, d=20. Given the fact that there is no labeled dataset available, we choose to manually label anomalies in this paper.Additionally, inspired by Liu et al. [34], to alleviate the problem of unbalanced learning in anomaly detection, we select several detour paths from which anomalous trajectories are generated. The detour paths, called generated routes, traverse the real-world links and are implemented in ArcGIS and Google maps. Among the generated routes, generated anomalous trajectories can be generated through sampling from the GPS points of generated routes. The generated anomalous trajectories are injected into the original dataset for “data argument.”As stated above, the related information of those OD pairs is shown in Table1, where O and D are represented with (longitude and latitude), and each OD pair can be shown in Figure 4. Out of all testing trajectories, the coral color lines represent the original historical dataset in the testing dataset, whereas other colors represent the generated routes from which the generated anomalous trajectories are sampled.Table 1
The information on OD pairs.
OD1OD2OD3OD4O(−8.6399, 41.1598)(−8.6109, 41.1457)(−8.6141, 41.1412)(−8.5856, 41.1485)D(−8.6542, 41.1806)(−8.6098, 41.1605)(−8.6497, 41.1544)(−8.6068, 41.1457)Historical trajectories996946687559Training dataset897852619504Testing datasetHistorical testing dataset99946855Generated trajectories12969Anomalous trajectories15101010Anomaly ratio (%)13.519.7113.5115.63Figure 4
The testing dataset of each OD pair, where the lawn green color upper triangle represents the pick-up location and the cyan color lower triangle represents the drop-off location. (a) OD1, (b) OD2, (c) OD3, and (d) OD4.
(a)(b)(c)(d)


### 4.1.2. Baseline

In this study, we will evaluate our model compared with the following methods.iBAT [25]: iBAT exploits an isolation mechanism that anomalous trajectories are susceptible to, i.e., anomalies are easy to be separated from the majority of the trajectories since anomalies are “few and different.” It is more likely to be anomalous for a higher anomaly score.ATDC [23]: ATDC proposes a distance metric, namely, the DIS distance, to evaluate the similarity between any two trajectories. Based on the DIS distance, ATDC can further calculate the anomalous score of a trajectory and then determines if it is an anomalous trajectory.


### 4.1.3. Evaluation Criteria

In this study, we employ the area under the receiver operating characteristic curve (AU-ROC) as the evaluation metric. To evaluate the performance of the anomaly detection method, detection rate (DR) and false alarm rate (FAR) (in this study, we refer to true positive rate (TPR) and false positive rate (FPR) as detection rate and false alarm rate respectively) are two important metrics. As shown in the confusion matrix Table2, trajectories are labeled either as anomalous (i.e., positive) or normal (i.e., negative).Table 2
The confusion matrix of the binary classification problem.
Prediction resultReal valueAnomalousNormalAnomalousTPFPNormalFNTNA trajectory will be classified as one of our possible outcomes: (1) true positive (TP): an anomalous trajectory is correctly predicted as anomalous; (2) false positive (FP): a trajectory is predicted as anomalous while it is normal; (3) false negative (FN): a trajectory is predicted as normal while it is anomalous; (4) true negative (TN): a normal trajectory is correctly predicted as normal. The DR measures the rate of correctly predicted anomalous trajectories among all real anomalies, i.e.,(19)DR=TPTP+FN.The FAR is defined as the proportion of normal trajectories that are predicted as anomalous, i.e.,(20)FAR=FPFP+TN.The better anomaly detection method will have a higher DR and a lower FAR. The ROC curve shows the detection rate (Y-axis) against the false alarm rate (X-axis) at various thresholds, which depicts the tradeoff between false alarms and accurate classifications. AU-ROC value is the area under the ROC curve, and the anomaly detection method is of better quality for higher AU-ROC.


## 4.1.1. Dataset Preprocessing

Our experiments are conducted on the real-world taxi trajectory dataset provided by Kaggle ECML-PKDD 2015 competition (https://www.kaggle.com/c/pkdd-15-predict-taxi-service-trajectory-i/data). In detail, the dataset is generated from 442 taxis running in the city of Porto from 01/07/2013 to 30/06/2014. There are 1710670 raw trajectories in total and each taxi reports its location every 15 seconds.Out of approximately 1.7 million trajectories from the original dataset, we remove the trajectories with less than 20 GPS. After filtering, we split the city traffic network space into100m×100m grids, i.e., gl=gw=100m. Consequently, GPS points can be represented with grids and each trajectory can be denoted by a sequence of grids. Subsequently, we extract 4 OD pairs, denoted as OD1 to OD4, respectively. In this study, we segment a trajectory into subtrajectories with 20 GPS points, that is, d=20. Given the fact that there is no labeled dataset available, we choose to manually label anomalies in this paper.Additionally, inspired by Liu et al. [34], to alleviate the problem of unbalanced learning in anomaly detection, we select several detour paths from which anomalous trajectories are generated. The detour paths, called generated routes, traverse the real-world links and are implemented in ArcGIS and Google maps. Among the generated routes, generated anomalous trajectories can be generated through sampling from the GPS points of generated routes. The generated anomalous trajectories are injected into the original dataset for “data argument.”As stated above, the related information of those OD pairs is shown in Table1, where O and D are represented with (longitude and latitude), and each OD pair can be shown in Figure 4. Out of all testing trajectories, the coral color lines represent the original historical dataset in the testing dataset, whereas other colors represent the generated routes from which the generated anomalous trajectories are sampled.Table 1
The information on OD pairs.
OD1OD2OD3OD4O(−8.6399, 41.1598)(−8.6109, 41.1457)(−8.6141, 41.1412)(−8.5856, 41.1485)D(−8.6542, 41.1806)(−8.6098, 41.1605)(−8.6497, 41.1544)(−8.6068, 41.1457)Historical trajectories996946687559Training dataset897852619504Testing datasetHistorical testing dataset99946855Generated trajectories12969Anomalous trajectories15101010Anomaly ratio (%)13.519.7113.5115.63Figure 4
The testing dataset of each OD pair, where the lawn green color upper triangle represents the pick-up location and the cyan color lower triangle represents the drop-off location. (a) OD1, (b) OD2, (c) OD3, and (d) OD4.
(a)(b)(c)(d)


## 4.1.2. Baseline

In this study, we will evaluate our model compared with the following methods.iBAT [25]: iBAT exploits an isolation mechanism that anomalous trajectories are susceptible to, i.e., anomalies are easy to be separated from the majority of the trajectories since anomalies are “few and different.” It is more likely to be anomalous for a higher anomaly score.ATDC [23]: ATDC proposes a distance metric, namely, the DIS distance, to evaluate the similarity between any two trajectories. Based on the DIS distance, ATDC can further calculate the anomalous score of a trajectory and then determines if it is an anomalous trajectory.


## 4.1.3. Evaluation Criteria

In this study, we employ the area under the receiver operating characteristic curve (AU-ROC) as the evaluation metric. To evaluate the performance of the anomaly detection method, detection rate (DR) and false alarm rate (FAR) (in this study, we refer to true positive rate (TPR) and false positive rate (FPR) as detection rate and false alarm rate respectively) are two important metrics. As shown in the confusion matrix Table2, trajectories are labeled either as anomalous (i.e., positive) or normal (i.e., negative).Table 2
The confusion matrix of the binary classification problem.
Prediction resultReal valueAnomalousNormalAnomalousTPFPNormalFNTNA trajectory will be classified as one of our possible outcomes: (1) true positive (TP): an anomalous trajectory is correctly predicted as anomalous; (2) false positive (FP): a trajectory is predicted as anomalous while it is normal; (3) false negative (FN): a trajectory is predicted as normal while it is anomalous; (4) true negative (TN): a normal trajectory is correctly predicted as normal. The DR measures the rate of correctly predicted anomalous trajectories among all real anomalies, i.e.,(19)DR=TPTP+FN.The FAR is defined as the proportion of normal trajectories that are predicted as anomalous, i.e.,(20)FAR=FPFP+TN.The better anomaly detection method will have a higher DR and a lower FAR. The ROC curve shows the detection rate (Y-axis) against the false alarm rate (X-axis) at various thresholds, which depicts the tradeoff between false alarms and accurate classifications. AU-ROC value is the area under the ROC curve, and the anomaly detection method is of better quality for higher AU-ROC.


## 4.2. Results

### 4.2.1. Performance Evaluation on Anomalous Trajectory Detection

We evaluate the results on OD pair with the above baselines. Taking the instance ofOD2, the results of anomalous trajectory detection in OD2 are shown in Figure 5. As shown in the figure, the MAFRC-ATD model shows the highest detection rate under a given false alarm rate, indicating that it can effectively detect the anomalies. Similarly, the MAFRC-ATD model possessed of the lowest false alarm for a given detection rate, indicating that it has less potential for mistaken detection. For the overall curve, the ROC curve of the MAFRC-ATD model covers other the other two curves, suggesting that the MAFRC-ATD method performs better and has expressive power on anomalous trajectory detection.Figure 5
The performance evaluation on anomalous trajectories detection regardingOD2.To explore the influence of anomalous trajectory detection on different OD pairs instead of a given OD pair, we conduct experiments on 4 OD pairs. In detail, we train the model with the training dataset of each OD pair and then evaluate the testing dataset, respectively. OD pairs and the final results are shown in Table3. The results indicate that MAFRC-ATD achieves the best results over the 4 OD pairs and has the potential power to be well-suited for different situations.Table 3
Performance evaluation on anomalous trajectory detection in contrast to baseline.
MethodsODOD1OD2OD3OD4MAFRC-ATD1.000.981.001.00iBAT0.920.940.920.62ATDC0.820.720.830.93The experiments indicate that the MAFRC-ATD model could effectively capture the autoregressive characteristics of trajectories and model the probability density of subtrajectories. However, the reason for the undesirable results of iBAT and ATDC might be that those methods are based on distance or isolation mechanisms, mainly focusing on geometric information of the trajectory and neglecting the sequential information of the trajectory. Obviously, iBAT is well adapted to identify various detours, but may not be suitable for situations where anomalies are intertwined with normal onesOD4. ATDC performs a little terribly when existing local anomalous trajectories (such as OD2 and OD3); it applies to intertwined situations.


### 4.2.2. Unintentionally Anomalous Trajectory Analysis

In addition to the performance of anomalous trajectories detection, discovering unintentionally anomalous trajectories is also essential. Route choice analysis is employed to discover the unintentional anomalies as follows.TakingOD1, for instance, there are 10 routes for this OD pair, denoted as r1 to r10, respectively, i.e., m=10 and ℂ=rj,forj=1,2,…,10. Trajectory set as well as link information for each route regarding OD1 can be shown in Table 4. Among all paths, r1 contains the most amount of trajectories. For the sake of convenience, “(…)” in r1 represents the trajectories of OD1 except what are contained in r2-r10. ?? shows each route in the OD1.Table 4
The trajectory index set and link information regardingOD1.
RouteTrajectory index setLink set1…[1, 2, 3, 4, 5, 6, 7, 8, 9]2[12][1, 10, 18, 11, 4, 5, 6, 7, 8, 9]3[7, 38, 83][1, 2, 12, 13, 6, 7, 8, 9]4[54][1, 14, 15, 16, 17, 7, 8, 9]5[81][1, 10, 19, 1, 2, 3, 4, 5, 6, 7, 8, 9]6[82][1, 14, 20, 21, 22, 7, 8, 9]7[99, 100, 101][1, 14, 15, 23, 24, 22, 7, 8, 9]8[102, 103, 104][1, 2, 3, 4, 25, 26, 27, 28, 7, 8, 9]9[105, 106, 107][1, 10, 29, 27, 28, 8, 9]10[108, 109, 110][1, 10, 18, 11, 4, 5, 6, 7, 28, 30, 9]In this study, we set velocity equivalent coefficientc as 8.91 m/s according to the mean speed value of historical trips. For any given link in OD1, the generalized cost of each route is calculated as the mean value of the generalized costs of all trajectories corresponding to this route.Whenδ sets to 0.02 and ξ sets to 1.5, experiments show that the trajectories corresponding to ℂn=C1,C2,C3 are normal, whereas trajectories to ℂan=Cj,forj=4,5,…,10 are anomalous. Among all anomalous trajectories, the trajectory corresponding to ℂun=r6, i.e., 82nd trajectory, is unintentionally anomalous, whereas trajectories corresponding to ℂun=ℂan/r6 are intentionally anomalous. Simply we can find that the 82nd trajectory happened on the evening peak hours, Tuesday. The choice probability of the 82nd trajectory is large enough, i.e., greater than 1/mξ, to make the anomaly score less than 1 despite greater than δ. Henceforth, we have sufficient confidence that the 82nd trajectory (i.e., corresponding to r6) has the strong potential to be chosen when taking this trip. This result indicates that the 82nd trajectory could be unintentionally generated by drivers whose intentions are to avoid traffic congestion to reduce trip time during peak hours. The results agree well with the route choice probability result, as shown in Figure 6.Figure 6
The route choice probability of each route inOD1.


## 4.2.1. Performance Evaluation on Anomalous Trajectory Detection

We evaluate the results on OD pair with the above baselines. Taking the instance ofOD2, the results of anomalous trajectory detection in OD2 are shown in Figure 5. As shown in the figure, the MAFRC-ATD model shows the highest detection rate under a given false alarm rate, indicating that it can effectively detect the anomalies. Similarly, the MAFRC-ATD model possessed of the lowest false alarm for a given detection rate, indicating that it has less potential for mistaken detection. For the overall curve, the ROC curve of the MAFRC-ATD model covers other the other two curves, suggesting that the MAFRC-ATD method performs better and has expressive power on anomalous trajectory detection.Figure 5
The performance evaluation on anomalous trajectories detection regardingOD2.To explore the influence of anomalous trajectory detection on different OD pairs instead of a given OD pair, we conduct experiments on 4 OD pairs. In detail, we train the model with the training dataset of each OD pair and then evaluate the testing dataset, respectively. OD pairs and the final results are shown in Table3. The results indicate that MAFRC-ATD achieves the best results over the 4 OD pairs and has the potential power to be well-suited for different situations.Table 3
Performance evaluation on anomalous trajectory detection in contrast to baseline.
MethodsODOD1OD2OD3OD4MAFRC-ATD1.000.981.001.00iBAT0.920.940.920.62ATDC0.820.720.830.93The experiments indicate that the MAFRC-ATD model could effectively capture the autoregressive characteristics of trajectories and model the probability density of subtrajectories. However, the reason for the undesirable results of iBAT and ATDC might be that those methods are based on distance or isolation mechanisms, mainly focusing on geometric information of the trajectory and neglecting the sequential information of the trajectory. Obviously, iBAT is well adapted to identify various detours, but may not be suitable for situations where anomalies are intertwined with normal onesOD4. ATDC performs a little terribly when existing local anomalous trajectories (such as OD2 and OD3); it applies to intertwined situations.


## 4.2.2. Unintentionally Anomalous Trajectory Analysis

In addition to the performance of anomalous trajectories detection, discovering unintentionally anomalous trajectories is also essential. Route choice analysis is employed to discover the unintentional anomalies as follows.TakingOD1, for instance, there are 10 routes for this OD pair, denoted as r1 to r10, respectively, i.e., m=10 and ℂ=rj,forj=1,2,…,10. Trajectory set as well as link information for each route regarding OD1 can be shown in Table 4. Among all paths, r1 contains the most amount of trajectories. For the sake of convenience, “(…)” in r1 represents the trajectories of OD1 except what are contained in r2-r10. ?? shows each route in the OD1.Table 4
The trajectory index set and link information regardingOD1.
RouteTrajectory index setLink set1…[1, 2, 3, 4, 5, 6, 7, 8, 9]2[12][1, 10, 18, 11, 4, 5, 6, 7, 8, 9]3[7, 38, 83][1, 2, 12, 13, 6, 7, 8, 9]4[54][1, 14, 15, 16, 17, 7, 8, 9]5[81][1, 10, 19, 1, 2, 3, 4, 5, 6, 7, 8, 9]6[82][1, 14, 20, 21, 22, 7, 8, 9]7[99, 100, 101][1, 14, 15, 23, 24, 22, 7, 8, 9]8[102, 103, 104][1, 2, 3, 4, 25, 26, 27, 28, 7, 8, 9]9[105, 106, 107][1, 10, 29, 27, 28, 8, 9]10[108, 109, 110][1, 10, 18, 11, 4, 5, 6, 7, 28, 30, 9]In this study, we set velocity equivalent coefficientc as 8.91 m/s according to the mean speed value of historical trips. For any given link in OD1, the generalized cost of each route is calculated as the mean value of the generalized costs of all trajectories corresponding to this route.Whenδ sets to 0.02 and ξ sets to 1.5, experiments show that the trajectories corresponding to ℂn=C1,C2,C3 are normal, whereas trajectories to ℂan=Cj,forj=4,5,…,10 are anomalous. Among all anomalous trajectories, the trajectory corresponding to ℂun=r6, i.e., 82nd trajectory, is unintentionally anomalous, whereas trajectories corresponding to ℂun=ℂan/r6 are intentionally anomalous. Simply we can find that the 82nd trajectory happened on the evening peak hours, Tuesday. The choice probability of the 82nd trajectory is large enough, i.e., greater than 1/mξ, to make the anomaly score less than 1 despite greater than δ. Henceforth, we have sufficient confidence that the 82nd trajectory (i.e., corresponding to r6) has the strong potential to be chosen when taking this trip. This result indicates that the 82nd trajectory could be unintentionally generated by drivers whose intentions are to avoid traffic congestion to reduce trip time during peak hours. The results agree well with the route choice probability result, as shown in Figure 6.Figure 6
The route choice probability of each route inOD1.


## 5. Conclusion

Anomaly trajectory detection is crucial for preserving the legitimate interests of passengers and discovering the pattern of anomalous driving behaviors. In this study, we propose an unsupervised detection framework, namely, MAFRC-ATD, to detect anomalous trajectories. Compared to traditional methods, MAFRC-ATD can carry out the following:(1)
Taking the spatiotemporal information of trajectory data into consideration, the MAFRC-ATD model exploits the autoregressive character of trajectories and effectively captures the spatiotemporal information of trajectories, making it possible to assign lower likelihoods to anomalous trajectories(2)
Incorporating the route choice model to discover the unintentional anomalous due to traffic congestion, route choice analysis is employed to further explore the motivation behind random choice behaviors, such as traffic congestionMoreover, multi-od experiments are also conducted to evaluate the generalization properties of the MAFRC-ATD model. Experiments on the real-world dataset demonstrate the effectiveness of our methods over baseline methods. Furthermore, testing the proposed method with more real-world datasets is crucial to evaluate the applicability and robustness of the method, which is left for our future study.In the future, we will extend our model online with time-series methods, such as the self-attention mechanism. In addition, the ensembling-based NF model could perform better to alleviate the imbalance learning problem.



---

*Source: 7223646-2022-10-18.xml*