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

k-means++ is the standard algorithm for clustering, but it is sensitive to the random selection of initial centroids. To mitigate this, practitioners typically restart the algorithm multiple times and select the best result. However, the number of restarts is almost always chosen arbitrarily—often set to a fixed value like 10, 20, or 100—and applied uniformly across all datasets. This approach is inefficient: it wastes computational resources on simple datasets while potentially failing to find high-quality solutions on complex, difficult datasets. There has historically been no principled, data-driven way to decide when to stop restarting.

The author introduces GTRC, a stopping rule that uses a combination of three theoretical bounds to estimate the probability that a further restart will yield a better clustering objective than the best one found so far. The algorithm stops once this estimated probability falls below a user-specified tolerance level, ε.

The criterion integrates three distinct approaches:

1. Good–Turing Estimation: Estimates the probability of observing a previously unseen (and potentially better) objective value.
2. Unconditional Bound: A theoretical limit derived from the properties of the k-means++ objective function.
3. Confidence-based Bound: Uses a Clopper–Pearson lower confidence bound to estimate the probability of hitting the current best-observed partition again.

By taking the minimum of these three bounds, GTRC provides a robust, interpretable signal that adapts to the specific structure of the data.

Experimental results across 36 diverse datasets show that GTRC performs as well as, or better than, fixed-restart strategies. Crucially, the number of restarts required by GTRC varies significantly depending on the dataset's complexity, demonstrating that the algorithm successfully identifies when further computation is likely to be fruitful. This provides researchers with a reportable, reproducible alternative to arbitrary restart counts, ensuring that comparisons between clustering algorithms are not biased by inconsistent baseline efforts.