Anomaly detection for maritime navigation based on probability density function of error of reconstruction

1 Introduction

Anomaly detection is one of the classical problems in machine learning. This problem has been defined and explored in a multitude of different contexts, such as visual data [1], audio/video files [2,3], and EEG signals [4]. The goal is to detect patterns of data that do not conform to the general trend in the data. This problem is closely related to outlier detection. Outlier removal is considered as one of the key components of data cleaning and data preprocessing [5]. One historic approach for unsupervised detection of anomalies in time series data is based on clustering methods in which anomalies are considered as samples that do not fit in the formed clusters. In this regard, there is a large pool of related literature that employ clustering algorithms such as k -means [6], density-based spatial clustering of applications with noise (DBSCAN) [7], and hierarchical clustering methods [8,9]. A multi-scale learning approach based on the clustering trajectory of data is proposed in ref. [10]. One obvious disadvantage of clustering-based approach is that, it is not directly developed and optimized for anomaly detection and depends on hyperparameter tuning. In these methods, cluster shapes and the number of clusters can directly influence the detected anomalies. Another highly applied method for unsupervised identification of anomaly samples in time series data is based on forecasting algorithms using autoregression methods such as autoregressive integrated moving average (ARIMA) [11] and seasonal auto-regressive integrated moving average [12]. These approaches pursue the idea that the data points that cannot be estimated accurately are more likely to be anomalous. One potential drawback of these methods is that they perform poorly for forecasting long trajectories and require parameter selection. There are also approaches based on linear regression modeling in which outliers are detected based on standardized residuals [13]. Bianco et al. studied outlier detection in regression models by proposing a robust estimation for ARIMA parameters [14]. In the study by Yuen and Mu [15], a robust outlier detection method is proposed based on considering the optimal regression parameters, residuals, and outlier probability calculation. This method is later extended by the same authors, where the method is improved by considering the correlation between residuals [16]. A stable real-time cleansing method was proposed by Mu et al. [17] based on Extended Kalman Filter (EKF), which can be used for abnormal data removal in real time.

In this work, we are concerned with analyzing the behavioral patterns of vessels’ trajectories in order to detect anomalous data points. Anomaly detection of maritime data is important to support safe travel and manage sea traffic [18]. More specifically, we develop a method for anomaly detection in the maritime domain using a public Automatic Identification System (AIS) dataset. AIS is a system that is developed for automatically tracking vessels and monitoring traffic over oceans. Each vessel is equipped with a transmitter that must be turned on all the time in order to broadcast AIS signals about their status to other vessels to ease navigation and prevent collisions. The AIS messages include static and dynamic information about vessel identity, position, speed, and course [19]. However, this dataset is not annotated, and there is no supervised information about the anomalous patterns. Therefore, an additional problem is the unknowability of the training and test data. Hence, in our approach, instead of categorizing data into anomalous and nonanomalous patterns, we propose a method for creating different Confidence Levels (CLs) of irregularity and introduce a formula for measuring the anomaly score. Our anomaly detection method is based on Autoencoders (AEs). A notable attribute of AEs is that they can be trained without requiring labeled data. However, one common approach to applying AEs for anomaly detection is a supervised learning strategy. In a supervised-learning approach, an AE is trained on normal data and then tested with test data. This approach is also known as a one-class classification problem [20]. The reconstruction loss is then leveraged to detect anomalous patterns. If the error of reconstruction is high for a sample, then the sample will be considered as an anomalous data. Xia et al. [21] followed this idea but only trained an AE on positive anomalous data and then analyzed the reconstruction error using a clustering mechanism. Zhou and Paffenroth [22] in their study have proposed a supervised algorithm for outlier and anomaly detection by developing a robust AE-based technique that computationally relies on Robust Principal Component Analysis (RPCA). However, all of these methods require annotated anomalous data. A number of researchers have made an attempt at softly labeling data before applying AE. For instance, Li et al. [23] first applied clustering to the data in order to estimate and collect normal data and then trained an AE on the normal data. The second approach for anomaly detection using AE benefits from the nonlinear feature space resulting from training an AE model. More specifically, AEs are capable of projecting data into a low-dimensional space with better separability features and thus provide the possibility of applying different clustering techniques to the projected data for outlier identification [24]. Here, we provide a fully unsupervised method for detecting and localizing abnormal behavior in serial data. In general, the unsupervised approach to anomaly detection relies mostly on thresholding the error. However, there is no efficient method for finding a proper cutoff value for a threshold. Often, the mean error value is leveraged as a fair threshold value. But depending on the distribution of data and the task in demand, the mean value could give rise to misleading results. To alleviate this issue, we propose a method for finding thresholds at certain CLs by estimating the distribution of the reconstruction error obtained from training an AE. The encoder–decoder architecture of this network yields an efficient data representation. The reconstruction error encompasses information about nonconformities in a series of data. Hence, the probability density of error can provide insight about the rare events in a trajectory. In this study, we identify the irregular points by computing CLs of anomaly. The rest of this article is organized as follows: Section 2 explores prior art and related work. Section 3 introduces the proposed method. In Section 4, we present the experimental results. Finally, we conclude in Section 5.

2 Related work

Anomaly detection and outlier identification are two closely related problems. In general, outlier detection is considered a preprocessing stage for data cleansing and noise removal [25], whereas anomaly detection is regarded as a technique for finding unexpected and abnormal behavior. Anomaly detection is correlated with salient pattern detection, i.e., localizing and identifying the sources of nonconformity and conspicuous patterns. The primary goal is to detect rare and unexpected patterns. Anomaly detection has a broad range of applications in various domains. These applications include fraud detection [26], fault detection [27], theft detection [28], intrusion detection [29], and abuse detection [30]. In this work, our focus is on detecting anomalous behavior from maritime vessel navigation. However, there are various anomalous situations that can occur in the maritime environment. Port arrival time [31], entering restricted zones [32], close proximity between vessels [33], route deviation [34], AIS off-on switching [35], and silent period in message transmission [35] are the most studied problems. Our work can be categorized as a route deviation method since we look at the behavior of vessels of the same type. Maritime anomaly detection has been investigated as maritime situational awareness using machine learning models based on feature engineering for a long time. To this end, various classification and clustering methods are proposed. Zhen et al. first clustered the normal trajectories and then measured the posterior probability of assigning a new trajectory into one of the clusters using the Bayesian rule [36]. Another Bayesian-based approach is proposed by Mascaro et al. using Bayesian network learners [37]. Support Vector Machine (SVM) has also been applied for transforming data into a high-dimensional feature space and grouping data behavior into normal and abnormal classes [38]. In the study by De Vries and Van Someren [39], trajectories are first compressed, then a one-class SVM model is applied. Unsupervised learning based on grouping- or clustering-based anomaly detection is another category of traditional approaches that have been widely investigated. Murray and Perera, in their study [40], applied a Gaussian Mixture Model (GMM) to cluster data and exploited the trace of covariance matrices to threshold them in order to identify anomalous clusters. The Self-Organizing Map (SOM) is another classical technique that has been applied to model clusters of normal and anomalous points [41]. A spline-based trajectory clustering approach is presented for detecting anomalous events in a coastal surveillance scenario [42]. The Gaussian Process (GP) has been exploited for anomaly detection by predicting vessel positions [43]. As a matter of fact, finding abnormal patterns in time series data is challenging because of the conditional dependency between subsequent time points. In addition, due to various weather conditions and unpredictability and complexity of maritime navigation, marine vessels do not follow a predefined road map, and the pattern of movements of similar vessel types varies greatly. Thus, it is very difficult to apply traditional similarity-based and regular data mining algorithms [44] to vessel movements to analyze their activities, and thus, traditional machine learning algorithms are not capable of finding efficient answers. Therefore, many researchers have applied Deep Neural Networks (DNNs) to vessel trajectories for handling different problems, such as vessel trajectory prediction [45,46], collision avoidance [47], movement or trajectory classification [48,49] and traffic prediction [50]. In the context of anomaly detection, DNNs such as Recurrent Neural Network (RNN) [51], Long-Short-Term Memory (LSTM) [52], and AEs [53] have been adopted and applied by several research groups. There are also a few attempts for combining different methods. For instance, in the study by Zhao and Shi [51], an RNN with an LSTM unit is trained on the clustered trajectories using the DBSCAN method. An anomaly detector is proposed in the study by Nguyen et al. [54], which exploits variational RNN architecture to build the normal representation of movement patterns and then applies the geo-spatial information of AIS messages to find abnormal data. A behavior-based anomaly detection approach is also proposed in the study by Blauwkamp et al. [55], where images of the trajectory of vessel movements are created and then used for training a DNN. Nevertheless, there are still limited research on applying deep learning methods to a time series of AIS messages. Essentially, two types of anomaly detection can be considered: (1) contextual anomaly detection and (2) behavioral anomaly detection. Contextual anomaly detection is about anomalous data that depend on time [56]. In this regard, the same pattern can be determined as anomalous at one particular time and nonanomalous at another time based on the context, which is usually provided by meta data. In contrast, behavioral anomaly detection is totally dependent on the geometric and kinematic behavior of trajectories, regardless of the time of occurrence. This problem can be assumed as temporal anomaly detection as the objective is to find the time that the typical pattern of the sequence changes. In contrast to some of the domains in which the time series data can be categorized into known stages [57], the trajectory patterns of movement of vessels in the maritime environment are largely unpredictable, which leads to a lack of annotated data in this domain. In essence, the anomalous patterns of vessel movements are diverse and variable and do not generally represent a well-defined signature. Hence, in this domain, the anomalous behavior can be grounded on changes in the movement patterns of each vessel, or they can be decided in a collective manner depending on the trajectories taken by other similar samples from the same vessel-type category [58]. As aforementioned, another challenge in regard to the task of anomaly detection in the maritime domain is related to the lack of labeled public datasets. While it is very intuitive for humans to identify anomalies, solving this problem with machine learning techniques relies on a trained model with an effective feature representation that can distinguish anomalous data points. In order to accomplish this purpose, a common approach is to train a model on an annotated dataset for learning the distinction between groups of regular and irregular data, and therefore, typically, anomaly detection problem has been addressed in a supervised setting. However, labeling sequence data for the task of anomaly detection is an expensive manual task. Not only does it take a huge human effort to annotate each time step in a long data sequence, but it is also not feasible due to different anomalous scenarios in the maritime environment. One issue with anomaly annotation deals with the abundance of unknown and undefined anomalous events. Therefore, there is no annotated AIS dataset for anomaly identification that is publicly available for research. Consequently, machine learning researchers have endeavored to attack AIS anomaly detection in a semi-supervised and unsupervised fashion. The semi-supervised approach rests on the assumption that normal data are known and available [59]. Hence, even though it requires less annotated data, it still relies on labeled normal data. Rhodes et al. proposed a method to measure vessel route deviation according to Hebbian learning [60]. This technique requires a large history of trajectories to accurately predict anomalous data. The aforementioned methods suffer from requiring labeled data or using a feature engineering mechanism for modeling the data. This article uses an unsupervised technique based on deep learning to overcome these issues.

3 Method

As mentioned earlier, our method is based on an unsupervised feature learning procedure by training AE models. In this procedure, unlabeled data x is first compressed into a low-dimensional feature representation h . Then, the input data are reconstructed into x ′ by decompressing the hidden representation and mapping it to its original dimensional space. The reconstruction error ∣ x − x ′ ∣ is the loss value for training the network, which needs to be minimized. Here, we train an AE on the AIS dataset and exploit the Speed Over Ground (SOG) feature. This feature consists of sequential information about the speed of vessels at each time step. The sequence of SOG is then divided uniformly into fixed-sized segments and treated as a sample. In mathematical terms, having a sequence data s = x 1 , … , x n , we divide it into equal sequences of size m and treat each segment as a sample. We then train a convolutional AE in a fully unsupervised setting. Following the study by Xia et al. [21], we treat the reconstruction error as a signal for anomaly detection. We expect to obtain a lower error for the sequences that are less likely to comply with the frequent patterns. In contrast to previous methods, we use the Probability Density Function (PDF) of error for localizing the anomalous behavior in the time series of movement data.

4 Experimental results

For all the experiments, we used the AIS dataset for 2020, which is publicly available for download^[1]. This dataset contains both static and dynamic attributes about vessels’ identity, location, and movement [65]. The dynamic attributes include latitude, longitude, SOG and course over ground features. For the purpose of this research, we focus on the SOG dimension. This feature contains the footprint about speed of vessels at each time-step and therefore encompasses movement patterns. We rely on this feature for the anomaly analysis of vessels’ movement. We collect maritime trajectories of all tankers corresponding to vessel IDs 80–89. We first normalize the dataset and process it to eliminate unknown values. The size of trajectory for each vessel is not equal, and therefore, in order to feed the data into the network, we segment each trajectory into segments of equal length. Data are then divided into training and test sets with a split ratio of 80:20, and all trajectories with length less than 10,000 are removed. We developed an AE with four hidden layers. For the architecture of the AE model, we used a simple structure consisting of two convolutional layers in the encoder and two transposed convolutional layers in the decoder. The number of nodes in each layer is 32, 16, 32, and 16, respectively. Kernel sizes are 7 and ReLU activation functions are applied to the output of convolution layers. DNN training includes several hyperparameters that control the learning and training process. Adjusting the values of these hyperparameters can lead to an increases in the performance of the trained models. However, there is no analytical method for hyperparameter configuration. Hyperparameter optimization is an approach to search for the best values in the entire space of feasible values. In this research, we do not focus on optimizing these values, and hence, hyperparameter tuning for training deep network is performed in a linear search fashion. For learning rate, we tried the values in the range of [0.1, 1 0 − 6 ] with a step size of 0.1 and chose 0.001. For batch size, the values within the set 64,128,256 are tried, and finally, batch size of 128 is used for training all the networks. We also checked Adam and RMSProp and opted for Adam. We trained three AEs that are similar in structure but different in segment sizes. Mean absolute error (MAE) is used as the loss function for training the deep network. The idea of anomaly detection based on the error of AE is depicted in Figure 1. As can be understood, the anomalous patterns generate higher error values. The learning curves that include training and validation loss values over the course of learning are shown in Figure 2. We then estimate the density of error. As previously mentioned, a histogram cannot provide a smooth and accurate estimation. Hence, KDE with three different kernels, i.e., Gaussian, Epanechnikov, and Tophat kernels, is modeled and fitted to the error as shown in Figure 3. After applying KDE, the threshold values are calculated for four different CLs. The CLs for the KDEs are obtained based on the idea of percentile and are exactly computed based on the distribution of data. Four levels of thresholds are marked in each distribution. For histogram, threshold levels can be selected based on bin size, which need to be manually decided, whereas in our approach for KDE distributions, the thresholds are computed based on their CLs. Figure 4(a) and (b) presents the estimated distribution of error by histogram and KDE methods based on the idea of anomaly CLs. The dotted line specifies the cutoff value. All samples on the right side of this line correspond to anomaly, whereas the samples on the left side are normal samples. The impact of each CL on the original error signal is indicated in Figure 5. As can be observed, the higher the level of confidence, the lower the number of anomalous patterns that can be captured. The anomaly score that links the error value with an anomaly degree in a continuous manner is presented in Figure 6. These scores are specified with dashed lines and compared for different PDF estimations, as explained in previous sections. As mentioned before, AIS dataset does not include labels for anomaly detection problem. Therefore, in order to assess the performance of our algorithm quantitatively, we create pseudo labels for the dataset. For this purpose, we make time series stationary by utilizing the difference mechanism [66]. Then, we convert each time series into a binary vector by employing a cutoff value. This value serves as an approximate estimation of aberrant fluctuations in data and is arbitrarily chosen as 0.1 in our experiments. We have also tried two other values of 0.1 and 0.2 in our implementation and did not find a significant effect on the results. Our approach is not dependent on this value, and it is only used for the sake of numerical evaluation. Figure 7 demonstrates the predicted labels at different levels of confidence according to the pseudo labels, which are shown in Figure 8. As evident from the results, the number of correct anomalous points increases when we try a lower CL.

Figure 1

Anomaly detection with AEs.

Figure 2

Learning curves for three trained AEs.

Figure 3

Kernels for density estimation: (a) Epanechnikov kernel, (b) Gaussian kernel, and (c) Tophat kernel.

Figure 4

Anomaly CLs computation on distribution of error. The dashed lines indicate threshold levels. Each line divides samples into anomalous (on the right-hand side) and nonanomalous (on the left-hand side) samples. (a) Histogram and (b) KDE.

Figure 5

Impact of anomaly CLs on a sample trajectory. (a) Histogram and (b) KDE.

Figure 6

Anomaly score. The dashed graph are corresponding to the anomaly score functions.

Figure 7

Predicted labels. The signal is shown in dark blue and the pseudo labels are specified with light blue.

Figure 8

Pseudo labels. The signal is shown in blue and the pseudo labels created with cutoff value of 0.1 are specified with yellow.

We exploited six metrics, i.e., accuracy, sensitivity, specificity, precision, recall, and f1-measure, for evaluating the results. In fact, sensitivity and recall are the same criterion. Since we did not observe a significant difference with different kernel methods and the results for all three kernels are very similar, we only provide the performance obtained from the Gaussian kernel. Figure 9 outlines the evaluated results on test trajectories in bar charts. We show the results obtained from four CLs evaluated by pseudo labels with a threshold of 0.1 for three segment sizes of 20, 100, and 300. For the sake of comparison, Tables 1 and 2 provide the numerical values organized in two measurement sets. All the measurements are compared with baseline in which the differentiation threshold between anomalous and normal points is considered according to mean error. In addition, we provide the results for three different pseudo labels at threshold values of 0.1, 0.2, and 0.3. As depicted in Figure 10, the parameter of pseudo label creation does not affect the performance of our method significantly. A minor impact is observable on specificity metric, which is related to true negative rate. Nevertheless, true positive samples or true anomalies have been detected at high rates in all three cases. As expected, it is remarkable that the detection performance is slightly better when using pseudo labels with higher thresholds, which correspond to easier tasks. However, as we increase the threshold gap for creating pseudo labels, the anomaly detection task becomes easier and the precision improves. The results indicate that the highest sensitivity (or recall) and accuracy are achieved at the highest anomaly CL. Sensitivity is representative of true detected anomalies, and it drops as we decrease the anomaly CL. This is due to the fact that with a lower CL, the number of correctly classified samples decreases. Likewise, accuracy and precision have the top values within the highest amount of CL. On the other hand, we observe that, under the same condition, specificity, which represents the true negative rate, goes up. This suggests that the likelihood of correctly identifying normal patterns increases when a higher degree of freedom for irregularity is applied. More importantly, precision is not affected by the level of confidence, which suggests that the number of correctly detected anomalies against wrongly detected anomalies remains high at all CLs. In anomaly detection methods, two issues of masking and swamping can arise [67]. The masking effect occurs when an outlier prevents the identification of other outliers and produces false negative (FN), whereas swamping refers to the situation in which an outlier makes nonoutliers or normal data to be categorized as outliers and hence increases false positive (FP) cases [68]. In order to measure the effect of these situations, we have measured precision and recall. Lower values of FP and FN result in higher precision and recall. Figure 11 depicts the precision-recall curve for four CLs and four segment sizes. As can be observed, both precision and recall values are reasonably high for different segment sizes and CLs. This result suggests that the proposed method is not suffered from masking and swamping issues. Moreover, it can be inferred that lower segment sizes provide superior results. This can be due to the more accurate models that are trained on low-length sequences. For a reliable anomaly detection system, it is crucial to have high sensitivity and precision. In other words, these measurements reflect the correctly identified true positives, which are true anomalies in our case. Therefore, in order to guarantee the best identification of true anomalies, we can focus on the results from higher CLs (i.e., the ones above 90% CL). In contrast, if the requirements tend towards thorough detection of all possible anomalies, lower levels of confidence such as 80% CL should be considered.

Figure 9

Performance measurements.

Figure 10

The effect of three different thresholds for creating pseudo labels. The pseudo label 1, pseudo label 2, and pseudo label 3 are corresponding to thresholds of 0.1, 0.2, and 0.3, respectively. Performance measurements for segment sizes of (a) 300, (b) 100, and (c) 20.

Figure 11

Precision-recall curve.

5 Conclusion

Anomaly and outlier detection is one of the challenging problems in machine learning and pattern recognition due to the lack of clarity of anomaly definition in various real-world applications and the lack of sufficient data for training efficient models. In this article, we proposed an autonomous methodology for anomaly detection for time series data in a fully unsupervised fashion. Since we do not have access to the labels for the time steps at which an anomaly has taken place or information about abnormal trajectories, we detect anomalies at different levels of confidence. We proposed a thresholding mechanism by applying KDE in order to find different levels of confidence for anomaly detection based on computation of percentiles of the PDF of error. In addition, we formulated anomaly score calculation based on cumulative distribution function of error. Our method provides flexibility for users in making decisions about anomalous patterns by specifying a certain CL and can assign a particular anomaly score to each sample. This provides a degree of freedom to decision-makers to identify anomalies with different severity levels of aberration. Especially, this feature is very important in the maritime domain where, due to the complexity and unpredictability of vessels’ motions, the suspicious behavior of vessels is not easily noticeable. Hence, setting different levels of confidence and comparing the number of anomalies in each level can facilitate decisions about the alert amount that should be given to each anomalous pattern. One possible avenue of future work is concerned with multi-level thresholding, hence defining multi-level anomaly score functions that can divide a trajectory into multiple categories simultaneously. Each category can then identify a semantic segment of a trajectory that reveals a particular behavior of vessels’ movements.