We answer the question: "Does local progress (on batches) imply global progress (on the entire dataset) for mini-batch $k$-means?". Specifically, we consider mini-batch $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 $\tilde{\Omega}((d/\epsilon)^2)$, it must terminate within $O(d/\epsilon)$ iterations with high probability, where $d$ is the dimension of the input, and $\epsilon$ 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.


翻译:摘要:我们回答了问题:"小批量k均值聚类中的局部进展(在批处理上)是否意味着全局进展(在整个数据集上)?". 具体而言,我们考虑了只有在采样批次中聚类质量的改进低于某个阈值时才终止的小批量k均值聚类。虽然乍一看该算法可能会无限执行,但我们肯定答案并表明,如果样本批次的大小为$\tilde{\Omega}((d/\epsilon)^2)$,则它必须在高概率下在$O(d/\epsilon)$次迭代内终止,其中$d$是输入的维度,$\epsilon$是终止的阈值参数。这对于中心如何初始化都是正确的。当使用$k$-means++初始化方案初始化算法时,它达到了$O(\log k)$的近似比(与完整批次版本相同)。最后,我们展示了我们的结果适用于scikit-learn(sklearn)python库中实现的小批量k均值聚类算法。

0
下载
关闭预览

相关内容

【ICDM 2022教程】图挖掘中的公平性:度量、算法和应用
专知会员服务
27+阅读 · 2022年12月26日
专知会员服务
25+阅读 · 2021年4月2日
专知会员服务
50+阅读 · 2020年12月14日
系列教程GNN-algorithms之七:《图同构网络—GIN》
专知会员服务
47+阅读 · 2020年8月9日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
浅聊对比学习(Contrastive Learning)第一弹
PaperWeekly
0+阅读 · 2022年6月10日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
RF、GBDT、XGBoost面试级整理
数据挖掘入门与实战
17+阅读 · 2018年3月21日
BAT机器学习面试题1000题(316~320题)
七月在线实验室
14+阅读 · 2018年1月18日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年5月19日
Meta-Learning with Implicit Gradients
Arxiv
13+阅读 · 2019年9月10日
Simplifying Graph Convolutional Networks
Arxiv
12+阅读 · 2019年2月19日
VIP会员
相关资讯
浅聊对比学习(Contrastive Learning)第一弹
PaperWeekly
0+阅读 · 2022年6月10日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
RF、GBDT、XGBoost面试级整理
数据挖掘入门与实战
17+阅读 · 2018年3月21日
BAT机器学习面试题1000题(316~320题)
七月在线实验室
14+阅读 · 2018年1月18日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员