STRP-DBSCAN: A Parallel DBSCAN Algorithm Based on Spatial-Temporal Random Partitioning for Clustering Trajectory Data

Trajectory clustering algorithms analyze the movement trajectory of the target objects to mine the potential movement trend, regularity, and behavioral patterns of the object. Therefore, the trajectory clustering algorithm has a wide range of applications in the fields of traffic flow analysis, logistics and transportation management, and crime analysis. Existing algorithms do not make good use of the temporal attributes of trajectory data, resulting in a long clustering time and low clustering accuracy of spatial-temporal trajectory data. Meanwhile, the density-based clustering algorithms represented by DBSCAN are very sensitive to the clustering parameters. The radius value Eps and the minimal points number MinPts within Eps radius, defined by the user, have a significant impact on the clustering results, and tuning these parameters is difficult. In this paper, we present STRP-DBSCAN, a parallel DBSCAN algorithm based on spatial-temporal random partitioning for clustering trajectory data. It adopts spatial-temporal random partitioning to distribute balanced computation among different computing nodes and reduce the communication overhead of the parallel clustering algorithm, thus improving the execution efficiency of the DBSCAN algorithm. We also present the PER-SAC algorithm, which uses deep reinforcement learning to combine the prioritized experience replay (PER) and the soft actor-critic (SAC) algorithm for autotuning the optimal parameters of DBSCAN. The experimental results show that STRP-DBSCAN effectively reduces the clustering time of spatial-temporal trajectory data by up to 96.2% and 31.2% compared to parallel DBSCAN and the state-of-the-art RP-DBSCAN. The PER-SAC algorithm also outperforms the state-of-the-art DBSCAN parameter tuning algorithms and improves the clustering accuracy by up to 8.8%. At the same time, the proposed algorithm obtains a higher stability of clustering accuracy.

Automated summary

Trajectory clustering algorithms are widely used in traffic flow analysis, logistics and transportation management, and crime analysis for mining the movement trends and behavioral patterns of objects. However, existing algorithms have limitations in utilizing the temporal attributes of trajectory data, resulting in low clustering accuracy and long clustering time for spatial-temporal trajectory data. In this paper, a parallel DBSCAN algorithm called STRP-DBSCAN is proposed, which adopts spatial-temporal random partitioning to reduce the clustering time and improve the execution efficiency. Furthermore, the PER-SAC algorithm is presented for autotuning the optimal parameters of DBSCAN using deep reinforcement learning, achieving higher clustering accuracy and stability.