Concepts / Hierarchical Clustering

Hierarchical Clustering

Linkage-based clustering repeatedly merges clusters, beginning with single-point clusters.

  • 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…

The First Round

Hierarchical clustering is a clustering approach built around repeated merging. It begins with every data point in its own single-point cluster. In each round, the algorithm looks at the existing clusters, identifies the closest pair according to a chosen cluster-distance rule, and merges that pair.

Round 0{A} {B} {C} {D}Round 1{A,B} {C} {D}Round 2{A,B} {C,D}Round 3{A,B,C,D}merge two clustersmerge two clustersmerge two clusters
What happens to individual-point clusters and merged clusters after each round?

The Merge Cycle

  1. 1
    Start with every data point in its own single-point cluster.
  2. 2
    Use the selected cluster-distance method to compare the existing clusters.
  3. 3
    Identify the closest pair of clusters under that method.
  4. 4
    Merge the selected pair into one cluster.
  5. 5
    Repeat the comparison and merge process for the next round.

The important state change is the merge. Two existing clusters become one new cluster. Other clusters remain available for later comparisons, and the next round evaluates the updated collection of clusters rather than the original collection of individual points.

Existing clusterscurrent roundCluster-distancemethodsingle, average, or maxCompare cluster pairsunder the chosen methodClosest pairselected for mergingMerged clusternext roundmeasuredefines distancesfindmerge
How does the algorithm compare existing clusters to decide which pair merges next?

Why the Count Falls

Every merge replaces two clusters with one cluster. Therefore, the total number of clusters decreases after every merge. If a round begins with a collection of clusters, the merge removes two separate entries from that collection and puts back one combined entry. Continued merging can eventually produce one large cluster containing all domain points.

Cluster ACluster ABCluster Bmergemerge
How does merging two clusters change the total cluster count from one round to the next?
Worked example

Counting Merges

Suppose a round starts with four clusters and the algorithm performs one merge.

  1. 1
    Before the merge

    There are four separate clusters.

  2. 2
    During the merge

    The algorithm selects two clusters and combines them.

  3. 3
    After the merge

    The selected pair is represented by one cluster, while the other two clusters remain separate.

Result

The next round has three clusters. The count decreases because two clusters were replaced by one.

Three Linkage Rules

A linkage rule defines the distance between two clusters by examining distances between their members. Single, average, and max linkage use different summaries of those member-to-member distances. Because the summary can change, the same pair of clusters can receive different cluster distances under different linkage rules. That can cause different pairs to be chosen for the next merge.

Single linkageminimum member-to-memberdistanceAverage linkageaverage member-to-memberdistanceMember-to-memberdistancesbetween two clustersMax linkagemaximum member-to-memberdistanceselects minimumsummarizes by averageselects maximum
How does each linkage method measure the distance between two clusters?
Linkage methodCluster distance is based on
Single linkageThe minimum distance between a member of one cluster and a member of the other cluster
Average linkageThe average of the distances between members of the two clusters
Max linkageThe maximum distance between members of the two clusters

The methods differ in which summary of member-to-member distances they use.

A Linkage Comparison

Worked example

One Pair of Clusters, Three Distances

Consider two hypothetical clusters. The distances between their members are 2, 5, and 9.

  1. 1
    Single linkage

    Single linkage uses the minimum member-to-member distance, so the cluster distance is 2.

  2. 2
    Average linkage

    Average linkage uses the average of the member-to-member distances, so the cluster distance is 16 divided by 3.

  3. 3
    Max linkage

    Max linkage uses the maximum member-to-member distance, so the cluster distance is 9.

Result

The same two clusters have different distances under the three linkage rules: 2 for single linkage, 16 divided by 3 for average linkage, and 9 for max linkage.

This example shows why the linkage choice matters before the algorithm selects its next merge. The algorithm compares cluster distances, and the selected rule determines how those distances are summarized. A pair that looks close under one rule may not be the closest pair under another rule.

The Two Required Choices

A linkage-based clustering algorithm is defined by two choices. First, it needs a cluster-distance method, such as single, average, or max linkage, to determine how far apart two clusters are. Second, it needs a rule for when merging stops. The distance method controls which pair is considered closest at each round; the stopping rule controls how long the repeated merging process continues.

Linkage-basedalgorithmCluster-distancemethoddetermines closest pairNext mergeStopping ruledetermines when mergingendsFinal cluster stateincludesincludescontrolscontrols
Which two choices must be specified before linkage-based clustering begins?

Common Reasoning Errors

  • Common mistake

    Assuming the number of clusters stays constant

    What it looks like

    Treating a merge as if it only records a relationship while leaving both clusters separate

    Why it fails

    A merge replaces two clusters with one, so the cluster count decreases after every merge.

    Do this instead

    Update the collection of clusters after each round: remove the selected pair and add their combined cluster.

  • Common mistake

    Treating single linkage as an average

    What it looks like

    Using all member-to-member distances and averaging them when the selected method is single linkage

    Why it fails

    Single linkage uses the minimum member-to-member distance.

    Do this instead

    Match the summary to the method: minimum for single, average for average, and maximum for max linkage.

  • Common mistake

    Treating max linkage as the nearest connection

    What it looks like

    Selecting the smallest member-to-member distance when the selected method is max linkage

    Why it fails

    Max linkage uses the maximum distance between the clusters' elements.

    Do this instead

    Look for the largest relevant member-to-member distance when computing max linkage.

  • Common mistake

    Specifying only a linkage method

    What it looks like

    Defining an algorithm as average linkage without stating when merging stops

    Why it fails

    A linkage-based clustering algorithm requires both a cluster-distance method and a stopping rule.

    Do this instead

    State both choices before describing the algorithm.

Check Your Understanding

EASY

A linkage-based algorithm begins with six single-point clusters. It performs two merges. How many clusters exist after the second merge? Then state which linkage method uses the minimum member-to-member distance and name the second parameter required to define the algorithm.

Hints
  • Each merge replaces two clusters with one, so account for one fewer cluster after each merge.
  • Compare the words minimum, average, and maximum with the three linkage methods.
  • The second parameter determines when the repeated merging process stops.

What do you think happens?

Two clusters have member-to-member distances of 3, 6, and 12. Which linkage method assigns the distance 3 to the pair?

  • Single linkage

  • Average linkage

  • Max linkage

Reveal answer
Answer:

Single linkage

Single linkage defines the distance between two clusters using the minimum member-to-member distance.

Key Takeaways

  1. 1
    Hierarchical clustering begins with every data point in its own single-point cluster.
  2. 2
    Each round identifies the closest pair under a chosen cluster-distance rule and merges that pair.
  3. 3
    The number of clusters decreases after every merge because two clusters become one.
  4. 4
    Single, average, and max linkage use the minimum, average, and maximum member-to-member distances respectively.
  5. 5
    A complete linkage-based clustering definition requires both a cluster-distance method and a rule for when merging stops.

At a glance

  • The process starts with one cluster per data point and repeatedly merges clusters.
  • Every merge reduces the cluster count by one and updates the state used in the next round.
  • Single linkage uses the minimum, average linkage uses the average, and max linkage uses the maximum member-to-member distance.
  • The two defining choices are the cluster-distance method and the stopping rule.

Related Topics

Related concepts

More concepts starting with H