CURE (Clustering Using REpresentatives) is a scalable clustering algorithm in data mining that represents each cluster not by a single centroid but by a fixed number m of well-scattered representative points selected greedily from the cluster boundary and then shrunk by a fraction alpha toward the cluster centroid. Assigning each point to the cluster whose nearest representative is closest generalises the centroid assignment rule of k-means, allowing non-convex cluster shapes, while the shrinkage step confers robustness to outliers. Scalability is obtained by never solving a clustering problem larger than one memory-resident partition: the data is randomly partitioned, CURE runs independently (and in parallel) on each partition, the resulting m*k representative points are pooled and clustered again, and a single final pass assigns every original point to its nearest final representative — two full scans of the data in total.
CURE (Clustering Using REpresentatives) is a scalable clustering algorithm in data mining that represents each cluster not by a single centroid but by a fixed number m of well-scattered representativ…