2.8. DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) groups points that sit in dense regions. It labels the rest as noise. Unlike KMeans, DBSCAN does not need the number of clusters up front. It finds clusters of any shape, not only round blobs, and it marks outliers explicitly. In exchange, you set 2 density parameters, eps and min_samples, instead of k. This page covers the density model RustyML implements, a method to pick eps, what predict does, and the cost of the O(n^2) algorithm.

2.8.1. The density model: core, border, and noise points

DBSCAN assigns every training point one of 3 roles. The 2 parameters eps (the neighborhood radius) and min_samples (the density threshold) decide the role.

A point’s neighborhood is every point within eps of it. The boundary is inclusive, so a point at distance exactly eps counts as a neighbor. RustyML’s neighborhood query also counts the point itself, since its distance to itself is 0, and 0 is always <= eps. This fact sets the meaning of min_samples:

So min_samples counts the query point itself, the same way scikit-learn counts it. If you count a neighbor as only another nearby point, not the point itself, subtract 1 from min_samples. With min_samples = 2, any point with 1 other point within eps becomes a core point.

Clusters form by density connectivity. fit starts at an unvisited core point, claims it, then floods through the neighborhoods of core points and absorbs every point it reaches. A border point joins the cluster but does not extend the flood, because fit does not expand a border point’s neighborhood. Any point the flood never reaches stays -1.

2 facts follow from this design. First, fit has no random number generator, so the clustering is fully deterministic. fit processes points in ascending row order, and each neighbor list comes back sorted by index. The same input always produces the same labels and the same cluster ids. Second, when a border point sits within reach of 2 clusters, the cluster whose flood reaches the point first claims it. Because fit processes rows in order, that is the cluster with the lower id. This resolves the classic DBSCAN border ambiguity in a deterministic way instead of leaving it undefined.

2.8.2. Constructing and configuring the estimator

The constructor takes the 2 density parameters and validates them:

pub fn new(eps: f64, min_samples: usize) -> Result<Self, Error>
pub fn with_metric(self, metric: DistanceCalculationMetric) -> Result<Self, Error>

new returns Error::InvalidParameter if eps is non-positive or non-finite, or if min_samples is 0. The distance metric defaults to Euclidean. Change it with with_metric, which also returns Result because it validates the Minkowski order (see section 2.8.4). Default::default() gives eps = 0.5, min_samples = 5, and Euclidean. These numbers are placeholders. They are not good defaults for your data.

Getters expose the stored state after construction: get_epsilon, get_min_samples, and get_metric. Once the model is fitted, it also exposes get_labels() -> Option<&Array1<isize>> and get_core_sample_indices() -> Option<&Array1<usize>>. See Error Handling for how the error variants map to real failures.

2.8.3. Fitting and reading the labels

fit runs the clustering and stores the result. fit_predict does the same and also returns the label array. get_labels reads the stored labels after that. Labels have type Array1<isize>. Cluster ids run 0, 1, 2, ... in discovery order, and -1 marks noise. The signed isize type lets DBSCAN store noise in the same array as the cluster ids, with no separate mask.

use rustyml::machine_learning::DBSCAN;
use ndarray::Array2;

fn main() {
    // Two tight blobs plus one isolated point.
    let data = Array2::from_shape_vec(
        (9, 2),
        vec![
            0.0, 0.0, 0.1, 0.0, 0.0, 0.1, 0.1, 0.1, // blob A near the origin
            10.0, 10.0, 10.1, 10.0, 10.0, 10.1, 10.1, 10.1, // blob B near (10, 10)
            5.0, 5.0, // noise: far from both blobs
        ],
    )
    .unwrap();

    let mut dbscan = DBSCAN::new(0.5, 2).unwrap();
    let labels = dbscan.fit_predict(&data).unwrap();

    let n_clusters = labels.iter().filter(|&&l| l >= 0).map(|&l| l).max().map_or(0, |m| m + 1);
    let n_noise = labels.iter().filter(|&&l| l == -1).count();
    println!("labels     = {:?}", labels);
    println!("clusters   = {}", n_clusters);
    println!("noise pts  = {}", n_noise);

    // core_sample_indices holds only the rows that qualified as core points, sorted ascending.
    let cores = dbscan.get_core_sample_indices().unwrap();
    println!("core rows  = {:?}", cores);
}

Blob A becomes cluster 0, because fit discovers it first. Blob B becomes cluster 1. The lone point at (5, 5) stays -1. With min_samples = 2 and 4 points per blob, every blob point is a core point. So core_sample_indices is [0,1,2,3,4,5,6,7], and the noise row is absent.

labels     = [0, 0, 0, 0, 1, 1, 1, 1, -1], shape=[9], strides=[1], layout=CFcf (0xf), const ndim=1
clusters   = 2
noise pts  = 1
core rows  = [0, 1, 2, 3, 4, 5, 6, 7], shape=[8], strides=[1], layout=CFcf (0xf), const ndim=1

fit validates the input before it does any work. A zero-row matrix gives Error::EmptyInput. Any NaN or infinite value in the data gives Error::NonFinite. This shows the split of responsibility. A bad hyperparameter, such as a non-finite eps, gives InvalidParameter at construction. A bad value in the data gives NonFinite at fit time.

2.8.4. Distance metrics

with_metric accepts the 3 variants of DistanceCalculationMetric: Euclidean (the default, L2), Manhattan (L1), and Minkowski(p) (the general Lp norm). Minkowski(2.0) gives the same labels as Euclidean. Minkowski(1.0) gives the same labels as Manhattan. Use the named variants for L1 or L2. Reserve Minkowski for a fractional or higher order.

use rustyml::machine_learning::{DBSCAN, DistanceCalculationMetric};
use ndarray::array;

fn main() {
    let data = array![
        [0.0, 0.0], [0.1, 0.0], [0.0, 0.1],
        [5.0, 5.0], [5.1, 5.0], [5.0, 5.1],
    ];

    let mut dbscan = DBSCAN::new(0.5, 2)
        .unwrap()
        .with_metric(DistanceCalculationMetric::Manhattan)
        .unwrap();
    let labels = dbscan.fit_predict(&data).unwrap();
    println!("{:?}", labels); // two clusters, no noise
}

The constructor rejects a Minkowski order below 1 (including 0.5) or a non-finite order. Such an order breaks the triangle inequality, and that would break the neighborhood test. Changing the metric changes the units of eps, not only its meaning. The same points span a larger Manhattan distance than a Euclidean distance, so an eps tuned for one metric is wrong for another. Retune eps after every metric change. See Distance Metrics for the metric definitions and their tradeoffs.

2.8.5. Choosing eps: the k-distance heuristic

eps is the parameter people set wrong most often. This section gives a concrete method to pick it, instead of trial and error. For each point, measure the distance to its k-th nearest neighbor. Take k = min_samples, and count the point itself, so index 0 is the point at distance 0. Sort all the k-distances in ascending order and look at the curve. Points inside a dense cluster have a small k-distance. Noise points have a large one. The curve stays flat and low across the clustered points, then bends sharply upward at the “knee” as it starts to hit outliers. The k-distance at that knee makes a good eps value. It is large enough to connect real clusters, and small enough to leave outliers isolated.

This sorting step mirrors what a KNN query returns. You can compute the k-distances directly with the public metric dispatcher:

use rustyml::machine_learning::DistanceCalculationMetric;
use ndarray::array;

fn main() {
    // Dense cluster of 5 points plus 2 scattered outliers.
    let data = array![
        [0.0, 0.0], [0.2, 0.1], [0.1, 0.2], [0.3, 0.0], [0.0, 0.3],
        [4.0, 4.0], [8.0, 1.0],
    ];

    let metric = DistanceCalculationMetric::Euclidean;
    let min_samples = 3usize; // k for the k-distance graph
    let n = data.nrows();

    // k-distance of each point: the distance to its k-th nearest neighbor (self included).
    let mut k_dists: Vec<f64> = (0..n)
        .map(|i| {
            let mut d: Vec<f64> = (0..n)
                .map(|j| metric.distance(data.row(i), data.row(j)))
                .collect();
            d.sort_by(|a, b| a.partial_cmp(b).unwrap());
            d[min_samples - 1] // index 0 is self (distance 0)
        })
        .collect();

    k_dists.sort_by(|a, b| a.partial_cmp(b).unwrap());
    // Read the curve from left to right. The sharp rise near the end marks the knee.
    println!("sorted k-distances: {:?}", k_dists);
}

The flat prefix of the printed curve corresponds to the clustered points. Pick eps where the curve turns up. Reserve min_samples for the density floor. A common starting point is 2 * n_features. Raise it for noisy data, because more required neighbors means stricter noise rejection. Lower it toward n_features + 1 for clean, low-dimensional data. RustyML counts the point itself, so min_samples = 1 makes every point a core point. That produces 0 noise points, which is rarely what you want.

2.8.6. What predict does, and why it is not classic DBSCAN

Textbook DBSCAN has no predict method for new points. This gap is fundamental, not an oversight. Cluster membership in DBSCAN is transductive. A point’s label depends on the density of the whole neighborhood. Adding a new point to the data could turn it into a core point. It could also join 2 separate clusters into one, or shift where a border falls. There is no way to label a new point correctly without a new density analysis over the combined set.

RustyML still offers a predict method. It does something narrower and cheaper than a new density analysis. This section states exactly what it does:

use rustyml::machine_learning::DBSCAN;
use ndarray::array;

fn main() {
    let train = 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 mut dbscan = DBSCAN::new(0.5, 2).unwrap();
    dbscan.fit(&train).unwrap();

    // Assign each new point to the cluster of its nearest core point, if within eps.
    let queries = array![
        [0.05, 0.05],   // inside blob A  -> 0
        [10.05, 10.05], // inside blob B  -> 1
        [5.0, 5.0],     // far from all cores -> noise (-1)
    ];
    let preds = dbscan.predict(&queries).unwrap();
    println!("{:?}", preds); // preds is [0, 1, -1], one label per query.
}

predict finds each query’s nearest core point. It searches the core points saved during fit, not the full training set. It returns that core point’s cluster label if the query is within eps. Otherwise, it returns -1. predict picks the single nearest core point. It does not check every core point within eps. The eps gate is inclusive. predict never creates a new cluster, never promotes a query to a core point, and never runs the density flood again. So predict(x) does not give the same result as adding x to the training data and calling fit again. Treat predict as a fast, approximate way to assign held-out points to clusters fit already found. Call fit again on the enlarged set to get true DBSCAN semantics.

Calling predict before fit gives Error::NotFitted. A feature-count mismatch gives Error::DimensionMismatch. A non-finite query value gives Error::NonFinite. Empty input returns an empty array.

2.8.7. Two rings where KMeans fails

Shape is the main reason to choose DBSCAN over KMeans. KMeans partitions space with straight boundaries around k centroids, so it can only carve out convex, roughly round regions. DBSCAN follows density, so it can trace any shape. Two concentric rings show the difference clearly. The rings are not linearly separable around their shared center. KMeans cuts straight through both rings, while DBSCAN walks each ring as a connected chain.

use rustyml::machine_learning::{DBSCAN, KMeans};
use ndarray::Array2;

fn main() {
    // Build 2 concentric rings: inner radius 1, outer radius 4.
    let mut coords: Vec<f64> = Vec::new();
    let inner = 12usize;
    for k in 0..inner {
        let t = k as f64 / inner as f64 * std::f64::consts::TAU;
        coords.push(t.cos());
        coords.push(t.sin());
    }
    let outer = 28usize;
    for k in 0..outer {
        let t = k as f64 / outer as f64 * std::f64::consts::TAU;
        coords.push(4.0 * t.cos());
        coords.push(4.0 * t.sin());
    }
    let data = Array2::from_shape_vec((inner + outer, 2), coords).unwrap();

    // eps covers each ring's neighbor spacing but not the >= 3-unit gap between rings.
    let mut dbscan = DBSCAN::new(1.2, 2).unwrap();
    let db = dbscan.fit_predict(&data).unwrap();
    let db_clusters = db.iter().filter(|&&l| l >= 0).map(|&l| l).max().map_or(0, |m| m + 1);
    let db_noise = db.iter().filter(|&&l| l == -1).count();

    // KMeans with k = 2 (seeded for reproducibility).
    let mut km = KMeans::new(2, 100, 1e-4).unwrap().with_random_state(0);
    let km_labels = km.fit_predict(&data).unwrap();
    // km_inner0 and km_outer0 count how KMeans cluster 0 splits across the 2 rings.
    let km_inner0 = (0..inner).filter(|&i| km_labels[i] == 0).count();
    let km_outer0 = (inner..inner + outer).filter(|&i| km_labels[i] == 0).count();

    println!("DBSCAN: {} clusters, {} noise", db_clusters, db_noise);
    println!("KMeans cluster 0: {} inner-ring + {} outer-ring points", km_inner0, km_outer0);
}

DBSCAN recovers the 2 rings exactly. It finds 2 clusters and 0 noise points, with the inner ring as one label and the outer ring as the other. KMeans splits the plane with a line through the origin. So each of its 2 clusters mixes inner-ring and outer-ring points. KMeans cannot represent a ring at all.

DBSCAN: 2 clusters, 0 noise
KMeans cluster 0: 6 inner-ring + 14 outer-ring points

See Clustering Metrics to score these results with ground-truth labels or an intrinsic metric.

2.8.8. Cost, indexing, and parallelism

Naive DBSCAN runs in O(n^2) time. Every point runs a region query, and a brute-force region query scans all n points. RustyML lowers the constant with a kd-tree. During fit, RustyML builds one kd-tree over the data and answers each region query in about O(log n) average time. This only applies when the data has at most 8 features (DBSCAN_KD_TREE_MAX_DIMS). Above 8 dimensions, a kd-tree stops pruning well, because of the curse of dimensionality (almost every point looks “far” from every other point). So fit falls back to a brute-force scan. Clustering stays correct on that path, only slower. Reduce dimensionality first with PCA or t-SNE before you use high-dimensional data. This speeds up the index, and Euclidean neighborhoods lose meaning in high dimensions regardless of the index.

The brute-force region query runs in parallel across neighbors with rayon. This happens when the scan work (n_samples * n_features) clears a calibrated element gate (262_144 by default). The cluster-expansion loop stays sequential, because it is a flood-fill. So parallelism speeds up each region scan, not the overall control flow. predict runs in parallel over query points when n_queries * n_core_points * n_features clears the same gate. You can tune these gates through the crate::tuning facade, with no recompile needed. See Performance Tuning and Parallelism for how, and Parallel Reductions for the gate mechanism. As a guardrail, if a pathological dataset produces isize::MAX clusters, fit returns Error::Computation instead of an overflow in the label counter.

DBSCAN gives you clusters of any shape, automatic outlier detection, and no k to guess. In exchange, it costs quadratic time in the worst case. The kd-tree lowers this cost in low dimensions but does not remove it. DBSCAN is also sensitive to eps when clusters have different densities. A single global eps cannot fit both a dense cluster and a sparse cluster at once.

2.8.9. Persistence

A fitted DBSCAN serializes with save_to_path and load_from_path. Both methods use the compact postcard binary format. The saved data includes the hyperparameters and the fitted state that predict needs: the stored core points and their labels. A reloaded model predicts the same labels, with no need to see the original training set again.

use rustyml::machine_learning::DBSCAN;
use ndarray::array;

fn main() {
    let data = 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 mut dbscan = DBSCAN::new(0.5, 2).unwrap();
    dbscan.fit(&data).unwrap();

    let path = "dbscan_model.bin";
    dbscan.save_to_path(path).unwrap();

    let loaded = DBSCAN::load_from_path(path).unwrap();
    let preds = loaded.predict(&array![[0.05, 0.05], [10.05, 10.05], [5.0, 5.0]]).unwrap();
    println!("{:?}", preds); // preds is [0, 1, -1], the same labels fit produced.

    std::fs::remove_file(path).unwrap();
}

See Model Persistence in Depth for the format details, versioning caveats, and how persistence interacts with the rest of the crate.