HDBSCAN - Hierarchical Density-Based Spatial Clustering of Applications with Noise.
HDBSCAN turns DBSCAN into a hierarchical algorithm and then extracts a flat clustering
from that hierarchy. Unlike Scholar.Cluster.DBSCAN it does not need an eps radius,
so it can recover clusters of differing densities, and points that belong to no cluster
are labelled as noise. The root is never returned as a cluster, so data with no real
split in it comes back as all noise.
The algorithm proceeds in four steps:
Compute the core distance of each point, the distance to its
:min_samples-th neighbour, which is a local estimate of how sparse the point's neighbourhood is.Build the mutual reachability, $d_{mreach}(a, b) = \max(core(a), core(b), d(a, b))$, which pushes sparse points away from everything while leaving dense regions untouched.
Build a single linkage hierarchy over the mutual reachability, via
Scholar.Cluster.Hierarchical.Condense that hierarchy using
:min_cluster_sizeand select the flat clustering that maximises cluster stability (the "excess of mass" criterion).
The time complexity is $O(N^2 \log N)$ for $N$ samples. The space complexity is $O(N^2)$, since the mutual reachability is held as a dense matrix.
Comparing against other implementations
The mutual reachability contains many exactly equal values by construction: whenever a
core distance dominates a pair, every pair it dominates collapses onto that same value.
Single linkage is then genuinely ambiguous, and different implementations resolve those
ties differently while producing dendrograms of identical height. So the labels here can
differ from sklearn.cluster.HDBSCAN on such data, without either being wrong. On data
where the merge heights are all distinct, and therefore the dendrogram is unique, the two
agree on which points are grouped together, up to which cluster gets which integer id.
References
- Density-Based Clustering Based on Hierarchical Density Estimates, Campello, Moulavi and Sander, 2013.
Summary
Functions
Performs HDBSCAN clustering on x.
Functions
Performs HDBSCAN clustering on x.
Options
:min_cluster_size(pos_integer/0) - The smallest group of points that should be considered a cluster. Groups smaller than this are treated as points falling out of their parent cluster. Must be at least2. The default value is5.:min_samples(pos_integer/0) - The number of samples in a neighbourhood for a point to be considered a core point, including the point itself. Larger values make the clustering more conservative, so more points end up as noise. Defaults to:min_cluster_size.:metric- The function that measures the pairwise distance between two points. Possible values:{:minkowski, p}- Minkowski metric. By changing value ofpparameter (a positive number or:infinity) we can set Manhattan (1), Euclidean (2), Chebyshev (:infinity), or any arbitrary $L_p$ metric.:euclidean- Euclidean metric.:squared_euclidean- Squared Euclidean metric.:manhattan- Manhattan metric.:cosine- Cosine metric.Anonymous function of arity 2 that takes two rank-2 tensors.
The default value is
&Scholar.Metrics.Distance.pairwise_euclidean/2.
Return Values
The function returns a struct with the following parameters:
:labels- Cluster labels for each point inx. Noisy samples are given the label-1. Clusters are numbered from0, ordered by the point at which they appear in the condensed hierarchy.
Examples
iex> x = Nx.tensor([[1, 2], [2, 2], [2, 3], [1, 3], [8, 7], [8, 8], [7, 8], [7, 7]])
iex> model = Scholar.Cluster.HDBSCAN.fit(x, min_cluster_size: 3, min_samples: 2)
iex> model.labels
#Nx.Tensor<
s32[8]
[0, 0, 0, 0, 1, 1, 1, 1]
>