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
    2. Repeat to form other clusters
    3. Eliminate noise points.
  • Pros:
    • Discover any number of clusters (different from K-Means 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.

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

from sklearn.cluster import DBSCAN
clr = DBSCAN(eps=3, min_samples=2)
clr.fit(X)
clr.predict(X)
# or
clr.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 here.

from hdbscan import HDBSCAN
clr = DBSCAN(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 \to the more points will be declared as noise & clusters will be restricted to progressively more dense areas.

Box’s content.

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.

from hdbscan import HDBSCAN

class WrapperHDBSCAN(HDBSCAN):
    def predict(self, X):
        self.fit(X)
        return self.labels_

Reference

Notes with this notation aren't good enough. They are being updated.