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 , 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 → 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
- with brute-force neighbour search ( = iterations per point, usually 5–30); roughly with a KD-tree in low dimension
- Prediction cost
- nearest-centre lookup (scikit-learn), or a fresh climb from the new point
- Key hyperparameters
- bandwidth (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 ; one bandwidth suits the whole space; Euclidean distance is meaningful (scale your features)
The problem
k-means asks you for up front and then carves space into convex Voronoi cells, one per centroid. Both halves of that are often wrong. You rarely know , 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 , or a soft Gaussian bump of width ) 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 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)
- : a smooth estimate of the density made by placing a bump of width on every data point and adding them up
- Kernel / profile
- the bump's shape. Radially symmetric kernels are written via a profile :
- 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 (flat), or every point weighted by distance (Gaussian)
- Mean-shift vector
- = window mean − current position; it points uphill on the density
- Mode
- a local maximum of , where ; 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 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 ,
- the location where the density is evaluated
- the -th data point,
- bandwidth (kernel width)
- number of features
- profile: a non-increasing function of the squared scaled distance
- constant that makes integrate to 1
Two profiles matter. The Gaussian profile gives every point some weight. The Epanechnikov profile for (0 otherwise) is a parabola-shaped bump that ends exactly at distance . A mode satisfies , so differentiate. Write and . The chain rule gives , so
- , the shadow profile; it supplies the weights
- weight of point for a window centred at
- the mean-shift vector: weighted window mean minus the current position
The gradient of the density is a positive number times , so points uphill, and it is zero exactly where the gradient is zero. Setting the gradient to zero and solving for gives a fixed-point equation, and iterating it is the whole algorithm:
- position of the climbing copy after shifts; is the seed
- , the step taken
Which kernel's weights do we use? For the Epanechnikov profile, inside the window and 0 outside — the flat kernel. So replace the point by the plain average of the data within radius is gradient ascent on an Epanechnikov KDE. This is what scikit-learn's MeanShift does. For the Gaussian profile, : the Gaussian is its own shadow, and the formula simplifies to
- gradient of the log-density,
This tells us how the step size adapts by itself. Dividing by 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 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 . Small : is a spiky sum of narrow bumps with a mode near almost every point → many clusters. Large : bumps overlap and merge, hills fuse → few clusters; as 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 , unique smooth path, but convergence is only asymptotic and every step touches all points.
- Stopping tolerance
- Stop when (scikit-learn uses ). Copies of the same mode then sit within about of each other, which is why a merge step is needed.
- Merge radius
- Modes closer than are fused, keeping the one with more points within (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 km: a point's window is everything within 2.2 km.
| # | x | y | group (by eye) |
|---|---|---|---|
| 1 | 1 | 1 | A |
| 2 | 2 | 1 | A |
| 3 | 1 | 2 | A |
| 4 | 2 | 3 | A |
| 5 | 3 | 2 | A |
| 6 | 6 | 6 | B |
| 7 | 7 | 6 | B |
| 8 | 6 | 7 | B |
| 9 | 8 | 7 | B |
| 10 | 7 | 8 | B |
| 11 | 4 | 4.5 | between |
| 12 | 9 | 2 | isolated |
Climbing from point 1 = (1, 1)
- 1Window at (1, 1). Distances: point 2 and point 3 are 1.000 away, points 4 and 5 are — just outside. The window holds points 1, 2, 3.
- 2Shift 1. Mean of (1,1), (2,1), (1,2) = . Mean-shift vector — towards the bulk of A.
- 3Window at (1.333, 1.333). Points 4 and 5 are now away — inside. Point 11 is 4.140 away. The window holds all five A points.
- 4Shift 2. Mean of the five A points , .
- 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): . 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.
| Seeds | Path | Shifts | Mode | Intensity |
|---|---|---|---|---|
| 1 | (1,1) → (1.333,1.333) → (1.8,1.8) | 2 | (1.8, 1.8) | 5 |
| 2, 3 | → (1.8,1.8) directly | 1 | (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) directly | 1 | (6.8, 6.8) | 5 |
| 9, 10 | → (7,7) → (6.8,6.8) | 2 | (6.8, 6.8) | 5 |
| 11 | stays | 0 | (4, 4.5) | 1 |
| 12 | stays | 0 | (9, 2) | 1 |
Merge, label, predict
- 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.
- 2Merge. Sort by intensity and keep a mode only if no kept mode is within . 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.
- 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.
- 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.
- 5But scikit-learn's
predictdoes 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). Sopredictputs it in the singleton cluster of point 11. The two rules disagree on points that lie between hills.
The algorithm, step by step
MeanShift(X, h)
- 1Seed. Start one copy at every data point (or, with bin seeding, at the centre of every grid cell of side that holds at least
min_bin_freqpoints). - 2Climb. For each seed : find the points in its window, set their (weighted) mean, and repeat until the step or
max_iter(300) is reached. Record the final position and its intensity. - 3Deduplicate. Sort the end points by intensity (highest first). Walk the list and keep a point only if no already-kept point lies within . The kept points are the cluster centres.
- 4Label. Assign every training point to its nearest centre. With
cluster_all=False, points farther than from every centre get the label (orphans). - 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: brute force, about + window size with a KD/ball tree in low
- Whole fit
- brute force for seeds; by default, so — quadratic, fine for thousands of points, slow for millions
- Bin seeding
- replaces seeds by the number of occupied bins, often 10–100× fewer
- Memory
- — 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 . scikit-learn's estimate_bandwidth sets it to the average, over points, of the distance to the -th nearest neighbour (default quantile ). On the twelve check-ins it returns , inside the 1.5–2.6 range that yields the 4 natural clusters. A sturdier habit is to sweep and look for the widest plateau in the number of clusters — on this data that is the 4-cluster plateau from to .
| Knob | Effect | Advice |
|---|---|---|
bandwidth | scale of the hills; fewer clusters as it grows | standardise features first; sweep and look for a plateau, or start from estimate_bandwidth |
| kernel | flat (sklearn) vs Gaussian / Epanechnikov | Gaussian gives smoother modes; flat is faster and stops in few steps |
bin_seeding | seeds on a grid of side h instead of every point | turn on for n ≳ 10⁴; results are nearly identical |
min_bin_freq | ignore bins with fewer points as seeds | raise to skip climbs from noise |
cluster_all | False → points far from every centre get −1 | use False when you want outliers flagged, as in DBSCAN |
| adaptive bandwidth | a per-point (e.g. k-NN distance) | for data whose clusters have very different densities |
| blurring mean shift | move the data itself each iteration, not copies | converges much faster but can over-shrink clusters |
Mean shift among its siblings
- vs k-means
- both move points to means — k-means moves centroids to the mean of their Voronoi cell, mean shift moves every seed to the mean of its distance window. Mean shift needs no 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 parametric components; mean shift's density is non-parametric (one bump per point) and 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
1import numpy as np23def 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 h11 else:12 w = np.exp(-d2 / (2 * h * h)) # Gaussian, std h13 new = w @ X / w.sum() # weighted mean of the window14 done = np.linalg.norm(new - x) <= tol * h15 x = new16 if done:17 break18 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 kept21 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, labels2930X = 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]1import numpy as np2from sklearn.cluster import MeanShift, estimate_bandwidth34X = 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]])78print("estimated h:", round(estimate_bandwidth(X), 3)) # 1.7349ms = 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 climbing1314for 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 1Use 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: . Its step is proportional to , 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.