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::*;
use linfa_clustering::{DbscanParams, Dbscan};
use linfa_datasets::generate;
use ndarray::{Axis, array, s};
use ndarray_rand::rand::SeedableRng;
use rand_xoshiro::Xoshiro256Plus;
use approx::assert_abs_diff_eq;

// Our random number generator, seeded for reproducibility
let seed = 42;
let mut rng = Xoshiro256Plus::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)
    .unwrap();
// Points are `None` if noise `Some(id)` if belonging to a cluster.

Implementations

impl Dbscan

pub fn params<F: Float>( min_points: usize ) -> DbscanParams<F, L2Dist, CommonNearestNeighbour>

Configures the hyperparameters with the minimum number of points required to form a cluster

Defaults are provided if the optional parameters are not specified:

• tolerance = 1e-4
• dist_fn = L2Dist (Euclidean distance)
• nn_algo = KdTree

pub fn params_with<F: Float, D: Distance<F>, N: NearestNeighbour>( min_points: usize, dist_fn: D, nn_algo: N ) -> DbscanParams<F, D, N>

Configures the hyperparameters with the minimum number of points, a custom distance metric, and a custom nearest neighbour algorithm

Trait Implementations

impl Clone for Dbscan

fn clone(&self) -> Dbscan

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Dbscan

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

Formats the value using the given formatter.

impl PartialEq for Dbscan

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

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for Dbscan

impl StructuralEq for Dbscan

impl StructuralPartialEq for Dbscan