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