Stable Trajectory Clustering: An Efficient Split and Merge Algorithm
This work addresses trajectory clustering for analyzing human, animal, and vehicle movements, but it is incremental as it builds on existing DBSCAN-based methods with a focus on stability.
The paper tackles the problem of trajectory clustering being disrupted by temporary anomalies, introducing a stable algorithm that uses mean absolute deviation to omit transient deviations, resulting in improved cluster stability and interpretability as demonstrated on real datasets.
Clustering algorithms group data points by characteristics to identify patterns. Over the past two decades, researchers have extended these methods to analyze trajectories of humans, animals, and vehicles, studying their behavior and movement across applications. This paper presents whole-trajectory clustering and sub-trajectory clustering algorithms based on DBSCAN line segment clustering, which encompasses two key events: split and merge of line segments. The events are employed by object movement history and the average Euclidean distance between line segments. In this framework, whole-trajectory clustering considers entire entities' trajectories, whereas sub-trajectory clustering employs a sliding window model to identify similar sub-trajectories. Many existing trajectory clustering algorithms respond to temporary anomalies in data by splitting trajectories, which often obscures otherwise consistent clustering patterns and leads to less reliable insights. We introduce the stable trajectory clustering algorithm, which leverages the mean absolute deviation concept to demonstrate that selective omission of transient deviations not only preserves the integrity of clusters but also improves their stability and interpretability. We run all proposed algorithms on real trajectory datasets to illustrate their effectiveness and sensitivity to parameter variations.