Distance and Similarity Functions
The chosen distance or similarity notion shapes the result.
Try it: Linkage-Based Clustering
How agglomerative clustering starts from singletons and repeatedly merges the two closest clusters under single (min), complete (max) or average linkage, building a dendrogram until a stopping rule (k clusters or distance threshold r) says stop.
How it works
- Start with every point in its own cluster and compute the distance matrix.
- Cluster distance: single = closest pair of members (minimum), complete = farthest pair (max linkage), average = mean over all pairs.
- Find the closest pair of current clusters (ties go to the pair listed first) and merge them; the cluster count drops by one.
- Update the new cluster's row of the distance matrix and record the merge height in the dendrogram.
- Stop when k clusters remain, or when every between-cluster distance is larger than r.
Default run (12 steps): 8 points, each its own cluster. Single linkage; stop when 3 clusters remain. … Done: 3 clusters — {A,B,C} {D,E,F,G} {H}.
Simplified: Toy 2-D data (3–10 points) with Euclidean distance. Real hierarchical clustering uses many more points, other distances and faster data structures.
Loading the simulation…
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.
- 1Start
The method begins with four singleton clusters: {A}, {B}, {C}, and {D}.
- 2First merge
The method identifies the closest pair among the current clusters and merges that pair. There are now three clusters.
- 3Later merge
The method compares the current clusters, identifies the closest pair under its linkage rule, and merges them. The number of clusters falls again.
- 4Stopping
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.
- 1Local connection
Single linkage can first join a close neighboring pair, such as Endpoint A with Bridge 1.
- 2Bridge 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.
- 3Endpoint connection
The resulting cluster can be joined with Endpoint B because Bridge 2 and Endpoint B are a close pair.
- 4Final 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. |
Different representations expose different aspects of a clustering result.
Mistakes in Interpreting Clusters
Common mistake Assuming that every data set has one objectively correct clustering.
What it looks likeTreating the output of one clustering method as the only valid grouping.
Why it failsThe aims of grouping similar objects and separating dissimilar objects can conflict, and different notions of similarity can produce different defensible results.
Do this insteadAsk what distance or similarity notion the method embodies and whether that notion matches the intended meaning of closeness.
Common mistake Thinking that linkage-based clustering starts with one large cluster.
What it looks likeDescribing the first step as splitting the full data set into smaller groups.
Why it failsLinkage-based clustering begins with every data point in its own one-point cluster.
Do this insteadTrace the process from singleton clusters, through repeated merges, toward the chosen stopping condition.
Common mistake Assuming single linkage compares all cross-cluster pairs equally.
What it looks likeExpecting the overall separation of two clusters to determine their single-linkage distance.
Why it failsSingle linkage is based on the closest pair across the two clusters.
Do this insteadLook for the closest cross-cluster pair; that pair determines the single-linkage comparison.
Common mistake Assuming that dissimilar endpoints cannot share a single-linkage cluster.
What it looks likeRejecting a cluster because its first and last points are far apart.
Why it failsA chain of nearby points can connect the endpoints through repeated local merges.
Do this insteadInspect 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
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
- 1Clustering has no universally correct answer because similarity and separation can be interpreted in different ways.
- 2A distance or similarity function supplies the method's particular meaning of closeness, and that choice shapes the resulting groups.
- 3Linkage-based clustering starts with singleton clusters, repeatedly merges the closest current pair, and stops according to a chosen condition.
- 4Single linkage uses the closest pair across two clusters.
- 5A chain of nearby points can connect dissimilar endpoints and place them in the same single-linkage cluster.
At a glance
- 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.