Hierarchical Clustering

Botie compares sensors by their response time. Two nearly identical sensors seem to belong together, and another nearby pair seems to form a second group. At a broader scale, all four might belong to one family. A single list of group labels hides that relationship.

Let's begin with every sensor in its own group. We will join the nearest groups, keep a record of each join, and see how that record lets us choose a useful level of detail later.

Single linkage only needs one short connection between groups. Move a response time in either group and follow the smallest cross-group distance.

3

Distance between two observations is familiar. After the first join, we need a distance between groups containing several observations. The choice of that group distance is called linkage.

Agglomerative clustering starts with individual observations and repeatedly joins groups. It makes locally chosen merges; an early merge is not undone just because a later view would favour another partition.

A = [0, 1]
B = [4, 6]
Cross-group distances:
  [4, 6]
  [3, 5]

Every entry compares one member of A with one member of B. This small table gives us several possible summaries.

Single linkage uses the smallest cross-group distance. Complete linkage uses the largest. Average linkage averages all cross-group distances. Each answers a different question about what makes groups similar.

Single linkage can connect a long chain of neighbouring points. Complete linkage resists that chain because distant endpoints count against a merge. Neither choice discovers an objectively correct grouping without a useful notion of similarity.

For the distance table above:
single linkage = 3
complete linkage = 6
average linkage = (4 + 6 + 3 + 5) / 4 = 4.5

Ward linkage is another criterion: the increase in within-group sum of squares. It is not simply one of these three summaries.

After selecting the closest pair of groups, combine their members and recalculate distances to the remaining groups. Record which groups joined and the distance or criterion value of the join.

A dendrogram draws that record as a tree. Leaves represent original observations; branch heights show when groups joined. The left-to-right order of leaves is not a measurement axis.

Response times: [0, 1, 7, 9]
Single-linkage merge heights: 1, 2, 6
Groups after the second merge: [0, 1] and [7, 9]

A horizontal cut between the second and third merge heights retains two groups. A different cut gives a different level of detail.

A hierarchy records similarities under our chosen measurements, scaling, and linkage. It does not establish that the sensors have different physical causes or that each branch is a real category.

Inspect whether small data changes alter the joins. Revisit features and units. Ties need a consistent policy because several equally close merges may lead to different later structures.

The workshop isolates the group-distance step. Choosing a different reducer changes what it means for two groups to be close.

A complete distance table grows with the square of the number of observations. Large datasets may need different algorithms or constraints on possible neighbours.

A fitted hierarchy also does not automatically define a prediction rule for a new observation. Decide whether to rebuild, attach it by a documented rule, or use a model designed to assign future observations.

Keeping the full hierarchy is useful when the task has meaningful levels of grouping, rather than only one required partition.

import numpy as np
a = np.array([0., 1.])
b = np.array([4., 6.])
d = np.abs(a[:, None] - b[None, :])
print(d.tolist())
print([float(d.min()), float(d.max()), float(d.mean())])

[[4.0, 6.0], [3.0, 5.0]]
[3.0, 6.0, 4.5]

After joining the first pair, recompute linkage using the members of the new group. A group identifier is only a bookkeeping label. Its numerical value has no role in the distance calculation.

For single linkage, the nearest pair across two groups determines their separation. This lets nearby points extend a chain even when its endpoints are far apart. Complete linkage would ask about those endpoints and can produce a different hierarchy.

import numpy as np
x = np.array([0., 1., 5., 6.])
groups = [[i] for i in range(len(x))]
while len(groups) > 1:
    candidates = []
    for i in range(len(groups)):
        for j in range(i+1, len(groups)):
            distance = min(abs(x[a]-x[b]) for a in groups[i] for b in groups[j])
            candidates.append((distance, i, j))
    distance, i, j = min(candidates)
    merged = groups[i] + groups[j]
    print(sorted(merged), float(distance))
    groups = [g for k,g in enumerate(groups) if k not in [i,j]] + [merged]

[0, 1] 1.0
[2, 3] 1.0
[0, 1, 2, 3] 4.0

The hierarchy does not automatically tell us how many physical sensor types exist. A cut chooses the resolution at which we want to describe similarity. Compare that choice with the purpose of grouping: shared calibration, inspection scheduling or exploratory description may favour different resolutions.

Check whether small measurement changes move important merges. Stable groups can be useful, but stability alone does not establish a causal or biological category. Retain the distance definition and linkage with the result so another reader can reproduce the tree.