use ndarray::{Array1, Array2, ArrayView2};
use solow_core::{Error, Result};
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum KMeansInit {
Random,
KMeansPlusPlus,
}
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Clone, Debug, PartialEq)]
pub struct KMeansResult {
pub centroids: Array2<f64>,
pub labels: Array1<usize>,
pub inertia: f64,
pub n_iter: usize,
pub converged: bool,
}
#[derive(Clone, Debug)]
pub struct KMeans {
pub k: usize,
pub init: KMeansInit,
pub n_init: usize,
pub max_iter: usize,
pub tol: f64,
pub seed: u64,
}
impl KMeans {
pub fn new(k: usize, seed: u64) -> Self {
Self {
k,
init: KMeansInit::KMeansPlusPlus,
n_init: 10,
max_iter: 300,
tol: 1e-4,
seed,
}
}
pub fn n_init(mut self, n: usize) -> Self {
self.n_init = n;
self
}
pub fn max_iter(mut self, m: usize) -> Self {
self.max_iter = m;
self
}
pub fn tol(mut self, t: f64) -> Self {
self.tol = t;
self
}
pub fn init(mut self, i: KMeansInit) -> Self {
self.init = i;
self
}
pub fn fit(&self, x: ArrayView2<'_, f64>) -> Result<KMeansResult> {
let (n, d) = (x.nrows(), x.ncols());
if n == 0 || d == 0 {
return Err(Error::Value(
"KMeans::fit: x must have at least one row and one column".into(),
));
}
if self.k == 0 || self.k > n {
return Err(Error::Value(format!(
"KMeans::fit: k must be in [1, n] (got k={}, n={n})",
self.k
)));
}
let mut best: Option<KMeansResult> = None;
for restart in 0..self.n_init.max(1) {
let sub_seed = self
.seed
.wrapping_add((restart as u64).wrapping_mul(0x9E37_79B9_7F4A_7C15));
let mut centroids = initial_centroids(x, self.k, self.init, sub_seed)?;
let mut labels = Array1::<usize>::zeros(n);
let mut converged = false;
let mut iter_count = 0usize;
for it in 0..self.max_iter {
iter_count = it + 1;
assign(x, centroids.view(), &mut labels);
let new_centroids = update(x, &labels, self.k, centroids.view())?;
let mut max_shift = 0.0_f64;
for r in 0..self.k {
let mut s = 0.0_f64;
for j in 0..d {
let dd = new_centroids[[r, j]] - centroids[[r, j]];
s += dd * dd;
}
let s = s.sqrt();
if s > max_shift {
max_shift = s;
}
}
centroids = new_centroids;
if max_shift <= self.tol {
converged = true;
break;
}
}
assign(x, centroids.view(), &mut labels);
let inertia = compute_inertia(x, centroids.view(), &labels);
let candidate = KMeansResult {
centroids,
labels,
inertia,
n_iter: iter_count,
converged,
};
match &best {
None => best = Some(candidate),
Some(b) if candidate.inertia < b.inertia => best = Some(candidate),
_ => {}
}
}
Ok(best.unwrap())
}
pub fn fit_predict(&self, x: ArrayView2<'_, f64>) -> Result<Array1<usize>> {
Ok(self.fit(x)?.labels)
}
}
fn assign(x: ArrayView2<'_, f64>, centroids: ArrayView2<'_, f64>, labels: &mut Array1<usize>) {
for i in 0..x.nrows() {
let mut best = 0usize;
let mut best_d = f64::INFINITY;
for c in 0..centroids.nrows() {
let mut dd = 0.0_f64;
for j in 0..x.ncols() {
let diff = x[[i, j]] - centroids[[c, j]];
dd += diff * diff;
}
if dd < best_d {
best_d = dd;
best = c;
}
}
labels[i] = best;
}
}
fn update(
x: ArrayView2<'_, f64>,
labels: &Array1<usize>,
k: usize,
prev: ArrayView2<'_, f64>,
) -> Result<Array2<f64>> {
let d = x.ncols();
let mut sums = Array2::<f64>::zeros((k, d));
let mut counts = vec![0usize; k];
for i in 0..x.nrows() {
let c = labels[i];
counts[c] += 1;
for j in 0..d {
sums[[c, j]] += x[[i, j]];
}
}
let mut out = Array2::<f64>::zeros((k, d));
for c in 0..k {
if counts[c] == 0 {
for j in 0..d {
out[[c, j]] = prev[[c, j]];
}
} else {
for j in 0..d {
out[[c, j]] = sums[[c, j]] / counts[c] as f64;
}
}
}
Ok(out)
}
fn compute_inertia(
x: ArrayView2<'_, f64>,
centroids: ArrayView2<'_, f64>,
labels: &Array1<usize>,
) -> f64 {
let mut total = 0.0_f64;
for i in 0..x.nrows() {
let c = labels[i];
for j in 0..x.ncols() {
let diff = x[[i, j]] - centroids[[c, j]];
total += diff * diff;
}
}
total
}
fn initial_centroids(
x: ArrayView2<'_, f64>,
k: usize,
init: KMeansInit,
seed: u64,
) -> Result<Array2<f64>> {
match init {
KMeansInit::Random => random_init(x, k, seed),
KMeansInit::KMeansPlusPlus => kpp_init(x, k, seed),
}
}
fn random_init(x: ArrayView2<'_, f64>, k: usize, seed: u64) -> Result<Array2<f64>> {
let n = x.nrows();
let mut state = seed.wrapping_add(0xA0B1_C2D3_E4F5_0617);
let mut chosen = std::collections::HashSet::<usize>::new();
while chosen.len() < k {
chosen.insert(uniform_index(&mut state, n as u64));
}
let mut centroids = Array2::<f64>::zeros((k, x.ncols()));
for (r, &i) in chosen.iter().enumerate() {
for j in 0..x.ncols() {
centroids[[r, j]] = x[[i, j]];
}
}
Ok(centroids)
}
fn kpp_init(x: ArrayView2<'_, f64>, k: usize, seed: u64) -> Result<Array2<f64>> {
let (n, d) = (x.nrows(), x.ncols());
let mut state = seed.wrapping_add(0xBEEF_D06E_1234_5678);
let mut centroids = Array2::<f64>::zeros((k, d));
let first = uniform_index(&mut state, n as u64);
for j in 0..d {
centroids[[0, j]] = x[[first, j]];
}
let mut d2 = vec![f64::INFINITY; n];
for i in 0..n {
let mut dd = 0.0_f64;
for j in 0..d {
let diff = x[[i, j]] - centroids[[0, j]];
dd += diff * diff;
}
d2[i] = dd;
}
for c in 1..k {
let total: f64 = d2.iter().sum();
if total <= 0.0 {
let pick = uniform_index(&mut state, n as u64);
for j in 0..d {
centroids[[c, j]] = x[[pick, j]];
}
} else {
let target = uniform_f64(&mut state) * total;
let mut acc = 0.0_f64;
let mut pick = 0usize;
for (i, &dd) in d2.iter().enumerate() {
acc += dd;
if acc >= target {
pick = i;
break;
}
}
for j in 0..d {
centroids[[c, j]] = x[[pick, j]];
}
}
for i in 0..n {
let mut dd = 0.0_f64;
for j in 0..d {
let diff = x[[i, j]] - centroids[[c, j]];
dd += diff * diff;
}
if dd < d2[i] {
d2[i] = dd;
}
}
}
Ok(centroids)
}
fn lcg_next(state: &mut u64) -> u64 {
*state = state
.wrapping_mul(6_364_136_223_846_793_005)
.wrapping_add(1_442_695_040_888_963_407);
*state
}
fn uniform_index(state: &mut u64, n: u64) -> usize {
let max = u64::MAX - (u64::MAX % n);
loop {
let r = lcg_next(state);
if r < max {
return (r % n) as usize;
}
}
}
fn uniform_f64(state: &mut u64) -> f64 {
(lcg_next(state) >> 11) as f64 / ((1u64 << 53) as f64)
}
#[cfg(test)]
mod tests {
use super::*;
use approx::assert_abs_diff_eq;
use ndarray::array;
#[test]
fn recovers_two_well_separated_clusters() {
let mut rows: Vec<[f64; 2]> = Vec::new();
for i in 0..30 {
rows.push([(i as f64 * 0.01).sin(), (i as f64 * 0.017).cos()]);
}
for i in 0..30 {
rows.push([
10.0 + (i as f64 * 0.03).sin(),
10.0 + (i as f64 * 0.019).cos(),
]);
}
let flat: Vec<f64> = rows.into_iter().flatten().collect();
let x = Array2::from_shape_vec((60, 2), flat).unwrap();
let km = KMeans::new(2, 42);
let r = km.fit(x.view()).unwrap();
let a = r.labels[0];
let b = r.labels[30];
assert_ne!(a, b);
for i in 0..30 {
assert_eq!(r.labels[i], a);
}
for i in 30..60 {
assert_eq!(r.labels[i], b);
}
assert!(r.inertia < 5.0);
}
#[test]
fn is_deterministic_by_seed() {
let x = array![
[1.0, 2.0],
[1.1, 2.1],
[0.9, 1.9],
[5.0, 6.0],
[5.2, 6.1],
[4.9, 5.8]
];
let a = KMeans::new(2, 7).fit(x.view()).unwrap();
let b = KMeans::new(2, 7).fit(x.view()).unwrap();
assert_eq!(a.labels, b.labels);
for (u, v) in a.centroids.iter().zip(b.centroids.iter()) {
assert_abs_diff_eq!(u, v, epsilon = 1e-12);
}
}
#[test]
fn rejects_impossible_k() {
let x = array![[1.0], [2.0]];
assert!(KMeans::new(5, 0).fit(x.view()).is_err());
}
}