用均匀采样提升k均值聚类的随机与量子算法速度
Provably faster randomized and quantum algorithms for $k$-means clustering via uniform sampling
- 采用均匀采样替代传统按数据范数采样，保留问题对称性
- 算法最坏情况时间复杂度显著优于已有工作，依赖对数级数据点数量
- 适合追求理论性能极限或研究量子机器学习的学者
k均值算法（Lloyd算法）是广泛使用的无监督聚类方法。其主要瓶颈在于每次迭代需线性时间处理所有数据点，在大数据场景下开销巨大。近期工作提出量子及量子启发式经典算法，可在仅对数时间复杂度内近似局部聚类结果（依赖于数据相关参数）[q-means: A quantum algorithm for unsupervised machine learning, Kerenidis et al., NeurIPS 2019；Do you know what q-means?, Cornelissen et al., QTML 2025]。本文提出一种简单的随机小批量k均值算法，以及受其启发的量子算法。我们证明，这些算法在最坏情况下的保证可显著优于先前工作的界。改进源于对均匀采样的精心使用，该方法保留了传统算法中未被保持的k均值问题对称性。
原文摘要 · Abstract (English)
The $k$-means algorithm (Lloyd's algorithm) is a widely used method for clustering unlabeled data. A key bottleneck of the $k$-means algorithm is that each iteration requires time linear in the number of data points, which can be expensive in big data applications. This was improved in recent works proposing quantum and quantum-inspired classical algorithms to approximate the $k$-means algorithm locally, in time depending only logarithmically on the number of data points (along with data dependent parameters) [q-means: A quantum algorithm for unsupervised machine learning, Kerenidis, Landman, Luongo, and Prakash, NeurIPS 2019; Do you know what $q$-means?, Cornelissen, Doriguello, Luongo, Tang, QTML 2025]. In this work, we describe a simple randomized mini-batch $k$-means algorithm and a quantum algorithm inspired by the classical algorithm. We demonstrate that the worst case guarantees of these algorithms can significantly improve upon the bounds for algorithms in prior work. Our improvements are due to a careful use of uniform sampling, which preserves certain symmetries of the $k$-means problem that are not preserved in previous algorithms that use data norm-based sampling.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。