Hierarchical clustering: agglomerative merge order

The problem, from first principles

K-Means, GMM, and DBSCAN each build clusters by some form of "which points does this cluster currently claim," starting from some notion of cluster centers or dense regions. Agglomerative (bottom-up) hierarchical clustering takes the opposite approach entirely: start with every point as its own cluster, and repeatedly merge whichever two clusters are closest, until only the desired number remain.

From theory to code

Implement cluster_distance(points_a, points_b, linkage) and agglomerative_fit(input, n_clusters, linkage="single"). linkage is 'single', 'complete', or 'average' — anything else raises ValueError. Reuse 01-knn's pairwise_distances.

Constraints

• cluster_distance computes the distance between two groups of points under the given linkage: 'single' (closest pair), 'complete' (farthest pair), 'average' (mean over all pairs).
• An unrecognized linkage raises ValueError.
• agglomerative_fit starts with every row as its own cluster and repeatedly merges the two closest (by cluster_distance) until exactly n_clusters remain.
• Returns one cluster id per row, consistent within a merged group.

Hints

Open one at a time. Each gives away a little more than the last.