Hierarchical clustering algorithms

Hierarchical clustering algorithms according to the cluster-generating method can further be divided into:

► Agglomerating hierarchical algorithms. These algorithms produce a sequence of clustering schemes by reducing the number of clusters in each step. The cluster plan produced at each step leads from the previous one by merging the two closest clusters. To find the similarity of two clusters, one of the following criteria is used: the minimum, maximum, or average pair wise distance between the points of the two clusters.
​
► Divisive Hierarchical algorithms. These algorithms produce a sequence of clustering schemes that increase the number of clusters in each step. Unlike Agglomerating algorithms, the clustering generated in each step from the previous algorithm leads to the separation of a cluster into two.

CURE is a hierarchical clustering algorithm whose key features are:

► Can recognize blocks of arbitrary shapes (e.g. ellipsoidal).

► It’s strong in the presence of outliers.

► It’s storage requirements are a linear function of the number of input elements and it's time complexity is 0 (n2) for small data, where n is the number of input elements.

The algorithm can be efficiently applied to clustering big databases by combining random sampling and partitioning techniques. Therefore, the data input to the algorithm may be a sample selected randomly or a subset of this sample if the clustering is previously applied.