Mean-Shift Density Climbing

Points climb a kernel density landscape to its modes.

Switch to 3D

Presets

Playback

Data

Random points around a few blob centres.

Mean shift

The kernel bandwidth decides how many hills the density has.

Time

How many mean-shift iterations happen each second.

Layers

Model checks

The science

The density landscape

Given n points x_i in the plane, the Gaussian kernel density estimate is p(x) = 1/(n 2 pi h^2) sum_i exp(-|x - x_i|^2 / (2 h^2)), where the bandwidth h sets how far each point's influence reaches. It integrates to 1. Its hills (modes) are the candidate cluster centres.

The mean-shift step

With weights w_i = exp(-|x - x_i|^2 / (2 h^2)) the mean-shift update replaces x by the weighted mean m(x) = sum w_i x_i / sum w_i. For the Gaussian kernel the shift is exactly a gradient step on the log density: m(x) - x = h^2 grad ln p(x), a step with an automatically adapted size (large on slopes with little density, small near a peak). Because this is an EM-like bound-optimisation step, the density never decreases along the path, and every path converges to a stationary point of p, normally a mode. Points that end on the same mode (merged within 0.3 h here) form one cluster, so the number of clusters is an output, not an input.

Bandwidth

Small h gives a bumpy estimate with many spurious modes; large h smooths neighbouring blobs into one. The first graph counts density peaks on a 41 x 41 grid for every h and compares with the true number of blobs; the page's mean-shift cluster count is found by the climbing points themselves, independently of that grid count.

Simplifications

The points move on a fixed density built from the original data (non-blurring mean shift). Clusters are merged by a simple distance threshold. Cost is O(n^2) per iteration, which is why the page keeps n at 300 or fewer; real implementations use spatial trees. Mean shift suffers from the curse of dimensionality, and one global bandwidth fits blobs of very different sizes badly.

What to try
  1. With the default bandwidth 0.8 and three blobs, press Restart and watch the colours settle on three clusters.
  2. Choose the small-bandwidth preset: the estimate becomes bumpy and many tiny clusters appear; the first graph shows peaks far above the true blob count.
  3. Choose the large-bandwidth preset: neighbouring blobs merge and the cluster count drops below the truth.
  4. Watch graph 3: the mean density at the points only ever rises, as the ascent theorem says.
  5. Compare the readouts "Clusters found" and "Density peaks on a grid": they use different methods and normally agree once the points have converged.
Number of density peaks against bandwidth
Mean shift step size against iteration (log scale)
Mean density at the points against iteration
Points per cluster