NS-DBSCAN: A Density-Based Clustering Algorithm in Network Space

Tianfu Wang, Chang Ren, Yun Luo, Jing TianISPRS International Journal of Geo-Information 2019 · OpenReview

TL;DR

This paper introduces NS-DBSCAN, a novel density-based clustering algorithm designed for spatial data constrained by network structures (like roads). It addresses the limitations of existing methods by providing a new way to visualize density distributions and efficiently compute network distances, leading to more accurate detection of high-density regions in complex urban environments.

What Problem Does This Paper Address?

Spatial clustering is crucial for identifying patterns in geographic data, such as hot spots for traffic accidents or disease outbreaks. While clustering algorithms for data in Euclidean space are well-developed, those for data constrained by networks (e.g., points along roads, events on transportation networks) are less mature. Analyzing network-constrained data in a planar space can lead to inaccurate conclusions. Existing network-based clustering methods often struggle with parameter sensitivity, computational efficiency, or the ability to accurately delineate clusters of arbitrary shapes in complex network topologies. This paper aims to bridge this gap by adapting the robust DBSCAN algorithm to network spaces.

Methods

The core contribution is the NS-DBSCAN algorithm, which extends the well-known DBSCAN (Density-Based Spatial Clustering of Applications with Noise) algorithm for network-constrained events. The algorithm operates in two main steps:

  1. Generating Density Ordering:
    • Local Shortest-Path Distance (LSPD) Algorithm: This is a key innovation. Instead of computing a full distance matrix (which is computationally expensive for networks), LSPD efficiently finds the shortest-path distance from a central point to its neighbors within a given radius (eps). It achieves this through a controlled expansion process on the network graph, minimizing the current distance to the central vertex (CDCV) for each node.
  2. Density Ordering Table and Graph: Using the eps-neighborhoods and densities calculated via LSPD, the algorithm constructs a density ordering table. This table is then visualized as a density ordering graph, which helps in understanding the overall density distribution and identifying potential cluster structures (hills in the graph often correspond to clusters).
  3. Forming Clusters:
    • This step is similar to the original DBSCAN. A density threshold (MinPts) is set, guided by the density ordering graph. Points with density above MinPts are considered core points, and their eps-neighbors become border points. Clusters are formed by expanding from core points and including their border points.

Datasets

The proposed NS-DBSCAN algorithm was evaluated using a real-world dataset from the Hanyang district in Wuhan, China. This dataset comprised:

  • Points of Interest (POIs): 4062 points classified into 11 categories, downloaded from Baidu Map. These POIs represent events or locations of interest.
  • Road Network: 944 road segments downloaded from OpenStreetMap.

The data underwent preprocessing to ensure it was suitable for network analysis, including deleting flyovers/tunnels, extracting road skeletons, and aligning POIs to the nearest road segments.

Key Insights and Ideas

  • Visualizing Network Density: The density ordering graph is a powerful tool. It transforms abstract network distances into an intuitive visual representation of density, making it easier to understand the spatial distribution of events and to guide parameter selection.
  • Efficient Network Distance Calculation: The LSPD algorithm is a significant improvement over computing all-pairs shortest paths. It allows for efficient neighborhood identification within a network space, making the clustering process more scalable.
  • DBSCAN's Adaptability: The paper demonstrates that the core principles of DBSCAN, particularly its ability to handle arbitrary shapes and noise, can be effectively adapted to network-constrained data with appropriate modifications to distance calculation and density estimation.
  • Parameter Guidance: The density ordering graph provides a visual cue for setting the eps and MinPts parameters, reducing the reliance on trial-and-error or domain expertise.

Key Results

The NS-DBSCAN algorithm was compared against two other methods: a classical hierarchical clustering algorithm and a network-constraint Delaunay triangulation (NC_DT) algorithm.

  • Qualitative Evaluation: NS-DBSCAN accurately detected highly populated regions in the Hanyang district, delineating them into clusters that approximated the shape of these regions. It successfully distinguished between dense and less dense areas, with less aggregated POIs being correctly identified as noise.
  • Quantitative Evaluation: Using metrics like silhouette, R-squared index, Davis-Bouldin index, and clustering scheme quality index, NS-DBSCAN generally outperformed both the hierarchical clustering and NC_DT algorithms.
  • The hierarchical algorithm was sensitive to the chosen cluster number.
  • The NC_DT algorithm tended to create a single large cluster and many small, disconnected clusters, performing poorly on this dataset.
  • Parameter Sensitivity: While NS-DBSCAN still requires eps and MinPts, the density ordering graph provides guidance, making the parameter selection process more informed and less arbitrary than in some other network clustering methods.

Limitations and Future Work

  • Parameter Sensitivity (Still Exists): Although the density ordering graph provides guidance, users may still need to experiment with different eps values to obtain the most suitable graph. The paper suggests that future work could focus on developing heuristic or statistical methods for automatically determining the eps parameter.
  • Strict Hill-to-Cluster Correspondence: The paper notes that while hills in the density ordering graph generally correspond to clusters, this isn't always a strict one-to-one mapping. Future research could explore mechanisms to improve the certainty of this correspondence.
  • One-way and Dead-End Roads: The current LSPD algorithm assumes bidirectional roads. While dead-end roads were considered, handling one-way roads would require further algorithmic adjustments.
  • Computational Complexity: While LSPD is more efficient than all-pairs shortest paths, the overall complexity for very large networks might still be a consideration.

Summary updated

BibTeX
@article{wang2019ns,
  author = {Tianfu Wang and Chang Ren and Yun Luo and Jing Tian},
  title = {{NS-DBSCAN: A Density-Based Clustering Algorithm in Network Space}},
  journal = {ISPRS International Journal of Geo-Information},
  year = {2019},
  url = {https://openreview.net/forum?id=62uaP3spn9},
}
Figure