Modern GPS recording devices and big data infrastructures enable us to study trafic patterns in a multitude of ways, including trajectory outlier detection. A trajectory is a sequence of consecutive geographical points that can also have timestamps and an outlier is defined as a record, which in our case is a trajectory, that significantly difers from the norm. In this work, we are motivated by the need (i) to encapsulate trajectory outlier detection in real-life Fleet Management Systems (FMSs) and (ii) to improve the performance of existing outlier detection methods. To this end, two trajectory outlier detection methods are proposed, the first one relying on the DBSCAN clustering algorithm and the Hausdorf distance and the second one relying on a Support Vector Machine (SVM) classifier and the Generalized Sequence Pattern algorithm. These two algorithms are evaluated against baselines on two automatically labeled trafic datasets, the former from the Beijing metropolitan area and the latter from a real FMS in Cyprus. Automated labelling process is adopted to both allow for reproducibility and lift the burden of manual annotations from domain experts. The results show that our proposals exhibit better performance than the baselines in terms of accuracy and the F1 score, while, in general, the SVM model performs better than the path clustering one. Finally, trafic clusters and specific outliers are discussed to prove the validity of the models.
1. Introduction With the massive trafic data generation in urban and rural street grids, the rapid growth of urbanization and also the geolocation functionality embedded in virtually all portable devices such as smartphones, wearables and navigation devices, the need and opportunity for performing trafic analytics arises, mostly on urban trafic data since the trafic in cities is significantly more massive and chaotic than in rural areas. Trafic analytics comprises a broad range of techniques that include, among others, spotting trafic patterns and, in a complementary manner, detecting anomalies in the trafic data.
Targeted anomalies can either be individual flows , subtrajectories or entire trajectories [1]. A flow is defined as the number of objects moving on the road section from location A to location B on a timestamp or in a certain time-slot. Trajectories are defined as sequences of locations that a vehicle passes through and can also have a timestamp for each point, thus making them spatiotemporal sequences. A sub-trajectory is a slice of a larger trajectory, which implies that a larger trajectory can be split into sub-trajectories to study trafic patterns and outliers at a finer detail.
There are several areas that utilize trafic data outliers, which highlights the value of this research field. Example use cases are the following: • Urban trafic detection: The most obvious use of trajectory outlier detection is the detection of trafic patterns and anomalies. Two research works that deal with this use case are the one authored by Kong et al. [2], who study anomalous areas with long-term trafic issues by analyzing bus route data, and the one by Djenouri et al. [3], who analyze the distribution of flow outliers in the city of Odense, Denmark. • Fraud and crime detection: This includes taxi drivers who intentionally take longer routes than needed in order to increase the cost for the clients [4] or do unmetered trips and overcharge without getting noticed [5]. Another representative case is the detection of illegal maritime activity [6]. • Abnormal weather patterns: An example of this category is detecting outlier trajectories and sub-trajectories of storms, typhoons and other meteorological data, like in the work of Lee at al. [7], who attempt to detect outlying subtrajectories from real hurricane trajectory data. • Animal Movement Analysis: Unusual animal movements, which do not conform to an expected pattern, are frequently of great interest to biologists and botanists. The approach of Li et al [8] utilizes animal trajectory data to discover animal movement patterns. to yield solutions with higher performance than existing fortunately, most published papers do not include links methods while allowing for reproducibility. We start with to the code used by the researchers, so, for the needs explaining the categories in trafic flow outlier detection of a benchmarking comparison among diferent models, systems. an implementation of a few already proposed models is
A main criterion to divide trajectory outlier detection needed. This benchmarking should also include methods systems is based on online versus ofline processing. On- from the event sequence mining area, as reasoned above. line systems are capable of producing their output in However, the biggest problem is not the lack of free imreal-time, for example in real-time trafic reporting ap- plementations of several existing methods, but the lack plications, while ofline systems are applied on datasets of labeled data and data that has temporal features for trato extract post-mortem insights from them. The online jectories. Regarding labeled data, very few publications methods are used for processing data streams in real include links to publicly available datasets and even fewer time, since they can provide insights about shorter parts include labeled datasets or the ground truth. For papers of the route and proceed to recommendations on the that include unlabeled public datasets, most authors use lfy, while the ofline methods do not provide such fine- an annotation by field experts as ground truth, which grained analysis, especially if they are not combined with makes their results hard or even impossible to reproduce. an additional post-processing analysis step after the out- As for the labeled datasets, there has to be more informalier detection. Our work belongs to the latter category, tion (temporal features) for the datasets to be more comaccording to the main requirements in real Fleet Manage- plete. Thus, an automated annotation method is needed ment Systems (FMSs) by which we are motivated. so that there can be produced (real-world) datasets that
The three families of trafic flow outlier detection sys- are accompanied by ground truth information, so that tems are distinguished by Djenouri et al. [1] as (i) statis- diferent trajectory outlier techniques can be objectively tical methods, which use statistical measures and theory compared against each other. In our work, we adopt an to find anomalous trafic flows; (ii) similarity methods, established method for automated labelling so that the which apply neighbourhood computations and clustering main experiments are objective. for the same purpose; and finally (iii) pattern mining methods, which use and extend well-known algorithms such 1.2. Contribution and Structure as FP-Growth and Apriori, and similar pattern-mining approaches.
Another way to process trajectories is viewing them as event sequences, where events correspond to an object passing through a crossroad, or a specific coordinates point or a grid area (in case the area studied is split into grids to group same-area GPS points). Based on this rationale, event sequence mining methods such as [9] can be useful; these methods find frequent and infrequent (outlying) sequence patterns in datasets. Table 1 ness and conciseness by using the minimum description Overview of main existing methods length (MDL) principle. In a similar way, Eldawy and
Name Outlier Type Approach Mokhtar[11] propose a method to detect trajectory outTRACLUS[10] Sub-trajectories Clustering liers that also uses the DBSCAN algorithm and the MDL Eldawy[11] Trajectories Clustering principle. DBSCAN and k-means are also used in the proZhongjian et al.[12] Trajectories Clustering posed method of [12]. Other algorithms proposed include RomiVaAnTe+t[1a4l.][13] SuTbr-atjreacjetocrtoiersies CClluusstteerriinngg iVAT, iVAT+, clustiVAT, clustiVAT+ ([14][15]), and CaD clustiVAT+[15] Trajectories Clustering ([13]) that uses the TSA [32] algorithm to break down TPRO[16] Trajectories Clustering the trajectories.
TPRRO [17] Trajectories Clustering Statistics-based methods: Statistics-based methods Zhang[4] Trajectories Statistics adopt the basic rationale that if the features extracted MT-MAD[18] Trajectories Statistics from a data point (such as distance, speed, direction, trafLLaiun eett aall..[[2109]] SuTbra-tfircaFjelocwtosries SSttaattiissttiiccss ifc condition) exceed a threshold or deviate enough from Bao et al.[21] Sub-trajectories Statistics the norm, it is an outlier. For example, the authors of [20] TRAOD[7] Sub-trajectories Density detect outlying trafic flows by measuring their extremeDBTOD[22] Sub-trajectories Density ness in terms of deviation from the frequent transition LDTRAOD[23] Sub-trajectories Density volume between street network nodes and from the trafDjYenuoeutraile.[t2a4l][3] SuTbra-tfircaFjelocwtosries DDeennssiittyy ifc in previous days and weeks. In [ 4], the authors detect Djenouri et al.[25] Trafic Flows Density outlier trajectories based on their length deviation from
LoTAD[2] Sub-trajectories Density the optimal path’s deviation for each trajectory. In [19], TF-Outlier[26] Sub-trajectories Density a sub-trajectory is marked as outlying if it deviates sigMaiorano[27] Sub-trajectories Other nificantly from other sub-trajectories in terms of trafic Varlamis et al.[6] Sub-trajectories Other volume. Other methods in this category include [16] [17] TOP[9] Trajectories Other iBAT[28] Trajectories Other [21] [18].
DeepTEA[29] Trajectories Other Density-based methods: Density-based methods Our proposal Trajectories Clustering + Other leverage the basic idea is that if a data point lies in a lowdensity region, then it must be some kind of an anomaly.
This may look similar to the clustering based methods, available.4 however it is diferent since there are no frequent group
The structure of the paper is as follows. In Section forming general patterns detected by density-based meth2, the relevant literature is discussed. In Section 3, the ods. The TRAOD algorithm[7] is a partition-and-detect proposed methods are presented. Section 4 deals with the method that uses the distance and density measures for evaluation results and Section 5 includes the conclusions trajectory fragments and is used as an inspiration for from this work and discussion of future work. multiple research works, such as [22] and [23]. [24] uses a k-neighbor strategy to detect outlier sub-trajectories and leverages the duration in which a trajectory is an out2. Related Work lier or an inlier. [3] also follows a kNN approach. Other We organize the related work according to the algorith- interesting approaches are these in [25] [2] and [26]. mic approaches followed, whereas a summary is pre- Other methods: This part includes methods that do sented in Table 1. The focus is on trajectory outliers, not fit in the prior classification. The work of [ 6] uses however the table contains a broader range of proposals. graph theory to produce a network abstraction of mar
Clustering-based methods: Trajectory outlier detec- itime vessels’ trajectories. The authors of [9] propose an tion methods that rely on clustering usually apply a com- event sequence outlier detection method that uses a patmon clustering algorithm, such as DBSCAN, k-means, tern mining algorithm to detect outlying event sequences. k-medoids, and employ a diferent distance function than This approach can be generalized to trajectories by repthe euclidean distance or Manhattan distance that are resenting a transition through a road section as an event. usually applied in most clustering libraries and applica- The algorithm returns contextually frequent patterns and tion scenarios. In [30], which is extended by [31], the contextual outliers by employing a pattern mining algoauthors apply trajectory clustering among other meth- rithm called Reduce. [27] apply a rough (uncertain) set ods, in order to find trajectory outliers. The clustering theory-based approach to detect outlying sub-trajectories method that they use is the one of [10], which is based on based on the number of outlying points a trajectory conthe DBSCAN algorithm. They break-down trajectories tains. [29] is a probabilistic model that uses deep neural in segments in an optimal way that maximizes precise- and convolutional networks to detect time-dependent outliers and handle complex trafic conditions. Finally, 4https://github.com/amoavinis/trajectory-outliers the authors of [28] use the Isolation Forest algorithm to detect outlying trajectories. is used for sequence mining. It includes two main steps
How does our proposal compare to the above work? that can run iteratively, namely candidate generation and The answer is that it is a novel hybrid solution for tra- support counting. It returns frequent sub-sequences of jectory outlier detection. It utilizes the DBSCAN cluster- the dataset’s sequences. ing algorithm, similarly to [30], [31], [10], [11] and [12].
But it goes beyond clustering and also employs a SVM 3.2. Path Clustering classifier, and optionally, a sequential pattern mining component (GSP). More importantly, it investigates the The path clustering method that we adopt uses the DBimpact of Hausdorf distance when employing DBSCAN. SCAN algorithm to cluster the trajectories based on the Since we extend clustering-based solutions, the evalua- similarity of their paths. In our context, two trajectories tion presented in Section 4 focuses on (i) evaluating the are considered close to each other if their paths are ‘close’ efectiveness of such extensions; and (ii) evaluating the to each other. This closeness is measured with two difimprovements upon other solutions for trajectory outlier ferent distance functions, the Hausdorf distance and the detection, such as the ones presented in [9] and [4]. The DTW distance. proposals in [9] and [4] fall in the “Other" and “Statis- Roughly speaking, two trajectories, each represented tics" approach categories, respectively. Moreover, the as a sequence of points, are close with regard to the Hausproposal in [9] also leverages sequential pattern mining. dorf distance if every point of either trajectory is Due to the diferent focus, we do not directly compare close to some points of the other trajectory. The formula with the other trajectory outlier detection techniques in is: the “Other" category. The work in [6] is more tailored to vessels and relies on attributes such as speed, bearing and bearing rate, and percentile values. The proposal (, ) = (ℎ(, ), ℎ( , )) in [29] focuses on time-dependent anomalies, which we leave for future work. Finally, iBAT [28] uses grid cells as we do, but focuses on trajectories including rare points, ℎ(, ) = m∈ax(m∈in ((, ))) which is not the case we target.
with dist(a, b) being the Euclidean distance between points and . 3. Proposed Method The Hausdorf distance between trajectories and returns the maximum unidirectional Hausdorf disOur proposal employs (sequential) pattern mining, tance from to and from to . It measures the DBSCAN-based clustering and SVM-based classification. maximum degree of mismatching between two trajectoIn the sequel, we describe each component separately. ries.
The novelty is in the usage of the Hausdorf distance. Hausdorf distance is extremely sensitive to noise. For Then, we explain two approaches to combining our pro- example, a single point of far away from will reposals and, at the end of the section, we summarize the sult in a large distance value. In this case, the calculated novel aspects. distance is unable to represent actual diference between trajectories. Employing the Hausdorf distance is a novel 3.1. Auxiliary Techniques element of our solution, since, to the best of our knowledge, it has not been used for trafic outlier detection in Grid partitioning is used in order to discretize and com- any published work known to the author. This distance pact trajectories. Because each trajectory consists of hun- function has quadratic complexity because it requires dreds or thousands of GPS points, a scalable system can the calculation of all distances between the points of the largely benefit from a significant reduction of the input two trajectories. So, given two trajectories with lengths size, since operations that require calculations between and , the time complexity is (). For this reaall points of two trajectories are of quadratic complexity son, the length of the trajectories should be decreased in and thus can experience speedups of several orders of such a way as to retain the properties of the paths and magnitude. Grid partitioning simply divides the 2D plane at the same time to not make the distance computation into rectangular grid cells and each trajectory forming too time-expensive. This is achieved by grid-partitioning a sequence of GPS points gets mapped to a sequence of the 2D plane and then converting the trajectories into grid cells. Numerous consecutive GPS points fall in the sequences of grid cells, as already explained. same grid cell, which is recorded only once, thus greatly Dynamic Time Warping (DTW) is a technique reducing the size of the trajectory. proposed by Sankof and Kruskal to find the optimal
Additionally, the GSP algorithm (Generalized Sequen- alignment between two time-dependent sequences [34]. tial Pattern) [33], which is based on the Apriori algorithm, It is suitable for matching trajectories of diferent length. The sequences are “warped" non-linearly with regards to is calculated and the lengths are aggregated into time to calculate a measure of their similarity indepen- a total length of the trajectory. dently of certain non-linear variations in the time dimen- 4. Deviation from closest frequent subsequence: the sion. The formula to calculate the DTW score between a Hausdorf distance of the trajectory and its closest trajectory A of length and a trajectory B of length is: frequent sub-trajectory, as calculated by the GSP ⎪⎪⎧0 = = 0 algorithm.
⎪⎪⎪([− 1], [− 1]) DTW(A, B) = ⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪+ ⎨⎧⎪⎪⎩ (((,(())(,,)))()) * > 0 thoaIvonebtotaoridnbeetrhtmeoiltnars-atminfaetaxhtusecrSaeVl,enMdamionnetlhytheteh[se0e-df1ee]avrtiauantriegosen,.firfIsrntotmohredtyheer ⎪⎩⎪∞ closest frequent subsequence, the Generalized Sequenwhere Rest(L) is the trajectory without its final point tial Path Mining (GSP) is used. For this final step, the and dist is the distance function used to compute the GSP model first learns the frequent sub-trajectories by deviation between two points of the trajectory (Euclidean using the grid-converted trajectories, and the Hausdorf distance). The complexity of this algorithm is ( * ), distance calculation between a trajectory under evalui.e., the same complexity as the Hausdorf distance. ation and a grid representation frequent sub-trajectory
In addition, we may want to experiment with unidi- requires the trajectory to be also converted to its grid cell mensional trajectories. A mathematical method to trans- representation. form 2D sequences into single dimensional ones is the Hilbert curve, which falls into the larger family of space- 3.4. Combining the two solutions iflling curves. A space-filling curve is a curve whose range contains the entire 2-dimensional unit square. The We explore if a combination of the outputs of the two Hilbert curve is a space-filling curve that adequately pre- solutions, the one based on path clustering and the SVM serves point locality. The curve is firstly constructed one, will perform better, two approaches are examined. and each point on it corresponds to a number, which The first one involves a simple logistic regression model, starts from 0 at the start of the curve and increases lin- which is applied on the results of the two solutions. It early as the curve progresses. For any 2D point that is takes 2 inputs (the 0 or 1 value from each model) and to be converted to a Hilbert curve 1D representation, produces 2 outputs, one for each class. In detail, the the nearest point of the curve is found and the point is outputs of the path clustering and the SVM model, which mapped to its number value. This notion is used to cal- (for each instance) are two single integers that can be 0 culate a distance between 2D points as a substitute for or 1, are stored and then used as input to train the logistic the Euclidean distance. In this paper, a third distance regression model, which is trained with the ground truth; function is used for the Path Clustering method, which 0 corresponds to the ’inlier’ class and 1 to the ’outlier’ is the same as the already mentioned DTW distance but class. The second combination approach is a logical OR uses this Hilbert distance instead of the Euclidean dis- operator applied on the outputs. For a single trajectory, tance between points. In detail the distance of 2 points is if either the clustering or the SVM model labels it as an (()− (), where and are the two outlier, the system decides that it is an outlier; else it is an points, is the absolute value function and is inlier. The above process implies that we are interested the function that converts the 2D point into a 1D Hilbert in binary labelling of the trajectories. Quantifying the curve representation. For both DTW variations, the grid degree of outlierness is left for future work, although it cell conversion of trajectories that happens before the is straightforward to extend our techniques to produce Hausdorf distance is calculated is also applied. outlier scores rather than just binary labels.
this proposal, we build a classification model using the following features: In a nutshell, we investigate a solution consisting of (i) a path clustering module that uses the DBSCAN algo1. Starting coordinates: converted from latitude- rithm and the Hausdorf distance, and (ii) a SVM classifier longitude to min-max-normalized values from module that uses the starting and ending coordinates, 0 to 1. trip distance and Hausdorf distance from nearest GSP2. Destination coordinates: similar to starting coor- generated sub-trajectory as features. The output of these dinates. two modules can be combined. The novelty of our work is the usage of the Hausdorf distance as a distance metric 3. Distance: the total distance of the trajectory. The for the DBSCAN algorithm and in the features fed to the length of each path section between two points SVM-based solution, which yields a novel proposal for The second dataset is provided by Istognosis Ltd. and employing a SVM model and leveraging the GSP algo- is not publically available. It is referred to as the “Cyprus" rithm in order to find the nearest frequent sub-trajectory dataset. It contains approximately 17K trajectories from for each trajectory. Furthermore, these novelties can be the company’s customer base. The main trajectory type employed in combination. As the following experiments it includes is movement of cargo vehicles that serve retail suggest, our solution improves on the state-of-the-art in stores by providing shopping goods from distribution real trafic datasets. centers. The total length of the trajectories is 151000 kilometers, making each trajectory significantly shorter (on average) than the Geolife trajectories. 4. Experimental Evaluation Both datasets, in their original format, just include coordinates and timestamps for the trajectories and do To evaluate our techniques, we need to employ ground not contain labels for the training of a supervised tratruth. To this end, and since there are no publicly avail- jectory outlier detection system. So, a systematic, imable trafic datasets that are suitable for assessing the partial and reproducible labeling process has to take performance of trajectory outlier detection solutions, we place for the usage of the dataset in the evaluation of ifrst explain how such ground truth can be yielded in a the proposed method. In addition, the labeling process systematic manner. The provision of labels is a signifi- has to be automated because the options of manual lacant by-product of our work and a useful contribution beling by the dedicated user groups and/or experts is too for other researchers and practitioners in the same field. resource-consuming. In our approach, the process folThen, we explain our competitors and finally, we present lowed by Wu et al.[38] for the automatic labeling of their our experiments that focus on assessing the efectiveness dataset is applied. They first partition the dataset into of the outlier detection process using the accuracy and start-destination pair-based partitions, and the ones that F1 measures. contain fewer trajectories than a threshold minThr are ifltered out. In this implementation, a start-destination 4.1. Datasets and systematic labeling pair is not defined by the coordinates but by the grid square that the points fall in. After this filtering, the removed trajectories are marked as outliers and for each remaining partition, the following process is followed. A complete linkage agglomerative clustering is performed with the Jaccard distance as the distance function. The exact formula is:
The first one is the Geolife dataset[ 35][36][37], created by the Geolife project of Microsoft Research Asia. The data was collected from 182 users in the time period from April 2007 to August 2012 in the area of Beijing. A trajectory of this dataset is a sequence of time-stamped points. For teiatcuhdep.oTinhti,stdhaetfaesaettucroesntianicnlusd1e7,l6a2ti1tutrdaej,elcotnogriietus,dreuannndinagl- (, ) = 1 − ||(( ∪∩ ))|| a total distance of approximately 1.2 million kilometers.
The trajectories were recorded by using various GPS for routes , ; the routes refer to grid cell sequences tracking devices and are thus of diferent sampling rates. as already explained.
A broad range of outdoor movements are included, such After the clustering, for each start-destination partias commuting, sports activities, shopping, sightseeing, tion the clusters that are of relative size to their respechiking, and cycling. tive partition’s size greater than a ratio threshold thr are
We first proceed with dataset cleaning. The dataset in- marked as inliers; otherwise, they are marked as outcludes trajectories with data points that are not valid GPS liers. Note that this labeling technique relies on spatial coordinates or are produced by wrong measurements and information without taking into account the temporal appear to be very far from the rest of the dataset points, information; so the outlier ground truth produced refer e.g. a latitude value of 440 (which is not a valid value) or only to the spatial aspect of the trajectories. 30, which is unreasonably far from Beijing. Also, there In our implementation, the grid partitioning parameter are few trajectories that reach very far from the area of is set to 5 for the Geolife dataset and 10 for the Cyprus the city; including such datasets in the test dataset would dataset, the complete linkage clustering parameter to shift the outlier detection away from detecting inner-city stop cluster merging is set to 0.4 for both, the minThr outlying trajectories and towards detecting peripheral parameter is 15 and the thr parameter is 0.03. These outliers, while this work chooses to study the trajectories parameters are set so that the outlier ratio is near 5% of that are in the close vicinity of the city. Thus, the dataset the dataset. is filtered so that it includes only trajectories with points with a latitude from 39.65 to 40.3 degrees and a longitude of 116.1 to 116.6 degrees.
The former is named TOP both in the original paper and also in our evaluation. The latter is originally based on Djikstra shortest path calculation with a significant speedup from the usage of the Contraction Hierarchies algorithm. In our implementation though, the Contraction Hierarchies is not used. The reason is that we are mostly interested in the accuracy and F1 measure of the solutions. Since it is a variation of the originally proposed algorithm, it is named DODB in the results presented (Dijkstra Optimal Distance Based Trajectory Outlier Detection System).5
3.10.6. The experiments were conducted on a 12th Gen i7-12700K processor with 64GB of RAM and a NVMe SSD drive, with the system running on the Ubuntu 22.04 OS.
For the experiments, the datasets were split into a 75-25% train-test ratio and converted into a grid representation. The accuracy and F1 Score are measured for each experiment and presented.
The configuration is given in the repository and is performed in such a manner that the highest accuracy is achieved. For the clustering module, the grid parameter is 40 for the Cyprus dataset and 20 for the Geolife dataset. The epsilon parameter is set to 1.5 and minPts to 5. minPts is set to 20 for PC1-Geolife, 2 for PC2/PC3-Geolife, 30 for PC1-Cyprus, 5 for PC2-Cyprus and 2 for PC3-Cyprus. For the SVM module, C is set to 8000, gamma is set to ’scale’ as per the sklearn documentation, the SVM kernel is the RBF one and the GSP support parameter is 0.05, with the grid parameter being also used if the GSP algorithm is ran and is set at 40 for the Cyprus dataset and 20 for the Geolife.
Since the DBSCAN algorithm does not have a prediction function for instances that are not included in the train set, a custom one is applied here. The training labels are obtained from the fitting process and for each test instance, its nearest neighbor in the training set is found and its class is assigned to the instance.
The main efectiveness results for both datasets are summarized in Table 2. PC1 is the Path Clustering solution 5We have also tried to adapt and apply the sub-trajectory-oriented technique in [10] using the codebase provided at https://github. com/MillerWu2014/trajectory-cluster but the results were much inferior compared to any of the techniques presented in the evaluation results section. Given also that we have not investigated sub-trajectory-oriented techniques in depth, no results from [10] are presented. with the Hausdorf distance, PC2 is the Path Clustering solution with the DTW distance, PC3 is the Path Clustering solution with the DTW-Hilbert distance and SVM is the plain SVM-based model. Wherever GSP is mentioned, it is used as a feature for the SVM solution’s input data. Finally, the SVM+GSP+PC1(LR) model is the LogReg-combined model, as described above, and the SVM+GSP+PC1(OR) is the logical OR ensemble model.
The results show that in general F1 and accuracy scores are high and our proposals can significantly improve upon existing state-of-the-art solutions. The SVM+GSP combinations yield the best results in terms of both accuracy and F1. When combined with the PC1 model and the LogReg method, the total performance does not increase for either dataset. If the logical OR is applied instead, the accuracy and F1 drop for both datasets. However, PC1 is significantly more efective than PC2 that employs the Euclidean distance, and also DTW, since trajectories are of diferent length in general. Finally, both proposed models outperform the baseline. More importantly, the improvements are larger with regards to F1, which is more suitable for an outlier detection problem.
Our solutions improve F1 by up to 21.26% and 27.31% for the Geolife and the Cyprus datasets, respectively. The corresponding accuracy improvements are 5.7% and 9.6%.
For all models, the execution times (including both iftting and predicting) are mentioned in Table 3. By examining this table, it can be observed that the TOP model is the fastest solution overall, while DODB is a computationally expensive model due to the calculation of optimal distances (i.e., it does make sense for performance reasons to resort to the implementation in [4]). From the proposed models, the DTW-based Path Clustering ones are also very slow, which implies that the DTW distance is significantly more expensive to calculate than the Hausdorf one. Regarding the SVM-based models, they are reasonably fast and the addition of GSP increases the execution time. Finally, in the proposed models, the Geolife dataset takes more time than the Cyprus one, because it has longer trajectories in terms of points and thus calculations that use the point sequences (i.e., grid conversion and distance calculation) are more expensive. On the other hand, TOP is slower for the Cyprus dataset, mainly due to the fact that the same number of trajectories refer to a smaller overall surface in square kilometers.
Since the DTW distance proved to be costly to calculate and in our last experiment (to be discussed below), it has its merits, we applied the following simplification to speed-up its processing. More specifically, the trajectories whose grid square representation exceeds a limit are sampled in a way that we keep points as equidistant as possible, including the first and last ones. For example, in a trajectory originally spanning 20 cells with =6 sampling points, the trajectory points with indices [0, 4, 8, 11, 15, 19] are the ones chosen in the sample. In our implementation, to configure , the average length of the grid-converted trajectories is calculated, the ceiling function is applied to it and the result is incremented by 1. Any trajectory larger than that is sampled in the way mentioned above. All the accuracy results for DTWbased techniques presented follow this simplification.
In our final experiment, with a view to determining the proposed models’ performance in known outliers, 22 manually created outliers by domain experts were added in the Cyprus dataset and the percentage of them accurately getting labeled as outliers is measured. The data matrix used for the SVM model building (without the GSP column) is used to fit a -Means clustering model. This is performed in order to find meaningful clusters in the data and be capable of explaining them. With =6, the silhouette score is maximized and interesting patterns are revealed. The six clusters that appear are the ones in Figure 1 and they correspond to the 5 administrative regions of Cyprus plus some trajectories among the regions (and especially the cities) of Nicosia, Limassol and then evaluated on detecting the manual outliers using the same setting as in the experiment that yielded Table 2. The results are shown in Table 4. PC1 is the lowestperforming model, with a 68% detection rate, while SVM, SVM+GSP and PC1+SG(LR) have a 77% detection rate, PC3 has 77%, PC2 has 82% and PC1+SG(OR) has the highest detection rate, 86.4%. Interestingly, there is a single outlier case in the second row that only PC1 and PC1+SG(OR) managed to detect. All models face dificulties in detecting very short trajectories as outliers, while Figure 2: The manually added outliers: trajectories that con- most of them correctly detect the very long ones as outnect regions that are usually not connected, very long trajecto- liers. Finally, most of them perform almost perfectly on ries in a certain cluster and very short trajectories in a certain detecting infrequent trips between administrative region cluster (that they may not be easily visible in the chart). centers as outliers.
Overall, our remarks are summarized as follows. In the generic case, where there outliers are a small proportion Larnaca. This conforms to the domain knowledge that of the whole dataset at the level of 5%, SVM along with most trajectories happen from warehouses in the urban GSP performs better and significantly improves upon centers to dropping locations inside or near the city, with the competitors. When tested using very few artificially some also connecting diferent warehouses in diferent generated and manually injected outliers, using an encities. semble in which SVM with GSP is paired with Hausdorf
Based on the aforementioned understanding of the distance-enabled path clustering is the dominant soludataset, outlying trajectories are injected manually. tion. This supports our main observation that, in general, These trajectories are significantly diferent than the the Hausdorf distance is preferable in path clustering. norm. For example, some of them start from an urban cen- Finally, in absolute values, the achieved F1-scores are ter and go to another urban center that does not usually high and reach 0.8741, whereas [9] achieved up to 0.7042. interconnect with the former. Others have a generally very long distance and, finally, others may run between 5. Conclusion and Further frequently connected cities but are too lengthy since they take too many detours through rural areas. The 22 tra- Research jectories that are used for this experiment are plotted in Figure 2. In this paper, two methods are proposed, a path clustering
The proposed solutions along with their variants are method and a SVM+GSP method. The former performs DBSCAN clustering on the trajectories by using their New York, NY, USA, 2012, p. 157–162. URL: https: Hausdorf distance, DTW distance and DTW-Hilbert dis- //doi.org/10.1145/2346496.2346521. doi:10.1145/ tance, while the latter fits a SVM classifier on a 2-class 2346496.2346521. dataset by using as features the starting and destination [5] X. Zhou, Y. Ding, F. Peng, Q. Luo, L. Ni, Decoordinates, the distance of the trajectory and the devia- tecting unmetered taxi rides from trajectory data, tion from the closest frequent subsequence. The last fea- 2017, pp. 530–535. doi:10.1109/BigData.2017. ture is calculated by applying the GSP algorithm to find 8257968. the top frequent sub-trajectories and using the Hausdorf [6] I. Varlamis, K. Tserpes, M. Etemad, A. S. Júnior, distance as well. The results show that both methods out- S. Matwin, A network abstraction of multiperform the baseline and detect outliers eficiently, with vessel trajectory data for detecting anomalies., in: SVM+GSP performing better than path clustering both in EDBT/ICDT Workshops, volume 2019, 2019. terms of accuracy/F1 and execution time. However, when [7] J.-G. Lee, J. Han, X. Li, Trajectory outlier detection: the outputs of the 2 models are combined with a logistic A partition-and-detect framework, 2008, pp. 140– regression layer, the performance of the classification 149. doi:10.1109/ICDE.2008.4497422. does not improve. When an ensemble combining the two [8] Z. Li, J. Han, M. Ji, L. Tang, Y. Yu, B. Ding, J.-G. Lee, proposals using a logical OR is applied, the performance R. Kays, Movemine: Mining moving object data for drops in the case of the datasets with 5% outliers but is discovery of animal movement patterns, ACM TIST the the highest one in terms of detecting the rare manu- 2 (2011) 37. doi:10.1145/1989734.1989741. ally injected outliers. All our code has become publicly [9] L. Cao, Y. Yan, S. Madden, E. Rundensteiner, available. M. Gopalsamy, Eficient discovery of sequence out
The proposed methods have space and time limitations, lier patterns, Proc. of VLDB 12 (2019) 920–932. being quadratic for both aspects. Thus, it would be of doi:10.14778/3324301.3324308. interest to study more scalable solutions with a view to [10] J.-G. Lee, J. Han, K.-Y. Whang, Trajectory clustering: rendering the solutions suitable for real-time processing. a partition-and-group framework, in: Proceedings Finally, the application of the temporal dimension in the of the 2007 ACM SIGMOD international conference proposed method, along with derived features such as on Management of data, 2007, pp. 593–604. velocities, accelerations and so on, would be beneficial [11] E. O. Eldawy, H. M. Mokhtar, Clusteringand we plan to explore it in the future. based trajectory outlier detection, International Journal of Advanced Computer Science and Applications 11 (2020). URL: Acknowledgments http://dx.doi.org/10.14569/IJACSA.2020.0110520. The research is funded by Research Promotion Founda- [12] dZo.iL:1v0,.J1.4X5u6,9P/.IZJhAaCoS,AG.2.0L2iu0,.L0.11Z0h5a2o,0.X. Zhou, tion under Restart Research 2016-2020 Programme under Outlier trajectory detection: A trajectory analytthe ENTERPRISES/0521/0138 agreement. ics based approach, in: International Conference on Database Systems for Advanced Applications, References Springer, 2017, pp. 231–246.
[13] I. San Román, I. Martín de Diego, C. Conde, E. Ca[1] Y. Djenouri, A. Belhadi, J. C.-W. Lin, D. Djenouri, bello, Outlier trajectory detection through a A. Cano, A survey on urban trafic anomalies detec- context-aware distance, Pattern Analysis and Aption algorithms, IEEE Access 7 (2019) 12192–12205. plications 22 (2019) 831–839. [2] X. Kong, X. Song, F. Xia, H.-Y. Guo, J. Wang, A. M. [14] D. Kumar, M. Palaniswami, S. Rajasegarar, C. Leckie, Tolba, Lotad: long-term trafic anomaly detection J. Bezdek, T. Havens, Clusivat: A mixed vibased on crowdsourced bus trajectory data, World sual/numerical clustering algorithm for big data, Wide Web 21 (2017) 825–847. 2013, pp. 112–117. doi:10.1109/BigData.2013. [3] Y. Djenouri, A. Belhadi, J. C.-W. Lin, A. Cano, 6691561.
Adapted k-nearest neighbors for detecting anoma- [15] D. Kumar, J. Bezdek, S. Rajasegarar, C. Leckie, lies on spatio–temporal trafic flow, IEEE Access 7 M. Palaniswami, A visual-numeric approach to (2019) 10015–10027. doi:10.1109/ACCESS.2019. clustering and anomaly detection for trajectory 2891933. data, The Visual Computer 33 (2017). doi:10.1007/ [4] J. Zhang, Smarter outlier detection and deeper un- s00371-015-1192-x.
derstanding of large-scale taxi trip records: A case [16] J. Zhu, W. Jiang, A. Liu, G. Liu, L. Zhao, Timestudy of nyc, in: Proceedings of the ACM SIGKDD dependent popular routes based trajectory outlier International Workshop on Urban Computing, Urb- detection, in: International Conference on Web Comp ’12, Association for Computing Machinery, Information Systems Engineering, Springer, 2015, pp. 16–30. doi:10.14778/3523210.3523225. [17] J. Zhu, W. Jiang, A. Liu, G. Liu, L. Zhao, Efective [30] Z. Li, M. Ji, J.-G. Lee, L.-A. Tang, Y. Yu, J. Han, and eficient trajectory outlier detection based on R. Kays, Movemine: Mining moving object time-dependent popular route, World Wide Web databases, in: Proceedings of the 2010 ACM SIG20 (2017) 111–134. MOD International Conference on Management of [18] P.-R. Lei, A framework for anomaly detection in data, 2010, pp. 1203–1206.
maritime trajectory behavior, Knowledge and In- [31] F. Wu, T. K. H. Lei, Z. Li, J. Han, Movemine 2.0: formation Systems 47 (2016) 189–214. Mining object relationships from movement data, [19] J. Lan, C. Long, R. C.-W. Wong, Y. Chen, Y. Fu, Proceedings of the VLDB Endowment 7 (2014) 1613– D. Guo, S. Liu, Y. Ge, Y. Zhou, J. Li, A new frame- 1616. work for trafic anomaly detection, in: Proceed- [32] O. S. Siordia, I. M. de Diego, C. Conde, E. Cabello, ings of the 2014 SIAM International Conference on Section-wise similarities for clustering and outDATA MINING, SIAM, 2014, pp. 875–883. lier detection of subjective sequential data, in: [20] W. Liu, Y. Zheng, S. Chawla, J. Yuan, X. Xing, M. Pelillo, E. R. Hancock (Eds.), Similarity-Based Discovering spatio-temporal causal interactions in Pattern Recognition, Springer Berlin Heidelberg, trafic data streams, 2011, pp. 1010–1018. doi: 10. Berlin, Heidelberg, 2011, pp. 61–76. 1145/2020408.2020571. [33] R. Srikant, R. Agrawal, Mining sequential patterns: [21] B. Lei, D. Mingchao, A distance-based trajectory Generalizations and performance improvements, outlier detection method on maritime trafic data, in: International conference on extending database in: 2018 4th International Conference on Control, technology, Springer, 1996, pp. 1–17. Automation and Robotics (ICCAR), 2018, pp. 340– [34] D. Sankof, J. B. Kruskal (Eds.), Time Warps, String 343. doi:10.1109/ICCAR.2018.8384697. Edits, and Macromolecules: The Theory and Prac[22] Z. Liu, D. Pi, J. Jiang, Density-based trajectory tice of Sequence Comparison, Addison-Wesley, outlier detection algorithm, Journal of Systems 1983.
Engineering and Electronics 24 (2013) 335–340. [35] Y. Zheng, Q. Li, Y. Chen, X. Xie, W.-Y. Ma, Undoi:10.1109/JSEE.2013.00042. derstanding mobility based on gps data, in: Pro[23] F. Luan, Y. Zhang, K. Cao, Q. Li, Based local den- ceedings of the 10th international conference on sity trajectory outlier detection with partition-and- Ubiquitous computing, 2008, pp. 312–321. detect framework, in: 2017 13th International Con- [36] Y. Zheng, X. Xie, W.-Y. Ma, et al., Geolife: A colference on Natural Computation, Fuzzy Systems laborative social networking service among user, and Knowledge Discovery (ICNC-FSKD), 2017, pp. location and trajectory., IEEE Data Eng. Bull. 33 1708–1714. doi:10.1109/FSKD.2017.8393023. (2010) 32–39. [24] Y. Yu, L. Cao, E. Rundensteiner, Q. Wang, Outlier de- [37] Y. Zheng, L. Zhang, X. Xie, W.-Y. Ma, Mining intection over massive-scale trajectory streams, ACM teresting locations and travel sequences from gps Transactions on Database Systems 42 (2017) 1–33. trajectories, in: Proceedings of the 18th Internadoi:10.1145/3013527. tional Conference on World Wide Web, WWW ’09, [25] Y. Djenouri, A. Zimek, M. Chiarandini, Outlier Association for Computing Machinery, New York, detection in urban trafic flow distributions, 2018, NY, USA, 2009, p. 791–800. URL: https://doi.org/ pp. 935–940. doi:10.1109/ICDM.2018.00114. 10.1145/1526709.1526816. doi:10.1145/1526709. [26] J. Mao, T. Wang, C. Jin, A. Zhou, Feature grouping- 1526816.
based outlier detection upon streaming trajectories, [38] H. Wu, W. Sun, B. Zheng, A fast trajectory outlier IEEE Transactions on Knowledge and Data Engi- detection approach via driving behavior modeling, neering 29 (2017) 2696–2709. doi:10.1109/TKDE. in: Proceedings of the 2017 ACM on Conference on 2017.2744619. Information and Knowledge Management, 2017, pp. [27] F. Maiorano, A. Petrosino, Granular trajectory 837–846. doi:10.1145/3132847.3132933. based anomaly detection for surveillance, in: 2016 23rd International Conference on Pattern Recognition (ICPR), IEEE, 2016, pp. 2066–2072. A. Online Resources [28] D. Zhang, N. Li, Z.-H. Zhou, C. Chen, L. Sun, S. Li, ibat: Detecting anomalous taxi trajectories from gps https://github.com/amoavinis/trajectory-outliers traces, 2011, pp. 99–108. doi:10.1145/2030112.
2030127. [29] H. Xiaolin, C. Reynold, M. Chenhao, T. Grubenmann, Deeptea: Efective and eficient online time-dependent trajectory outlier detection (2022).