Search papers, labs, and topics across Lattice.
This paper introduces the Good-Turing Restart Criterion (GTRC) for the k-means++ algorithm, which adaptively determines the number of restarts based on the difficulty of the dataset rather than using a fixed count. By leveraging a Good-Turing estimate and confidence bounds, GTRC stops restarting when the probability of improvement falls below a specified threshold, optimizing computational resources while maintaining clustering quality. In experiments across 36 datasets, GTRC achieved clustering results comparable to traditional methods with a variable number of restarts, demonstrating its effectiveness in adapting to dataset complexity.
GTRC intelligently adjusts the number of k-means++ restarts based on dataset difficulty, optimizing performance and efficiency without sacrificing clustering quality.
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. We introduce GTRC, a restart criterion combining 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 $\varepsilon$. Across 36 data sets, GTRC reached clustering quality competitive with well-chosen fixed restart counts, while the number of restarts used varied considerably and appropriately with data set difficulty, governed by an interpretable, data-dependent signal rather than a fixed rule. GTRC offers a principled and reportable alternative to fixing the number of $k$-means++ restarts in advance. Software:https://github.com/RCdeAmorim/Good-Turing-Restart-Criterion.
