Generalized mean shift with triangular kernel profile

Sébastien Razakarivony, Axel BarrauarXiv 2020 · arXiv · OpenReview

TL;DR

This paper introduces a novel variant of the Mean Shift algorithm, specifically tailored for triangular kernel profiles, and proves its convergence in a finite number of steps. This work also proposes a Wasserstein Median Shift algorithm, which demonstrates superior performance in histogram clustering compared to traditional L2-norm-based methods.

What Problem Does This Paper Address?

The Mean Shift algorithm is a powerful tool for finding modes in probability density functions, widely used in clustering and visual tracking. However, a clear and universally accepted theoretical understanding of its convergence properties, especially for generalized kernels and distances, has remained an open problem. This paper addresses this by focusing on a specific class of kernels (triangular profiles) and proposing a new algorithm (Wasserstein Median Shift) that tackles the challenge of clustering histograms, where traditional L2-norm-based approaches struggle due to their insensitivity to bin order.

Methods

The paper builds upon the existing Mean Shift framework, which can be interpreted as a weighted average, gradient ascent, or bound optimization. The authors generalize the Mean Shift algorithm to work with arbitrary distance functions, not just Euclidean. They then focus on the specific case of a "triangular" kernel profile, which leads to a "flat" weighting function. For this specific case, they derive a novel iterative update rule and prove that the sequence of estimates converges to a stationary point in a finite number of steps.

A key contribution is the development of the Wasserstein Median Shift algorithm. This algorithm leverages the Wasserstein metric (Earth Mover's Distance) for comparing histograms, which is more suitable than the L2-norm because it accounts for the order of histogram bins. The algorithm cleverly reformulates the optimization problem in the space of cumulated histograms, allowing for efficient computation and demonstrating convergence.

Datasets

The paper evaluates its proposed algorithms on two types of datasets:

  • Synthetic Dataset: This dataset consists of empirical histograms generated from two classes of random variables: Gaussian variables with similar means and variances, and mixtures of two Gaussian variables. This dataset was specifically designed to highlight the limitations of L2-norm-based histogram clustering.
  • Real Aeronautical Data: This dataset comprises 122 time series representing helicopter flight altitudes. These time series are converted into histograms for comparison, addressing the challenge of comparing variable-length sequences.

Key Insights and Ideas

  • Generalizing Mean Shift: The paper demonstrates that Mean Shift can be generalized to work with non-Euclidean distances, opening up possibilities for applying it to more diverse data types.
  • Triangular Kernel Convergence: By focusing on triangular kernel profiles, the authors achieve a significant theoretical breakthrough: proving convergence in a finite number of steps for a generalized Mean Shift variant. This provides a stronger theoretical guarantee than previously established for many Mean Shift variations.
  • Wasserstein Metric for Histograms: The core insight for histogram clustering is that the Wasserstein metric is far more effective than the L2-norm because it respects the inherent order of histogram bins. This is crucial for applications where the relative positions of bins carry significant meaning.
  • Cumulated Histograms for Efficiency: The clever use of cumulated histograms transforms the complex Wasserstein distance calculation into a simpler L1-norm problem, making the Wasserstein Median Shift algorithm computationally tractable.

Key Results

  • Theoretical Convergence: The paper proves that the generalized Mean Shift algorithm with triangular kernel profiles converges to a stationary point in a finite number of steps, regardless of the distance metric used.
  • Wasserstein Median Shift Performance: Experimental results show that the Wasserstein Median Shift algorithm significantly outperforms classical Mean Shift and other clustering algorithms (like K-means, DBSCAN, etc.) on both the synthetic and real datasets, particularly in histogram clustering tasks.
  • Improved Wasserstein Variants: Modified versions of K-means and DBSCAN using the Wasserstein metric also show improved performance over their L2-norm counterparts, further validating the metric's suitability for histogram data.

Limitations and Future Work

  • Limited Kernel Scope: The theoretical convergence proof is specific to triangular kernel profiles. The authors suggest exploring extensions to other kernel profiles in future work.
  • Bandwidth Adaptation: The current algorithms use a fixed bandwidth. Future research could investigate methods for adapting bandwidths to local sample densities.
  • Clustering with Varying Bandwidths: Extending the algorithms to handle clustering with different bandwidths for different samples is another avenue for future exploration.

Summary updated

Abstract

The mean shift algorithm is a popular way to find modes of some probability density functions taking a specific kernel-based shape, used for clustering or visual tracking. Since its introduction, it underwent several practical improvements and generalizations, as well as deep theoretical analysis mainly focused on its convergence properties. In spite of encouraging results, this question has not received a clear general answer yet. In this paper we focus on a specific class of kernels, adapted in particular to the distributions clustering applications which motivated this work. We show that a novel Mean Shift variant adapted to them can be derived, and proved to converge after a finite number of iterations. In order to situate this new class of methods in the general picture of the Mean Shift theory, we alo give a synthetic exposure of existing results of this field.
BibTeX
@misc{razakarivony2020generalized,
  author = {Sébastien Razakarivony and Axel Barrau},
  title = {{Generalized mean shift with triangular kernel profile}},
  year = {2020},
  eprint = {2001.02165},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2001.02165},
}
Figure