Mini-batch k-means terminates within O(d/ε) iterations
Mini-batch k-means terminates within O(d/ε) iterations
复制标题
DOI：
10.48550/arxiv.2304.00419
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Gregory Schwartzman
中科院分区：
文献类型：
--
作者：
Gregory Schwartzman
我们回答这个问题：“局部进度（在批次上）是否意味着小批量 k 均值的全局进度（在整个数据集上）？”。具体来说，我们考虑小批量 k 均值，仅当采样批次的聚类质量改进低于某个阈值时才会终止。尽管乍一看该算法可能会永远执行，但我们对上述问题的回答是肯定的，并表明如果批量大小为 Ω̃((d/ε))，则它必须以高概率在 O(d/ε) 次迭代内终止，其中 d 是输入的维度，ε 是终止的阈值参数。无论中心如何初始化，都是如此。当算法使用 k-means++ 初始化方案初始化时，它实现了 O(log k) 的近似率（与 full-batch 版本相同）。最后，我们展示了我们的结果对 scikit-learn (sklearn) python 库中实现的小批量 k 均值算法的适用性。
We answer the question: "Does local progress (on batches) imply global progress (on the entire dataset) for mini-batch k-means?". Specifically, we consider minibatch k-means which terminates only when the improvement in the quality of the clustering on the sampled batch is below some threshold. Although at first glance it appears that this algorithm might execute forever, we answer the above question in the affirmative and show that if the batch is of size Ω̃((d/ε)), it must terminate within O(d/ε) iterations with high probability, where d is the dimension of the input, and ε is a threshold parameter for termination. This is true regardless of how the centers are initialized. When the algorithm is initialized with the k-means++ initialization scheme, it achieves an approximation ratio of O(log k) (the same as the full-batch version). Finally, we show the applicability of our results to the mini-batch k-means algorithm implemented in the scikit-learn (sklearn) python library.