Chapter 4.7: Clustering

The problem of clustering arises whenever there is a collection of objects that you want to classify or organize into coherent groups. Naturally, the first thing you do is check how similar or dissimilar each pair of objects is. This is commonly known as a distance function, where the objects at a larger distance from one another are less similar to each other. Given a distance function on the objects, the clustering problem seeks to divide them into groups so that objects within the same group are “close” and objects in different groups are “far apart.” Our goal is to find a clustering of maximum spacing.

Suppose we are given a set U of n objects, labeled p_1, p_2,…, p_n. For each pair, p_i, p_j, we have a distance d(p_i, p_j), where d(p_i, p_i)=0 and d(p_i, p_j) > 0 for distinct p_i and p_j and that distances are symmetric. We want to divide the objects in U into k groups, for a given parameter k. A k-clustering of U is a partition of U into k nonempty sets C_1, C_2,…, C_k. The spacing of a k-clustering is the minimum distance between any pair of points lying in different clusters. We want to maximize this minimum distance.

To find a clustering of maximum spaces, we grow a graph on the vertex set U. The connected components will be clusters. We start by drawing an edge between the closest pair of points. Then we draw an edge between the next closest pair of points. We continue in this way, adding edges in order of increasing distance. We only add an edge, however, between points p_i and p_j if they do not already belong to the same cluster. So, our graph-growing process will never create a cycle (each cluster will be a tree). We stop once we have k clusters/trees. This is basically Kruskal's Algorithm, but we stop when we have k components rather than when we have 1 component. In other words, we stop the algorithm before it adds the last k-1 edges. This is the same as taking the entire spanning tree and deleting the k-1 most expensive edges. This algorithm produces a k-clustering of maximum spacing.

I would rate this section a 10. It was very easy to read and understand, especially after the lecture (which was kind of tricky). This definitely solidified my understanding of clustering.