Applicability Evaluation of Several Spatial Clustering Methods in Spatiotemporal Data Mining of Floating Car Trajectory

Haoxuan Chen, Fei Tao, Peilong Ma, Li-Na Gao, Tong ZhouISPRS Int. J. Geo Inf 2021 · DOI

TL;DR

This paper evaluates four common spatial clustering algorithms (KMeans, DBSCAN, CFSFDP, KDE) for their effectiveness in analyzing taxi trajectory data. It finds that DBSCAN and KDE excel at hotspot discovery and classification, while DBSCAN and CFSFDP are more accurate for pinpointing Points of Interest (POIs). The study provides a crucial guide for selecting the right tool for specific spatiotemporal data mining tasks.

What Problem Does This Paper Address?

Analyzing the vast amounts of data generated by floating car trajectories (like taxis) is essential for understanding urban dynamics, traffic patterns, and population movement. However, a significant challenge lies in choosing the most appropriate spatial clustering method for different analytical tasks. Existing research often lacks a clear, scientific basis for this selection, leading to potentially suboptimal results or inefficient processing. This paper aims to bridge this gap by systematically evaluating the performance of four prominent spatial clustering algorithms across various spatiotemporal data mining applications relevant to taxi trajectories.

Methods

The study focuses on four representative spatial clustering algorithms:

  • KMeans: A partitioning method that aims to divide data into a pre-defined number of clusters (k) by minimizing the sum of squared distances from each point to its cluster's centroid.
  • DBSCAN (Density-Based Spatial Clustering of Applications with Noise): A density-based method that groups together points that are closely packed together, marking points that lie alone in low-density regions as outliers. It can discover clusters of arbitrary shapes and handle noise.
  • CFSFDP (Clustering by Fast Search and Find of Density Peaks): A density-based clustering algorithm that identifies cluster centers based on both local density and distance to points with higher densities. It's known for its ability to find non-spherical clusters.
  • KDE (Kernel Density Estimation): A non-parametric method that estimates the probability density function of a random variable. In this context, it's used to create a smooth surface representing the density of trajectory points, effectively identifying "hotspots."

The paper's research framework involves:

  1. Data Cleaning: Removing erroneous and empty trajectory points.
  2. Algorithm Selection: Choosing the four algorithms mentioned above.
  3. Specific Problem Application: Applying the algorithms to tasks like hotspot discovery, POI extraction, and hotspot classification.
  4. Applicability Evaluation: Assessing the performance of each algorithm based on experimental results.

Datasets

The study utilizes taxi trajectory data collected from 1000 taxis in Nantong City, China, during October 2018. This dataset includes approximately 801,679 drop-off points. The data was collected every 30 seconds and contains information such as plate number, time, latitude, longitude, speed, direction, and passenger status. For verification, the study also references the Baidu city heat map.

Key Insights and Ideas

  • Noise Matters: The ability of a clustering algorithm to handle noise points significantly impacts its performance, especially with real-world, often noisy, trajectory data. Algorithms that can effectively filter noise (like DBSCAN and CFSFDP) tend to yield more robust results for tasks requiring high accuracy.
  • Shape of Clusters: Not all hotspots or POIs are perfectly spherical. DBSCAN and CFSFDP's ability to identify non-spherical clusters makes them more suitable for capturing the complex spatial distributions often found in urban environments.
  • Task-Specific Suitability: There's no one-size-fits-all algorithm. DBSCAN and KDE are strong for general hotspot discovery and classification due to their density-based nature. However, for precise POI location extraction, DBSCAN and CFSFDP show superior accuracy.
  • Trade-offs in Efficiency: While KMeans offers the best time efficiency, especially with large datasets, it sacrifices accuracy and the ability to find non-spherical clusters. Conversely, CFSFDP and KDE, while better at handling complex shapes, are significantly slower.

Key Results

  • Hotspot Discovery: DBSCAN and KDE achieved the highest accuracy (94.6% and 94.8% respectively) in identifying hotspots, outperforming KMeans (73.9%) and CFSFDP (85.3%). DBSCAN and KDE were better at capturing the density distribution of drop-off points.
  • POI Position Extraction: DBSCAN and CFSFDP demonstrated the highest accuracy in extracting POI entrance/exit positions, with average errors of 7.3m and 12.3m, respectively. KMeans and KDE showed significantly larger errors.
  • Hotspot Classification: KDE achieved the highest accuracy (86.7%) in classifying hotspot levels, followed by DBSCAN (66.7%). KMeans (60.0%) and CFSFDP (40.0%) performed poorly, with CFSFDP struggling to divide AOIs due to uneven point distribution.
  • Time Efficiency: For large datasets, KMeans and DBSCAN were the most time-efficient. CFSFDP and KDE were considerably slower, especially as the data volume increased.

Limitations and Future Work

The paper acknowledges that parameter setting can be challenging, particularly for CFSFDP, and often requires manual tuning based on experience. While the study provides a valuable comparison, it focuses on specific applications of taxi trajectory data. Future work could explore the applicability of these algorithms to other types of trajectory data (e.g., public transport, pedestrian movement) or investigate more advanced spatiotemporal clustering techniques. The authors also suggest that further research could refine the selection criteria for these algorithms, providing even clearer guidance for practitioners.

Summary updated

BibTeX
@article{chen2021applicability,
  author = {Haoxuan Chen and Fei Tao and Peilong Ma and Li-Na Gao and Tong Zhou},
  title = {{Applicability Evaluation of Several Spatial Clustering Methods in Spatiotemporal Data Mining of Floating Car Trajectory}},
  journal = {ISPRS Int. J. Geo Inf.},
  year = {2021},
  doi = {10.3390/ijgi10030161},
}
Figure