A two-stage method for detecting trajectory clusters of different densities with peak trajectories identification

Trajectory clustering is a fundamental yet challenging data mining task that aims to group similar trajectories. Due to the inherent nature and implicit patterns of trajectories, existing methods often struggle to cluster trajectories with varying densities and noise, and automatically determine cluster numbers. We propose an adaptive two-stage trajectory cluster (ATSTC) algorithm considering the intra-cluster trajectory distance distributions. In the first stage, peak trajectories with the highest local densities, and their adaptively estimated <i>k</i>-nearest neighbors, are initialized as candidate clusters. Trajectories in multiple peak neighborhoods are assigned to clusters with minimal relative distances while remaining trajectories are merged with the nearest cluster or labeled as noise depending on the resultant changes in intra-cluster distance standard deviation. In the second stage, a hierarchical agglomerative strategy is employed to merge clusters by analyzing changes in the average distance and standard deviation of intra-cluster trajectories before and after merging. Experiments on four simulated datasets, with comparisons to eight baselines, demonstrate the superior performance (e.g. ARI) of ATSTC in detecting trajectory clusters under different scenarios. Case studies involving route extraction from ship trajectories and bird tracks with clusters of different sizes, densities, and noise underscore the potential and efficacy of ATSTC in real-world applications.