Cure: An Efficient Clustering Algorithm for Large Databases

Sudipto Guha, Rajeev Rastogi, Kyuseok ShimInf. Syst 2001 · DOI

TL;DR

This paper introduces CURE, a novel hierarchical clustering algorithm designed for large datasets. CURE overcomes limitations of existing methods by using multiple "representative points" per cluster, allowing it to discover non-spherical shapes and handle varying cluster sizes, while also being robust to outliers. Its efficiency for large datasets is achieved through random sampling and partitioning, making it scalable without sacrificing accuracy.

What Problem Does This Paper Address?

Clustering is a fundamental task in data mining, aiming to group similar data points together. Traditional clustering algorithms often struggle with real-world datasets, which rarely consist of perfectly spherical, uniformly sized clusters. Algorithms like K-Means (partitional) and hierarchical clustering often favor spherical shapes and can be highly sensitive to outliers, leading to inaccurate results. For instance, they might split large clusters or merge distinct ones if outliers create a false connection. Furthermore, the quadratic time complexity of many hierarchical algorithms makes them impractical for the massive databases common today. Existing methods for large datasets, like BIRCH, use summaries but can still struggle with non-spherical clusters during the final labeling phase.

Methods

CURE introduces a two-pronged approach:

  • Hierarchical Clustering with Representative Points: Instead of using a single centroid (like in K-Means) or all points (like in MST), CURE represents each cluster by a fixed number of well-scattered points. These "representative points" are then "shrunk" towards the cluster's centroid by a fraction $\alpha$. This shrinking helps to dampen the effect of outliers. The distance between two clusters is then calculated as the minimum distance between any pair of their representative points. This allows CURE to capture the shape and extent of clusters, enabling it to identify non-spherical and varied-sized clusters. The parameter $\alpha$ controls the degree of shrinking, with values between 0.2 and 0.7 being effective for non-spherical clusters.
  • Random Sampling and Partitioning for Scalability: To handle large datasets, CURE first draws a random sample. This sample is then partitioned, and each partition is partially clustered. Finally, these partial clusters are merged in a second pass. This strategy significantly reduces the computational burden. Outliers are also handled in multiple steps, including during sampling and through a two-phase elimination process.

Datasets

The paper evaluates CURE on four synthetic 2D datasets:

  • Data Set 1: Big and small circles, ellipsoids, with outliers.
  • Data Set 2: Big and small ellipsoids, with outliers.
  • Data Set 3: Big and small rings.
  • Data Set 4: 100 clusters arranged in a grid, with normally distributed points.

These datasets are designed to test the algorithms' ability to handle non-spherical shapes, varying sizes, and outliers.

Key Insights and Ideas

  • Representative points are key: Using multiple, well-chosen, and shrunk representative points is a powerful way to capture cluster geometry beyond simple centroids, making algorithms robust to shape and outliers.
  • Shrinking dampens outliers: The "shrinking" of representative points towards the centroid effectively mitigates the influence of outliers, preventing them from distorting cluster boundaries.
  • Sampling and partitioning are crucial for scale: For massive datasets, reducing the problem size through random sampling and then processing partitions in parallel (or sequentially) is an effective strategy that doesn't significantly compromise clustering quality.
  • Labeling matters for non-spherical clusters: Using multiple representative points for final data labeling on disk is essential for correctly assigning points to non-spherical or non-uniform clusters, unlike methods relying solely on centroids.

Key Results

  • Superior Clustering Quality: CURE consistently outperformed BIRCH and MST (Minimum Spanning Tree, equivalent to all-points approach) in identifying clusters with non-spherical shapes (ellipsoids, rings) and wide variances in size.
  • Robustness to Outliers: CURE was significantly less sensitive to outliers than MST, which was heavily affected by chains of outliers connecting clusters.
  • Scalability: CURE's execution time was shown to be significantly lower than BIRCH, especially as the dataset size increased. Partitioning further improved CURE's performance, reducing execution times by over 50%.
  • Parameter Sensitivity: The paper demonstrates that CURE's performance is sensitive to parameters like the shrink factor ($\alpha$) and the number of representative points ($c$). Optimal ranges were identified (e.g., $\alpha$ between 0.2-0.7).
  • Efficient Handling of High Dimensions: CURE was shown to handle high-dimensional data effectively.

Limitations and Future Work

  • Parameter Tuning: While CURE performs well, finding the optimal parameters ($\alpha$, $c$, $s$, $p$) might require some experimentation, though the paper provides good default ranges.
  • Sample Size vs. Accuracy Trade-off: While random sampling is effective, there's an inherent trade-off between sample size and the probability of missing clusters or misidentifying them, especially for poorly separated clusters. The paper uses Chernoff bounds to analytically derive minimum sample sizes to mitigate this.
  • Future Work: The paper implicitly suggests further exploration into optimal partitioning strategies and more sophisticated outlier detection mechanisms. The authors also mention that the labeling phase for BIRCH and CURE is similar, implying that improvements in CURE's labeling could further differentiate it.

Summary updated

BibTeX
@article{guha2001cure,
  author = {Sudipto Guha and Rajeev Rastogi and Kyuseok Shim},
  title = {{Cure: An Efficient Clustering Algorithm for Large Databases}},
  journal = {Inf. Syst.},
  year = {2001},
  doi = {10.1016/s0306-4379(01)00008-4},
}
Figure