我们提出了首个**迷你批次核 k 均值算法**，与全批次算法相比，该算法的运行时间提升了一个数量级。我们算法的单次迭代需要 $\widetilde{O}(kb^2)$ 的时间，显著快于全批次核 k 均值算法所需的 $O(n^2)$ 时间，其中 $n$ 是数据集大小，$b$ 是批次大小。大量的实验表明，我们的算法在保持质量几乎无损的情况下，始终能实现 10-100 倍的加速，解决了核 k 均值算法在实践中因运行时间过长而难以推广的问题。我们进一步通过理论分析补充了这些结果，在提前停止条件下证明了，当批次大小为 $\widetilde{\Omega}(\max \{\gamma^{4}, \gamma^{2}\} \cdot \epsilon^{-2})$ 时，该算法以高概率在 $O(\gamma^2/\epsilon)$ 次迭代内终止，其中 $\gamma$ 是特征空间中点的范数上限，$\epsilon$ 是终止阈值。我们的分析适用于任何合理的中心初始化，当使用 k-means++ 初始化时，该算法在期望意义上实现了 $O(\log k)$ 的近似比。对于归一化核，例如高斯核或拉普拉斯核，$\gamma=1$ 成立。当取 $\epsilon = O(1)$ 和 $b=\Theta(\log n)$ 时，该算法在 $O(1)$ 次迭代内终止，每次迭代的运行时间为 $\widetilde{O}(k)$。