Skip to main content

solow_cluster/
agglomerative.rs

1//! [`AgglomerativeClustering`] — bottom-up hierarchical clustering with
2//! `Single`, `Complete`, `Average`, or `Ward` linkage.
3//!
4//! # Algorithm
5//!
6//! Start with `n` singleton clusters. At each step, merge the two
7//! clusters with minimum linkage distance until a target `n_clusters`
8//! is reached (or all points are in one cluster if that target is 1).
9//! The pairwise distance matrix is updated in `O(n)` per merge via the
10//! Lance-Williams recurrence, so the whole fit is `O(n² · log n)` time
11//! with `O(n²)` space.
12//!
13//! Ward linkage minimises the total within-cluster variance and
14//! matches `cluster.AgglomerativeClustering(linkage='ward')`;
15//! it's the recommended default when Euclidean distances are meaningful.
16//!
17//! # References
18//!
19//! * Lance, G. N., & Williams, W. T. (1967). *A general theory of
20//!   classificatory sorting strategies: 1. Hierarchical systems.*
21//!   The Computer Journal, 9(4), 373-380.
22//! * Müllner, D. (2011). *Modern hierarchical, agglomerative clustering
23//!   algorithms.* arXiv:1109.2378.
24
25use ndarray::{Array1, ArrayView2};
26use solow_core::{Error, Result};
27
28/// Linkage criterion.
29#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
30#[derive(Copy, Clone, Debug, PartialEq, Eq)]
31pub enum Linkage {
32    /// Single (min pairwise distance).
33    Single,
34    /// Complete (max pairwise distance).
35    Complete,
36    /// Unweighted average pairwise distance (UPGMA).
37    Average,
38    /// Ward — minimises within-cluster variance increase.
39    Ward,
40}
41
42/// One row of the dendrogram: the merge that created a new cluster.
43#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
44#[derive(Clone, Copy, Debug, PartialEq)]
45pub struct DendrogramNode {
46    /// Left child cluster id.
47    pub left: usize,
48    /// Right child cluster id.
49    pub right: usize,
50    /// Linkage distance at which the merge occurred.
51    pub distance: f64,
52    /// Number of original samples in the merged cluster.
53    pub size: usize,
54}
55
56/// Agglomerative clusterer.
57#[derive(Clone, Copy, Debug)]
58pub struct AgglomerativeClustering {
59    /// Target cluster count. If `1`, the whole dendrogram is built.
60    pub n_clusters: usize,
61    /// Linkage criterion.
62    pub linkage: Linkage,
63}
64
65impl AgglomerativeClustering {
66    /// New clusterer with the given target count and linkage.
67    pub fn new(n_clusters: usize, linkage: Linkage) -> Self {
68        Self {
69            n_clusters,
70            linkage,
71        }
72    }
73
74    /// Fit and return per-sample labels in `[0, n_clusters)`.
75    pub fn fit_predict(
76        &self,
77        x: ArrayView2<'_, f64>,
78    ) -> Result<(Array1<usize>, Vec<DendrogramNode>)> {
79        let n = x.nrows();
80        if n == 0 || x.ncols() == 0 {
81            return Err(Error::Value(
82                "AgglomerativeClustering::fit_predict: x must have at least one row and one column"
83                    .into(),
84            ));
85        }
86        if self.n_clusters == 0 || self.n_clusters > n {
87            return Err(Error::Value(format!(
88                "AgglomerativeClustering::fit_predict: n_clusters must be in [1, n] (got {}, n={n})",
89                self.n_clusters
90            )));
91        }
92        // Initial pairwise distances (Euclidean).
93        let mut d = vec![vec![0.0_f64; n]; n];
94        for i in 0..n {
95            for j in (i + 1)..n {
96                let mut s = 0.0_f64;
97                for k in 0..x.ncols() {
98                    let diff = x[[i, k]] - x[[j, k]];
99                    s += diff * diff;
100                }
101                let dist = if matches!(self.linkage, Linkage::Ward) {
102                    // For Ward we store squared distances weighted by 0.5 so
103                    // the Lance-Williams update matches Ward exactly.
104                    s
105                } else {
106                    s.sqrt()
107                };
108                d[i][j] = dist;
109                d[j][i] = dist;
110            }
111        }
112        let mut sizes = vec![1usize; n];
113        let mut alive: Vec<bool> = vec![true; n];
114        let mut parent: Vec<Option<usize>> = vec![None; n]; // for label reconstruction
115        let mut nodes: Vec<DendrogramNode> = Vec::with_capacity(n - 1);
116
117        let target_merges = if self.n_clusters == 0 {
118            n - 1
119        } else {
120            n - self.n_clusters
121        };
122
123        for merge_idx in 0..(n - 1) {
124            if merge_idx >= target_merges {
125                break;
126            }
127            // Find the closest live pair.
128            let mut best = (0usize, 0usize);
129            let mut best_d = f64::INFINITY;
130            for i in 0..(n + nodes.len()) {
131                if i >= alive.len() || !alive[i] {
132                    continue;
133                }
134                for j in (i + 1)..(n + nodes.len()) {
135                    if j >= alive.len() || !alive[j] {
136                        continue;
137                    }
138                    if d[i][j] < best_d {
139                        best_d = d[i][j];
140                        best = (i, j);
141                    }
142                }
143            }
144            let (a, b) = best;
145            let new_size = sizes[a] + sizes[b];
146            let node_id = n + nodes.len();
147            let node_dist = if matches!(self.linkage, Linkage::Ward) {
148                // Store the Ward "distance" as the sqrt of merge SSE contribution.
149                (best_d).sqrt()
150            } else {
151                best_d
152            };
153            nodes.push(DendrogramNode {
154                left: a,
155                right: b,
156                distance: node_dist,
157                size: new_size,
158            });
159            // Update distance matrix — Lance-Williams.
160            // Grow the vectors by one row/column.
161            for row in d.iter_mut() {
162                row.push(0.0);
163            }
164            d.push(vec![0.0; n + nodes.len()]);
165            for k in 0..(n + nodes.len() - 1) {
166                if !alive.get(k).copied().unwrap_or(false) || k == a || k == b {
167                    continue;
168                }
169                let d_ak = d[a][k];
170                let d_bk = d[b][k];
171                let d_ab = d[a][b];
172                let (na, nb, nk) = (sizes[a] as f64, sizes[b] as f64, sizes[k] as f64);
173                let new_d = match self.linkage {
174                    Linkage::Single => d_ak.min(d_bk),
175                    Linkage::Complete => d_ak.max(d_bk),
176                    Linkage::Average => (na * d_ak + nb * d_bk) / (na + nb),
177                    Linkage::Ward => {
178                        let total = na + nb + nk;
179                        ((na + nk) * d_ak + (nb + nk) * d_bk - nk * d_ab) / total
180                    }
181                };
182                d[node_id][k] = new_d;
183                d[k][node_id] = new_d;
184            }
185            alive[a] = false;
186            alive[b] = false;
187            alive.push(true);
188            sizes.push(new_size);
189            parent.push(None);
190            parent[a] = Some(node_id);
191            parent[b] = Some(node_id);
192        }
193
194        // Assign labels by walking each original sample up to the highest
195        // live ancestor.
196        let mut root_of = vec![0usize; n];
197        for i in 0..n {
198            let mut cur = i;
199            while let Some(p) = parent[cur] {
200                if alive[p] {
201                    cur = p;
202                    break;
203                }
204                cur = p;
205            }
206            root_of[i] = cur;
207        }
208        // Dense-relabel to [0, n_clusters).
209        let mut label_of = std::collections::BTreeMap::<usize, usize>::new();
210        let mut next_label = 0usize;
211        let mut labels = Array1::<usize>::zeros(n);
212        for i in 0..n {
213            let r = root_of[i];
214            let l = *label_of.entry(r).or_insert_with(|| {
215                let out = next_label;
216                next_label += 1;
217                out
218            });
219            labels[i] = l;
220        }
221        Ok((labels, nodes))
222    }
223}
224
225#[cfg(test)]
226mod tests {
227    use super::*;
228    use ndarray::array;
229
230    #[test]
231    fn recovers_two_well_separated_clusters_with_ward() {
232        let x = array![
233            [0.0, 0.0],
234            [0.1, 0.0],
235            [0.0, 0.1],
236            [0.1, 0.1],
237            [10.0, 10.0],
238            [10.1, 10.0],
239            [10.0, 10.1],
240            [10.1, 10.1],
241        ];
242        let (labels, dendro) = AgglomerativeClustering::new(2, Linkage::Ward)
243            .fit_predict(x.view())
244            .unwrap();
245        assert_eq!(dendro.len(), 6); // n - n_clusters = 8 - 2 = 6
246        let a = labels[0];
247        let b = labels[4];
248        assert_ne!(a, b);
249        for i in 0..4 {
250            assert_eq!(labels[i], a);
251        }
252        for i in 4..8 {
253            assert_eq!(labels[i], b);
254        }
255    }
256
257    #[test]
258    fn single_linkage_is_chain_friendly() {
259        // A chain of points [0, 1, 2, 3, 20] — single linkage sees 4 close
260        // pairs and one outlier; with k=2 the outlier gets its own cluster.
261        let x = array![[0.0], [1.0], [2.0], [3.0], [20.0]];
262        let (labels, _) = AgglomerativeClustering::new(2, Linkage::Single)
263            .fit_predict(x.view())
264            .unwrap();
265        let outlier = labels[4];
266        let others = labels[0];
267        assert_ne!(outlier, others);
268        for i in 0..4 {
269            assert_eq!(labels[i], others);
270        }
271    }
272}