use ndarray::{Array1, ArrayView2};
use solow_core::{Error, Result};
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum Linkage {
Single,
Complete,
Average,
Ward,
}
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct DendrogramNode {
pub left: usize,
pub right: usize,
pub distance: f64,
pub size: usize,
}
#[derive(Clone, Copy, Debug)]
pub struct AgglomerativeClustering {
pub n_clusters: usize,
pub linkage: Linkage,
}
impl AgglomerativeClustering {
pub fn new(n_clusters: usize, linkage: Linkage) -> Self {
Self {
n_clusters,
linkage,
}
}
pub fn fit_predict(
&self,
x: ArrayView2<'_, f64>,
) -> Result<(Array1<usize>, Vec<DendrogramNode>)> {
let n = x.nrows();
if n == 0 || x.ncols() == 0 {
return Err(Error::Value(
"AgglomerativeClustering::fit_predict: x must have at least one row and one column"
.into(),
));
}
if self.n_clusters == 0 || self.n_clusters > n {
return Err(Error::Value(format!(
"AgglomerativeClustering::fit_predict: n_clusters must be in [1, n] (got {}, n={n})",
self.n_clusters
)));
}
let mut d = vec![vec![0.0_f64; n]; n];
for i in 0..n {
for j in (i + 1)..n {
let mut s = 0.0_f64;
for k in 0..x.ncols() {
let diff = x[[i, k]] - x[[j, k]];
s += diff * diff;
}
let dist = if matches!(self.linkage, Linkage::Ward) {
s
} else {
s.sqrt()
};
d[i][j] = dist;
d[j][i] = dist;
}
}
let mut sizes = vec![1usize; n];
let mut alive: Vec<bool> = vec![true; n];
let mut parent: Vec<Option<usize>> = vec![None; n]; let mut nodes: Vec<DendrogramNode> = Vec::with_capacity(n - 1);
let target_merges = if self.n_clusters == 0 {
n - 1
} else {
n - self.n_clusters
};
for merge_idx in 0..(n - 1) {
if merge_idx >= target_merges {
break;
}
let mut best = (0usize, 0usize);
let mut best_d = f64::INFINITY;
for i in 0..(n + nodes.len()) {
if i >= alive.len() || !alive[i] {
continue;
}
for j in (i + 1)..(n + nodes.len()) {
if j >= alive.len() || !alive[j] {
continue;
}
if d[i][j] < best_d {
best_d = d[i][j];
best = (i, j);
}
}
}
let (a, b) = best;
let new_size = sizes[a] + sizes[b];
let node_id = n + nodes.len();
let node_dist = if matches!(self.linkage, Linkage::Ward) {
(best_d).sqrt()
} else {
best_d
};
nodes.push(DendrogramNode {
left: a,
right: b,
distance: node_dist,
size: new_size,
});
for row in d.iter_mut() {
row.push(0.0);
}
d.push(vec![0.0; n + nodes.len()]);
for k in 0..(n + nodes.len() - 1) {
if !alive.get(k).copied().unwrap_or(false) || k == a || k == b {
continue;
}
let d_ak = d[a][k];
let d_bk = d[b][k];
let d_ab = d[a][b];
let (na, nb, nk) = (sizes[a] as f64, sizes[b] as f64, sizes[k] as f64);
let new_d = match self.linkage {
Linkage::Single => d_ak.min(d_bk),
Linkage::Complete => d_ak.max(d_bk),
Linkage::Average => (na * d_ak + nb * d_bk) / (na + nb),
Linkage::Ward => {
let total = na + nb + nk;
((na + nk) * d_ak + (nb + nk) * d_bk - nk * d_ab) / total
}
};
d[node_id][k] = new_d;
d[k][node_id] = new_d;
}
alive[a] = false;
alive[b] = false;
alive.push(true);
sizes.push(new_size);
parent.push(None);
parent[a] = Some(node_id);
parent[b] = Some(node_id);
}
let mut root_of = vec![0usize; n];
for i in 0..n {
let mut cur = i;
while let Some(p) = parent[cur] {
if alive[p] {
cur = p;
break;
}
cur = p;
}
root_of[i] = cur;
}
let mut label_of = std::collections::BTreeMap::<usize, usize>::new();
let mut next_label = 0usize;
let mut labels = Array1::<usize>::zeros(n);
for i in 0..n {
let r = root_of[i];
let l = *label_of.entry(r).or_insert_with(|| {
let out = next_label;
next_label += 1;
out
});
labels[i] = l;
}
Ok((labels, nodes))
}
}
#[cfg(test)]
mod tests {
use super::*;
use ndarray::array;
#[test]
fn recovers_two_well_separated_clusters_with_ward() {
let x = array![
[0.0, 0.0],
[0.1, 0.0],
[0.0, 0.1],
[0.1, 0.1],
[10.0, 10.0],
[10.1, 10.0],
[10.0, 10.1],
[10.1, 10.1],
];
let (labels, dendro) = AgglomerativeClustering::new(2, Linkage::Ward)
.fit_predict(x.view())
.unwrap();
assert_eq!(dendro.len(), 6); let a = labels[0];
let b = labels[4];
assert_ne!(a, b);
for i in 0..4 {
assert_eq!(labels[i], a);
}
for i in 4..8 {
assert_eq!(labels[i], b);
}
}
#[test]
fn single_linkage_is_chain_friendly() {
let x = array![[0.0], [1.0], [2.0], [3.0], [20.0]];
let (labels, _) = AgglomerativeClustering::new(2, Linkage::Single)
.fit_predict(x.view())
.unwrap();
let outlier = labels[4];
let others = labels[0];
assert_ne!(outlier, others);
for i in 0..4 {
assert_eq!(labels[i], others);
}
}
}