Hierarchical clustering starts with every point as a cluster of its own and repeats one move: merge the two closest clusters. It stops when a single cluster is left. The list of merges it makes, with the distance at which each one happened, is exactly what a dendrogram draws: every merge is a branch point, and its distance is that branch's height.
Task: write merge_history(points, linkage), where points is a list of (x, y) pairs (point i is the i-th pair) and linkage is "single", "complete" or "average". Return the list of merges in the order they happen.
The distance between two points is straight-line (Euclidean) distance. The distance between two clusters depends on linkage, and is always worked out from the original points:
linkage | distance between clusters and |
|---|---|
"single" | the distance of the closest pair, one point from and one from |
"complete" | the distance of the farthest pair, one point from and one from |
"average" | the average distance over every pair with one point from and one from |
Each merge is a tuple (left, right, height):
left and right are the two clusters being joined, each a sorted list of point indices, and left is the one holding the smaller index;height is the linkage distance between them at the moment they merge, rounded to 4 decimal places.A list of points makes merges, so a single point makes none. The tests never have two pairs of clusters tied for closest.