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 PointRole {
Core,
Border,
Noise,
}
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Clone, Debug, PartialEq)]
pub struct DbscanResult {
pub labels: Array1<usize>,
pub roles: Vec<PointRole>,
pub n_clusters: usize,
pub n_noise: usize,
}
#[derive(Clone, Copy, Debug)]
pub struct Dbscan {
pub eps: f64,
pub min_samples: usize,
}
impl Dbscan {
pub fn new(eps: f64, min_samples: usize) -> Self {
Self { eps, min_samples }
}
pub fn fit(&self, x: ArrayView2<'_, f64>) -> Result<DbscanResult> {
if x.nrows() == 0 || x.ncols() == 0 {
return Err(Error::Value(
"Dbscan::fit: x must have at least one row and one column".into(),
));
}
if !(self.eps > 0.0 && self.eps.is_finite()) {
return Err(Error::Value(format!(
"Dbscan::fit: eps must be finite and > 0 (got {})",
self.eps
)));
}
if self.min_samples < 1 {
return Err(Error::Value("Dbscan::fit: min_samples must be ≥ 1".into()));
}
let n = x.nrows();
let neighbours: Vec<Vec<usize>> = (0..n)
.map(|i| {
let mut nbrs = Vec::new();
for j in 0..n {
if i == j {
nbrs.push(j);
continue;
}
let mut dd = 0.0_f64;
for k in 0..x.ncols() {
let diff = x[[i, k]] - x[[j, k]];
dd += diff * diff;
}
if dd.sqrt() <= self.eps {
nbrs.push(j);
}
}
nbrs
})
.collect();
let mut labels = Array1::<usize>::from_elem(n, usize::MAX);
let mut roles = vec![PointRole::Noise; n];
let mut cluster_id = 0usize;
for p in 0..n {
if labels[p] != usize::MAX {
continue;
}
if neighbours[p].len() < self.min_samples {
continue;
}
let c = cluster_id;
cluster_id += 1;
labels[p] = c;
roles[p] = PointRole::Core;
let mut queue: Vec<usize> = neighbours[p].iter().copied().filter(|&i| i != p).collect();
let mut head = 0usize;
while head < queue.len() {
let q = queue[head];
head += 1;
if labels[q] == usize::MAX {
labels[q] = c;
if neighbours[q].len() >= self.min_samples {
roles[q] = PointRole::Core;
for &nb in &neighbours[q] {
if !queue.contains(&nb) {
queue.push(nb);
}
}
} else if roles[q] == PointRole::Noise {
roles[q] = PointRole::Border;
}
} else if roles[q] == PointRole::Noise {
labels[q] = c;
roles[q] = PointRole::Border;
}
}
}
let n_noise = labels.iter().filter(|&&l| l == usize::MAX).count();
Ok(DbscanResult {
labels,
roles,
n_clusters: cluster_id,
n_noise,
})
}
pub fn fit_predict(&self, x: ArrayView2<'_, f64>) -> Result<Array1<usize>> {
Ok(self.fit(x)?.labels)
}
}
#[cfg(test)]
mod tests {
use super::*;
use ndarray::array;
#[test]
fn finds_two_clusters_and_isolates_noise() {
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],
[100.0, 100.0]
];
let r = Dbscan::new(0.5, 3).fit(x.view()).unwrap();
assert_eq!(r.n_clusters, 2);
assert_eq!(r.n_noise, 1);
assert_eq!(r.labels[8], usize::MAX);
for i in 1..4 {
assert_eq!(r.labels[i], r.labels[0]);
}
for i in 5..8 {
assert_eq!(r.labels[i], r.labels[4]);
}
}
#[test]
fn rejects_bad_params() {
let x = array![[1.0]];
assert!(Dbscan::new(-1.0, 3).fit(x.view()).is_err());
assert!(Dbscan::new(1.0, 0).fit(x.view()).is_err());
}
}