PaperlayerView exact revision on arXiv

Source-linked AI summary

A review of mean-shift algorithms for clustering

Miguel Á. Carreira-Perpiñán

arXiv:1503.00687v1cs.LGcs.CVstat.ML

TL;DR

The paper considers how to define clusters from high-density regions while avoiding some difficulties of parametric mixture models. It reviews KDE-based mean-shift methods and related algorithms, and concludes that mean-shift suits low-dimensional nonconvex data while K-modes methods perform well with high-dimensional data and outliers.

  • Problem

    Parametric mixture models can be sensitive to initialization and require users to choose a model and cluster count, while complex cluster shapes may require many components.

    Source: §1 · p. 1

  • Method

    The review synthesizes KDE-based clustering with mean-shift, covering its theory, variants, extensions, accelerations, K-modes methods, and applications.

    Source: §1 · p. 1, §2.3 · p. 9, §2.6 · p. 14

  • Results

    Mean-shift can model nonconvex clusters and, despite its computational cost, can be accelerated to scale to large datasets; (Laplacian) K-modes perform well with high-dimensional data and outliers.

    Source: §5 · p. 21

  • Takeaways & Limitations

    Mean-shift is popular for low-dimensional nonconvex clustering, particularly image segmentation, while K-modes methods remain an option for high-dimensional data and outliers.

    Source: §5 · p. 21

    KDE modes can change abruptly with small bandwidth decreases in high dimensions, and most successful mean-shift applications have been low-dimensional.

    Source: §2.1 · p. 7

Abstract

from arXiv · show

A natural way to characterize the cluster structure of a dataset is by finding regions containing a high density of data. This can be done in a nonparametric way with a kernel density estimate, whose modes and hence clusters can be found using mean-shift algorithms. We describe the theory and practice behind clustering based on kernel density estimates and mean-shift algorithms. We discuss the blurring and non-blurring versions of mean-shift; theoretical results about mean-shift algorithms and Gaussian mixtures; relations with scale-space theory, spectral clustering and other algorithms; extensions to tracking, to manifold and graph data, and to manifold denoising; K-modes and Laplacian K-modes algorithms; acceleration strategies for large datasets; and applications to image segmentation, manifold denoising and multivalued regression.

1 Introduction

The introduction motivates density-based clustering and presents KDE modes with mean-shift as a nonparametric route to clusters, including complex nonconvex shapes. It previews the review’s theoretical, algorithmic, and application topics.

1 Introduction

  • Parametric Gaussian mixtures can fit elliptical clusters efficiently, but local optima, initialization, model selection, and complex shapes can make them costly or difficult to use.Approximating complex clusters may require many mixture components, increasing training time and the number of local optima.Source: §1 · p. 1
  • KDEs provide smooth density estimates whose modes define clusters; mean-shift seeks those modes from data-point initializations, with bandwidth determining the KDE and its clusters.The resulting clusters can be complex and nonconvex, without requiring the user to specify their number or use random restarts.Source: §1 · p. 1
  • The review covers mean-shift theory and variants, related algorithms, extensions, acceleration, K-modes methods, and applications, assuming multivariate continuous data.Applications include image segmentation, inverse problems, denoising, and other areas.Source: §1 · p. 2

2 Problem formulation and mean-shift algorithms

This section formulates mean-shift clustering through kernel-density modes and weighted-average updates, covering non-blurring and blurring variants. It develops their convergence and geometric properties, connections to spectral clustering and related optimization problems, extensions to tracking and non-Euclidean data and denoising, and acceleration strategies.

2 Problem formulation and mean-shift algorithms

  • The mean-shift update averages data-point shifts with kernel-based weights; MS assigns points to the modes they converge to, while BMS updates every data point.The presentation focuses mainly on Gaussian kernels and a shared scalar bandwidth, though extensions allow point-specific weights and bandwidths.Source: §2 · p. 3, §2.1 · pp. 3–4

2.1 Two basic types of mean-shift algorithms: MS and BMS

  • MS and BMS can yield different cluster counts at a fixed bandwidth, although their clusterings across a bandwidth range can be similar; BMS quickly forms tight clusters before all points eventually coincide.BMS is faster than MS in iterations and runtime, and an entropy-change criterion can detect the tight-cluster stage before the slower subsequent collapse.Source: §2.1 · p. 4
  • Bandwidth determines the number of clusters, so a bandwidth optimal for density estimation need not be best for clustering, and exploring a range is recommended.Adaptive KDEs can instead set a bandwidth per point, for example by choosing each to yield a target perplexity k of effective neighbors.Source: §2.1 · p. 5
  • Scale-space clustering tracks modes as bandwidth increases and uses their lifetime as an indicator of importance, but the resulting clusterings need not be nested.In dimensions above one, modes can be created as scale decreases; such events are described as generally rare and short-lived in practice.Source: §2.1 · pp. 5–6
  • Mean shift needs no explicit cluster-count choice and can model nonconvex clusters, but KDE clustering can change abruptly with bandwidth in high dimensions and offers no direct control over cluster count.Outliers can form their own modes, and computational cost is another disadvantage; mean shift is also most successful in low-dimensional applications.Source: §2.1 · p. 7

2.2 Origins of the mean-shift algorithm

  • Fukunaga and Hostetler proposed BMS for an Epanechnikov KDE, while Carreira-Perpiñán independently rediscovered Gaussian mean shift and proved convergence for arbitrary covariance matrices.Comaniciu and Meer later demonstrated non-blurring mean shift in image filtering and segmentation.Source: §2.2 · p. 7

2.3 Theoretical results about mean-shift algorithms and Gaussian mixtures

  • A Gaussian mixture has at most N modes in one dimension, but can have more than N in dimension two or higher, even with isotropic components; mode locations can also depend on covariance structure.With isotropic components, modes lie inside the data convex hull, whereas diagonal or full covariance components can produce modes outside it; some kernels can produce continuous ridges of modes.Source: §2.3 · p. 8
  • Convergence depends on the kernel: Epanechnikov mean shift converges in finitely many iterations, whereas Gaussian mean shift converges in infinitely many, generally at a linear rate.For kernels where MS converges, most initial points reach a mode, though convergence can be to a stationary point such as a minimum or saddle; some valid kernels can diverge.Source: §2.3 · pp. 8–9
  • Gaussian mean-shift is an EM algorithm with guaranteed convergence and nondecreasing density, while non-Gaussian mean-shift is generalized EM whose update may not increase likelihood.For non-Gaussian kernels, the update is a single iteration toward the M-step solution, and likelihood increase depends on the kernel.Source: §2.3 · p. 9
  • Near a mode, Gaussian mean-shift converges linearly at a bandwidth-dependent rate, follows local covariance directions within the data convex hull, and can have curved, disconnected convergence regions.Its shift vector is proportional to the density gradient, but the step is not optimal along that gradient.Source: §2.3 · pp. 9–10
  • Broad-kernel BMS collapses all points together; sufficiently narrow finite-support kernels yield coincident within-cluster points, while Gaussian BMS rapidly collapses clusters and can leave temporary line-shaped remnants.For Gaussian data, each principal-axis standard deviation shrinks cubically; finite-sample variance need not decrease at every step.Source: §2.3 · p. 10

2.4 Relations with other algorithms

  • BMS and spectral clustering share random-walk affinities but differ in outputs and controls: spectral clustering sets K and solves an eigenproblem, whereas BMS sets bandwidth and infers clusters through iterative matrix products.Generalized BMS implicitly transforms the spectrum without computing eigenvectors.Source: §2.4 · p. 11

2.5 Extensions of mean-shift for clustering

  • Extensions use KDE similarity maximization to track objects, adapt updates to known or unknown manifolds, and assign graph points to higher-density parents to form mode-rooted clusters [51].The graph-based parent search optimizes over observed data points rather than the full Euclidean space.Source: §2.5 · p. 12
  • Other variants include medoidshift's discrete center-of-mass filtering [75], score-matching weighted-kernel updates [71], Kendall-distance ranking updates, and functional-data adaptive gradient ascent [26].Score-matching updates with negative weights are not guaranteed to converge.Source: §2.5 · p. 13

2.6 Extensions of mean-shift beyond clustering: manifold denoising

  • Early mean-shift iterations denoise manifold data, while MBMS removes tangential motion to preserve local structure and can improve classifier performance on denoised MNIST images.MBMS estimates local tangent spaces with nearest-neighbor PCA and stops using a criterion comparing orthogonal and tangent eigenvalues.Source: §2.6 · pp. 13–14

2.7 Accelerated mean-shift algorithms

  • Mean-shift is computationally quadratic in dataset size and may need many iterations, motivating approximate methods; Epanechnikov mean-shift converges finitely and can use known neighborhoods without approximation.The iterations for different points are independently parallelizable.Source: §2.7 · p. 15
  • Gaussian MS costs O(IDN^2) over the dataset because convergence may take many iterations and each iteration averages over N points.The iteration count can grow when modes are close, and acceleration should preserve a clustering close to naive MS.Source: §2.7 · p. 15
  • MS-Newton accelerates convergence by starting with MS iterations and switching to Newton’s method, which has quadratic convergence but may introduce parameters or change the converged mode.Newton steps may also be ineffective far from a mode, where the Hessian is undefined.Source: §2.7 · p. 15
  • Per-iteration costs can be reduced with nearby-point approximations or N-body methods, though neighbor search may still cost O(N), and N-body methods suit low dimensions.Fast Gauss transforms or tree structures can reduce the cost for all points to O(N) or O(N log N), respectively; large bandwidths can make many data points relevant.Source: §2.7 · p. 15
  • Spatial discretization avoids assigning points by nearest neighbor alone, instead tracking MS trajectories and stopping a point when its iterate nears an existing trajectory’s mode.For image segmentation, subpixel cells encode visited trajectories, reducing average iterations per point to nearly 1 with very small, controllable clustering error.Source: §2.7 · pp. 15–16
  • Yuan et al. show that points within distance ∥y − x∥ of the post-step point y have KDE value at least p(x), enabling many points to skip iterations and share x’s mode assignment.Not all such points converge to the same mode; using radius r∥y − x∥ with r ∈ [0, 1] can control approximation error.Source: §2.7 · p. 16
  • Accelerated BMS alternates a BMS step with connected-components contraction, replacing collapsed clusters with weighted points while retaining equivalence to original BMS.The contraction threshold ǫ sets the method’s resolution and is applied at each iteration; the approach has essentially zero approximation error when using coincident-point reduction.Source: §2.7 · p. 16
  • 2 to 4 times faster than BMS and 5 to 60 times faster than MS, accelerated BMS has nearly bandwidth-independent runtime on image segmentation.Its runtime corresponds to about 4 to 5 BMS iterations and is dominated by the first few iterations, when little merging occurs.Source: §2.7 · p. 16

3 K-modes and Laplacian K-modes algorithms

K-modes and Laplacian K-modes address mean-shift’s lack of direct control over cluster count and its convex-cluster limitation. K-modes targets exactly K modes, while Laplacian regularization allows nonconvex clusters with soft assignments.

3 K-modes and Laplacian K-modes algorithms

  • K-modes combines binary cluster assignments with mode-seeking in K separate KDEs, and its objective ranges from K-means as σ → ∞ to a K-medoids variant as σ → 0.The homotopy algorithm starts at σ = ∞ and gradually decreases σ; each iteration costs O(DNK), versus O(DN^2) for mean-shift, though it needs more iterations.Source: §3 · p. 17
  • K-modes [17] returns exactly K modes, even when the full-data KDE has more or fewer, and its homotopy procedure tracks major modes while avoiding outliers.It can work well in high dimensions, unlike mean-shift.Source: §3 · p. 17
  • K-modes [17] forms convex Voronoi clusters, whereas Laplacian K-modes [87] relaxes hard assignments and encourages neighboring points to have similar soft assignments.The neighbor-similarity term uses a graph Laplacian and weight λ ≥ 0.Source: §3 · p. 17
  • Laplacian K-modes [87] permits nonconvex clusters through a quadratic-program assignment step, returning a KDE, mode centroids, and soft assignments rather than spectral clustering’s hard assignments.At λ = 0 it reduces to K-modes; at σ = ∞ it becomes Laplacian K-means.Source: §3 · p. 17
  • Laplacian K-modes’ soft assignments can represent clustering uncertainty and serve as smooth pixel masks for image matting, conditional random fields, or saliency maps.For a test point, assignments can be interpreted as posterior probabilities of cluster membership.Source: §3 · pp. 17–18
  • Unlike means that can fall in low-density regions or noisy exemplars that may look atypical, KDE modes are scale-dependent local averages that can be valid, typical, denoised representatives.At intermediate bandwidth, modes average nearby data and can remove noise affecting individual exemplars.Source: §3 · p. 18

4 Examples, applications, software

The examples show mean-shift’s strong fit for low-dimensional image segmentation and its limits on manifold-structured and high-dimensional data. Conditional modes also support multivalued inversion, while mean-shift methods have applications beyond clustering.

Software

  • The review notes that Matlab code is available for most of the algorithms it describes.Source: §4 · p. 18

Image segmentation

  • Image segmentation applies mean-shift to pixel location and intensity features; the grayscale example produces five clusters at bandwidth 8 pixels.Spatial features encourage nearby pixels to share a cluster, and feature scaling affects the clustering.Source: §4 · pp. 18–19, Figure 5 · p. 19
  • Gaussian BMS yields seven clusters in the cameraman example, with rapid collapse supporting clustering and slower collapse along the principal direction supporting denoising.The sequence stops at iteration 11; without stopping, the clusters would eventually merge into one.Source: Figure 6 · p. 19

Cases when mean-shift clustering does not work well

  • No bandwidth clusters the spirals correctly with mean-shift: smaller bandwidths produce many modes, while larger ones mix manifolds; Laplacian K-modes succeeds.It also estimates a reasonable KDE and mode for each spiral.Source: §4 · p. 20
  • On 784-dimensional MNIST data, mean-shift tends toward one uninformative mode or many modes on small groups or outliers; Laplacian K-modes finds representative digit-like modes.K-means centroids can average distant points, potentially from different digit classes, and fail to look like digits.Source: §4 · p. 20

Multivalued regression and inversion

  • Conditional modes represent multiple outputs for an input and select the number of inverses automatically; conditional means can produce invalid inverses in robot kinematics and speech inversion.The speech example has three tongue-shape modes for one sound.Source: §4 · pp. 20–21

Other applications

  • Mean-shift has also been applied to video segmentation, image denoising, discontinuity-preserving smoothing, object tracking, and manifold and surface denoising.The review identifies image segmentation as its most successful application, particularly for low-dimensional data.Source: §4 · pp. 18, 21

5 Conclusion and open problems

The conclusion presents mean-shift as a nonparametric approach for modeling nonconvex clusters, with scale rather than cluster count specified by the user. It connects the algorithms to graph-based methods and identifies open problems in high-dimensional mixtures, directed graphs, matrix design, and KDE-based cluster definitions.

Conclusion

  • Mean-shift uses nonparametric KDEs, makes few data assumptions, models nonconvex clusters, and asks users to specify scale rather than the number of clusters.The conclusion also notes computational slowness, while stating that acceleration can make the algorithms scale to large datasets.Source: §5 · p. 21
  • The review positions mean-shift for low-dimensional nonconvex data such as image segmentation, while (Laplacian) K-modes also performs well with high-dimensional data and outliers.Source: §5 · p. 21

Relations to other algorithms

  • Mean-shift and blurring mean-shift alternate between smoothing data with a random-walk matrix P and updating P itself.The review relates this view to the graph Laplacian and random-walk matrix as objects that encode dataset geometry.Source: §5 · pp. 21–22

Open problems

  • Open problems include understanding high-dimensional Gaussian-mixture geometry, extending blurring mean-shift to directed graphs, and designing useful random-walk or Laplacian matrices.The review also asks for a KDE cluster definition based on distinct high-probability regions rather than modes.Source: §5 · p. 22

A Connected-components algorithm

Connected-components clusters points linked by distances below a threshold and can merge numerically distinct mean-shift iterates around the same mode. A tight-cluster assumption enables a faster representative-based implementation, with further heuristics for speed.

Connected-components algorithm

Use with mean-shift

  • As mean-shift iterates near the same mode can stop at slightly different points, connected-components can merge their tight groups as a postprocessing step.The resulting groups around different modes are widely separated.Source: A Connected-components algorithm · p. 22

Efficient implementation

  • Under the tight-cluster assumption, connected-components takes O(DNK) rather than the naive O(DN^2) time.The assumption requires a threshold larger than each component’s diameter but smaller than the distance between components.Source: A Connected-components algorithm · p. 22, Figure 9 · p. 23

Further acceleration

  • Incremental distance checks and raster-order pixel scanning can further reduce runtime; the latter has average cost O(ND) when most pixels share the previous pixel’s component.Incremental checks can reduce cost to O(N(K + D)) under the tight-cluster assumption.Source: A Connected-components algorithm · p. 22

Threshold choice

  • For image segmentation in pixel units, the threshold can be 0.5; BMS can use a smaller value such as 0.01 because its cubic convergence quickly forms tight clusters.Source: A Connected-components algorithm · p. 22
Loading 1503.00687v1…