Struct linfa_clustering::Dbscan

pub struct Dbscan;

DBSCAN (Density-based Spatial Clustering of Applications with Noise) clusters together points which are close together with enough neighbors labelled points which are sparsely neighbored as noise. As points may be part of a cluster or noise the predict method returns Array1<Option<usize>>

As it groups together points in dense regions the number of clusters is determined by the dataset and distance tolerance not the user.

We provide an implemention of the standard O(N^2) query-based algorithm of which more details can be found in the next section or here.

The standard DBSCAN algorithm isn't iterative and therefore there's no fit method provided only predict.

The algorithm

The algorithm iterates over each point in the dataset and for every point not yet assigned to a cluster:

• Find all points within the neighborhood of size tolerance
• If the number of points in the neighborhood is below a minimum size label as noise
• Otherwise label the point with the cluster ID and repeat with each of the neighbours

Tutorial

Let's do a walkthrough of an example running DBSCAN on some data.

use linfa::traits::Transformer;
use linfa_clustering::{DbscanHyperParams, Dbscan, generate_blobs};
use ndarray::{Axis, array, s};
use ndarray_rand::rand::SeedableRng;
use rand_isaac::Isaac64Rng;
use approx::assert_abs_diff_eq;

// Our random number generator, seeded for reproducibility
let seed = 42;
let mut rng = Isaac64Rng::seed_from_u64(seed);

// `expected_centroids` has shape `(n_centroids, n_features)`
// i.e. three points in the 2-dimensional plane
let expected_centroids = array![[0., 1.], [-10., 20.], [-1., 10.]];
// Let's generate a synthetic dataset: three blobs of observations
// (100 points each) centered around our `expected_centroids`
let observations = generate_blobs(100, &expected_centroids, &mut rng);

// Let's configure and run our DBSCAN algorithm
// We use the builder pattern to specify the hyperparameters
// `min_points` is the only mandatory parameter.
// If you don't specify the others (e.g. `tolerance`)
// default values will be used.
let min_points = 3;
let clusters = Dbscan::params(min_points)
    .tolerance(1e-2)
    .transform(&observations);
// Points are `None` if noise `Some(id)` if belonging to a cluster.

Implementations

impl Dbscan

pub fn params<F: Float>(min_points: usize) -> DbscanHyperParamsBuilder<F>

Trait Implementations

impl Clone for Dbscan

pub fn clone(&self) -> Dbscan

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Dbscan

pub fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl PartialEq<Dbscan> for Dbscan

pub fn eq(&self, other: &Dbscan) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl StructuralPartialEq for Dbscan