Concepts / Single Linkage Clustering

Single Linkage Clustering

Single Linkage Clustering is a clustering method.

  • Programming
Interactive lab

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

  1. Start with every point in its own cluster and compute the distance matrix.
  2. Cluster distance: single = closest pair of members (minimum), complete = farthest pair (max linkage), average = mean over all pairs.
  3. Find the closest pair of current clusters (ties go to the pair listed first) and merge them; the cluster count drops by one.
  4. Update the new cluster's row of the distance matrix and record the merge height in the dendrogram.
  5. 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.

Educational simulation

Loading the simulation…

A Boundary Between Topics

Single Linkage Clustering is a clustering method. Clustering is an unsupervised grouping task: it organizes observations according to choices about similarity and distance. The supplied material does not define PCA, variance maximization, principal components, or dimensionality reduction. Therefore, this lesson establishes what the material does support: how clustering groups observations and how Single Linkage compares clusters during that process.

Clusteringgroups observationsSimilarity anddistancechoices affect resultPCAnot defined hereDimensionalityreductionnot defined heredepends ontopic boundary only
What distinction can be made from the supplied material without inventing a definition of PCA?

Model Input and Output

A clustering model receives observations together with a basis for judging similarity or distance. The source material emphasizes that the original input supplies a distance between points. The model then produces a grouping of those observations. Because the similarity and distance choices influence the result, changing those choices can change the resulting clusters.

ObservationspointsClustering modelsimilarity and linkagechoicesClustersgrouped observationsPoint distancesinput relationshipenterdescribeproduces
What data enters a clustering model, and what kind of result comes out?
In the real world

Suppose a dataset has several observations and a distance value for each relevant pair of observations. A clustering model uses those distances to decide which observations or existing groups are close enough to be merged according to its algorithm. The output is a set of clusters rather than a reduced-dimensional representation established by the supplied material.

The Two Linkage Decisions

Linkage-based clustering begins with distances between individual points, but later it must compare clusters containing multiple points. Two decisions specify the algorithm. First, it must define the distance between clusters. Second, it must specify when to stop merging. Different choices for either decision can lead to different clusterings.

Worked example

Separating the Algorithm's Decisions

A linkage-based method has several current clusters. What must be decided before its behavior is fully specified?

  1. 1
    Define cluster distance

    The method needs a rule for turning the distances between individual points into a distance between two clusters.

  2. 2
    Choose a stopping rule

    The method needs a rule for deciding when the repeated merging process ends.

  3. 3
    Recognize possible variation

    Changing either decision can produce a different clustering.

Result

A linkage-based algorithm is not fully described by the word clustering alone; its cluster-distance rule and stopping decision matter.

The Closest-Pair Rule

Definition

Single Linkage defines the distance between two clusters as the minimum distance between any two members of those clusters. In plain language, compare every relevant cross-cluster pair and use the distance of the closest pair as the cluster-to-cluster distance.

Worked example

Finding One Single Linkage Distance

Cluster A contains points A1 and A2. Cluster B contains points B1 and B2. The cross-cluster distances are A1-B1: 8, A1-B2: 3, A2-B1: 6, and A2-B2: 5. What is the Single Linkage distance between the clusters?

  1. 1
    List the cross-cluster distances

    The relevant values are 8, 3, 6, and 5. They compare a member of Cluster A with a member of Cluster B.

  2. 2
    Select the minimum

    The smallest cross-cluster distance is 3, belonging to the pair A1 and B2.

  3. 3
    Assign the cluster distance

    Single Linkage uses that smallest pairwise distance as the distance between Cluster A and Cluster B.

Result

The Single Linkage distance between Cluster A and Cluster B is 3.

Cluster AA1, A2A1-B2distance 3Cluster distanceminimum cross-clusterdistanceCluster BB1, B2member A1member B2defines
How is the distance between two clusters determined from the closest pair of points?

Repeated Merging

Linkage-based clustering repeatedly merges the closest clusters. After one merge, the number of clusters is reduced. The algorithm then evaluates the current clusters again, using its linkage rule to determine which pair is closest for the next merge. This process continues until the chosen stopping condition is reached.

What do you think happens?

If the closest pair of current clusters is merged, what happens to the number of clusters before the next comparison?

  • It increases

  • It decreases

  • It must stay the same

Reveal answer
Answer:

It decreases.

Linkage-based clustering merges two current clusters into one, reducing the number of clusters each round.

A | B | C | Dcurrent clustersAB | C | Dclosest pair mergedAB | CDclosest current pair mergedABCDlater stopping pointmerge closest clustersrecompare current clustersmerge again
What happens next as the two closest clusters are repeatedly merged?
Worked example

Tracing Three Merge Rounds

Consider four current clusters named A, B, C, and D. Assume the closest pair at the first round is A and B, and that after this merge the closest current pair is AB and C. Trace the process.

  1. 1
    First round

    The algorithm identifies A and B as the closest current clusters and merges them. The current set becomes AB, C, and D.

  2. 2
    Second round

    The algorithm compares the current clusters again. By assumption, AB and C are now the closest pair, so they merge into ABC.

  3. 3
    Third round

    The current set is ABC and D. The algorithm can compare these remaining clusters and apply its stopping decision.

Result

The process is iterative: merge the closest current clusters, reduce the number of clusters, then evaluate the new current state.

Mistakes About Single Linkage

  • Common mistake

    Treating Single Linkage as the distance between cluster centers or representatives.

    What it looks like

    Using a center-based distance even though the method is defined by its members.

    Why it fails

    Single Linkage uses the minimum distance between any two members of the two clusters.

    Do this instead

    Inspect the cross-cluster point distances and select the smallest one.

  • Common mistake

    Assuming that clustering and PCA are interchangeable.

    What it looks like

    Describing a clustering result as though it were a PCA result.

    Why it fails

    The supplied material establishes clustering as an unsupervised grouping task but does not define PCA or dimensionality reduction.

    Do this instead

    Describe the clustering output as groups, and do not attribute unsupported PCA behavior to it.

  • Common mistake

    Describing only the first merge.

    What it looks like

    Stopping the explanation after identifying the first closest pair.

    Why it fails

    Linkage-based clustering repeatedly merges the closest current clusters, and the current set changes after every merge.

    Do this instead

    After each merge, describe the new cluster set and the next comparison.

  • Common mistake

    Ignoring the stopping decision.

    What it looks like

    Assuming the algorithm is fully specified once Single Linkage is named.

    Why it fails

    A linkage-based algorithm also needs a rule for when to stop merging.

    Do this instead

    State both the cluster-distance rule and the stopping decision.

Apply the Rule

EASY

Cluster X contains X1 and X2. Cluster Y contains Y1 and Y2. Their cross-cluster distances are X1-Y1: 9, X1-Y2: 4, X2-Y1: 7, and X2-Y2: 6. Identify the Single Linkage distance between Cluster X and Cluster Y, name the point pair that determines it, and explain why the other three distances do not determine the cluster distance.

Hints
  • List all four distances between a member of Cluster X and a member of Cluster Y.
  • Single Linkage selects the minimum cross-cluster distance.
  • The determining pair is the pair associated with that minimum.
MEDIUM

A linkage-based process currently has clusters A, B, C, and D. It merges A and C because they are the closest current pair. Describe the next state and explain what the algorithm must do before choosing another merge.

Hints
  • Replace A and C with one combined cluster.
  • The number of current clusters decreases.
  • The algorithm must compare the new current clusters using its linkage rule.

Key Takeaways

  1. 1
    Clustering is an unsupervised grouping task whose result depends on similarity and distance choices.
  2. 2
    A clustering model uses observations and point-distance information to produce groups.
  3. 3
    Linkage-based clustering repeatedly merges the closest current clusters, reducing the number of clusters after each merge.
  4. 4
    Single Linkage defines the distance between two clusters as the minimum distance between any two of their members.
  5. 5
    The supplied material does not define PCA, variance maximization, principal components, or dimensionality reduction.

At a glance

  • Single Linkage is a clustering method, not a definition of PCA or dimensionality reduction.
  • Clustering uses similarity or distance choices to organize observations into groups.
  • Linkage-based clustering repeatedly merges the closest current clusters.
  • Single Linkage measures two clusters by the closest pair of members across them.
  • A complete linkage-based algorithm also needs a stopping decision.

Related Topics

Related concepts

More concepts starting with S