use linfa::prelude::*;
use linfa_clustering::{GaussianMixtureModel, KMeans};
use ndarray015::Array2;
use rand::{Rng, SeedableRng};
use rand_xoshiro::Xoshiro256PlusPlus;
fn to_f32_array2(values: Vec<f64>) -> Result<Array2<f32>, String> {
let n = values.len();
let f32_values: Vec<f32> = values.into_iter().map(|v| v as f32).collect();
Array2::from_shape_vec((n, 1), f32_values).map_err(|e| e.to_string())
}
pub fn cluster_kmeans_impl(
values: Vec<f64>,
n_clusters: usize,
max_iter: u64,
tolerance: f64,
seed: u64,
) -> Result<Vec<usize>, String> {
let n = values.len();
if n < n_clusters {
return Err(format!("need at least {n_clusters} samples, got {n}"));
}
let arr = to_f32_array2(values)?;
let dataset = DatasetBase::from(arr);
let rng = Xoshiro256PlusPlus::seed_from_u64(seed);
let model = KMeans::params_with_rng(n_clusters, rng)
.max_n_iterations(max_iter)
.tolerance(tolerance as f32)
.fit(&dataset)
.map_err(|e| e.to_string())?;
Ok(model.predict(&dataset).into_raw_vec())
}
pub fn cluster_standardized_kmeans_impl(
features: &[f64],
n_features: usize,
n_clusters: usize,
max_iter: u64,
tolerance: f64,
seed: u64,
n_init: usize,
) -> Result<Vec<usize>, String> {
if n_features == 0 || !features.len().is_multiple_of(n_features) {
return Err("features must be a non-empty row-major matrix".to_string());
}
let n_rows = features.len() / n_features;
if n_rows < n_clusters {
return Err(format!("need at least {n_clusters} samples, got {n_rows}"));
}
if !features.iter().all(|value| value.is_finite()) {
return Err("features must be finite".to_string());
}
let mut means = vec![0.0; n_features];
for row in features.chunks_exact(n_features) {
for (feature, value) in row.iter().enumerate() {
means[feature] += value;
}
}
for mean in &mut means {
*mean /= n_rows as f64;
}
let mut scales = vec![0.0; n_features];
for row in features.chunks_exact(n_features) {
for (feature, value) in row.iter().enumerate() {
scales[feature] += (value - means[feature]).powi(2);
}
}
for scale in &mut scales {
*scale = (*scale / n_rows as f64).sqrt();
}
let standardized: Vec<f64> = features
.chunks_exact(n_features)
.flat_map(|row| {
row.iter().enumerate().map(|(feature, value)| {
if scales[feature] == 0.0 {
0.0
} else {
(value - means[feature]) / scales[feature]
}
})
})
.collect();
let attempts = n_init.max(1);
let mut best: Option<(f64, Vec<usize>)> = None;
for init in 0..attempts {
let (inertia, labels) = kmeans_plus_plus(
&standardized,
n_rows,
n_features,
n_clusters,
max_iter,
tolerance,
seed.wrapping_add(init as u64),
);
if best
.as_ref()
.is_none_or(|(best_inertia, _)| inertia < *best_inertia)
{
best = Some((inertia, labels));
}
}
Ok(best.expect("at least one K-Means initialisation").1)
}
fn squared_distance(row: &[f64], centroid: &[f64]) -> f64 {
row.iter()
.zip(centroid)
.map(|(value, center)| (value - center).powi(2))
.sum()
}
fn kmeans_plus_plus(
values: &[f64],
n_rows: usize,
n_features: usize,
n_clusters: usize,
max_iter: u64,
tolerance: f64,
seed: u64,
) -> (f64, Vec<usize>) {
if n_features == 2 {
return kmeans_two_dimensions(values, n_rows, n_clusters, max_iter, tolerance, seed);
}
kmeans_plus_plus_generic(
values, n_rows, n_features, n_clusters, max_iter, tolerance, seed,
)
}
fn kmeans_two_dimensions(
values: &[f64],
n_rows: usize,
n_clusters: usize,
max_iter: u64,
tolerance: f64,
seed: u64,
) -> (f64, Vec<usize>) {
let mut rng = Xoshiro256PlusPlus::seed_from_u64(seed);
let mut centroids = Vec::with_capacity(n_clusters * 2);
let first = rng.gen_range(0..n_rows);
centroids.extend_from_slice(&values[first * 2..first * 2 + 2]);
let mut nearest = vec![f64::INFINITY; n_rows];
for _ in 1..n_clusters {
let cx = centroids[centroids.len() - 2];
let cy = centroids[centroids.len() - 1];
let mut total = 0.0;
for index in 0..n_rows {
let dx = values[index * 2] - cx;
let dy = values[index * 2 + 1] - cy;
nearest[index] = nearest[index].min(dx * dx + dy * dy);
total += nearest[index];
}
let selected = if total == 0.0 {
rng.gen_range(0..n_rows)
} else {
let target = rng.r#gen::<f64>() * total;
let mut cumulative = 0.0;
nearest
.iter()
.position(|distance| {
cumulative += distance;
cumulative >= target
})
.unwrap_or(n_rows - 1)
};
centroids.extend_from_slice(&values[selected * 2..selected * 2 + 2]);
}
let mut labels = vec![0; n_rows];
for _ in 0..max_iter {
let mut sums_x = vec![0.0; n_clusters];
let mut sums_y = vec![0.0; n_clusters];
let mut counts = vec![0usize; n_clusters];
for index in 0..n_rows {
let x = values[index * 2];
let y = values[index * 2 + 1];
let mut label = 0;
let mut best_distance = f64::INFINITY;
for cluster in 0..n_clusters {
let dx = x - centroids[cluster * 2];
let dy = y - centroids[cluster * 2 + 1];
let distance = dx * dx + dy * dy;
if distance < best_distance {
best_distance = distance;
label = cluster;
}
}
labels[index] = label;
counts[label] += 1;
sums_x[label] += x;
sums_y[label] += y;
}
let mut max_shift: f64 = 0.0;
for (cluster, &count) in counts.iter().enumerate().take(n_clusters) {
if count == 0 {
continue;
}
let start = cluster * 2;
let next_x = sums_x[cluster] / counts[cluster] as f64;
let next_y = sums_y[cluster] / counts[cluster] as f64;
let dx = centroids[start] - next_x;
let dy = centroids[start + 1] - next_y;
max_shift = max_shift.max(dx * dx + dy * dy);
centroids[start] = next_x;
centroids[start + 1] = next_y;
}
if max_shift <= tolerance * tolerance {
break;
}
}
let inertia = (0..n_rows)
.map(|index| {
let cluster = labels[index];
let dx = values[index * 2] - centroids[cluster * 2];
let dy = values[index * 2 + 1] - centroids[cluster * 2 + 1];
dx * dx + dy * dy
})
.sum();
(inertia, labels)
}
fn kmeans_plus_plus_generic(
values: &[f64],
n_rows: usize,
n_features: usize,
n_clusters: usize,
max_iter: u64,
tolerance: f64,
seed: u64,
) -> (f64, Vec<usize>) {
let mut rng = Xoshiro256PlusPlus::seed_from_u64(seed);
let mut centroids = Vec::with_capacity(n_clusters * n_features);
let first = rng.gen_range(0..n_rows);
centroids.extend_from_slice(&values[first * n_features..(first + 1) * n_features]);
let mut nearest = vec![f64::INFINITY; n_rows];
for _ in 1..n_clusters {
let latest = ¢roids[centroids.len() - n_features..];
let mut total = 0.0;
for (index, row) in values.chunks_exact(n_features).enumerate() {
nearest[index] = nearest[index].min(squared_distance(row, latest));
total += nearest[index];
}
let selected = if total == 0.0 {
rng.gen_range(0..n_rows)
} else {
let target = rng.r#gen::<f64>() * total;
let mut cumulative = 0.0;
nearest
.iter()
.position(|distance| {
cumulative += distance;
cumulative >= target
})
.unwrap_or(n_rows - 1)
};
centroids.extend_from_slice(&values[selected * n_features..(selected + 1) * n_features]);
}
let mut labels = vec![0; n_rows];
for _ in 0..max_iter {
let mut sums = vec![0.0; n_clusters * n_features];
let mut counts = vec![0usize; n_clusters];
for (index, row) in values.chunks_exact(n_features).enumerate() {
let label = (0..n_clusters)
.min_by(|&left, &right| {
squared_distance(row, ¢roids[left * n_features..(left + 1) * n_features])
.total_cmp(&squared_distance(
row,
¢roids[right * n_features..(right + 1) * n_features],
))
})
.expect("at least one cluster");
labels[index] = label;
counts[label] += 1;
for (feature, value) in row.iter().enumerate() {
sums[label * n_features + feature] += value;
}
}
let mut max_shift: f64 = 0.0;
for (cluster, &count) in counts.iter().enumerate().take(n_clusters) {
if count == 0 {
continue;
}
let start = cluster * n_features;
let previous = centroids[start..start + n_features].to_vec();
for feature in 0..n_features {
centroids[start + feature] = sums[start + feature] / count as f64;
}
max_shift = max_shift.max(squared_distance(
&previous,
¢roids[start..start + n_features],
));
}
if max_shift <= tolerance * tolerance {
break;
}
}
let inertia = values
.chunks_exact(n_features)
.zip(&labels)
.map(|(row, &label)| {
squared_distance(
row,
¢roids[label * n_features..(label + 1) * n_features],
)
})
.sum();
(inertia, labels)
}
pub fn cluster_gmm_impl(
values: Vec<f64>,
n_clusters: usize,
max_iter: u64,
tolerance: f64,
seed: u64,
) -> Result<Vec<usize>, String> {
let n = values.len();
if n < n_clusters {
return Err(format!("need at least {n_clusters} samples, got {n}"));
}
let arr = to_f32_array2(values)?;
let dataset = DatasetBase::from(arr);
let rng = Xoshiro256PlusPlus::seed_from_u64(seed);
let model = GaussianMixtureModel::params(n_clusters)
.max_n_iterations(max_iter)
.tolerance(tolerance as f32)
.with_rng(rng)
.fit(&dataset)
.map_err(|e| e.to_string())?;
Ok(model.predict(&dataset).into_raw_vec())
}