# 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](./2.7._KMeans_Clustering.md), 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`:
| Role | Definition in this implementation |
|------|-----------------------------------|
| **Core point** | Its neighborhood has at least `min_samples` points, counting itself. So at least `min_samples - 1` other points lie within `eps`. |
| **Border point** | Not a core point, but within `eps` of a core point. It joins that core point's cluster. |
| **Noise point** | Neither core nor border. Labeled `-1`. |
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:
```rust,ignore
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.
| Parameter | Type | Meaning | Validation |
|-----------|------|---------|------------|
| `eps` | `f64` | Neighborhood radius, in the metric's units | must be positive and finite |
| `min_samples` | `usize` | Neighborhood size (including self) for a core point | must be `> 0` |
| `metric` | `DistanceCalculationMetric` | Distance function | Minkowski `p` must be `>= 1` and finite |
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](../Chapter-01/1.6._Error_Handling.md) 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.
```rust
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.
```text
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.
```rust
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](../Chapter-06/6.1._Distance_Metrics.md) 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](./2.3._K_Nearest_Neighbors.md) query returns. You can compute the k-distances directly with the public metric dispatcher:
```rust
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:
```rust
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.
```rust
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.
```text
DBSCAN: 2 clusters, 0 noise
KMeans cluster 0: 6 inner-ring + 14 outer-ring points
```
See [Clustering Metrics](../Chapter-05/5.3._Clustering_Metrics.md) 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](./2.10._Principal_Component_Analysis.md) or [t-SNE](./2.12._t-SNE.md) 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](https://docs.rs/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](../Chapter-07/7.3._Performance_Tuning_and_Parallelism.md) for how, and [Parallel Reductions](../Chapter-06/6.3._Parallel_Reductions.md) 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](https://docs.rs/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.
```rust
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](../Chapter-07/7.2._Model_Persistence_in_Depth.md) for the format details, versioning caveats, and how persistence interacts with the rest of the crate.