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
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
//! `hclust`: agglomerative hierarchical clustering of a distance matrix — the
//! leaf order a heatmap's rows and columns follow so that similar items sit
//! side by side (R's `heatmap()`, `corrplot(order = "hclust")`,
//! `ggcorrplot(hc.order = TRUE)`), and the merges a dendrogram draws
//! ([`dendrogram_links`](super::tree::dendrogram_links) takes them as they
//! are).
//!
//! The merges follow R's `hclust` convention: merge `k` (1-based) joins two
//! children, `-(i + 1)` for item `i` and `m` for merge `m`. Ties merge the
//! pair found first (lowest indices), so the result is deterministic.
//!
//! The leaf order goes one step beyond R's: when two clusters merge, each may
//! be reversed so that the two leaves that meet are the closest of the four
//! possible pairs — a cheap leaf-ordering pass that keeps neighbours
//! across a merge similar too (the heatmap's blocks join smoothly).
/// How the distance between two clusters is measured.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
#[non_exhaustive]
pub enum Linkage {
/// The mean distance over all pairs (UPGMA, R's `"average"`).
#[default]
Average,
/// The largest pairwise distance (R's `"complete"`).
Complete,
/// The smallest pairwise distance (R's `"single"`).
Single,
}
/// The result of [`hclust`].
#[derive(Clone, Debug, PartialEq)]
pub struct Hclust {
/// One pair of children per merge (see the module docs for the
/// numbering), `n - 1` of them.
pub merge: Vec<(i64, i64)>,
/// The distance each merge happened at, non-decreasing for average,
/// complete and single linkage.
pub heights: Vec<f64>,
/// The items in leaf order (a permutation of `0..n`).
pub order: Vec<usize>,
}
/// Cluster `n` items from their `n × n` distance matrix (symmetric; only the
/// upper triangle is read). A missing or non-finite distance counts as the
/// largest finite one; a ragged row's missing entries too. No items: an
/// empty result; one item: no merges and the order `[0]`.
pub fn hclust(dist: &[Vec<f64>], linkage: Linkage) -> Hclust {
let n = dist.len();
let raw = |i: usize, j: usize| {
let (a, b) = if i < j { (i, j) } else { (j, i) };
dist[a].get(b).copied().filter(|d| d.is_finite())
};
let worst = (0..n)
.flat_map(|i| (i + 1..n).map(move |j| (i, j)))
.filter_map(|(i, j)| raw(i, j))
.fold(0.0_f64, f64::max);
let d = |i: usize, j: usize| raw(i, j).unwrap_or(worst);
// Active clusters: their id in the merge numbering, size and leaves (in
// leaf order), and the current cluster-to-cluster distances.
let mut ids: Vec<i64> = (0..n).map(|i| -(i as i64 + 1)).collect();
let mut size: Vec<usize> = vec![1; n];
let mut leaves: Vec<Vec<usize>> = (0..n).map(|i| vec![i]).collect();
let mut alive: Vec<bool> = vec![true; n];
let mut cd: Vec<Vec<f64>> = (0..n)
.map(|i| (0..n).map(|j| if i == j { 0.0 } else { d(i, j) }).collect())
.collect();
let mut merge = Vec::with_capacity(n.saturating_sub(1));
let mut heights = Vec::with_capacity(n.saturating_sub(1));
for k in 1..n {
// the closest pair of live clusters, the first found on a tie
let mut best: Option<(usize, usize, f64)> = None;
for i in 0..n {
if !alive[i] {
continue;
}
for j in i + 1..n {
if alive[j] && best.is_none_or(|(_, _, b)| cd[i][j] < b) {
best = Some((i, j, cd[i][j]));
}
}
}
let Some((a, b, h)) = best else { break };
// R lists a singleton before a merge, two singletons by item and two
// merges by age
let pair = if (ids[a] < 0) == (ids[b] < 0) {
if ids[a] < 0 {
(ids[a].max(ids[b]), ids[a].min(ids[b]))
} else {
(ids[a].min(ids[b]), ids[a].max(ids[b]))
}
} else {
(ids[a].min(ids[b]), ids[a].max(ids[b]))
};
merge.push(pair);
heights.push(h);
// the leaf order: orient both halves so the leaves that meet are
// the closest of the four candidates
let (la, lb) = (
std::mem::take(&mut leaves[a]),
std::mem::take(&mut leaves[b]),
);
let ends = |l: &[usize]| (l[0], l[l.len() - 1]);
let ((a0, a1), (b0, b1)) = (ends(&la), ends(&lb));
let options = [
(false, false, d(a1, b0)),
(false, true, d(a1, b1)),
(true, false, d(a0, b0)),
(true, true, d(a0, b1)),
];
let (ra, rb, _) =
options
.iter()
.copied()
.fold(options[0], |acc, o| if o.2 < acc.2 { o } else { acc });
let mut joined: Vec<usize> = if ra {
la.into_iter().rev().collect()
} else {
la
};
if rb {
joined.extend(lb.into_iter().rev());
} else {
joined.extend(lb);
}
// the new cluster lives on in slot a
for x in 0..n {
if !alive[x] || x == a || x == b {
continue;
}
let (da, db) = (cd[a][x], cd[b][x]);
let v = match linkage {
Linkage::Average => {
(da * size[a] as f64 + db * size[b] as f64) / (size[a] + size[b]) as f64
}
Linkage::Complete => da.max(db),
Linkage::Single => da.min(db),
};
cd[a][x] = v;
cd[x][a] = v;
}
alive[b] = false;
size[a] += size[b];
ids[a] = k as i64;
leaves[a] = joined;
}
let order = (0..n)
.find(|&i| alive[i])
.map(|i| leaves[i].clone())
.unwrap_or_default();
Hclust {
merge,
heights,
order,
}
}
/// The leaf order of `n` items from their `n × n` *similarity* matrix (a
/// correlation's absolute value, a normalized mutual information): distance
/// = largest similarity − similarity, average linkage.
pub fn similarity_order(sim: &[Vec<f64>]) -> Vec<usize> {
let n = sim.len();
let top = sim
.iter()
.enumerate()
.flat_map(|(i, r)| {
r.iter()
.enumerate()
.filter(move |(j, _)| *j != i)
.map(|(_, v)| *v)
})
.filter(|v| v.is_finite())
.fold(f64::NEG_INFINITY, f64::max);
let dist: Vec<Vec<f64>> = (0..n)
.map(|i| {
(0..n)
.map(|j| {
let s = sim[i].get(j).copied().unwrap_or(f64::NAN);
if s.is_finite() {
top - s
} else {
f64::NAN
}
})
.collect()
})
.collect();
hclust(&dist, Linkage::Average).order
}
#[cfg(test)]
mod tests {
use super::*;
fn m(rows: &[&[f64]]) -> Vec<Vec<f64>> {
rows.iter().map(|r| r.to_vec()).collect()
}
#[test]
fn empty_and_single() {
assert_eq!(hclust(&[], Linkage::Average).order, Vec::<usize>::new());
let one = hclust(&m(&[&[0.0]]), Linkage::Average);
assert_eq!(one.order, vec![0]);
assert!(one.merge.is_empty());
}
// R: hclust(as.dist(d), "average") on the same matrix
#[test]
fn merges_and_heights_as_r() {
let d = m(&[
&[0.0, 2.0, 6.0, 10.0, 9.0],
&[2.0, 0.0, 5.0, 9.0, 8.0],
&[6.0, 5.0, 0.0, 4.0, 5.0],
&[10.0, 9.0, 4.0, 0.0, 3.0],
&[9.0, 8.0, 5.0, 3.0, 0.0],
]);
let h = hclust(&d, Linkage::Average);
assert_eq!(h.merge, vec![(-1, -2), (-4, -5), (-3, 2), (1, 3)]);
assert_eq!(h.heights[..3], [2.0, 3.0, 4.5]);
// (6 + 10 + 9 + 5 + 9 + 8) / 6
assert!((h.heights[3] - 47.0 / 6.0).abs() < 1e-12);
// the two blocks side by side, 1 next to 2 and 2 next to 3
assert_eq!(h.order, vec![0, 1, 2, 3, 4]);
}
#[test]
fn complete_and_single() {
let d = m(&[&[0.0, 1.0, 4.0], &[1.0, 0.0, 2.0], &[4.0, 2.0, 0.0]]);
assert_eq!(hclust(&d, Linkage::Complete).heights, vec![1.0, 4.0]);
assert_eq!(hclust(&d, Linkage::Single).heights, vec![1.0, 2.0]);
}
// shuffled blocks come back together
#[test]
fn similarity_order_groups_blocks() {
// items 0, 2, 4 are one block, 1 and 3 another
let s = |i: usize, j: usize| {
if i == j {
1.0
} else if i % 2 == j % 2 {
0.8
} else {
0.1
}
};
let sim: Vec<Vec<f64>> = (0..5).map(|i| (0..5).map(|j| s(i, j)).collect()).collect();
let o = similarity_order(&sim);
let pos = |x: usize| o.iter().position(|&v| v == x).unwrap();
let mut evens = [pos(0), pos(2), pos(4)];
evens.sort();
assert_eq!(
evens[2] - evens[0],
2,
"the even block is contiguous: {o:?}"
);
}
#[test]
fn missing_distances_count_as_the_largest() {
let d = m(&[
&[0.0, f64::NAN, 1.0],
&[f64::NAN, 0.0, 3.0],
&[1.0, 3.0, 0.0],
]);
let h = hclust(&d, Linkage::Single);
assert_eq!(h.merge[0], (-1, -3));
assert_eq!(h.heights, vec![1.0, 3.0]);
}
}