Struct linfa_clustering::Dbscan
source · pub struct Dbscan;
Expand description
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§
source§impl Dbscan
impl Dbscan
sourcepub fn params<F: Float>(
min_points: usize
) -> DbscanParams<F, L2Dist, CommonNearestNeighbour>
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
sourcepub fn params_with<F: Float, D: Distance<F>, N: NearestNeighbour>(
min_points: usize,
dist_fn: D,
nn_algo: N
) -> DbscanParams<F, D, N>
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§
source§impl PartialEq for Dbscan
impl PartialEq for Dbscan
impl Eq for Dbscan
impl StructuralEq for Dbscan
impl StructuralPartialEq for Dbscan
Auto Trait Implementations§
impl RefUnwindSafe for Dbscan
impl Send for Dbscan
impl Sync for Dbscan
impl Unpin for Dbscan
impl UnwindSafe for Dbscan
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<Q, K> Equivalent<K> for Qwhere
Q: Eq + ?Sized,
K: Borrow<Q> + ?Sized,
impl<Q, K> Equivalent<K> for Qwhere Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,
source§fn equivalent(&self, key: &K) -> bool
fn equivalent(&self, key: &K) -> bool
key
and return true
if they are equal.