An interpretable Good--Turing restart criterion for k-means++

Abstract:The k-means++ algorithm is commonly restarted multiple times to avoid poor local optima, yet the number of restarts is almost always chosen arbitrarily and applied uniformly regardless of data set difficulty. This undermines any comparison relying on such a choice and wastes computation on easy data sets while potentially under-serving hard ones. Here, we introduce the Good-Turing Restart Criterion (GTRC). This combines a Good-Turing estimate, a proven unconditional bound, and a confidence-based bound on the probability that a further restart would improve on the current result, stopping once this probability falls below a user-specified tolerance. Our experiments on 34 real-world data sets show that GTRC identifies the point beyond which further k-means++ restarts yield only negligible improvement, achieving a more favourable balance between the number of restarts used and clustering quality than three existing stopping rules for multistart local search and popular fixed restart counts. Software: this https URL.

Machine Learning (cs.LG); Machine Learning (stat.ML)

arXiv:2607.08243 [cs.LG]

(or arXiv:2607.08243v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2607.08243 Focus to learn more arXiv-issued DOI via DataCite

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.