1use ndarray::{Array1, ArrayView2};
26use solow_core::{Error, Result};
27
28#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
30#[derive(Copy, Clone, Debug, PartialEq, Eq)]
31pub enum Linkage {
32 Single,
34 Complete,
36 Average,
38 Ward,
40}
41
42#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
44#[derive(Clone, Copy, Debug, PartialEq)]
45pub struct DendrogramNode {
46 pub left: usize,
48 pub right: usize,
50 pub distance: f64,
52 pub size: usize,
54}
55
56#[derive(Clone, Copy, Debug)]
58pub struct AgglomerativeClustering {
59 pub n_clusters: usize,
61 pub linkage: Linkage,
63}
64
65impl AgglomerativeClustering {
66 pub fn new(n_clusters: usize, linkage: Linkage) -> Self {
68 Self {
69 n_clusters,
70 linkage,
71 }
72 }
73
74 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 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 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]; 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 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 (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 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 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 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); 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 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}