前言

MiniBatchKmeans是Kmeans聚类算法的一种优化版本。
Kmeans算法的缺点：需要每一步都计算每个样本点和各个类别之间的距离，复杂度非常高。在面对大规模数据的时候，Kmeans往往需要非常长的时间去完成聚类。因此就产生了Kmeans算法的一种优化变种MiniBatchKmeans。

MiniBatchKmeans算法

算法每次迭代的时候只会采用随机产生的小批量的数据子集，这样可以大大减少计算时间，并且每次迭代中它仍会试图优化目标函数。并且在实际使用的过程中，MiniBatchKmeans的效果只会略差于标准算法。
MiniBatchKmeans聚类的迭代步骤如下：

1. 确定超参数聚类的类别数目K；
2. 随机抽取一个batch，使用Kmeans算法构建出K个簇；
3. 继续抽取一个batch，将他们添加到模型中，分配给最近的簇中心；
4. 参考Kmeans聚类更新簇中心，更新只用本次抽取的数据子集；
5. 循环迭代步骤3),4),直到簇中心稳定，或者达到迭代次数。

总结与思考

总结

MinibatchKmeans为了解决Kmeans面对大数据量的效率问题，提出来的一种优化方案。通过有放回的随机抽样小批次样本Kmeans聚类，可以高效聚类。经验证明，这种在小批次数据上的Kmeans聚类和在全量数据集上Kmeans聚类得到得质心偏差不大。 全量Kmeans
如上图所示，作者在5万个全量样本使用Kmeans聚类得到的质心和执行时间。而当使用MinibatchKmeans聚类，Batchsize设置为1000时聚类效果如下图所示： 小批量Kmeans
可以看到，两种聚类得到的质心偏差不大，但是后者花费的时间少了很多。

思考

• MiniBatchKmeans适合做为增量聚类算法吗？
  由于需要指定聚类数量，所以当新来的Batch中样本发生了较大的漂移时，算法不会迭代得到新的类别，所以会破坏已经聚好的类簇质量。
• MiniBatchKmeans的batchsize如何设置？
  batchsize的大小结合有放回随机抽样的特点，存在较小batchsize抽样得到的样本子集反应不出全量样本的分布。针对这一问题个人认为有两种解决方案：

1. 增大batchsize，这个就比较好理解；
2. 通过多次抽样，取多次聚类效果的平均值（类似于集成学习中的Bagging）。

参考资料

1. https://zhuanlan.zhihu.com/p/116399159