STCAD: Scalable Trajectory Clustering and Anomaly Detection on Terabyte-Scale AIS Data

STCAD: Scalable Trajectory Clustering and Anomaly Detection on Terabyte-Scale AIS Data

This paper presents STCAD, a scalable unsupervised framework for clustering maritime trajectories and detecting anomalies in terabyte-scale Automatic Identification System (AIS) data. The framework combines a self-supervised BERT-style Transformer encoder trained via masked token modeling with the CURE hierarchical clustering algorithm, supported by a preprocessing pipeline that enables year-scale analysis of billions of AIS messages.

The study uses a national-scale AIS dataset from the Danish Maritime Authority covering Danish waters for the entire 2024 calendar year, comprising approximately 6.89 billion messages totaling 1.2 TB of raw data. Each observation includes MMSI vessel identifier, latitude, longitude, Speed over Ground (SOG), and Course over Ground (COG). The dataset contains 38,026 unique vessels, including 19,597 sailing or pleasure crafts, 8,627 cargo or tanker vessels, 1,632 fishing vessels, and 8,170 other or undefined categories.

Data preprocessing occurred in two phases. First, global filters removed erroneous messages outside the geographical region of Denmark (lat ∈ [54, 59], lon ∈ [5, 17]) and messages with unrealistic values (SOG > 30 knots or COG outside [0, 360]), resulting in 5,383,009,610 messages. The per-vessel phase defined voyages as contiguous trajectories with intervals between consecutive messages less than 2 hours, split voyages exceeding 20 hours, discarded voyages shorter than 4 hours or with fewer than 20 messages, removed messages with empirical speed exceeding 40 knots, applied linear interpolation for regular 5-minute sampling, and performed min-max normalization. Using 64 CPU cores with 128 threads, processing time was reduced from an estimated sequential runtime of 170 hours to 80 minutes. The preprocessing reduced the dataset from 1,342,406 initial trajectories to 453,712 final voyages.

For sequence encoding, variable-length trajectories are transformed into fixed-dimensional embeddings using a Transformer with four encoder layers, four attention heads per layer, and a hidden size of 256. A classification token ([CLS]) is prepended to each sequence, and its final hidden state serves as the trajectory embedding. Each AIS message is represented by [lat, lon, SOG, COG] ∈ R4, projected into the model hidden space via a linear mapping f: R4 → R256, with positional encodings added. Training uses masked token modeling with 15% masking probability and dropout of 0.1. The model was trained on 80% of the preprocessed dataset, reaching a stable validation MSE loss of 0.0044 after 17 epochs on an A100 Nvidia GPU with batch size 512 and the Adam optimizer with learning rate 5·10−5.

For clustering, the framework employs CURE (Clustering Using REpresentatives) to address the computational prohibitive O(n3) complexity of standard agglomerative clustering. By clustering a sample (N = 1000) and assigning remaining points to the nearest representative set, CURE reduces fitting time to linear O(n) complexity. Embeddings are L2-normalized so Euclidean distance corresponds to cosine similarity. An assignment threshold labels points as noise if distance to the nearest cluster representative exceeds the threshold. Samples from the AC sample set that remain isolated after the first N·ρ merges (ρ = 0.05) are discarded to avoid including noisy points as representatives.

The UMAP visualization of the embedding space exhibits clusters with non-spherical geometries. Single linkage clustering showed pronounced chaining effects, and average linkage produced fragmented, unstable dendrograms. Agglomerative clustering with WARD linkage yielded the most coherent and stable cluster partitions. CURE hyperparameters were set with compression factor 0.6 and 20 representative points. The dendrogram indicates stable partitioning at cluster counts k ∈ 2, 3, 5, 8, with subsequent analyses conducted for k = 3 and k = 5.

At k = 3, one cluster is primarily associated with trajectories north of the Jutland Peninsula. At k = 5, two clusters are further subdivided, resulting in more spatially localized trajectory groups. Cluster characterization uses trajectory-level descriptors including mean latitude/longitude, mean speed over ground, start-to-end displacement, course variability (σCOG), and vessel type. Z-scores assess deviations in continuous features, and Pointwise Mutual Information (PMI) scores assess categorical vessel types.

The cluster descriptors reveal distinct patterns: Cluster 4 is characterized by high latitudes and low longitudes with predominance of fishing vessels; Clusters 1 and 2 are dominated by cargo vessels with high speed and displacement, corresponding to transit through the Kiel Canal and onward routing toward Danish harbors; Clusters 0 and 3 primarily consist of low-speed, low-displacement pleasure crafts spatially concentrated south of Jutland and around the island of Funen, respectively.

For anomaly detection, AC and CURE are applied with intrinsic noise detection controlled by two hyperparameters: number of clusters and assignment threshold. Trajectories classified as noise exhibit higher reconstruction error since the encoder is optimized on frequently occurring trajectory patterns. A Reconstruction Contrast Ratio (RCR) is defined as RCR = E[MSE noise] / E[MSE cluster]. An assignment threshold of 0.22 with 12 clusters is used, corresponding to 1.4% noise and an RCR of 1.5. Noise-labelled trajectories at this setting tend to exhibit high speed and are situated at lower longitudes than cluster points. Noise trajectories are twice as likely to be marked with label types other than Cargo, Fishing, Tanker, Sailing or Pleasure, with especially low representation of Sailing/Pleasure vessels, suggesting high cluster purity for recreational vessels.

The study concludes that the framework effectively models and monitors large-scale maritime traffic, producing physically interpretable clusters capturing distinct behaviors and fishing activities, with anomaly detection identifying irregular trajectories in noisy, real-world maritime data. All code used in the study is made available.

Improvements to AI Systems:

1. Self-Supervised Trajectory Representation Learning

• Implement a BERT-style masked-token Transformer encoder for sequential spatiotemporal data, enabling fixed-dimensional embeddings of variable-length trajectories without labeled data.

• The improved system can generate robust, generalizable embeddings for any trajectory-based domain (e.g., vehicle GPS, animal movement, human mobility) that capture both local motion patterns and global route semantics.

2. Scalable Hierarchical Clustering via CURE

• Replace O(n3) agglomerative clustering with CURE’s representative-based approach, reducing fitting complexity to O(n) after sampling.

• The improved system can cluster billions of data points (terabyte-scale) on commodity hardware, enabling real-time or near-real-time pattern discovery in streaming trajectory data.

3. Hybrid Noise Detection via Reconstruction Contrast

• Combine clustering-based noise labels (assignment threshold) with reconstruction error from the masked-token autoencoder to compute a Reconstruction Contrast Ratio (RCR).

• The improved system can automatically flag anomalies with higher precision by leveraging both geometric isolation (clustering) and semantic deviation (reconstruction loss), reducing false positives in noisy real-world data.

4. Two-Phase Preprocessing for Massive Datasets

• Apply global filters (geographic bounds, physical plausibility) followed by per-vessel voyage segmentation (time gaps, duration limits, interpolation, normalization) with parallel CPU execution.

• The improved system can process 1.2 TB of raw data in 80 minutes (vs. 170 hours sequential), enabling year-scale analysis of national or global sensor networks (e.g., AIS, ADS-B, IoT telemetry).

5. Interpretable Cluster Characterization

• Use trajectory-level descriptors (mean position, speed, displacement, course variability) and categorical vessel-type PMI scores to automatically label clusters.

• The improved system can generate human-readable summaries of discovered traffic patterns (e.g., fishing activity in high-latitude zones, cargo transit via canal routes), facilitating domain-expert validation and decision-making.

6. Adaptive Hyperparameter Selection via Dendrogram Stability

• Analyze dendrogram stability across cluster counts (k ∈ 2,3,5,8) to select optimal k without ground truth.

• The improved system can autonomously determine the number of clusters in unseen datasets, avoiding manual tuning and improving generalization to new geographic regions or data types.

7. Unified Framework for Monitoring and Alerting

• Integrate the trained encoder, clustering, and noise detection into a single pipeline for continuous ingestion.

• The improved system can operate as an automated maritime traffic monitor, detecting irregular behaviors (e.g., speeding, off-route vessels, unusual fishing patterns) in real time and triggering alerts with interpretable reasons (e.g., vessel deviates from known cargo routes with high reconstruction error).

8. Transferable Pre-trained Models

• The Transformer encoder trained on 5.38 billion AIS messages can be fine-tuned for other spatiotemporal tasks (e.g., destination prediction, route forecasting, collision risk assessment).

• The improved system can leverage this pre-trained backbone to achieve high accuracy with minimal labeled data in downstream maritime or mobility applications.