Agglomerative linkage and cluster cuts

Last updated: 7 Oct 20265 min read

tutorial

Agglomerative clustering starts with one cluster per observation and repeatedly joins the closest pair under a declared linkage rule.

Linkage answers what closest means

A planner groups warehouse profiles after scaling intake volume and delay rate. Single linkage uses the closest cross-cluster pair and can chain through narrow bridges; complete linkage uses the farthest cross-cluster pair, favoring compact groups. Average linkage uses an average. Ward-style linkage instead follows a variance objective and has its own distance assumptions. The code implements complete linkage only, so its merges should not be described as Ward merges.

Read the merge history before choosing a cut

A hierarchy records which groups joined and at what distance. Cutting it at two groups is a decision that changes the final segmentation, not a property that the data announced. The example stops at two clusters and checks two clearly separated operating groups. On real data, inspect the jump in merge distances, support counts and operational interpretability; the same numerical cut may behave differently after adding a new site.

Check the distance contract

If volume has a much larger numeric range than late-scan rate, Euclidean distance can largely ignore the rate. Fit scaling on the reference cohort and preserve that transform when comparing future sites. Missing measurements need a defined policy before distance is computed. The scaling guide covers this, while PCA explains a possible but lossy projection.

Compare stability with other cluster ideas

A long chain of sites might become one group under single linkage but split under complete linkage. DBSCAN can leave sparse sites unassigned; agglomerative clustering will eventually merge every site if allowed to run to one group. K-means optimizes a center-based objective. Compare memberships under reasonable distances and linkage settings, not just one summary score.

Do not turn a grouping into a causal story

A cluster of high-volume sites may appear to have worse handoff rates because the sites serve different routes or use different clocks. The grouping describes the selected features. It does not show that changing a site’s cluster label would change its outcome. Review measurement quality and any proposed staffing rule separately. The project asks for an action test and a no-action option.

Implementation

from math import dist

warehouse_profiles = [(1.0, 1.1), (1.3, 0.9), (0.8, 1.4),
                      (7.8, 8.0), (8.1, 8.4), (8.5, 7.7)]
distances = {(left, right): dist(warehouse_profiles[left], warehouse_profiles[right])
             for left in range(len(warehouse_profiles))
             for right in range(left + 1, len(warehouse_profiles))}

def point_distance(left, right):
    return distances[(min(left, right), max(left, right))]

def complete_linkage(first, second):
    return max(point_distance(left, right)
               for left in first for right in second)

clusters = [frozenset([index]) for index in range(len(warehouse_profiles))]
merge_distances = []
while len(clusters) > 2:
    options = [(complete_linkage(clusters[left], clusters[right]), left, right)
               for left in range(len(clusters))
               for right in range(left + 1, len(clusters))]
    distance, left, right = min(options)
    merge_distances.append(distance)
    joined = clusters[left] | clusters[right]
    clusters = [group for index, group in enumerate(clusters)
                if index not in (left, right)] + [joined]

assert set(clusters) == {frozenset({0, 1, 2}), frozenset({3, 4, 5})}
assert len(merge_distances) == 4

Performance and operating cost

The distance matrix takes O(N²F) time and O(N²) memory. This direct merge search revisits interpoint distances over O(N) rounds, costing up to O(N³) time. Use a tested clustering implementation and measure memory before applying full hierarchical methods to large cohorts.

Common Mistakes

Do not call complete linkage Ward linkage.
Do not treat a two-group cut as an inherent truth about the sites.
Do not infer an operational effect from cluster membership alone.