DBSCAN / HDBSCAN Clustering

Anh-Thi Dinh
Machine Learning

What?

The key idea is that for each point of a cluster, the neighborhood of a given radius has to contain at least a minimum number of points.

DBSCAN

  • "DBSCAN" = Density-based-spatial clustering of application with noise.
  • Separate clusters of high density from ones of low density.
  • Can sort data into clusters of varying shapes.
  • Input: set of points & neighborhood N & minpts (density)
  • Output: clusters with density (+ noises)
  • Each point is either:
    • Core point: has at least minpts points in its neighborhood.
    • Border point: not a core but has at least 1 core point in its neighborhoods.
    • Noise point: not a core or border point.
  • Phase:
      1. Choose a point → it's a core point?
        1. If yes → expand → check core / check border
        2. If no → form a cluster
      1. Repeat to form other clusters
      1. Eliminate noise points.
  • Pros:
    • Discover any number of clusters (different from K-Means & K-Medoids Clustering which need an input of number of clusters).
    • Cluster of varying sizes and shapes.
    • Detect and ignore outliers.
  • Cons:
    • Sensitive → choice of neighborhood parameters (eg. If minpts is too small → wrong noises)
    • Produce noise: unclear → how to calculate metric indexes when there is noise.

HDBSCAN

  • High DBSCAN.
  • Difference between DBSCAN and HDBSCAN:
    • HDBSCAN: focus much on high density.
    • DBSCAN: create right clusters but also create clusters with very low density of examples (Figure 1).
    • Check more in this note.
  • Reduce the speed of clustering in comparision with other methods (Figure 2).
  • HDBScan has the parameter minimum cluster size (min_cluster_size), which is how big a cluster needs to be in order to form.
Figure 1. Difference between DBSCAN (left) and HDBSCAN (right). Source of figure.
Figure 2.Performance comparison of difference clustering methods. HDBSCAN is much faster than DBSCAN with more data points. Source of figure.

When?

  • We are not sure the number of clusters (like in KMeans)
  • There are outliers or noises in data.
  • Arbitrary cluster's shape.

In Code

DBSCAN with Scikit-learn

1from sklearn.cluster import DBSCAN
2clr = DBSCAN(eps=3, min_samples=2)
1clr.fit(X)
2clr.predict(X)
1# or
2clr.fit_predict(X)
Parameters (others):
  • min_samples: min number of samples to be called "dense"
  • eps: max distance between 2 samples to be in the same cluster. Its unit/value based on the unit of data.
  • Higher min_samples + lower eps indicates higher density necessary to form a cluster.
Attributes:
  • clr.labels_: clusters' labels.

HDBSCAN

For a ref of paramaters, check the API.
1from hdbscan import HDBSCAN
2clr = HDBSCAN(eps=3, min_cluster_size=3, metric='euclidean')
Parameters:
  • min_cluster_size: (ref) the smallest size grouping that you wish to consider a cluster.
  • min_samples: (ref) The number of samples in a neighbourhood for a point to be considered a core point. The larger value → the more points will be declared as noise & clusters will be restricted to progressively more dense areas.
  • Working with (more): metric='precomputed' (ref)
      • 1from dtaidistance import dtw
2matrix = dtw.distance_matrix_fast(series) # something likes that
3model = HDBSCAN(metric='precomputed')
4clusters = model.fit_predict(matrix)
Attributes:
  • Label 1 means that this sample is not assigned to any cluster, or noise!
  • clt.labels_: labels of clusters (including 1)
  • clt.probabilities_: scores (between 0 and 1). 0 means sample is not in cluster at all (noise), 1 means the heart of cluster.

HDBSCAN and scikit-learn

Note that, HDBSCAN is built based on scikit-learn but it doesn't have an .predict() method as other clustering methods does on scikit-learn. Below code gives you a new version of HDBSCAN (WrapperHDBSCAN) which has an additional .predict() method.
1from hdbscan import HDBSCAN
2
3class WrapperHDBSCAN(HDBSCAN):
4    def predict(self, X):
5        self.fit(X)
6        return self.labels_

Reference