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, logi...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-10-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/13/20/11122 |
| _version_ | 1797574868454080512 |
|---|---|
| author | Xiaoya An Ziming Wang Ding Wang Song Liu Cheng Jin Xinpeng Xu Jianjun Cao |
| author_facet | Xiaoya An Ziming Wang Ding Wang Song Liu Cheng Jin Xinpeng Xu Jianjun Cao |
| author_sort | Xiaoya An |
| collection | DOAJ |
| description | 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 <i>Eps</i> and the minimal points number <i>MinPts</i> within <i>Eps</i> 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. |
| first_indexed | 2024-03-10T21:29:11Z |
| format | Article |
| id | doaj.art-36627c40f560467f962acbbdea8cd080 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T21:29:11Z |
| publishDate | 2023-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-36627c40f560467f962acbbdea8cd0802023-11-19T15:28:49ZengMDPI AGApplied Sciences2076-34172023-10-0113201112210.3390/app132011122STRP-DBSCAN: A Parallel DBSCAN Algorithm Based on Spatial-Temporal Random Partitioning for Clustering Trajectory DataXiaoya An0Ziming Wang1Ding Wang2Song Liu3Cheng Jin4Xinpeng Xu5Jianjun Cao6State Key Laboratory of Geo-Information Engineering, Xi’an Research Institute of Surveying and Mapping, Xi’an 710054, ChinaSchool of Computer Science and Technology, Xi’an Jiaotong University, Xi’an 710049, ChinaSchool of Computer Science and Technology, Xi’an Jiaotong University, Xi’an 710049, ChinaSchool of Computer Science and Technology, Xi’an Jiaotong University, Xi’an 710049, ChinaState Key Laboratory of Geo-Information Engineering, Xi’an Research Institute of Surveying and Mapping, Xi’an 710054, ChinaSchool of Computer Science and Technology, Xi’an Jiaotong University, Xi’an 710049, ChinaEast-China Research Institute of Computer Technology, Shanghai 201818, ChinaTrajectory 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 <i>Eps</i> and the minimal points number <i>MinPts</i> within <i>Eps</i> 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.https://www.mdpi.com/2076-3417/13/20/11122parallel DBSCAN algorithmclustering parameters autotuningdeep reinforcement learningspatial-temporal random partitioningtrajectory data clustering |
| spellingShingle | Xiaoya An Ziming Wang Ding Wang Song Liu Cheng Jin Xinpeng Xu Jianjun Cao STRP-DBSCAN: A Parallel DBSCAN Algorithm Based on Spatial-Temporal Random Partitioning for Clustering Trajectory Data Applied Sciences parallel DBSCAN algorithm clustering parameters autotuning deep reinforcement learning spatial-temporal random partitioning trajectory data clustering |
| title | STRP-DBSCAN: A Parallel DBSCAN Algorithm Based on Spatial-Temporal Random Partitioning for Clustering Trajectory Data |
| title_full | STRP-DBSCAN: A Parallel DBSCAN Algorithm Based on Spatial-Temporal Random Partitioning for Clustering Trajectory Data |
| title_fullStr | STRP-DBSCAN: A Parallel DBSCAN Algorithm Based on Spatial-Temporal Random Partitioning for Clustering Trajectory Data |
| title_full_unstemmed | STRP-DBSCAN: A Parallel DBSCAN Algorithm Based on Spatial-Temporal Random Partitioning for Clustering Trajectory Data |
| title_short | STRP-DBSCAN: A Parallel DBSCAN Algorithm Based on Spatial-Temporal Random Partitioning for Clustering Trajectory Data |
| title_sort | strp dbscan a parallel dbscan algorithm based on spatial temporal random partitioning for clustering trajectory data |
| topic | parallel DBSCAN algorithm clustering parameters autotuning deep reinforcement learning spatial-temporal random partitioning trajectory data clustering |
| url | https://www.mdpi.com/2076-3417/13/20/11122 |
| work_keys_str_mv | AT xiaoyaan strpdbscanaparalleldbscanalgorithmbasedonspatialtemporalrandompartitioningforclusteringtrajectorydata AT zimingwang strpdbscanaparalleldbscanalgorithmbasedonspatialtemporalrandompartitioningforclusteringtrajectorydata AT dingwang strpdbscanaparalleldbscanalgorithmbasedonspatialtemporalrandompartitioningforclusteringtrajectorydata AT songliu strpdbscanaparalleldbscanalgorithmbasedonspatialtemporalrandompartitioningforclusteringtrajectorydata AT chengjin strpdbscanaparalleldbscanalgorithmbasedonspatialtemporalrandompartitioningforclusteringtrajectorydata AT xinpengxu strpdbscanaparalleldbscanalgorithmbasedonspatialtemporalrandompartitioningforclusteringtrajectorydata AT jianjuncao strpdbscanaparalleldbscanalgorithmbasedonspatialtemporalrandompartitioningforclusteringtrajectorydata |