Hierarchical clustering: follow merges and choose a grouping

After grouping library readers, you may want more than one fixed partition. Which readers form close pairs, and how do those pairs combine into broader groups? Hierarchical clustering builds a nested structure of groups that lets you examine several levels of detail.

We will use an agglomerative method: start with one group per observation, then repeatedly merge groups according to a comparison rule. A dendrogram draws this merge history as a tree. Its leaves are observations; its join heights record the method’s merge dissimilarity.

Four invented readers borrowed one, two, eight and nine books in the same month. We intentionally use just one feature so the arithmetic is visible; this does not establish permanent reader categories. Review clustering without supplied target labels and feature distance before starting if needed.

Our feature table contains borrowing counts A = 1, B = 2, C = 8 and D = 9. Reader letters name the records; only their numeric counts enter the fit. Each starts as its own one-record group: {A}, {B}, {C}, {D}.

The two close pairs are easy to recognize. Their distances tie, so either pair may be the first recorded merge, depending on tie handling. Both pair merges occur before joining the distant pairs in the demonstrated methods.

A numerical difference in monthly books is not a probability that readers are alike. It also does not measure all reading behavior. Choosing this feature and period defines the scope of the grouping.

Prepare and run

Use Python with NumPy and scikit-learn in the course environment. The invented data is included; no file or download is needed.

Python · complete runnable example

from sklearn.cluster import AgglomerativeClustering

# Invented monthly borrowing counts for readers A, B, C and D.
X = [[1.0], [2.0], [8.0], [9.0]]
model = AgglomerativeClustering(n_clusters=2, linkage="ward").fit(X)
print("First pair together:", bool(model.labels_[0] == model.labels_[1]))
print("Last pair together:", bool(model.labels_[2] == model.labels_[3]))
print("Pairs separated:", bool(model.labels_[0] != model.labels_[2]))

Expected output

First pair together: True
Last pair together: True
Pairs separated: True

X has four rows and one feature column. There is no target array. n_clusters=2 requests a two-group partition, while linkage="ward" selects the merge rule explained next.

The assigned labels put the first two readers together and the final two together, with the pairs separated. Numeric group IDs are arbitrary, so the output compares membership equality rather than claiming ID zero must be a particular pair.

This is a partition of these reference observations, not a classification accuracy. Unlike KMeans, this estimator has no standard predict method for assigning a new record to fixed clusters. Refitting with an additional record can alter the hierarchy. The AgglomerativeClustering API describes the partition and supported settings.

After A and B merge, treat {A, B} as one group for subsequent comparisons. After C and D merge, the active groups are {A, B} and {C, D}. Joining those two produces {A, B, C, D}. The smaller groups remain part of the recorded history.

In ordinary agglomerative clustering, a merge is not undone later. This differs from K-means assignment updates, where an observation can switch between fitted groups as centers move. Early hierarchical choices influence the later structure.

A divisive method goes in the other direction: begin with observations together and split groups recursively. This lesson’s code uses the agglomerative approach. The names describe how the hierarchy is built, not which direction the tree must be drawn on screen.

A merge tree can describe relationships at different resolutions. It is an analysis under a chosen distance and rule, not proof that the population naturally follows that hierarchy.

The distance between individual records is not enough once a group contains several records. Linkage defines how their members are combined into a group-to-group comparison. For {A, B} = {1, 2} and {C, D} = {8, 9}, the four cross-group distances are 7, 8, 6 and 7.

Single linkage can join groups through a chain of nearby observations even when the ends are far apart. Complete linkage uses the most distant pair, often favoring tighter groups. Average linkage summarizes all cross-group pair distances; it is not simply the distance between the two means.

These rules can produce different hierarchies on less obvious data. Our four records deliberately give the same near-pair membership, so the main visible difference will be the height of the final merge.

Ward linkage compares the increase in the sum of squared distances from group members to their group mean. It uses Euclidean geometry. It is a different question from the closest pair, farthest pair or average pairwise distance.

For {1, 2}, the mean is 1.5 and its squared deviations sum to 0.25 + 0.25 = 0.5. For {8, 9}, the mean is 8.5 and its total is also 0.5. Together, the separate groups contribute 1.

Merging all four gives mean 5 and squared deviations 16 + 9 + 9 + 16 = 50. The increase is 50 − 1 = 49. In the SciPy/scikit-learn Ward convention used here, the corresponding dendrogram height is √(2 × 49), approximately 9.899. It is not the raw gap of six between counts two and eight.

For a pair of singleton records with count difference one, the variation increase is 0.5 and the height is one. This explains the two short joins and later tall join in our diagram. Ward heights must be read under this convention rather than interpreted as ordinary distances between arbitrary individual readers.

Prepare and run

Use Python with NumPy and scikit-learn in the course environment. The invented data is included; no file or download is needed.

Python · complete runnable example

from scipy.cluster.hierarchy import linkage

# Same invented counts: A=1, B=2, C=8, D=9.
X = [[1.0], [2.0], [8.0], [9.0]]
history = linkage(X, method="ward")
for step, (left, right, height, count) in enumerate(history, start=1):
    print("Merge", step, ": nodes", int(left), "+", int(right),
          "height", round(float(height), 3), "readers", int(count))

Expected output

Merge 1 : nodes 0 + 1 height 1.0 readers 2
Merge 2 : nodes 2 + 3 height 1.0 readers 2
Merge 3 : nodes 4 + 5 height 9.899 readers 4

This independent example uses SciPy, which is included with the course’s scikit-learn environment. linkage receives the four observation rows, not a square distance table. It returns one row per merge.

Original observations have node IDs 0–3. The first merge creates node 4 from A and B; the second creates node 5 from C and D; the final merge joins nodes 4 and 5. Each history row stores the two child IDs, merge height and number of original readers in that new group.

The printed values match the diagram’s calculated heights. Because the two first pair distances tie, another implementation could record the pair merges in the opposite order without changing this hierarchy. The SciPy linkage reference documents the history format and merge conventions.

A dendrogram’s leaves identify original observations. A horizontal join connects two groups; its height is their linkage-specific merge dissimilarity. Follow upward from a leaf to see the groups it enters as the allowed level grows.

Our A–B and C–D joins are at height one, while the final join is about 9.899 under Ward. A horizontal cut between those heights keeps the two pairs separate. A cut above the final merge puts every reader together; a cut below the first joins leaves four separate records.

Horizontal leaf spacing is not the original count distance. A and B may be drawn as far apart as C and D for readability, and left/right subtree order can flip without changing the merges. Merge heights are not membership probabilities or measured confidence.

SciPy’s dendrogram tool draws a linkage history. Our page draws the same small history directly as accessible SVG. Larger plots may truncate or summarize branches, so inspect the plotting options before assuming every displayed leaf is one original observation.

Prepare and run

Use Python with NumPy and scikit-learn in the course environment. The invented data is included; no file or download is needed.

Python · complete runnable example

from scipy.cluster.hierarchy import linkage

# Same four invented records for every linkage rule.
X = [[1.0], [2.0], [8.0], [9.0]]
for method in ["single", "complete", "average", "ward"]:
    history = linkage(X, method=method)
    print(method, "heights:", history[:, 2].round(3).tolist())

Expected output

single heights: [1.0, 1.0, 6.0]
complete heights: [1.0, 1.0, 8.0]
average heights: [1.0, 1.0, 7.0]
ward heights: [1.0, 1.0, 9.899]

The program repeats all four records and applies each method independently. All four identify the same two early pairs. Their final merge values differ because each rule compares the resulting groups differently.

Do not treat a final Ward height of 9.899 as evidence that its groups are more certain than the groups at single-linkage height six. These are different quantities. A numerical cutoff chosen for one linkage cannot automatically be reused with another interpretation.

With two requested groups, these particular methods agree on this dataset. That does not mean linkage never changes membership. Examine the tree structure and assignments on the actual records, especially when there are bridges, unusual observations or overlapping regions.

Prepare and run

Use Python with NumPy and scikit-learn in the course environment. The invented data is included; no file or download is needed.

Python · complete runnable example

from sklearn.cluster import AgglomerativeClustering

# Invented counts A=1, B=2, C=8, D=9.
X = [[1.0], [2.0], [8.0], [9.0]]
for threshold in [0.5, 3.0, 11.0]:
    model = AgglomerativeClustering(
        n_clusters=None, distance_threshold=threshold, linkage="ward"
    ).fit(X)
    print("Cutoff:", threshold, "groups:", model.n_clusters_)
    print("First pair together:", bool(model.labels_[0] == model.labels_[1]))
    print("Pairs separated:", bool(model.labels_[0] != model.labels_[2]))

Expected output

Cutoff: 0.5 groups: 4
First pair together: False
Pairs separated: True
Cutoff: 3.0 groups: 2
First pair together: True
Pairs separated: True
Cutoff: 11.0 groups: 1
First pair together: True
Pairs separated: False

Instead of requesting a fixed cluster count, this complete program supplies a distance_threshold and sets n_clusters to None. The estimator computes the required hierarchy and uses the selected threshold to obtain a partition.

A cutoff of 0.5 is below both height-one pair merges, leaving four groups. Three includes both pair merges but excludes the final 9.899 join, leaving two. Eleven includes all three merges, leaving one group.

For this scikit-learn setting, a merge at or above the threshold is not included. Our page’s cutoff slider uses the same strict-below convention. At exactly one it therefore leaves four groups; at 1.5 it includes both pair merges. Do not rely on a diagram’s rounded height to determine an exact tie.

Two groups highlight the large separation between borrowing counts in this teaching data. One group gives a coarser summary and four groups preserve individual records. The right resolution depends on the purpose; a dendrogram does not supply a mandatory answer.

Look for meaningful profiles, group sizes, unusual members and sensitivity to feature or sampling changes. A large jump in merge height can suggest a useful cut, but an elbow-like visual jump does not prove that a population contains that many natural categories.

Describe groups with the observed features and period, such as “lower monthly borrowing” and “higher monthly borrowing”. Cluster IDs are arbitrary and should not rank people. The segmentation lesson develops useful summaries and questions their meaning.

Your task: In the complete first program below, change n_clusters from two to one. Predict the three printed comparisons. Does placing all records together make their original count differences disappear?

Python · complete program to modify

from sklearn.cluster import AgglomerativeClustering

# Invented monthly borrowing counts for readers A, B, C and D.
X = [[1.0], [2.0], [8.0], [9.0]]
model = AgglomerativeClustering(n_clusters=2, linkage="ward").fit(X)
print("First pair together:", bool(model.labels_[0] == model.labels_[1]))
print("Last pair together:", bool(model.labels_[2] == model.labels_[3]))
print("Pairs separated:", bool(model.labels_[0] != model.labels_[2]))

Original output with two groups

First pair together: True
Last pair together: True
Pairs separated: True

Worked answer

Use AgglomerativeClustering(n_clusters=1, linkage="ward"). It joins the two pairs, so every record shares one group label.

First pair together: True
Last pair together: True
Pairs separated: False

The feature values are unchanged: B and C still differ by six books. A coarser partition changes the description of membership, not the observed measurements. Requesting four groups would leave each record separate in this example.

With more features, distance and linkage depend on the feature scales. Books, visits and amounts spent can contribute very differently if their raw numbers differ in magnitude. Choose an appropriate representation and review scaling. Ward requires Euclidean geometry; do not combine it with an arbitrary non-Euclidean metric.

There is no standard reassignment stage that repairs an early agglomerative merge. Ties or small data changes can affect later structure. A new record is not automatically assigned by a predict method in this estimator. Refitting, or designing a separate assignment model, answers a different question and can change earlier group relationships.

Many ordinary hierarchical methods store or process pairwise relationships, which can require quadratic memory: the number of pairs grows roughly with the square of the record count. Time and memory depend on method and implementation. A four-leaf diagram is not evidence that a full dendrogram is practical for millions of observations.

Connectivity constraints can restrict allowed merges and exploit known structure, but they change the problem. The hierarchical clustering guide describes supported methods and constraints. Compare suitable alternatives when the dataset or geometry does not fit this approach.

Our four readers began as separate groups, formed two near pairs and joined at a later Ward height. Different cuts produced different levels of detail without changing the underlying measurements.

• Understand the direction: agglomerative methods merge; divisive methods split.
• State the comparison: single, complete, average and Ward linkage measure group relationships differently.
• Read the diagram: leaves identify observations and heights record linkage-specific joins. Horizontal spacing is layout.
• Choose a level: a cluster count or height cutoff selects a partition; it does not prove natural categories.
• Respect limits: feature scales, tie handling, irreversible merges and computational cost affect the analysis.

Before moving on: trace the cutoff-three groups, calculate complete linkage for the cross-group distances and explain why a Ward height is not a probability. Next, we will simplify a feature representation with principal component analysis.