Clustering is a cornerstone of unsupervised learning, yet traditional algorithms often struggle with the dual challenges of high dimensionality and computational scale. This paper, presented at AAAI-23, introduces UEQMS, a framework that revitalizes the classic Mean Shift (MS) algorithm for the modern era. By integrating UMAP dimensionality reduction with a novel "Quick Mean Shift" (QMS) optimization, UEQMS achieves clustering speeds up to $10^7$ times faster than vanilla Mean Shift while maintaining superior accuracy.
The Challenge: Complexity and the Curse of Dimensionality
Mean Shift is a "mode-seeking" algorithm that identifies clusters by finding dense regions in data without requiring a predefined cluster count ($k$). However, it faces two primary hurdles:
- Computational Cost: Vanilla MS scales at $O(n^2)$, making it impractical for large datasets.
- Dimensionality: While variants like MeanShift++ (MS++) use grid-based partitioning to improve speed, their complexity grows exponentially with dimensions ($O(3^d)$). In spaces with more than five dimensions, MS++ often becomes slower than the original algorithm.
Furthermore, MS++ lacked a formal proof of convergence, and its non-smooth kernel could lead to the algorithm getting stuck at suboptimal "non-critical" points.
The UEQMS Framework
To address these limitations, the authors proposed a three-part solution:
1. UMAP Embedding
UEQMS utilizes Uniform Manifold Approximation and Projection (UMAP) to project high-dimensional data onto a low-dimensional (2D or 3D) manifold. This step is crucial because UMAP preserves both local and global structures, effectively acting as a denoiser that makes the data more "clusterable" for density-based methods.
2. Quick Mean Shift (QMS)
The authors observed that grid-based clustering in MS++ results in significant redundant work, as many points in the same grid cell undergo identical shifts. QMS optimizes this by using hash tables to store cell sums and counts, processing only unique grid positions. This refinement makes QMS roughly 40x faster than MS++ on standard datasets.
3. Theoretical Rigor
The paper provides the first formal theoretical analysis of the MeanShift++ family. By defining the kernel function numerically and introducing a specific step to handle non-smooth points, the authors guarantee convergence in a finite number of iterations.
Key Results and Performance
UEQMS was evaluated against a wide array of benchmarks, including sensor data, medical datasets, and image sets like MNIST. The results demonstrate a dramatic improvement in both efficiency and clustering quality.
- Speed: On high-dimensional data, UEQMS is approximately $10^7$ times faster than vanilla Mean Shift. For instance, on the "Skin" dataset (~245k points), QMS finished in 0.28 seconds, compared to 12.58 seconds for MS++.
- Accuracy: On MNIST, UEQMS achieved an Adjusted Rand Index (ARI) of 0.88, significantly outperforming deep clustering models like DeepCluster (0.66) and DCN (0.81).
Conclusion
UEQMS successfully bridges the gap between the intuitive mode-seeking nature of Mean Shift and the requirements of high-dimensional, large-scale data processing. By leveraging the manifold-preserving properties of UMAP and the algorithmic efficiency of QMS, the framework provides a mathematically grounded, highly efficient alternative to both traditional and deep clustering methods.
Summary updated