# Mean shift

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

Source: https://www.mlfoundry.in/learn/mean-shift  
Section: ML Algorithms › Unsupervised · Clustering  
Level: core · 16 min read · updated 2026-10-07

**Mean shift:** is a clustering algorithm that treats the data as samples from an unknown density, estimates that density with a kernel of width $h$, 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.

- **Task:** Clustering (unsupervised); also mode seeking in tracking and image smoothing
- **Input → output:** points $x_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\,n^2 d)$ with brute-force neighbour search ($T$ = iterations per point, usually 5–30); roughly $O(T\,n\log n)$ with a KD-tree in low dimension
- **Prediction cost:** $O(K d)$ nearest-centre lookup (scikit-learn), or a fresh $O(T\,n d)$ climb from the new point
- **Key hyperparameters:** bandwidth $h$ (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 $h$; one bandwidth suits the whole space; Euclidean distance is meaningful (scale your features)

## The problem

*k-means* asks you for $k$ up front and then carves space into $k$ convex Voronoi cells, one per centroid. Both halves of that are often wrong. You rarely know $k$, 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 $h$, or a soft Gaussian bump of width $h$) 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 $k$ 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):** $\hat f(x)$: a smooth estimate of the density made by placing a bump of width $h$ on every data point and adding them up
- **Kernel / profile:** the bump's shape. Radially symmetric kernels are written via a *profile* $k$: $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 $h$ (flat), or every point weighted by distance (Gaussian)
- **Mean-shift vector:** $m(x)$ = window mean − current position; it points uphill on the density
- **Mode:** a local maximum of $\hat f$, where $m(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 $h$ 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 $k$,

$$
\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)
$$

- $x$: the location where the density is evaluated
- $x_i$: the $i$-th data point, $i=1\dots n$
- $h$: bandwidth (kernel width)
- $d$: number of features
- $k(u)$: profile: a non-increasing function of the squared scaled distance $u$
- $c_k$: constant that makes $\hat f_K$ integrate to 1

Two profiles matter. The **Gaussian** profile $k(u)=e^{-u/2}$ gives every point some weight. The **Epanechnikov** profile $k(u)=1-u$ for $u\le1$ (0 otherwise) is a parabola-shaped bump that ends exactly at distance $h$. A mode satisfies $\nabla\hat f_K(x)=0$, so differentiate. Write $g(u)=-k'(u)$ and $g_i=g\big(\lVert (x-x_i)/h\rVert^2\big)$. The chain rule gives $\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

$$
\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)$: $-k'(u)$, the *shadow* profile; it supplies the weights
- $g_i$: weight of point $x_i$ for a window centred at $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)$, so **$m(x)$ points uphill**, and it is zero exactly where the gradient is zero. Setting the gradient to zero and solving for $x$ gives a fixed-point equation, and iterating it is the whole algorithm:

$$
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)}$: position of the climbing copy after $t$ shifts; $x^{(0)}$ is the seed
- $x^{(t+1)}-x^{(t)}$: $=m(x^{(t)})$, the step taken

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

$$
m(x)=h^2\,\nabla\log \hat f(x)
$$

- $\nabla\log\hat f$: gradient of the log-density, $\nabla\hat f/\hat f$

This tells us how the **step size adapts by itself**. Dividing by $\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 $\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\big(\lVert (x-x_i)/h\rVert^2\big)$. Small $h$: $\hat f$ is a spiky sum of narrow bumps with a mode near almost every point → many clusters. Large $h$: bumps overlap and merge, hills fuse → few clusters; as $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 $\hat f$, unique smooth path, but convergence is only asymptotic and every step touches all $n$ points.
- **Stopping tolerance:** Stop when $\lVert m(x)\rVert\le\varepsilon h$ (scikit-learn uses $\varepsilon=10^{-3}$). Copies of the same mode then sit within about $\varepsilon h$ of each other, which is why a merge step is needed.
- **Merge radius:** Modes closer than $h$ are fused, keeping the one with more points within $h$ (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.2$ km**: a point's window is everything within 2.2 km.

The data (km). Highlighted: the in-between point 11 and the isolated point 12.

| # | 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)**

1. **Window at (1, 1).** Distances: point 2 and point 3 are 1.000 away, points 4 and 5 are $\sqrt{1^2+2^2}=2.236>2.2$ — just outside. The window holds points 1, 2, 3.
2. **Shift 1.** Mean of (1,1), (2,1), (1,2) = $(\tfrac43,\tfrac43)=(1.333, 1.333)$. Mean-shift vector $m=(0.333, 0.333)$ — towards the bulk of A.
3. **Window at (1.333, 1.333).** Points 4 and 5 are now $\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. **Shift 2.** Mean of the five A points $=(\tfrac{9}{5},\tfrac{9}{5})=(1.8, 1.8)$, $m=(0.467, 0.467)$.
5. **Window 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=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.

Where every seed ends (flat kernel, h = 2.2). Intensity = data points within h of the mode.

| 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**

1. **Collect 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. **Merge.** Sort by intensity and keep a mode only if no kept mode is within $h=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. **Label.** 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. **New 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. **But** 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.

> **Changing h on the same data:** On a 0.1 grid of bandwidths, scikit-learn finds 8 clusters for $h$ = 1.0–1.4, **4** for 1.5–2.6, **3** for 2.7–3.9 (point 11 joins A), 2 for 4.0–4.4 (A and B fuse; point 12 stays alone) and **1** from 4.5 up. At $h=3$, seeds 4, 5 and 11 stop at (2.167, 2.25) while seeds 1–3 stop at (1.8, 1.8) — two plateau modes of the same hill, 0.580 apart; the merge keeps (2.167, 2.25) because 6 points lie within 3 km of it versus 5.

> Figure: 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. **Seed.** Start one copy at every data point (or, with bin seeding, at the centre of every grid cell of side $h$ that holds at least `min_bin_freq` points).
2. **Climb.** For each seed $x$: find the points in its window, set $x\leftarrow$ their (weighted) mean, and repeat until the step $\lVert m(x)\rVert\le 10^{-3}h$ or `max_iter` (300) is reached. Record the final position and its intensity.
3. **Deduplicate.** Sort the end points by intensity (highest first). Walk the list and keep a point only if no already-kept point lies within $h$. The kept points are the cluster centres.
4. **Label.** Assign every training point to its nearest centre. With `cluster_all=False`, points farther than $h$ from every centre get the label $-1$ (orphans).
5. **Predict** 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)$ brute force, about $O(\log n)$ + window size with a KD/ball tree in low $d$
- **Whole fit:** $O(T\cdot s\cdot nd)$ brute force for $s$ seeds; $s=n$ by default, so $O(Tn^2d)$ — quadratic, fine for thousands of points, slow for millions
- **Bin seeding:** replaces $n$ seeds by the number of occupied bins, often 10–100× fewer
- **Memory:** $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 $h$. scikit-learn's `estimate_bandwidth` sets it to the average, over points, of the distance to the $q\cdot n$-th nearest neighbour (default quantile $q=0.3$). On the twelve check-ins it returns $h=1.734$, inside the 1.5–2.6 range that yields the 4 natural clusters. A sturdier habit is to sweep $h$ and look for the **widest plateau** in the number of clusters — on this data that is the 4-cluster plateau from $h=1.5$ to $2.6$.

Knobs worth knowing (scikit-learn names where they exist).

| 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 $h_i$ (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 $k$ centroids to the mean of their Voronoi cell, mean shift moves every seed to the mean of its distance window. Mean shift needs no $k$ 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 $K$ parametric components; mean shift's density is non-parametric (one bump per point) and $K$ 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
import numpy as np

def mean_shift(X, h, kernel="flat", tol=1e-3, max_iter=300):
    """Move every point uphill on the KDE; merge modes closer than h."""
    modes, intensity = [], []
    for x in X.astype(float):
        for _ in range(max_iter):
            d2 = ((X - x) ** 2).sum(axis=1)
            if kernel == "flat":
                w = (d2 <= h * h).astype(float)          # uniform window of radius h
            else:
                w = np.exp(-d2 / (2 * h * h))            # Gaussian, std h
            new = w @ X / w.sum()                        # weighted mean of the window
            done = np.linalg.norm(new - x) <= tol * h
            x = new
            if done:
                break
        modes.append(x)
        intensity.append(int((((X - x) ** 2).sum(axis=1) <= h * h).sum()))
    # keep the densest modes; drop any mode within h of one already kept
    order = np.argsort(intensity, kind="stable")[::-1]
    centers = []
    for i in order:
        if all(np.linalg.norm(modes[i] - c) > h for c in centers):
            centers.append(modes[i])
    centers = np.array(centers)
    labels = np.argmin(((X[:, None] - centers[None]) ** 2).sum(-1), axis=1)
    return centers, labels

X = np.array([[1, 1], [2, 1], [1, 2], [2, 3], [3, 2],
              [6, 6], [7, 6], [6, 7], [8, 7], [7, 8],
              [4, 4.5], [9, 2]])
centers, labels = mean_shift(X, h=2.2)
print(centers.round(2))   # [[6.8 6.8] [1.8 1.8] [9. 2.] [4. 4.5]]
print(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
import numpy as np
from sklearn.cluster import MeanShift, estimate_bandwidth

X = np.array([[1, 1], [2, 1], [1, 2], [2, 3], [3, 2],
              [6, 6], [7, 6], [6, 7], [8, 7], [7, 8],
              [4, 4.5], [9, 2]])

print("estimated h:", round(estimate_bandwidth(X), 3))   # 1.734
ms = MeanShift(bandwidth=2.2).fit(X)
print(ms.cluster_centers_.round(2))   # [[6.8 6.8] [1.8 1.8] [9. 2.] [4. 4.5]]
print(ms.labels_)                     # [1 1 1 1 1 0 0 0 0 0 3 2]
print("predict (5, 5):", ms.predict([[5, 5]]))   # [3] -- nearest centre, no climbing

for h in [1.2, 2.2, 3.0, 4.0, 4.5]:
    print(h, len(MeanShift(bandwidth=h).fit(X).cluster_centers_), "clusters")
# 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.

**Strengths**

- 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.

**Limitations**

- 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.

- **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.

> **Unscaled features break the window:** The window is a Euclidean disc of radius $h$. If one feature is in metres and another in kilometres, the disc is effectively a thin strip and only the large-scale feature matters. Standardise (or deliberately weight) features before choosing $h$ — and re-choose $h$ after any rescaling.

> **predict is not the basin of attraction:** scikit-learn's `predict` returns the nearest cluster centre. For points between hills this can differ from where the point would actually climb: in the worked example, (5, 5) climbs into neighbourhood B but is predicted to be in point 11's singleton cluster. If basin membership matters, run the climb for new points (it is cheap — a handful of shifts).

> **Singleton clusters are a feature, until they are not:** With a small $h$ every isolated point becomes its own mode and its own cluster (8 clusters at $h=1.2$ on twelve points). Either drop clusters below a minimum size, set `cluster_all=False` and a `min_bin_freq`, or treat singletons as outliers explicitly.

> **No learning rate, by design:** Because $m(x)=h^2\nabla\log\hat f(x)$ for the Gaussian kernel, mean shift is gradient ascent on the log-density whose step size is chosen by the data: big strides across empty space, tiny steps near a peak. That is why it converges without any tuning beyond $h$ — and why $h$ alone decides how many hills there are.

**Question:** 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?

- A. (1, 1) — it is already a data point
- B. (1.333, 1.333)
- C. (1.5, 1.5)
- D. (1.8, 1.8)

**Answer:** B. (1.333, 1.333) — With the flat kernel the new position is the plain average of the window: $\big(\tfrac{1+2+1}{3},\tfrac{1+1+2}{3}\big)=(1.333, 1.333)$. It reaches (1.8, 1.8) only on the next step, once points (2, 3) and (3, 2) are inside the window.

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

- A. Nothing — mean shift is scale-free
- B. More clusters, because each window sees more points
- C. Fewer clusters: the hills fuse, and at h = 4.5 everything is one cluster
- D. It no longer converges

**Answer:** C. Fewer clusters: the hills fuse, and at h = 4.5 everything is one cluster — A wider kernel smooths the density, so neighbouring peaks merge. scikit-learn goes from 4 clusters at h = 2.2 to 3 at 3.0, 2 at 4.0 and 1 at 4.5.

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

- A. Because it is defined as the direction of steepest ascent, computed numerically
- B. Because the KDE's gradient equals a positive scalar times (weighted window mean − x)
- C. Because the window always contains more points ahead than behind by construction
- D. It doesn't; it points to the nearest data point

**Answer:** B. Because the KDE's gradient equals a positive scalar times (weighted window mean − x) — Differentiating the KDE gives $\nabla\hat f_K(x)=\tfrac{2c_k}{nh^{d+2}}\big(\sum_i g_i\big)\,m(x)$. The scalar is positive, so $m(x)$ has the gradient's direction, and $m(x)=0$ exactly at stationary points.

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

- A. Mean shift needs a bandwidth h; k-means needs the number of clusters k
- B. Both need k
- C. Mean shift needs k; k-means needs h
- D. Neither needs any hyperparameter

**Answer:** A. Mean shift needs a bandwidth h; k-means needs the number of clusters k — Mean shift trades k for a length scale h. The number of clusters is an output — the number of distinct modes of the density at that scale.

**Key points**

- 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\leftarrow\sum_i x_i g_i/\sum_i g_i$. Its step $m(x)$ is proportional to $\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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
