aiqbench analysis
This research proposes a novel variation of the k-means++ algorithm where the number of clustering centers is randomized within a specific range, demonstrating an improved approximation ratio under adversarial conditions. By shifting from a fixed center count to a budget-smoothed selection process, the study offers significant theoretical insights for optimizing unsupervised learning initialization strategies in high-dimensional data scenarios.
Randomizing the Number of Centers in k-means++
arXiv:2607.26202v1 Announce Type: cross Abstract: The $k$-means++ algorithm is a standard and widely used seeding method for $k$-means clustering, but for a fixed number $k$ of centers its worst-case expected approximation ratio is $\Theta(\log k)$. We consider the same algorithm when an adversary first fixes the dataset and some $K$; the number of centers $k$ is then chosen uniformly from $\{K,\ldots,2K-1\}$. We prove that $k$-means++ is an $O(1)$-approximation with constant probability in this budget-smoothed setup.
Abstract:The $k$-means++ algorithm is a standard and widely used seeding method for $k$-means clustering, but for a fixed number $k$ of centers its worst-case expected approximation ratio is $\Theta(\log k)$. We consider the same algorithm when an adversary first fixes the dataset and some $K$; the number of centers $k$ is then chosen uniformly from $\{K,\ldots,2K-1\}$. We prove that $k$-means++ is an $O(1)$-approximation with constant probability in this budget-smoothed setup.
Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Machine Learning (stat.ML)
arXiv:2607.26202 [cs.DS]
(or arXiv:2607.26202v1 [cs.DS] for this version)
https://doi.org/10.48550/arXiv.2607.26202 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 172 words
