Show that the MST clustering technique of Section 9.4.2 produces the same clusters as single link. To avoid complications and special cases, assume that all the pairwise similarities are distinct.

Question

What will be an ideal response?

Answer 1

In single link, we start with with clusters of individual points and then succes-
sively join two clusters that have the pair of points that are closest together.

Conceptually, we can view the merging of the clusters as putting an edge
between the two closest points of the two clusters. Note that if both clusters
are currently connected, then the resulting cluster will also be connected.
However, since the clusters are formed from disjoint sets of points, and edges
are only placed between points in different clusters, no cycle can be formed.
From these observations and by noting that we start with clusters (graphs)
of size one that are vacuously connected, we can deduce by induction that

at any stage in single link clustering process, each cluster consists of a con-
nected set of points without any cycles. Thus, when the last two clusters are

merged to form a cluster containing all the points, we also have a connected
graph of all the points that is a spanning tree of the graph. Furthermore,
since each point in the graph is connected to its nearest point, the spanning
tree must be a minimum spanning tree. All that remains to establish the
equivalence of MST and single link is to note that MST essentially reverses
the process by which single link built the minimum spanning tree; i.e., by
breaking edges beginning with the longest and proceeding until the smallest.
Thus, it generates the same clusters as single link, but in reverse order.