\( \newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\mat}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

ML03.3 · Density-based clustering

A free, illustrated module of 4 lessons and one interactive in ML03 Unsupervised Learning: Clusters as dense regions: DBSCAN; Choosing eps and min_samples; Many densities at once: OPTICS; HDBSCAN.

ML03.3 L2 · Intermediate 4 lessons · about 120 min Live · in review

Part of ML03 Unsupervised Learning in the Machine Learning track.

A cluster need not be a round cloud around a centre. These four lessons treat a cluster as a dense region separated by sparse ground, whatever its shape: DBSCAN with its core, border and noise points, the sorted k-distance plot for choosing eps and the places where one eps cannot work, OPTICS, which orders the points so that clusters at every density show as valleys, and HDBSCAN, which builds the whole hierarchy from mutual reachability and keeps the most stable clusters.

What you need first. Distances and nearest neighbours (ML01.3), k-means and its failures (ML03.1), and single linkage with its minimum spanning tree (ML03.2) for the last lesson. NumPy for the code.

Lessons

1. Clusters as dense regions: DBSCAN ML03.3.1 30 min

   A cluster is a crowd of points separated from other crowds by sparse ground, whatever its shape. Learn the definitions of DBSCAN (core, border and noise points, and reachability), run it by hand on the twelve points, and build it as a breadth-first search.

2. Choosing eps and min_samples ML03.3.2 30 min

   DBSCAN needs a radius and a count. Read eps off the sorted k-distance plot, standardise first because eps is a distance in the data’s units, and see the three places where DBSCAN fails: mixed densities, many dimensions and contested border points.

3. Many densities at once: OPTICS ML03.3.3 30 min

   Instead of one eps, OPTICS orders the points so that each comes after its densest neighbour and records a reachability distance. Read clusters at every density as valleys of the reachability plot, recover DBSCAN for any eps with one horizontal line, and build it with a priority queue.

4. HDBSCAN ML03.3.4 30 min

   HDBSCAN runs DBSCAN at every eps at once, as single linkage on the mutual reachability distance, then keeps the clusters that last longest. Build the spanning tree, condense it with min_cluster_size, score clusters by stability, and solve the blobs that defeated DBSCAN.

The interactive

ML03.3-X1 · DBSCAN explorer. The twelve points and up to twenty more that you add, each with its circle of radius eps. Slide eps and step min_samples to watch points relabel as core, border or noise, grow a cluster one point at a time, and read the sorted k-distance plot beneath, with a line at the current eps. It lives in Choosing eps and min_samples.