Density-Based Spatial Clustering of Applications with Noise.
Classes
DBSCAN (Density-Based Spatial Clustering of Applications with Noise).
Groups together points that are closely packed (points with many nearby neighbors), marking points in low-density regions as outliers. Unlike partitional methods, DBSCAN does not require the number of clusters to be specified in advance.
Constructor
__init__( self, eps: float = 0.5, min_samples: int = 5, metric: str = 'euclidean', )
Overview
The algorithm discovers clusters through density-connected regions:
- Compute the \epsilon-neighborhood for every point
-
Identify core points that have at least
min_samplesneighbors - Form clusters by connecting core points that are within \epsilon of each other
- Assign border points to the cluster of a reachable core point
- Label remaining points as noise (label -1)
Theory
The \epsilon-neighborhood of a point p is defined as:
N_{\epsilon}(p) = \{q \in D \mid \text{dist}(p, q) \leq \epsilon\}
A point p is a core point if |N_{\epsilon}(p)| \geq \text{min\_samples}.
A point q is directly density-reachable from p if:
q \in N_{\epsilon}(p) \quad \text{and} \quad |N_{\epsilon}(p)| \geq \text{min\_samples}
A cluster is a maximal set of density-connected points, where density-connectivity is the transitive closure of direct density-reachability.
Parameters
eps
float
= 0.5
The maximum distance between two samples for one to be considered as in the neighborhood of the other.
min_samples
int
= 5
The number of samples in a neighborhood for a point to be considered as a core point. This includes the point itself.
metric
{"euclidean", "manhattan"}
= "euclidean"
The metric to use when calculating distance between instances in a feature array.
Attributes
labels_
np.ndarray of shape (n_samples,)
Cluster labels for each point in the dataset given to fit(). Noisy samples are given the label -1.
core_sample_indices_
np.ndarray of shape (n_core_samples,)
Indices of core samples.
components_
np.ndarray of shape (n_core_samples, n_features)
Copy of each core sample found by training.
Notes
Complexity:
- Training: O(n^2) time in the worst case. With a spatial index,
- Space: O(n^2) to store the distance matrix.
- When the number of clusters is unknown
- Data contains arbitrarily shaped clusters (non-globular)
- Outlier or noise detection is important
- When clusters have similar densities
References
Ester1996
Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996).
A density-based algorithm for discovering clusters in
large spatial databases with noise.
KDD, 96(34), pp. 226-231.
Schubert2017
Schubert, E., Sander, J., Ester, M., Kriegel, H.P., & Xu, X. (2017).
DBSCAN revisited, revisited: why and how you should (still) use DBSCAN.
ACM Transactions on Database Systems, 42(3), Article 19.
DOI: 10.1145/3068335
Density-based clustering with noise detection:
python
>>> import numpy as np
>>> from tuiml.algorithms.clustering import DBSCANClusterer
>>> X = np.array([[1, 2], [2, 2], [2, 3],
... [8, 7], [8, 8], [25, 80]])
>>> dbscan = DBSCANClusterer(eps=3, min_samples=2)
>>> dbscan.fit(X)
>>> dbscan.labels_
array([ 0, 0, 0, 1, 1, -1])