Mean shift

Move every point uphill on a kernel density estimate until it reaches a mode; points that share a mode form a cluster.

16 min read1828 wordscore7 viewsupdated 2026-10-07

Definition

Mean shift is a clustering algorithm that treats the data as samples from an unknown density, estimates that density with a kernel of width hh, and moves a copy of every point uphill by repeatedly replacing it with the (kernel-weighted) mean of the data in a window around it. Each copy stops at a peak — a mode — of the density. Points whose copies stop at the same mode form one cluster, so the number of clusters is whatever the number of peaks turns out to be.

At a glance

Task
Clustering (unsupervised); also mode seeking in tracking and image smoothing
Input → output
points x1,…,xn∈Rdx_1,\dots,x_n\in\mathbb R^d → a set of modes (cluster centres) and a label per point
Learns
the locations of the local maxima of a kernel density estimate; nothing else — no weights, no k
Training cost
O(T n2d)O(T\,n^2 d) with brute-force neighbour search (TT = iterations per point, usually 5–30); roughly O(T nlog⁡n)O(T\,n\log n) with a KD-tree in low dimension
Prediction cost
O(Kd)O(K d) nearest-centre lookup (scikit-learn), or a fresh O(T nd)O(T\,n d) climb from the new point
Key hyperparameters
bandwidth hh (almost everything); kernel shape; seeding (every point vs binned seeds); whether far-away orphans are forced into a cluster
Assumes
clusters are regions around peaks of density at scale hh; one bandwidth suits the whole space; Euclidean distance is meaningful (scale your features)

The problem

k-means asks you for kk up front and then carves space into kk convex Voronoi cells, one per centroid. Both halves of that are often wrong. You rarely know kk, and every point — including an isolated outlier — is forced into some cell, dragging its centroid away from where the data actually concentrates. A Gaussian mixture (see Gaussian mixtures & EM) softens the assignment but still needs the number of components and assumes elliptical blobs.

A different way to say what a cluster is: a cluster is a hill in the data density, and its centre is the top of the hill. If we could estimate the density and find its peaks, the number of clusters would come out of the data, outliers would sit on their own little hills, and a cluster's centre would be its densest location rather than an average pulled around by stragglers. Mean shift is exactly that program, done without ever computing the density explicitly.

The idea

Put a window (a disc of radius hh, or a soft Gaussian bump of width hh) on a point. Compute the mean of the data inside the window. Unless the window is already balanced, that mean lies towards the denser side — there is more data there to pull it. Move the window to the mean and repeat. Each move is a step uphill; the steps shrink as the window approaches a peak, where the data around it is balanced and the mean equals the centre. Do this starting from every data point, then group the points by the peak they reached.

The step from the current position to the window mean is the mean-shift vector, and the whole method is "follow the mean-shift vector until it vanishes". There is no objective with a kk in it, no random initialisation and no assignment step — every point independently climbs, which also makes the algorithm embarrassingly parallel.

Vocabulary

Kernel density estimate (KDE)
f^(x)\hat f(x): a smooth estimate of the density made by placing a bump of width hh on every data point and adding them up
Kernel / profile
the bump's shape. Radially symmetric kernels are written via a profile kk: K(x)=c k(∥x∥2)K(x)=c\,k(\lVert x\rVert^2)
Bandwidth h
the bump's width — window radius for the flat kernel, standard deviation for the Gaussian. It sets the scale at which you look for hills
Window
the region around the current position whose points are averaged: all points within hh (flat), or every point weighted by distance (Gaussian)
Mean-shift vector
m(x)m(x) = window mean − current position; it points uphill on the density
Mode
a local maximum of f^\hat f, where m(x)=0m(x)=0; one mode per cluster
Basin of attraction
the set of starting points that climb to the same mode — this is the cluster
Seed
a starting position for a climb; every data point by default, or one per occupied grid bin (bin seeding) for speed
Intensity
number of data points within hh of a mode; used to decide which of two nearby modes survives the merge

The math

Start from the kernel density estimate. With a radially symmetric kernel described by its profile kk,

f^K(x)=cknhd∑i=1nk ⁣(∥x−xih∥2)\hat f_K(x)=\frac{c_k}{n h^d}\sum_{i=1}^{n} k\!\left(\left\lVert \frac{x-x_i}{h}\right\rVert^2\right)
xx
the location where the density is evaluated
xix_i
the ii-th data point, i=1…ni=1\dots n
hh
bandwidth (kernel width)
dd
number of features
k(u)k(u)
profile: a non-increasing function of the squared scaled distance uu
ckc_k
constant that makes f^K\hat f_K integrate to 1

Two profiles matter. The Gaussian profile k(u)=e−u/2k(u)=e^{-u/2} gives every point some weight. The Epanechnikov profile k(u)=1−uk(u)=1-u for u≤1u\le1 (0 otherwise) is a parabola-shaped bump that ends exactly at distance hh. A mode satisfies ∇f^K(x)=0\nabla\hat f_K(x)=0, so differentiate. Write g(u)=−k′(u)g(u)=-k'(u) and gi=g(∥(x−xi)/h∥2)g_i=g\big(\lVert (x-x_i)/h\rVert^2\big). The chain rule gives ∇xk(∥(x−xi)/h∥2)=2h2(x−xi) k′(⋅)=2h2(xi−x) gi\nabla_x k(\lVert (x-x_i)/h\rVert^2)=\tfrac{2}{h^2}(x-x_i)\,k'(\cdot)=\tfrac{2}{h^2}(x_i-x)\,g_i, so

∇f^K(x)=2cknhd+2∑i(xi−x) gi=2cknhd+2∑igi⏟positive scalar  [∑ixi gi∑igi−x]⏟m(x)\nabla \hat f_K(x)=\frac{2c_k}{n h^{d+2}}\sum_{i} (x_i-x)\,g_i=\underbrace{\frac{2c_k}{n h^{d+2}}\sum_i g_i}_{\text{positive scalar}}\;\underbrace{\left[\frac{\sum_i x_i\,g_i}{\sum_i g_i}-x\right]}_{m(x)}
g(u)g(u)
−k′(u)-k'(u), the shadow profile; it supplies the weights
gig_i
weight of point xix_i for a window centred at xx
m(x)m(x)
the mean-shift vector: weighted window mean minus the current position

The gradient of the density is a positive number times m(x)m(x), so m(x)m(x) points uphill, and it is zero exactly where the gradient is zero. Setting the gradient to zero and solving for xx gives a fixed-point equation, and iterating it is the whole algorithm:

x(t+1)=∑i=1nxi g ⁣(∥x(t)−xih∥2)∑i=1ng ⁣(∥x(t)−xih∥2)x^{(t+1)}=\frac{\sum_{i=1}^{n} x_i\, g\!\left(\left\lVert \frac{x^{(t)}-x_i}{h}\right\rVert^2\right)}{\sum_{i=1}^{n} g\!\left(\left\lVert \frac{x^{(t)}-x_i}{h}\right\rVert^2\right)}
x(t)x^{(t)}
position of the climbing copy after tt shifts; x(0)x^{(0)} is the seed
x(t+1)−x(t)x^{(t+1)}-x^{(t)}
=m(x(t))=m(x^{(t)}), the step taken

Which kernel's weights do we use? For the Epanechnikov profile, g(u)=1g(u)=1 inside the window and 0 outside — the flat kernel. So replace the point by the plain average of the data within radius hh is gradient ascent on an Epanechnikov KDE. This is what scikit-learn's MeanShift does. For the Gaussian profile, g(u)=12e−u/2∝k(u)g(u)=\tfrac12e^{-u/2}\propto k(u): the Gaussian is its own shadow, and the formula simplifies to

m(x)=h2 ∇log⁡f^(x)m(x)=h^2\,\nabla\log \hat f(x)
∇log⁡f^\nabla\log\hat f
gradient of the log-density, ∇f^/f^\nabla\hat f/\hat f

This tells us how the step size adapts by itself. Dividing by f^\hat f makes steps long in sparse, low-density regions (far from any hill, where you want to move fast) and short near a peak, where the gradient vanishes — no learning rate to tune. It is also why mean shift converges: Comaniciu and Meer (2002) showed that for a convex, monotonically decreasing profile the density at the visited positions f^(x(0))≤f^(x(1))≤…\hat f(x^{(0)})\le\hat f(x^{(1)})\le\dots never decreases and the sequence converges to a stationary point. Carreira-Perpiñán (2007) showed that Gaussian mean shift is itself an EM algorithm, which is another way to see why each step can only go uphill.

What each hyperparameter does to the math

Bandwidth h
Scales every distance in g(∥(x−xi)/h∥2)g\big(\lVert (x-x_i)/h\rVert^2\big). Small hh: f^\hat f is a spiky sum of narrow bumps with a mode near almost every point → many clusters. Large hh: bumps overlap and merge, hills fuse → few clusters; as h→∞h\to\infty every weight is equal, the window mean is the global mean, and you get one cluster.
Kernel
Flat: piecewise-constant weights, so the climb jumps between window averages and stops in a finite number of steps, but modes are plateaus and nearby seeds can stop at slightly different spots. Gaussian: smooth f^\hat f, unique smooth path, but convergence is only asymptotic and every step touches all nn points.
Stopping tolerance
Stop when ∥m(x)∥≤εh\lVert m(x)\rVert\le\varepsilon h (scikit-learn uses ε=10−3\varepsilon=10^{-3}). Copies of the same mode then sit within about εh\varepsilon h of each other, which is why a merge step is needed.
Merge radius
Modes closer than hh are fused, keeping the one with more points within hh (higher intensity). This also cleans up the plateau modes of the flat kernel.

Worked example: twelve check-ins

Twelve check-ins on a 10 km × 10 km map: two neighbourhoods of five (A in the south-west, B in the north-east), one point on its own between them, and one isolated point in the south-east. We use the flat kernel with h=2.2h=2.2 km: a point's window is everything within 2.2 km.

#xygroup (by eye)
111A
221A
312A
423A
532A
666B
776B
867B
987B
1078B
1144.5between
1292isolated
The data (km). Highlighted: the in-between point 11 and the isolated point 12.

Climbing from point 1 = (1, 1)

  1. 1Window at (1, 1). Distances: point 2 and point 3 are 1.000 away, points 4 and 5 are 12+22=2.236>2.2\sqrt{1^2+2^2}=2.236>2.2 — just outside. The window holds points 1, 2, 3.
  2. 2Shift 1. Mean of (1,1), (2,1), (1,2) = (43,43)=(1.333,1.333)(\tfrac43,\tfrac43)=(1.333, 1.333). Mean-shift vector m=(0.333,0.333)m=(0.333, 0.333) — towards the bulk of A.
  3. 3Window at (1.333, 1.333). Points 4 and 5 are now 0.6672+1.6672=1.795\sqrt{0.667^2+1.667^2}=1.795 away — inside. Point 11 is 4.140 away. The window holds all five A points.
  4. 4Shift 2. Mean of the five A points =(95,95)=(1.8,1.8)=(\tfrac{9}{5},\tfrac{9}{5})=(1.8, 1.8), m=(0.467,0.467)m=(0.467, 0.467).
  5. 5Window at (1.8, 1.8). Still exactly the five A points (point 11 is 3.483 away), so the mean is again (1.8, 1.8): m=0m=0. Converged — (1.8, 1.8) is a mode.

Every other seed climbs the same way. Point 4 = (2, 3) sees points 2, 3, 4, 5 (point 2 is exactly 2.0 away; point 1 at 2.236 and point 11 at 2.5 are out), jumps to (2, 2), then sees all of A and lands on (1.8, 1.8). Neighbourhood B is a translated copy of A, so it behaves identically. The lone points see nobody else within 2.2 km — point 11 is 2.5 km from its nearest neighbours (points 4 and 6) and point 12 is 4.472 km from its nearest (point 7) — so their window mean is themselves and they never move.

SeedsPathShiftsModeIntensity
1(1,1) → (1.333,1.333) → (1.8,1.8)2(1.8, 1.8)5
2, 3→ (1.8,1.8) directly1(1.8, 1.8)5
4, 5→ (2,2) → (1.8,1.8)2(1.8, 1.8)5
6(6,6) → (6.333,6.333) → (6.8,6.8)2(6.8, 6.8)5
7, 8→ (6.8,6.8) directly1(6.8, 6.8)5
9, 10→ (7,7) → (6.8,6.8)2(6.8, 6.8)5
11stays0(4, 4.5)1
12stays0(9, 2)1
Where every seed ends (flat kernel, h = 2.2). Intensity = data points within h of the mode.

Merge, label, predict

  1. 1Collect modes. Four distinct modes: (1.8, 1.8) and (6.8, 6.8) with intensity 5, (9, 2) and (4, 4.5) with intensity 1.
  2. 2Merge. Sort by intensity and keep a mode only if no kept mode is within h=2.2h=2.2. The nearest pair, (1.8, 1.8) and (4, 4.5), is 3.483 apart, so nothing merges: 4 clusters — A, B, and two singletons. Unlike k-means, the outliers did not distort A's or B's centre.
  3. 3Label. Every point gets the nearest kept centre: points 1–5 → (1.8, 1.8), 6–10 → (6.8, 6.8), 11 and 12 on their own.
  4. 4New check-in at (5, 5). Climb it: the window holds points 6 and 11 → (5, 5.25); now points 6, 7, 8, 11 → (5.75, 5.875); point 11 is now 2.226 away and drops out, leaving 6, 7, 8 → (6.333, 6.333); then all of B → (6.8, 6.8). Four shifts, and the new point belongs to B.
  5. 5But scikit-learn's predict does not climb — it returns the nearest centre, and (5, 5) is 1.118 km from (4, 4.5) but 2.546 km from (6.8, 6.8). So predict puts it in the singleton cluster of point 11. The two rules disagree on points that lie between hills.
flat kernel · h = 2.2 km · iteration 0/400224466881010km · drag the white diamond (new point)
h2.2
12 points reached 4 distinct modes → merged within h: 4 clusters · longest climb 2 shifts
probe step 0: at (5.00, 5.00), window holds 2 points, shift m = (0.00, 0.25)
probe (5.00, 5.00) climbs in 4 shifts to (6.80, 6.80) → cluster 1 · nearest-centre predict → cluster 4 (they disagree)
fig.The worked example, live. Background: the kernel density (window counts for the flat kernel). Press play: every point moves to the mean of its window, leaving a trail, until it reaches a mode (crosses = cluster centres after merging). With the flat kernel at h = 2.2 the points converge in at most 2 shifts to 4 clusters; the white diamond (a new check-in at (5, 5)) needs 4 shifts and climbs into B, while nearest-centre predict sends it to point 11's singleton cluster. Its window, the points it averages and its mean-shift vector are drawn at every step. Drag the diamond, slide h (4 clusters for h = 1.5–2.6, 3 for 2.7–3.9, 1 from 4.5), or switch to the Gaussian kernel (h = 1.0: the same 4 clusters with modes at (1.64, 1.64) and (6.64, 6.64), longest climb 14 shifts).

The algorithm, step by step

MeanShift(X, h)

  1. 1Seed. Start one copy at every data point (or, with bin seeding, at the centre of every grid cell of side hh that holds at least min_bin_freq points).
  2. 2Climb. For each seed xx: find the points in its window, set x←x\leftarrow their (weighted) mean, and repeat until the step ∥m(x)∥≤10−3h\lVert m(x)\rVert\le 10^{-3}h or max_iter (300) is reached. Record the final position and its intensity.
  3. 3Deduplicate. Sort the end points by intensity (highest first). Walk the list and keep a point only if no already-kept point lies within hh. The kept points are the cluster centres.
  4. 4Label. Assign every training point to its nearest centre. With cluster_all=False, points farther than hh from every centre get the label −1-1 (orphans).
  5. 5Predict a new point by nearest centre (fast) — or, if you want the true basin of attraction, climb it like a seed and see where it lands.

Complexity

One shift
a radius query: O(nd)O(nd) brute force, about O(log⁡n)O(\log n) + window size with a KD/ball tree in low dd
Whole fit
O(T⋅s⋅nd)O(T\cdot s\cdot nd) brute force for ss seeds; s=ns=n by default, so O(Tn2d)O(Tn^2d) — quadratic, fine for thousands of points, slow for millions
Bin seeding
replaces nn seeds by the number of occupied bins, often 10–100× fewer
Memory
O(nd)O(nd) — no pairwise matrix is ever stored
Parallelism
seeds are independent; scikit-learn runs them in parallel with n_jobs

Variants and tuning

The single most important decision is hh. scikit-learn's estimate_bandwidth sets it to the average, over points, of the distance to the q⋅nq\cdot n-th nearest neighbour (default quantile q=0.3q=0.3). On the twelve check-ins it returns h=1.734h=1.734, inside the 1.5–2.6 range that yields the 4 natural clusters. A sturdier habit is to sweep hh and look for the widest plateau in the number of clusters — on this data that is the 4-cluster plateau from h=1.5h=1.5 to 2.62.6.

KnobEffectAdvice
bandwidthscale of the hills; fewer clusters as it growsstandardise features first; sweep and look for a plateau, or start from estimate_bandwidth
kernelflat (sklearn) vs Gaussian / EpanechnikovGaussian gives smoother modes; flat is faster and stops in few steps
bin_seedingseeds on a grid of side h instead of every pointturn on for n ≳ 10⁴; results are nearly identical
min_bin_freqignore bins with fewer points as seedsraise to skip climbs from noise
cluster_allFalse → points far from every centre get −1use False when you want outliers flagged, as in DBSCAN
adaptive bandwidtha per-point hih_i (e.g. k-NN distance)for data whose clusters have very different densities
blurring mean shiftmove the data itself each iteration, not copiesconverges much faster but can over-shrink clusters
Knobs worth knowing (scikit-learn names where they exist).

Mean shift among its siblings

vs k-means
both move points to means — k-means moves kk centroids to the mean of their Voronoi cell, mean shift moves every seed to the mean of its distance window. Mean shift needs no kk and finds density peaks, not least-squares centres
vs DBSCAN / HDBSCAN / OPTICS
all density-based. DBSCAN thresholds density and follows connectivity, so clusters can be any shape; mean shift follows gradients to peaks, so each cluster is a basin around one mode. See HDBSCAN and OPTICS for multi-density versions
vs GMM
a Gaussian mixture fits KK parametric components; mean shift's density is non-parametric (one bump per point) and KK is an output
vs spectral clustering
spectral clustering handles rings and moons via a graph; mean shift would split a ring into several modes

In code

python
1import numpy as np
2
3def mean_shift(X, h, kernel="flat", tol=1e-3, max_iter=300):
4 """Move every point uphill on the KDE; merge modes closer than h."""
5 modes, intensity = [], []
6 for x in X.astype(float):
7 for _ in range(max_iter):
8 d2 = ((X - x) ** 2).sum(axis=1)
9 if kernel == "flat":
10 w = (d2 <= h * h).astype(float) # uniform window of radius h
11 else:
12 w = np.exp(-d2 / (2 * h * h)) # Gaussian, std h
13 new = w @ X / w.sum() # weighted mean of the window
14 done = np.linalg.norm(new - x) <= tol * h
15 x = new
16 if done:
17 break
18 modes.append(x)
19 intensity.append(int((((X - x) ** 2).sum(axis=1) <= h * h).sum()))
20 # keep the densest modes; drop any mode within h of one already kept
21 order = np.argsort(intensity, kind="stable")[::-1]
22 centers = []
23 for i in order:
24 if all(np.linalg.norm(modes[i] - c) > h for c in centers):
25 centers.append(modes[i])
26 centers = np.array(centers)
27 labels = np.argmin(((X[:, None] - centers[None]) ** 2).sum(-1), axis=1)
28 return centers, labels
29
30X = np.array([[1, 1], [2, 1], [1, 2], [2, 3], [3, 2],
31 [6, 6], [7, 6], [6, 7], [8, 7], [7, 8],
32 [4, 4.5], [9, 2]])
33centers, labels = mean_shift(X, h=2.2)
34print(centers.round(2)) # [[6.8 6.8] [1.8 1.8] [9. 2.] [4. 4.5]]
35print(labels) # [1 1 1 1 1 0 0 0 0 0 3 2]
From scratch: flat or Gaussian kernel, scikit-learn's stopping and merging rules. Prints the 4 centres and the labels of the worked example.
python
1import numpy as np
2from sklearn.cluster import MeanShift, estimate_bandwidth
3
4X = np.array([[1, 1], [2, 1], [1, 2], [2, 3], [3, 2],
5 [6, 6], [7, 6], [6, 7], [8, 7], [7, 8],
6 [4, 4.5], [9, 2]])
7
8print("estimated h:", round(estimate_bandwidth(X), 3)) # 1.734
9ms = MeanShift(bandwidth=2.2).fit(X)
10print(ms.cluster_centers_.round(2)) # [[6.8 6.8] [1.8 1.8] [9. 2.] [4. 4.5]]
11print(ms.labels_) # [1 1 1 1 1 0 0 0 0 0 3 2]
12print("predict (5, 5):", ms.predict([[5, 5]])) # [3] -- nearest centre, no climbing
13
14for h in [1.2, 2.2, 3.0, 4.0, 4.5]:
15 print(h, len(MeanShift(bandwidth=h).fit(X).cluster_centers_), "clusters")
16# 1.2 8 · 2.2 4 · 3.0 3 · 4.0 2 · 4.5 1
scikit-learn on the same data: identical centres, the estimated bandwidth, nearest-centre prediction for (5, 5), and the bandwidth sweep.

Use when

  • +You don't know the number of clusters and want it to come out of the data.
  • +Clusters are blobs around a dense core (any convex-ish shape, unequal sizes), and you want centres at the densest point, robust to outliers.
  • +Low-dimensional data — 2-D/3-D positions, colour spaces, image feature spaces — where a density estimate is meaningful.
  • +You need mode seeking itself: tracking a target, smoothing an image while keeping edges, finding hotspots.

Avoid when

  • −High dimensions (≳ 10–20 features): kernel density estimates need exponentially many points, windows become empty or contain everything.
  • −Clusters with very different densities or scales: one global h either splits the wide ones or fuses the tight ones.
  • −Elongated, curved or ring-shaped clusters: one mode per cluster cannot describe a ring; use DBSCAN or spectral clustering.
  • −Large n without bin seeding or a fast neighbour index: the default fit is quadratic.

Where it's used

Image segmentation

Cluster pixels in a joint (x, y, L, u, v) space: each segment is a colour mode near a location. This was the headline application of Comaniciu & Meer (2002).

Object tracking

CAMShift and kernel-based tracking move a window each frame to the mode of a colour-likelihood map — mean shift on a moving target.

Edge-preserving smoothing

Replacing every pixel by the mode it converges to flattens texture within regions but keeps sharp boundaries (OpenCV's pyrMeanShiftFiltering).

Hotspot and location analysis

Find the busiest spots among GPS check-ins, taxi pick-ups or crime reports, where the number of hotspots is unknown and isolated events should not move them.

Check yourself

Flat kernel, h = 2.2. The window around (1, 1) contains exactly (1, 1), (2, 1) and (1, 2). Where is the point after one mean-shift step?

Check yourself

You increase the bandwidth h from 2.2 to 4.5 on the twelve check-ins. What happens to the clustering?

Check yourself

Why does the mean-shift vector point uphill on the density?

Check yourself

Which of these must you supply to mean shift but NOT to k-means — and vice versa?

Remember

  • ✓Mean shift estimates the density with a kernel of width h and moves a copy of every point uphill to a mode; points sharing a mode form a cluster.
  • ✓The update is the kernel-weighted mean of the window: x←∑ixigi/∑igix\leftarrow\sum_i x_i g_i/\sum_i g_i. Its step m(x)m(x) is proportional to ∇f^/f^\nabla\hat f/\hat f, so it climbs with a self-adapting step size.
  • ✓The flat kernel (average of points within h, as in scikit-learn) is exact gradient ascent on an Epanechnikov KDE; the Gaussian kernel ascends a Gaussian KDE.
  • ✓The number of clusters is an output; the bandwidth h decides it — sweep h, look for a plateau, and standardise features first.
  • ✓Modes closer than h are merged by intensity; predict uses the nearest centre, which can differ from where a new point would climb.
  • ✓Best in low dimensions with blob-like clusters of similar scale; quadratic cost by default, so use bin seeding for big data.
← back to ML Algorithms roadmap