提出可解释的重启准则，自动判断k-means++何时停止重试
An interpretable Good--Turing restart criterion for k-means++
- 基于Good-Turing估计与置信度，动态评估继续重启的收益
- 在34个真实数据集上验证，显著减少无效重启次数
- 适合对计算效率敏感或需可解释性聚类的场景
k-means++算法通常多次重启以避免局部最优，但重启次数常随意设定且对所有数据集相同，导致比较不可靠，易浪费计算资源于简单数据集，又可能低估困难数据集需求。本文提出Good-Turing重启准则（GTRC），结合Good-Turing估计、已证明的无条件界和基于置信度的进一步重启收益概率界，当该概率低于用户设定容差时停止。在34个真实数据集上的实验表明，GTRC能准确识别出继续重启不再带来显著改进的点，在重启次数与聚类质量之间取得更优平衡，优于三种现有多起点局部搜索停止规则及常见固定重启数。代码开源：https://github.com/RCdeAmorim/Good-Turing-Restart-Criterion。
原文摘要 · Abstract (English)
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: https://github.com/RCdeAmorim/Good-Turing-Restart-Criterion.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。