对于 vanilla K-Means 聚类算法，我知道时间复杂度为：
时间复杂度：O(tknm)，
其中 n 是数据点的数量，k 是聚类的数量，t 是迭代次数，m 是向量的维数。
所以，当我研究 Mini-batch K-Means 以使算法更快收敛时，我想知道它的空间和时间复杂度是多少？
从本质上讲，我很好理解，我们在 vanilla K-Means 上优化了多少。
Mini-Batch K-Means 聚类算法的空间和时间复杂度是多少？
数据挖掘
分类
聚类
算法
k-均值
2022-02-14 08:45:55
1个回答
无限的。
小批量 k-means 永远不会收敛，您需要使用迭代限制或类似的启发式方法，并且您永远无法保证找到局部最优值。
本质上，小批量 k-means 是：
- 抽取随机样本
- 使用此样本执行一次 k-means 迭代
- 重复
假设您的样本量为 N，则 2 需要 O(k N mt) 时间。
其它你可能感兴趣的问题