Linkage-Based Clustering

Why One Grouping May Not Be Enough

Suppose you are given a collection of unlabeled data points and asked to organize them into groups. There may not be one objectively correct answer waiting to be discovered. Clustering is an unsupervised organization problem, so there are no supplied labels whose prediction accuracy can provide a single clear measure of success.

The result depends on what similarity means and on which structural goal the method emphasizes. One approach may emphasize keeping close points together, while another may emphasize preventing far-apart points from sharing a cluster. Both concerns can lead to meaningful but different groupings.

Clustering Inputs and Outputs

A clustering task starts with a collection of elements, written as X, together with information about how those elements relate to one another. That information may be a distance function or a similarity function. Some clustering methods also receive a requested number of clusters, k.

The output is an organization of X into groups. A hard clustering assigns each element to a separate group. A soft clustering assigns each element a vector of probabilities describing possible membership in the groups. A dendrogram is another possible output: it represents a hierarchy whose leaves are single-element sets and whose root contains the full domain.

The First Clustering Round

Linkage-based clustering builds its result progressively. At the beginning, every data point is placed in its own one-point cluster. The algorithm then examines the current collection of clusters, identifies the closest pair, and merges that pair.

How Cluster Distance Controls a Merge

A point-to-point distance is not enough for this procedure because the algorithm compares clusters, not just individual points. The point-to-point notion must be extended into a distance between clusters. In each round, the pair with the smallest current cluster distance is selected for merging.

The Chaining Effect

Single linkage can produce an unintuitive result because one close connection is enough to make two clusters appear close. After a merge, a point in the growing cluster may be close to a point in another cluster, even if many other points across the two clusters are far apart.

Repeated local connections can therefore join a long sequence of points. The points at the two distant ends of the sequence may not resemble one another directly, yet single linkage can connect them through intermediate points. This is called the chain effect in the supplied material.

Defining the Algorithm Clearly

A description such as “repeatedly merge close clusters” is incomplete. Two design choices determine the behavior of a linkage-based clustering algorithm: how distance between clusters is measured, and when the merging process stops.

• Assuming that clustering must discover one uniquely correct grouping.

  Clustering is unsupervised, and different notions of similarity or structural goals can support different meaningful groupings.

  Fix: State what similarity means and what structural goal the method is emphasizing.

• Comparing only the original individual points after the first merge.

  The next decision must use the new collection of current clusters.

  Fix: Reconsider the cluster collection after every merge.

• Assuming single linkage requires every cross-cluster pair to be close.

  Single linkage uses the closest cross-cluster pair; one close connection can control the cluster distance.

  Fix: Search for the minimum member-to-member distance between the two clusters.

• Describing the method without a stopping rule.

  The distance rule and the point at which merging stops both determine the defined procedure.

  Fix: Specify both the cluster-distance rule and the stopping rule.

Practice the Merge Process

What to Remember

1. Clustering is an unsupervised organization problem, so the same data can support multiple meaningful groupings.
2. A clustering task takes elements and relationship information such as distances or similarities, and it produces groups, probabilities, or a hierarchy.
3. Linkage-based clustering starts with every point in its own cluster and repeatedly merges the closest current clusters.
4. Every merge replaces two clusters with one, so the number of clusters decreases after each round.
5. Single linkage uses the closest pair of members across two clusters, which can create a chain connecting globally dissimilar ends.
6. A complete algorithm description must specify both how cluster distance is measured and when merging stops.