论文标题
在线$ k $ -means的融合
Convergence of online $k$-means
论文作者
论文摘要
我们证明，对于从分布中的流数据执行的$ k $ -MEANS算法的通用类别的渐近融合：中心渐近地收敛到$ K $ - 米恩斯成本函数的一组固定点。为此，我们表明在线$ k $ - 分配上的分配可以解释为具有随机学习率计划的随机梯度下降。然后，我们通过扩展在优化文献中用于处理中心特定学习率可能取决于中心的过去轨迹的设置的技术来证明融合。
We prove asymptotic convergence for a general class of $k$-means algorithms performed over streaming data from a distribution: the centers asymptotically converge to the set of stationary points of the $k$-means cost function. To do so, we show that online $k$-means over a distribution can be interpreted as stochastic gradient descent with a stochastic learning rate schedule. Then, we prove convergence by extending techniques used in optimization literature to handle settings where center-specific learning rates may depend on the past trajectory of the centers.
