UEQMS: UMAP Embedded Quick Mean Shift Algorithm for High Dimensional Clustering

Abhishek Kumar, Swagatam Das, Rammohan MallipeddiAAAI 2023 · DOI

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:

  1. Computational Cost: Vanilla MS scales at $O(n^2)$, making it impractical for large datasets.
  2. 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.

UMAP visualization demonstrating clear manifold structure and cluster separation, which facilitates more effective density-based clustering.

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.

Performance comparison table showing UEQMS achieving the highest NMI and ARI scores while maintaining a significantly lower runtime (RT) compared to traditional and accelerated Mean Shift variants.
  • 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

BibTeX
@inproceedings{kumar2023ueqms,
  author = {Abhishek Kumar and Swagatam Das and Rammohan Mallipeddi},
  title = {{UEQMS: UMAP Embedded Quick Mean Shift Algorithm for High Dimensional Clustering}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i7.26011},
}
Figure