CURE algorithm

CURE, short for Clustering Using REpresentatives, is a hierarchical data clustering algorithm designed for large databases. Where K-means minimises a sum of squared errors and so tends to split large clusters or fail on clusters that are not round, and where BIRCH assigns points using only cluster centroids, CURE takes a middle path. It keeps a small constant number of well scattered points from each cluster and shrinks them toward the cluster centre by a fixed fraction. These shrunken points act as the cluster's representatives, and at each step the two clusters with the closest pair of representatives are merged. This lets CURE find clusters of non-spherical shape and very different sizes and makes it less sensitive to outliers. The plain algorithm is expensive, with running time quadratic in the number of points times a logarithmic factor, so it is combined with random sampling, partitioning of the sample and labelling the remaining data on disk. The source article notes an open source implementation in the pyclustering library.