about summary refs log tree commit diff
path: root/src/heatmap.rs
blob: f179980e6f53a3a953c355b2bb51ee5fff7eedf3 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
//! 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<usize>,
    pub merges: Vec<Merge>,
    /// 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<Option<f64>>], cap: usize) -> Option<Clustering> {
    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<Vec<usize>> = (0..n).map(|index| vec![index]).collect();
    let mut active: Vec<bool> = vec![true; n];
    let mut sizes: Vec<usize> = vec![1; n];
    let mut dist = distance;
    let mut merges: Vec<Merge> = 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<usize>) {
        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<Vec<Option<f64>>> {
        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());
    }
}