Mean shift clustering

The problem, from first principles

k-means needs you to choose k. Mean shift does not. Think of each point as a climber on a density landscape: it repeatedly moves to the weighted average of nearby points, which climbs toward a peak. Points that climb to the same peak belong to the same cluster, and the number of peaks is discovered from the data, controlled by one bandwidth parameter.

Implement mean_shift(X, bandwidth, max_iter=300, tol=1e-6), which returns integer cluster labels with the Gaussian kernel.

1. Start each point at its own position.
2. Move each point to the kernel-weighted mean of all data, with weights w = exp(−‖m − x‖² / (2h²)). Repeat until the largest move is below tol or max_iter is reached.
3. Merge converged positions: walk through them in order, and assign each to an existing mode if it lies within bandwidth / 2 of that mode, otherwise start a new mode.
4. Labels are the mode indices, numbered from 0 in order of creation.

Constraints

• bandwidth must be positive, otherwise raise ValueError.
• Do not modify X.

Hints

Open one at a time. Each gives away a little more than the last.