Distance and Similarity Functions
Clustering does not necessarily have one correct answer.
Why Grouping Has No Single Answer
Clustering asks a model to group similar objects together and separate dissimilar objects. Unlike a supervised task with a specified correct answer, clustering does not necessarily have one correct grouping waiting to be discovered. The goals of keeping similar objects together and keeping dissimilar objects apart can conflict, so different interpretations of similarity can produce different groupings that are each defensible.
From Elements to Groups
A clustering model receives elements and a way to compare pairs of elements. A distance function interprets smaller values as greater closeness, while a similarity function interprets greater values as greater similarity. The model uses that chosen notion of closeness to decide which elements or groups should belong together. Because the comparison rule embodies a particular idea of similarity, changing it can change the resulting groups.
| Comparison notion | How closeness is interpreted |
|---|---|
| Distance | Elements or clusters with a smaller distance are treated as closer. |
| Similarity | Elements or clusters with a greater similarity are treated as more similar. |
The comparison function supplies the meaning of closeness used by the clustering method.
The Linkage Merge Process
Linkage-based clustering begins with the most separated possible grouping: every data point is its own one-point cluster. The method then repeatedly identifies the closest pair of current clusters and merges them. Each merge reduces the number of clusters. If the process continues without stopping, all elements eventually become one cluster.
Tracing a linkage-based run
Suppose a data set contains four elements: A, B, C, and D. Trace the structure of linkage-based clustering without assuming a particular numerical distance.
Start: The method begins with four singleton clusters: {A}, {B}, {C}, and {D}.
First merge: The method identifies the closest pair among the current clusters and merges that pair. There are now three clusters.
Later merge: The method compares the current clusters, identifies the closest pair under its linkage rule, and merges them. The number of clusters falls again.
Stopping: The process stops according to a chosen condition. If it does not stop, repeated merging eventually produces one cluster containing all four elements.
The important state change is that the method moves from one cluster per element toward progressively larger groups, always selecting the closest current pair according to the chosen linkage rule.
Single Linkage and the Closest Pair
Single linkage measures the distance between two clusters using the closest pair of points across those clusters. It does not require every point in one cluster to be close to every point in the other cluster. One especially close cross-cluster pair can therefore determine which two clusters are merged.
This rule makes single linkage sensitive to local connections. A cluster may be linked to another cluster because of one close pair, even when other points in the two clusters are much less alike. That behavior is the basis of the single-linkage chaining effect.
The Chaining Effect
Imagine a sequence of points in which each point is close to the next point, but the first and last points are dissimilar. Single linkage can connect the sequence one local pair at a time. Once the intermediate points form a bridge, the two dissimilar endpoints can end up in the same cluster. This is called a chain effect.
Following a local connection
Consider points arranged as Endpoint A, Bridge 1, Bridge 2, and Endpoint B. Each neighboring pair is close, while the two endpoints are dissimilar.
Local connection: Single linkage can first join a close neighboring pair, such as Endpoint A with Bridge 1.
Bridge extension: The cluster containing Endpoint A can then be joined with Bridge 2 because Bridge 1 and Bridge 2 provide a close cross-cluster pair.
Endpoint connection: The resulting cluster can be joined with Endpoint B because Bridge 2 and Endpoint B are a close pair.
Final effect: The two endpoints are now in the same cluster even though they are dissimilar to one another. The intermediate points created the chain.
Single linkage can favor a continuous chain of local similarities over the overall similarity of the cluster's endpoints.
Cluster Output Formats
The result of clustering can be represented in more than one way. In a hard partition, each element belongs to one of the resulting subsets. In a soft partition, the output assigns each element probabilities of belonging to the different clusters. A dendrogram represents nested groups: individual elements appear at the leaves, while the full domain appears at the root.
| Output form | What it represents |
|---|---|
| Hard partition | Each element belongs to one resulting subset. |
| Soft partition | Each element receives probabilities of belonging to the different clusters. |
| Dendrogram | Nested groups, with individual elements at the leaves and the full domain at the root. |
Mistakes in Interpreting Clusters
Assuming that every data set has one objectively correct clustering.
The aims of grouping similar objects and separating dissimilar objects can conflict, and different notions of similarity can produce different defensible results.
Fix:
Ask what distance or similarity notion the method embodies and whether that notion matches the intended meaning of closeness.Thinking that linkage-based clustering starts with one large cluster.
Linkage-based clustering begins with every data point in its own one-point cluster.
Fix:
Trace the process from singleton clusters, through repeated merges, toward the chosen stopping condition.Assuming single linkage compares all cross-cluster pairs equally.
Single linkage is based on the closest pair across the two clusters.
Fix:
Look for the closest cross-cluster pair; that pair determines the single-linkage comparison.Assuming that dissimilar endpoints cannot share a single-linkage cluster.
A chain of nearby points can connect the endpoints through repeated local merges.
Fix:
Inspect the intermediate connections rather than only comparing the endpoints.
Practice the Trace
A linkage-based method has begun with one cluster per element. At the next round, two current clusters contain many points, but one point in the first cluster is especially close to one point in the second cluster. Explain why single linkage may use that pair when deciding whether the clusters are close. Then describe how a sequence of such local connections could eventually connect two dissimilar endpoints.
Hints
- Recall which pair of points single linkage uses across two clusters.
- Track the number of clusters after each merge.
- Distinguish local neighboring connections from the overall similarity of the endpoints.
What do you think happens?
A chain contains Endpoint A, Bridge 1, Bridge 2, and Endpoint B. Each neighboring pair is close, but Endpoint A and Endpoint B are dissimilar. Under single linkage, can the endpoints end up in the same cluster?
Reveal answer
Answer: Yes, because local close pairs can create a chain.
Single linkage uses the closest pair across two clusters. Repeated local connections through the bridge points can therefore merge clusters containing the dissimilar endpoints.
Key Takeaways
- Clustering has no universally correct answer because similarity and separation can be interpreted in different ways.
- A distance or similarity function supplies the method's particular meaning of closeness, and that choice shapes the resulting groups.
- Linkage-based clustering starts with singleton clusters, repeatedly merges the closest current pair, and stops according to a chosen condition.
- Single linkage uses the closest pair across two clusters.
- A chain of nearby points can connect dissimilar endpoints and place them in the same single-linkage cluster.
Key Takeaways
- Clustering does not necessarily have one correct answer because different notions of similarity can produce different defensible groupings.
- Distance and similarity functions determine what the clustering method treats as close.
- Linkage-based clustering repeatedly merges the closest current clusters, beginning with one cluster per element.
- Single linkage bases the distance between two clusters on their closest cross-cluster pair.
- Local connections can form a chain that places dissimilar endpoints in one cluster.