In recent years, electronic tracking has provided voluminous data on vessel movements, leading researchers to try various data mining techniques to nd patterns and, especially, deviations from patterns, i.e., for anomaly detection. Here we tackle anomaly detection with Bayesian Networks, learning them from real world Automated Identi cation System (AIS) data, and from supplementary data, producing both dynamic and static Bayesian network models. We nd that the learned networks are quite easy to examine and verify despite incorporating a large number of variables. Combining the mined models improves performance in a variety of cases, demonstrating that learning Bayesian Networks from track data is a promising approach to anomaly detection.
A wealth of information on vessel movements has
become available to authorities through the use of the
Automated Identi cation System (AIS). Much of this
data has even ltered through to the general public via
the Internet. Surveillance authorities are interested in
using this data to uncover threats to security, illegal
tra cking or other risks. While in the past,
surveillance has su ered from a lack of solid data, electronic
tracking has transformed the problem into one of
overabundance, leading to a need for automated analysis.
The main goal of vessel behaviour analysis is to
identify anomalies. This requires the development of a
model representing normal behaviour, with
anomalous behaviour being then identi ed by the extent of
a vessel's deviation from normality. A common
approach is to cluster the data around a set of points in
a multi-dimensional feature space, where the features
of the track are items such as longitude and latitude,
speed and course (Laxhammar, 2008). Tracks that
are within or near one of these clusters may be
considered normal, while the remainder are agged as
potential anomalies. Researchers use many di erent
machine learning techniques to generate normality
models from vessel movement data (typically AIS data),
and the models are commonly speci ed in the language
of Gaussian mixture models (Laxhammar, 2008),
support vector machines
Here, we explore the use of Bayesian Networks (BNs)
Outside of the maritime domain,
In our study here we data mined AIS data supplied by
the Australian Defence Science and Technology
Organisation (DSTO). Since many factors can contribute to
the (ab)normality of a vessel's behaviour, in this study
we also enhanced that data set by adding information
such as weather and time, as well as vessel interactions.
We used a metric BN learner, CaMML
We investigated two approaches to model learning.
First, we trained a model on the track data in its
original time series form. For variables related to motion,
we added new variables to represent the motion at
both step k and k + 1, e ectively making the data
represent a dynamic Bayesian network (DBN), which
have been used successfully for other kinds of anomaly
detection
Next we describe our approach to the main components of this study, including details of the time series and track summary methods, the variables used by the BNs and the learning algorithms. We analyse interesting aspects of the learned BNs, then present experimental results in Section 3, which demonstrate the value of Bayesian networks for anomaly detection. 2
While our basic approach is well known | applying a BN learner to produce normality models to be used in assessing degrees of anomaly | in practice the experimental work ow was complex, as shown in Figure 1. We used AIS data from May 1st to July 31st, 2009 for a section of the NSW coast framing Sydney harbour (see Figure 2). The raw data initially contained just under 9.2 million rows and each row consisted of seven elds: the vessel's MMSI (a nine digit numerical vessel identi er), a timestamp, the latitude and longitude of the vessel, and its reported speed, course and heading (see Table 1). We did not use the MMSI directly in learning, but did use it in pre-processing and to locate additional information about the vessel.
The AIS data was cleaned and separated into `tracks', rst by assigning each record to a separate track based on the MMSI. We then cleaned the data in each track by rounding (and interpolating) each row to the nearest 10 second interval and eliminating duplicate data. However, since the raw data contained many cases in which a single vessel transmits for much of the three month period of the data, further track splitting was required. We split a track record into multiple records when the vessel was stopped or not transmitting for 6 hours or more.1 This yielded 2,473 tracks across 544 unique MMSIs averaging 1,995 rows each.
Vessel track anomaly detection models have been
lim1We note, however, that since such stops may
themselves indicate an anomaly, deciding what constitutes a
track warrants future investigation.
ited to kinematic variables, such as location, speed and
course, coupled with the type of the vessel
We investigated two kinds of model based on two different forms of the training data. The rst, the time series model, uses the data in its original time series form. Each timestep in a track was associated with a set of variables, such as latitude, longitude, speed and so on, that have corresponding nodes in the BN. This approach, of course, has the advantage that learned models can be used in online analysis, but it may miss patterns at a broader time scale.
The second model, the track summary model, was
based on summaries of each track | e.g., identifying
for a given track the number of times the vessel stops,
the main stopping locations, etc. While track
summaries cannot be used as easily in real-time
surveillance, they can capture patterns that occur at the time
scale of the track as a whole. For example, if a
vessel heads straight out to sea, turns around at a
constant rate, then returns directly home, each timestep
in the track may appear perfectly normal to any time
series-based normality model. However, the behaviour
embodied by the track as a whole may be anomalous
and worthy of attention. The variables for each type
of model are in Figure 3
We were interested in whether the pre-processing
summarization might help us directly to identify types
of tracks and anomalies. To test this, we classi ed
the summary tracks using Snob
Discretization of variables in the data set was needed
for technical reasons: (1) the version of CaMML that
allows structural priors requires discrete data and (2)
we used Netica, which also requires discrete variables.
To perform discretization, we again used Snob to
classify each continuous variable in one dimension, with
each discovered class becoming a state. Using Snob
in this way allowed us to recover any hidden
regularities and is similar to the attribute clustering
approach taken by
In this work, we make use of the CaMML BN learner
Figure 3(a) shows an example BN produced by CaMML from the time series data, while Figure 3(b) shows an example learned from the track summary data. It is clear that few arcs in the learned networks represent intuitive direct causal relations, other than the DBN arcs (given as hard priors) and the weather variables. Many of the other variables are simultaneous properties of the vessel, which will be correlated by hidden common ancestors. For example, while we would expect a ship's speed, size and course to be related, it isn't obvious what the underlying causes might be. They may be such things as the business the vessel belongs to, the purpose of its trip or the nature of its crew and contents. Some of these hidden causes will be partly captured by the ShipType, e.g., the purpose of a trip employing a cargo ship is almost always transport. This explains why that variable is the common cause of so many others in the time series models. In the track summary network this common cause role is assumed by the `Class' variable instead. Causal discovery relying on joint sample data very often gets arc directions wrong, in the anti-causal direction, because it is dependent upon sparse information about any uncovered collisions (where two parents of a child node are not themselves directly connected) to infer all arc directions. For example, Figure 3(a) shows ShipType!Weather, for a variety of weather variables. Of course, ship type cannot a ect the weather. A plausible interpretation of this result is that weather conditions do a ect which types of ship put to sea, so, if anything, the arc directions here are reversed. The simplest and very e ective method of dealing with this problem is to introduce extra prior constraints, such as putting some weather variables into a zeroeth Tier. Exploring Bayesian networks is very easy and natural and here turned up many points of interest. In conrming the reasonableness of the time series model, we found that entering `Tug' or `Pilot Vessel' into the `ShipType' variable signi cantly increases the chance of another vessel being nearby. Cargo ships, on the other hand, travel mostly solo and tankers almost exclusively so. Ship sizes (i.e., the `ShipSize' variable) are also highly correlated with position (the `Lat' and `Lon' variables) via the `ShipType' variable, with larger vessels tending to appear in a restricted set of locations. The track summary model shows that cargo ships and tankers spend most of their time travelling straight, while tug directions are much more variable. Tugs also tend to stop in di erent locations from cargo ships, and they tend to be stopped for longer periods than cargo ships. 3.2
There is no generally accepted method for
detecting anomalies from BN models.
P (E1 = e1)
P (Em = em)
: : :
P (E)
Jensen and Nielsen use this to identify when a power
plant begins behaving abnormally. Unfortunately, this
will only catch cases where each attribute is
independently common but jointly uncommon. Here, we're
interested in any kind of joint uncommonness, even
when variables are independently uncommon, which
simply comes down to a di erence in requirements.
In other approaches
We started from the same assumption as Cansado and Soto, however we think choosing any particular threshold for deciding when tracks are anomalous would be arbitrary. In real applications a speci c threshold may present itself as most suitable, but in general we feel it is better to present the probability itself to surveillance operators, albeit in a more convenient form. Thus, for track summary data, we rst computed each track's prior probability given the normality model. Since these probabilities are usually very low (around the order of 1 10) we took the negative log (base 2) to produce an \anomaly score" (i.e., the number of bits required to describe the data, given the model). Put simply, the higher the anomaly score, the less probable the track.
For time series networks we took a similar approach,
but instead fed each timestep of the track into the
network to yield a probability estimate for that timestep.
We then took the average probability over all timesteps
to generate a negative log anomaly score. For time
series data it is possible, of course, to base anomaly
criteria upon changes in the track over time.
Calculating anomaly scores for all the tracks in our data set and plotting the distribution of the results (using a Gaussian Kernel Density Estimator [KDE]), we obtained Figure 4. These show a fair amount of diversity among anomaly scores, i.e. they do not simply clump around the lowest possible score. Note that the scores produced by the time series model are quite distinct from those of the track summary model. One likely reason is that the track summary scores are simply based on more variables, making each instance more speci c and less probable. There is a surprisingly small correlation between the two sets of scores (r =0.159; p < 0:001).2 The two models look at di erent aspects of each track, and, as we see below, reinforce each other when performing anomaly detection. 3.3
Unfortunately, we did not have any access to known
anomalous tracks nor are there any standardised or
publicly available vessel track data sets containing
anomalies (or otherwise). Nevertheless, there are
many ways to create anomalous data.
For each track in the training set, the ship type information was swapped with that of another randomly selected ship of a di erent type, leaving the track data alone. Figure 5(a) shows how this a ected the anomaly score. In most cases this false ship e ect is positive, increasing the anomaly score. The false ship e ect for the time series model is positive in around 87.2% of the cases as opposed to 69.4% of cases for the track summary model. Sometimes, however, tracks have become more probable given incorrect ship information, which itself seems anomalous! To be sure, many of the ship types are in fact quite similar (e.g., there are several sub-categories of cargo ship) so switching between these may randomly produce a more likely track. However, this does not account for all the cases. A closer look at these showed that many are highly improbable (i.e., have high anomaly scores), suggesting that either they have been mislabelled or, more intriguingly, that they do indeed behave anomalously according to their type. This suggests a new criterion for anomalousness based not merely upon the probability of the given track but on what alterations might explain the track better. This has some of the spirit of Jensen and Nielsen's con ict measure, though is clearly quite different; we leave this possibility for future exploration. Figures 5(b) and 5(c) show scatter plots of the anomaly score versus the false ship e ect. With the time series model, we can see that as the anomaly score grows, the 2Earlier iterations with cruder discretizations and more variables in common showed a stronger correlation | however, as models grew more detailed, the correlation shrank.
3
160 80 100 120 Anomaly score
(c) False ship effect for all data false ship e ect falls (r =-0.70, p 0:01). This also occurs with the track summary model, to a smaller extent (r =-0.31, p 0:01). We also created anomalous tracks by splicing random tracks together. This allowed us to test our models for their ability to detect discontinuities as well as major changes in behaviour. Speci cally, we selected 140 tracks at random and replaced their tails with those of other tracks (retaining the times and types of the original track). We spliced half of the tracks with those created by ships of a di erent type and we spliced the other half with tracks created by ships of the same type. When assessing these tracks using the track summary model, tracks forged from di erent types yield an average anomaly score of 121.3 while those forged from the same type yield an anomaly score of 115.4 (p 0:01). Both scores are signi cantly di erent from the average anomaly score for all data of 89.0. With the spliced tracks, as we expected the track summary model performed slightly better than the time series approach, because the time series model is not able to detect unusual behaviour across the whole track. Tracks put together from ships of di erent types produced an average score of 48.9 while those spliced from same types had a score of 45.6; while a small di erence, this was statistically signi cant (p < 0:01). In addition, while the higher score was signi cantly different (p < 0:01) from the average of the full data set (43.8), the lower score was not (p 0:01). Here we can see the advantage of the higher level view of the track summaries. 3.3.3
Finally, we tested models using anomalous tracks drawn with a mouse over a map, where the mouse location and speed generated the vessel location and speed respectively. Other factors were created randomly, including the time and duration, noise in the data, vessel details and maximum speed. This allowed us to compare the performance of both models across several di erent categories of anomalous behaviour, thereby shedding light on the strengths and weaknesses of each model. Anomalous behaviour in these tracks included very noisy data, close interactions with many other vessels, vessels that circle in unusual patterns, vessels travelling over land, overly short tracks in the middle of the sea and vessels behaving against their type. In all, 107 such tracks were created.
When combined with the normal track test data, and scored using the two models both independently and combined, the ROC (receiver operating characteristic) curves of Figure 6 are the result. The ROC curves demonstrate the tradeo s that can be made (if we were to settle on speci c thresholds for anomalies) between false positives and true positives; the greater
0.4 0.6
False positive rate the area under the curve (AUC), the less severe the tradeo needs to be. We can see that the track summary model (with an AUC of 0.780) performs better than the time series model (AUC 0.712). Adding the anomaly scores from the two models together (in e ect, creating a combined model with equal weight given to each individual model) performs better again (AUC 0.809). Table 3 shows the average scores each model yielded for various kinds of anomalous tracks. We can see that both models easily detected the tracks containing too many close interactions (average scores of 139.9 and 75.8, against the test averages of 90.8 and 45.7, giving Deltas of +49.1 and +30.1 for track summary and time series models, respectively). The time series model detected overly short tracks best (track summary: +4.7; time series: +17), while the track summary model substantially outperformed the time series model for tracks containing unusual stops, as would be expected (track summary: +28.3; time series: +2.9). In most cases, the track summary model outperformed the time series model. 3.3.4
We also applied our methods to the simulated data
used by
We also examined what happens when the ship type of the tracks is altered. Interestingly, the only cases in which this change created a notable negative false ship e ect (i.e., increased the probability of the track) again involved high anomaly scores. These scores were 25 and above for the track summaries and 36 and above for the time series | both much higher than the respective average scores for the anomalous tracks.4 4
We have demonstrated Bayesian Networks are a
promising tool for detecting anomalies in vessel tracks.
By using a BN learner on AIS data supplemented
by additional real world data, we produced both
dynamic and static networks, which demonstrated
distinct and complementary strengths in identifying
anomalies. Thus, we were able to improve anomaly
detection by combining their assessments. This
sug4For further details of our comparison with Johansson
& Falkman's work, see
The authors would like to thank the DSTO for supporting this work, Goran Falkman and especially Fredrik Johansson for providing access to their data and generously answering many questions about their approach, and SAAB Microwave Systems for permitting us the use of their simulated data. 90.8 102.4 101.7 95.5 119.1 139.9 126.2 122.2 103.5 135.2 113.7 126.9
Delta Laxhammar, R. (2008). Anomaly detection for sea surveillance. In The 11th Int. Conf. on Information Fusion, pp. 55{62.