K-Means实现mini-batch online learning的原理是什么?

  统计/机器学习 无监督学习    浏览次数: 255
1

K-Means实现mini-batch online learning的原理是什么?

被面试官问到了,这个概念没怎么接触过。谢谢!

----2018.10.21更新----

我有个后续问题在这里:关于online KMeans步骤中成员更新分类的问题?

 

lllinnn   2018-10-01 10:57



   1个回答 
4

mini batch K means的原始论文Web-Scale K-Means Clustering


每次数据只随机取一个mini batch$M$。第13行的公式$c\leftarrow (1-\eta)c+\eta x$,其中第一项$(1-\eta)c$是momentum,第二项$\eta x$是每个数据点带来的改变量,相当于每个点提供的gradient,$\eta$是learning rate。所以相当于是带momentum的minibatch gradient descent。注意,比较一下一般不带momentum的batch Kmeans,第13行应该改为$c\leftarrow \sum_{x_i \in S_c}\frac{x_i}{N_c}$,也就是cluster中所有数据点的均值为中心点。

原文并没有从原理或理论上证明mini-batch Kmeans等价于Kmeans。事实上可能并不等价。作者的动机是


我理解是batch gradient descent是每个batch有所有数据点,minibatch是每个batch有随机M个数据点,SGD是每个batch只有一个数据点。对于随机噪音batch > minibatch> SGD。对于计算量batch < minibatch< SGD。取一个中庸之道,就是minibatch。

论文中结果也说明minibatch(蓝色)收敛最快,效果也相近于Batch Kmeans。


SofaSofa数据科学社区 DS面经 问答 实战

Zealing   2018-10-02 00:50

谢谢你的回答。$c\leftarrow (1−\eta)c+\eta x$这一步应该就是重新更新centroid吧,跟直接计算所有点的centroid的结果是等价的吧 - lllinnn   2018-10-02 10:36
假设原来centroid为c1,现在所有点计算的centroid为c2,那么真正更新的c是c1和c2间的一点。c到c1的距离就是momentum项。其实算法里描述的和我说的还有点出入,但思路就是这样。 - Zealing   2018-10-02 12:02


  相关主题

通俗地解释c-means以及fuzzy c-means是什么意思   1回答

如何用K Means做异常点检测?   3回答

K Means初始点必须是样本中的点吗   2回答

Jenks和K Means在一维数据时,是不是等价的?   2回答

关于online KMeans步骤中成员更新分类的问题?   1回答

关于小批量K均值(mini-batch K Means)的问题   3回答

k-medoids和k-means区别   3回答

K-MEANS初始点选择的问题   2回答

K-means怎么选K?   6回答

二分法K Means的算法是什么?和普通的K Means有什么区别?   2回答

为什么K Means算法对样本的输入顺序比较敏感?   2回答

进行K-Means聚类前,需要对数据做怎样的预处理?   1回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!