Hierarchical clustering

Of the several clustering algorithms that we will examine in this chapter, hierarchical clustering is probably the simplest. The trade-off is that it works well only with small datasets in Euclidean space.

The general setup is that we have a dataset S of m points in which we want to partition into a given number k of clusters C₁, C₂,..., C_k, where within each cluster the points are relatively close together. (B. J. Frey and D. Dueck, Clustering by Passing Messages Between Data Points Science 315, Feb 16, 2007 http://science.sciencemag.org/content/315/5814/972).

Here is the algorithm:

1. Create a singleton cluster for each of the m data points.

2. Repeat m – k times:

   • Find the two clusters whose centroids are closest

   • Replace those two clusters with a new cluster that contains their points

The centroid of a cluster is the point whose coordinates are the averages of the corresponding coordinates of the cluster points. For example, the centroid of the cluster C = {(2, 4), (3, 5),...