//! Clustered ordering of a correlation matrix, for a heatmap. //! //! The matrix is symmetric, so one ordering serves both axes: cluster the //! traits, then draw the r matrix in that order and a neighbour is a trait that //! actually looks like its neighbour. //! //! Decisions, all stated because a clustering nobody can reproduce is worse //! than no clustering: //! //! * **Distance is `1 - r`**, so a pair at r = 1 sits at 0 and a pair at //! r = -1 at 2. That is the usual choice for correlation matrices and it //! keeps anti-correlated traits far apart, which is what a reader expects //! from a heatmap of *correlations*. //! * **Average linkage (UPGMA).** Single linkage chains along a gradient and //! complete linkage makes one huge flat cluster from anything with noise in //! it; average is the compromise that behaves on real expression traits. It //! is also what GN1's heatmaps used (R's `hclust(method="average")`). //! * **Deterministic ties**: when two merges have the same height the lower //! index wins, and the leaf order comes out of the tree by always placing the //! earlier-clustered side first. Two runs on the same matrix give the same //! order, which is what makes the plot diffable. //! //! The algorithm is the textbook O(n^3) one: n is at most `MAX_PCA_TRAITS`, and //! clarity beats a faster distance-update scheme that has to be trusted. /// One merge in the tree, enough to draw a dendrogram. #[derive(Debug, Clone, serde::Serialize, utoipa::ToSchema)] pub struct Merge { /// Cluster ids 0..n-1 are the traits themselves; n and up are merges, in /// the order they appear in this list. pub left: usize, pub right: usize, /// Distance at which the two were joined (`1 - r`, so 0 is identical). pub height: f64, } /// The clustered order and the tree that produced it. #[derive(Debug, Clone, serde::Serialize, utoipa::ToSchema)] pub struct Clustering { /// Trait indices in drawing order (row and column order both). pub order: Vec, pub merges: Vec, /// Largest distance seen, so a plotter can scale the dendrogram. pub max_height: f64, } /// Average-linkage clustering of a correlation matrix. /// /// Returns `None` for a matrix that is not square, is larger than the cap, or /// has a cell that is not a number -- a gap means the two traits' distance is /// unknown, and quietly treating it as 1 would invent a structure. pub fn cluster(r: &[Vec>], cap: usize) -> Option { let n = r.len(); if n < 2 || n > cap || r.iter().any(|row| row.len() != n) { return None; } let mut distance = vec![vec![0.0; n]; n]; for i in 0..n { for j in 0..n { let value = r[i][j]?; if !value.is_finite() { return None; } distance[i][j] = 1.0 - value; } } // Active clusters: members and the merge tree. let mut members: Vec> = (0..n).map(|index| vec![index]).collect(); let mut active: Vec = vec![true; n]; let mut sizes: Vec = vec![1; n]; let mut dist = distance; let mut merges: Vec = Vec::new(); let mut max_height = 0.0_f64; for _ in 1..n { // Nearest pair of active clusters, lowest index pair on a tie. let mut best = (f64::INFINITY, 0usize, 0usize); for i in 0..dist.len() { if !active[i] { continue; } for j in (i + 1)..dist.len() { if !active[j] { continue; } let d = dist[i][j]; if d < best.0 { best = (d, i, j); } } } let (height, left, right) = best; if !height.is_finite() { return None; } max_height = max_height.max(height); // Ids in this array ARE the tree ids: traits are 0..n-1 and merge m is // n+m, created in this order, so the pair can be recorded as it stands. let new_id = dist.len(); merges.push(Merge { left, right, height }); // Average linkage: the new distance is the size-weighted mean. let mut row = vec![0.0; new_id + 1]; for k in 0..new_id { if !active[k] || k == left || k == right { continue; } row[k] = (dist[left][k] * sizes[left] as f64 + dist[right][k] * sizes[right] as f64) / (sizes[left] + sizes[right]) as f64; } // Grow the matrix to new_id + 1 rows before writing into the new row: // pushing the row first is what makes dist[new_id] exist. for existing in dist.iter_mut() { existing.push(0.0); } dist.push(row.clone()); for k in 0..new_id { dist[new_id][k] = row[k]; dist[k][new_id] = row[k]; } active[left] = false; active[right] = false; active.push(true); sizes.push(sizes[left] + sizes[right]); members.push(Vec::new()); let mut merged = members[left].clone(); merged.extend(members[right].iter().copied()); members[new_id] = merged; } // Leaf order: walk the tree, earlier-clustered side first (deterministic). let mut order = Vec::with_capacity(n); fn walk(id: usize, n: usize, merges: &[Merge], order: &mut Vec) { if id < n { order.push(id); return; } let index = id - n; let merge = &merges[index]; walk(merge.left, n, merges, order); walk(merge.right, n, merges, order); } walk(dist.len() - 1, n, &merges, &mut order); if order.len() != n { return None; } Some(Clustering { order, merges, max_height, }) } #[cfg(test)] mod tests { use super::*; fn matrix(values: &[&[f64]]) -> Vec>> { values .iter() .map(|row| row.iter().map(|v| Some(*v)).collect()) .collect() } #[test] fn two_blocks_are_ordered_together() { // 0 and 1 correlate strongly with each other and with nothing else; // same for 2 and 3. A good ordering keeps each pair adjacent. let r = matrix(&[ &[1.0, 0.9, 0.0, 0.1], &[0.9, 1.0, 0.1, 0.0], &[0.0, 0.1, 1.0, 0.85], &[0.1, 0.0, 0.85, 1.0], ]); let clustering = cluster(&r, 300).expect("4x4"); let order = clustering.order; let position = |trait_index: usize| order.iter().position(|x| *x == trait_index).unwrap(); assert_eq!(position(0).abs_diff(position(1)), 1, "0 and 1 adjacent: {order:?}"); assert_eq!(position(2).abs_diff(position(3)), 1, "2 and 3 adjacent: {order:?}"); assert_eq!(order.len(), 4); assert_eq!(clustering.merges.len(), 3); // The first merges are the within-block ones, so they are the closest. assert!(clustering.merges[0].height < 0.2); assert!(clustering.merges[2].height >= clustering.merges[0].height); } #[test] fn the_order_is_reproducible() { let r = matrix(&[ &[1.0, 0.4, -0.2], &[0.4, 1.0, 0.1], &[-0.2, 0.1, 1.0], ]); let first = cluster(&r, 300).expect("3x3"); let second = cluster(&r, 300).expect("3x3"); assert_eq!(first.order, second.order); assert_eq!(first.merges.len(), second.merges.len()); } #[test] fn a_gap_refuses_rather_than_invents() { let mut r = matrix(&[&[1.0, 0.5], &[0.5, 1.0]]); r[0][1] = None; assert!(cluster(&r, 300).is_none(), "a null cell is not a distance of 1"); } #[test] fn the_cap_is_honoured() { let r = matrix(&[&[1.0, 0.5, 0.2], &[0.5, 1.0, 0.3], &[0.2, 0.3, 1.0]]); assert!(cluster(&r, 2).is_none()); } }