cluster
Mojo module đźˇ
cluster
Agglomerative clustering of a matrix’s rows: a distance, a linkage rule, the merge tree they produce, and the leaf order that tree implies (#355).
No drawing here. A clustermap’s whole point is the reordering – a heatmap in arbitrary row order shows almost nothing, and the same matrix with similar rows together shows its block structure at a glance – and the reordering is a numerical question with a right answer, testable against a hand-worked example without rendering anything.
The algorithm is the nearest-neighbour chain, which is O(n^2) time and
O(n^2) memory rather than the O(n^3) of repeatedly scanning for the
closest pair. That matters here: #325 had just finished taking an
O(n^2) out of delaunay(), and the benchmark guard exists so the next
one is caught rather than shipped. scripts/bench.mojo carries this
from the start.
The chain works by walking from a cluster to its nearest neighbour, then to that one’s nearest neighbour, until two are each other’s nearest – a reciprocal pair, which is always safe to merge. Every linkage here is “reducible”, meaning a merge never makes some other pair closer than both were to each other, which is exactly the property that makes the walk valid. Lance-Williams gives the updated distance in constant time per remaining cluster, so no distance is ever recomputed from the rows.
Structs
DistanceMetric: How far apart two rows are.Linkage: How far apart two clusters are, given how far apart their members are.Merge: One join in aDendrogram: two nodes and the distance they were joined at.Dendrogram: A finished merge tree: the joins in increasing height, and the leaf order they imply.