CURE algorithm

CURE (Clustering Using REpresentatives) is an efficient data clustering algorithm for large databases . Compared with K-means clustering it is more robust to outliers and able to identify clusters having non-spherical shapes and size variances.

CURE (Clustering Using REpresentatives) is an efficient data clustering algorithm for large databases . Compared with K-means clustering it is more robust to outliers and able to identify clusters having non-spherical shapes and size variances. E = \sum_{i=1}^{k} \sum_{p \in C_i} (p-m_i)^{2}, Given large differences in sizes or geometries of different clusters, the square error method could split the large clusters to minimize the square error, which is not always correct. Also, with hierarchic clustering algorithms these problems exist as none of the distance measures between clusters ( d_{min}, d_{mean} ) tend to work with different cluster shapes. Also the running time is high when n is large. The problem with the BIRCH algorithm is that once the clusters are generated after step 3, it uses centroids of the clusters and assigns each data point to the cluster with the closest centroid. Using only the centroid to redistribute the data has problems when clusters lack uniform sizes and shapes. For every cluster u (each input point), in u.mean and u.rep store the mean of the points in the cluster and a set of c representative points of the cluster (initially c = 1 since each cluster has one data point). Also u.closest stores the cluster closest to u. All the input points are inserted into a k-d tree T Treat each input point as separate cluster, compute u.closest for each u and then insert each cluster into the heap Q. (clusters are arranged in increasing order of distances between u and u.closest). While size (Q) > k Remove the top element of Q (say u) and merge it with its closest cluster u.closest (say v) and compute the new representative points for the merged cluster w. Remove u and v from T and Q. For all the clusters x in Q, update x.closest and relocate x insert w into Q repeat ==See also== k-means clustering BFR algorithm

Text derived from https://en.wikipedia.org/w/index.php?oldid=1282972435 under CC BY-SA 4.0; modifications have been made.