A Novel Divisive Hierarchical Clustering Algorithm for Geospatial Analysis

Shaoning Li, Wenjing Li, Jia QiuISPRS Int. J. Geo Inf 2017 · DOI

TL;DR

This paper introduces a novel divisive hierarchical clustering algorithm (CDHC) designed to effectively cluster geospatial data with varying densities and noise. By leveraging a convex hull structure to capture global spatial context and a unique boundary retraction mechanism, CDHC offers improved robustness and efficiency compared to traditional methods, particularly for complex, multi-density point distributions.

What Problem Does This Paper Address?

Clustering is a fundamental technique in geospatial analysis, used for tasks like image segmentation, pattern recognition, and cartographic generalization. However, existing clustering methods often struggle with several challenges:

  • Computational Complexity: Many algorithms become prohibitively slow with large datasets.
  • Noise Sensitivity: Outliers can significantly distort clustering results.
  • Multi-Density Objects: Differentiating between clusters of varying point densities is difficult, especially when they are close together.
  • Limited Spatial Context: Traditional methods often focus on local spatial relationships, making it hard to handle global structures and distinguish between noise and actual cluster boundaries.

These limitations hinder accurate analysis of real-world geospatial data, which frequently exhibits these characteristics.

Methods

The paper proposes a Cell-dividing Hierarchical Clustering (CDHC) algorithm, a divisive (top-down) hierarchical approach. Its core novelty lies in:

  • Global Spatial Context via Convex Hull: CDHC first constructs a minimum convex hull around the entire set of geospatial points. This hull serves as a global descriptor of the data's spatial structure, allowing the algorithm to consider the overall arrangement rather than just local neighborhoods.
  • Boundary Retraction Mechanism: Instead of traditional merging or splitting based on distance, CDHC uses a "boundary retraction" process. This involves creating a concave boundary by "retracting" the convex hull edges inwards.
  • Parabola-Based Retraction: The paper introduces a novel parabola-based convex hull retraction method. This method uses a parabolic function to define the retracted boundary, offering better detection efficiency and a more reasonable boundary shape compared to previous arc-based methods. The retraction depth and accuracy are controlled by parameters.
  • Splitting Condition: A cluster is split into two sub-clusters when the retracted boundaries intersect. This process is repeated iteratively.
  • Adaptive Parameterization: The algorithm uses a variable retracting accuracy parameter, which is adjusted based on local point density. This allows CDHC to adapt to varying densities within the dataset.
  • Termination Condition: The splitting process continues until borderlines are marked as "0" (indicating no further splitting is possible) or a sub-cluster contains too few points to form a convex hull, at which point these points are classified as noise.

Datasets

The paper evaluates CDHC using several synthetic datasets designed to test its capabilities:

  • Experiment 1: A dataset with two distinct point clusters surrounded by noisy points.
  • Experiment 2: Multiple datasets featuring multi-density objects, both with and without noise. These include:
  • Three geospatial point sets with different densities (no noise).
  • A dataset with two clusters and abundant noise.
  • A dataset with multi-density objects and a little noise.
  • Experiment 3: Real-world geospatial data representing the spatial distribution of five types of restaurants (Chinese, Western, hot-pot, fast food, supermarket) in Wuhan's Central District.

Key Insights and Ideas

  • Global Context is Key for Noise and Multi-Density: The paper strongly advocates for using global spatial context (via convex hull) to effectively distinguish between noise and genuine clusters, especially when densities vary significantly.
  • Divisive Hierarchical Clustering Offers Efficiency: By starting with a single cluster and progressively splitting, CDHC avoids the computational burden of calculating pairwise distances between all objects at each step, leading to improved efficiency for large datasets.
  • Parabola Retraction is Superior: The proposed parabola-based boundary retraction method demonstrates better efficiency and produces more sensible cluster boundaries than previous arc-based retraction techniques.
  • Adaptive Density Handling: The ability to adjust retraction parameters based on local density is crucial for successfully clustering datasets with widely varying point concentrations.

Key Results

  • Noise and Multi-Density Handling: CDHC successfully separates multi-density objects from noise and handles datasets with varying densities more effectively than traditional Agglomerative Hierarchical Clustering (AHC) and Clustering based on Delaunay Triangulation (CBDT).
  • Efficiency: Table 1 shows that CDHC significantly outperforms AHC in terms of processing time for large point sets, with a time complexity of O(Kn) compared to AHC's O(n²).
  • Comparison with Other Algorithms:
    • CDHC, CBDT, and DBSCAN showed good anti-noise ability (around 95% recognition rate) on general data with noise.
  • K-means struggled to identify noise and effective data.
  • CBDT had difficulty with multi-density points, and its recognition rate dropped to 70%.
  • DBSCAN sometimes misclassified noise points and struggled with large density differences.
  • K-means, while identifying cluster centers, partitioned multi-density objects incorrectly.
  • Real-World Application: The CDHC algorithm was successfully applied to analyze the spatial distribution of restaurants in Wuhan, producing results that align with known commercial development patterns.

Limitations and Future Work

  • Clusters within Clusters: The authors acknowledge that CDHC, in its current form, is unable to address clusters contained within other clusters.
  • Future Work: The paper suggests future research could focus on combining CDHC with improved DBSCAN methods to address the "clusters within clusters" problem and further solve multi-density clustering challenges.

Summary updated

BibTeX
@article{li2017novel,
  author = {Shaoning Li and Wenjing Li and Jia Qiu},
  title = {{A Novel Divisive Hierarchical Clustering Algorithm for Geospatial Analysis}},
  journal = {ISPRS Int. J. Geo Inf.},
  year = {2017},
  doi = {10.3390/ijgi6010030},
}
Figure